lemon/topology.h
author deba
Fri, 04 Nov 2005 16:10:23 +0000
changeset 1769 a67ec111236c
parent 1763 49045f2d28d4
child 1793 d8130458dd86
permissions -rw-r--r--
Removed todo
Moved to topology module
deba@1698
     1
/* -*- C++ -*-
deba@1698
     2
 * lemon/topology.h - Part of LEMON, a generic C++ optimization library
deba@1698
     3
 *
deba@1698
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1698
     5
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1698
     6
 *
deba@1698
     7
 * Permission to use, modify and distribute this software is granted
deba@1698
     8
 * provided that this copyright notice appears in all copies. For
deba@1698
     9
 * precise terms see the accompanying LICENSE file.
deba@1698
    10
 *
deba@1698
    11
 * This software is provided "AS IS" with no warranty of any kind,
deba@1698
    12
 * express or implied, and with no claim as to its suitability for any
deba@1698
    13
 * purpose.
deba@1698
    14
 *
deba@1698
    15
 */
deba@1698
    16
deba@1698
    17
#ifndef LEMON_TOPOLOGY_H
deba@1698
    18
#define LEMON_TOPOLOGY_H
deba@1698
    19
deba@1698
    20
#include <lemon/dfs.h>
deba@1740
    21
#include <lemon/bfs.h>
deba@1698
    22
#include <lemon/graph_utils.h>
deba@1750
    23
#include <lemon/graph_adaptor.h>
deba@1750
    24
#include <lemon/maps.h>
deba@1698
    25
deba@1698
    26
#include <lemon/concept/graph.h>
deba@1698
    27
#include <lemon/concept/undir_graph.h>
deba@1698
    28
#include <lemon/concept_check.h>
deba@1698
    29
deba@1750
    30
#include <lemon/bin_heap.h>
deba@1750
    31
#include <lemon/linear_heap.h>
deba@1750
    32
deba@1750
    33
#include <stack>
deba@1750
    34
#include <functional>
deba@1750
    35
deba@1750
    36
/// \ingroup topology
deba@1698
    37
/// \file
deba@1698
    38
/// \brief Topology related algorithms
deba@1698
    39
///
deba@1698
    40
/// Topology related algorithms
deba@1698
    41
deba@1698
    42
namespace lemon {
deba@1698
    43
deba@1750
    44
  /// \ingroup topology
deba@1750
    45
  ///
deba@1750
    46
  /// \brief Check that the given undirected graph is connected.
deba@1750
    47
  ///
deba@1750
    48
  /// Check that the given undirected graph connected.
deba@1750
    49
  /// \param graph The undirected graph.
deba@1750
    50
  /// \return %True when there is path between any two nodes in the graph.
deba@1750
    51
  /// \warning The empty graph is not connected.
deba@1750
    52
  template <typename UndirGraph>
deba@1750
    53
  bool connected(const UndirGraph& graph) {
deba@1750
    54
    checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750
    55
    typedef typename UndirGraph::NodeIt NodeIt;
deba@1750
    56
    if (NodeIt(graph) == INVALID) return false;
deba@1750
    57
    Dfs<UndirGraph> dfs(graph);
deba@1750
    58
    dfs.run(NodeIt(graph));
deba@1750
    59
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
    60
      if (!dfs.reached(it)) {
deba@1750
    61
	return false;
deba@1750
    62
      }
deba@1750
    63
    }
deba@1750
    64
    return true;
deba@1750
    65
  }
deba@1750
    66
deba@1750
    67
  /// \ingroup topology
deba@1750
    68
  ///
deba@1750
    69
  /// \brief Count the number of connected components of an undirected graph
deba@1750
    70
  ///
deba@1750
    71
  /// Count the number of connected components of an undirected graph
deba@1750
    72
  ///
deba@1750
    73
  /// \param g The graph. In must be undirected.
deba@1750
    74
  /// \return The number of components
deba@1750
    75
  template <typename UndirGraph>
deba@1750
    76
  int countConnectedComponents(const UndirGraph &graph) {
deba@1750
    77
    checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750
    78
    typedef typename UndirGraph::Node Node;
deba@1750
    79
    typedef typename UndirGraph::Edge Edge;
deba@1750
    80
deba@1750
    81
    typedef NullMap<Node, Edge> PredMap;
deba@1750
    82
    typedef NullMap<Node, int> DistMap;
deba@1750
    83
deba@1750
    84
    int compNum = 0;
deba@1750
    85
    typename Bfs<UndirGraph>::
deba@1750
    86
      template DefPredMap<PredMap>::
deba@1750
    87
      template DefDistMap<DistMap>::
deba@1750
    88
      Create bfs(graph);
deba@1750
    89
deba@1750
    90
    PredMap predMap;
deba@1750
    91
    bfs.predMap(predMap);
deba@1750
    92
deba@1750
    93
    DistMap distMap;
deba@1750
    94
    bfs.distMap(distMap);
deba@1750
    95
deba@1750
    96
    bfs.init();
deba@1750
    97
    for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@1750
    98
      if (!bfs.reached(n)) {
deba@1750
    99
	bfs.addSource(n);
deba@1750
   100
	bfs.start();
deba@1750
   101
	++compNum;
deba@1750
   102
      }
deba@1750
   103
    }
deba@1750
   104
    return compNum;
deba@1750
   105
  }
deba@1750
   106
deba@1750
   107
  /// \ingroup topology
deba@1750
   108
  ///
deba@1750
   109
  /// \brief Find the connected components of an undirected graph
deba@1750
   110
  ///
deba@1750
   111
  /// Find the connected components of an undirected graph.
deba@1750
   112
  ///
deba@1763
   113
  /// \image html connected_components.png
deba@1763
   114
  /// \image latex connected_components.eps "Connected components" width=\textwidth
deba@1763
   115
  ///
deba@1750
   116
  /// \param g The graph. In must be undirected.
deba@1750
   117
  /// \retval comp A writable node map. The values will be set from 0 to
deba@1750
   118
  /// the number of the connected components minus one. Each values of the map
deba@1750
   119
  /// will be set exactly once, the values of a certain component will be
deba@1750
   120
  /// set continuously.
deba@1750
   121
  /// \return The number of components
deba@1763
   122
  ///
deba@1750
   123
  template <class UndirGraph, class NodeMap>
deba@1750
   124
  int connectedComponents(const UndirGraph &graph, NodeMap &compMap) {
deba@1750
   125
    checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750
   126
    typedef typename UndirGraph::Node Node;
deba@1750
   127
    typedef typename UndirGraph::Edge Edge;
deba@1750
   128
    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
deba@1750
   129
deba@1750
   130
    typedef NullMap<Node, Edge> PredMap;
deba@1750
   131
    typedef NullMap<Node, int> DistMap;
deba@1750
   132
deba@1750
   133
    int compNum = 0;
deba@1750
   134
    typename Bfs<UndirGraph>::
deba@1750
   135
      template DefPredMap<PredMap>::
deba@1750
   136
      template DefDistMap<DistMap>::
deba@1750
   137
      Create bfs(graph);
deba@1750
   138
deba@1750
   139
    PredMap predMap;
deba@1750
   140
    bfs.predMap(predMap);
deba@1750
   141
deba@1750
   142
    DistMap distMap;
deba@1750
   143
    bfs.distMap(distMap);
deba@1750
   144
    
deba@1750
   145
    bfs.init();
deba@1750
   146
    for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@1750
   147
      if(!bfs.reached(n)) {
deba@1750
   148
	bfs.addSource(n);
deba@1750
   149
	while (!bfs.emptyQueue()) {
deba@1750
   150
	  compMap.set(bfs.nextNode(), compNum);
deba@1750
   151
	  bfs.processNextNode();
deba@1750
   152
	}
deba@1750
   153
	++compNum;
deba@1750
   154
      }
deba@1750
   155
    }
deba@1750
   156
    return compNum;
deba@1750
   157
  }
deba@1750
   158
deba@1750
   159
  namespace _topology_bits {
deba@1750
   160
deba@1750
   161
    template <typename Graph, typename Iterator >
deba@1750
   162
    struct LeaveOrderVisitor : public DfsVisitor<Graph> {
deba@1750
   163
    public:
deba@1750
   164
      typedef typename Graph::Node Node;
deba@1750
   165
      LeaveOrderVisitor(Iterator it) : _it(it) {}
deba@1750
   166
deba@1750
   167
      void leave(const Node& node) {
deba@1750
   168
	*(_it++) = node;
deba@1750
   169
      }
deba@1750
   170
deba@1750
   171
    private:
deba@1750
   172
      Iterator _it;
deba@1750
   173
    };
deba@1750
   174
deba@1750
   175
    template <typename Graph, typename Map>
deba@1750
   176
    struct FillMapVisitor : public DfsVisitor<Graph> {
deba@1750
   177
    public:
deba@1750
   178
      typedef typename Graph::Node Node;
deba@1750
   179
      typedef typename Map::Value Value;
deba@1750
   180
deba@1750
   181
      FillMapVisitor(Map& map, Value& value) 
deba@1750
   182
	: _map(map), _value(value) {}
deba@1750
   183
deba@1750
   184
      void reach(const Node& node) {
deba@1750
   185
	_map.set(node, _value);
deba@1750
   186
      }
deba@1750
   187
    private:
deba@1750
   188
      Map& _map;
deba@1750
   189
      Value& _value;
deba@1750
   190
    };
deba@1750
   191
deba@1750
   192
    template <typename Graph, typename EdgeMap>
deba@1750
   193
    struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
deba@1750
   194
    public:
deba@1750
   195
      typedef typename Graph::Node Node;
deba@1750
   196
      typedef typename Graph::Edge Edge;
deba@1750
   197
deba@1750
   198
      StronglyConnectedCutEdgesVisitor(const Graph& graph, EdgeMap& cutMap, 
deba@1750
   199
				       int& cutNum) 
deba@1750
   200
	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 
deba@1750
   201
	  _compMap(graph), _num(0) {
deba@1750
   202
      }
deba@1750
   203
deba@1750
   204
      void stop(const Node&) {
deba@1750
   205
	++_num;
deba@1750
   206
      }
deba@1750
   207
deba@1750
   208
      void reach(const Node& node) {
deba@1750
   209
	_compMap.set(node, _num);
deba@1750
   210
      }
deba@1750
   211
deba@1750
   212
      void examine(const Edge& edge) {
deba@1750
   213
 	if (_compMap[_graph.source(edge)] != _compMap[_graph.target(edge)]) {
deba@1750
   214
 	  _cutMap.set(edge, true);
deba@1750
   215
 	  ++_cutNum;
deba@1750
   216
 	}
deba@1750
   217
      }
deba@1750
   218
    private:
deba@1750
   219
      const Graph& _graph;
deba@1750
   220
      EdgeMap& _cutMap;
deba@1750
   221
      int& _cutNum;
deba@1750
   222
deba@1750
   223
      typename Graph::template NodeMap<int> _compMap;
deba@1750
   224
      int _num;
deba@1750
   225
    };
deba@1750
   226
deba@1750
   227
  }
deba@1750
   228
deba@1750
   229
deba@1750
   230
  /// \ingroup topology
deba@1750
   231
  ///
deba@1750
   232
  /// \brief Check that the given directed graph is strongly connected.
deba@1750
   233
  ///
deba@1750
   234
  /// Check that the given directed graph is strongly connected. The
deba@1750
   235
  /// graph is strongly connected when any two nodes of the graph are
deba@1750
   236
  /// connected with directed pathes in both direction.
deba@1750
   237
  /// \return %False when the graph is not strongly connected.
deba@1750
   238
  /// \see connected
deba@1750
   239
  ///
deba@1750
   240
  /// \waning Empty graph is not strongly connected.
deba@1750
   241
  template <typename Graph>
deba@1750
   242
  bool stronglyConnected(const Graph& graph) {
deba@1750
   243
    checkConcept<concept::StaticGraph, Graph>();
deba@1750
   244
    if (NodeIt(graph) == INVALID) return false;
deba@1750
   245
deba@1750
   246
    typedef typename Graph::Node Node;
deba@1750
   247
    typedef typename Graph::NodeIt NodeIt;
deba@1750
   248
deba@1750
   249
    using namespace _topology_bits;
deba@1750
   250
deba@1750
   251
    typedef DfsVisitor<Graph> Visitor;
deba@1750
   252
    Visitor visitor;
deba@1750
   253
deba@1750
   254
    DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@1750
   255
    dfs.init();
deba@1750
   256
    dfs.addSource(NodeIt(graph));
deba@1750
   257
    dfs.start();
deba@1750
   258
deba@1750
   259
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
   260
      if (!dfs.reached(it)) {
deba@1750
   261
	return false;
deba@1750
   262
      }
deba@1750
   263
    }
deba@1750
   264
deba@1750
   265
    typedef RevGraphAdaptor<const Graph> RGraph;
deba@1750
   266
    RGraph rgraph(graph);
deba@1750
   267
deba@1750
   268
    typedef DfsVisitor<Graph> RVisitor;
deba@1750
   269
    RVisitor rvisitor;
deba@1750
   270
deba@1750
   271
    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
deba@1750
   272
    rdfs.init();    
deba@1750
   273
    rdfs.addSource(NodeIt(graph));
deba@1750
   274
    rdfs.start();
deba@1750
   275
deba@1750
   276
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
   277
      if (!rdfs.reached(it)) {
deba@1750
   278
	return false;
deba@1750
   279
      }
deba@1750
   280
    }
deba@1750
   281
deba@1750
   282
    return true;
deba@1750
   283
  }
deba@1750
   284
deba@1750
   285
  /// \ingroup topology
deba@1750
   286
  ///
deba@1750
   287
  /// \brief Count the strongly connected components of a directed graph
deba@1750
   288
  ///
deba@1750
   289
  /// Count the strongly connected components of a directed graph.
deba@1750
   290
  /// The strongly connected components are the classes of an equivalence
deba@1750
   291
  /// relation on the nodes of the graph. Two nodes are connected with
deba@1750
   292
  /// directed paths in both direction.
deba@1750
   293
  ///
deba@1750
   294
  /// \param g The graph.
deba@1750
   295
  /// \return The number of components
deba@1750
   296
  template <typename Graph>
deba@1750
   297
  int countStronglyConnectedComponents(const Graph& graph) {
deba@1750
   298
    checkConcept<concept::StaticGraph, Graph>();
deba@1750
   299
deba@1750
   300
    using namespace _topology_bits;
deba@1750
   301
deba@1750
   302
    typedef typename Graph::Node Node;
deba@1750
   303
    typedef typename Graph::Edge Edge;
deba@1750
   304
    typedef typename Graph::NodeIt NodeIt;
deba@1750
   305
    typedef typename Graph::EdgeIt EdgeIt;
deba@1750
   306
    
deba@1750
   307
    typedef std::vector<Node> Container;
deba@1750
   308
    typedef typename Container::iterator Iterator;
deba@1750
   309
deba@1750
   310
    Container nodes(countNodes(graph));
deba@1750
   311
    typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
deba@1750
   312
    Visitor visitor(nodes.begin());
deba@1750
   313
      
deba@1750
   314
    DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@1750
   315
    dfs.init();
deba@1750
   316
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
   317
      if (!dfs.reached(it)) {
deba@1750
   318
	dfs.addSource(it);
deba@1750
   319
	dfs.start();
deba@1750
   320
      }
deba@1750
   321
    }
deba@1750
   322
deba@1750
   323
    typedef typename Container::reverse_iterator RIterator;
deba@1750
   324
    typedef RevGraphAdaptor<const Graph> RGraph;
deba@1750
   325
deba@1750
   326
    RGraph rgraph(graph);
deba@1750
   327
deba@1750
   328
    typedef DfsVisitor<Graph> RVisitor;
deba@1750
   329
    RVisitor rvisitor;
deba@1750
   330
deba@1750
   331
    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
deba@1750
   332
deba@1750
   333
    int compNum = 0;
deba@1750
   334
deba@1750
   335
    rdfs.init();
deba@1750
   336
    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@1750
   337
      if (!rdfs.reached(*it)) {
deba@1750
   338
	rdfs.addSource(*it);
deba@1750
   339
	rdfs.start();
deba@1750
   340
	++compNum;
deba@1750
   341
      }
deba@1750
   342
    }
deba@1750
   343
    return compNum;
deba@1750
   344
  }
deba@1750
   345
deba@1750
   346
  /// \ingroup topology
deba@1750
   347
  ///
deba@1750
   348
  /// \brief Find the strongly connected components of a directed graph
deba@1750
   349
  ///
deba@1750
   350
  /// Find the strongly connected components of a directed graph.
deba@1750
   351
  /// The strongly connected components are the classes of an equivalence
deba@1750
   352
  /// relation on the nodes of the graph. Two nodes are in relationship
deba@1750
   353
  /// when there are directed paths between them in both direction.
deba@1750
   354
  ///
deba@1763
   355
  /// \image html strongly_connected_components.png
deba@1763
   356
  /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
deba@1763
   357
  ///
deba@1750
   358
  /// \param g The graph.
deba@1750
   359
  /// \retval comp A writable node map. The values will be set from 0 to
deba@1750
   360
  /// the number of the strongly connected components minus one. Each values 
deba@1750
   361
  /// of the map will be set exactly once, the values of a certain component 
deba@1750
   362
  /// will be set continuously.
deba@1750
   363
  /// \return The number of components
deba@1763
   364
  ///
deba@1750
   365
  template <typename Graph, typename NodeMap>
deba@1750
   366
  int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
deba@1750
   367
    checkConcept<concept::StaticGraph, Graph>();
deba@1750
   368
    typedef typename Graph::Node Node;
deba@1750
   369
    typedef typename Graph::NodeIt NodeIt;
deba@1750
   370
    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
deba@1750
   371
deba@1750
   372
    using namespace _topology_bits;
deba@1750
   373
    
deba@1750
   374
    typedef std::vector<Node> Container;
deba@1750
   375
    typedef typename Container::iterator Iterator;
deba@1750
   376
deba@1750
   377
    Container nodes(countNodes(graph));
deba@1750
   378
    typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
deba@1750
   379
    Visitor visitor(nodes.begin());
deba@1750
   380
      
deba@1750
   381
    DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@1750
   382
    dfs.init();
deba@1750
   383
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
   384
      if (!dfs.reached(it)) {
deba@1750
   385
	dfs.addSource(it);
deba@1750
   386
	dfs.start();
deba@1750
   387
      }
deba@1750
   388
    }
deba@1750
   389
deba@1750
   390
    typedef typename Container::reverse_iterator RIterator;
deba@1750
   391
    typedef RevGraphAdaptor<const Graph> RGraph;
deba@1750
   392
deba@1750
   393
    RGraph rgraph(graph);
deba@1750
   394
deba@1750
   395
    int compNum = 0;
deba@1750
   396
deba@1750
   397
    typedef FillMapVisitor<RGraph, NodeMap> RVisitor;
deba@1750
   398
    RVisitor rvisitor(compMap, compNum);
deba@1750
   399
deba@1750
   400
    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
deba@1750
   401
deba@1750
   402
    rdfs.init();
deba@1750
   403
    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@1750
   404
      if (!rdfs.reached(*it)) {
deba@1750
   405
	rdfs.addSource(*it);
deba@1750
   406
	rdfs.start();
deba@1750
   407
	++compNum;
deba@1750
   408
      }
deba@1750
   409
    }
deba@1750
   410
    return compNum;
deba@1750
   411
  }
deba@1750
   412
deba@1750
   413
  /// \ingroup topology
deba@1750
   414
  ///
deba@1750
   415
  /// \brief Find the cut edges of the strongly connected components.
deba@1750
   416
  ///
deba@1750
   417
  /// Find the cut edges of the strongly connected components.
deba@1750
   418
  /// The strongly connected components are the classes of an equivalence
deba@1750
   419
  /// relation on the nodes of the graph. Two nodes are in relationship
deba@1750
   420
  /// when there are directed paths between them in both direction.
deba@1750
   421
  /// The strongly connected components are separated by the cut edges.
deba@1750
   422
  ///
deba@1750
   423
  /// \param g The graph.
deba@1750
   424
  /// \retval comp A writable edge map. The values will be set true when
deba@1750
   425
  /// the edge is cut edge otherwise false.
deba@1750
   426
  ///
deba@1750
   427
  /// \return The number of cut edges
deba@1750
   428
  template <typename Graph, typename EdgeMap>
deba@1750
   429
  int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
deba@1750
   430
    checkConcept<concept::StaticGraph, Graph>();
deba@1750
   431
    typedef typename Graph::Node Node;
deba@1750
   432
    typedef typename Graph::Edge Edge;
deba@1750
   433
    typedef typename Graph::NodeIt NodeIt;
deba@1750
   434
    checkConcept<concept::WriteMap<Edge, bool>, EdgeMap>();
deba@1750
   435
deba@1750
   436
    using namespace _topology_bits;
deba@1750
   437
    
deba@1750
   438
    typedef std::vector<Node> Container;
deba@1750
   439
    typedef typename Container::iterator Iterator;
deba@1750
   440
deba@1750
   441
    Container nodes(countNodes(graph));
deba@1750
   442
    typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
deba@1750
   443
    Visitor visitor(nodes.begin());
deba@1750
   444
      
deba@1750
   445
    DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@1750
   446
    dfs.init();
deba@1750
   447
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
   448
      if (!dfs.reached(it)) {
deba@1750
   449
	dfs.addSource(it);
deba@1750
   450
	dfs.start();
deba@1750
   451
      }
deba@1750
   452
    }
deba@1750
   453
deba@1750
   454
    typedef typename Container::reverse_iterator RIterator;
deba@1750
   455
    typedef RevGraphAdaptor<const Graph> RGraph;
deba@1750
   456
deba@1750
   457
    RGraph rgraph(graph);
deba@1750
   458
deba@1750
   459
    int cutNum = 0;
deba@1750
   460
deba@1750
   461
    typedef StronglyConnectedCutEdgesVisitor<RGraph, EdgeMap> RVisitor;
deba@1750
   462
    RVisitor rvisitor(rgraph, cutMap, cutNum);
deba@1750
   463
deba@1750
   464
    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
deba@1750
   465
deba@1750
   466
    rdfs.init();
deba@1750
   467
    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@1750
   468
      if (!rdfs.reached(*it)) {
deba@1750
   469
	rdfs.addSource(*it);
deba@1750
   470
	rdfs.start();
deba@1750
   471
      }
deba@1750
   472
    }
deba@1750
   473
    return cutNum;
deba@1750
   474
  }
deba@1750
   475
deba@1698
   476
  namespace _topology_bits {
deba@1698
   477
    
deba@1750
   478
    template <typename Graph>
deba@1750
   479
    class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
deba@1698
   480
    public:
deba@1750
   481
      typedef typename Graph::Node Node;
deba@1750
   482
      typedef typename Graph::Edge Edge;
deba@1750
   483
      typedef typename Graph::UndirEdge UndirEdge;
deba@1698
   484
deba@1750
   485
      CountNodeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) 
deba@1750
   486
	: _graph(graph), _compNum(compNum), 
deba@1750
   487
	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@1750
   488
deba@1750
   489
      void start(const Node& node) {
deba@1750
   490
	_predMap.set(node, INVALID);
deba@1750
   491
      }
deba@1750
   492
      
deba@1750
   493
      void reach(const Node& node) {
deba@1750
   494
	_numMap.set(node, _num);
deba@1750
   495
	_retMap.set(node, _num);
deba@1750
   496
	++_num;
deba@1750
   497
      }
deba@1750
   498
deba@1750
   499
      void discover(const Edge& edge) {
deba@1750
   500
	_predMap.set(_graph.target(edge), _graph.source(edge));
deba@1750
   501
      }
deba@1750
   502
deba@1750
   503
      void examine(const Edge& edge) {
deba@1750
   504
	if (_graph.source(edge) == _graph.target(edge) && 
deba@1750
   505
	    _graph.direction(edge)) {
deba@1750
   506
	  ++_compNum;
deba@1750
   507
	  return;
deba@1750
   508
	}
deba@1750
   509
	if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
deba@1750
   510
	  return;
deba@1750
   511
	}
deba@1750
   512
	if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
deba@1750
   513
	  _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
deba@1698
   514
	}
deba@1698
   515
      }
deba@1698
   516
deba@1750
   517
      void backtrack(const Edge& edge) {
deba@1750
   518
	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750
   519
	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750
   520
	}  
deba@1750
   521
	if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
deba@1750
   522
	  ++_compNum;
deba@1750
   523
	}
deba@1750
   524
      }
deba@1750
   525
      
deba@1750
   526
    private:
deba@1750
   527
      const Graph& _graph;
deba@1750
   528
      int& _compNum; 
deba@1750
   529
deba@1750
   530
      typename Graph::template NodeMap<int> _numMap;
deba@1750
   531
      typename Graph::template NodeMap<int> _retMap;
deba@1750
   532
      typename Graph::template NodeMap<Node> _predMap;
deba@1750
   533
      int _num;
deba@1750
   534
    };
deba@1750
   535
deba@1750
   536
    template <typename Graph, typename EdgeMap>
deba@1750
   537
    class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
deba@1750
   538
    public:
deba@1750
   539
      typedef typename Graph::Node Node;
deba@1750
   540
      typedef typename Graph::Edge Edge;
deba@1750
   541
      typedef typename Graph::UndirEdge UndirEdge;
deba@1750
   542
deba@1750
   543
      NodeBiconnectedComponentsVisitor(const Graph& graph, 
deba@1750
   544
				       EdgeMap& compMap, int &compNum) 
deba@1750
   545
	: _graph(graph), _compMap(compMap), _compNum(compNum), 
deba@1750
   546
	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@1750
   547
deba@1750
   548
      void start(const Node& node) {
deba@1750
   549
	_predMap.set(node, INVALID);
deba@1750
   550
      }
deba@1750
   551
      
deba@1750
   552
      void reach(const Node& node) {
deba@1750
   553
	_numMap.set(node, _num);
deba@1750
   554
	_retMap.set(node, _num);
deba@1750
   555
	++_num;
deba@1750
   556
      }
deba@1750
   557
deba@1750
   558
      void discover(const Edge& edge) {
deba@1750
   559
	Node target = _graph.target(edge);
deba@1750
   560
	_predMap.set(target, edge);
deba@1750
   561
	_edgeStack.push(edge);
deba@1750
   562
      }
deba@1750
   563
deba@1750
   564
      void examine(const Edge& edge) {
deba@1750
   565
	Node source = _graph.source(edge);
deba@1750
   566
	Node target = _graph.target(edge);
deba@1750
   567
	if (source == target && _graph.direction(edge)) {
deba@1750
   568
	  _compMap.set(edge, _compNum);
deba@1750
   569
	  ++_compNum;
deba@1750
   570
	  return;
deba@1750
   571
	}
deba@1750
   572
	if (_numMap[target] < _numMap[source]) {
deba@1750
   573
	  if (_predMap[source] != _graph.oppositeEdge(edge)) {
deba@1750
   574
	    _edgeStack.push(edge);
deba@1750
   575
	  }
deba@1750
   576
	}
deba@1750
   577
	if (_predMap[source] != INVALID && 
deba@1750
   578
	    target == _graph.source(_predMap[source])) {
deba@1750
   579
	  return;
deba@1750
   580
	}
deba@1750
   581
	if (_retMap[source] > _numMap[target]) {
deba@1750
   582
	  _retMap.set(source, _numMap[target]);
deba@1750
   583
	}
deba@1750
   584
      }
deba@1750
   585
deba@1750
   586
      void backtrack(const Edge& edge) {
deba@1750
   587
	Node source = _graph.source(edge);
deba@1750
   588
	Node target = _graph.target(edge);
deba@1750
   589
	if (_retMap[source] > _retMap[target]) {
deba@1750
   590
	  _retMap.set(source, _retMap[target]);
deba@1750
   591
	}  
deba@1750
   592
	if (_numMap[source] <= _retMap[target]) {
deba@1750
   593
	  while (_edgeStack.top() != edge) {
deba@1750
   594
	    _compMap.set(_edgeStack.top(), _compNum);
deba@1750
   595
	    _edgeStack.pop();
deba@1750
   596
	  }
deba@1750
   597
	  _compMap.set(edge, _compNum);
deba@1750
   598
	  _edgeStack.pop();
deba@1750
   599
	  ++_compNum;
deba@1750
   600
	}
deba@1750
   601
      }
deba@1750
   602
      
deba@1750
   603
    private:
deba@1750
   604
      const Graph& _graph;
deba@1750
   605
      EdgeMap& _compMap;
deba@1750
   606
      int& _compNum; 
deba@1750
   607
deba@1750
   608
      typename Graph::template NodeMap<int> _numMap;
deba@1750
   609
      typename Graph::template NodeMap<int> _retMap;
deba@1750
   610
      typename Graph::template NodeMap<Edge> _predMap;
deba@1750
   611
      std::stack<UndirEdge> _edgeStack;
deba@1750
   612
      int _num;
deba@1750
   613
    };
deba@1750
   614
deba@1750
   615
deba@1750
   616
    template <typename Graph, typename NodeMap>
deba@1750
   617
    class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> {
deba@1750
   618
    public:
deba@1750
   619
      typedef typename Graph::Node Node;
deba@1750
   620
      typedef typename Graph::Edge Edge;
deba@1750
   621
      typedef typename Graph::UndirEdge UndirEdge;
deba@1750
   622
deba@1750
   623
      NodeBiconnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
deba@1750
   624
				     int& cutNum) 
deba@1750
   625
	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
deba@1750
   626
	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@1750
   627
deba@1750
   628
      void start(const Node& node) {
deba@1750
   629
	_predMap.set(node, INVALID);
deba@1750
   630
	rootCut = false;
deba@1750
   631
      }
deba@1750
   632
      
deba@1750
   633
      void reach(const Node& node) {
deba@1750
   634
	_numMap.set(node, _num);
deba@1750
   635
	_retMap.set(node, _num);
deba@1750
   636
	++_num;
deba@1750
   637
      }
deba@1750
   638
deba@1750
   639
      void discover(const Edge& edge) {
deba@1750
   640
	_predMap.set(_graph.target(edge), _graph.source(edge));
deba@1750
   641
      }
deba@1750
   642
deba@1750
   643
      void examine(const Edge& edge) {
deba@1750
   644
	if (_graph.source(edge) == _graph.target(edge) && 
deba@1750
   645
	    _graph.direction(edge)) {
deba@1750
   646
	  if (!_cutMap[_graph.source(edge)]) {
deba@1750
   647
	    _cutMap.set(_graph.source(edge), true);
deba@1750
   648
	    ++_cutNum;
deba@1750
   649
	  }
deba@1750
   650
	  return;
deba@1750
   651
	}
deba@1750
   652
	if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
deba@1750
   653
	if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
deba@1750
   654
	  _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
deba@1750
   655
	}
deba@1750
   656
      }
deba@1750
   657
deba@1750
   658
      void backtrack(const Edge& edge) {
deba@1750
   659
	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750
   660
	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750
   661
	}  
deba@1750
   662
	if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
deba@1750
   663
	  if (_predMap[_graph.source(edge)] != INVALID) {
deba@1750
   664
	    if (!_cutMap[_graph.source(edge)]) {
deba@1750
   665
	      _cutMap.set(_graph.source(edge), true);
deba@1750
   666
	      ++_cutNum;
deba@1750
   667
	    }
deba@1750
   668
	  } else if (rootCut) {
deba@1750
   669
	    if (!_cutMap[_graph.source(edge)]) {
deba@1750
   670
	      _cutMap.set(_graph.source(edge), true);
deba@1750
   671
	      ++_cutNum;
deba@1750
   672
	    }
deba@1750
   673
	  } else {
deba@1750
   674
	    rootCut = true;
deba@1750
   675
	  }
deba@1750
   676
	}
deba@1750
   677
      }
deba@1750
   678
      
deba@1750
   679
    private:
deba@1750
   680
      const Graph& _graph;
deba@1750
   681
      NodeMap& _cutMap;
deba@1750
   682
      int& _cutNum; 
deba@1750
   683
deba@1750
   684
      typename Graph::template NodeMap<int> _numMap;
deba@1750
   685
      typename Graph::template NodeMap<int> _retMap;
deba@1750
   686
      typename Graph::template NodeMap<Node> _predMap;
deba@1750
   687
      std::stack<UndirEdge> _edgeStack;
deba@1750
   688
      int _num;
deba@1750
   689
      bool rootCut;
deba@1750
   690
    };
deba@1750
   691
deba@1750
   692
  }
deba@1750
   693
deba@1750
   694
  template <typename UndirGraph>
deba@1750
   695
  int countNodeBiconnectedComponents(const UndirGraph& graph);
deba@1750
   696
deba@1750
   697
  /// \ingroup topology
deba@1750
   698
  ///
deba@1767
   699
  /// \brief Checks the graph is bi-node-connected.
deba@1750
   700
  ///
deba@1767
   701
  /// This function checks that the undirected graph is bi-node-connected  
deba@1767
   702
  /// graph. The graph is bi-node-connected if any two undirected edge is 
deba@1750
   703
  /// on same circle.
deba@1750
   704
  ///
deba@1750
   705
  /// \param graph The graph.
deba@1767
   706
  /// \return %True when the graph bi-node-connected.
deba@1750
   707
  /// \todo Make it faster.
deba@1750
   708
  template <typename UndirGraph>
deba@1767
   709
  bool biNodeConnected(const UndirGraph& graph) {
deba@1750
   710
    return countNodeBiconnectedComponents(graph) == 1;
deba@1750
   711
  }
deba@1750
   712
deba@1750
   713
  /// \ingroup topology
deba@1750
   714
  ///
deba@1750
   715
  /// \brief Count the biconnected components.
deba@1750
   716
  ///
deba@1767
   717
  /// This function finds the bi-node-connected components in an undirected 
deba@1750
   718
  /// graph. The biconnected components are the classes of an equivalence 
deba@1750
   719
  /// relation on the undirected edges. Two undirected edge is in relationship
deba@1750
   720
  /// when they are on same circle.
deba@1750
   721
  ///
deba@1750
   722
  /// \param graph The graph.
deba@1750
   723
  /// \return The number of components.
deba@1750
   724
  template <typename UndirGraph>
deba@1750
   725
  int countNodeBiconnectedComponents(const UndirGraph& graph) {
deba@1750
   726
    checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750
   727
    typedef typename UndirGraph::NodeIt NodeIt;
deba@1750
   728
deba@1750
   729
    using namespace _topology_bits;
deba@1750
   730
deba@1750
   731
    typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor;
deba@1750
   732
deba@1750
   733
    int compNum = 0;
deba@1750
   734
    Visitor visitor(graph, compNum);
deba@1750
   735
deba@1750
   736
    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
deba@1750
   737
    dfs.init();
deba@1750
   738
    
deba@1750
   739
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
   740
      if (!dfs.reached(it)) {
deba@1750
   741
	dfs.addSource(it);
deba@1750
   742
	dfs.start();
deba@1750
   743
      }
deba@1750
   744
    }
deba@1750
   745
    return compNum;
deba@1750
   746
  }
deba@1750
   747
deba@1750
   748
  /// \ingroup topology
deba@1750
   749
  ///
deba@1767
   750
  /// \brief Find the bi-node-connected components.
deba@1750
   751
  ///
deba@1767
   752
  /// This function finds the bi-node-connected components in an undirected 
deba@1767
   753
  /// graph. The bi-node-connected components are the classes of an equivalence
deba@1750
   754
  /// relation on the undirected edges. Two undirected edge are in relationship
deba@1750
   755
  /// when they are on same circle.
deba@1750
   756
  ///
deba@1763
   757
  /// \image html node_biconnected_components.png
deba@1767
   758
  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
deba@1763
   759
  ///
deba@1750
   760
  /// \param graph The graph.
deba@1750
   761
  /// \retval comp A writable undir edge map. The values will be set from 0 to
deba@1750
   762
  /// the number of the biconnected components minus one. Each values 
deba@1750
   763
  /// of the map will be set exactly once, the values of a certain component 
deba@1750
   764
  /// will be set continuously.
deba@1750
   765
  /// \return The number of components.
deba@1763
   766
  ///
deba@1750
   767
  template <typename UndirGraph, typename UndirEdgeMap>
deba@1767
   768
  int biNodeConnectedComponents(const UndirGraph& graph, 
deba@1750
   769
				UndirEdgeMap& compMap) {
deba@1750
   770
    checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750
   771
    typedef typename UndirGraph::NodeIt NodeIt;
deba@1750
   772
    typedef typename UndirGraph::UndirEdge UndirEdge;
deba@1750
   773
    checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>();
deba@1750
   774
deba@1750
   775
    using namespace _topology_bits;
deba@1750
   776
deba@1750
   777
    typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
deba@1750
   778
    
deba@1750
   779
    int compNum = 0;
deba@1750
   780
    Visitor visitor(graph, compMap, compNum);
deba@1750
   781
deba@1750
   782
    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
deba@1750
   783
    dfs.init();
deba@1750
   784
    
deba@1750
   785
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
   786
      if (!dfs.reached(it)) {
deba@1750
   787
	dfs.addSource(it);
deba@1750
   788
	dfs.start();
deba@1750
   789
      }
deba@1750
   790
    }
deba@1750
   791
    return compNum;
deba@1750
   792
  }
deba@1750
   793
deba@1750
   794
  /// \ingroup topology
deba@1750
   795
  ///
deba@1767
   796
  /// \brief Find the bi-node-connected cut nodes.
deba@1750
   797
  ///
deba@1767
   798
  /// This function finds the bi-node-connected cut nodes in an undirected 
deba@1767
   799
  /// graph. The bi-node-connected components are the classes of an equivalence
deba@1750
   800
  /// relation on the undirected edges. Two undirected edges are in 
deba@1750
   801
  /// relationship when they are on same circle. The biconnected components 
deba@1750
   802
  /// are separted by nodes which are the cut nodes of the components.
deba@1750
   803
  ///
deba@1750
   804
  /// \param graph The graph.
deba@1750
   805
  /// \retval comp A writable edge map. The values will be set true when
deba@1750
   806
  /// the node separate two or more components.
deba@1750
   807
  /// \return The number of the cut nodes.
deba@1750
   808
  template <typename UndirGraph, typename NodeMap>
deba@1767
   809
  int biNodeConnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) {
deba@1750
   810
    checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750
   811
    typedef typename UndirGraph::Node Node;
deba@1750
   812
    typedef typename UndirGraph::NodeIt NodeIt;
deba@1750
   813
    checkConcept<concept::WriteMap<Node, bool>, NodeMap>();
deba@1750
   814
deba@1750
   815
    using namespace _topology_bits;
deba@1750
   816
deba@1750
   817
    typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
deba@1750
   818
    
deba@1750
   819
    int cutNum = 0;
deba@1750
   820
    Visitor visitor(graph, cutMap, cutNum);
deba@1750
   821
deba@1750
   822
    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
deba@1750
   823
    dfs.init();
deba@1750
   824
    
deba@1750
   825
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
   826
      if (!dfs.reached(it)) {
deba@1750
   827
	dfs.addSource(it);
deba@1750
   828
	dfs.start();
deba@1750
   829
      }
deba@1750
   830
    }
deba@1750
   831
    return cutNum;
deba@1750
   832
  }
deba@1750
   833
deba@1750
   834
  namespace _topology_bits {
deba@1750
   835
    
deba@1750
   836
    template <typename Graph>
deba@1750
   837
    class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
deba@1750
   838
    public:
deba@1750
   839
      typedef typename Graph::Node Node;
deba@1750
   840
      typedef typename Graph::Edge Edge;
deba@1750
   841
      typedef typename Graph::UndirEdge UndirEdge;
deba@1750
   842
deba@1750
   843
      CountEdgeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) 
deba@1750
   844
	: _graph(graph), _compNum(compNum), 
deba@1750
   845
	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@1750
   846
deba@1750
   847
      void start(const Node& node) {
deba@1750
   848
	_predMap.set(node, INVALID);
deba@1750
   849
      }
deba@1750
   850
      
deba@1750
   851
      void reach(const Node& node) {
deba@1750
   852
	_numMap.set(node, _num);
deba@1750
   853
	_retMap.set(node, _num);
deba@1750
   854
	++_num;
deba@1750
   855
      }
deba@1750
   856
      
deba@1750
   857
      void leave(const Node& node) {
deba@1750
   858
	if (_numMap[node] <= _retMap[node]) {
deba@1750
   859
	  ++_compNum;
deba@1750
   860
	}	
deba@1750
   861
      }
deba@1750
   862
deba@1750
   863
      void discover(const Edge& edge) {
deba@1750
   864
	_predMap.set(_graph.target(edge), edge);
deba@1750
   865
      }
deba@1750
   866
deba@1750
   867
      void examine(const Edge& edge) {
deba@1750
   868
	if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
deba@1750
   869
	  return;
deba@1750
   870
	}
deba@1750
   871
	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750
   872
	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750
   873
	}
deba@1750
   874
      }
deba@1750
   875
deba@1750
   876
      void backtrack(const Edge& edge) {
deba@1750
   877
	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750
   878
	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750
   879
	}  
deba@1750
   880
      }
deba@1750
   881
      
deba@1750
   882
    private:
deba@1750
   883
      const Graph& _graph;
deba@1750
   884
      int& _compNum; 
deba@1750
   885
deba@1750
   886
      typename Graph::template NodeMap<int> _numMap;
deba@1750
   887
      typename Graph::template NodeMap<int> _retMap;
deba@1750
   888
      typename Graph::template NodeMap<Edge> _predMap;
deba@1750
   889
      int _num;
deba@1750
   890
    };
deba@1750
   891
deba@1750
   892
    template <typename Graph, typename NodeMap>
deba@1750
   893
    class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
deba@1750
   894
    public:
deba@1750
   895
      typedef typename Graph::Node Node;
deba@1750
   896
      typedef typename Graph::Edge Edge;
deba@1750
   897
      typedef typename Graph::UndirEdge UndirEdge;
deba@1750
   898
deba@1750
   899
      EdgeBiconnectedComponentsVisitor(const Graph& graph, 
deba@1750
   900
				       NodeMap& compMap, int &compNum) 
deba@1750
   901
	: _graph(graph), _compMap(compMap), _compNum(compNum), 
deba@1750
   902
	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@1750
   903
deba@1750
   904
      void start(const Node& node) {
deba@1750
   905
	_predMap.set(node, INVALID);
deba@1750
   906
      }
deba@1750
   907
      
deba@1750
   908
      void reach(const Node& node) {
deba@1750
   909
	_numMap.set(node, _num);
deba@1750
   910
	_retMap.set(node, _num);
deba@1750
   911
	_nodeStack.push(node);
deba@1750
   912
	++_num;
deba@1750
   913
      }
deba@1750
   914
      
deba@1750
   915
      void leave(const Node& node) {
deba@1750
   916
	if (_numMap[node] <= _retMap[node]) {
deba@1750
   917
	  while (_nodeStack.top() != node) {
deba@1750
   918
	    _compMap.set(_nodeStack.top(), _compNum);
deba@1750
   919
	    _nodeStack.pop();
deba@1750
   920
	  }
deba@1750
   921
	  _compMap.set(node, _compNum);
deba@1750
   922
	  _nodeStack.pop();
deba@1750
   923
	  ++_compNum;
deba@1750
   924
	}	
deba@1750
   925
      }
deba@1750
   926
deba@1750
   927
      void discover(const Edge& edge) {
deba@1750
   928
	_predMap.set(_graph.target(edge), edge);
deba@1750
   929
      }
deba@1750
   930
deba@1750
   931
      void examine(const Edge& edge) {
deba@1750
   932
	if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
deba@1750
   933
	  return;
deba@1750
   934
	}
deba@1750
   935
	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750
   936
	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750
   937
	}
deba@1750
   938
      }
deba@1750
   939
deba@1750
   940
      void backtrack(const Edge& edge) {
deba@1750
   941
	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750
   942
	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750
   943
	}  
deba@1750
   944
      }
deba@1750
   945
      
deba@1750
   946
    private:
deba@1750
   947
      const Graph& _graph;
deba@1750
   948
      NodeMap& _compMap;
deba@1750
   949
      int& _compNum; 
deba@1750
   950
deba@1750
   951
      typename Graph::template NodeMap<int> _numMap;
deba@1750
   952
      typename Graph::template NodeMap<int> _retMap;
deba@1750
   953
      typename Graph::template NodeMap<Edge> _predMap;
deba@1750
   954
      std::stack<Node> _nodeStack;
deba@1750
   955
      int _num;
deba@1750
   956
    };
deba@1750
   957
deba@1750
   958
deba@1750
   959
    template <typename Graph, typename EdgeMap>
deba@1750
   960
    class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> {
deba@1750
   961
    public:
deba@1750
   962
      typedef typename Graph::Node Node;
deba@1750
   963
      typedef typename Graph::Edge Edge;
deba@1750
   964
      typedef typename Graph::UndirEdge UndirEdge;
deba@1750
   965
deba@1750
   966
      EdgeBiconnectedCutEdgesVisitor(const Graph& graph, 
deba@1750
   967
				     EdgeMap& cutMap, int &cutNum) 
deba@1750
   968
	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 
deba@1750
   969
	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@1750
   970
deba@1750
   971
      void start(const Node& node) {
deba@1750
   972
	_predMap[node] = INVALID;
deba@1750
   973
      }
deba@1750
   974
      
deba@1750
   975
      void reach(const Node& node) {
deba@1750
   976
	_numMap.set(node, _num);
deba@1750
   977
	_retMap.set(node, _num);
deba@1750
   978
	++_num;
deba@1750
   979
      }
deba@1750
   980
      
deba@1750
   981
      void leave(const Node& node) {
deba@1750
   982
	if (_numMap[node] <= _retMap[node]) {
deba@1750
   983
	  if (_predMap[node] != INVALID) {
deba@1750
   984
	    _cutMap.set(_predMap[node], true);
deba@1750
   985
	    ++_cutNum;
deba@1750
   986
	  }
deba@1750
   987
	}	
deba@1750
   988
      }
deba@1750
   989
deba@1750
   990
      void discover(const Edge& edge) {
deba@1750
   991
	_predMap.set(_graph.target(edge), edge);
deba@1750
   992
      }
deba@1750
   993
deba@1750
   994
      void examine(const Edge& edge) {
deba@1750
   995
	if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
deba@1750
   996
	  return;
deba@1750
   997
	}
deba@1750
   998
	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750
   999
	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750
  1000
	}
deba@1750
  1001
      }
deba@1750
  1002
deba@1750
  1003
      void backtrack(const Edge& edge) {
deba@1750
  1004
	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750
  1005
	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750
  1006
	}  
deba@1750
  1007
      }
deba@1750
  1008
      
deba@1750
  1009
    private:
deba@1750
  1010
      const Graph& _graph;
deba@1750
  1011
      EdgeMap& _cutMap;
deba@1750
  1012
      int& _cutNum; 
deba@1750
  1013
deba@1750
  1014
      typename Graph::template NodeMap<int> _numMap;
deba@1750
  1015
      typename Graph::template NodeMap<int> _retMap;
deba@1750
  1016
      typename Graph::template NodeMap<Edge> _predMap;
deba@1750
  1017
      int _num;
deba@1750
  1018
    };
deba@1750
  1019
  }
deba@1750
  1020
deba@1750
  1021
  template <typename UndirGraph>
deba@1750
  1022
  int countEdgeBiconnectedComponents(const UndirGraph& graph);
deba@1750
  1023
deba@1750
  1024
  /// \ingroup topology
deba@1750
  1025
  ///
deba@1767
  1026
  /// \brief Checks that the graph is bi-edge-connected.
deba@1750
  1027
  ///
deba@1767
  1028
  /// This function checks that the graph is bi-edge-connected. The undirected
deba@1767
  1029
  /// graph is bi-edge-connected when any two nodes are connected with two
deba@1750
  1030
  /// edge-disjoint paths.
deba@1750
  1031
  ///
deba@1750
  1032
  /// \param graph The undirected graph.
deba@1750
  1033
  /// \return The number of components.
deba@1750
  1034
  /// \todo Make it faster.
deba@1750
  1035
  template <typename UndirGraph>
deba@1767
  1036
  bool biEdgeConnected(const UndirGraph& graph) { 
deba@1750
  1037
    return countEdgeBiconnectedComponents(graph) == 1;
deba@1750
  1038
  }
deba@1750
  1039
deba@1750
  1040
  /// \ingroup topology
deba@1750
  1041
  ///
deba@1767
  1042
  /// \brief Count the bi-edge-connected components.
deba@1750
  1043
  ///
deba@1767
  1044
  /// This function count the bi-edge-connected components in an undirected 
deba@1767
  1045
  /// graph. The bi-edge-connected components are the classes of an equivalence
deba@1750
  1046
  /// relation on the nodes. Two nodes are in relationship when they are  
deba@1750
  1047
  /// connected with at least two edge-disjoint paths.
deba@1750
  1048
  ///
deba@1750
  1049
  /// \param graph The undirected graph.
deba@1750
  1050
  /// \return The number of components.
deba@1750
  1051
  template <typename UndirGraph>
deba@1750
  1052
  int countEdgeBiconnectedComponents(const UndirGraph& graph) { 
deba@1750
  1053
    checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750
  1054
    typedef typename UndirGraph::NodeIt NodeIt;
deba@1750
  1055
deba@1750
  1056
    using namespace _topology_bits;
deba@1750
  1057
deba@1750
  1058
    typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor;
deba@1750
  1059
    
deba@1750
  1060
    int compNum = 0;
deba@1750
  1061
    Visitor visitor(graph, compNum);
deba@1750
  1062
deba@1750
  1063
    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
deba@1750
  1064
    dfs.init();
deba@1750
  1065
    
deba@1750
  1066
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
  1067
      if (!dfs.reached(it)) {
deba@1750
  1068
	dfs.addSource(it);
deba@1750
  1069
	dfs.start();
deba@1750
  1070
      }
deba@1750
  1071
    }
deba@1750
  1072
    return compNum;
deba@1750
  1073
  }
deba@1750
  1074
deba@1750
  1075
  /// \ingroup topology
deba@1750
  1076
  ///
deba@1767
  1077
  /// \brief Find the bi-edge-connected components.
deba@1750
  1078
  ///
deba@1767
  1079
  /// This function finds the bi-edge-connected components in an undirected 
deba@1767
  1080
  /// graph. The bi-edge-connected components are the classes of an equivalence
deba@1750
  1081
  /// relation on the nodes. Two nodes are in relationship when they are  
deba@1750
  1082
  /// connected at least two edge-disjoint paths.
deba@1750
  1083
  ///
deba@1763
  1084
  /// \image html edge_biconnected_components.png
deba@1767
  1085
  /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
deba@1763
  1086
  ///
deba@1750
  1087
  /// \param graph The graph.
deba@1750
  1088
  /// \retval comp A writable node map. The values will be set from 0 to
deba@1750
  1089
  /// the number of the biconnected components minus one. Each values 
deba@1750
  1090
  /// of the map will be set exactly once, the values of a certain component 
deba@1750
  1091
  /// will be set continuously.
deba@1750
  1092
  /// \return The number of components.
deba@1763
  1093
  ///
deba@1750
  1094
  template <typename UndirGraph, typename NodeMap>
deba@1767
  1095
  int biEdgeConnectedComponents(const UndirGraph& graph, NodeMap& compMap) { 
deba@1750
  1096
    checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750
  1097
    typedef typename UndirGraph::NodeIt NodeIt;
deba@1750
  1098
    typedef typename UndirGraph::Node Node;
deba@1750
  1099
    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
deba@1750
  1100
deba@1750
  1101
    using namespace _topology_bits;
deba@1750
  1102
deba@1750
  1103
    typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
deba@1750
  1104
    
deba@1750
  1105
    int compNum = 0;
deba@1750
  1106
    Visitor visitor(graph, compMap, compNum);
deba@1750
  1107
deba@1750
  1108
    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
deba@1750
  1109
    dfs.init();
deba@1750
  1110
    
deba@1750
  1111
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
  1112
      if (!dfs.reached(it)) {
deba@1750
  1113
	dfs.addSource(it);
deba@1750
  1114
	dfs.start();
deba@1750
  1115
      }
deba@1750
  1116
    }
deba@1750
  1117
    return compNum;
deba@1750
  1118
  }
deba@1750
  1119
deba@1750
  1120
  /// \ingroup topology
deba@1750
  1121
  ///
deba@1767
  1122
  /// \brief Find the bi-edge-connected cut edges.
deba@1750
  1123
  ///
deba@1767
  1124
  /// This function finds the bi-edge-connected components in an undirected 
deba@1767
  1125
  /// graph. The bi-edge-connected components are the classes of an equivalence
deba@1750
  1126
  /// relation on the nodes. Two nodes are in relationship when they are 
deba@1767
  1127
  /// connected with at least two edge-disjoint paths. The bi-edge-connected 
deba@1750
  1128
  /// components are separted by edges which are the cut edges of the 
deba@1750
  1129
  /// components.
deba@1750
  1130
  ///
deba@1750
  1131
  /// \param graph The graph.
deba@1750
  1132
  /// \retval comp A writable node map. The values will be set true when the
deba@1750
  1133
  /// edge is a cut edge.
deba@1750
  1134
  /// \return The number of cut edges.
deba@1750
  1135
  template <typename UndirGraph, typename UndirEdgeMap>
deba@1767
  1136
  int biEdgeConnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) { 
deba@1750
  1137
    checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750
  1138
    typedef typename UndirGraph::NodeIt NodeIt;
deba@1750
  1139
    typedef typename UndirGraph::UndirEdge UndirEdge;
deba@1750
  1140
    checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>();
deba@1750
  1141
deba@1750
  1142
    using namespace _topology_bits;
deba@1750
  1143
deba@1750
  1144
    typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
deba@1750
  1145
    
deba@1750
  1146
    int cutNum = 0;
deba@1750
  1147
    Visitor visitor(graph, cutMap, cutNum);
deba@1750
  1148
deba@1750
  1149
    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
deba@1750
  1150
    dfs.init();
deba@1750
  1151
    
deba@1750
  1152
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
  1153
      if (!dfs.reached(it)) {
deba@1750
  1154
	dfs.addSource(it);
deba@1750
  1155
	dfs.start();
deba@1750
  1156
      }
deba@1750
  1157
    }
deba@1750
  1158
    return cutNum;
deba@1750
  1159
  }
deba@1750
  1160
deba@1750
  1161
deba@1750
  1162
  namespace _topology_bits {
deba@1750
  1163
    
deba@1750
  1164
    template <typename Graph, typename IntNodeMap>
deba@1750
  1165
    class TopologicalSortVisitor : public DfsVisitor<Graph> {
deba@1750
  1166
    public:
deba@1750
  1167
      typedef typename Graph::Node Node;
deba@1750
  1168
      typedef typename Graph::Edge edge;
deba@1750
  1169
deba@1750
  1170
      TopologicalSortVisitor(IntNodeMap& order, int num) 
deba@1750
  1171
	: _order(order), _num(num) {}
deba@1750
  1172
      
deba@1750
  1173
      void leave(const Node& node) {
deba@1750
  1174
	_order.set(node, --_num);
deba@1698
  1175
      }
deba@1698
  1176
deba@1698
  1177
    private:
deba@1750
  1178
      IntNodeMap& _order;
deba@1750
  1179
      int _num;
deba@1698
  1180
    };
deba@1750
  1181
    
deba@1698
  1182
  }
deba@1698
  1183
deba@1750
  1184
  /// \ingroup topology
deba@1750
  1185
  ///
deba@1750
  1186
  /// \brief Sort the nodes of a DAG into topolgical order.
deba@1750
  1187
  ///
deba@1750
  1188
  /// Sort the nodes of a DAG into topolgical order.
deba@1750
  1189
  ///
deba@1750
  1190
  /// \param g The graph. In must be directed and acyclic.
deba@1750
  1191
  /// \retval comp A writable node map. The values will be set from 0 to
deba@1750
  1192
  /// the number of the nodes in the graph minus one. Each values of the map
deba@1750
  1193
  /// will be set exactly once, the values  will be set descending order.
deba@1750
  1194
  ///
deba@1750
  1195
  /// \see checkedTopologicalSort
deba@1750
  1196
  /// \see dag
deba@1698
  1197
  template <typename Graph, typename NodeMap>
deba@1750
  1198
  void topologicalSort(const Graph& graph, NodeMap& order) {
deba@1750
  1199
    using namespace _topology_bits;
deba@1750
  1200
deba@1750
  1201
    checkConcept<concept::StaticGraph, Graph>();
deba@1750
  1202
    checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>();
deba@1750
  1203
deba@1750
  1204
    typedef typename Graph::Node Node;
deba@1750
  1205
    typedef typename Graph::NodeIt NodeIt;
deba@1750
  1206
    typedef typename Graph::Edge Edge;
deba@1750
  1207
deba@1750
  1208
    TopologicalSortVisitor<Graph, NodeMap> 
deba@1750
  1209
      visitor(order, countNodes(graph)); 
deba@1750
  1210
deba@1750
  1211
    DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
deba@1750
  1212
      dfs(graph, visitor);
deba@1750
  1213
deba@1750
  1214
    dfs.init();
deba@1750
  1215
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750
  1216
      if (!dfs.reached(it)) {
deba@1750
  1217
	dfs.addSource(it);
deba@1750
  1218
	dfs.start();
deba@1750
  1219
      }
deba@1750
  1220
    }    
deba@1750
  1221
  }
deba@1750
  1222
deba@1750
  1223
  /// \ingroup topology
deba@1750
  1224
  ///
deba@1750
  1225
  /// \brief Sort the nodes of a DAG into topolgical order.
deba@1750
  1226
  ///
deba@1750
  1227
  /// Sort the nodes of a DAG into topolgical order. It also checks
deba@1750
  1228
  /// that the given graph is DAG.
deba@1750
  1229
  ///
deba@1750
  1230
  /// \param g The graph. In must be directed and acyclic.
deba@1750
  1231
  /// \retval order A readable - writable node map. The values will be set 
deba@1750
  1232
  /// from 0 to the number of the nodes in the graph minus one. Each values 
deba@1750
  1233
  /// of the map will be set exactly once, the values will be set descending 
deba@1750
  1234
  /// order.
deba@1750
  1235
  /// \return %False when the graph is not DAG.
deba@1750
  1236
  ///
deba@1750
  1237
  /// \see topologicalSort
deba@1750
  1238
  /// \see dag
deba@1750
  1239
  template <typename Graph, typename NodeMap>
deba@1750
  1240
  bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {
deba@1698
  1241
    using namespace _topology_bits;
deba@1698
  1242
deba@1698
  1243
    checkConcept<concept::StaticGraph, Graph>();
deba@1698
  1244
    checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
deba@1698
  1245
deba@1698
  1246
    typedef typename Graph::Node Node;
deba@1698
  1247
    typedef typename Graph::NodeIt NodeIt;
deba@1698
  1248
    typedef typename Graph::Edge Edge;
deba@1698
  1249
deba@1750
  1250
    order = constMap<Node, int, -1>();
deba@1698
  1251
deba@1750
  1252
    TopologicalSortVisitor<Graph, NodeMap> 
deba@1750
  1253
      visitor(order, countNodes(graph)); 
deba@1698
  1254
deba@1750
  1255
    DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
deba@1750
  1256
      dfs(graph, visitor);
deba@1698
  1257
deba@1698
  1258
    dfs.init();
deba@1698
  1259
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698
  1260
      if (!dfs.reached(it)) {
deba@1698
  1261
	dfs.addSource(it);
deba@1698
  1262
	while (!dfs.emptyQueue()) {
deba@1750
  1263
 	  Edge edge = dfs.nextEdge();
deba@1750
  1264
 	  Node target = graph.target(edge);
deba@1750
  1265
 	  if (dfs.reached(target) && order[target] == -1) {
deba@1750
  1266
 	    return false;
deba@1750
  1267
 	  }
deba@1750
  1268
 	  dfs.processNextEdge();
deba@1750
  1269
 	}
deba@1698
  1270
      }
deba@1750
  1271
    }
deba@1698
  1272
    return true;
deba@1698
  1273
  }
deba@1698
  1274
deba@1750
  1275
  /// \ingroup topology
deba@1698
  1276
  ///
deba@1750
  1277
  /// \brief Check that the given directed graph is a DAG.
deba@1750
  1278
  ///
deba@1750
  1279
  /// Check that the given directed graph is a DAG. The DAG is
deba@1698
  1280
  /// an Directed Acyclic Graph.
deba@1750
  1281
  /// \return %False when the graph is not DAG.
deba@1750
  1282
  /// \see acyclic
deba@1698
  1283
  template <typename Graph>
deba@1698
  1284
  bool dag(const Graph& graph) {
deba@1698
  1285
deba@1698
  1286
    checkConcept<concept::StaticGraph, Graph>();
deba@1698
  1287
deba@1698
  1288
    typedef typename Graph::Node Node;
deba@1698
  1289
    typedef typename Graph::NodeIt NodeIt;
deba@1698
  1290
    typedef typename Graph::Edge Edge;
deba@1698
  1291
deba@1698
  1292
    typedef typename Graph::template NodeMap<bool> ProcessedMap;
deba@1698
  1293
deba@1698
  1294
    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
deba@1709
  1295
      Create dfs(graph);
deba@1698
  1296
deba@1698
  1297
    ProcessedMap processed(graph);
deba@1698
  1298
    dfs.processedMap(processed);
deba@1698
  1299
deba@1698
  1300
    dfs.init();
deba@1698
  1301
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698
  1302
      if (!dfs.reached(it)) {
deba@1698
  1303
	dfs.addSource(it);
deba@1698
  1304
	while (!dfs.emptyQueue()) {
deba@1698
  1305
	  Edge edge = dfs.nextEdge();
deba@1698
  1306
	  Node target = graph.target(edge);
deba@1698
  1307
	  if (dfs.reached(target) && !processed[target]) {
deba@1698
  1308
	    return false;
deba@1698
  1309
	  }
deba@1698
  1310
	  dfs.processNextEdge();
deba@1698
  1311
	}
deba@1698
  1312
      }
deba@1698
  1313
    }    
deba@1698
  1314
    return true;
deba@1698
  1315
  }
deba@1698
  1316
deba@1750
  1317
  /// \ingroup topology
deba@1698
  1318
  ///
deba@1698
  1319
  /// \brief Check that the given undirected graph is acyclic.
deba@1698
  1320
  ///
deba@1698
  1321
  /// Check that the given undirected graph acyclic.
deba@1750
  1322
  /// \param graph The undirected graph.
deba@1750
  1323
  /// \return %True when there is no circle in the graph.
deba@1750
  1324
  /// \see dag
deba@1698
  1325
  template <typename UndirGraph>
deba@1698
  1326
  bool acyclic(const UndirGraph& graph) {
deba@1698
  1327
    checkConcept<concept::UndirGraph, UndirGraph>();
deba@1698
  1328
    typedef typename UndirGraph::Node Node;
deba@1698
  1329
    typedef typename UndirGraph::NodeIt NodeIt;
deba@1698
  1330
    typedef typename UndirGraph::Edge Edge;
deba@1698
  1331
    Dfs<UndirGraph> dfs(graph);
deba@1698
  1332
    dfs.init();
deba@1698
  1333
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698
  1334
      if (!dfs.reached(it)) {
deba@1698
  1335
	dfs.addSource(it);
deba@1698
  1336
	while (!dfs.emptyQueue()) {
deba@1698
  1337
	  Edge edge = dfs.nextEdge();
deba@1698
  1338
	  Node source = graph.source(edge);
deba@1698
  1339
	  Node target = graph.target(edge);
deba@1698
  1340
	  if (dfs.reached(target) && 
deba@1763
  1341
	      dfs.predEdge(source) != graph.oppositeEdge(edge)) {
deba@1698
  1342
	    return false;
deba@1698
  1343
	  }
deba@1698
  1344
	  dfs.processNextEdge();
deba@1698
  1345
	}
deba@1698
  1346
      }
deba@1698
  1347
    }
deba@1698
  1348
    return true;
deba@1698
  1349
  }
deba@1698
  1350
deba@1750
  1351
  /// \ingroup topology
deba@1750
  1352
  ///
deba@1698
  1353
  /// \brief Check that the given undirected graph is tree.
deba@1698
  1354
  ///
deba@1698
  1355
  /// Check that the given undirected graph is tree.
deba@1750
  1356
  /// \param graph The undirected graph.
deba@1750
  1357
  /// \return %True when the graph is acyclic and connected.
deba@1698
  1358
  template <typename UndirGraph>
deba@1698
  1359
  bool tree(const UndirGraph& graph) {
deba@1698
  1360
    checkConcept<concept::UndirGraph, UndirGraph>();
deba@1698
  1361
    typedef typename UndirGraph::Node Node;
deba@1698
  1362
    typedef typename UndirGraph::NodeIt NodeIt;
deba@1698
  1363
    typedef typename UndirGraph::Edge Edge;
deba@1698
  1364
    Dfs<UndirGraph> dfs(graph);
deba@1698
  1365
    dfs.init();
deba@1698
  1366
    dfs.addSource(NodeIt(graph));
deba@1698
  1367
    while (!dfs.emptyQueue()) {
deba@1698
  1368
      Edge edge = dfs.nextEdge();
deba@1698
  1369
      Node source = graph.source(edge);
deba@1698
  1370
      Node target = graph.target(edge);
deba@1698
  1371
      if (dfs.reached(target) && 
deba@1763
  1372
	  dfs.predEdge(source) != graph.oppositeEdge(edge)) {
deba@1698
  1373
	return false;
deba@1698
  1374
      }
deba@1698
  1375
      dfs.processNextEdge();
deba@1698
  1376
    }
deba@1698
  1377
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698
  1378
      if (!dfs.reached(it)) {
deba@1698
  1379
	return false;
deba@1698
  1380
      }
deba@1698
  1381
    }    
deba@1698
  1382
    return true;
deba@1698
  1383
  }
alpar@1739
  1384
deba@1750
  1385
  /// \ingroup topology
alpar@1739
  1386
  ///
deba@1750
  1387
  /// \brief Check that the given undirected graph is bipartite.
deba@1750
  1388
  ///
deba@1750
  1389
  /// Check that the given undirected graph is bipartite.
deba@1750
  1390
  /// \param graph The undirected graph.
deba@1750
  1391
  /// \return %True when the nodes can be separated into two sets that
deba@1750
  1392
  /// there are not connected nodes in neither sets.
deba@1750
  1393
  template <typename UndirGraph>
deba@1750
  1394
  bool bipartite(const UndirGraph& graph) {
deba@1740
  1395
    checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750
  1396
    typedef typename UndirGraph::Node Node;
deba@1750
  1397
    typedef typename UndirGraph::NodeIt NodeIt;
deba@1750
  1398
    typedef typename UndirGraph::Edge Edge;
deba@1750
  1399
    if (NodeIt(graph) == INVALID) return false;
deba@1750
  1400
    Dfs<UndirGraph> dfs(graph);
deba@1740
  1401
    dfs.init();
deba@1750
  1402
    typename UndirGraph::template NodeMap<bool> red(graph);
deba@1740
  1403
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@1740
  1404
      if (!dfs.reached(it)) {
deba@1740
  1405
	dfs.addSource(it);
deba@1750
  1406
	red[it] = true;
deba@1750
  1407
	while (!dfs.emptyQueue()) {
deba@1750
  1408
	  Edge edge = dfs.nextEdge();
deba@1750
  1409
	  Node source = graph.source(edge);
deba@1750
  1410
	  Node target = graph.target(edge);
deba@1750
  1411
	  if (dfs.reached(target) && red[source] == red[target]) {
deba@1750
  1412
	    return false;
deba@1750
  1413
	  } else {
deba@1750
  1414
	    red[target] = !red[source];
deba@1750
  1415
	  }
deba@1750
  1416
	  dfs.processNextEdge();
deba@1750
  1417
	}
deba@1740
  1418
      }
deba@1740
  1419
    }
deba@1750
  1420
    return true;
deba@1740
  1421
  }
deba@1750
  1422
   
deba@1698
  1423
} //namespace lemon
deba@1698
  1424
deba@1698
  1425
#endif //LEMON_TOPOLOGY_H