# User:CalebKennedy/NewPage

### 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 | |

getEdgeSet | returns set of edges | |

insertEdge | insert labeled edge between two labeled vertices | |

insertVertex | insert labeled vertex into graph | |

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

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

**size**

unsigned long size(void) const

**order**

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

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

**lineGraph**

LabeledGraph& lineGraph(void) const

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

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

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