# source:lemon-0.x/src/work/marci/bfs_dfs_misc.h@577:e8703f0a6e2f

Last change on this file since 577:e8703f0a6e2f was 577:e8703f0a6e2f, checked in by marci, 19 years ago

top-sort, dimacs mods.

File size: 2.5 KB
Line
1// -*- c++ -*-
2#ifndef HUGO_BFS_DFS_MISC_H
3#define HUGO_BFS_DFS_MISC_H
4
5#include <bfs_iterator.h>
6#include <for_each_macros.h>
7
8namespace hugo {
9
10  /// This function eat a read-write \c BoolMap& bool_map,
11  /// which have to work well up
12  /// to its \c set and \c operator[]() method. Thus we have to deal
13  /// very carefully with an uninitialized \c IterableBoolMap.
14  template<typename Graph, typename BoolMap>
15  bool isBipartite(const Graph& g, BoolMap& bool_map) {
16    typedef typename Graph::template NodeMap<bool> ReachedMap;
17    ReachedMap reached(g/*, false*/);
18    BfsIterator<Graph, ReachedMap> bfs(g, reached);
19    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
20      if (!reached[n]) {
21        bfs.pushAndSetReached(n);
22        bool_map.set(n, false);
23        while (!bfs.finished()) {
24          if (bfs.isBNodeNewlyReached()) {
25            bool_map.set(bfs.bNode())=!bfs.aNode();
26          } else {
27            if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
28              return false;
29            }
30          }
31          ++bfs;
32        }
33      }
34    }
35
36    return true;
37  }
38
39  /// experimental topsort,
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).
43  /// PredMap have to be a writtable node-map.
44  /// If the graph is directed and not acyclic,
45  /// then going back from the returned node via the pred information, a
46  /// cycle is obtained.
47  template<typename Graph, typename PredMap>
48  typename Graph::Node
49  topSort(const Graph& g, std::list<typename Graph::Node>& l,
50               PredMap& pred) {
51    l.clear();
52    typedef typename Graph::template NodeMap<bool> ReachedMap;
53    typedef typename Graph::template NodeMap<bool> ExaminedMap;
54    ReachedMap reached(g/*, false*/);
55    ExaminedMap examined(g/*, false*/);
56    DfsIterator<Graph, ReachedMap> dfs(g, reached);
57    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
58      if (!reached[n]) {
59        dfs.pushAndSetReached(n);
60        pred.set(n, INVALID);
61        while (!dfs.finished()) {
62          ++dfs;
63          if (dfs.isBNodeNewlyReached()) {
64            ///\bug hugo 0.2-ben Edge kell
65            pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));
66          } else {
67            ///\bug ugyanaz
68            if (g.valid(typename Graph::OutEdgeIt(dfs)) &&
69                !examined[dfs.bNode()]) {
70              ///\bug hugo 0.2-ben Edge kell
71              pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs));
72              return dfs.aNode();
73            }
74          }
75          if (dfs.isANodeExamined()) {
76            l.push_back(dfs.aNode());
77            examined.set(dfs.aNode(), true);
78          }
79        }
80      }
81    }
82    return INVALID;
83  }
84} //namespace hugo
85
86#endif //HUGO_BFS_DFS_MISC_H
Note: See TracBrowser for help on using the repository browser.