src/work/marci/bfs_dfs_misc.h
author athos
Tue, 11 May 2004 16:38:17 +0000
changeset 611 83530dad618a
parent 602 580b329c2a0c
child 615 b6b31b75b522
permissions -rw-r--r--
Some modifications and another testfile.
marci@455
     1
// -*- c++ -*-
marci@543
     2
#ifndef HUGO_BFS_DFS_MISC_H
marci@543
     3
#define HUGO_BFS_DFS_MISC_H
marci@455
     4
marci@604
     5
// ///\ingroup gwrappers
marci@604
     6
///\file
marci@604
     7
///\brief Miscellaneous algorithms using bfs and dfs.
marci@604
     8
///
marci@604
     9
///This file contains several algorithms using bfs and dfs.
marci@604
    10
///
marci@604
    11
// ///\author Marton Makai
marci@604
    12
marci@602
    13
#include <bfs_dfs.h>
marci@455
    14
#include <for_each_macros.h>
marci@455
    15
marci@455
    16
namespace hugo {
marci@455
    17
marci@455
    18
  /// This function eat a read-write \c BoolMap& bool_map, 
marci@455
    19
  /// which have to work well up 
marci@455
    20
  /// to its \c set and \c operator[]() method. Thus we have to deal 
marci@455
    21
  /// very carefully with an uninitialized \c IterableBoolMap.
marci@455
    22
  template<typename Graph, typename BoolMap> 
marci@455
    23
  bool isBipartite(const Graph& g, BoolMap& bool_map) {
marci@455
    24
    typedef typename Graph::template NodeMap<bool> ReachedMap;
marci@455
    25
    ReachedMap reached(g/*, false*/);
marci@455
    26
    BfsIterator<Graph, ReachedMap> bfs(g, reached);
marci@455
    27
    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
marci@455
    28
      if (!reached[n]) {
marci@455
    29
	bfs.pushAndSetReached(n);
marci@549
    30
	bool_map.set(n, false);
marci@549
    31
	while (!bfs.finished()) {
marci@549
    32
	  if (bfs.isBNodeNewlyReached()) {
marci@549
    33
	    bool_map.set(bfs.bNode())=!bfs.aNode();
marci@549
    34
	  } else {
marci@549
    35
	    if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
marci@549
    36
	      return false;
marci@455
    37
	    }
marci@455
    38
	  }
marci@549
    39
	  ++bfs;
marci@455
    40
	}
marci@455
    41
      }
marci@455
    42
    }
marci@549
    43
    
marci@455
    44
    return true;
marci@455
    45
  }
marci@540
    46
marci@540
    47
  /// experimental topsort, 
marci@540
    48
  /// I think the final version will work as an iterator
marci@549
    49
  /// if the graph is not a acyclic, the na pre-topological order is obtained 
marci@577
    50
  /// (see Schrijver's book).
marci@577
    51
  /// PredMap have to be a writtable node-map.
marci@577
    52
  /// If the graph is directed and not acyclic, 
marci@577
    53
  /// then going back from the returned node via the pred information, a 
marci@577
    54
  /// cycle is obtained.
marci@577
    55
  template<typename Graph, typename PredMap> 
marci@577
    56
  typename Graph::Node 
marci@577
    57
  topSort(const Graph& g, std::list<typename Graph::Node>& l, 
marci@577
    58
	       PredMap& pred) {
marci@540
    59
    l.clear();
marci@540
    60
    typedef typename Graph::template NodeMap<bool> ReachedMap;
marci@577
    61
    typedef typename Graph::template NodeMap<bool> ExaminedMap;    
marci@540
    62
    ReachedMap reached(g/*, false*/);
marci@577
    63
    ExaminedMap examined(g/*, false*/);
marci@540
    64
    DfsIterator<Graph, ReachedMap> dfs(g, reached);
marci@540
    65
    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
marci@540
    66
      if (!reached[n]) {
marci@540
    67
	dfs.pushAndSetReached(n);
marci@577
    68
	pred.set(n, INVALID);
marci@543
    69
	while (!dfs.finished()) {
marci@552
    70
	  ++dfs;
marci@577
    71
	  if (dfs.isBNodeNewlyReached()) {
marci@577
    72
	    ///\bug hugo 0.2-ben Edge kell
marci@577
    73
	    pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));
marci@577
    74
	  } else {
marci@577
    75
	    ///\bug ugyanaz
marci@577
    76
	    if (g.valid(typename Graph::OutEdgeIt(dfs)) && 
marci@577
    77
		!examined[dfs.bNode()]) {
marci@577
    78
	      ///\bug hugo 0.2-ben Edge kell
marci@577
    79
	      pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs));
marci@577
    80
	      return dfs.aNode();
marci@577
    81
	    }
marci@577
    82
	  }
marci@543
    83
	  if (dfs.isANodeExamined()) {
marci@543
    84
	    l.push_back(dfs.aNode());
marci@577
    85
	    examined.set(dfs.aNode(), true);
marci@540
    86
	  }
marci@540
    87
	}
marci@540
    88
      }
marci@540
    89
    }
marci@577
    90
    return INVALID;
marci@540
    91
  }
marci@548
    92
} //namespace hugo
marci@548
    93
marci@543
    94
#endif //HUGO_BFS_DFS_MISC_H