graph.h

Go to the documentation of this file.
00001 // -*- c-basic-offset: 4 -*-
00027 #ifndef _HUGIN_MATH_GRAPH_H
00028 #define _HUGIN_MATH_GRAPH_H
00029 
00030 #include <vector>
00031 #include <set>
00032 #include <queue>
00033 
00034 #include <hugin_utils/stl_utils.h>
00035 
00036 
00037 namespace hugin_utils
00038 {
00039 
00040 
00041     // some typedefs for graphs represented with stl stuff.
00042     typedef std::vector<int> AdjList;
00043     typedef std::vector<AdjList> AdjListGraph;
00044 
00050     void findSubGraphs(AdjListGraph & graph,
00051                        std::vector<int> & subgraphStart);
00052 
00053         
00054     struct GraphEdge
00055     {
00056         GraphEdge(int a, int b)
00057             {
00058                 // insert in order to be able to compare easily
00059                 if (a < b) {
00060                     n1 = a;
00061                     n2 = b;
00062                 } else {
00063                     n1 = b;
00064                     n2 = a;
00065                 }
00066             };
00067         bool operator==(const GraphEdge & o) const
00068             { return ( n1 == o.n1 && n2 == o.n2); }
00069         bool operator<(const GraphEdge & o) const
00070             {
00071                 return n1 < o.n1 || (!(o.n1 < n1) && n2 < o.n2);
00072             }
00073         int n1;
00074         int n2;
00075     };
00076         
00080     template<class FUNCTOR>
00081     void traverseEdges(const AdjListGraph & graph,
00082                        int startNode,
00083                        FUNCTOR & visitor)
00084     {
00085         DEBUG_DEBUG("start: " << startNode);
00086         // keep track of visited nodes
00087         std::set<GraphEdge>visited;
00088 
00089         // queue of nodes that need to be visited
00090         std::queue<int> nextNodes;
00091         nextNodes.push(startNode);
00092         // as long as we can traverse further
00093         while(nextNodes.size() != 0) {
00094             // current node
00095             int cNode = nextNodes.front();
00096             nextNodes.pop();
00097             DEBUG_DEBUG("current node: " << cNode);
00098             // visit neighbours
00099             for (AdjList::const_iterator it = graph[cNode].begin();
00100                  it != graph[cNode].end(); ++it)
00101             {
00102                 GraphEdge e(cNode,*it);
00103                 if (! set_contains(visited, e)) {
00104                     // we have found edge that hasn't been visited
00105                     DEBUG_DEBUG("visiting link" << cNode << " to " << *it);
00106                     visited.insert(e);
00107                     visitor(cNode,*it);
00108                     // examine neighbours, add to the queue.
00109                     nextNodes.push(*it);
00110                 } else {
00111                     DEBUG_DEBUG("link already visited: " << cNode << " to " << *it);
00112                 }
00113             }
00114         }
00115     }
00116 
00117         
00120     template<class FUNCTOR>
00121     void traverseVertices(const AdjListGraph & graph,
00122                                 int start,
00123                                 FUNCTOR & visitor)
00124     {
00125         // keep track of visited nodes
00126         std::set<int>visited;
00127 
00128         // queue of nodes that need to be visited
00129         std::queue<int> nextNodes;
00130         nextNodes.push(start);
00131         // as long as we can traverse further
00132         while(nextNodes.size() != 0) {
00133             // current node
00134             int cNode = nextNodes.front();
00135             nextNodes.pop();
00136             // we have visited this node
00137             visitor(cNode);
00138             visited.insert(cNode);
00139             // visit neighbours
00140             for (AdjList::const_iterator it = graph[cNode].begin();
00141                  it != graph[cNode].end(); ++it)
00142             {
00143               if (! set_contains(visited, *it)) {
00144                     // examine neighbours, add to the subgraph and queue.
00145                     nextNodes.push(*it);
00146                 }
00147             }
00148         }
00149     }
00150 
00152     struct RemoveVisitor
00153     {
00154         RemoveVisitor(std::set<int> & vertices)
00155             : m_vert(vertices)
00156             { };
00157         void operator()(int vert1)
00158             {
00159                 m_vert.erase(vert1);
00160             }
00161         std::set<int> & m_vert;
00162     };
00163 
00164 
00166     struct TrackVisitor
00167     {
00168         void operator()(int vert1)
00169             {
00170                 m_vert.insert(vert1);
00171             }
00172         std::set<int> &  getTraversed()
00173             {
00174                 return m_vert;
00175             }
00176         std::set<int> m_vert;
00177     };
00178 
00179 
00180 } // namespace
00181 
00182 
00183 
00184 #endif // _H

Generated on Tue Sep 2 01:25:41 2014 for Hugintrunk by  doxygen 1.3.9.1