1 // -*- c++ -*- |
|
2 #ifndef LEMON_BFS_DFS_MISC_H |
|
3 #define LEMON_BFS_DFS_MISC_H |
|
4 |
|
5 /// \ingroup galgs |
|
6 /// \file |
|
7 /// \brief Miscellaneous algorithms using bfs and dfs. |
|
8 /// |
|
9 /// This file contains several algorithms using bfs and dfs. |
|
10 /// |
|
11 // ///\author Marton Makai |
|
12 |
|
13 #include <bfs_dfs.h> |
|
14 #include <for_each_macros.h> |
|
15 |
|
16 namespace lemon { |
|
17 |
|
18 /// This function eats 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 /// \ingroup galgs |
|
23 template<typename Graph, typename BoolMap> |
|
24 bool isBipartite(const Graph& g, BoolMap& bool_map) { |
|
25 typedef typename Graph::template NodeMap<bool> ReachedMap; |
|
26 ReachedMap reached(g/*, false*/); |
|
27 BfsIterator<Graph, ReachedMap> bfs(g, reached); |
|
28 FOR_EACH_LOC(typename Graph::NodeIt, n, g) { |
|
29 if (!reached[n]) { |
|
30 bfs.pushAndSetReached(n); |
|
31 bool_map.set(n, false); |
|
32 while (!bfs.finished()) { |
|
33 if (bfs.isBNodeNewlyReached()) { |
|
34 bool_map.set(bfs.bNode())=!bfs.aNode(); |
|
35 } else { |
|
36 if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) { |
|
37 return false; |
|
38 } |
|
39 } |
|
40 ++bfs; |
|
41 } |
|
42 } |
|
43 } |
|
44 |
|
45 return true; |
|
46 } |
|
47 |
|
48 /// experimental topsort, |
|
49 /// I think the final version will work as an iterator |
|
50 /// if the graph is not a acyclic, the na pre-topological order is obtained |
|
51 /// (see Schrijver's book). |
|
52 /// PredMap have to be a writtable node-map. |
|
53 /// If the graph is directed and not acyclic, |
|
54 /// then going back from the returned node via the pred information, a |
|
55 /// cycle is obtained. |
|
56 /// \ingroup galgs |
|
57 template<typename Graph, typename PredMap> |
|
58 typename Graph::Node |
|
59 topSort(const Graph& g, std::list<typename Graph::Node>& l, |
|
60 PredMap& pred) { |
|
61 l.clear(); |
|
62 typedef typename Graph::template NodeMap<bool> ReachedMap; |
|
63 typedef typename Graph::template NodeMap<bool> ExaminedMap; |
|
64 ReachedMap reached(g/*, false*/); |
|
65 ExaminedMap examined(g/*, false*/); |
|
66 DfsIterator<Graph, ReachedMap> dfs(g, reached); |
|
67 FOR_EACH_LOC(typename Graph::NodeIt, n, g) { |
|
68 if (!reached[n]) { |
|
69 dfs.pushAndSetReached(n); |
|
70 pred.set(n, INVALID); |
|
71 while (!dfs.finished()) { |
|
72 ++dfs; |
|
73 if (dfs.isBNodeNewlyReached()) { |
|
74 ///\bug lemon 0.2-ben Edge kell |
|
75 pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs)); |
|
76 } else { |
|
77 ///\bug ugyanaz |
|
78 if (g.valid(typename Graph::OutEdgeIt(dfs)) && |
|
79 !examined[dfs.bNode()]) { |
|
80 ///\bug lemon 0.2-ben Edge kell |
|
81 pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs)); |
|
82 return dfs.aNode(); |
|
83 } |
|
84 } |
|
85 if (dfs.isANodeExamined()) { |
|
86 l.push_back(dfs.aNode()); |
|
87 examined.set(dfs.aNode(), true); |
|
88 } |
|
89 } |
|
90 } |
|
91 } |
|
92 return INVALID; |
|
93 } |
|
94 |
|
95 } //namespace lemon |
|
96 |
|
97 #endif //LEMON_BFS_DFS_MISC_H |
|