User:CalebKennedy/LabeledGraph

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

C++ LabledGraph<VertexType, EdgeType> 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>. Public methods: <TABLE border="1"> <TR><TH><TD><A href="#const">LabeledGraph constructors & destructor</A><TD>methods to allocate, copy, and deallocate LabeledGraphs                   <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> Friends: <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>                                         <TD>returns graph similarity measure </TABLE>

<A name="const">LabeledGraph constructors & destructor</A> LabeledGraph(void) LabeledGraph(const unsigned long&, const bool&) LabeledGraph(const LabeledGraph&) ~LabeledGraph(void) The default LabeledGraph constructor creates an undirected <A href="http://mathworld.wolfram.com/NullGraph.html">null graph</A> with default vertex capacity (MAXVERT = 1000) . <A name="oper">LabeledGraph operators</A> LabeledGraph& operator=(const LabeledGraph&) virtual LabeledGraph& operator+=(const LabeledGraph&) virtual LabeledGraph operator+(const LabeledGraph&) const The addition operator performs a <A href="http://mathworld.wolfram.com/GraphUnion.html">graph union</A>. <A name="size">size</A> unsigned long size(void) const <A name="order">order</A> unsigned long order(void) const <A name="cap">capacity</A> unsigned long capacity(void) const <A name="ges">getEdgeSet</A> set<edge::type> getEdgeSet(void) const 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. <A name="iedge">insertEdge</A> virtual void insertEdge(const_iterator, const_iterator, EdgeType* const) 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. <A name="ivert">insertVertex</A> virtual const_iterator insertVertex(const_iterator) virtual const_iterator insertVertex(const VertexType&) <A name="density">density</A> double density(void) const <A name="eedge">eraseEdge</A> 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. <A name="exp">expand</A> 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 <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. <A name="dfs">searchDepthFirst</A> virtual void searchDepthFirst(Pruner&) <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. <A name="begin">begin</A> Vertex::iterator begin(void) const <A name="end">end</A> 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++; } <A name="comp">complement</A> virtual LabeledGraph& complement(EdgeType* (*) (const EdgeType* const)) const 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. <A name="lgraph">lineGraph</A> LabeledGraph& lineGraph(void) const Line graph construction is supported for undirected graphs only. <A name="pgraph">productGraph</A> 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: <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. e.g., LabeledGraph<VertexType, EdgeType> product = graph1.productGraph(Cartesian, graph2); <A name="adj">adjacent</A> friend bool adjacent(const_iterator, const_iterator) <A name="getedge">getEdge</A> friend Vertex::Edge* getEdge(const_iterator, const_iterator) 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:       1. EdgeType* label (the edge label) and       2. Vertex* target (the vertex adjacent to this vertex). <A name="clique">clique</A> friend bool clique(const CliqueFinder&, unsigned long&) 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. <A name="sim">graphSimilarity</A> 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 <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). 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. </html> --CalebKennedy 21:46, 18 April 2007 (EDT)

User:CalebKennedy/LabeledGraph

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

research

Tools