OMCGraph.h

//-----------------------------------------------------------------------------
//
// Module:       OMCGraph.h
//
// Author:       Feng Xie -- xief@mcmaster.ca
//
// Discription:  Graph algorithms.
//
// Todo:         *) Get more efficient data structure and algorithms for 
//                  diameter computation.
//               *) More efficient implementation of triangle counting.
//               *) General alogirhtm for n-gon counting.
//
// Change log:
//   09-06-26    Created.
//
//-----------------------------------------------------------------------------

#ifndef OMC_GRAPH_H
#define OMC_GRAPH_H

#include "Core.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

namespace omc 
{
  // Undirected and unweighted graph used to represent polytope skeleton.
  class OMCGraph 
  {
    // Output stream overloading.
    friend std::ostream & operator<< (std::ostream &, const OMCGraph &);

  public:

    enum state { unvisited, discovered, finished };

    OMCGraph (size_t);               // constructor
    
    ~OMCGraph () {};                 // destructor

    size_t getNumVertices () const;  // number of vertices in the graph

    size_t getNumEdges () const;     // number of edges in the graph
    
    void addEdge (index_t, index_t); // add an edge

    size_t diameter () const;        // compute the diameter

    size_t numTriangles () const;    // count triangles

    size_t num4gons () const;        // count 4-gons

    size_t num5gons () const;        // count 5-gons
    
  private:
    size_t m_numEdges;

    std::vector <std::vector <bool> > m_AM; // adjacency matrix

  }; // class OMCGraph

  inline OMCGraph::OMCGraph (size_t n)
    : m_numEdges (0), m_AM (n, std::vector<bool> (n, false))
  {
    for (index_t i=0; i<n; i++) 
      m_AM[i][i] = true;
  }

  inline size_t OMCGraph::getNumVertices () const {
    return m_AM.size();
  }

  inline size_t OMCGraph::getNumEdges () const {
    return m_numEdges;
  }

  inline void OMCGraph::addEdge (index_t i, index_t j) {
    if (i >= m_AM.size() || j >= m_AM.size())
      throw OMCException ("Invalid vertex", "OMCGraph::addEdge()");
        
    m_numEdges++;
    m_AM[i][j] = m_AM[j][i] = true;
  }

}; // namespace omc

#endif // OMC_GRAPH_H

---