Last change on this file since 771:ad7dff9ee2fd was 762:511200bdb71f, checked in by marci, 16 years ago

technical corrections

File size: 2.7 KB
Line
1// -*- c++ -*-
2#ifndef HUGO_BFS_DFS_MISC_H
3#define HUGO_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
16namespace hugo {
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 hugo 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 hugo 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 hugo
96
97#endif //HUGO_BFS_DFS_MISC_H
Note: See TracBrowser for help on using the repository browser.