User:CalebKennedy/NewPage

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>

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>. <p>Public methods:

<A href="#const">LabeledGraph constructors & destructor</A>methods to allocate, copy, and deallocate LabeledGraphs                    
<A href="#oper">LabeledGraph operators</A>assign LabeledGraphs
<A href="#size">size</A>returns number of <A href="http://mathworld.wolfram.com/GraphEdge.html">edges</A>
<A href="#order">order</A>returns number of <A href="http://mathworld.wolfram.com/GraphVertex.html">vertices</A>
<A href="#ges">getEdgeSet</A>returns set of edges
<A href="#iedge">insertEdge</A>insert labeled edge between two labeled vertices
<A href="#ivert">insertVertex</A>insert labeled vertex into graph
<A href="#dfs">searchDepthFirst</A><A href="http://mathworld.wolfram.com/Depth-FirstTraversal.html">depth-first</A> graph traversal with <A href="http://en.wikipedia.org/wiki/Heuristic">heuristic</A> <A href="http://en.wikipedia.org/wiki/Backtracking">backtracking</A>
<A href="#lgraph">lineGraph</A>construct <A href="http://mathworld.wolfram.com/LineGraph.html">line graph</A>
<A href="#pgraph">productGraph</A>construct <A href="http://mathworld.wolfram.com/GraphProduct.html">product graph</A>

Friends:

<A href="#adj">adjacent</A>returns true if two vertices are connected by an edge
<A href="#getedge">getEdge</A>returns a pointer to the edge connecting two vertices, else returns NULL
<A href="#clique">clique</A>returns true if vertex list (path) constitutes a <A href="http://mathworld.wolfram.com/Clique.html">clique</A>
<A href="#sim">graphSimilarity</A>                                    returns graph-based similarity measure

<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 graph with default number of vertices (MAXVERT = 1000) and zero edges

<A name="oper">LabeledGraph operators</A> <p> LabeledGraph& operator=(const LabeledGraph&)
LabeledGraph& operator+=(const LabeledGraph&)
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="ges">getEdgeSet</A>

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 <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="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="lgraph">lineGraph</A>

LabeledGraph& lineGraph(void) const

<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: Cartesian, Categorical, Lexicographic, Modular, and Strong.

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

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

</HTML>