lemon/connectivity.h
author Balazs Dezso <deba@inf.elte.hu>
Sun, 14 Feb 2010 23:14:09 +0100
changeset 833 d2bc45e8f6f2
parent 647 dcba640438c7
child 877 141f9c0db4a3
child 1089 552e3d1242c6
permissions -rw-r--r--
Merge bugfix #337
deba@417
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@417
     2
 *
deba@417
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@417
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
deba@417
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@417
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@417
     8
 *
deba@417
     9
 * Permission to use, modify and distribute this software is granted
deba@417
    10
 * provided that this copyright notice appears in all copies. For
deba@417
    11
 * precise terms see the accompanying LICENSE file.
deba@417
    12
 *
deba@417
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@417
    14
 * express or implied, and with no claim as to its suitability for any
deba@417
    15
 * purpose.
deba@417
    16
 *
deba@417
    17
 */
deba@417
    18
deba@419
    19
#ifndef LEMON_CONNECTIVITY_H
deba@419
    20
#define LEMON_CONNECTIVITY_H
deba@417
    21
deba@417
    22
#include <lemon/dfs.h>
deba@417
    23
#include <lemon/bfs.h>
deba@417
    24
#include <lemon/core.h>
deba@417
    25
#include <lemon/maps.h>
deba@417
    26
#include <lemon/adaptors.h>
deba@417
    27
deba@417
    28
#include <lemon/concepts/digraph.h>
deba@417
    29
#include <lemon/concepts/graph.h>
deba@417
    30
#include <lemon/concept_check.h>
deba@417
    31
deba@417
    32
#include <stack>
deba@417
    33
#include <functional>
deba@417
    34
kpeter@586
    35
/// \ingroup graph_properties
deba@417
    36
/// \file
deba@417
    37
/// \brief Connectivity algorithms
deba@417
    38
///
deba@417
    39
/// Connectivity algorithms
deba@417
    40
deba@417
    41
namespace lemon {
deba@417
    42
kpeter@586
    43
  /// \ingroup graph_properties
deba@417
    44
  ///
kpeter@648
    45
  /// \brief Check whether an undirected graph is connected.
deba@417
    46
  ///
kpeter@648
    47
  /// This function checks whether the given undirected graph is connected,
kpeter@648
    48
  /// i.e. there is a path between any two nodes in the graph.
kpeter@648
    49
  ///
kpeter@648
    50
  /// \return \c true if the graph is connected.
deba@417
    51
  /// \note By definition, the empty graph is connected.
kpeter@648
    52
  ///
kpeter@648
    53
  /// \see countConnectedComponents(), connectedComponents()
kpeter@648
    54
  /// \see stronglyConnected()
deba@417
    55
  template <typename Graph>
deba@417
    56
  bool connected(const Graph& graph) {
deba@417
    57
    checkConcept<concepts::Graph, Graph>();
deba@417
    58
    typedef typename Graph::NodeIt NodeIt;
deba@417
    59
    if (NodeIt(graph) == INVALID) return true;
deba@417
    60
    Dfs<Graph> dfs(graph);
deba@417
    61
    dfs.run(NodeIt(graph));
deba@417
    62
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@417
    63
      if (!dfs.reached(it)) {
deba@417
    64
        return false;
deba@417
    65
      }
deba@417
    66
    }
deba@417
    67
    return true;
deba@417
    68
  }
deba@417
    69
kpeter@586
    70
  /// \ingroup graph_properties
deba@417
    71
  ///
deba@417
    72
  /// \brief Count the number of connected components of an undirected graph
deba@417
    73
  ///
kpeter@648
    74
  /// This function counts the number of connected components of the given
kpeter@648
    75
  /// undirected graph.
deba@417
    76
  ///
kpeter@648
    77
  /// The connected components are the classes of an equivalence relation
kpeter@648
    78
  /// on the nodes of an undirected graph. Two nodes are in the same class
kpeter@648
    79
  /// if they are connected with a path.
kpeter@648
    80
  ///
kpeter@648
    81
  /// \return The number of connected components.
deba@417
    82
  /// \note By definition, the empty graph consists
deba@417
    83
  /// of zero connected components.
kpeter@648
    84
  ///
kpeter@648
    85
  /// \see connected(), connectedComponents()
deba@417
    86
  template <typename Graph>
deba@417
    87
  int countConnectedComponents(const Graph &graph) {
deba@417
    88
    checkConcept<concepts::Graph, Graph>();
deba@417
    89
    typedef typename Graph::Node Node;
deba@417
    90
    typedef typename Graph::Arc Arc;
deba@417
    91
deba@417
    92
    typedef NullMap<Node, Arc> PredMap;
deba@417
    93
    typedef NullMap<Node, int> DistMap;
deba@417
    94
deba@417
    95
    int compNum = 0;
deba@417
    96
    typename Bfs<Graph>::
deba@417
    97
      template SetPredMap<PredMap>::
deba@417
    98
      template SetDistMap<DistMap>::
deba@417
    99
      Create bfs(graph);
deba@417
   100
deba@417
   101
    PredMap predMap;
deba@417
   102
    bfs.predMap(predMap);
deba@417
   103
deba@417
   104
    DistMap distMap;
deba@417
   105
    bfs.distMap(distMap);
deba@417
   106
deba@417
   107
    bfs.init();
deba@417
   108
    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
deba@417
   109
      if (!bfs.reached(n)) {
deba@417
   110
        bfs.addSource(n);
deba@417
   111
        bfs.start();
deba@417
   112
        ++compNum;
deba@417
   113
      }
deba@417
   114
    }
deba@417
   115
    return compNum;
deba@417
   116
  }
deba@417
   117
kpeter@586
   118
  /// \ingroup graph_properties
deba@417
   119
  ///
deba@417
   120
  /// \brief Find the connected components of an undirected graph
deba@417
   121
  ///
kpeter@648
   122
  /// This function finds the connected components of the given undirected
kpeter@648
   123
  /// graph.
kpeter@648
   124
  ///
kpeter@648
   125
  /// The connected components are the classes of an equivalence relation
kpeter@648
   126
  /// on the nodes of an undirected graph. Two nodes are in the same class
kpeter@648
   127
  /// if they are connected with a path.
deba@417
   128
  ///
kpeter@586
   129
  /// \image html connected_components.png
kpeter@586
   130
  /// \image latex connected_components.eps "Connected components" width=\textwidth
kpeter@586
   131
  ///
kpeter@648
   132
  /// \param graph The undirected graph.
deba@417
   133
  /// \retval compMap A writable node map. The values will be set from 0 to
kpeter@648
   134
  /// the number of the connected components minus one. Each value of the map
kpeter@648
   135
  /// will be set exactly once, and the values of a certain component will be
deba@417
   136
  /// set continuously.
kpeter@648
   137
  /// \return The number of connected components.
kpeter@648
   138
  /// \note By definition, the empty graph consists
kpeter@648
   139
  /// of zero connected components.
kpeter@648
   140
  ///
kpeter@648
   141
  /// \see connected(), countConnectedComponents()
deba@417
   142
  template <class Graph, class NodeMap>
deba@417
   143
  int connectedComponents(const Graph &graph, NodeMap &compMap) {
deba@417
   144
    checkConcept<concepts::Graph, Graph>();
deba@417
   145
    typedef typename Graph::Node Node;
deba@417
   146
    typedef typename Graph::Arc Arc;
deba@417
   147
    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
deba@417
   148
deba@417
   149
    typedef NullMap<Node, Arc> PredMap;
deba@417
   150
    typedef NullMap<Node, int> DistMap;
deba@417
   151
deba@417
   152
    int compNum = 0;
deba@417
   153
    typename Bfs<Graph>::
deba@417
   154
      template SetPredMap<PredMap>::
deba@417
   155
      template SetDistMap<DistMap>::
deba@417
   156
      Create bfs(graph);
deba@417
   157
deba@417
   158
    PredMap predMap;
deba@417
   159
    bfs.predMap(predMap);
deba@417
   160
deba@417
   161
    DistMap distMap;
deba@417
   162
    bfs.distMap(distMap);
deba@417
   163
deba@417
   164
    bfs.init();
deba@417
   165
    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
deba@417
   166
      if(!bfs.reached(n)) {
deba@417
   167
        bfs.addSource(n);
deba@417
   168
        while (!bfs.emptyQueue()) {
deba@417
   169
          compMap.set(bfs.nextNode(), compNum);
deba@417
   170
          bfs.processNextNode();
deba@417
   171
        }
deba@417
   172
        ++compNum;
deba@417
   173
      }
deba@417
   174
    }
deba@417
   175
    return compNum;
deba@417
   176
  }
deba@417
   177
deba@419
   178
  namespace _connectivity_bits {
deba@417
   179
deba@417
   180
    template <typename Digraph, typename Iterator >
deba@417
   181
    struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
deba@417
   182
    public:
deba@417
   183
      typedef typename Digraph::Node Node;
deba@417
   184
      LeaveOrderVisitor(Iterator it) : _it(it) {}
deba@417
   185
deba@417
   186
      void leave(const Node& node) {
deba@417
   187
        *(_it++) = node;
deba@417
   188
      }
deba@417
   189
deba@417
   190
    private:
deba@417
   191
      Iterator _it;
deba@417
   192
    };
deba@417
   193
deba@417
   194
    template <typename Digraph, typename Map>
deba@417
   195
    struct FillMapVisitor : public DfsVisitor<Digraph> {
deba@417
   196
    public:
deba@417
   197
      typedef typename Digraph::Node Node;
deba@417
   198
      typedef typename Map::Value Value;
deba@417
   199
deba@417
   200
      FillMapVisitor(Map& map, Value& value)
deba@417
   201
        : _map(map), _value(value) {}
deba@417
   202
deba@417
   203
      void reach(const Node& node) {
deba@417
   204
        _map.set(node, _value);
deba@417
   205
      }
deba@417
   206
    private:
deba@417
   207
      Map& _map;
deba@417
   208
      Value& _value;
deba@417
   209
    };
deba@417
   210
deba@417
   211
    template <typename Digraph, typename ArcMap>
deba@419
   212
    struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
deba@417
   213
    public:
deba@417
   214
      typedef typename Digraph::Node Node;
deba@417
   215
      typedef typename Digraph::Arc Arc;
deba@417
   216
deba@419
   217
      StronglyConnectedCutArcsVisitor(const Digraph& digraph,
deba@419
   218
                                      ArcMap& cutMap,
deba@419
   219
                                      int& cutNum)
deba@417
   220
        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
deba@419
   221
          _compMap(digraph, -1), _num(-1) {
deba@417
   222
      }
deba@417
   223
deba@419
   224
      void start(const Node&) {
deba@417
   225
        ++_num;
deba@417
   226
      }
deba@417
   227
deba@417
   228
      void reach(const Node& node) {
deba@417
   229
        _compMap.set(node, _num);
deba@417
   230
      }
deba@417
   231
deba@417
   232
      void examine(const Arc& arc) {
deba@417
   233
         if (_compMap[_digraph.source(arc)] !=
deba@417
   234
             _compMap[_digraph.target(arc)]) {
deba@417
   235
           _cutMap.set(arc, true);
deba@417
   236
           ++_cutNum;
deba@417
   237
         }
deba@417
   238
      }
deba@417
   239
    private:
deba@417
   240
      const Digraph& _digraph;
deba@417
   241
      ArcMap& _cutMap;
deba@417
   242
      int& _cutNum;
deba@417
   243
deba@417
   244
      typename Digraph::template NodeMap<int> _compMap;
deba@417
   245
      int _num;
deba@417
   246
    };
deba@417
   247
deba@417
   248
  }
deba@417
   249
deba@417
   250
kpeter@586
   251
  /// \ingroup graph_properties
deba@417
   252
  ///
kpeter@648
   253
  /// \brief Check whether a directed graph is strongly connected.
deba@417
   254
  ///
kpeter@648
   255
  /// This function checks whether the given directed graph is strongly
kpeter@648
   256
  /// connected, i.e. any two nodes of the digraph are
deba@417
   257
  /// connected with directed paths in both direction.
deba@417
   258
  ///
kpeter@648
   259
  /// \return \c true if the digraph is strongly connected.
kpeter@648
   260
  /// \note By definition, the empty digraph is strongly connected.
kpeter@648
   261
  /// 
kpeter@648
   262
  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
kpeter@648
   263
  /// \see connected()
deba@417
   264
  template <typename Digraph>
deba@417
   265
  bool stronglyConnected(const Digraph& digraph) {
deba@417
   266
    checkConcept<concepts::Digraph, Digraph>();
deba@417
   267
deba@417
   268
    typedef typename Digraph::Node Node;
deba@417
   269
    typedef typename Digraph::NodeIt NodeIt;
deba@417
   270
deba@417
   271
    typename Digraph::Node source = NodeIt(digraph);
deba@417
   272
    if (source == INVALID) return true;
deba@417
   273
deba@419
   274
    using namespace _connectivity_bits;
deba@417
   275
deba@417
   276
    typedef DfsVisitor<Digraph> Visitor;
deba@417
   277
    Visitor visitor;
deba@417
   278
deba@417
   279
    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
deba@417
   280
    dfs.init();
deba@417
   281
    dfs.addSource(source);
deba@417
   282
    dfs.start();
deba@417
   283
deba@417
   284
    for (NodeIt it(digraph); it != INVALID; ++it) {
deba@417
   285
      if (!dfs.reached(it)) {
deba@417
   286
        return false;
deba@417
   287
      }
deba@417
   288
    }
deba@417
   289
deba@417
   290
    typedef ReverseDigraph<const Digraph> RDigraph;
deba@419
   291
    typedef typename RDigraph::NodeIt RNodeIt;
deba@417
   292
    RDigraph rdigraph(digraph);
deba@417
   293
kpeter@648
   294
    typedef DfsVisitor<RDigraph> RVisitor;
deba@417
   295
    RVisitor rvisitor;
deba@417
   296
deba@417
   297
    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
deba@417
   298
    rdfs.init();
deba@417
   299
    rdfs.addSource(source);
deba@417
   300
    rdfs.start();
deba@417
   301
deba@419
   302
    for (RNodeIt it(rdigraph); it != INVALID; ++it) {
deba@417
   303
      if (!rdfs.reached(it)) {
deba@417
   304
        return false;
deba@417
   305
      }
deba@417
   306
    }
deba@417
   307
deba@417
   308
    return true;
deba@417
   309
  }
deba@417
   310
kpeter@586
   311
  /// \ingroup graph_properties
deba@417
   312
  ///
kpeter@648
   313
  /// \brief Count the number of strongly connected components of a 
kpeter@648
   314
  /// directed graph
deba@417
   315
  ///
kpeter@648
   316
  /// This function counts the number of strongly connected components of
kpeter@648
   317
  /// the given directed graph.
kpeter@648
   318
  ///
deba@417
   319
  /// The strongly connected components are the classes of an
kpeter@648
   320
  /// equivalence relation on the nodes of a digraph. Two nodes are in
deba@417
   321
  /// the same class if they are connected with directed paths in both
deba@417
   322
  /// direction.
deba@417
   323
  ///
kpeter@648
   324
  /// \return The number of strongly connected components.
kpeter@648
   325
  /// \note By definition, the empty digraph has zero
deba@417
   326
  /// strongly connected components.
kpeter@648
   327
  ///
kpeter@648
   328
  /// \see stronglyConnected(), stronglyConnectedComponents()
deba@417
   329
  template <typename Digraph>
deba@417
   330
  int countStronglyConnectedComponents(const Digraph& digraph) {
deba@417
   331
    checkConcept<concepts::Digraph, Digraph>();
deba@417
   332
deba@419
   333
    using namespace _connectivity_bits;
deba@417
   334
deba@417
   335
    typedef typename Digraph::Node Node;
deba@417
   336
    typedef typename Digraph::Arc Arc;
deba@417
   337
    typedef typename Digraph::NodeIt NodeIt;
deba@417
   338
    typedef typename Digraph::ArcIt ArcIt;
deba@417
   339
deba@417
   340
    typedef std::vector<Node> Container;
deba@417
   341
    typedef typename Container::iterator Iterator;
deba@417
   342
deba@417
   343
    Container nodes(countNodes(digraph));
deba@417
   344
    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
deba@417
   345
    Visitor visitor(nodes.begin());
deba@417
   346
deba@417
   347
    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
deba@417
   348
    dfs.init();
deba@417
   349
    for (NodeIt it(digraph); it != INVALID; ++it) {
deba@417
   350
      if (!dfs.reached(it)) {
deba@417
   351
        dfs.addSource(it);
deba@417
   352
        dfs.start();
deba@417
   353
      }
deba@417
   354
    }
deba@417
   355
deba@417
   356
    typedef typename Container::reverse_iterator RIterator;
deba@417
   357
    typedef ReverseDigraph<const Digraph> RDigraph;
deba@417
   358
deba@417
   359
    RDigraph rdigraph(digraph);
deba@417
   360
deba@417
   361
    typedef DfsVisitor<Digraph> RVisitor;
deba@417
   362
    RVisitor rvisitor;
deba@417
   363
deba@417
   364
    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
deba@417
   365
deba@417
   366
    int compNum = 0;
deba@417
   367
deba@417
   368
    rdfs.init();
deba@417
   369
    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@417
   370
      if (!rdfs.reached(*it)) {
deba@417
   371
        rdfs.addSource(*it);
deba@417
   372
        rdfs.start();
deba@417
   373
        ++compNum;
deba@417
   374
      }
deba@417
   375
    }
deba@417
   376
    return compNum;
deba@417
   377
  }
deba@417
   378
kpeter@586
   379
  /// \ingroup graph_properties
deba@417
   380
  ///
deba@417
   381
  /// \brief Find the strongly connected components of a directed graph
deba@417
   382
  ///
kpeter@648
   383
  /// This function finds the strongly connected components of the given
kpeter@648
   384
  /// directed graph. In addition, the numbering of the components will
kpeter@648
   385
  /// satisfy that there is no arc going from a higher numbered component
kpeter@648
   386
  /// to a lower one (i.e. it provides a topological order of the components).
kpeter@648
   387
  ///
kpeter@648
   388
  /// The strongly connected components are the classes of an
kpeter@648
   389
  /// equivalence relation on the nodes of a digraph. Two nodes are in
kpeter@648
   390
  /// the same class if they are connected with directed paths in both
kpeter@648
   391
  /// direction.
deba@417
   392
  ///
kpeter@586
   393
  /// \image html strongly_connected_components.png
kpeter@586
   394
  /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
kpeter@586
   395
  ///
deba@417
   396
  /// \param digraph The digraph.
deba@417
   397
  /// \retval compMap A writable node map. The values will be set from 0 to
deba@417
   398
  /// the number of the strongly connected components minus one. Each value
kpeter@648
   399
  /// of the map will be set exactly once, and the values of a certain
kpeter@648
   400
  /// component will be set continuously.
kpeter@648
   401
  /// \return The number of strongly connected components.
kpeter@648
   402
  /// \note By definition, the empty digraph has zero
kpeter@648
   403
  /// strongly connected components.
kpeter@648
   404
  ///
kpeter@648
   405
  /// \see stronglyConnected(), countStronglyConnectedComponents()
deba@417
   406
  template <typename Digraph, typename NodeMap>
deba@417
   407
  int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
deba@417
   408
    checkConcept<concepts::Digraph, Digraph>();
deba@417
   409
    typedef typename Digraph::Node Node;
deba@417
   410
    typedef typename Digraph::NodeIt NodeIt;
deba@417
   411
    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
deba@417
   412
deba@419
   413
    using namespace _connectivity_bits;
deba@417
   414
deba@417
   415
    typedef std::vector<Node> Container;
deba@417
   416
    typedef typename Container::iterator Iterator;
deba@417
   417
deba@417
   418
    Container nodes(countNodes(digraph));
deba@417
   419
    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
deba@417
   420
    Visitor visitor(nodes.begin());
deba@417
   421
deba@417
   422
    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
deba@417
   423
    dfs.init();
deba@417
   424
    for (NodeIt it(digraph); it != INVALID; ++it) {
deba@417
   425
      if (!dfs.reached(it)) {
deba@417
   426
        dfs.addSource(it);
deba@417
   427
        dfs.start();
deba@417
   428
      }
deba@417
   429
    }
deba@417
   430
deba@417
   431
    typedef typename Container::reverse_iterator RIterator;
deba@417
   432
    typedef ReverseDigraph<const Digraph> RDigraph;
deba@417
   433
deba@417
   434
    RDigraph rdigraph(digraph);
deba@417
   435
deba@417
   436
    int compNum = 0;
deba@417
   437
deba@417
   438
    typedef FillMapVisitor<RDigraph, NodeMap> RVisitor;
deba@417
   439
    RVisitor rvisitor(compMap, compNum);
deba@417
   440
deba@417
   441
    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
deba@417
   442
deba@417
   443
    rdfs.init();
deba@417
   444
    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@417
   445
      if (!rdfs.reached(*it)) {
deba@417
   446
        rdfs.addSource(*it);
deba@417
   447
        rdfs.start();
deba@417
   448
        ++compNum;
deba@417
   449
      }
deba@417
   450
    }
deba@417
   451
    return compNum;
deba@417
   452
  }
deba@417
   453
kpeter@586
   454
  /// \ingroup graph_properties
deba@417
   455
  ///
deba@417
   456
  /// \brief Find the cut arcs of the strongly connected components.
deba@417
   457
  ///
kpeter@648
   458
  /// This function finds the cut arcs of the strongly connected components
kpeter@648
   459
  /// of the given digraph.
kpeter@648
   460
  ///
kpeter@648
   461
  /// The strongly connected components are the classes of an
kpeter@648
   462
  /// equivalence relation on the nodes of a digraph. Two nodes are in
kpeter@648
   463
  /// the same class if they are connected with directed paths in both
kpeter@648
   464
  /// direction.
deba@417
   465
  /// The strongly connected components are separated by the cut arcs.
deba@417
   466
  ///
kpeter@648
   467
  /// \param digraph The digraph.
kpeter@648
   468
  /// \retval cutMap A writable arc map. The values will be set to \c true
kpeter@648
   469
  /// for the cut arcs (exactly once for each cut arc), and will not be
kpeter@648
   470
  /// changed for other arcs.
kpeter@648
   471
  /// \return The number of cut arcs.
deba@417
   472
  ///
kpeter@648
   473
  /// \see stronglyConnected(), stronglyConnectedComponents()
deba@417
   474
  template <typename Digraph, typename ArcMap>
kpeter@648
   475
  int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
deba@417
   476
    checkConcept<concepts::Digraph, Digraph>();
deba@417
   477
    typedef typename Digraph::Node Node;
deba@417
   478
    typedef typename Digraph::Arc Arc;
deba@417
   479
    typedef typename Digraph::NodeIt NodeIt;
deba@417
   480
    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
deba@417
   481
deba@419
   482
    using namespace _connectivity_bits;
deba@417
   483
deba@417
   484
    typedef std::vector<Node> Container;
deba@417
   485
    typedef typename Container::iterator Iterator;
deba@417
   486
kpeter@648
   487
    Container nodes(countNodes(digraph));
deba@417
   488
    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
deba@417
   489
    Visitor visitor(nodes.begin());
deba@417
   490
kpeter@648
   491
    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
deba@417
   492
    dfs.init();
kpeter@648
   493
    for (NodeIt it(digraph); it != INVALID; ++it) {
deba@417
   494
      if (!dfs.reached(it)) {
deba@417
   495
        dfs.addSource(it);
deba@417
   496
        dfs.start();
deba@417
   497
      }
deba@417
   498
    }
deba@417
   499
deba@417
   500
    typedef typename Container::reverse_iterator RIterator;
deba@417
   501
    typedef ReverseDigraph<const Digraph> RDigraph;
deba@417
   502
kpeter@648
   503
    RDigraph rdigraph(digraph);
deba@417
   504
deba@417
   505
    int cutNum = 0;
deba@417
   506
deba@419
   507
    typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
kpeter@648
   508
    RVisitor rvisitor(rdigraph, cutMap, cutNum);
deba@417
   509
kpeter@648
   510
    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
deba@417
   511
deba@417
   512
    rdfs.init();
deba@417
   513
    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@417
   514
      if (!rdfs.reached(*it)) {
deba@417
   515
        rdfs.addSource(*it);
deba@417
   516
        rdfs.start();
deba@417
   517
      }
deba@417
   518
    }
deba@417
   519
    return cutNum;
deba@417
   520
  }
deba@417
   521
deba@419
   522
  namespace _connectivity_bits {
deba@417
   523
deba@417
   524
    template <typename Digraph>
deba@417
   525
    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
deba@417
   526
    public:
deba@417
   527
      typedef typename Digraph::Node Node;
deba@417
   528
      typedef typename Digraph::Arc Arc;
deba@417
   529
      typedef typename Digraph::Edge Edge;
deba@417
   530
deba@417
   531
      CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
deba@417
   532
        : _graph(graph), _compNum(compNum),
deba@417
   533
          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@417
   534
deba@417
   535
      void start(const Node& node) {
deba@417
   536
        _predMap.set(node, INVALID);
deba@417
   537
      }
deba@417
   538
deba@417
   539
      void reach(const Node& node) {
deba@417
   540
        _numMap.set(node, _num);
deba@417
   541
        _retMap.set(node, _num);
deba@417
   542
        ++_num;
deba@417
   543
      }
deba@417
   544
deba@417
   545
      void discover(const Arc& edge) {
deba@417
   546
        _predMap.set(_graph.target(edge), _graph.source(edge));
deba@417
   547
      }
deba@417
   548
deba@417
   549
      void examine(const Arc& edge) {
deba@417
   550
        if (_graph.source(edge) == _graph.target(edge) &&
deba@417
   551
            _graph.direction(edge)) {
deba@417
   552
          ++_compNum;
deba@417
   553
          return;
deba@417
   554
        }
deba@417
   555
        if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
deba@417
   556
          return;
deba@417
   557
        }
deba@417
   558
        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
deba@417
   559
          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
deba@417
   560
        }
deba@417
   561
      }
deba@417
   562
deba@417
   563
      void backtrack(const Arc& edge) {
deba@417
   564
        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417
   565
          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417
   566
        }
deba@417
   567
        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
deba@417
   568
          ++_compNum;
deba@417
   569
        }
deba@417
   570
      }
deba@417
   571
deba@417
   572
    private:
deba@417
   573
      const Digraph& _graph;
deba@417
   574
      int& _compNum;
deba@417
   575
deba@417
   576
      typename Digraph::template NodeMap<int> _numMap;
deba@417
   577
      typename Digraph::template NodeMap<int> _retMap;
deba@417
   578
      typename Digraph::template NodeMap<Node> _predMap;
deba@417
   579
      int _num;
deba@417
   580
    };
deba@417
   581
deba@417
   582
    template <typename Digraph, typename ArcMap>
deba@417
   583
    class BiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
deba@417
   584
    public:
deba@417
   585
      typedef typename Digraph::Node Node;
deba@417
   586
      typedef typename Digraph::Arc Arc;
deba@417
   587
      typedef typename Digraph::Edge Edge;
deba@417
   588
deba@417
   589
      BiNodeConnectedComponentsVisitor(const Digraph& graph,
deba@417
   590
                                       ArcMap& compMap, int &compNum)
deba@417
   591
        : _graph(graph), _compMap(compMap), _compNum(compNum),
deba@417
   592
          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@417
   593
deba@417
   594
      void start(const Node& node) {
deba@417
   595
        _predMap.set(node, INVALID);
deba@417
   596
      }
deba@417
   597
deba@417
   598
      void reach(const Node& node) {
deba@417
   599
        _numMap.set(node, _num);
deba@417
   600
        _retMap.set(node, _num);
deba@417
   601
        ++_num;
deba@417
   602
      }
deba@417
   603
deba@417
   604
      void discover(const Arc& edge) {
deba@417
   605
        Node target = _graph.target(edge);
deba@417
   606
        _predMap.set(target, edge);
deba@417
   607
        _edgeStack.push(edge);
deba@417
   608
      }
deba@417
   609
deba@417
   610
      void examine(const Arc& edge) {
deba@417
   611
        Node source = _graph.source(edge);
deba@417
   612
        Node target = _graph.target(edge);
deba@417
   613
        if (source == target && _graph.direction(edge)) {
deba@417
   614
          _compMap.set(edge, _compNum);
deba@417
   615
          ++_compNum;
deba@417
   616
          return;
deba@417
   617
        }
deba@417
   618
        if (_numMap[target] < _numMap[source]) {
deba@417
   619
          if (_predMap[source] != _graph.oppositeArc(edge)) {
deba@417
   620
            _edgeStack.push(edge);
deba@417
   621
          }
deba@417
   622
        }
deba@417
   623
        if (_predMap[source] != INVALID &&
deba@417
   624
            target == _graph.source(_predMap[source])) {
deba@417
   625
          return;
deba@417
   626
        }
deba@417
   627
        if (_retMap[source] > _numMap[target]) {
deba@417
   628
          _retMap.set(source, _numMap[target]);
deba@417
   629
        }
deba@417
   630
      }
deba@417
   631
deba@417
   632
      void backtrack(const Arc& edge) {
deba@417
   633
        Node source = _graph.source(edge);
deba@417
   634
        Node target = _graph.target(edge);
deba@417
   635
        if (_retMap[source] > _retMap[target]) {
deba@417
   636
          _retMap.set(source, _retMap[target]);
deba@417
   637
        }
deba@417
   638
        if (_numMap[source] <= _retMap[target]) {
deba@417
   639
          while (_edgeStack.top() != edge) {
deba@417
   640
            _compMap.set(_edgeStack.top(), _compNum);
deba@417
   641
            _edgeStack.pop();
deba@417
   642
          }
deba@417
   643
          _compMap.set(edge, _compNum);
deba@417
   644
          _edgeStack.pop();
deba@417
   645
          ++_compNum;
deba@417
   646
        }
deba@417
   647
      }
deba@417
   648
deba@417
   649
    private:
deba@417
   650
      const Digraph& _graph;
deba@417
   651
      ArcMap& _compMap;
deba@417
   652
      int& _compNum;
deba@417
   653
deba@417
   654
      typename Digraph::template NodeMap<int> _numMap;
deba@417
   655
      typename Digraph::template NodeMap<int> _retMap;
deba@417
   656
      typename Digraph::template NodeMap<Arc> _predMap;
deba@417
   657
      std::stack<Edge> _edgeStack;
deba@417
   658
      int _num;
deba@417
   659
    };
deba@417
   660
deba@417
   661
deba@417
   662
    template <typename Digraph, typename NodeMap>
deba@417
   663
    class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Digraph> {
deba@417
   664
    public:
deba@417
   665
      typedef typename Digraph::Node Node;
deba@417
   666
      typedef typename Digraph::Arc Arc;
deba@417
   667
      typedef typename Digraph::Edge Edge;
deba@417
   668
deba@417
   669
      BiNodeConnectedCutNodesVisitor(const Digraph& graph, NodeMap& cutMap,
deba@417
   670
                                     int& cutNum)
deba@417
   671
        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
deba@417
   672
          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@417
   673
deba@417
   674
      void start(const Node& node) {
deba@417
   675
        _predMap.set(node, INVALID);
deba@417
   676
        rootCut = false;
deba@417
   677
      }
deba@417
   678
deba@417
   679
      void reach(const Node& node) {
deba@417
   680
        _numMap.set(node, _num);
deba@417
   681
        _retMap.set(node, _num);
deba@417
   682
        ++_num;
deba@417
   683
      }
deba@417
   684
deba@417
   685
      void discover(const Arc& edge) {
deba@417
   686
        _predMap.set(_graph.target(edge), _graph.source(edge));
deba@417
   687
      }
deba@417
   688
deba@417
   689
      void examine(const Arc& edge) {
deba@417
   690
        if (_graph.source(edge) == _graph.target(edge) &&
deba@417
   691
            _graph.direction(edge)) {
deba@417
   692
          if (!_cutMap[_graph.source(edge)]) {
deba@417
   693
            _cutMap.set(_graph.source(edge), true);
deba@417
   694
            ++_cutNum;
deba@417
   695
          }
deba@417
   696
          return;
deba@417
   697
        }
deba@417
   698
        if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
deba@417
   699
        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
deba@417
   700
          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
deba@417
   701
        }
deba@417
   702
      }
deba@417
   703
deba@417
   704
      void backtrack(const Arc& edge) {
deba@417
   705
        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417
   706
          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417
   707
        }
deba@417
   708
        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
deba@417
   709
          if (_predMap[_graph.source(edge)] != INVALID) {
deba@417
   710
            if (!_cutMap[_graph.source(edge)]) {
deba@417
   711
              _cutMap.set(_graph.source(edge), true);
deba@417
   712
              ++_cutNum;
deba@417
   713
            }
deba@417
   714
          } else if (rootCut) {
deba@417
   715
            if (!_cutMap[_graph.source(edge)]) {
deba@417
   716
              _cutMap.set(_graph.source(edge), true);
deba@417
   717
              ++_cutNum;
deba@417
   718
            }
deba@417
   719
          } else {
deba@417
   720
            rootCut = true;
deba@417
   721
          }
deba@417
   722
        }
deba@417
   723
      }
deba@417
   724
deba@417
   725
    private:
deba@417
   726
      const Digraph& _graph;
deba@417
   727
      NodeMap& _cutMap;
deba@417
   728
      int& _cutNum;
deba@417
   729
deba@417
   730
      typename Digraph::template NodeMap<int> _numMap;
deba@417
   731
      typename Digraph::template NodeMap<int> _retMap;
deba@417
   732
      typename Digraph::template NodeMap<Node> _predMap;
deba@417
   733
      std::stack<Edge> _edgeStack;
deba@417
   734
      int _num;
deba@417
   735
      bool rootCut;
deba@417
   736
    };
deba@417
   737
deba@417
   738
  }
deba@417
   739
deba@417
   740
  template <typename Graph>
deba@417
   741
  int countBiNodeConnectedComponents(const Graph& graph);
deba@417
   742
kpeter@586
   743
  /// \ingroup graph_properties
deba@417
   744
  ///
kpeter@648
   745
  /// \brief Check whether an undirected graph is bi-node-connected.
deba@417
   746
  ///
kpeter@648
   747
  /// This function checks whether the given undirected graph is 
kpeter@648
   748
  /// bi-node-connected, i.e. any two edges are on same circle.
deba@417
   749
  ///
kpeter@648
   750
  /// \return \c true if the graph bi-node-connected.
kpeter@648
   751
  /// \note By definition, the empty graph is bi-node-connected.
kpeter@648
   752
  ///
kpeter@648
   753
  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
deba@417
   754
  template <typename Graph>
deba@417
   755
  bool biNodeConnected(const Graph& graph) {
deba@417
   756
    return countBiNodeConnectedComponents(graph) <= 1;
deba@417
   757
  }
deba@417
   758
kpeter@586
   759
  /// \ingroup graph_properties
deba@417
   760
  ///
kpeter@648
   761
  /// \brief Count the number of bi-node-connected components of an 
kpeter@648
   762
  /// undirected graph.
deba@417
   763
  ///
kpeter@648
   764
  /// This function counts the number of bi-node-connected components of
kpeter@648
   765
  /// the given undirected graph.
deba@417
   766
  ///
kpeter@648
   767
  /// The bi-node-connected components are the classes of an equivalence
kpeter@648
   768
  /// relation on the edges of a undirected graph. Two edges are in the
kpeter@648
   769
  /// same class if they are on same circle.
kpeter@648
   770
  ///
kpeter@648
   771
  /// \return The number of bi-node-connected components.
kpeter@648
   772
  ///
kpeter@648
   773
  /// \see biNodeConnected(), biNodeConnectedComponents()
deba@417
   774
  template <typename Graph>
deba@417
   775
  int countBiNodeConnectedComponents(const Graph& graph) {
deba@417
   776
    checkConcept<concepts::Graph, Graph>();
deba@417
   777
    typedef typename Graph::NodeIt NodeIt;
deba@417
   778
deba@419
   779
    using namespace _connectivity_bits;
deba@417
   780
deba@417
   781
    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
deba@417
   782
deba@417
   783
    int compNum = 0;
deba@417
   784
    Visitor visitor(graph, compNum);
deba@417
   785
deba@417
   786
    DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@417
   787
    dfs.init();
deba@417
   788
deba@417
   789
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@417
   790
      if (!dfs.reached(it)) {
deba@417
   791
        dfs.addSource(it);
deba@417
   792
        dfs.start();
deba@417
   793
      }
deba@417
   794
    }
deba@417
   795
    return compNum;
deba@417
   796
  }
deba@417
   797
kpeter@586
   798
  /// \ingroup graph_properties
deba@417
   799
  ///
kpeter@648
   800
  /// \brief Find the bi-node-connected components of an undirected graph.
deba@417
   801
  ///
kpeter@648
   802
  /// This function finds the bi-node-connected components of the given
kpeter@648
   803
  /// undirected graph.
kpeter@648
   804
  ///
kpeter@648
   805
  /// The bi-node-connected components are the classes of an equivalence
kpeter@648
   806
  /// relation on the edges of a undirected graph. Two edges are in the
kpeter@648
   807
  /// same class if they are on same circle.
deba@417
   808
  ///
kpeter@586
   809
  /// \image html node_biconnected_components.png
kpeter@586
   810
  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
kpeter@586
   811
  ///
kpeter@648
   812
  /// \param graph The undirected graph.
kpeter@648
   813
  /// \retval compMap A writable edge map. The values will be set from 0
kpeter@648
   814
  /// to the number of the bi-node-connected components minus one. Each
kpeter@648
   815
  /// value of the map will be set exactly once, and the values of a 
kpeter@648
   816
  /// certain component will be set continuously.
kpeter@648
   817
  /// \return The number of bi-node-connected components.
kpeter@648
   818
  ///
kpeter@648
   819
  /// \see biNodeConnected(), countBiNodeConnectedComponents()
deba@417
   820
  template <typename Graph, typename EdgeMap>
deba@417
   821
  int biNodeConnectedComponents(const Graph& graph,
deba@417
   822
                                EdgeMap& compMap) {
deba@417
   823
    checkConcept<concepts::Graph, Graph>();
deba@417
   824
    typedef typename Graph::NodeIt NodeIt;
deba@417
   825
    typedef typename Graph::Edge Edge;
deba@417
   826
    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
deba@417
   827
deba@419
   828
    using namespace _connectivity_bits;
deba@417
   829
deba@417
   830
    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
deba@417
   831
deba@417
   832
    int compNum = 0;
deba@417
   833
    Visitor visitor(graph, compMap, compNum);
deba@417
   834
deba@417
   835
    DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@417
   836
    dfs.init();
deba@417
   837
deba@417
   838
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@417
   839
      if (!dfs.reached(it)) {
deba@417
   840
        dfs.addSource(it);
deba@417
   841
        dfs.start();
deba@417
   842
      }
deba@417
   843
    }
deba@417
   844
    return compNum;
deba@417
   845
  }
deba@417
   846
kpeter@586
   847
  /// \ingroup graph_properties
deba@417
   848
  ///
kpeter@648
   849
  /// \brief Find the bi-node-connected cut nodes in an undirected graph.
deba@417
   850
  ///
kpeter@648
   851
  /// This function finds the bi-node-connected cut nodes in the given
kpeter@648
   852
  /// undirected graph.
deba@417
   853
  ///
kpeter@648
   854
  /// The bi-node-connected components are the classes of an equivalence
kpeter@648
   855
  /// relation on the edges of a undirected graph. Two edges are in the
kpeter@648
   856
  /// same class if they are on same circle.
kpeter@648
   857
  /// The bi-node-connected components are separted by the cut nodes of
kpeter@648
   858
  /// the components.
kpeter@648
   859
  ///
kpeter@648
   860
  /// \param graph The undirected graph.
kpeter@648
   861
  /// \retval cutMap A writable node map. The values will be set to 
kpeter@648
   862
  /// \c true for the nodes that separate two or more components
kpeter@648
   863
  /// (exactly once for each cut node), and will not be changed for
kpeter@648
   864
  /// other nodes.
deba@417
   865
  /// \return The number of the cut nodes.
kpeter@648
   866
  ///
kpeter@648
   867
  /// \see biNodeConnected(), biNodeConnectedComponents()
deba@417
   868
  template <typename Graph, typename NodeMap>
deba@417
   869
  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
deba@417
   870
    checkConcept<concepts::Graph, Graph>();
deba@417
   871
    typedef typename Graph::Node Node;
deba@417
   872
    typedef typename Graph::NodeIt NodeIt;
deba@417
   873
    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
deba@417
   874
deba@419
   875
    using namespace _connectivity_bits;
deba@417
   876
deba@417
   877
    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
deba@417
   878
deba@417
   879
    int cutNum = 0;
deba@417
   880
    Visitor visitor(graph, cutMap, cutNum);
deba@417
   881
deba@417
   882
    DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@417
   883
    dfs.init();
deba@417
   884
deba@417
   885
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@417
   886
      if (!dfs.reached(it)) {
deba@417
   887
        dfs.addSource(it);
deba@417
   888
        dfs.start();
deba@417
   889
      }
deba@417
   890
    }
deba@417
   891
    return cutNum;
deba@417
   892
  }
deba@417
   893
deba@419
   894
  namespace _connectivity_bits {
deba@417
   895
deba@417
   896
    template <typename Digraph>
deba@417
   897
    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
deba@417
   898
    public:
deba@417
   899
      typedef typename Digraph::Node Node;
deba@417
   900
      typedef typename Digraph::Arc Arc;
deba@417
   901
      typedef typename Digraph::Edge Edge;
deba@417
   902
deba@417
   903
      CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
deba@417
   904
        : _graph(graph), _compNum(compNum),
deba@417
   905
          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@417
   906
deba@417
   907
      void start(const Node& node) {
deba@417
   908
        _predMap.set(node, INVALID);
deba@417
   909
      }
deba@417
   910
deba@417
   911
      void reach(const Node& node) {
deba@417
   912
        _numMap.set(node, _num);
deba@417
   913
        _retMap.set(node, _num);
deba@417
   914
        ++_num;
deba@417
   915
      }
deba@417
   916
deba@417
   917
      void leave(const Node& node) {
deba@417
   918
        if (_numMap[node] <= _retMap[node]) {
deba@417
   919
          ++_compNum;
deba@417
   920
        }
deba@417
   921
      }
deba@417
   922
deba@417
   923
      void discover(const Arc& edge) {
deba@417
   924
        _predMap.set(_graph.target(edge), edge);
deba@417
   925
      }
deba@417
   926
deba@417
   927
      void examine(const Arc& edge) {
deba@417
   928
        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
deba@417
   929
          return;
deba@417
   930
        }
deba@417
   931
        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417
   932
          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417
   933
        }
deba@417
   934
      }
deba@417
   935
deba@417
   936
      void backtrack(const Arc& edge) {
deba@417
   937
        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417
   938
          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417
   939
        }
deba@417
   940
      }
deba@417
   941
deba@417
   942
    private:
deba@417
   943
      const Digraph& _graph;
deba@417
   944
      int& _compNum;
deba@417
   945
deba@417
   946
      typename Digraph::template NodeMap<int> _numMap;
deba@417
   947
      typename Digraph::template NodeMap<int> _retMap;
deba@417
   948
      typename Digraph::template NodeMap<Arc> _predMap;
deba@417
   949
      int _num;
deba@417
   950
    };
deba@417
   951
deba@417
   952
    template <typename Digraph, typename NodeMap>
deba@417
   953
    class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
deba@417
   954
    public:
deba@417
   955
      typedef typename Digraph::Node Node;
deba@417
   956
      typedef typename Digraph::Arc Arc;
deba@417
   957
      typedef typename Digraph::Edge Edge;
deba@417
   958
deba@417
   959
      BiEdgeConnectedComponentsVisitor(const Digraph& graph,
deba@417
   960
                                       NodeMap& compMap, int &compNum)
deba@417
   961
        : _graph(graph), _compMap(compMap), _compNum(compNum),
deba@417
   962
          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@417
   963
deba@417
   964
      void start(const Node& node) {
deba@417
   965
        _predMap.set(node, INVALID);
deba@417
   966
      }
deba@417
   967
deba@417
   968
      void reach(const Node& node) {
deba@417
   969
        _numMap.set(node, _num);
deba@417
   970
        _retMap.set(node, _num);
deba@417
   971
        _nodeStack.push(node);
deba@417
   972
        ++_num;
deba@417
   973
      }
deba@417
   974
deba@417
   975
      void leave(const Node& node) {
deba@417
   976
        if (_numMap[node] <= _retMap[node]) {
deba@417
   977
          while (_nodeStack.top() != node) {
deba@417
   978
            _compMap.set(_nodeStack.top(), _compNum);
deba@417
   979
            _nodeStack.pop();
deba@417
   980
          }
deba@417
   981
          _compMap.set(node, _compNum);
deba@417
   982
          _nodeStack.pop();
deba@417
   983
          ++_compNum;
deba@417
   984
        }
deba@417
   985
      }
deba@417
   986
deba@417
   987
      void discover(const Arc& edge) {
deba@417
   988
        _predMap.set(_graph.target(edge), edge);
deba@417
   989
      }
deba@417
   990
deba@417
   991
      void examine(const Arc& edge) {
deba@417
   992
        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
deba@417
   993
          return;
deba@417
   994
        }
deba@417
   995
        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417
   996
          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417
   997
        }
deba@417
   998
      }
deba@417
   999
deba@417
  1000
      void backtrack(const Arc& edge) {
deba@417
  1001
        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417
  1002
          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417
  1003
        }
deba@417
  1004
      }
deba@417
  1005
deba@417
  1006
    private:
deba@417
  1007
      const Digraph& _graph;
deba@417
  1008
      NodeMap& _compMap;
deba@417
  1009
      int& _compNum;
deba@417
  1010
deba@417
  1011
      typename Digraph::template NodeMap<int> _numMap;
deba@417
  1012
      typename Digraph::template NodeMap<int> _retMap;
deba@417
  1013
      typename Digraph::template NodeMap<Arc> _predMap;
deba@417
  1014
      std::stack<Node> _nodeStack;
deba@417
  1015
      int _num;
deba@417
  1016
    };
deba@417
  1017
deba@417
  1018
deba@417
  1019
    template <typename Digraph, typename ArcMap>
deba@417
  1020
    class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
deba@417
  1021
    public:
deba@417
  1022
      typedef typename Digraph::Node Node;
deba@417
  1023
      typedef typename Digraph::Arc Arc;
deba@417
  1024
      typedef typename Digraph::Edge Edge;
deba@417
  1025
deba@417
  1026
      BiEdgeConnectedCutEdgesVisitor(const Digraph& graph,
deba@417
  1027
                                     ArcMap& cutMap, int &cutNum)
deba@417
  1028
        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
deba@417
  1029
          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@417
  1030
deba@417
  1031
      void start(const Node& node) {
deba@417
  1032
        _predMap[node] = INVALID;
deba@417
  1033
      }
deba@417
  1034
deba@417
  1035
      void reach(const Node& node) {
deba@417
  1036
        _numMap.set(node, _num);
deba@417
  1037
        _retMap.set(node, _num);
deba@417
  1038
        ++_num;
deba@417
  1039
      }
deba@417
  1040
deba@417
  1041
      void leave(const Node& node) {
deba@417
  1042
        if (_numMap[node] <= _retMap[node]) {
deba@417
  1043
          if (_predMap[node] != INVALID) {
deba@417
  1044
            _cutMap.set(_predMap[node], true);
deba@417
  1045
            ++_cutNum;
deba@417
  1046
          }
deba@417
  1047
        }
deba@417
  1048
      }
deba@417
  1049
deba@417
  1050
      void discover(const Arc& edge) {
deba@417
  1051
        _predMap.set(_graph.target(edge), edge);
deba@417
  1052
      }
deba@417
  1053
deba@417
  1054
      void examine(const Arc& edge) {
deba@417
  1055
        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
deba@417
  1056
          return;
deba@417
  1057
        }
deba@417
  1058
        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417
  1059
          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417
  1060
        }
deba@417
  1061
      }
deba@417
  1062
deba@417
  1063
      void backtrack(const Arc& edge) {
deba@417
  1064
        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@417
  1065
          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@417
  1066
        }
deba@417
  1067
      }
deba@417
  1068
deba@417
  1069
    private:
deba@417
  1070
      const Digraph& _graph;
deba@417
  1071
      ArcMap& _cutMap;
deba@417
  1072
      int& _cutNum;
deba@417
  1073
deba@417
  1074
      typename Digraph::template NodeMap<int> _numMap;
deba@417
  1075
      typename Digraph::template NodeMap<int> _retMap;
deba@417
  1076
      typename Digraph::template NodeMap<Arc> _predMap;
deba@417
  1077
      int _num;
deba@417
  1078
    };
deba@417
  1079
  }
deba@417
  1080
deba@417
  1081
  template <typename Graph>
deba@417
  1082
  int countBiEdgeConnectedComponents(const Graph& graph);
deba@417
  1083
kpeter@586
  1084
  /// \ingroup graph_properties
deba@417
  1085
  ///
kpeter@648
  1086
  /// \brief Check whether an undirected graph is bi-edge-connected.
deba@417
  1087
  ///
kpeter@648
  1088
  /// This function checks whether the given undirected graph is 
kpeter@648
  1089
  /// bi-edge-connected, i.e. any two nodes are connected with at least
kpeter@648
  1090
  /// two edge-disjoint paths.
deba@417
  1091
  ///
kpeter@648
  1092
  /// \return \c true if the graph is bi-edge-connected.
kpeter@648
  1093
  /// \note By definition, the empty graph is bi-edge-connected.
kpeter@648
  1094
  ///
kpeter@648
  1095
  /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
deba@417
  1096
  template <typename Graph>
deba@417
  1097
  bool biEdgeConnected(const Graph& graph) {
deba@417
  1098
    return countBiEdgeConnectedComponents(graph) <= 1;
deba@417
  1099
  }
deba@417
  1100
kpeter@586
  1101
  /// \ingroup graph_properties
deba@417
  1102
  ///
kpeter@648
  1103
  /// \brief Count the number of bi-edge-connected components of an
kpeter@648
  1104
  /// undirected graph.
deba@417
  1105
  ///
kpeter@648
  1106
  /// This function counts the number of bi-edge-connected components of
kpeter@648
  1107
  /// the given undirected graph.
deba@417
  1108
  ///
kpeter@648
  1109
  /// The bi-edge-connected components are the classes of an equivalence
kpeter@648
  1110
  /// relation on the nodes of an undirected graph. Two nodes are in the
kpeter@648
  1111
  /// same class if they are connected with at least two edge-disjoint
kpeter@648
  1112
  /// paths.
kpeter@648
  1113
  ///
kpeter@648
  1114
  /// \return The number of bi-edge-connected components.
kpeter@648
  1115
  ///
kpeter@648
  1116
  /// \see biEdgeConnected(), biEdgeConnectedComponents()
deba@417
  1117
  template <typename Graph>
deba@417
  1118
  int countBiEdgeConnectedComponents(const Graph& graph) {
deba@417
  1119
    checkConcept<concepts::Graph, Graph>();
deba@417
  1120
    typedef typename Graph::NodeIt NodeIt;
deba@417
  1121
deba@419
  1122
    using namespace _connectivity_bits;
deba@417
  1123
deba@417
  1124
    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
deba@417
  1125
deba@417
  1126
    int compNum = 0;
deba@417
  1127
    Visitor visitor(graph, compNum);
deba@417
  1128
deba@417
  1129
    DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@417
  1130
    dfs.init();
deba@417
  1131
deba@417
  1132
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@417
  1133
      if (!dfs.reached(it)) {
deba@417
  1134
        dfs.addSource(it);
deba@417
  1135
        dfs.start();
deba@417
  1136
      }
deba@417
  1137
    }
deba@417
  1138
    return compNum;
deba@417
  1139
  }
deba@417
  1140
kpeter@586
  1141
  /// \ingroup graph_properties
deba@417
  1142
  ///
kpeter@648
  1143
  /// \brief Find the bi-edge-connected components of an undirected graph.
deba@417
  1144
  ///
kpeter@648
  1145
  /// This function finds the bi-edge-connected components of the given
kpeter@648
  1146
  /// undirected graph.
kpeter@648
  1147
  ///
kpeter@648
  1148
  /// The bi-edge-connected components are the classes of an equivalence
kpeter@648
  1149
  /// relation on the nodes of an undirected graph. Two nodes are in the
kpeter@648
  1150
  /// same class if they are connected with at least two edge-disjoint
kpeter@648
  1151
  /// paths.
deba@417
  1152
  ///
kpeter@586
  1153
  /// \image html edge_biconnected_components.png
kpeter@586
  1154
  /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
kpeter@586
  1155
  ///
kpeter@648
  1156
  /// \param graph The undirected graph.
deba@417
  1157
  /// \retval compMap A writable node map. The values will be set from 0 to
kpeter@648
  1158
  /// the number of the bi-edge-connected components minus one. Each value
kpeter@648
  1159
  /// of the map will be set exactly once, and the values of a certain
kpeter@648
  1160
  /// component will be set continuously.
kpeter@648
  1161
  /// \return The number of bi-edge-connected components.
kpeter@648
  1162
  ///
kpeter@648
  1163
  /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
deba@417
  1164
  template <typename Graph, typename NodeMap>
deba@417
  1165
  int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
deba@417
  1166
    checkConcept<concepts::Graph, Graph>();
deba@417
  1167
    typedef typename Graph::NodeIt NodeIt;
deba@417
  1168
    typedef typename Graph::Node Node;
deba@417
  1169
    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
deba@417
  1170
deba@419
  1171
    using namespace _connectivity_bits;
deba@417
  1172
deba@417
  1173
    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
deba@417
  1174
deba@417
  1175
    int compNum = 0;
deba@417
  1176
    Visitor visitor(graph, compMap, compNum);
deba@417
  1177
deba@417
  1178
    DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@417
  1179
    dfs.init();
deba@417
  1180
deba@417
  1181
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@417
  1182
      if (!dfs.reached(it)) {
deba@417
  1183
        dfs.addSource(it);
deba@417
  1184
        dfs.start();
deba@417
  1185
      }
deba@417
  1186
    }
deba@417
  1187
    return compNum;
deba@417
  1188
  }
deba@417
  1189
kpeter@586
  1190
  /// \ingroup graph_properties
deba@417
  1191
  ///
kpeter@648
  1192
  /// \brief Find the bi-edge-connected cut edges in an undirected graph.
deba@417
  1193
  ///
kpeter@648
  1194
  /// This function finds the bi-edge-connected cut edges in the given
kpeter@648
  1195
  /// undirected graph. 
deba@417
  1196
  ///
kpeter@648
  1197
  /// The bi-edge-connected components are the classes of an equivalence
kpeter@648
  1198
  /// relation on the nodes of an undirected graph. Two nodes are in the
kpeter@648
  1199
  /// same class if they are connected with at least two edge-disjoint
kpeter@648
  1200
  /// paths.
kpeter@648
  1201
  /// The bi-edge-connected components are separted by the cut edges of
kpeter@648
  1202
  /// the components.
kpeter@648
  1203
  ///
kpeter@648
  1204
  /// \param graph The undirected graph.
kpeter@648
  1205
  /// \retval cutMap A writable edge map. The values will be set to \c true
kpeter@648
  1206
  /// for the cut edges (exactly once for each cut edge), and will not be
kpeter@648
  1207
  /// changed for other edges.
deba@417
  1208
  /// \return The number of cut edges.
kpeter@648
  1209
  ///
kpeter@648
  1210
  /// \see biEdgeConnected(), biEdgeConnectedComponents()
deba@417
  1211
  template <typename Graph, typename EdgeMap>
deba@417
  1212
  int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
deba@417
  1213
    checkConcept<concepts::Graph, Graph>();
deba@417
  1214
    typedef typename Graph::NodeIt NodeIt;
deba@417
  1215
    typedef typename Graph::Edge Edge;
deba@417
  1216
    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
deba@417
  1217
deba@419
  1218
    using namespace _connectivity_bits;
deba@417
  1219
deba@417
  1220
    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
deba@417
  1221
deba@417
  1222
    int cutNum = 0;
deba@417
  1223
    Visitor visitor(graph, cutMap, cutNum);
deba@417
  1224
deba@417
  1225
    DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@417
  1226
    dfs.init();
deba@417
  1227
deba@417
  1228
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@417
  1229
      if (!dfs.reached(it)) {
deba@417
  1230
        dfs.addSource(it);
deba@417
  1231
        dfs.start();
deba@417
  1232
      }
deba@417
  1233
    }
deba@417
  1234
    return cutNum;
deba@417
  1235
  }
deba@417
  1236
deba@417
  1237
deba@419
  1238
  namespace _connectivity_bits {
deba@417
  1239
deba@417
  1240
    template <typename Digraph, typename IntNodeMap>
deba@417
  1241
    class TopologicalSortVisitor : public DfsVisitor<Digraph> {
deba@417
  1242
    public:
deba@417
  1243
      typedef typename Digraph::Node Node;
deba@417
  1244
      typedef typename Digraph::Arc edge;
deba@417
  1245
deba@417
  1246
      TopologicalSortVisitor(IntNodeMap& order, int num)
deba@417
  1247
        : _order(order), _num(num) {}
deba@417
  1248
deba@417
  1249
      void leave(const Node& node) {
deba@417
  1250
        _order.set(node, --_num);
deba@417
  1251
      }
deba@417
  1252
deba@417
  1253
    private:
deba@417
  1254
      IntNodeMap& _order;
deba@417
  1255
      int _num;
deba@417
  1256
    };
deba@417
  1257
deba@417
  1258
  }
deba@417
  1259
kpeter@586
  1260
  /// \ingroup graph_properties
deba@417
  1261
  ///
kpeter@648
  1262
  /// \brief Check whether a digraph is DAG.
kpeter@648
  1263
  ///
kpeter@648
  1264
  /// This function checks whether the given digraph is DAG, i.e.
kpeter@648
  1265
  /// \e Directed \e Acyclic \e Graph.
kpeter@648
  1266
  /// \return \c true if there is no directed cycle in the digraph.
kpeter@648
  1267
  /// \see acyclic()
kpeter@648
  1268
  template <typename Digraph>
kpeter@648
  1269
  bool dag(const Digraph& digraph) {
kpeter@648
  1270
kpeter@648
  1271
    checkConcept<concepts::Digraph, Digraph>();
kpeter@648
  1272
kpeter@648
  1273
    typedef typename Digraph::Node Node;
kpeter@648
  1274
    typedef typename Digraph::NodeIt NodeIt;
kpeter@648
  1275
    typedef typename Digraph::Arc Arc;
kpeter@648
  1276
kpeter@648
  1277
    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
kpeter@648
  1278
kpeter@648
  1279
    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
kpeter@648
  1280
      Create dfs(digraph);
kpeter@648
  1281
kpeter@648
  1282
    ProcessedMap processed(digraph);
kpeter@648
  1283
    dfs.processedMap(processed);
kpeter@648
  1284
kpeter@648
  1285
    dfs.init();
kpeter@648
  1286
    for (NodeIt it(digraph); it != INVALID; ++it) {
kpeter@648
  1287
      if (!dfs.reached(it)) {
kpeter@648
  1288
        dfs.addSource(it);
kpeter@648
  1289
        while (!dfs.emptyQueue()) {
kpeter@648
  1290
          Arc arc = dfs.nextArc();
kpeter@648
  1291
          Node target = digraph.target(arc);
kpeter@648
  1292
          if (dfs.reached(target) && !processed[target]) {
kpeter@648
  1293
            return false;
kpeter@648
  1294
          }
kpeter@648
  1295
          dfs.processNextArc();
kpeter@648
  1296
        }
kpeter@648
  1297
      }
kpeter@648
  1298
    }
kpeter@648
  1299
    return true;
kpeter@648
  1300
  }
kpeter@648
  1301
kpeter@648
  1302
  /// \ingroup graph_properties
kpeter@648
  1303
  ///
deba@417
  1304
  /// \brief Sort the nodes of a DAG into topolgical order.
deba@417
  1305
  ///
kpeter@648
  1306
  /// This function sorts the nodes of the given acyclic digraph (DAG)
kpeter@648
  1307
  /// into topolgical order.
deba@417
  1308
  ///
kpeter@648
  1309
  /// \param digraph The digraph, which must be DAG.
deba@417
  1310
  /// \retval order A writable node map. The values will be set from 0 to
kpeter@648
  1311
  /// the number of the nodes in the digraph minus one. Each value of the
kpeter@648
  1312
  /// map will be set exactly once, and the values will be set descending
kpeter@648
  1313
  /// order.
deba@417
  1314
  ///
kpeter@648
  1315
  /// \see dag(), checkedTopologicalSort()
deba@417
  1316
  template <typename Digraph, typename NodeMap>
kpeter@648
  1317
  void topologicalSort(const Digraph& digraph, NodeMap& order) {
deba@419
  1318
    using namespace _connectivity_bits;
deba@417
  1319
deba@417
  1320
    checkConcept<concepts::Digraph, Digraph>();
deba@417
  1321
    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
deba@417
  1322
deba@417
  1323
    typedef typename Digraph::Node Node;
deba@417
  1324
    typedef typename Digraph::NodeIt NodeIt;
deba@417
  1325
    typedef typename Digraph::Arc Arc;
deba@417
  1326
deba@417
  1327
    TopologicalSortVisitor<Digraph, NodeMap>
kpeter@648
  1328
      visitor(order, countNodes(digraph));
deba@417
  1329
deba@417
  1330
    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
kpeter@648
  1331
      dfs(digraph, visitor);
deba@417
  1332
deba@417
  1333
    dfs.init();
kpeter@648
  1334
    for (NodeIt it(digraph); it != INVALID; ++it) {
deba@417
  1335
      if (!dfs.reached(it)) {
deba@417
  1336
        dfs.addSource(it);
deba@417
  1337
        dfs.start();
deba@417
  1338
      }
deba@417
  1339
    }
deba@417
  1340
  }
deba@417
  1341
kpeter@586
  1342
  /// \ingroup graph_properties
deba@417
  1343
  ///
deba@417
  1344
  /// \brief Sort the nodes of a DAG into topolgical order.
deba@417
  1345
  ///
kpeter@648
  1346
  /// This function sorts the nodes of the given acyclic digraph (DAG)
kpeter@648
  1347
  /// into topolgical order and also checks whether the given digraph
kpeter@648
  1348
  /// is DAG.
deba@417
  1349
  ///
kpeter@648
  1350
  /// \param digraph The digraph.
kpeter@648
  1351
  /// \retval order A readable and writable node map. The values will be
kpeter@648
  1352
  /// set from 0 to the number of the nodes in the digraph minus one. 
kpeter@648
  1353
  /// Each value of the map will be set exactly once, and the values will
kpeter@648
  1354
  /// be set descending order.
kpeter@648
  1355
  /// \return \c false if the digraph is not DAG.
deba@417
  1356
  ///
kpeter@648
  1357
  /// \see dag(), topologicalSort()
deba@417
  1358
  template <typename Digraph, typename NodeMap>
deba@419
  1359
  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
deba@419
  1360
    using namespace _connectivity_bits;
deba@417
  1361
deba@417
  1362
    checkConcept<concepts::Digraph, Digraph>();
deba@417
  1363
    checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
deba@417
  1364
      NodeMap>();
deba@417
  1365
deba@417
  1366
    typedef typename Digraph::Node Node;
deba@417
  1367
    typedef typename Digraph::NodeIt NodeIt;
deba@417
  1368
    typedef typename Digraph::Arc Arc;
deba@417
  1369
deba@419
  1370
    for (NodeIt it(digraph); it != INVALID; ++it) {
deba@419
  1371
      order.set(it, -1);
deba@419
  1372
    }
deba@417
  1373
deba@417
  1374
    TopologicalSortVisitor<Digraph, NodeMap>
deba@419
  1375
      visitor(order, countNodes(digraph));
deba@417
  1376
deba@417
  1377
    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
deba@419
  1378
      dfs(digraph, visitor);
deba@417
  1379
deba@417
  1380
    dfs.init();
deba@419
  1381
    for (NodeIt it(digraph); it != INVALID; ++it) {
deba@417
  1382
      if (!dfs.reached(it)) {
deba@417
  1383
        dfs.addSource(it);
deba@417
  1384
        while (!dfs.emptyQueue()) {
deba@419
  1385
           Arc arc = dfs.nextArc();
deba@419
  1386
           Node target = digraph.target(arc);
deba@417
  1387
           if (dfs.reached(target) && order[target] == -1) {
deba@417
  1388
             return false;
deba@417
  1389
           }
deba@417
  1390
           dfs.processNextArc();
deba@417
  1391
         }
deba@417
  1392
      }
deba@417
  1393
    }
deba@417
  1394
    return true;
deba@417
  1395
  }
deba@417
  1396
kpeter@586
  1397
  /// \ingroup graph_properties
deba@417
  1398
  ///
kpeter@648
  1399
  /// \brief Check whether an undirected graph is acyclic.
deba@417
  1400
  ///
kpeter@648
  1401
  /// This function checks whether the given undirected graph is acyclic.
kpeter@648
  1402
  /// \return \c true if there is no cycle in the graph.
kpeter@648
  1403
  /// \see dag()
deba@417
  1404
  template <typename Graph>
deba@417
  1405
  bool acyclic(const Graph& graph) {
deba@417
  1406
    checkConcept<concepts::Graph, Graph>();
deba@417
  1407
    typedef typename Graph::Node Node;
deba@417
  1408
    typedef typename Graph::NodeIt NodeIt;
deba@417
  1409
    typedef typename Graph::Arc Arc;
deba@417
  1410
    Dfs<Graph> dfs(graph);
deba@417
  1411
    dfs.init();
deba@417
  1412
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@417
  1413
      if (!dfs.reached(it)) {
deba@417
  1414
        dfs.addSource(it);
deba@417
  1415
        while (!dfs.emptyQueue()) {
kpeter@648
  1416
          Arc arc = dfs.nextArc();
kpeter@648
  1417
          Node source = graph.source(arc);
kpeter@648
  1418
          Node target = graph.target(arc);
deba@417
  1419
          if (dfs.reached(target) &&
kpeter@648
  1420
              dfs.predArc(source) != graph.oppositeArc(arc)) {
deba@417
  1421
            return false;
deba@417
  1422
          }
deba@417
  1423
          dfs.processNextArc();
deba@417
  1424
        }
deba@417
  1425
      }
deba@417
  1426
    }
deba@417
  1427
    return true;
deba@417
  1428
  }
deba@417
  1429
kpeter@586
  1430
  /// \ingroup graph_properties
deba@417
  1431
  ///
kpeter@648
  1432
  /// \brief Check whether an undirected graph is tree.
deba@417
  1433
  ///
kpeter@648
  1434
  /// This function checks whether the given undirected graph is tree.
kpeter@648
  1435
  /// \return \c true if the graph is acyclic and connected.
kpeter@648
  1436
  /// \see acyclic(), connected()
deba@417
  1437
  template <typename Graph>
deba@417
  1438
  bool tree(const Graph& graph) {
deba@417
  1439
    checkConcept<concepts::Graph, Graph>();
deba@417
  1440
    typedef typename Graph::Node Node;
deba@417
  1441
    typedef typename Graph::NodeIt NodeIt;
deba@417
  1442
    typedef typename Graph::Arc Arc;
kpeter@647
  1443
    if (NodeIt(graph) == INVALID) return true;
deba@417
  1444
    Dfs<Graph> dfs(graph);
deba@417
  1445
    dfs.init();
deba@417
  1446
    dfs.addSource(NodeIt(graph));
deba@417
  1447
    while (!dfs.emptyQueue()) {
kpeter@648
  1448
      Arc arc = dfs.nextArc();
kpeter@648
  1449
      Node source = graph.source(arc);
kpeter@648
  1450
      Node target = graph.target(arc);
deba@417
  1451
      if (dfs.reached(target) &&
kpeter@648
  1452
          dfs.predArc(source) != graph.oppositeArc(arc)) {
deba@417
  1453
        return false;
deba@417
  1454
      }
deba@417
  1455
      dfs.processNextArc();
deba@417
  1456
    }
deba@417
  1457
    for (NodeIt it(graph); it != INVALID; ++it) {
deba@417
  1458
      if (!dfs.reached(it)) {
deba@417
  1459
        return false;
deba@417
  1460
      }
deba@417
  1461
    }
deba@417
  1462
    return true;
deba@417
  1463
  }
deba@417
  1464
deba@419
  1465
  namespace _connectivity_bits {
deba@417
  1466
deba@417
  1467
    template <typename Digraph>
deba@417
  1468
    class BipartiteVisitor : public BfsVisitor<Digraph> {
deba@417
  1469
    public:
deba@417
  1470
      typedef typename Digraph::Arc Arc;
deba@417
  1471
      typedef typename Digraph::Node Node;
deba@417
  1472
deba@417
  1473
      BipartiteVisitor(const Digraph& graph, bool& bipartite)
deba@417
  1474
        : _graph(graph), _part(graph), _bipartite(bipartite) {}
deba@417
  1475
deba@417
  1476
      void start(const Node& node) {
deba@417
  1477
        _part[node] = true;
deba@417
  1478
      }
deba@417
  1479
      void discover(const Arc& edge) {
deba@417
  1480
        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
deba@417
  1481
      }
deba@417
  1482
      void examine(const Arc& edge) {
deba@417
  1483
        _bipartite = _bipartite &&
deba@417
  1484
          _part[_graph.target(edge)] != _part[_graph.source(edge)];
deba@417
  1485
      }
deba@417
  1486
deba@417
  1487
    private:
deba@417
  1488
deba@417
  1489
      const Digraph& _graph;
deba@417
  1490
      typename Digraph::template NodeMap<bool> _part;
deba@417
  1491
      bool& _bipartite;
deba@417
  1492
    };
deba@417
  1493
deba@417
  1494
    template <typename Digraph, typename PartMap>
deba@417
  1495
    class BipartitePartitionsVisitor : public BfsVisitor<Digraph> {
deba@417
  1496
    public:
deba@417
  1497
      typedef typename Digraph::Arc Arc;
deba@417
  1498
      typedef typename Digraph::Node Node;
deba@417
  1499
deba@417
  1500
      BipartitePartitionsVisitor(const Digraph& graph,
deba@417
  1501
                                 PartMap& part, bool& bipartite)
deba@417
  1502
        : _graph(graph), _part(part), _bipartite(bipartite) {}
deba@417
  1503
deba@417
  1504
      void start(const Node& node) {
deba@417
  1505
        _part.set(node, true);
deba@417
  1506
      }
deba@417
  1507
      void discover(const Arc& edge) {
deba@417
  1508
        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
deba@417
  1509
      }
deba@417
  1510
      void examine(const Arc& edge) {
deba@417
  1511
        _bipartite = _bipartite &&
deba@417
  1512
          _part[_graph.target(edge)] != _part[_graph.source(edge)];
deba@417
  1513
      }
deba@417
  1514
deba@417
  1515
    private:
deba@417
  1516
deba@417
  1517
      const Digraph& _graph;
deba@417
  1518
      PartMap& _part;
deba@417
  1519
      bool& _bipartite;
deba@417
  1520
    };
deba@417
  1521
  }
deba@417
  1522
kpeter@586
  1523
  /// \ingroup graph_properties
deba@417
  1524
  ///
kpeter@648
  1525
  /// \brief Check whether an undirected graph is bipartite.
deba@417
  1526
  ///
kpeter@648
  1527
  /// The function checks whether the given undirected graph is bipartite.
kpeter@648
  1528
  /// \return \c true if the graph is bipartite.
kpeter@648
  1529
  ///
kpeter@648
  1530
  /// \see bipartitePartitions()
deba@417
  1531
  template<typename Graph>
kpeter@648
  1532
  bool bipartite(const Graph &graph){
deba@419
  1533
    using namespace _connectivity_bits;
deba@417
  1534
deba@417
  1535
    checkConcept<concepts::Graph, Graph>();
deba@417
  1536
deba@417
  1537
    typedef typename Graph::NodeIt NodeIt;
deba@417
  1538
    typedef typename Graph::ArcIt ArcIt;
deba@417
  1539
deba@417
  1540
    bool bipartite = true;
deba@417
  1541
deba@417
  1542
    BipartiteVisitor<Graph>
deba@417
  1543
      visitor(graph, bipartite);
deba@417
  1544
    BfsVisit<Graph, BipartiteVisitor<Graph> >
deba@417
  1545
      bfs(graph, visitor);
deba@417
  1546
    bfs.init();
deba@417
  1547
    for(NodeIt it(graph); it != INVALID; ++it) {
deba@417
  1548
      if(!bfs.reached(it)){
deba@417
  1549
        bfs.addSource(it);
deba@417
  1550
        while (!bfs.emptyQueue()) {
deba@417
  1551
          bfs.processNextNode();
deba@417
  1552
          if (!bipartite) return false;
deba@417
  1553
        }
deba@417
  1554
      }
deba@417
  1555
    }
deba@417
  1556
    return true;
deba@417
  1557
  }
deba@417
  1558
kpeter@586
  1559
  /// \ingroup graph_properties
deba@417
  1560
  ///
kpeter@648
  1561
  /// \brief Find the bipartite partitions of an undirected graph.
deba@417
  1562
  ///
kpeter@648
  1563
  /// This function checks whether the given undirected graph is bipartite
kpeter@648
  1564
  /// and gives back the bipartite partitions.
kpeter@586
  1565
  ///
kpeter@586
  1566
  /// \image html bipartite_partitions.png
kpeter@586
  1567
  /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
kpeter@586
  1568
  ///
deba@417
  1569
  /// \param graph The undirected graph.
kpeter@648
  1570
  /// \retval partMap A writable node map of \c bool (or convertible) value
kpeter@648
  1571
  /// type. The values will be set to \c true for one component and
kpeter@648
  1572
  /// \c false for the other one.
kpeter@648
  1573
  /// \return \c true if the graph is bipartite, \c false otherwise.
kpeter@648
  1574
  ///
kpeter@648
  1575
  /// \see bipartite()
deba@417
  1576
  template<typename Graph, typename NodeMap>
kpeter@648
  1577
  bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
deba@419
  1578
    using namespace _connectivity_bits;
deba@417
  1579
deba@417
  1580
    checkConcept<concepts::Graph, Graph>();
kpeter@648
  1581
    checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
deba@417
  1582
deba@417
  1583
    typedef typename Graph::Node Node;
deba@417
  1584
    typedef typename Graph::NodeIt NodeIt;
deba@417
  1585
    typedef typename Graph::ArcIt ArcIt;
deba@417
  1586
deba@417
  1587
    bool bipartite = true;
deba@417
  1588
deba@417
  1589
    BipartitePartitionsVisitor<Graph, NodeMap>
deba@417
  1590
      visitor(graph, partMap, bipartite);
deba@417
  1591
    BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >
deba@417
  1592
      bfs(graph, visitor);
deba@417
  1593
    bfs.init();
deba@417
  1594
    for(NodeIt it(graph); it != INVALID; ++it) {
deba@417
  1595
      if(!bfs.reached(it)){
deba@417
  1596
        bfs.addSource(it);
deba@417
  1597
        while (!bfs.emptyQueue()) {
deba@417
  1598
          bfs.processNextNode();
deba@417
  1599
          if (!bipartite) return false;
deba@417
  1600
        }
deba@417
  1601
      }
deba@417
  1602
    }
deba@417
  1603
    return true;
deba@417
  1604
  }
deba@417
  1605
kpeter@648
  1606
  /// \ingroup graph_properties
deba@417
  1607
  ///
kpeter@648
  1608
  /// \brief Check whether the given graph contains no loop arcs/edges.
kpeter@648
  1609
  ///
kpeter@648
  1610
  /// This function returns \c true if there are no loop arcs/edges in
kpeter@648
  1611
  /// the given graph. It works for both directed and undirected graphs.
kpeter@648
  1612
  template <typename Graph>
kpeter@648
  1613
  bool loopFree(const Graph& graph) {
kpeter@648
  1614
    for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
kpeter@648
  1615
      if (graph.source(it) == graph.target(it)) return false;
deba@417
  1616
    }
deba@417
  1617
    return true;
deba@417
  1618
  }
deba@417
  1619
kpeter@648
  1620
  /// \ingroup graph_properties
deba@417
  1621
  ///
kpeter@648
  1622
  /// \brief Check whether the given graph contains no parallel arcs/edges.
kpeter@648
  1623
  ///
kpeter@648
  1624
  /// This function returns \c true if there are no parallel arcs/edges in
kpeter@648
  1625
  /// the given graph. It works for both directed and undirected graphs.
kpeter@647
  1626
  template <typename Graph>
kpeter@647
  1627
  bool parallelFree(const Graph& graph) {
kpeter@647
  1628
    typename Graph::template NodeMap<int> reached(graph, 0);
kpeter@647
  1629
    int cnt = 1;
kpeter@647
  1630
    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
kpeter@647
  1631
      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
kpeter@647
  1632
        if (reached[graph.target(a)] == cnt) return false;
kpeter@647
  1633
        reached[graph.target(a)] = cnt;
deba@417
  1634
      }
kpeter@647
  1635
      ++cnt;
deba@417
  1636
    }
deba@417
  1637
    return true;
deba@417
  1638
  }
deba@417
  1639
kpeter@648
  1640
  /// \ingroup graph_properties
deba@417
  1641
  ///
kpeter@648
  1642
  /// \brief Check whether the given graph is simple.
kpeter@648
  1643
  ///
kpeter@648
  1644
  /// This function returns \c true if the given graph is simple, i.e.
kpeter@648
  1645
  /// it contains no loop arcs/edges and no parallel arcs/edges.
kpeter@648
  1646
  /// The function works for both directed and undirected graphs.
kpeter@648
  1647
  /// \see loopFree(), parallelFree()
kpeter@647
  1648
  template <typename Graph>
kpeter@647
  1649
  bool simpleGraph(const Graph& graph) {
kpeter@647
  1650
    typename Graph::template NodeMap<int> reached(graph, 0);
kpeter@647
  1651
    int cnt = 1;
kpeter@647
  1652
    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
kpeter@647
  1653
      reached[n] = cnt;
kpeter@647
  1654
      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
kpeter@647
  1655
        if (reached[graph.target(a)] == cnt) return false;
kpeter@647
  1656
        reached[graph.target(a)] = cnt;
deba@417
  1657
      }
kpeter@647
  1658
      ++cnt;
deba@417
  1659
    }
deba@417
  1660
    return true;
deba@417
  1661
  }
deba@417
  1662
deba@417
  1663
} //namespace lemon
deba@417
  1664
deba@419
  1665
#endif //LEMON_CONNECTIVITY_H