LEMON/LEMON-main Changeset - r648:4ff8041e9c2e

@@ -33,55 +33,65 @@

33

#include <functional>

34

35

/// \ingroup graph_properties

36

/// \file

37

/// \brief Connectivity algorithms

38

///

39

/// Connectivity algorithms

40

41

namespace lemon {

42

43

  /// \ingroup graph_properties

44

///

45

  /// \brief Check whether the given undirected graph is connected.

45

  /// \brief Check whether an undirected graph is connected.

46

///

47

  /// Check whether the given undirected graph is connected.

48

  /// \param graph The undirected graph.

49

  /// \return \c true when there is path between any two nodes in the graph.

47

  /// This function checks whether the given undirected graph is connected,

48

  /// i.e. there is a path between any two nodes in the graph.

49

///

50

  /// \return \c true if the graph is connected.

50

51

  /// \note By definition, the empty graph is connected.

52

///

53

  /// \see countConnectedComponents(), connectedComponents()

54

  /// \see stronglyConnected()

51

55

  template <typename Graph>

52

56

  bool connected(const Graph& graph) {

53

57

    checkConcept<concepts::Graph, Graph>();

54

58

    typedef typename Graph::NodeIt NodeIt;

55

59

    if (NodeIt(graph) == INVALID) return true;

56

60

    Dfs<Graph> dfs(graph);

57

61

    dfs.run(NodeIt(graph));

58

62

    for (NodeIt it(graph); it != INVALID; ++it) {

59

63

      if (!dfs.reached(it)) {

60

64

        return false;

    return true;

  /// \ingroup graph_properties

67

71

///

68

72

  /// \brief Count the number of connected components of an undirected graph

69

73

///

70

  /// Count the number of connected components of an undirected graph

74

  /// This function counts the number of connected components of the given

75

  /// undirected graph.

71

76

///

72

  /// \param graph The graph. It must be undirected.

73

  /// \return The number of components

77

  /// The connected components are the classes of an equivalence relation

78

  /// on the nodes of an undirected graph. Two nodes are in the same class

79

  /// if they are connected with a path.

80

///

81

  /// \return The number of connected components.

74

82

  /// \note By definition, the empty graph consists

75

83

  /// of zero connected components.

84

///

85

  /// \see connected(), connectedComponents()

76

86

  template <typename Graph>

77

87

  int countConnectedComponents(const Graph &graph) {

78

88

    checkConcept<concepts::Graph, Graph>();

79

89

    typedef typename Graph::Node Node;

80

90

    typedef typename Graph::Arc Arc;

    typedef NullMap<Node, Arc> PredMap;

83

93

    typedef NullMap<Node, int> DistMap;

    int compNum = 0;

86

96

    typename Bfs<Graph>::

87

97

      template SetPredMap<PredMap>::

...

@@ -100,35 +110,44 @@

100

110

        bfs.addSource(n);

101

111

        bfs.start();

102

112

        ++compNum;

    return compNum;

  /// \ingroup graph_properties

109

119

///

110

120

  /// \brief Find the connected components of an undirected graph

111

121

///

112

  /// Find the connected components of an undirected graph.

122

  /// This function finds the connected components of the given undirected

123

  /// graph.

124

///

125

  /// The connected components are the classes of an equivalence relation

126

  /// on the nodes of an undirected graph. Two nodes are in the same class

127

  /// if they are connected with a path.

113

128

///

114

129

  /// \image html connected_components.png

115

130

  /// \image latex connected_components.eps "Connected components" width=\textwidth

116

131

///

117

  /// \param graph The graph. It must be undirected.

132

  /// \param graph The undirected graph.

118

133

  /// \retval compMap A writable node map. The values will be set from 0 to

119

  /// the number of the connected components minus one. Each values of the map

120

  /// will be set exactly once, the values of a certain component will be

134

  /// the number of the connected components minus one. Each value of the map

135

  /// will be set exactly once, and the values of a certain component will be

121

136

  /// set continuously.

122

  /// \return The number of components

137

  /// \return The number of connected components.

138

  /// \note By definition, the empty graph consists

139

  /// of zero connected components.

140

///

141

  /// \see connected(), countConnectedComponents()

123

142

  template <class Graph, class NodeMap>

124

143

  int connectedComponents(const Graph &graph, NodeMap &compMap) {

125

144

    checkConcept<concepts::Graph, Graph>();

126

145

    typedef typename Graph::Node Node;

127

146

    typedef typename Graph::Arc Arc;

128

147

    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();

    typedef NullMap<Node, Arc> PredMap;

131

150

    typedef NullMap<Node, int> DistMap;

    int compNum = 0;

134

153

    typename Bfs<Graph>::

...

@@ -222,33 +241,35 @@

222

241

      ArcMap& _cutMap;

223

242

      int& _cutNum;

      typename Digraph::template NodeMap<int> _compMap;

226

245

      int _num;

227

246

};

  /// \ingroup graph_properties

233

252

///

234

  /// \brief Check whether the given directed graph is strongly connected.

253

  /// \brief Check whether a directed graph is strongly connected.

235

254

///

236

  /// Check whether the given directed graph is strongly connected. The

237

  /// graph is strongly connected when any two nodes of the graph are

255

  /// This function checks whether the given directed graph is strongly

256

  /// connected, i.e. any two nodes of the digraph are

238

257

  /// connected with directed paths in both direction.

239

  /// \return \c false when the graph is not strongly connected.

240

  /// \see connected

241

258

///

242

  /// \note By definition, the empty graph is strongly connected.

259

  /// \return \c true if the digraph is strongly connected.

260

  /// \note By definition, the empty digraph is strongly connected.

261

///

262

  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()

263

  /// \see connected()

243

264

  template <typename Digraph>

244

265

  bool stronglyConnected(const Digraph& digraph) {

245

266

    checkConcept<concepts::Digraph, Digraph>();

    typedef typename Digraph::Node Node;

248

269

    typedef typename Digraph::NodeIt NodeIt;

    typename Digraph::Node source = NodeIt(digraph);

251

272

    if (source == INVALID) return true;

    using namespace _connectivity_bits;

254

275

...

@@ -261,55 +282,59 @@

261

282

    dfs.start();

    for (NodeIt it(digraph); it != INVALID; ++it) {

264

285

      if (!dfs.reached(it)) {

265

286

        return false;

    typedef ReverseDigraph<const Digraph> RDigraph;

270

291

    typedef typename RDigraph::NodeIt RNodeIt;

271

292

    RDigraph rdigraph(digraph);

272

293

273

    typedef DfsVisitor<Digraph> RVisitor;

294

    typedef DfsVisitor<RDigraph> RVisitor;

274

295

    RVisitor rvisitor;

    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);

277

298

    rdfs.init();

278

299

    rdfs.addSource(source);

279

300

    rdfs.start();

    for (RNodeIt it(rdigraph); it != INVALID; ++it) {

282

303

      if (!rdfs.reached(it)) {

283

304

        return false;

    return true;

  /// \ingroup graph_properties

291

312

///

292

  /// \brief Count the strongly connected components of a directed graph

313

  /// \brief Count the number of strongly connected components of a

314

  /// directed graph

293

315

///

294

  /// Count the strongly connected components of a directed graph.

316

  /// This function counts the number of strongly connected components of

317

  /// the given directed graph.

318

///

295

319

  /// The strongly connected components are the classes of an

296

  /// equivalence relation on the nodes of the graph. Two nodes are in

320

  /// equivalence relation on the nodes of a digraph. Two nodes are in

297

321

  /// the same class if they are connected with directed paths in both

298

322

  /// direction.

299

323

///

300

  /// \param digraph The graph.

301

  /// \return The number of components

302

  /// \note By definition, the empty graph has zero

324

  /// \return The number of strongly connected components.

325

  /// \note By definition, the empty digraph has zero

303

326

  /// strongly connected components.

327

///

328

  /// \see stronglyConnected(), stronglyConnectedComponents()

304

329

  template <typename Digraph>

305

330

  int countStronglyConnectedComponents(const Digraph& digraph) {

306

331

    checkConcept<concepts::Digraph, Digraph>();

    using namespace _connectivity_bits;

    typedef typename Digraph::Node Node;

311

336

    typedef typename Digraph::Arc Arc;

312

337

    typedef typename Digraph::NodeIt NodeIt;

313

338

    typedef typename Digraph::ArcIt ArcIt;

    typedef std::vector<Node> Container;

...

@@ -346,41 +371,47 @@

346

371

        rdfs.addSource(*it);

347

372

        rdfs.start();

348

373

        ++compNum;

    return compNum;

  /// \ingroup graph_properties

355

380

///

356

381

  /// \brief Find the strongly connected components of a directed graph

357

382

///

358

  /// Find the strongly connected components of a directed graph.  The

359

  /// strongly connected components are the classes of an equivalence

360

  /// relation on the nodes of the graph. Two nodes are in

361

  /// relationship when there are directed paths between them in both

362

  /// direction. In addition, the numbering of components will satisfy

363

  /// that there is no arc going from a higher numbered component to

364

  /// a lower.

383

  /// This function finds the strongly connected components of the given

384

  /// directed graph. In addition, the numbering of the components will

385

  /// satisfy that there is no arc going from a higher numbered component

386

  /// to a lower one (i.e. it provides a topological order of the components).

387

///

388

  /// The strongly connected components are the classes of an

389

  /// equivalence relation on the nodes of a digraph. Two nodes are in

390

  /// the same class if they are connected with directed paths in both

391

  /// direction.

365

392

///

366

393

  /// \image html strongly_connected_components.png

367

394

  /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth

368

395

///

369

396

  /// \param digraph The digraph.

370

397

  /// \retval compMap A writable node map. The values will be set from 0 to

371

398

  /// the number of the strongly connected components minus one. Each value

372

  /// of the map will be set exactly once, the values of a certain component

373

  /// will be set continuously.

374

  /// \return The number of components

399

  /// of the map will be set exactly once, and the values of a certain

400

  /// component will be set continuously.

401

  /// \return The number of strongly connected components.

402

  /// \note By definition, the empty digraph has zero

403

  /// strongly connected components.

404

///

405

  /// \see stronglyConnected(), countStronglyConnectedComponents()

375

406

  template <typename Digraph, typename NodeMap>

376

407

  int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {

377

408

    checkConcept<concepts::Digraph, Digraph>();

378

409

    typedef typename Digraph::Node Node;

379

410

    typedef typename Digraph::NodeIt NodeIt;

380

411

    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();

    using namespace _connectivity_bits;

    typedef std::vector<Node> Container;

385

416

    typedef typename Container::iterator Iterator;

386

417

...

@@ -415,72 +446,77 @@

415

446

        rdfs.addSource(*it);

416

447

        rdfs.start();

417

448

        ++compNum;

    return compNum;

  /// \ingroup graph_properties

424

455

///

425

456

  /// \brief Find the cut arcs of the strongly connected components.

426

457

///

427

  /// Find the cut arcs of the strongly connected components.

428

  /// The strongly connected components are the classes of an equivalence

429

  /// relation on the nodes of the graph. Two nodes are in relationship

430

  /// when there are directed paths between them in both direction.

458

  /// This function finds the cut arcs of the strongly connected components

459

  /// of the given digraph.

460

///

461

  /// The strongly connected components are the classes of an

462

  /// equivalence relation on the nodes of a digraph. Two nodes are in

463

  /// the same class if they are connected with directed paths in both

464

  /// direction.

431

465

  /// The strongly connected components are separated by the cut arcs.

432

466

///

433

  /// \param graph The graph.

434

  /// \retval cutMap A writable node map. The values will be set true when the

435

  /// arc is a cut arc.

467

  /// \param digraph The digraph.

468

  /// \retval cutMap A writable arc map. The values will be set to \c true

469

  /// for the cut arcs (exactly once for each cut arc), and will not be

470

  /// changed for other arcs.

471

  /// \return The number of cut arcs.

436

472

///

437

  /// \return The number of cut arcs

473

  /// \see stronglyConnected(), stronglyConnectedComponents()

438

474

  template <typename Digraph, typename ArcMap>

439

  int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {

475

  int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {

440

476

    checkConcept<concepts::Digraph, Digraph>();

441

477

    typedef typename Digraph::Node Node;

442

478

    typedef typename Digraph::Arc Arc;

443

479

    typedef typename Digraph::NodeIt NodeIt;

444

480

    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();

    using namespace _connectivity_bits;

    typedef std::vector<Node> Container;

449

485

    typedef typename Container::iterator Iterator;

450

486

451

    Container nodes(countNodes(graph));

487

    Container nodes(countNodes(digraph));

452

488

    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;

453

489

    Visitor visitor(nodes.begin());

454

490

455

    DfsVisit<Digraph, Visitor> dfs(graph, visitor);

491

    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);

456

492

    dfs.init();

457

    for (NodeIt it(graph); it != INVALID; ++it) {

493

    for (NodeIt it(digraph); it != INVALID; ++it) {

458

494

      if (!dfs.reached(it)) {

459

495

        dfs.addSource(it);

460

496

        dfs.start();

    typedef typename Container::reverse_iterator RIterator;

465

501

    typedef ReverseDigraph<const Digraph> RDigraph;

466

502

467

    RDigraph rgraph(graph);

503

    RDigraph rdigraph(digraph);

    int cutNum = 0;

    typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;

472

    RVisitor rvisitor(rgraph, cutMap, cutNum);

508

    RVisitor rvisitor(rdigraph, cutMap, cutNum);

473

509

474

    DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);

510

    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);

    rdfs.init();

477

513

    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {

478

514

      if (!rdfs.reached(*it)) {

479

515

        rdfs.addSource(*it);

480

516

        rdfs.start();

    return cutNum;

  namespace _connectivity_bits {

...

@@ -697,48 +733,53 @@

697

733

      std::stack<Edge> _edgeStack;

698

734

      int _num;

699

735

      bool rootCut;

700

736

};

  template <typename Graph>

705

741

  int countBiNodeConnectedComponents(const Graph& graph);

  /// \ingroup graph_properties

708

744

///

709

  /// \brief Checks the graph is bi-node-connected.

745

  /// \brief Check whether an undirected graph is bi-node-connected.

710

746

///

711

  /// This function checks that the undirected graph is bi-node-connected

712

  /// graph. The graph is bi-node-connected if any two undirected edge is

713

  /// on same circle.

747

  /// This function checks whether the given undirected graph is

748

  /// bi-node-connected, i.e. any two edges are on same circle.

714

749

///

715

  /// \param graph The graph.

716

  /// \return \c true when the graph bi-node-connected.

750

  /// \return \c true if the graph bi-node-connected.

751

  /// \note By definition, the empty graph is bi-node-connected.

752

///

753

  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()

717

754

  template <typename Graph>

718

755

  bool biNodeConnected(const Graph& graph) {

719

756

    return countBiNodeConnectedComponents(graph) <= 1;

  /// \ingroup graph_properties

723

760

///

724

  /// \brief Count the biconnected components.

761

  /// \brief Count the number of bi-node-connected components of an

762

  /// undirected graph.

725

763

///

726

  /// This function finds the bi-node-connected components in an undirected

727

  /// graph. The biconnected components are the classes of an equivalence

728

  /// relation on the undirected edges. Two undirected edge is in relationship

729

  /// when they are on same circle.

764

  /// This function counts the number of bi-node-connected components of

765

  /// the given undirected graph.

730

766

///

731

  /// \param graph The graph.

732

  /// \return The number of components.

767

  /// The bi-node-connected components are the classes of an equivalence

768

  /// relation on the edges of a undirected graph. Two edges are in the

769

  /// same class if they are on same circle.

770

///

771

  /// \return The number of bi-node-connected components.

772

///

773

  /// \see biNodeConnected(), biNodeConnectedComponents()

733

774

  template <typename Graph>

734

775

  int countBiNodeConnectedComponents(const Graph& graph) {

735

776

    checkConcept<concepts::Graph, Graph>();

736

777

    typedef typename Graph::NodeIt NodeIt;

    using namespace _connectivity_bits;

    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;

    int compNum = 0;

743

784

    Visitor visitor(graph, compNum);

744

785

...

@@ -747,40 +788,44 @@

    for (NodeIt it(graph); it != INVALID; ++it) {

749

790

      if (!dfs.reached(it)) {

750

791

        dfs.addSource(it);

751

792

        dfs.start();

    return compNum;

  /// \ingroup graph_properties

758

799

///

759

  /// \brief Find the bi-node-connected components.

800

  /// \brief Find the bi-node-connected components of an undirected graph.

760

801

///

761

  /// This function finds the bi-node-connected components in an undirected

762

  /// graph. The bi-node-connected components are the classes of an equivalence

763

  /// relation on the undirected edges. Two undirected edge are in relationship

764

  /// when they are on same circle.

802

  /// This function finds the bi-node-connected components of the given

803

  /// undirected graph.

804

///

805

  /// The bi-node-connected components are the classes of an equivalence

806

  /// relation on the edges of a undirected graph. Two edges are in the

807

  /// same class if they are on same circle.

765

808

///

766

809

  /// \image html node_biconnected_components.png

767

810

  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth

768

811

///

769

  /// \param graph The graph.

770

  /// \retval compMap A writable uedge map. The values will be set from 0

771

  /// to the number of the biconnected components minus one. Each values

772

  /// of the map will be set exactly once, the values of a certain component

773

  /// will be set continuously.

774

  /// \return The number of components.

812

  /// \param graph The undirected graph.

813

  /// \retval compMap A writable edge map. The values will be set from 0

814

  /// to the number of the bi-node-connected components minus one. Each

815

  /// value of the map will be set exactly once, and the values of a

816

  /// certain component will be set continuously.

817

  /// \return The number of bi-node-connected components.

818

///

819

  /// \see biNodeConnected(), countBiNodeConnectedComponents()

775

820

  template <typename Graph, typename EdgeMap>

776

821

  int biNodeConnectedComponents(const Graph& graph,

777

822

                                EdgeMap& compMap) {

778

823

    checkConcept<concepts::Graph, Graph>();

779

824

    typedef typename Graph::NodeIt NodeIt;

780

825

    typedef typename Graph::Edge Edge;

781

826

    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();

    using namespace _connectivity_bits;

    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;

786

831

...

@@ -792,36 +837,43 @@

    for (NodeIt it(graph); it != INVALID; ++it) {

794

839

      if (!dfs.reached(it)) {

795

840

        dfs.addSource(it);

796

841

        dfs.start();

    return compNum;

  /// \ingroup graph_properties

803

848

///

804

  /// \brief Find the bi-node-connected cut nodes.

849

  /// \brief Find the bi-node-connected cut nodes in an undirected graph.

805

850

///

806

  /// This function finds the bi-node-connected cut nodes in an undirected

807

  /// graph. The bi-node-connected components are the classes of an equivalence

808

  /// relation on the undirected edges. Two undirected edges are in

809

  /// relationship when they are on same circle. The biconnected components

810

  /// are separted by nodes which are the cut nodes of the components.

851

  /// This function finds the bi-node-connected cut nodes in the given

852

  /// undirected graph.

811

853

///

812

  /// \param graph The graph.

813

  /// \retval cutMap A writable edge map. The values will be set true when

814

  /// the node separate two or more components.

854

  /// The bi-node-connected components are the classes of an equivalence

855

  /// relation on the edges of a undirected graph. Two edges are in the

856

  /// same class if they are on same circle.

857

  /// The bi-node-connected components are separted by the cut nodes of

858

  /// the components.

859

///

860

  /// \param graph The undirected graph.

861

  /// \retval cutMap A writable node map. The values will be set to

862

  /// \c true for the nodes that separate two or more components

863

  /// (exactly once for each cut node), and will not be changed for

864

  /// other nodes.

815

865

  /// \return The number of the cut nodes.

866

///

867

  /// \see biNodeConnected(), biNodeConnectedComponents()

816

868

  template <typename Graph, typename NodeMap>

817

869

  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {

818

870

    checkConcept<concepts::Graph, Graph>();

819

871

    typedef typename Graph::Node Node;

820

872

    typedef typename Graph::NodeIt NodeIt;

821

873

    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();

    using namespace _connectivity_bits;

    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;

    int cutNum = 0;

...

@@ -1022,48 +1074,55 @@

1022

1074

      typename Digraph::template NodeMap<int> _numMap;

1023

1075

      typename Digraph::template NodeMap<int> _retMap;

1024

1076

      typename Digraph::template NodeMap<Arc> _predMap;

1025

1077

      int _num;

1026

1078

};

  template <typename Graph>

1030

1082

  int countBiEdgeConnectedComponents(const Graph& graph);

  /// \ingroup graph_properties

1033

1085

///

1034

  /// \brief Checks that the graph is bi-edge-connected.

1086

  /// \brief Check whether an undirected graph is bi-edge-connected.

1035

1087

///

1036

  /// This function checks that the graph is bi-edge-connected. The undirected

1037

  /// graph is bi-edge-connected when any two nodes are connected with two

1038

  /// edge-disjoint paths.

1088

  /// This function checks whether the given undirected graph is

1089

  /// bi-edge-connected, i.e. any two nodes are connected with at least

1090

  /// two edge-disjoint paths.

1039

1091

///

1040

  /// \param graph The undirected graph.

1041

  /// \return The number of components.

1092

  /// \return \c true if the graph is bi-edge-connected.

1093

  /// \note By definition, the empty graph is bi-edge-connected.

1094

///

1095

  /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()

1042

1096

  template <typename Graph>

1043

1097

  bool biEdgeConnected(const Graph& graph) {

1044

1098

    return countBiEdgeConnectedComponents(graph) <= 1;

  /// \ingroup graph_properties

1048

1102

///

1049

  /// \brief Count the bi-edge-connected components.

1103

  /// \brief Count the number of bi-edge-connected components of an

1104

  /// undirected graph.

1050

1105

///

1051

  /// This function count the bi-edge-connected components in an undirected

1052

  /// graph. The bi-edge-connected components are the classes of an equivalence

1053

  /// relation on the nodes. Two nodes are in relationship when they are

1054

  /// connected with at least two edge-disjoint paths.

1106

  /// This function counts the number of bi-edge-connected components of

1107

  /// the given undirected graph.

1055

1108

///

1056

  /// \param graph The undirected graph.

1057

  /// \return The number of components.

1109

  /// The bi-edge-connected components are the classes of an equivalence

1110

  /// relation on the nodes of an undirected graph. Two nodes are in the

1111

  /// same class if they are connected with at least two edge-disjoint

1112

  /// paths.

1113

///

1114

  /// \return The number of bi-edge-connected components.

1115

///

1116

  /// \see biEdgeConnected(), biEdgeConnectedComponents()

1058

1117

  template <typename Graph>

1059

1118

  int countBiEdgeConnectedComponents(const Graph& graph) {

1060

1119

    checkConcept<concepts::Graph, Graph>();

1061

1120

    typedef typename Graph::NodeIt NodeIt;

    using namespace _connectivity_bits;

    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;

    int compNum = 0;

1068

1127

    Visitor visitor(graph, compNum);

1069

1128

...

@@ -1072,40 +1131,45 @@

    for (NodeIt it(graph); it != INVALID; ++it) {

1074

1133

      if (!dfs.reached(it)) {

1075

1134

        dfs.addSource(it);

1076

1135

        dfs.start();

    return compNum;

  /// \ingroup graph_properties

1083

1142

///

1084

  /// \brief Find the bi-edge-connected components.

1143

  /// \brief Find the bi-edge-connected components of an undirected graph.

1085

1144

///

1086

  /// This function finds the bi-edge-connected components in an undirected

1087

  /// graph. The bi-edge-connected components are the classes of an equivalence

1088

  /// relation on the nodes. Two nodes are in relationship when they are

1089

  /// connected at least two edge-disjoint paths.

1145

  /// This function finds the bi-edge-connected components of the given

1146

  /// undirected graph.

1147

///

1148

  /// The bi-edge-connected components are the classes of an equivalence

1149

  /// relation on the nodes of an undirected graph. Two nodes are in the

1150

  /// same class if they are connected with at least two edge-disjoint

1151

  /// paths.

1090

1152

///

1091

1153

  /// \image html edge_biconnected_components.png

1092

1154

  /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth

1093

1155

///

1094

  /// \param graph The graph.

1156

  /// \param graph The undirected graph.

1095

1157

  /// \retval compMap A writable node map. The values will be set from 0 to

1096

  /// the number of the biconnected components minus one. Each values

1097

  /// of the map will be set exactly once, the values of a certain component

1098

  /// will be set continuously.

1099

  /// \return The number of components.

1158

  /// the number of the bi-edge-connected components minus one. Each value

1159

  /// of the map will be set exactly once, and the values of a certain

1160

  /// component will be set continuously.

1161

  /// \return The number of bi-edge-connected components.

1162

///

1163

  /// \see biEdgeConnected(), countBiEdgeConnectedComponents()

1100

1164

  template <typename Graph, typename NodeMap>

1101

1165

  int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {

1102

1166

    checkConcept<concepts::Graph, Graph>();

1103

1167

    typedef typename Graph::NodeIt NodeIt;

1104

1168

    typedef typename Graph::Node Node;

1105

1169

    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();

    using namespace _connectivity_bits;

    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;

    int compNum = 0;

...

@@ -1116,37 +1180,43 @@

    for (NodeIt it(graph); it != INVALID; ++it) {

1118

1182

      if (!dfs.reached(it)) {

1119

1183

        dfs.addSource(it);

1120

1184

        dfs.start();

    return compNum;

  /// \ingroup graph_properties

1127

1191

///

1128

  /// \brief Find the bi-edge-connected cut edges.

1192

  /// \brief Find the bi-edge-connected cut edges in an undirected graph.

1129

1193

///

1130

  /// This function finds the bi-edge-connected components in an undirected

1131

  /// graph. The bi-edge-connected components are the classes of an equivalence

1132

  /// relation on the nodes. Two nodes are in relationship when they are

1133

  /// connected with at least two edge-disjoint paths. The bi-edge-connected

1134

  /// components are separted by edges which are the cut edges of the

1135

  /// components.

1194

  /// This function finds the bi-edge-connected cut edges in the given

1195

  /// undirected graph.

1136

1196

///

1137

  /// \param graph The graph.

1138

  /// \retval cutMap A writable node map. The values will be set true when the

1139

  /// edge is a cut edge.

1197

  /// The bi-edge-connected components are the classes of an equivalence

1198

  /// relation on the nodes of an undirected graph. Two nodes are in the

1199

  /// same class if they are connected with at least two edge-disjoint

1200

  /// paths.

1201

  /// The bi-edge-connected components are separted by the cut edges of

1202

  /// the components.

1203

///

1204

  /// \param graph The undirected graph.

1205

  /// \retval cutMap A writable edge map. The values will be set to \c true

1206

  /// for the cut edges (exactly once for each cut edge), and will not be

1207

  /// changed for other edges.

1140

1208

  /// \return The number of cut edges.

1209

///

1210

  /// \see biEdgeConnected(), biEdgeConnectedComponents()

1141

1211

  template <typename Graph, typename EdgeMap>

1142

1212

  int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {

1143

1213

    checkConcept<concepts::Graph, Graph>();

1144

1214

    typedef typename Graph::NodeIt NodeIt;

1145

1215

    typedef typename Graph::Edge Edge;

1146

1216

    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();

    using namespace _connectivity_bits;

    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;

    int cutNum = 0;

...

@@ -1180,77 +1250,120 @@

1180

1250

        _order.set(node, --_num);

    private:

1184

1254

      IntNodeMap& _order;

1185

1255

      int _num;

1186

1256

};

  /// \ingroup graph_properties

1191

1261

///

1262

  /// \brief Check whether a digraph is DAG.

1263

///

1264

  /// This function checks whether the given digraph is DAG, i.e.

1265

  /// \e Directed \e Acyclic \e Graph.

1266

  /// \return \c true if there is no directed cycle in the digraph.

1267

  /// \see acyclic()

1268

  template <typename Digraph>

1269

  bool dag(const Digraph& digraph) {

1270

1271

    checkConcept<concepts::Digraph, Digraph>();

1272

1273

    typedef typename Digraph::Node Node;

1274

    typedef typename Digraph::NodeIt NodeIt;

1275

    typedef typename Digraph::Arc Arc;

1276

1277

    typedef typename Digraph::template NodeMap<bool> ProcessedMap;

1278

1279

    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::

1280

      Create dfs(digraph);

1281

1282

    ProcessedMap processed(digraph);

1283

    dfs.processedMap(processed);

1284

1285

    dfs.init();

1286

    for (NodeIt it(digraph); it != INVALID; ++it) {

1287

      if (!dfs.reached(it)) {

1288

        dfs.addSource(it);

1289

        while (!dfs.emptyQueue()) {

1290

          Arc arc = dfs.nextArc();

1291

          Node target = digraph.target(arc);

1292

          if (dfs.reached(target) && !processed[target]) {

1293

            return false;

1294

1295

          dfs.processNextArc();

    return true;

1300

1301

1302

  /// \ingroup graph_properties

1303

///

1192

1304

  /// \brief Sort the nodes of a DAG into topolgical order.

1193

1305

///

1194

  /// Sort the nodes of a DAG into topolgical order.

1306

  /// This function sorts the nodes of the given acyclic digraph (DAG)

1307

  /// into topolgical order.

1195

1308

///

1196

  /// \param graph The graph. It must be directed and acyclic.

1309

  /// \param digraph The digraph, which must be DAG.

1197

1310

  /// \retval order A writable node map. The values will be set from 0 to

1198

  /// the number of the nodes in the graph minus one. Each values of the map

1199

  /// will be set exactly once, the values  will be set descending order.

1311

  /// the number of the nodes in the digraph minus one. Each value of the

1312

  /// map will be set exactly once, and the values will be set descending

1313

  /// order.

1200

1314

///

1201

  /// \see checkedTopologicalSort

1202

  /// \see dag

1315

  /// \see dag(), checkedTopologicalSort()

1203

1316

  template <typename Digraph, typename NodeMap>

1204

  void topologicalSort(const Digraph& graph, NodeMap& order) {

1317

  void topologicalSort(const Digraph& digraph, NodeMap& order) {

1205

1318

    using namespace _connectivity_bits;

    checkConcept<concepts::Digraph, Digraph>();

1208

1321

    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();

    typedef typename Digraph::Node Node;

1211

1324

    typedef typename Digraph::NodeIt NodeIt;

1212

1325

    typedef typename Digraph::Arc Arc;

    TopologicalSortVisitor<Digraph, NodeMap>

1215

      visitor(order, countNodes(graph));

1328

      visitor(order, countNodes(digraph));

    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >

1218

      dfs(graph, visitor);

1331

      dfs(digraph, visitor);

    dfs.init();

1221

    for (NodeIt it(graph); it != INVALID; ++it) {

1334

    for (NodeIt it(digraph); it != INVALID; ++it) {

1222

1335

      if (!dfs.reached(it)) {

1223

1336

        dfs.addSource(it);

1224

1337

        dfs.start();

  /// \ingroup graph_properties

1230

1343

///

1231

1344

  /// \brief Sort the nodes of a DAG into topolgical order.

1232

1345

///

1233

  /// Sort the nodes of a DAG into topolgical order. It also checks

1234

  /// that the given graph is DAG.

1346

  /// This function sorts the nodes of the given acyclic digraph (DAG)

1347

  /// into topolgical order and also checks whether the given digraph

1348

  /// is DAG.

1235

1349

///

1236

  /// \param digraph The graph. It must be directed and acyclic.

1237

  /// \retval order A readable - writable node map. The values will be set

1238

  /// from 0 to the number of the nodes in the graph minus one. Each values

1239

  /// of the map will be set exactly once, the values will be set descending

1240

  /// order.

1241

  /// \return \c false when the graph is not DAG.

1350

  /// \param digraph The digraph.

1351

  /// \retval order A readable and writable node map. The values will be

1352

  /// set from 0 to the number of the nodes in the digraph minus one.

1353

  /// Each value of the map will be set exactly once, and the values will

1354

  /// be set descending order.

1355

  /// \return \c false if the digraph is not DAG.

1242

1356

///

1243

  /// \see topologicalSort

1244

  /// \see dag

1357

  /// \see dag(), topologicalSort()

1245

1358

  template <typename Digraph, typename NodeMap>

1246

1359

  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {

1247

1360

    using namespace _connectivity_bits;

    checkConcept<concepts::Digraph, Digraph>();

1250

1363

    checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,

1251

1364

      NodeMap>();

    typedef typename Digraph::Node Node;

1254

1367

    typedef typename Digraph::NodeIt NodeIt;

1255

1368

    typedef typename Digraph::Arc Arc;

1256

1369

...

@@ -1274,121 +1387,78 @@

1274

1387

           if (dfs.reached(target) && order[target] == -1) {

1275

1388

             return false;

           dfs.processNextArc();

    return true;

  /// \ingroup graph_properties

1285

1398

///

1286

  /// \brief Check that the given directed graph is a DAG.

1399

  /// \brief Check whether an undirected graph is acyclic.

1287

1400

///

1288

  /// Check that the given directed graph is a DAG. The DAG is

1289

  /// an Directed Acyclic Digraph.

1290

  /// \return \c false when the graph is not DAG.

1291

  /// \see acyclic

1292

  template <typename Digraph>

1293

  bool dag(const Digraph& digraph) {

1294

1295

    checkConcept<concepts::Digraph, Digraph>();

1296

1297

    typedef typename Digraph::Node Node;

1298

    typedef typename Digraph::NodeIt NodeIt;

1299

    typedef typename Digraph::Arc Arc;

1300

1301

    typedef typename Digraph::template NodeMap<bool> ProcessedMap;

1302

1303

    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::

1304

      Create dfs(digraph);

1305

1306

    ProcessedMap processed(digraph);

1307

    dfs.processedMap(processed);

1308

1309

    dfs.init();

1310

    for (NodeIt it(digraph); it != INVALID; ++it) {

1311

      if (!dfs.reached(it)) {

1312

        dfs.addSource(it);

1313

        while (!dfs.emptyQueue()) {

1314

          Arc edge = dfs.nextArc();

1315

          Node target = digraph.target(edge);

1316

          if (dfs.reached(target) && !processed[target]) {

1317

            return false;

1318

1319

          dfs.processNextArc();

    return true;

1324

1325

1326

  /// \ingroup graph_properties

1327

///

1328

  /// \brief Check that the given undirected graph is acyclic.

1329

///

1330

  /// Check that the given undirected graph acyclic.

1331

  /// \param graph The undirected graph.

1332

  /// \return \c true when there is no circle in the graph.

1333

  /// \see dag

1401

  /// This function checks whether the given undirected graph is acyclic.

1402

  /// \return \c true if there is no cycle in the graph.

1403

  /// \see dag()

1334

1404

  template <typename Graph>

1335

1405

  bool acyclic(const Graph& graph) {

1336

1406

    checkConcept<concepts::Graph, Graph>();

1337

1407

    typedef typename Graph::Node Node;

1338

1408

    typedef typename Graph::NodeIt NodeIt;

1339

1409

    typedef typename Graph::Arc Arc;

1340

1410

    Dfs<Graph> dfs(graph);

1341

1411

    dfs.init();

1342

1412

    for (NodeIt it(graph); it != INVALID; ++it) {

1343

1413

      if (!dfs.reached(it)) {

1344

1414

        dfs.addSource(it);

1345

1415

        while (!dfs.emptyQueue()) {

1346

          Arc edge = dfs.nextArc();

1347

          Node source = graph.source(edge);

1348

          Node target = graph.target(edge);

1416

          Arc arc = dfs.nextArc();

1417

          Node source = graph.source(arc);

1418

          Node target = graph.target(arc);

1349

1419

          if (dfs.reached(target) &&

1350

              dfs.predArc(source) != graph.oppositeArc(edge)) {

1420

              dfs.predArc(source) != graph.oppositeArc(arc)) {

1351

1421

            return false;

          dfs.processNextArc();

    return true;

  /// \ingroup graph_properties

1361

1431

///

1362

  /// \brief Check that the given undirected graph is tree.

1432

  /// \brief Check whether an undirected graph is tree.

1363

1433

///

1364

  /// Check that the given undirected graph is tree.

1365

  /// \param graph The undirected graph.

1366

  /// \return \c true when the graph is acyclic and connected.

1434

  /// This function checks whether the given undirected graph is tree.

1435

  /// \return \c true if the graph is acyclic and connected.

1436

  /// \see acyclic(), connected()

1367

1437

  template <typename Graph>

1368

1438

  bool tree(const Graph& graph) {

1369

1439

    checkConcept<concepts::Graph, Graph>();

1370

1440

    typedef typename Graph::Node Node;

1371

1441

    typedef typename Graph::NodeIt NodeIt;

1372

1442

    typedef typename Graph::Arc Arc;

1373

1443

    if (NodeIt(graph) == INVALID) return true;

1374

1444

    Dfs<Graph> dfs(graph);

1375

1445

    dfs.init();

1376

1446

    dfs.addSource(NodeIt(graph));

1377

1447

    while (!dfs.emptyQueue()) {

1378

      Arc edge = dfs.nextArc();

1379

      Node source = graph.source(edge);

1380

      Node target = graph.target(edge);

1448

      Arc arc = dfs.nextArc();

1449

      Node source = graph.source(arc);

1450

      Node target = graph.target(arc);

1381

1451

      if (dfs.reached(target) &&

1382

          dfs.predArc(source) != graph.oppositeArc(edge)) {

1452

          dfs.predArc(source) != graph.oppositeArc(arc)) {

1383

1453

        return false;

      dfs.processNextArc();

    for (NodeIt it(graph); it != INVALID; ++it) {

1388

1458

      if (!dfs.reached(it)) {

1389

1459

        return false;

    return true;

@@ -1443,33 +1513,32 @@

    private:

      const Digraph& _graph;

1448

1518

      PartMap& _part;

1449

1519

      bool& _bipartite;

1450

1520

};

  /// \ingroup graph_properties

1454

1524

///

1455

  /// \brief Check if the given undirected graph is bipartite or not

1525

  /// \brief Check whether an undirected graph is bipartite.

1456

1526

///

1457

  /// The function checks if the given undirected \c graph graph is bipartite

1458

  /// or not. The \ref Bfs algorithm is used to calculate the result.

1459

  /// \param graph The undirected graph.

1460

  /// \return \c true if \c graph is bipartite, \c false otherwise.

1461

  /// \sa bipartitePartitions

1527

  /// The function checks whether the given undirected graph is bipartite.

1528

  /// \return \c true if the graph is bipartite.

1529

///

1530

  /// \see bipartitePartitions()

1462

1531

  template<typename Graph>

1463

  inline bool bipartite(const Graph &graph){

1532

  bool bipartite(const Graph &graph){

1464

1533

    using namespace _connectivity_bits;

    checkConcept<concepts::Graph, Graph>();

    typedef typename Graph::NodeIt NodeIt;

1469

1538

    typedef typename Graph::ArcIt ArcIt;

    bool bipartite = true;

    BipartiteVisitor<Graph>

1474

1543

      visitor(graph, bipartite);

1475

1544

    BfsVisit<Graph, BipartiteVisitor<Graph> >

...

@@ -1480,100 +1549,111 @@

1480

1549

        bfs.addSource(it);

1481

1550

        while (!bfs.emptyQueue()) {

1482

1551

          bfs.processNextNode();

1483

1552

          if (!bipartite) return false;

    return true;

  /// \ingroup graph_properties

1491

1560

///

1492

  /// \brief Check if the given undirected graph is bipartite or not

1561

  /// \brief Find the bipartite partitions of an undirected graph.

1493

1562

///

1494

  /// The function checks if the given undirected graph is bipartite

1495

  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.

1496

  /// During the execution, the \c partMap will be set as the two

1497

  /// partitions of the graph.

1563

  /// This function checks whether the given undirected graph is bipartite

1564

  /// and gives back the bipartite partitions.

1498

1565

///

1499

1566

  /// \image html bipartite_partitions.png

1500

1567

  /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth

1501

1568

///

1502

1569

  /// \param graph The undirected graph.

1503

  /// \retval partMap A writable bool map of nodes. It will be set as the

1504

  /// two partitions of the graph.

1505

  /// \return \c true if \c graph is bipartite, \c false otherwise.

1570

  /// \retval partMap A writable node map of \c bool (or convertible) value

1571

  /// type. The values will be set to \c true for one component and

1572

  /// \c false for the other one.

1573

  /// \return \c true if the graph is bipartite, \c false otherwise.

1574

///

1575

  /// \see bipartite()

1506

1576

  template<typename Graph, typename NodeMap>

1507

  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){

1577

  bool bipartitePartitions(const Graph &graph, NodeMap &partMap){

1508

1578

    using namespace _connectivity_bits;

    checkConcept<concepts::Graph, Graph>();

1581

    checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();

    typedef typename Graph::Node Node;

1513

1584

    typedef typename Graph::NodeIt NodeIt;

1514

1585

    typedef typename Graph::ArcIt ArcIt;

    bool bipartite = true;

    BipartitePartitionsVisitor<Graph, NodeMap>

1519

1590

      visitor(graph, partMap, bipartite);

1520

1591

    BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >

1521

1592

      bfs(graph, visitor);

1522

1593

    bfs.init();

1523

1594

    for(NodeIt it(graph); it != INVALID; ++it) {

1524

1595

      if(!bfs.reached(it)){

1525

1596

        bfs.addSource(it);

1526

1597

        while (!bfs.emptyQueue()) {

1527

1598

          bfs.processNextNode();

1528

1599

          if (!bipartite) return false;

    return true;

  /// \brief Returns true when there are not loop edges in the graph.

1606

  /// \ingroup graph_properties

1536

1607

///

1537

  /// Returns true when there are not loop edges in the graph.

1538

  template <typename Digraph>

1539

  bool loopFree(const Digraph& digraph) {

1540

    for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {

1541

      if (digraph.source(it) == digraph.target(it)) return false;

1608

  /// \brief Check whether the given graph contains no loop arcs/edges.

1609

///

1610

  /// This function returns \c true if there are no loop arcs/edges in

1611

  /// the given graph. It works for both directed and undirected graphs.

1612

  template <typename Graph>

1613

  bool loopFree(const Graph& graph) {

1614

    for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {

1615

      if (graph.source(it) == graph.target(it)) return false;

    return true;

  /// \brief Returns true when there are not parallel edges in the graph.

1620

  /// \ingroup graph_properties

1547

1621

///

1548

  /// Returns true when there are not parallel edges in the graph.

1622

  /// \brief Check whether the given graph contains no parallel arcs/edges.

1623

///

1624

  /// This function returns \c true if there are no parallel arcs/edges in

1625

  /// the given graph. It works for both directed and undirected graphs.

1549

1626

  template <typename Graph>

1550

1627

  bool parallelFree(const Graph& graph) {

1551

1628

    typename Graph::template NodeMap<int> reached(graph, 0);

1552

1629

    int cnt = 1;

1553

1630

    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {

1554

1631

      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {

1555

1632

        if (reached[graph.target(a)] == cnt) return false;

1556

1633

        reached[graph.target(a)] = cnt;

      ++cnt;

    return true;

  /// \brief Returns true when there are not loop edges and parallel

1564

  /// edges in the graph.

1640

  /// \ingroup graph_properties

1565

1641

///

1566

  /// Returns true when there are not loop edges and parallel edges in

1567

  /// the graph.

1642

  /// \brief Check whether the given graph is simple.

1643

///

1644

  /// This function returns \c true if the given graph is simple, i.e.

1645

  /// it contains no loop arcs/edges and no parallel arcs/edges.

1646

  /// The function works for both directed and undirected graphs.

1647

  /// \see loopFree(), parallelFree()

1568

1648

  template <typename Graph>

1569

1649

  bool simpleGraph(const Graph& graph) {

1570

1650

    typename Graph::template NodeMap<int> reached(graph, 0);

1571

1651

    int cnt = 1;

1572

1652

    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {

1573

1653

      reached[n] = cnt;

1574

1654

      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {

1575

1655

        if (reached[graph.target(a)] == cnt) return false;

1576

1656

        reached[graph.target(a)] = cnt;

      ++cnt;

1579

1659

RhodeCode

Login to your account

@@ -235,28 +235,28 @@
 		    ///
 		    ///\warning This incrementation returns an \c Arc (which converts to
 		    ///an \c Edge), not an \ref EulerIt, as one may expect.
 		    Arc operator++(int)
+		    {
 		      Arc e=*this;
 		      ++(*this);
 		      return e;
+		    }
 		  };
-		  ///Check if the given graph is \e Eulerian
 		  ///Check if the given graph is Eulerian
 		  /// \ingroup graph_properties
-		  ///This function checks if the given graph is \e Eulerian.
 		  ///This function checks if the given graph is Eulerian.
 		  ///It works for both directed and undirected graphs.
 		  ///
 		  ///By definition, a digraph is called \e Eulerian if
 		  ///and only if it is connected and the number of incoming and outgoing
 		  ///arcs are the same for each node.
 		  ///Similarly, an undirected graph is called \e Eulerian if
 		  ///and only if it is connected and the number of incident edges is even
 		  ///for each node.
 		  ///
 		  ///\note There are (di)graphs that are not Eulerian, but still have an
 		  /// Euler tour, since they may contain isolated nodes.
 		  ///