lemon/connectivity.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 24 Apr 2009 11:54:48 +0200
changeset 617 4137ef9aacc6
parent 559 c5fd2d996909
child 647 dcba640438c7
permissions -rw-r--r--
Fix and uniform the usage of Graph and Parent typedefs (#268)

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