Renamed simann_test.cc to simann_demo.cc.
2 #ifndef LEMON_BFS_DFS_MISC_H
3 #define LEMON_BFS_DFS_MISC_H
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 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.
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) {
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();
36 if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
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.
57 template<typename Graph, typename PredMap>
59 topSort(const Graph& g, std::list<typename Graph::Node>& l,
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) {
69 dfs.pushAndSetReached(n);
71 while (!dfs.finished()) {
73 if (dfs.isBNodeNewlyReached()) {
74 ///\bug lemon 0.2-ben Edge kell
75 pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));
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));
85 if (dfs.isANodeExamined()) {
86 l.push_back(dfs.aNode());
87 examined.set(dfs.aNode(), true);
97 #endif //LEMON_BFS_DFS_MISC_H