// -*- c++ -*- #ifndef LEMON_BFS_DFS_MISC_H #define LEMON_BFS_DFS_MISC_H /// \ingroup galgs /// \file /// \brief Miscellaneous algorithms using bfs and dfs. /// /// This file contains several algorithms using bfs and dfs. /// // ///\author Marton Makai #include #include namespace lemon { /// This function eats a read-write \c BoolMap& bool_map, /// which have to work well up /// to its \c set and \c operator[]() method. Thus we have to deal /// very carefully with an uninitialized \c IterableBoolMap. /// \ingroup galgs template bool isBipartite(const Graph& g, BoolMap& bool_map) { typedef typename Graph::template NodeMap ReachedMap; ReachedMap reached(g/*, false*/); BfsIterator bfs(g, reached); FOR_EACH_LOC(typename Graph::NodeIt, n, g) { if (!reached[n]) { bfs.pushAndSetReached(n); bool_map.set(n, false); while (!bfs.finished()) { if (bfs.isBNodeNewlyReached()) { bool_map.set(bfs.bNode())=!bfs.aNode(); } else { if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) { return false; } } ++bfs; } } } return true; } /// experimental topsort, /// I think the final version will work as an iterator /// if the graph is not a acyclic, the na pre-topological order is obtained /// (see Schrijver's book). /// PredMap have to be a writtable node-map. /// If the graph is directed and not acyclic, /// then going back from the returned node via the pred information, a /// cycle is obtained. /// \ingroup galgs template typename Graph::Node topSort(const Graph& g, std::list& l, PredMap& pred) { l.clear(); typedef typename Graph::template NodeMap ReachedMap; typedef typename Graph::template NodeMap ExaminedMap; ReachedMap reached(g/*, false*/); ExaminedMap examined(g/*, false*/); DfsIterator dfs(g, reached); FOR_EACH_LOC(typename Graph::NodeIt, n, g) { if (!reached[n]) { dfs.pushAndSetReached(n); pred.set(n, INVALID); while (!dfs.finished()) { ++dfs; if (dfs.isBNodeNewlyReached()) { ///\bug lemon 0.2-ben Edge kell pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs)); } else { ///\bug ugyanaz if (g.valid(typename Graph::OutEdgeIt(dfs)) && !examined[dfs.bNode()]) { ///\bug lemon 0.2-ben Edge kell pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs)); return dfs.aNode(); } } if (dfs.isANodeExamined()) { l.push_back(dfs.aNode()); examined.set(dfs.aNode(), true); } } } } return INVALID; } } //namespace lemon #endif //LEMON_BFS_DFS_MISC_H