lemon-0.x: src/work/marci/bfs_dfs

     1 // -*- c++ -*-

     2 #ifndef HUGO_BFS_DFS_MISC_H

     3 #define HUGO_BFS_DFS_MISC_H

     5 /// \ingroup galgs

     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

    13 #include <bfs_dfs.h>

    14 #include <hugo/for_each_macros.h>

    16 namespace hugo {

    18   /// This function eats 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   /// \ingroup galgs

    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);

    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;

    38 	    }

    39 	  }

    40 	  ++bfs;

    41 	}

    42       }

    43     }

    45     return true;

    46   }

    48   /// experimental topsort,

    49   /// I think the final version will work as an iterator

    50   /// if the graph is not a acyclic, the na pre-topological order is obtained

    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.

    56   /// \ingroup galgs

    57   template<typename Graph, typename PredMap>

    58   typename Graph::Node

    59   topSort(const Graph& g, std::list<typename Graph::Node>& l,

    60 	       PredMap& pred) {

    61     l.clear();

    62     typedef typename Graph::template NodeMap<bool> ReachedMap;

    63     typedef typename Graph::template NodeMap<bool> ExaminedMap;

    64     ReachedMap reached(g/*, false*/);

    65     ExaminedMap examined(g/*, false*/);

    66     DfsIterator<Graph, ReachedMap> dfs(g, reached);

    67     FOR_EACH_LOC(typename Graph::NodeIt, n, g) {

    68       if (!reached[n]) {

    69 	dfs.pushAndSetReached(n);

    70 	pred.set(n, INVALID);

    71 	while (!dfs.finished()) {

    72 	  ++dfs;

    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 	  }

    85 	  if (dfs.isANodeExamined()) {

    86 	    l.push_back(dfs.aNode());

    87 	    examined.set(dfs.aNode(), true);

    88 	  }

    89 	}

    90       }

    91     }

    92     return INVALID;

    93   }

    95 } //namespace hugo

    97 #endif //HUGO_BFS_DFS_MISC_H

author	alpar
	Mon, 19 Jul 2004 13:29:32 +0000
changeset 706	0fe42b8ec5a6
parent 615	b6b31b75b522
child 762	511200bdb71f
permissions	-rw-r--r--