User:CalebKennedy/LabeledGraph

From OpenWetWare
Jump to: navigation, search

<html> <HEAD> <TITLE> C++ LabeledGraph </TITLE> <META NAME="Generator" CONTENT="EditPlus"> <META NAME="Author" CONTENT=""> <META NAME="Keywords" CONTENT=""> <META NAME="Description" CONTENT=""> </HEAD>

<BODY>

<p><b>C++ LabledGraph&lt;VertexType, EdgeType&gt;</b></p> <p>LabeledGraph is a C++ template class for programming with simple <A href="http://mathworld.wolfram.com/Graph.html">graphs</A> and <A href="http://mathworld.wolfram.com/DirectedGraph.html">digraphs</A>. <p><b>Public methods:</b></p> <TABLE border="1"> <TR><TH><TD><A href="#const">LabeledGraph constructors & destructor</A><TD>methods to allocate, copy, and deallocate LabeledGraphs&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <TR><TH><TD><A href="#oper">LabeledGraph operators</A><TD>assign LabeledGraphs <TR><TH><TD><A href="#size">size</A><TD>returns number of <A href="http://mathworld.wolfram.com/GraphEdge.html">edges</A> <TR><TH><TD><A href="#order">order</A><TD>returns number of <A href="http://mathworld.wolfram.com/GraphVertex.html">vertices</A> <TR><TH><TD><A href="#cap">capacity</A><TD>returns the maximum number of vertices that a graph can hold <TR><TH><TD><A href="#ges">getEdgeSet</A><TD>returns set of edges <TR><TH><TD><A href="#iedge">insertEdge</A><TD>insert labeled edge between two labeled vertices <TR><TH><TD><A href="#ivert">insertVertex</A><TD>insert labeled vertex into graph <TR><TH><TD><A href="#density">density</A><TD>returns the <A href="http://en.wikipedia.org/wiki/Sparse_graph">graph density</A> measure <TR><TH><TD><A href="#eedge">eraseEdge</A><TD>erase edge <TR><TH><TD><A href="#exp">expand</A><TD>perform graph expansion <TR><TH><TD><A href="#dfs">searchDepthFirst</A><TD><A href="http://mathworld.wolfram.com/Depth-FirstTraversal.html">depth-first</A> graph <A href="http://en.wikipedia.org/wiki/Tree_traversal">traversal</A> with <A href="http://en.wikipedia.org/wiki/Heuristic">heuristic</A> <A href="http://en.wikipedia.org/wiki/Backtracking">backtracking</A> <TR><TH><TD><A href="#begin">begin</A><TD>returns an iterator to the first vertex in the graph <TR><TH><TD><A href="#end">end</A><TD>returns an iterator just past the last vertex in the graph <TR><TH><TD><A href="#comp">complement</A><TD>construct <A href="http://mathworld.wolfram.com/GraphComplement.html">complement graph</A> <TR><TH><TD><A href="#lgraph">lineGraph</A><TD>construct <A href="http://mathworld.wolfram.com/LineGraph.html">line graph</A> <TR><TH><TD><A href="#pgraph">productGraph</A><TD>construct <A href="http://mathworld.wolfram.com/GraphProduct.html">product graph</A> </TABLE> <p><b>Friends:</b></p> <TABLE border="1"> <TR><TH><TD><A href="#adj">adjacent</A><TD>returns true if two vertices are connected by an edge <TR><TH><TD><A href="#getedge">getEdge</A><TD>returns a pointer to the edge connecting two vertices, else returns NULL <TR><TH><TD><A href="#clique">clique</A><TD>returns true if vertex list (<A href="http://en.wikipedia.org/wiki/Path_(graph_theory)">path</A>) constitutes a <A href="http://mathworld.wolfram.com/Clique.html">clique</A> <TR><TH><TD><A href="#sim">graphSimilarity</A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<TD>returns graph similarity measure </TABLE><br>

<A name="const"><b>LabeledGraph constructors & destructor</b></A> <p><font face="Courier New"> LabeledGraph(void)<br> LabeledGraph(const unsigned long&, const bool&)<br> LabeledGraph(const LabeledGraph&)<br> ~LabeledGraph(void)<br> </font></p> <p>The default LabeledGraph constructor creates an undirected <A href="http://mathworld.wolfram.com/NullGraph.html">null graph</A> with default vertex capacity (<font face="Courier New">MAXVERT = 1000</font>) .<br><br> <A name="oper"><b>LabeledGraph operators</b></A> <p><font face="Courier New"> LabeledGraph& operator=(const LabeledGraph&)<br> virtual LabeledGraph& operator+=(const LabeledGraph&)<br> virtual LabeledGraph operator+(const LabeledGraph&) const<br> </font></p> <p>The addition operator performs a <A href="http://mathworld.wolfram.com/GraphUnion.html">graph union</A>.</p> <A name="size"><b>size</b></A> <p><font face="Courier New"> unsigned long size(void) const<br> </font></p> <A name="order"><b>order</b></A> <p><font face="Courier New"> unsigned long order(void) const<br> </font></p> <A name="cap"><b>capacity</b></A> <p><font face="Courier New"> unsigned long capacity(void) const<br> </font></p> <A name="ges"><b>getEdgeSet</b></A> <p><font face="Courier New"> set&lt;edge::type&gt; getEdgeSet(void) const<br> </font></p> <p>Returns a unique ordered set of edges. The data type named edge::type defines a <A href="http://openwetware.org/wiki/User:CalebKennedy/Couple">couple</A> (inherited from std::pair) of vertex pointers and a pointer to their associated edge label (or <A href="http://en.wikipedia.org/wiki/Null_%28computer%29" >NULL</A> 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.</p> <A name="iedge"><b>insertEdge</b></A> <p><font face="Courier New"> virtual void insertEdge(const_iterator, const_iterator, EdgeType* const)<br> </font></p> <p>Inserts a labeled edge between two vertices (pointed to by const_iterators). <A href="http://mathworld.wolfram.com/Multigraph.html">Multigraphs</A> and <A href="http://mathworld.wolfram.com/GraphLoop.html">graph loops</A> are not supported; attempts to construct them will result in errors and program termination.</p> <A name="ivert"><b>insertVertex</b></A> <p><font face="Courier New"> virtual const_iterator insertVertex(const_iterator)<br> virtual const_iterator insertVertex(const VertexType&)<br> </font></p> <A name="density"><b>density</b></A> <p><font face="Courier New"> double density(void) const<br> </font></p> <A name="eedge"><b>eraseEdge</b></A> <p><font face="Courier New"> virtual void eraseEdge(const_iterator, const_iterator)<br> </font></p> <p>Erases the edge connecting the two vertices specified as parameters. No action is taken if the two vertices are not adjacent.</p> <A name="exp"><b>expand</b></A> <p><font face="Courier New"> const_iterator expand(const_iterator, const_iterator, const VertexType&, EdgeType* const, EdgeType* const)<br> </font></p> <p>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 <A href="http://en.wikipedia.org/wiki/Subdivision_%28graph_theory%29#Subdivisions">subdivision</A>). 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 <A href="http://en.wikipedia.org/wiki/Null_%28computer%29">NULL</A> value.</p> <A name="dfs"><b>searchDepthFirst</b></A> <p><font face="Courier New"> virtual void searchDepthFirst(Pruner&)<br> </font></p> <p><A href="http://openwetware.org/wiki/User:CalebKennedy/Pruner">Pruner</A> is an abstract template <A href="http://www.tutok.sk/fastgl/callback.html">functor</A> 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.</p> <A name="begin"><b>begin</b></A> <p><font face="Courier New"> Vertex::iterator begin(void) const<br> </font></p> <A name="end"><b>end</b></A> <p><font face="Courier New"> Vertex::iterator end(void) const<br> </font></p> <p>Here's an example piece of code that uses iterators to print all vertex labels in a LabeledGraph: <br><br> <font face="Courier New">Vertex&lt;VertexType, EdgeType&gt;::iterator rootIterator = graph1.begin();<br> while (rootIterator != graph1.end());<br> {<br> &nbsp;&nbsp;&nbsp;&nbsp;cout << *rootIterator->target->label << endl; // Dereference label pointer<br> &nbsp;&nbsp;&nbsp;&nbsp;rootIterator++;<br> }<br> </font></p> <A name="comp"><b>complement</b></A> <p><font face="Courier New"> virtual LabeledGraph& complement(EdgeType* (*) (const EdgeType* const)) const<br> </font></p> <p>For undirected graphs, this method constructs the complement graph with all edge labels assigned a <A href="http://en.wikipedia.org/wiki/Null_%28computer%29">NULL</A> 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.<p> <A name="lgraph"><b>lineGraph</b></A> <p><font face="Courier New"> LabeledGraph& lineGraph(void) const<br> </font></p> <p>Line graph construction is supported for undirected graphs only.</p> <A name="pgraph"><b>productGraph</b></A> <p><font face="Courier New"> LabeledGraph& productGraph(bool (*) (const edge::type&, const edge::type&), const LabeledGraph&) const<br> </font></p> <p>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: <A href="http://mathworld.wolfram.com/GraphCartesianProduct.html">Cartesian</A>, <A href="http://mathworld.wolfram.com/GraphCategoricalProduct.html">Categorical</A>, <A href="http://mathworld.wolfram.com/GraphLexicographicProduct.html">Lexicographic</A>, Modular, and <A href="http://mathworld.wolfram.com/GraphStrongProduct.html">Strong</A>. Product graph construction is supported for undirected graphs only.</p> <p>e.g., <font face="Courier New">LabeledGraph&lt;VertexType, EdgeType&gt; product = graph1.productGraph(Cartesian, graph2);</font></p> <A name="adj"><b>adjacent</b></A> <p><font face="Courier New"> friend bool adjacent(const_iterator, const_iterator)<br> </font></p> <A name="getedge"><b>getEdge</b></A> <p><font face="Courier New"> friend Vertex::Edge* getEdge(const_iterator, const_iterator) </font></p> <p>Edge is a nested public struct defined within the <A href="http://openwetware.org/wiki/User:CalebKennedy/Vertex">Vertex</A> class. It has two public members:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1. EdgeType* label (the edge label) and<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2. Vertex* target (the vertex adjacent to this vertex).</p> <A name="clique"><b>clique</b></A> <p><font face="Courier New"> friend bool clique(const CliqueFinder&, unsigned long&) </font></p> <p>CliqueFinder is inherited from Finder, which is inherited from <A href="http://openwetware.org/wiki/User:CalebKennedy/Pruner">Pruner</A>. 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-<A href="http://en.wikipedia.org/wiki/Null_%28computer%29">NULL</A>) edges in the clique.</p> <A name="sim"><b>graphSimilarity</b></A> <p><font face="Courier New"> friend double graphSimilarity(const LabeledGraph&, const LabeledGraph&, const double&) </font></p> <p>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 <A href="http://mathworld.wolfram.com/GraphIsomorphism.html">graph isomorphism</A> common to a pair of graphs. graphSimilarity implements a version of the <A href="http://comjnl.oxfordjournals.org/cgi/content/abstract/45/6/631">RASCAL</A> 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).<br><br> </p>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: <i>Raymond JW et al. RASCAL: Calculation of graph similarity using maximum common edge subgraphs. The Computer Journal. 2002; 45(6):631-644</i>. </html> --CalebKennedy 21:46, 18 April 2007 (EDT)