Changeset 577:e8703f0a6e2f in lemon-0.x for src/work/marci/bfs_dfs_misc.h
- Timestamp:
- 05/07/04 13:57:34 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@753
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/bfs_dfs_misc.h
r552 r577 40 40 /// I think the final version will work as an iterator 41 41 /// if the graph is not a acyclic, the na pre-topological order is obtained 42 /// (see Schrijver's book) 43 template<typename Graph> 44 void topSort(const Graph& g, std::list<typename Graph::Node>& l) { 42 /// (see Schrijver's book). 43 /// PredMap have to be a writtable node-map. 44 /// If the graph is directed and not acyclic, 45 /// then going back from the returned node via the pred information, a 46 /// cycle is obtained. 47 template<typename Graph, typename PredMap> 48 typename Graph::Node 49 topSort(const Graph& g, std::list<typename Graph::Node>& l, 50 PredMap& pred) { 45 51 l.clear(); 46 52 typedef typename Graph::template NodeMap<bool> ReachedMap; 53 typedef typename Graph::template NodeMap<bool> ExaminedMap; 47 54 ReachedMap reached(g/*, false*/); 55 ExaminedMap examined(g/*, false*/); 48 56 DfsIterator<Graph, ReachedMap> dfs(g, reached); 49 57 FOR_EACH_LOC(typename Graph::NodeIt, n, g) { 50 58 if (!reached[n]) { 51 59 dfs.pushAndSetReached(n); 60 pred.set(n, INVALID); 52 61 while (!dfs.finished()) { 53 62 ++dfs; 63 if (dfs.isBNodeNewlyReached()) { 64 ///\bug hugo 0.2-ben Edge kell 65 pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs)); 66 } else { 67 ///\bug ugyanaz 68 if (g.valid(typename Graph::OutEdgeIt(dfs)) && 69 !examined[dfs.bNode()]) { 70 ///\bug hugo 0.2-ben Edge kell 71 pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs)); 72 return dfs.aNode(); 73 } 74 } 54 75 if (dfs.isANodeExamined()) { 55 76 l.push_back(dfs.aNode()); 77 examined.set(dfs.aNode(), true); 56 78 } 57 79 } 58 80 } 59 81 } 82 return INVALID; 60 83 } 61 84 } //namespace hugo
Note: See TracChangeset
for help on using the changeset viewer.