1.1 --- a/lemon/topology.h Mon Oct 24 15:59:38 2005 +0000
1.2 +++ b/lemon/topology.h Mon Oct 24 17:03:02 2005 +0000
1.3 @@ -18,6 +18,7 @@
1.4 #define LEMON_TOPOLOGY_H
1.5
1.6 #include <lemon/dfs.h>
1.7 +#include <lemon/bfs.h>
1.8 #include <lemon/graph_utils.h>
1.9
1.10 #include <lemon/concept/graph.h>
1.11 @@ -220,19 +221,19 @@
1.12 ///
1.13 ///\param g The graph. In must be undirected.
1.14 ///\return The number of components
1.15 - ///\todo Test required
1.16 - template<class UGraph>
1.17 - int numberOfComponents(const UGraph &g)
1.18 - {
1.19 - int c=0;
1.20 - Bfs<Graph> bfs(g);
1.21 + template <class UndirGraph>
1.22 + int countConnectedComponents(const UndirGraph &g) {
1.23 + checkConcept<concept::UndirGraph, UndirGraph>();
1.24 + int c = 0;
1.25 + Bfs<UndirGraph> bfs(g);
1.26 bfs.init();
1.27 - for(typename Graph::NodeIt n(g);n!=INVALID;++n)
1.28 + for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
1.29 if(!bfs.reached(n)) {
1.30 - c++;
1.31 bfs.addSource(n);
1.32 bfs.start();
1.33 + ++c;
1.34 }
1.35 + }
1.36 return c;
1.37 }
1.38
1.39 @@ -248,23 +249,173 @@
1.40 ///set continuously.
1.41 ///\return The number of components
1.42 ///\todo Test required
1.43 - template<class UGraph, class WMap>
1.44 - int connectedComponents(const UGraph &g, WMap &comp)
1.45 - {
1.46 - int c=0;
1.47 - Bfs<Graph> bfs(g);
1.48 + template <class UndirGraph, class IntNodeMap>
1.49 + int connectedComponents(const UndirGraph &g, IntNodeMap &comp) {
1.50 + checkConcept<concept::UndirGraph, UndirGraph>();
1.51 + checkConcept<concept::WriteMap<typename UndirGraph::Node, int>,
1.52 + IntNodeMap>();
1.53 + int c = 0;
1.54 + Bfs<UndirGraph> bfs(g);
1.55 bfs.init();
1.56 - for(typename Graph::NodeIt n(g);n!=INVALID;++n)
1.57 + for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
1.58 if(!bfs.reached(n)) {
1.59 bfs.addSource(n);
1.60 - while ( bfs.nextNode()!=INVALID ) {
1.61 - comp[bfs.nextNode()]=c;
1.62 - processNextNode();
1.63 - c++;
1.64 + while (!bfs.emptyQueue()) {
1.65 + comp[bfs.nextNode()] = c;
1.66 + bfs.processNextNode();
1.67 + }
1.68 + ++c;
1.69 }
1.70 + }
1.71 return c;
1.72 }
1.73
1.74 + namespace _components_bits {
1.75 +
1.76 + template <typename Key, typename IntMap>
1.77 + struct FillWriteMap : public MapBase<Key, bool> {
1.78 + public:
1.79 + FillWriteMap(IntMap& _map, int& _comp)
1.80 + : map(_map), comp(_comp) {}
1.81 + void set(Key key, bool value) {
1.82 + if (value) { map.set(key, comp); }
1.83 + }
1.84 + private:
1.85 + IntMap& map;
1.86 + int& comp;
1.87 + };
1.88 +
1.89 + template <typename Key, typename Container = std::vector<Key> >
1.90 + struct BackInserterWriteMap : public MapBase<Key, bool> {
1.91 + public:
1.92 + BackInserterWriteMap(Container& _container)
1.93 + : container(_container) {}
1.94 + void set(Key key, bool value) {
1.95 + if (value) { container.push_back(key); }
1.96 + }
1.97 + private:
1.98 + Container& container;
1.99 + };
1.100 +
1.101 + }
1.102 +
1.103 + /// \brief Count the strongly connected components of a directed graph
1.104 + ///
1.105 + /// Count the strongly connected components of a directed graph
1.106 + ///
1.107 + /// \param g The graph.
1.108 + /// \return The number of components
1.109 + template <typename Graph>
1.110 + int countStronglyConnectedComponents(const Graph& graph) {
1.111 + checkConcept<concept::StaticGraph, Graph>();
1.112 +
1.113 + using namespace _components_bits;
1.114 +
1.115 + typedef typename Graph::Node Node;
1.116 + typedef typename Graph::Edge Edge;
1.117 + typedef typename Graph::NodeIt NodeIt;
1.118 + typedef typename Graph::EdgeIt EdgeIt;
1.119 +
1.120 +
1.121 + typename Dfs<Graph>::
1.122 + template DefProcessedMap<BackInserterWriteMap<Node> >::
1.123 + Create dfs(graph);
1.124 +
1.125 + std::vector<Node> nodes;
1.126 + BackInserterWriteMap<Node> processed(nodes);
1.127 + dfs.processedMap(processed);
1.128 +
1.129 + dfs.init();
1.130 + for (NodeIt it(graph); it != INVALID; ++it) {
1.131 + if (!dfs.reached(it)) {
1.132 + dfs.addSource(it);
1.133 + dfs.start();
1.134 + }
1.135 + }
1.136 +
1.137 + typedef RevGraphAdaptor<const Graph> RGraph;
1.138 +
1.139 + RGraph rgraph(graph);
1.140 +
1.141 + Dfs<RGraph> rdfs(rgraph);
1.142 +
1.143 + int num = 0;
1.144 +
1.145 + rdfs.init();
1.146 + for (typename std::vector<Node>::reverse_iterator
1.147 + it = nodes.rbegin(); it != nodes.rend(); ++it) {
1.148 + if (!rdfs.reached(*it)) {
1.149 + rdfs.addSource(*it);
1.150 + rdfs.start();
1.151 + ++num;
1.152 + }
1.153 + }
1.154 + return num;
1.155 + }
1.156 +
1.157 + /// \brief Find the strongly connected components of a directed graph
1.158 + ///
1.159 + /// Find the strongly connected components of a directed graph
1.160 + ///
1.161 + /// \param g The graph.
1.162 + /// \retval comp A writable node map. The values will be set from 0 to
1.163 + /// the number of the strongly connected components minus one. Each values
1.164 + /// of the map will be set exactly once, the values of a certain component
1.165 + /// will be set continuously.
1.166 + /// \return The number of components
1.167 + template <typename Graph, typename IntNodeMap>
1.168 + int stronglyConnectedComponents(const Graph& graph, IntNodeMap& comp) {
1.169 + checkConcept<concept::StaticGraph, Graph>();
1.170 + checkConcept<concept::WriteMap<typename Graph::Node, int>, IntNodeMap>();
1.171 +
1.172 + using namespace _components_bits;
1.173 +
1.174 + typedef typename Graph::Node Node;
1.175 + typedef typename Graph::Edge Edge;
1.176 + typedef typename Graph::NodeIt NodeIt;
1.177 + typedef typename Graph::EdgeIt EdgeIt;
1.178 +
1.179 +
1.180 + typename Dfs<Graph>::
1.181 + template DefProcessedMap<BackInserterWriteMap<Node> >::
1.182 + Create dfs(graph);
1.183 +
1.184 + std::vector<Node> nodes;
1.185 + BackInserterWriteMap<Node> processed(nodes);
1.186 + dfs.processedMap(processed);
1.187 +
1.188 + dfs.init();
1.189 + for (NodeIt it(graph); it != INVALID; ++it) {
1.190 + if (!dfs.reached(it)) {
1.191 + dfs.addSource(it);
1.192 + dfs.start();
1.193 + }
1.194 + }
1.195 +
1.196 + typedef RevGraphAdaptor<const Graph> RGraph;
1.197 +
1.198 + RGraph rgraph(graph);
1.199 +
1.200 + typename Dfs<RGraph>::
1.201 + template DefProcessedMap<FillWriteMap<Node, IntNodeMap> >::
1.202 + Create rdfs(rgraph);
1.203 +
1.204 + int num = 0;
1.205 + FillWriteMap<Node, IntNodeMap> rprocessed(comp, num);
1.206 + rdfs.processedMap(rprocessed);
1.207 +
1.208 + rdfs.init();
1.209 + for (typename std::vector<Node>::reverse_iterator
1.210 + it = nodes.rbegin(); it != nodes.rend(); ++it) {
1.211 + if (!rdfs.reached(*it)) {
1.212 + rdfs.addSource(*it);
1.213 + rdfs.start();
1.214 + ++num;
1.215 + }
1.216 + }
1.217 + return num;
1.218 + }
1.219 +
1.220 } //namespace lemon
1.221
1.222 #endif //LEMON_TOPOLOGY_H