From OpenWetWare

Jump to: navigation, search

C++ LabeledGraph

C++ LabledGraph<VertexType, EdgeType>

LabeledGraph is a C++ template class for programming with simple graphs and digraphs.

Public methods:

LabeledGraph constructors & destructormethods to allocate, copy, and deallocate LabeledGraphs                  
LabeledGraph operatorsassign LabeledGraphs
sizereturns number of edges
orderreturns number of vertices
capacityreturns the maximum number of vertices that a graph can hold
getEdgeSetreturns set of edges
insertEdgeinsert labeled edge between two labeled vertices
insertVertexinsert labeled vertex into graph
densityreturns the graph density measure
eraseEdgeerase edge
expandperform graph expansion
searchDepthFirstdepth-first graph traversal with heuristic backtracking
beginreturns an iterator to the first vertex in the graph
endreturns an iterator just past the last vertex in the graph
complementconstruct complement graph
lineGraphconstruct line graph
productGraphconstruct product graph


adjacentreturns true if two vertices are connected by an edge
getEdgereturns a pointer to the edge connecting two vertices, else returns NULL
cliquereturns true if vertex list (path) constitutes a clique
graphSimilarity                                         returns graph similarity measure

LabeledGraph constructors & destructor

LabeledGraph(const unsigned long&, const bool&)
LabeledGraph(const LabeledGraph&)

The default LabeledGraph constructor creates an undirected null graph with default vertex capacity (MAXVERT = 1000) .

LabeledGraph operators

LabeledGraph& operator=(const LabeledGraph&)
virtual LabeledGraph& operator+=(const LabeledGraph&)
virtual LabeledGraph operator+(const LabeledGraph&) const

The addition operator performs a graph union.


unsigned long size(void) const


unsigned long order(void) const


unsigned long capacity(void) const


set<edge::type> getEdgeSet(void) const

Returns a unique ordered set of edges. The data type named edge::type defines a couple (inherited from std::pair) of vertex pointers and a pointer to their associated edge label (or NULL if the vertices are not adjacent). The class edge is privately defined within the LabeledGraph class; edge instantiations are therefore not available to the client.


virtual void insertEdge(const_iterator, const_iterator, EdgeType* const)

Inserts a labeled edge between two vertices (pointed to by const_iterators). Multigraphs and graph loops are not supported; attempts to construct them will result in errors and program termination.


virtual const_iterator insertVertex(const_iterator)
virtual const_iterator insertVertex(const VertexType&)


double density(void) const


virtual void eraseEdge(const_iterator, const_iterator)

Erases the edge connecting the two vertices specified as parameters. No action is taken if the two vertices are not adjacent.


const_iterator expand(const_iterator, const_iterator, const VertexType&, EdgeType* const, EdgeType* const)

This method performs a graph expansion by splicing a new vertex (of degree two) into the edge connecting the vertices specified by the first two parameters (this process is also known as subdivision). The new vertex is given the label specified by the third parameter and the two new undirected edges are given labels specified by the forth and fifth parameters, respectively. If edge label parameters are not given they will be assigned a NULL value.


virtual void searchDepthFirst(Pruner&)

Pruner is an abstract template functor that stores the vertices in the current traversed path. A virtual operator() allows application- and user-specific pruning methods defined in classes that inherit from Pruner.


Vertex::iterator begin(void) const


Vertex::iterator end(void) const

Here's an example piece of code that uses iterators to print all vertex labels in a LabeledGraph:

Vertex<VertexType, EdgeType>::iterator rootIterator = graph1.begin();
while (rootIterator != graph1.end());
    cout << *rootIterator->target->label << endl; // Dereference label pointer


virtual LabeledGraph& complement(EdgeType* (*) (const EdgeType* const)) const

For undirected graphs, this method constructs the complement graph with all edge labels assigned a NULL value. For digraphs, the graph complement method reverses the direction of adjacent vertices and transforms the edge labels according to the passed parameter--a user-defined function.


LabeledGraph& lineGraph(void) const

Line graph construction is supported for undirected graphs only.


LabeledGraph& productGraph(bool (*) (const edge::type&, const edge::type&), const LabeledGraph&) const

The first argument passed to productGraph defines a function that determines the adjacency between the set of node pairs in the product graph--returning true for adjacency and false for non-adjacency. There are 256 possible product graphs. LabeledGraph defines functions for very common types including: Cartesian, Categorical, Lexicographic, Modular, and Strong. Product graph construction is supported for undirected graphs only.

e.g., LabeledGraph<VertexType, EdgeType> product = graph1.productGraph(Cartesian, graph2);


friend bool adjacent(const_iterator, const_iterator)


friend Vertex::Edge* getEdge(const_iterator, const_iterator)

Edge is a nested public struct defined within the Vertex class. It has two public members:
      1. EdgeType* label (the edge label) and
      2. Vertex* target (the vertex adjacent to this vertex).


friend bool clique(const CliqueFinder&, unsigned long&)

CliqueFinder is inherited from Finder, which is inherited from Pruner. Its overloaded operator() finds the subgraph that corresponds to the maximal clique by using very simple heuristics to prune a depth-first traversal. The second parameter stores the number of real (non-NULL) edges in the clique.


friend double graphSimilarity(const LabeledGraph&, const LabeledGraph&, const double&)

Graph similarity can be defined in many ways and its particular definition is often application-specific. One convenient definition of graph similarity that is appropriate for a variety of applications involves finding the largest graph isomorphism common to a pair of graphs. graphSimilarity implements a version of the RASCAL algorithm based on finding the maximum common edge subgraph. The returned measure of graph similarity is a value between zero and one (a value of one meaning the two graphs are isomorphic).

The last parameter passed to the graphSimilarity method defines a minimal threshold similarity value. The calculation of minimal similarity between two labeled graphs is significantly less computationally intensive than the complete graph-based similarity measure. It can be used to reduce the time complexity of running many graph comparisons by rapidly filtering out those comparisons that do not meet a predefined minimal similarity measure. If the two graphs passed to the graphSimilarity method do not pass the filtering threshold an invalid similarity measure of -1.0 is returned. For algorithmic details see: Raymond JW et al. RASCAL: Calculation of graph similarity using maximum common edge subgraphs. The Computer Journal. 2002; 45(6):631-644. --CalebKennedy 21:46, 18 April 2007 (EDT)

Personal tools