1.1 --- a/src/work/marci/bfs_dfs_misc.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,97 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef LEMON_BFS_DFS_MISC_H
1.6 -#define LEMON_BFS_DFS_MISC_H
1.7 -
1.8 -/// \ingroup galgs
1.9 -/// \file
1.10 -/// \brief Miscellaneous algorithms using bfs and dfs.
1.11 -///
1.12 -/// This file contains several algorithms using bfs and dfs.
1.13 -///
1.14 -// ///\author Marton Makai
1.15 -
1.16 -#include <bfs_dfs.h>
1.17 -#include <for_each_macros.h>
1.18 -
1.19 -namespace lemon {
1.20 -
1.21 - /// This function eats a read-write \c BoolMap& bool_map,
1.22 - /// which have to work well up
1.23 - /// to its \c set and \c operator[]() method. Thus we have to deal
1.24 - /// very carefully with an uninitialized \c IterableBoolMap.
1.25 - /// \ingroup galgs
1.26 - template<typename Graph, typename BoolMap>
1.27 - bool isBipartite(const Graph& g, BoolMap& bool_map) {
1.28 - typedef typename Graph::template NodeMap<bool> ReachedMap;
1.29 - ReachedMap reached(g/*, false*/);
1.30 - BfsIterator<Graph, ReachedMap> bfs(g, reached);
1.31 - FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
1.32 - if (!reached[n]) {
1.33 - bfs.pushAndSetReached(n);
1.34 - bool_map.set(n, false);
1.35 - while (!bfs.finished()) {
1.36 - if (bfs.isBNodeNewlyReached()) {
1.37 - bool_map.set(bfs.bNode())=!bfs.aNode();
1.38 - } else {
1.39 - if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
1.40 - return false;
1.41 - }
1.42 - }
1.43 - ++bfs;
1.44 - }
1.45 - }
1.46 - }
1.47 -
1.48 - return true;
1.49 - }
1.50 -
1.51 - /// experimental topsort,
1.52 - /// I think the final version will work as an iterator
1.53 - /// if the graph is not a acyclic, the na pre-topological order is obtained
1.54 - /// (see Schrijver's book).
1.55 - /// PredMap have to be a writtable node-map.
1.56 - /// If the graph is directed and not acyclic,
1.57 - /// then going back from the returned node via the pred information, a
1.58 - /// cycle is obtained.
1.59 - /// \ingroup galgs
1.60 - template<typename Graph, typename PredMap>
1.61 - typename Graph::Node
1.62 - topSort(const Graph& g, std::list<typename Graph::Node>& l,
1.63 - PredMap& pred) {
1.64 - l.clear();
1.65 - typedef typename Graph::template NodeMap<bool> ReachedMap;
1.66 - typedef typename Graph::template NodeMap<bool> ExaminedMap;
1.67 - ReachedMap reached(g/*, false*/);
1.68 - ExaminedMap examined(g/*, false*/);
1.69 - DfsIterator<Graph, ReachedMap> dfs(g, reached);
1.70 - FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
1.71 - if (!reached[n]) {
1.72 - dfs.pushAndSetReached(n);
1.73 - pred.set(n, INVALID);
1.74 - while (!dfs.finished()) {
1.75 - ++dfs;
1.76 - if (dfs.isBNodeNewlyReached()) {
1.77 - ///\bug lemon 0.2-ben Edge kell
1.78 - pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));
1.79 - } else {
1.80 - ///\bug ugyanaz
1.81 - if (g.valid(typename Graph::OutEdgeIt(dfs)) &&
1.82 - !examined[dfs.bNode()]) {
1.83 - ///\bug lemon 0.2-ben Edge kell
1.84 - pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs));
1.85 - return dfs.aNode();
1.86 - }
1.87 - }
1.88 - if (dfs.isANodeExamined()) {
1.89 - l.push_back(dfs.aNode());
1.90 - examined.set(dfs.aNode(), true);
1.91 - }
1.92 - }
1.93 - }
1.94 - }
1.95 - return INVALID;
1.96 - }
1.97 -
1.98 -} //namespace lemon
1.99 -
1.100 -#endif //LEMON_BFS_DFS_MISC_H