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