# source:lemon-0.x/src/work/marci/bfs_dfs_misc.h@613:b5b5c4ae5107

Last change on this file since 613:b5b5c4ae5107 was 604:4acd273c3009, checked in by marci, 17 years ago

some docs

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 gwrappers
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 eat 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  template<typename Graph, typename BoolMap>
23  bool isBipartite(const Graph& g, BoolMap& bool_map) {
24    typedef typename Graph::template NodeMap<bool> ReachedMap;
25    ReachedMap reached(g/*, false*/);
26    BfsIterator<Graph, ReachedMap> bfs(g, reached);
27    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
28      if (!reached[n]) {
29        bfs.pushAndSetReached(n);
30        bool_map.set(n, false);
31        while (!bfs.finished()) {
32          if (bfs.isBNodeNewlyReached()) {
33            bool_map.set(bfs.bNode())=!bfs.aNode();
34          } else {
35            if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
36              return false;
37            }
38          }
39          ++bfs;
40        }
41      }
42    }
43
44    return true;
45  }
46
47  /// experimental topsort,
48  /// I think the final version will work as an iterator
49  /// if the graph is not a acyclic, the na pre-topological order is obtained
50  /// (see Schrijver's book).
51  /// PredMap have to be a writtable node-map.
52  /// If the graph is directed and not acyclic,
53  /// then going back from the returned node via the pred information, a
54  /// cycle is obtained.
55  template<typename Graph, typename PredMap>
56  typename Graph::Node
57  topSort(const Graph& g, std::list<typename Graph::Node>& l,
58               PredMap& pred) {
59    l.clear();
60    typedef typename Graph::template NodeMap<bool> ReachedMap;
61    typedef typename Graph::template NodeMap<bool> ExaminedMap;
62    ReachedMap reached(g/*, false*/);
63    ExaminedMap examined(g/*, false*/);
64    DfsIterator<Graph, ReachedMap> dfs(g, reached);
65    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
66      if (!reached[n]) {
67        dfs.pushAndSetReached(n);
68        pred.set(n, INVALID);
69        while (!dfs.finished()) {
70          ++dfs;
71          if (dfs.isBNodeNewlyReached()) {
72            ///\bug hugo 0.2-ben Edge kell
73            pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));
74          } else {
75            ///\bug ugyanaz
76            if (g.valid(typename Graph::OutEdgeIt(dfs)) &&
77                !examined[dfs.bNode()]) {
78              ///\bug hugo 0.2-ben Edge kell
79              pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs));
80              return dfs.aNode();
81            }
82          }
83          if (dfs.isANodeExamined()) {
84            l.push_back(dfs.aNode());
85            examined.set(dfs.aNode(), true);
86          }
87        }
88      }
89    }
90    return INVALID;
91  }
92} //namespace hugo
93
94#endif //HUGO_BFS_DFS_MISC_H
Note: See TracBrowser for help on using the repository browser.