1 // -*- c++ -*- |
1 // -*- c++ -*- |
2 #ifndef HUGO_BFS_DFS_MISC_H |
2 #ifndef HUGO_BFS_DFS_MISC_H |
3 #define HUGO_BFS_DFS_MISC_H |
3 #define HUGO_BFS_DFS_MISC_H |
4 |
4 |
5 // ///\ingroup gwrappers |
5 /// \ingroup galgs |
6 ///\file |
6 /// \file |
7 ///\brief Miscellaneous algorithms using bfs and dfs. |
7 /// \brief Miscellaneous algorithms using bfs and dfs. |
8 /// |
8 /// |
9 ///This file contains several algorithms using bfs and dfs. |
9 /// This file contains several algorithms using bfs and dfs. |
10 /// |
10 /// |
11 // ///\author Marton Makai |
11 // ///\author Marton Makai |
12 |
12 |
13 #include <bfs_dfs.h> |
13 #include <bfs_dfs.h> |
14 #include <for_each_macros.h> |
14 #include <for_each_macros.h> |
15 |
15 |
16 namespace hugo { |
16 namespace hugo { |
17 |
17 |
18 /// This function eat a read-write \c BoolMap& bool_map, |
18 /// This function eats a read-write \c BoolMap& bool_map, |
19 /// which have to work well up |
19 /// which have to work well up |
20 /// to its \c set and \c operator[]() method. Thus we have to deal |
20 /// to its \c set and \c operator[]() method. Thus we have to deal |
21 /// very carefully with an uninitialized \c IterableBoolMap. |
21 /// very carefully with an uninitialized \c IterableBoolMap. |
|
22 /// \ingroup galgs |
22 template<typename Graph, typename BoolMap> |
23 template<typename Graph, typename BoolMap> |
23 bool isBipartite(const Graph& g, BoolMap& bool_map) { |
24 bool isBipartite(const Graph& g, BoolMap& bool_map) { |
24 typedef typename Graph::template NodeMap<bool> ReachedMap; |
25 typedef typename Graph::template NodeMap<bool> ReachedMap; |
25 ReachedMap reached(g/*, false*/); |
26 ReachedMap reached(g/*, false*/); |
26 BfsIterator<Graph, ReachedMap> bfs(g, reached); |
27 BfsIterator<Graph, ReachedMap> bfs(g, reached); |
50 /// (see Schrijver's book). |
51 /// (see Schrijver's book). |
51 /// PredMap have to be a writtable node-map. |
52 /// PredMap have to be a writtable node-map. |
52 /// If the graph is directed and not acyclic, |
53 /// If the graph is directed and not acyclic, |
53 /// then going back from the returned node via the pred information, a |
54 /// then going back from the returned node via the pred information, a |
54 /// cycle is obtained. |
55 /// cycle is obtained. |
|
56 /// \ingroup galgs |
55 template<typename Graph, typename PredMap> |
57 template<typename Graph, typename PredMap> |
56 typename Graph::Node |
58 typename Graph::Node |
57 topSort(const Graph& g, std::list<typename Graph::Node>& l, |
59 topSort(const Graph& g, std::list<typename Graph::Node>& l, |
58 PredMap& pred) { |
60 PredMap& pred) { |
59 l.clear(); |
61 l.clear(); |