COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_dfs_misc.h @ 920:2d6c8075d9d0

Last change on this file since 920:2d6c8075d9d0 was 762:511200bdb71f, checked in by marci, 17 years ago

technical corrections

File size: 2.7 KB
RevLine 
[455]1// -*- c++ -*-
[543]2#ifndef HUGO_BFS_DFS_MISC_H
3#define HUGO_BFS_DFS_MISC_H
[455]4
[615]5/// \ingroup galgs
6/// \file
7/// \brief Miscellaneous algorithms using bfs and dfs.
[604]8///
[615]9/// This file contains several algorithms using bfs and dfs.
[604]10///
11// ///\author Marton Makai
12
[602]13#include <bfs_dfs.h>
[762]14#include <for_each_macros.h>
[455]15
16namespace hugo {
17
[615]18  /// This function eats a read-write \c BoolMap& bool_map,
[455]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.
[615]22  /// \ingroup galgs
[455]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);
[549]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;
[455]38            }
39          }
[549]40          ++bfs;
[455]41        }
42      }
43    }
[549]44   
[455]45    return true;
46  }
[540]47
48  /// experimental topsort,
49  /// I think the final version will work as an iterator
[549]50  /// if the graph is not a acyclic, the na pre-topological order is obtained
[577]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.
[615]56  /// \ingroup galgs
[577]57  template<typename Graph, typename PredMap>
58  typename Graph::Node
59  topSort(const Graph& g, std::list<typename Graph::Node>& l,
60               PredMap& pred) {
[540]61    l.clear();
62    typedef typename Graph::template NodeMap<bool> ReachedMap;
[577]63    typedef typename Graph::template NodeMap<bool> ExaminedMap;   
[540]64    ReachedMap reached(g/*, false*/);
[577]65    ExaminedMap examined(g/*, false*/);
[540]66    DfsIterator<Graph, ReachedMap> dfs(g, reached);
67    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
68      if (!reached[n]) {
69        dfs.pushAndSetReached(n);
[577]70        pred.set(n, INVALID);
[543]71        while (!dfs.finished()) {
[552]72          ++dfs;
[577]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          }
[543]85          if (dfs.isANodeExamined()) {
86            l.push_back(dfs.aNode());
[577]87            examined.set(dfs.aNode(), true);
[540]88          }
89        }
90      }
91    }
[577]92    return INVALID;
[540]93  }
[615]94
[548]95} //namespace hugo
96
[543]97#endif //HUGO_BFS_DFS_MISC_H
Note: See TracBrowser for help on using the repository browser.