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.
     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 
    16 namespace 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