17 ReachedMap reached(g/*, false*/); |
17 ReachedMap reached(g/*, false*/); |
18 BfsIterator<Graph, ReachedMap> bfs(g, reached); |
18 BfsIterator<Graph, ReachedMap> bfs(g, reached); |
19 FOR_EACH_LOC(typename Graph::NodeIt, n, g) { |
19 FOR_EACH_LOC(typename Graph::NodeIt, n, g) { |
20 if (!reached[n]) { |
20 if (!reached[n]) { |
21 bfs.pushAndSetReached(n); |
21 bfs.pushAndSetReached(n); |
22 bool_map.set(n, false) { |
22 bool_map.set(n, false); |
23 while (!bfs.finished()) { |
23 while (!bfs.finished()) { |
24 if (bfs.isBNodeNewlyReached()) { |
24 if (bfs.isBNodeNewlyReached()) { |
25 bool_map.set(bfs.bNode())=!bfs.aNode(); |
25 bool_map.set(bfs.bNode())=!bfs.aNode(); |
26 } else { |
26 } else { |
27 if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) { |
27 if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) { |
28 return false; |
28 return false; |
29 } |
|
30 } |
29 } |
31 ++bfs; |
|
32 } |
30 } |
|
31 ++bfs; |
33 } |
32 } |
34 } |
33 } |
35 } |
34 } |
|
35 |
36 return true; |
36 return true; |
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 |
|
42 /// (see Schrijver's book) |
41 template<typename Graph> |
43 template<typename Graph> |
42 void topSort(Graph& g, std::list<typename Graph::Node>& l) { |
44 void topSort(const Graph& g, std::list<typename Graph::Node>& l) { |
43 l.clear(); |
45 l.clear(); |
44 typedef typename Graph::template NodeMap<bool> ReachedMap; |
46 typedef typename Graph::template NodeMap<bool> ReachedMap; |
45 ReachedMap reached(g/*, false*/); |
47 ReachedMap reached(g/*, false*/); |
46 DfsIterator<Graph, ReachedMap> dfs(g, reached); |
48 DfsIterator<Graph, ReachedMap> dfs(g, reached); |
47 FOR_EACH_LOC(typename Graph::NodeIt, n, g) { |
49 FOR_EACH_LOC(typename Graph::NodeIt, n, g) { |