37 } |
37 } |
38 |
38 |
39 /// experimental topsort, |
39 /// experimental topsort, |
40 /// I think the final version will work as an iterator |
40 /// I think the final version will work as an iterator |
41 /// if the graph is not a acyclic, the na pre-topological order is obtained |
41 /// if the graph is not a acyclic, the na pre-topological order is obtained |
42 /// (see Schrijver's book) |
42 /// (see Schrijver's book). |
43 template<typename Graph> |
43 /// PredMap have to be a writtable node-map. |
44 void topSort(const Graph& g, std::list<typename Graph::Node>& l) { |
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 l.clear(); |
51 l.clear(); |
46 typedef typename Graph::template NodeMap<bool> ReachedMap; |
52 typedef typename Graph::template NodeMap<bool> ReachedMap; |
|
53 typedef typename Graph::template NodeMap<bool> ExaminedMap; |
47 ReachedMap reached(g/*, false*/); |
54 ReachedMap reached(g/*, false*/); |
|
55 ExaminedMap examined(g/*, false*/); |
48 DfsIterator<Graph, ReachedMap> dfs(g, reached); |
56 DfsIterator<Graph, ReachedMap> dfs(g, reached); |
49 FOR_EACH_LOC(typename Graph::NodeIt, n, g) { |
57 FOR_EACH_LOC(typename Graph::NodeIt, n, g) { |
50 if (!reached[n]) { |
58 if (!reached[n]) { |
51 dfs.pushAndSetReached(n); |
59 dfs.pushAndSetReached(n); |
|
60 pred.set(n, INVALID); |
52 while (!dfs.finished()) { |
61 while (!dfs.finished()) { |
53 ++dfs; |
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 if (dfs.isANodeExamined()) { |
75 if (dfs.isANodeExamined()) { |
55 l.push_back(dfs.aNode()); |
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 } //namespace hugo |
84 } //namespace hugo |
62 |
85 |
63 #endif //HUGO_BFS_DFS_MISC_H |
86 #endif //HUGO_BFS_DFS_MISC_H |