User:CalebKennedy/NewPage

<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="#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="#dfs">searchDepthFirst</A><TD><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> <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 (path) constitutes a <A href="http://mathworld.wolfram.com/Clique.html">clique</A> <TR><TH><TD><A href="#sim">graphSimilarity</A>                                    <TD>returns graph-based 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 graph with default number of vertices (MAXVERT = 1000) and zero edges <A name="oper">LabeledGraph operators</A> 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>

User:CalebKennedy/NewPage

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

research

Tools