1.1 --- a/lemon/topology.h Thu Jan 26 06:44:22 2006 +0000
1.2 +++ b/lemon/topology.h Thu Jan 26 15:42:13 2006 +0000
1.3 @@ -24,7 +24,7 @@
1.4 #include <lemon/maps.h>
1.5
1.6 #include <lemon/concept/graph.h>
1.7 -#include <lemon/concept/undir_graph.h>
1.8 +#include <lemon/concept/ugraph.h>
1.9 #include <lemon/concept_check.h>
1.10
1.11 #include <lemon/bin_heap.h>
1.12 @@ -49,12 +49,12 @@
1.13 /// \param graph The undirected graph.
1.14 /// \return %True when there is path between any two nodes in the graph.
1.15 /// \note By definition, the empty graph is connected.
1.16 - template <typename UndirGraph>
1.17 - bool connected(const UndirGraph& graph) {
1.18 - checkConcept<concept::UndirGraph, UndirGraph>();
1.19 - typedef typename UndirGraph::NodeIt NodeIt;
1.20 + template <typename UGraph>
1.21 + bool connected(const UGraph& graph) {
1.22 + checkConcept<concept::UGraph, UGraph>();
1.23 + typedef typename UGraph::NodeIt NodeIt;
1.24 if (NodeIt(graph) == INVALID) return true;
1.25 - Dfs<UndirGraph> dfs(graph);
1.26 + Dfs<UGraph> dfs(graph);
1.27 dfs.run(NodeIt(graph));
1.28 for (NodeIt it(graph); it != INVALID; ++it) {
1.29 if (!dfs.reached(it)) {
1.30 @@ -74,17 +74,17 @@
1.31 /// \return The number of components
1.32 /// \note By definition, the empty graph consists
1.33 /// of zero connected components.
1.34 - template <typename UndirGraph>
1.35 - int countConnectedComponents(const UndirGraph &graph) {
1.36 - checkConcept<concept::UndirGraph, UndirGraph>();
1.37 - typedef typename UndirGraph::Node Node;
1.38 - typedef typename UndirGraph::Edge Edge;
1.39 + template <typename UGraph>
1.40 + int countConnectedComponents(const UGraph &graph) {
1.41 + checkConcept<concept::UGraph, UGraph>();
1.42 + typedef typename UGraph::Node Node;
1.43 + typedef typename UGraph::Edge Edge;
1.44
1.45 typedef NullMap<Node, Edge> PredMap;
1.46 typedef NullMap<Node, int> DistMap;
1.47
1.48 int compNum = 0;
1.49 - typename Bfs<UndirGraph>::
1.50 + typename Bfs<UGraph>::
1.51 template DefPredMap<PredMap>::
1.52 template DefDistMap<DistMap>::
1.53 Create bfs(graph);
1.54 @@ -96,7 +96,7 @@
1.55 bfs.distMap(distMap);
1.56
1.57 bfs.init();
1.58 - for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
1.59 + for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) {
1.60 if (!bfs.reached(n)) {
1.61 bfs.addSource(n);
1.62 bfs.start();
1.63 @@ -122,18 +122,18 @@
1.64 /// set continuously.
1.65 /// \return The number of components
1.66 ///
1.67 - template <class UndirGraph, class NodeMap>
1.68 - int connectedComponents(const UndirGraph &graph, NodeMap &compMap) {
1.69 - checkConcept<concept::UndirGraph, UndirGraph>();
1.70 - typedef typename UndirGraph::Node Node;
1.71 - typedef typename UndirGraph::Edge Edge;
1.72 + template <class UGraph, class NodeMap>
1.73 + int connectedComponents(const UGraph &graph, NodeMap &compMap) {
1.74 + checkConcept<concept::UGraph, UGraph>();
1.75 + typedef typename UGraph::Node Node;
1.76 + typedef typename UGraph::Edge Edge;
1.77 checkConcept<concept::WriteMap<Node, int>, NodeMap>();
1.78
1.79 typedef NullMap<Node, Edge> PredMap;
1.80 typedef NullMap<Node, int> DistMap;
1.81
1.82 int compNum = 0;
1.83 - typename Bfs<UndirGraph>::
1.84 + typename Bfs<UGraph>::
1.85 template DefPredMap<PredMap>::
1.86 template DefDistMap<DistMap>::
1.87 Create bfs(graph);
1.88 @@ -145,7 +145,7 @@
1.89 bfs.distMap(distMap);
1.90
1.91 bfs.init();
1.92 - for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
1.93 + for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) {
1.94 if(!bfs.reached(n)) {
1.95 bfs.addSource(n);
1.96 while (!bfs.emptyQueue()) {
1.97 @@ -484,7 +484,7 @@
1.98 public:
1.99 typedef typename Graph::Node Node;
1.100 typedef typename Graph::Edge Edge;
1.101 - typedef typename Graph::UndirEdge UndirEdge;
1.102 + typedef typename Graph::UEdge UEdge;
1.103
1.104 CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum)
1.105 : _graph(graph), _compNum(compNum),
1.106 @@ -542,7 +542,7 @@
1.107 public:
1.108 typedef typename Graph::Node Node;
1.109 typedef typename Graph::Edge Edge;
1.110 - typedef typename Graph::UndirEdge UndirEdge;
1.111 + typedef typename Graph::UEdge UEdge;
1.112
1.113 BiNodeConnectedComponentsVisitor(const Graph& graph,
1.114 EdgeMap& compMap, int &compNum)
1.115 @@ -612,7 +612,7 @@
1.116 typename Graph::template NodeMap<int> _numMap;
1.117 typename Graph::template NodeMap<int> _retMap;
1.118 typename Graph::template NodeMap<Edge> _predMap;
1.119 - std::stack<UndirEdge> _edgeStack;
1.120 + std::stack<UEdge> _edgeStack;
1.121 int _num;
1.122 };
1.123
1.124 @@ -622,7 +622,7 @@
1.125 public:
1.126 typedef typename Graph::Node Node;
1.127 typedef typename Graph::Edge Edge;
1.128 - typedef typename Graph::UndirEdge UndirEdge;
1.129 + typedef typename Graph::UEdge UEdge;
1.130
1.131 BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
1.132 int& cutNum)
1.133 @@ -688,15 +688,15 @@
1.134 typename Graph::template NodeMap<int> _numMap;
1.135 typename Graph::template NodeMap<int> _retMap;
1.136 typename Graph::template NodeMap<Node> _predMap;
1.137 - std::stack<UndirEdge> _edgeStack;
1.138 + std::stack<UEdge> _edgeStack;
1.139 int _num;
1.140 bool rootCut;
1.141 };
1.142
1.143 }
1.144
1.145 - template <typename UndirGraph>
1.146 - int countBiNodeConnectedComponents(const UndirGraph& graph);
1.147 + template <typename UGraph>
1.148 + int countBiNodeConnectedComponents(const UGraph& graph);
1.149
1.150 /// \ingroup topology
1.151 ///
1.152 @@ -709,8 +709,8 @@
1.153 /// \param graph The graph.
1.154 /// \return %True when the graph bi-node-connected.
1.155 /// \todo Make it faster.
1.156 - template <typename UndirGraph>
1.157 - bool biNodeConnected(const UndirGraph& graph) {
1.158 + template <typename UGraph>
1.159 + bool biNodeConnected(const UGraph& graph) {
1.160 return countBiNodeConnectedComponents(graph) == 1;
1.161 }
1.162
1.163 @@ -725,19 +725,19 @@
1.164 ///
1.165 /// \param graph The graph.
1.166 /// \return The number of components.
1.167 - template <typename UndirGraph>
1.168 - int countBiNodeConnectedComponents(const UndirGraph& graph) {
1.169 - checkConcept<concept::UndirGraph, UndirGraph>();
1.170 - typedef typename UndirGraph::NodeIt NodeIt;
1.171 + template <typename UGraph>
1.172 + int countBiNodeConnectedComponents(const UGraph& graph) {
1.173 + checkConcept<concept::UGraph, UGraph>();
1.174 + typedef typename UGraph::NodeIt NodeIt;
1.175
1.176 using namespace _topology_bits;
1.177
1.178 - typedef CountBiNodeConnectedComponentsVisitor<UndirGraph> Visitor;
1.179 + typedef CountBiNodeConnectedComponentsVisitor<UGraph> Visitor;
1.180
1.181 int compNum = 0;
1.182 Visitor visitor(graph, compNum);
1.183
1.184 - DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
1.185 + DfsVisit<UGraph, Visitor> dfs(graph, visitor);
1.186 dfs.init();
1.187
1.188 for (NodeIt it(graph); it != INVALID; ++it) {
1.189 @@ -762,28 +762,28 @@
1.190 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
1.191 ///
1.192 /// \param graph The graph.
1.193 - /// \retval compMap A writable undir edge map. The values will be set from 0
1.194 + /// \retval compMap A writable uedge map. The values will be set from 0
1.195 /// to the number of the biconnected components minus one. Each values
1.196 /// of the map will be set exactly once, the values of a certain component
1.197 /// will be set continuously.
1.198 /// \return The number of components.
1.199 ///
1.200 - template <typename UndirGraph, typename UndirEdgeMap>
1.201 - int biNodeConnectedComponents(const UndirGraph& graph,
1.202 - UndirEdgeMap& compMap) {
1.203 - checkConcept<concept::UndirGraph, UndirGraph>();
1.204 - typedef typename UndirGraph::NodeIt NodeIt;
1.205 - typedef typename UndirGraph::UndirEdge UndirEdge;
1.206 - checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>();
1.207 + template <typename UGraph, typename UEdgeMap>
1.208 + int biNodeConnectedComponents(const UGraph& graph,
1.209 + UEdgeMap& compMap) {
1.210 + checkConcept<concept::UGraph, UGraph>();
1.211 + typedef typename UGraph::NodeIt NodeIt;
1.212 + typedef typename UGraph::UEdge UEdge;
1.213 + checkConcept<concept::WriteMap<UEdge, int>, UEdgeMap>();
1.214
1.215 using namespace _topology_bits;
1.216
1.217 - typedef BiNodeConnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
1.218 + typedef BiNodeConnectedComponentsVisitor<UGraph, UEdgeMap> Visitor;
1.219
1.220 int compNum = 0;
1.221 Visitor visitor(graph, compMap, compNum);
1.222
1.223 - DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
1.224 + DfsVisit<UGraph, Visitor> dfs(graph, visitor);
1.225 dfs.init();
1.226
1.227 for (NodeIt it(graph); it != INVALID; ++it) {
1.228 @@ -809,21 +809,21 @@
1.229 /// \retval cutMap A writable edge map. The values will be set true when
1.230 /// the node separate two or more components.
1.231 /// \return The number of the cut nodes.
1.232 - template <typename UndirGraph, typename NodeMap>
1.233 - int biNodeConnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) {
1.234 - checkConcept<concept::UndirGraph, UndirGraph>();
1.235 - typedef typename UndirGraph::Node Node;
1.236 - typedef typename UndirGraph::NodeIt NodeIt;
1.237 + template <typename UGraph, typename NodeMap>
1.238 + int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) {
1.239 + checkConcept<concept::UGraph, UGraph>();
1.240 + typedef typename UGraph::Node Node;
1.241 + typedef typename UGraph::NodeIt NodeIt;
1.242 checkConcept<concept::WriteMap<Node, bool>, NodeMap>();
1.243
1.244 using namespace _topology_bits;
1.245
1.246 - typedef BiNodeConnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
1.247 + typedef BiNodeConnectedCutNodesVisitor<UGraph, NodeMap> Visitor;
1.248
1.249 int cutNum = 0;
1.250 Visitor visitor(graph, cutMap, cutNum);
1.251
1.252 - DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
1.253 + DfsVisit<UGraph, Visitor> dfs(graph, visitor);
1.254 dfs.init();
1.255
1.256 for (NodeIt it(graph); it != INVALID; ++it) {
1.257 @@ -842,7 +842,7 @@
1.258 public:
1.259 typedef typename Graph::Node Node;
1.260 typedef typename Graph::Edge Edge;
1.261 - typedef typename Graph::UndirEdge UndirEdge;
1.262 + typedef typename Graph::UEdge UEdge;
1.263
1.264 CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum)
1.265 : _graph(graph), _compNum(compNum),
1.266 @@ -898,7 +898,7 @@
1.267 public:
1.268 typedef typename Graph::Node Node;
1.269 typedef typename Graph::Edge Edge;
1.270 - typedef typename Graph::UndirEdge UndirEdge;
1.271 + typedef typename Graph::UEdge UEdge;
1.272
1.273 BiEdgeConnectedComponentsVisitor(const Graph& graph,
1.274 NodeMap& compMap, int &compNum)
1.275 @@ -965,7 +965,7 @@
1.276 public:
1.277 typedef typename Graph::Node Node;
1.278 typedef typename Graph::Edge Edge;
1.279 - typedef typename Graph::UndirEdge UndirEdge;
1.280 + typedef typename Graph::UEdge UEdge;
1.281
1.282 BiEdgeConnectedCutEdgesVisitor(const Graph& graph,
1.283 EdgeMap& cutMap, int &cutNum)
1.284 @@ -1022,8 +1022,8 @@
1.285 };
1.286 }
1.287
1.288 - template <typename UndirGraph>
1.289 - int countbiEdgeConnectedComponents(const UndirGraph& graph);
1.290 + template <typename UGraph>
1.291 + int countbiEdgeConnectedComponents(const UGraph& graph);
1.292
1.293 /// \ingroup topology
1.294 ///
1.295 @@ -1036,8 +1036,8 @@
1.296 /// \param graph The undirected graph.
1.297 /// \return The number of components.
1.298 /// \todo Make it faster.
1.299 - template <typename UndirGraph>
1.300 - bool biEdgeConnected(const UndirGraph& graph) {
1.301 + template <typename UGraph>
1.302 + bool biEdgeConnected(const UGraph& graph) {
1.303 return countBiEdgeConnectedComponents(graph) == 1;
1.304 }
1.305
1.306 @@ -1052,19 +1052,19 @@
1.307 ///
1.308 /// \param graph The undirected graph.
1.309 /// \return The number of components.
1.310 - template <typename UndirGraph>
1.311 - int countBiEdgeConnectedComponents(const UndirGraph& graph) {
1.312 - checkConcept<concept::UndirGraph, UndirGraph>();
1.313 - typedef typename UndirGraph::NodeIt NodeIt;
1.314 + template <typename UGraph>
1.315 + int countBiEdgeConnectedComponents(const UGraph& graph) {
1.316 + checkConcept<concept::UGraph, UGraph>();
1.317 + typedef typename UGraph::NodeIt NodeIt;
1.318
1.319 using namespace _topology_bits;
1.320
1.321 - typedef CountBiEdgeConnectedComponentsVisitor<UndirGraph> Visitor;
1.322 + typedef CountBiEdgeConnectedComponentsVisitor<UGraph> Visitor;
1.323
1.324 int compNum = 0;
1.325 Visitor visitor(graph, compNum);
1.326
1.327 - DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
1.328 + DfsVisit<UGraph, Visitor> dfs(graph, visitor);
1.329 dfs.init();
1.330
1.331 for (NodeIt it(graph); it != INVALID; ++it) {
1.332 @@ -1095,21 +1095,21 @@
1.333 /// will be set continuously.
1.334 /// \return The number of components.
1.335 ///
1.336 - template <typename UndirGraph, typename NodeMap>
1.337 - int biEdgeConnectedComponents(const UndirGraph& graph, NodeMap& compMap) {
1.338 - checkConcept<concept::UndirGraph, UndirGraph>();
1.339 - typedef typename UndirGraph::NodeIt NodeIt;
1.340 - typedef typename UndirGraph::Node Node;
1.341 + template <typename UGraph, typename NodeMap>
1.342 + int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) {
1.343 + checkConcept<concept::UGraph, UGraph>();
1.344 + typedef typename UGraph::NodeIt NodeIt;
1.345 + typedef typename UGraph::Node Node;
1.346 checkConcept<concept::WriteMap<Node, int>, NodeMap>();
1.347
1.348 using namespace _topology_bits;
1.349
1.350 - typedef BiEdgeConnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
1.351 + typedef BiEdgeConnectedComponentsVisitor<UGraph, NodeMap> Visitor;
1.352
1.353 int compNum = 0;
1.354 Visitor visitor(graph, compMap, compNum);
1.355
1.356 - DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
1.357 + DfsVisit<UGraph, Visitor> dfs(graph, visitor);
1.358 dfs.init();
1.359
1.360 for (NodeIt it(graph); it != INVALID; ++it) {
1.361 @@ -1136,21 +1136,21 @@
1.362 /// \retval cutMap A writable node map. The values will be set true when the
1.363 /// edge is a cut edge.
1.364 /// \return The number of cut edges.
1.365 - template <typename UndirGraph, typename UndirEdgeMap>
1.366 - int biEdgeConnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) {
1.367 - checkConcept<concept::UndirGraph, UndirGraph>();
1.368 - typedef typename UndirGraph::NodeIt NodeIt;
1.369 - typedef typename UndirGraph::UndirEdge UndirEdge;
1.370 - checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>();
1.371 + template <typename UGraph, typename UEdgeMap>
1.372 + int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) {
1.373 + checkConcept<concept::UGraph, UGraph>();
1.374 + typedef typename UGraph::NodeIt NodeIt;
1.375 + typedef typename UGraph::UEdge UEdge;
1.376 + checkConcept<concept::WriteMap<UEdge, bool>, UEdgeMap>();
1.377
1.378 using namespace _topology_bits;
1.379
1.380 - typedef BiEdgeConnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
1.381 + typedef BiEdgeConnectedCutEdgesVisitor<UGraph, UEdgeMap> Visitor;
1.382
1.383 int cutNum = 0;
1.384 Visitor visitor(graph, cutMap, cutNum);
1.385
1.386 - DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
1.387 + DfsVisit<UGraph, Visitor> dfs(graph, visitor);
1.388 dfs.init();
1.389
1.390 for (NodeIt it(graph); it != INVALID; ++it) {
1.391 @@ -1326,13 +1326,13 @@
1.392 /// \param graph The undirected graph.
1.393 /// \return %True when there is no circle in the graph.
1.394 /// \see dag
1.395 - template <typename UndirGraph>
1.396 - bool acyclic(const UndirGraph& graph) {
1.397 - checkConcept<concept::UndirGraph, UndirGraph>();
1.398 - typedef typename UndirGraph::Node Node;
1.399 - typedef typename UndirGraph::NodeIt NodeIt;
1.400 - typedef typename UndirGraph::Edge Edge;
1.401 - Dfs<UndirGraph> dfs(graph);
1.402 + template <typename UGraph>
1.403 + bool acyclic(const UGraph& graph) {
1.404 + checkConcept<concept::UGraph, UGraph>();
1.405 + typedef typename UGraph::Node Node;
1.406 + typedef typename UGraph::NodeIt NodeIt;
1.407 + typedef typename UGraph::Edge Edge;
1.408 + Dfs<UGraph> dfs(graph);
1.409 dfs.init();
1.410 for (NodeIt it(graph); it != INVALID; ++it) {
1.411 if (!dfs.reached(it)) {
1.412 @@ -1359,13 +1359,13 @@
1.413 /// Check that the given undirected graph is tree.
1.414 /// \param graph The undirected graph.
1.415 /// \return %True when the graph is acyclic and connected.
1.416 - template <typename UndirGraph>
1.417 - bool tree(const UndirGraph& graph) {
1.418 - checkConcept<concept::UndirGraph, UndirGraph>();
1.419 - typedef typename UndirGraph::Node Node;
1.420 - typedef typename UndirGraph::NodeIt NodeIt;
1.421 - typedef typename UndirGraph::Edge Edge;
1.422 - Dfs<UndirGraph> dfs(graph);
1.423 + template <typename UGraph>
1.424 + bool tree(const UGraph& graph) {
1.425 + checkConcept<concept::UGraph, UGraph>();
1.426 + typedef typename UGraph::Node Node;
1.427 + typedef typename UGraph::NodeIt NodeIt;
1.428 + typedef typename UGraph::Edge Edge;
1.429 + Dfs<UGraph> dfs(graph);
1.430 dfs.init();
1.431 dfs.addSource(NodeIt(graph));
1.432 while (!dfs.emptyQueue()) {
1.433 @@ -1397,14 +1397,14 @@
1.434 /// \sa bipartitePartitions
1.435 ///
1.436 /// \author Balazs Attila Mihaly
1.437 - template<typename UndirGraph>
1.438 - inline bool bipartite(const UndirGraph &graph){
1.439 - checkConcept<concept::UndirGraph, UndirGraph>();
1.440 + template<typename UGraph>
1.441 + inline bool bipartite(const UGraph &graph){
1.442 + checkConcept<concept::UGraph, UGraph>();
1.443
1.444 - typedef typename UndirGraph::NodeIt NodeIt;
1.445 - typedef typename UndirGraph::EdgeIt EdgeIt;
1.446 + typedef typename UGraph::NodeIt NodeIt;
1.447 + typedef typename UGraph::EdgeIt EdgeIt;
1.448
1.449 - Bfs<UndirGraph> bfs(graph);
1.450 + Bfs<UGraph> bfs(graph);
1.451 bfs.init();
1.452 for(NodeIt i(graph);i!=INVALID;++i){
1.453 if(!bfs.reached(i)){
1.454 @@ -1434,15 +1434,15 @@
1.455 ///
1.456 /// \image html bipartite_partitions.png
1.457 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1.458 - template<typename UndirGraph, typename NodeMap>
1.459 - inline bool bipartitePartitions(const UndirGraph &graph, NodeMap &partMap){
1.460 - checkConcept<concept::UndirGraph, UndirGraph>();
1.461 + template<typename UGraph, typename NodeMap>
1.462 + inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
1.463 + checkConcept<concept::UGraph, UGraph>();
1.464
1.465 - typedef typename UndirGraph::Node Node;
1.466 - typedef typename UndirGraph::NodeIt NodeIt;
1.467 - typedef typename UndirGraph::EdgeIt EdgeIt;
1.468 + typedef typename UGraph::Node Node;
1.469 + typedef typename UGraph::NodeIt NodeIt;
1.470 + typedef typename UGraph::EdgeIt EdgeIt;
1.471
1.472 - Bfs<UndirGraph> bfs(graph);
1.473 + Bfs<UGraph> bfs(graph);
1.474 bfs.init();
1.475 for(NodeIt i(graph);i!=INVALID;++i){
1.476 if(!bfs.reached(i)){