Sorry, the other half of the move comes here.
2 #ifndef HUGO_BFS_DFS_MISC_H
3 #define HUGO_BFS_DFS_MISC_H
5 // ///\ingroup gwrappers
7 ///\brief Miscellaneous algorithms using bfs and dfs.
9 ///This file contains several algorithms using bfs and dfs.
11 // ///\author Marton Makai
14 #include <for_each_macros.h>
18 /// This function eat a read-write \c BoolMap& bool_map,
19 /// which have to work well up
20 /// to its \c set and \c operator[]() method. Thus we have to deal
21 /// very carefully with an uninitialized \c IterableBoolMap.
22 template<typename Graph, typename BoolMap>
23 bool isBipartite(const Graph& g, BoolMap& bool_map) {
24 typedef typename Graph::template NodeMap<bool> ReachedMap;
25 ReachedMap reached(g/*, false*/);
26 BfsIterator<Graph, ReachedMap> bfs(g, reached);
27 FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
29 bfs.pushAndSetReached(n);
30 bool_map.set(n, false);
31 while (!bfs.finished()) {
32 if (bfs.isBNodeNewlyReached()) {
33 bool_map.set(bfs.bNode())=!bfs.aNode();
35 if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
47 /// experimental topsort,
48 /// I think the final version will work as an iterator
49 /// if the graph is not a acyclic, the na pre-topological order is obtained
50 /// (see Schrijver's book).
51 /// PredMap have to be a writtable node-map.
52 /// If the graph is directed and not acyclic,
53 /// then going back from the returned node via the pred information, a
54 /// cycle is obtained.
55 template<typename Graph, typename PredMap>
57 topSort(const Graph& g, std::list<typename Graph::Node>& l,
60 typedef typename Graph::template NodeMap<bool> ReachedMap;
61 typedef typename Graph::template NodeMap<bool> ExaminedMap;
62 ReachedMap reached(g/*, false*/);
63 ExaminedMap examined(g/*, false*/);
64 DfsIterator<Graph, ReachedMap> dfs(g, reached);
65 FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
67 dfs.pushAndSetReached(n);
69 while (!dfs.finished()) {
71 if (dfs.isBNodeNewlyReached()) {
72 ///\bug hugo 0.2-ben Edge kell
73 pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));
76 if (g.valid(typename Graph::OutEdgeIt(dfs)) &&
77 !examined[dfs.bNode()]) {
78 ///\bug hugo 0.2-ben Edge kell
79 pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs));
83 if (dfs.isANodeExamined()) {
84 l.push_back(dfs.aNode());
85 examined.set(dfs.aNode(), true);
94 #endif //HUGO_BFS_DFS_MISC_H