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
getEdgeSetreturns set of edges
insertEdgeinsert labeled edge between two labeled vertices
insertVertexinsert labeled vertex into graph
searchDepthFirstdepth-first graph traversal with heuristic backtracking
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-based similarity measure

LabeledGraph constructors & destructor

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

The default LabeledGraph constructor creates an undirected graph with default number of vertices (MAXVERT = 1000) and zero edges

LabeledGraph operators

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

The addition operator performs a graph union.


unsigned long size(void) const


unsigned long order(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&)


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.


LabeledGraph& lineGraph(void) const


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.

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&)

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).

Personal tools