COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_dfs_misc.h @ 549:5531429143bc

Last change on this file since 549:5531429143bc was 549:5531429143bc, checked in by marci, 20 years ago
File size: 1.7 KB
RevLine 
[455]1// -*- c++ -*-
[543]2#ifndef HUGO_BFS_DFS_MISC_H
3#define HUGO_BFS_DFS_MISC_H
[455]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);
[549]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;
[455]29            }
30          }
[549]31          ++bfs;
[455]32        }
33      }
34    }
[549]35   
[455]36    return true;
37  }
[540]38
39  /// experimental topsort,
40  /// I think the final version will work as an iterator
[549]41  /// if the graph is not a acyclic, the na pre-topological order is obtained
42  /// (see Schrijver's book)
[540]43  template<typename Graph>
[549]44  void topSort(const Graph& g, std::list<typename Graph::Node>& l) {
[540]45    l.clear();
46    typedef typename Graph::template NodeMap<bool> ReachedMap;
47    ReachedMap reached(g/*, false*/);
48    DfsIterator<Graph, ReachedMap> dfs(g, reached);
49    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
50      if (!reached[n]) {
51        dfs.pushAndSetReached(n);
[543]52        while (!dfs.finished()) {
53          if (dfs.isANodeExamined()) {
54            l.push_back(dfs.aNode());
[540]55          }
[548]56          ++dfs;
[540]57        }
58      }
59    }
60  }
[548]61} //namespace hugo
62
[543]63#endif //HUGO_BFS_DFS_MISC_H
Note: See TracBrowser for help on using the repository browser.