# User:CalebKennedy/LabeledGraph

### From OpenWetWare

**C++ LabledGraph<VertexType, EdgeType>**

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

**Public methods:**

LabeledGraph constructors & destructor | methods to allocate, copy, and deallocate LabeledGraphs | |

LabeledGraph operators | assign LabeledGraphs | |

size | returns number of edges | |

order | returns number of vertices | |

capacity | returns the maximum number of vertices that a graph can hold | |

getEdgeSet | returns set of edges | |

insertEdge | insert labeled edge between two labeled vertices | |

insertVertex | insert labeled vertex into graph | |

density | returns the graph density measure | |

eraseEdge | erase edge | |

expand | perform graph expansion | |

searchDepthFirst | depth-first graph traversal with heuristic backtracking | |

begin | returns an iterator to the first vertex in the graph | |

end | returns an iterator just past the last vertex in the graph | |

complement | construct complement graph | |

lineGraph | construct line graph | |

productGraph | construct product graph |

**Friends:**

adjacent | returns true if two vertices are connected by an edge | |

getEdge | returns a pointer to the edge connecting two vertices, else returns NULL | |

clique | returns true if vertex list (path) constitutes a clique | |

graphSimilarity | returns graph similarity measure |

**LabeledGraph constructors & destructor**

LabeledGraph(void)

LabeledGraph(const unsigned long&, const bool&)

LabeledGraph(const LabeledGraph&)

~LabeledGraph(void)

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.

**size**

unsigned long size(void) const

**order**

unsigned long order(void) const

**capacity**

unsigned long capacity(void) const

**getEdgeSet**

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.

**insertEdge**

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.

**insertVertex**

virtual const_iterator insertVertex(const_iterator)

virtual const_iterator insertVertex(const VertexType&)

**density**

double density(void) const

**eraseEdge**

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.

**expand**

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.

**searchDepthFirst**

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.

**begin**

Vertex::iterator begin(void) const

**end**

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

rootIterator++;

}

**complement**

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.

**productGraph**

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

**adjacent**

friend bool adjacent(const_iterator, const_iterator)

**getEdge**

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

**clique**

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.

**graphSimilarity**

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

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