LEMON/LEMON-official Changeset - r478:5a1e9fdcfd3a

@@ -12,25 +12,25 @@

12

13

 * This software is provided "AS IS" with no warranty of any kind,

14

 * express or implied, and with no claim as to its suitability for any

15

 * purpose.

16

17

*/

18

19

#ifndef LEMON_ADAPTORS_H

20

#define LEMON_ADAPTORS_H

21

22

/// \ingroup graph_adaptors

23

/// \file

24

/// \brief Several graph adaptors

24

/// \brief Adaptor classes for digraphs and graphs

25

///

26

/// This file contains several useful adaptors for digraphs and graphs.

27

28

#include <lemon/core.h>

29

#include <lemon/maps.h>

30

#include <lemon/bits/variant.h>

31

32

#include <lemon/bits/graph_adaptor_extender.h>

33

#include <lemon/tolerance.h>

34

35

#include <algorithm>

36

...

@@ -61,39 +61,39 @@

61

62

    void next(Node& i) const { _digraph->next(i); }

63

    void next(Arc& i) const { _digraph->next(i); }

64

    void nextIn(Arc& i) const { _digraph->nextIn(i); }

65

    void nextOut(Arc& i) const { _digraph->nextOut(i); }

66

67

    Node source(const Arc& a) const { return _digraph->source(a); }

68

    Node target(const Arc& a) const { return _digraph->target(a); }

69

70

    typedef NodeNumTagIndicator<Digraph> NodeNumTag;

71

    int nodeNum() const { return _digraph->nodeNum(); }

72

73

    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;

73

    typedef ArcNumTagIndicator<Digraph> ArcNumTag;

74

    int arcNum() const { return _digraph->arcNum(); }

75

76

    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;

77

    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {

76

    typedef FindArcTagIndicator<Digraph> FindArcTag;

77

    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {

78

      return _digraph->findArc(u, v, prev);

79

80

81

    Node addNode() { return _digraph->addNode(); }

82

    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }

83

84

    void erase(const Node& n) const { _digraph->erase(n); }

85

    void erase(const Arc& a) const { _digraph->erase(a); }

86

87

    void clear() const { _digraph->clear(); }

84

    void erase(const Node& n) { _digraph->erase(n); }

85

    void erase(const Arc& a) { _digraph->erase(a); }

86

87

    void clear() { _digraph->clear(); }

88

89

    int id(const Node& n) const { return _digraph->id(n); }

90

    int id(const Arc& a) const { return _digraph->id(a); }

91

92

    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }

93

    Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }

94

95

    int maxNodeId() const { return _digraph->maxNodeId(); }

96

    int maxArcId() const { return _digraph->maxArcId(); }

97

98

    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;

99

    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }

...

@@ -189,33 +189,39 @@

189

    void nextOut(Arc& i) const { _graph->nextOut(i); }

190

    void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }

191

192

    Node u(const Edge& e) const { return _graph->u(e); }

193

    Node v(const Edge& e) const { return _graph->v(e); }

194

195

    Node source(const Arc& a) const { return _graph->source(a); }

196

    Node target(const Arc& a) const { return _graph->target(a); }

197

198

    typedef NodeNumTagIndicator<Graph> NodeNumTag;

199

    int nodeNum() const { return _graph->nodeNum(); }

200

201

    typedef ArcNumTagIndicator<Graph> ArcNumTag;

202

    int arcNum() const { return _graph->arcNum(); }

203

201

204

    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

202

    int arcNum() const { return _graph->arcNum(); }

203

205

    int edgeNum() const { return _graph->edgeNum(); }

204

206

205

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

206

    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {

207

    typedef FindArcTagIndicator<Graph> FindArcTag;

208

    Arc findArc(const Node& u, const Node& v,

209

                const Arc& prev = INVALID) const {

207

210

      return _graph->findArc(u, v, prev);

208

211

209

    Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {

212

213

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

214

    Edge findEdge(const Node& u, const Node& v,

215

                  const Edge& prev = INVALID) const {

210

216

      return _graph->findEdge(u, v, prev);

    Node addNode() { return _graph->addNode(); }

214

220

    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }

    void erase(const Node& i) { _graph->erase(i); }

217

223

    void erase(const Edge& i) { _graph->erase(i); }

    void clear() { _graph->clear(); }

    bool direction(const Arc& a) const { return _graph->direction(a); }

...

@@ -321,69 +327,84 @@

    void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }

323

329

    void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }

    void nextIn(Arc& a) const { Parent::nextOut(a); }

326

332

    void nextOut(Arc& a) const { Parent::nextIn(a); }

    Node source(const Arc& a) const { return Parent::target(a); }

329

335

    Node target(const Arc& a) const { return Parent::source(a); }

    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }

332

338

333

    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;

339

    typedef FindArcTagIndicator<Digraph> FindArcTag;

334

340

    Arc findArc(const Node& u, const Node& v,

335

                const Arc& prev = INVALID) {

341

                const Arc& prev = INVALID) const {

336

342

      return Parent::findArc(v, u, prev);

};

  /// \ingroup graph_adaptors

342

348

///

343

  /// \brief A digraph adaptor which reverses the orientation of the arcs.

349

  /// \brief Adaptor class for reversing the orientation of the arcs in

350

  /// a digraph.

344

351

///

345

  /// ReverseDigraph reverses the arcs in the adapted digraph. The

346

  /// SubDigraph is conform to the \ref concepts::Digraph

347

  /// "Digraph concept".

352

  /// ReverseDigraph can be used for reversing the arcs in a digraph.

353

  /// It conforms to the \ref concepts::Digraph "Digraph" concept.

348

354

///

349

  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph

350

  /// "Digraph concept". The type can be specified to be const.

351

  template<typename _Digraph>

355

  /// The adapted digraph can also be modified through this adaptor

356

  /// by adding or removing nodes or arcs, unless the \c GR template

357

  /// parameter is set to be \c const.

358

///

359

  /// \tparam GR The type of the adapted digraph.

360

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

361

  /// It can also be specified to be \c const.

362

///

363

  /// \note The \c Node and \c Arc types of this adaptor and the adapted

364

  /// digraph are convertible to each other.

365

  template<typename GR>

366

#ifdef DOXYGEN

367

  class ReverseDigraph {

368

#else

352

369

  class ReverseDigraph :

353

    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {

370

    public DigraphAdaptorExtender<ReverseDigraphBase<GR> > {

371

#endif

354

372

  public:

355

    typedef _Digraph Digraph;

356

    typedef DigraphAdaptorExtender<

357

      ReverseDigraphBase<_Digraph> > Parent;

373

    /// The type of the adapted digraph.

374

    typedef GR Digraph;

375

    typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent;

358

376

  protected:

359

377

    ReverseDigraph() { }

360

378

  public:

    /// \brief Constructor

363

381

///

364

    /// Creates a reverse digraph adaptor for the given digraph

382

    /// Creates a reverse digraph adaptor for the given digraph.

365

383

    explicit ReverseDigraph(Digraph& digraph) {

366

384

      Parent::setDigraph(digraph);

};

369

387

370

  /// \brief Just gives back a reverse digraph adaptor

388

  /// \brief Returns a read-only ReverseDigraph adaptor

371

389

///

372

  /// Just gives back a reverse digraph adaptor

373

  template<typename Digraph>

374

  ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {

375

    return ReverseDigraph<const Digraph>(digraph);

390

  /// This function just returns a read-only \ref ReverseDigraph adaptor.

391

  /// \ingroup graph_adaptors

392

  /// \relates ReverseDigraph

393

  template<typename GR>

394

  ReverseDigraph<const GR> reverseDigraph(const GR& digraph) {

395

    return ReverseDigraph<const GR>(digraph);

  template <typename _Digraph, typename _NodeFilterMap,

379

400

            typename _ArcFilterMap, bool _checked = true>

380

401

  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {

381

402

  public:

382

403

    typedef _Digraph Digraph;

383

404

    typedef _NodeFilterMap NodeFilterMap;

384

405

    typedef _ArcFilterMap ArcFilterMap;

    typedef SubDigraphBase Adaptor;

387

408

    typedef DigraphAdaptorBase<_Digraph> Parent;

388

409

  protected:

389

410

    NodeFilterMap* _node_filter;

...

@@ -448,39 +469,36 @@

448

469

      while (i != INVALID && (!(*_arc_filter)[i]

449

470

                              || !(*_node_filter)[Parent::source(i)]))

450

471

        Parent::nextIn(i);

    void nextOut(Arc& i) const {

454

475

      Parent::nextOut(i);

455

476

      while (i != INVALID && (!(*_arc_filter)[i]

456

477

                              || !(*_node_filter)[Parent::target(i)]))

457

478

        Parent::nextOut(i);

    void hide(const Node& n) const { _node_filter->set(n, false); }

461

    void hide(const Arc& a) const { _arc_filter->set(a, false); }

462

463

    void unHide(const Node& n) const { _node_filter->set(n, true); }

464

    void unHide(const Arc& a) const { _arc_filter->set(a, true); }

465

466

    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }

467

    bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }

481

    void status(const Node& n, bool v) const { _node_filter->set(n, v); }

482

    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }

483

484

    bool status(const Node& n) const { return (*_node_filter)[n]; }

485

    bool status(const Arc& a) const { return (*_arc_filter)[a]; }

    typedef False NodeNumTag;

470

    typedef False EdgeNumTag;

471

472

    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;

488

    typedef False ArcNumTag;

489

490

    typedef FindArcTagIndicator<Digraph> FindArcTag;

473

491

    Arc findArc(const Node& source, const Node& target,

474

                const Arc& prev = INVALID) {

492

                const Arc& prev = INVALID) const {

475

493

      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {

476

494

        return INVALID;

      Arc arc = Parent::findArc(source, target, prev);

479

497

      while (arc != INVALID && !(*_arc_filter)[arc]) {

480

498

        arc = Parent::findArc(source, target, arc);

      return arc;

    template <typename _Value>

486

504

    class NodeMap : public SubMapExtender<Adaptor,

...

@@ -591,39 +609,36 @@

591

609

      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);

    void nextIn(Arc& i) const {

594

612

      Parent::nextIn(i);

595

613

      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);

    void nextOut(Arc& i) const {

599

617

      Parent::nextOut(i);

600

618

      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);

    void hide(const Node& n) const { _node_filter->set(n, false); }

604

    void hide(const Arc& e) const { _arc_filter->set(e, false); }

605

606

    void unHide(const Node& n) const { _node_filter->set(n, true); }

607

    void unHide(const Arc& e) const { _arc_filter->set(e, true); }

608

609

    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }

610

    bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }

621

    void status(const Node& n, bool v) const { _node_filter->set(n, v); }

622

    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }

623

624

    bool status(const Node& n) const { return (*_node_filter)[n]; }

625

    bool status(const Arc& a) const { return (*_arc_filter)[a]; }

    typedef False NodeNumTag;

613

    typedef False EdgeNumTag;

614

615

    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;

628

    typedef False ArcNumTag;

629

630

    typedef FindArcTagIndicator<Digraph> FindArcTag;

616

631

    Arc findArc(const Node& source, const Node& target,

617

                const Arc& prev = INVALID) {

632

                const Arc& prev = INVALID) const {

618

633

      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {

619

634

        return INVALID;

      Arc arc = Parent::findArc(source, target, prev);

622

637

      while (arc != INVALID && !(*_arc_filter)[arc]) {

623

638

        arc = Parent::findArc(source, target, arc);

      return arc;

    template <typename _Value>

629

644

    class NodeMap : public SubMapExtender<Adaptor,

...

@@ -670,161 +685,194 @@

      template <typename CMap>

672

687

      ArcMap& operator=(const CMap& cmap) {

673

688

        MapParent::operator=(cmap);

674

689

        return *this;

};

};

  /// \ingroup graph_adaptors

681

696

///

682

  /// \brief An adaptor for hiding nodes and arcs in a digraph

697

  /// \brief Adaptor class for hiding nodes and arcs in a digraph

683

698

///

684

  /// SubDigraph hides nodes and arcs in a digraph. A bool node map

685

  /// and a bool arc map must be specified, which define the filters

686

  /// for nodes and arcs. Just the nodes and arcs with true value are

687

  /// shown in the subdigraph. The SubDigraph is conform to the \ref

688

  /// concepts::Digraph "Digraph concept". If the \c _checked parameter

689

  /// is true, then the arcs incident to filtered nodes are also

690

  /// filtered out.

699

  /// SubDigraph can be used for hiding nodes and arcs in a digraph.

700

  /// A \c bool node map and a \c bool arc map must be specified, which

701

  /// define the filters for nodes and arcs.

702

  /// Only the nodes and arcs with \c true filter value are

703

  /// shown in the subdigraph. The arcs that are incident to hidden

704

  /// nodes are also filtered out.

705

  /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.

691

706

///

692

  /// \tparam _Digraph It must be conform to the \ref

693

  /// concepts::Digraph "Digraph concept". The type can be specified

694

  /// to const.

695

  /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.

696

  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.

697

  /// \tparam _checked If the parameter is false then the arc filtering

698

  /// is not checked with respect to node filter. Otherwise, each arc

699

  /// is automatically filtered, which is incident to a filtered node.

707

  /// The adapted digraph can also be modified through this adaptor

708

  /// by adding or removing nodes or arcs, unless the \c GR template

709

  /// parameter is set to be \c const.

710

///

711

  /// \tparam GR The type of the adapted digraph.

712

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

713

  /// It can also be specified to be \c const.

714

  /// \tparam NF The type of the node filter map.

715

  /// It must be a \c bool (or convertible) node map of the

716

  /// adapted digraph. The default type is

717

  /// \ref concepts::Digraph::NodeMap "GR::NodeMap<bool>".

718

  /// \tparam AF The type of the arc filter map.

719

  /// It must be \c bool (or convertible) arc map of the

720

  /// adapted digraph. The default type is

721

  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".

722

///

723

  /// \note The \c Node and \c Arc types of this adaptor and the adapted

724

  /// digraph are convertible to each other.

700

725

///

701

726

  /// \see FilterNodes

702

727

  /// \see FilterArcs

703

  template<typename _Digraph,

704

           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,

705

           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,

706

           bool _checked = true>

707

  class SubDigraph

708

    : public DigraphAdaptorExtender<

709

      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {

728

#ifdef DOXYGEN

729

  template<typename GR, typename NF, typename AF>

730

  class SubDigraph {

731

#else

732

  template<typename GR,

733

           typename NF = typename GR::template NodeMap<bool>,

734

           typename AF = typename GR::template ArcMap<bool> >

735

  class SubDigraph :

736

    public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > {

737

#endif

710

738

  public:

711

    typedef _Digraph Digraph;

712

    typedef _NodeFilterMap NodeFilterMap;

713

    typedef _ArcFilterMap ArcFilterMap;

714

715

    typedef DigraphAdaptorExtender<

716

      SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >

717

    Parent;

739

    /// The type of the adapted digraph.

740

    typedef GR Digraph;

741

    /// The type of the node filter map.

742

    typedef NF NodeFilterMap;

743

    /// The type of the arc filter map.

744

    typedef AF ArcFilterMap;

745

746

    typedef DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> >

747

      Parent;

    typedef typename Parent::Node Node;

720

750

    typedef typename Parent::Arc Arc;

  protected:

723

753

    SubDigraph() { }

724

754

  public:

    /// \brief Constructor

727

757

///

728

    /// Creates a subdigraph for the given digraph with

729

    /// given node and arc map filters.

758

    /// Creates a subdigraph for the given digraph with the

759

    /// given node and arc filter maps.

730

760

    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,

731

761

               ArcFilterMap& arc_filter) {

732

762

      setDigraph(digraph);

733

763

      setNodeFilterMap(node_filter);

734

764

      setArcFilterMap(arc_filter);

    /// \brief Hides the node of the graph

767

    /// \brief Sets the status of the given node

738

768

///

739

    /// This function hides \c n in the digraph, i.e. the iteration

740

    /// jumps over it. This is done by simply setting the value of \c n

741

    /// to be false in the corresponding node-map.

742

    void hide(const Node& n) const { Parent::hide(n); }

743

744

    /// \brief Hides the arc of the graph

769

    /// This function sets the status of the given node.

770

    /// It is done by simply setting the assigned value of \c n

771

    /// to \c v in the node filter map.

772

    void status(const Node& n, bool v) const { Parent::status(n, v); }

773

774

    /// \brief Sets the status of the given arc

745

775

///

746

    /// This function hides \c a in the digraph, i.e. the iteration

747

    /// jumps over it. This is done by simply setting the value of \c a

748

    /// to be false in the corresponding arc-map.

749

    void hide(const Arc& a) const { Parent::hide(a); }

750

751

    /// \brief Unhides the node of the graph

776

    /// This function sets the status of the given arc.

777

    /// It is done by simply setting the assigned value of \c a

778

    /// to \c v in the arc filter map.

779

    void status(const Arc& a, bool v) const { Parent::status(a, v); }

780

781

    /// \brief Returns the status of the given node

752

782

///

753

    /// The value of \c n is set to be true in the node-map which stores

754

    /// hide information. If \c n was hidden previuosly, then it is shown

755

    /// again

756

    void unHide(const Node& n) const { Parent::unHide(n); }

757

758

    /// \brief Unhides the arc of the graph

783

    /// This function returns the status of the given node.

784

    /// It is \c true if the given node is enabled (i.e. not hidden).

785

    bool status(const Node& n) const { return Parent::status(n); }

786

787

    /// \brief Returns the status of the given arc

759

788

///

760

    /// The value of \c a is set to be true in the arc-map which stores

761

    /// hide information. If \c a was hidden previuosly, then it is shown

762

    /// again

763

    void unHide(const Arc& a) const { Parent::unHide(a); }

764

765

    /// \brief Returns true if \c n is hidden.

789

    /// This function returns the status of the given arc.

790

    /// It is \c true if the given arc is enabled (i.e. not hidden).

791

    bool status(const Arc& a) const { return Parent::status(a); }

792

793

    /// \brief Disables the given node

766

794

///

767

    /// Returns true if \c n is hidden.

795

    /// This function disables the given node in the subdigraph,

796

    /// so the iteration jumps over it.

797

    /// It is the same as \ref status() "status(n, false)".

798

    void disable(const Node& n) const { Parent::status(n, false); }

799

800

    /// \brief Disables the given arc

768

801

///

769

    bool hidden(const Node& n) const { return Parent::hidden(n); }

770

771

    /// \brief Returns true if \c a is hidden.

802

    /// This function disables the given arc in the subdigraph,

803

    /// so the iteration jumps over it.

804

    /// It is the same as \ref status() "status(a, false)".

805

    void disable(const Arc& a) const { Parent::status(a, false); }

806

807

    /// \brief Enables the given node

772

808

///

773

    /// Returns true if \c a is hidden.

809

    /// This function enables the given node in the subdigraph.

810

    /// It is the same as \ref status() "status(n, true)".

811

    void enable(const Node& n) const { Parent::status(n, true); }

812

813

    /// \brief Enables the given arc

774

814

///

775

    bool hidden(const Arc& a) const { return Parent::hidden(a); }

815

    /// This function enables the given arc in the subdigraph.

816

    /// It is the same as \ref status() "status(a, true)".

817

    void enable(const Arc& a) const { Parent::status(a, true); }

};

778

820

779

  /// \brief Just gives back a subdigraph

821

  /// \brief Returns a read-only SubDigraph adaptor

780

822

///

781

  /// Just gives back a subdigraph

782

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

783

  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>

784

  subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {

785

    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>

786

      (digraph, nfm, afm);

823

  /// This function just returns a read-only \ref SubDigraph adaptor.

824

  /// \ingroup graph_adaptors

825

  /// \relates SubDigraph

826

  template<typename GR, typename NF, typename AF>

827

  SubDigraph<const GR, NF, AF>

828

  subDigraph(const GR& digraph,

829

             NF& node_filter_map, AF& arc_filter_map) {

830

    return SubDigraph<const GR, NF, AF>

831

      (digraph, node_filter_map, arc_filter_map);

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

790

  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>

791

  subDigraph(const Digraph& digraph,

792

             const NodeFilterMap& nfm, ArcFilterMap& afm) {

793

    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>

794

      (digraph, nfm, afm);

834

  template<typename GR, typename NF, typename AF>

835

  SubDigraph<const GR, const NF, AF>

836

  subDigraph(const GR& digraph,

837

             const NF& node_filter_map, AF& arc_filter_map) {

838

    return SubDigraph<const GR, const NF, AF>

839

      (digraph, node_filter_map, arc_filter_map);

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

798

  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>

799

  subDigraph(const Digraph& digraph,

800

             NodeFilterMap& nfm, const ArcFilterMap& afm) {

801

    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>

802

      (digraph, nfm, afm);

842

  template<typename GR, typename NF, typename AF>

843

  SubDigraph<const GR, NF, const AF>

844

  subDigraph(const GR& digraph,

845

             NF& node_filter_map, const AF& arc_filter_map) {

846

    return SubDigraph<const GR, NF, const AF>

847

      (digraph, node_filter_map, arc_filter_map);

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

806

  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>

807

  subDigraph(const Digraph& digraph,

808

             const NodeFilterMap& nfm, const ArcFilterMap& afm) {

809

    return SubDigraph<const Digraph, const NodeFilterMap,

810

      const ArcFilterMap>(digraph, nfm, afm);

850

  template<typename GR, typename NF, typename AF>

851

  SubDigraph<const GR, const NF, const AF>

852

  subDigraph(const GR& digraph,

853

             const NF& node_filter_map, const AF& arc_filter_map) {

854

    return SubDigraph<const GR, const NF, const AF>

855

      (digraph, node_filter_map, arc_filter_map);

  template <typename _Graph, typename NodeFilterMap,

815

            typename EdgeFilterMap, bool _checked = true>

859

  template <typename _Graph, typename _NodeFilterMap,

860

            typename _EdgeFilterMap, bool _checked = true>

816

861

  class SubGraphBase : public GraphAdaptorBase<_Graph> {

817

862

  public:

818

863

    typedef _Graph Graph;

864

    typedef _NodeFilterMap NodeFilterMap;

865

    typedef _EdgeFilterMap EdgeFilterMap;

866

819

867

    typedef SubGraphBase Adaptor;

820

868

    typedef GraphAdaptorBase<_Graph> Parent;

821

869

  protected:

    NodeFilterMap* _node_filter_map;

824

872

    EdgeFilterMap* _edge_filter_map;

    SubGraphBase()

827

875

      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }

    void setNodeFilterMap(NodeFilterMap& node_filter_map) {

830

878

      _node_filter_map=&node_filter_map;

...

@@ -916,50 +964,50 @@

916

964

                            || !(*_node_filter_map)[Parent::target(i)]))

917

965

        Parent::nextOut(i);

    void nextInc(Edge& i, bool& d) const {

921

969

      Parent::nextInc(i, d);

922

970

      while (i!=INVALID && (!(*_edge_filter_map)[i]

923

971

                            || !(*_node_filter_map)[Parent::u(i)]

924

972

                            || !(*_node_filter_map)[Parent::v(i)]))

925

973

        Parent::nextInc(i, d);

    void hide(const Node& n) const { _node_filter_map->set(n, false); }

929

    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }

930

931

    void unHide(const Node& n) const { _node_filter_map->set(n, true); }

932

    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }

933

934

    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }

935

    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }

976

    void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }

977

    void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }

978

979

    bool status(const Node& n) const { return (*_node_filter_map)[n]; }

980

    bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }

    typedef False NodeNumTag;

983

    typedef False ArcNumTag;

938

984

    typedef False EdgeNumTag;

939

985

940

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

986

    typedef FindArcTagIndicator<Graph> FindArcTag;

941

987

    Arc findArc(const Node& u, const Node& v,

942

                const Arc& prev = INVALID) {

988

                const Arc& prev = INVALID) const {

943

989

      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {

944

990

        return INVALID;

      Arc arc = Parent::findArc(u, v, prev);

947

993

      while (arc != INVALID && !(*_edge_filter_map)[arc]) {

948

994

        arc = Parent::findArc(u, v, arc);

      return arc;

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

952

1000

    Edge findEdge(const Node& u, const Node& v,

953

                  const Edge& prev = INVALID) {

1001

                  const Edge& prev = INVALID) const {

954

1002

      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {

955

1003

        return INVALID;

      Edge edge = Parent::findEdge(u, v, prev);

958

1006

      while (edge != INVALID && !(*_edge_filter_map)[edge]) {

959

1007

        edge = Parent::findEdge(u, v, edge);

      return edge;

    template <typename _Value>

965

1013

    class NodeMap : public SubMapExtender<Adaptor,

...

@@ -1030,29 +1078,32 @@

1030

1078

        return operator=<EdgeMap>(cmap);

      template <typename CMap>

1034

1082

      EdgeMap& operator=(const CMap& cmap) {

1035

1083

        MapParent::operator=(cmap);

1036

1084

        return *this;

};

};

1041

1089

1042

  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>

1043

  class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>

1090

  template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>

1091

  class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>

1044

1092

    : public GraphAdaptorBase<_Graph> {

1045

1093

  public:

1046

1094

    typedef _Graph Graph;

1095

    typedef _NodeFilterMap NodeFilterMap;

1096

    typedef _EdgeFilterMap EdgeFilterMap;

1097

1047

1098

    typedef SubGraphBase Adaptor;

1048

1099

    typedef GraphAdaptorBase<_Graph> Parent;

1049

1100

  protected:

1050

1101

    NodeFilterMap* _node_filter_map;

1051

1102

    EdgeFilterMap* _edge_filter_map;

1052

1103

    SubGraphBase() : Parent(),

1053

1104

                     _node_filter_map(0), _edge_filter_map(0) { }

    void setNodeFilterMap(NodeFilterMap& node_filter_map) {

1056

1107

      _node_filter_map=&node_filter_map;

    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {

...

@@ -1112,47 +1163,47 @@

1112

1163

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);

    void nextOut(Arc& i) const {

1116

1167

      Parent::nextOut(i);

1117

1168

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);

    void nextInc(Edge& i, bool& d) const {

1120

1171

      Parent::nextInc(i, d);

1121

1172

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);

    void hide(const Node& n) const { _node_filter_map->set(n, false); }

1125

    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }

1126

1127

    void unHide(const Node& n) const { _node_filter_map->set(n, true); }

1128

    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }

1129

1130

    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }

1131

    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }

1175

    void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }

1176

    void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }

1177

1178

    bool status(const Node& n) const { return (*_node_filter_map)[n]; }

1179

    bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }

    typedef False NodeNumTag;

1182

    typedef False ArcNumTag;

1134

1183

    typedef False EdgeNumTag;

1135

1184

1136

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

1185

    typedef FindArcTagIndicator<Graph> FindArcTag;

1137

1186

    Arc findArc(const Node& u, const Node& v,

1138

                const Arc& prev = INVALID) {

1187

                const Arc& prev = INVALID) const {

1139

1188

      Arc arc = Parent::findArc(u, v, prev);

1140

1189

      while (arc != INVALID && !(*_edge_filter_map)[arc]) {

1141

1190

        arc = Parent::findArc(u, v, arc);

      return arc;

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

1145

1196

    Edge findEdge(const Node& u, const Node& v,

1146

                  const Edge& prev = INVALID) {

1197

                  const Edge& prev = INVALID) const {

1147

1198

      Edge edge = Parent::findEdge(u, v, prev);

1148

1199

      while (edge != INVALID && !(*_edge_filter_map)[edge]) {

1149

1200

        edge = Parent::findEdge(u, v, edge);

      return edge;

    template <typename _Value>

1155

1206

    class NodeMap : public SubMapExtender<Adaptor,

1156

1207

      typename Parent::template NodeMap<_Value> > {

1157

1208

    public:

1158

1209

      typedef _Value Value;

...

@@ -1222,449 +1273,565 @@

      template <typename CMap>

1224

1275

      EdgeMap& operator=(const CMap& cmap) {

1225

1276

        MapParent::operator=(cmap);

1226

1277

        return *this;

};

};

  /// \ingroup graph_adaptors

1233

1284

///

1234

  /// \brief A graph adaptor for hiding nodes and edges in an

1235

  /// undirected graph.

1285

  /// \brief Adaptor class for hiding nodes and edges in an undirected

1286

  /// graph.

1236

1287

///

1237

  /// SubGraph hides nodes and edges in a graph. A bool node map and a

1238

  /// bool edge map must be specified, which define the filters for

1239

  /// nodes and edges. Just the nodes and edges with true value are

1240

  /// shown in the subgraph. The SubGraph is conform to the \ref

1241

  /// concepts::Graph "Graph concept". If the \c _checked parameter is

1242

  /// true, then the edges incident to filtered nodes are also

1243

  /// filtered out.

1288

  /// SubGraph can be used for hiding nodes and edges in a graph.

1289

  /// A \c bool node map and a \c bool edge map must be specified, which

1290

  /// define the filters for nodes and edges.

1291

  /// Only the nodes and edges with \c true filter value are

1292

  /// shown in the subgraph. The edges that are incident to hidden

1293

  /// nodes are also filtered out.

1294

  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.

1244

1295

///

1245

  /// \tparam _Graph It must be conform to the \ref

1246

  /// concepts::Graph "Graph concept". The type can be specified

1247

  /// to const.

1248

  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.

1249

  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.

1250

  /// \tparam _checked If the parameter is false then the edge filtering

1251

  /// is not checked with respect to node filter. Otherwise, each edge

1252

  /// is automatically filtered, which is incident to a filtered node.

1296

  /// The adapted graph can also be modified through this adaptor

1297

  /// by adding or removing nodes or edges, unless the \c GR template

1298

  /// parameter is set to be \c const.

1299

///

1300

  /// \tparam GR The type of the adapted graph.

1301

  /// It must conform to the \ref concepts::Graph "Graph" concept.

1302

  /// It can also be specified to be \c const.

1303

  /// \tparam NF The type of the node filter map.

1304

  /// It must be a \c bool (or convertible) node map of the

1305

  /// adapted graph. The default type is

1306

  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".

1307

  /// \tparam EF The type of the edge filter map.

1308

  /// It must be a \c bool (or convertible) edge map of the

1309

  /// adapted graph. The default type is

1310

  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".

1311

///

1312

  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the

1313

  /// adapted graph are convertible to each other.

1253

1314

///

1254

1315

  /// \see FilterNodes

1255

1316

  /// \see FilterEdges

1256

  template<typename _Graph, typename NodeFilterMap,

1257

           typename EdgeFilterMap, bool _checked = true>

1258

  class SubGraph

1259

    : public GraphAdaptorExtender<

1260

      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {

1317

#ifdef DOXYGEN

1318

  template<typename GR, typename NF, typename EF>

1319

  class SubGraph {

1320

#else

1321

  template<typename GR,

1322

           typename NF = typename GR::template NodeMap<bool>,

1323

           typename EF = typename GR::template EdgeMap<bool> >

1324

  class SubGraph :

1325

    public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > {

1326

#endif

1261

1327

  public:

1262

    typedef _Graph Graph;

1263

    typedef GraphAdaptorExtender<

1264

      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;

1328

    /// The type of the adapted graph.

1329

    typedef GR Graph;

1330

    /// The type of the node filter map.

1331

    typedef NF NodeFilterMap;

1332

    /// The type of the edge filter map.

1333

    typedef EF EdgeFilterMap;

1334

1335

    typedef GraphAdaptorExtender< SubGraphBase<GR, NF, EF, true> >

1336

      Parent;

    typedef typename Parent::Node Node;

1267

1339

    typedef typename Parent::Edge Edge;

  protected:

1270

1342

    SubGraph() { }

1271

1343

  public:

    /// \brief Constructor

1274

1346

///

1275

    /// Creates a subgraph for the given graph with given node and

1276

    /// edge map filters.

1277

    SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,

1347

    /// Creates a subgraph for the given graph with the given node

1348

    /// and edge filter maps.

1349

    SubGraph(Graph& graph, NodeFilterMap& node_filter_map,

1278

1350

             EdgeFilterMap& edge_filter_map) {

1279

      setGraph(_graph);

1351

      setGraph(graph);

1280

1352

      setNodeFilterMap(node_filter_map);

1281

1353

      setEdgeFilterMap(edge_filter_map);

    /// \brief Hides the node of the graph

1356

    /// \brief Sets the status of the given node

1285

1357

///

1286

    /// This function hides \c n in the graph, i.e. the iteration

1287

    /// jumps over it. This is done by simply setting the value of \c n

1288

    /// to be false in the corresponding node-map.

1289

    void hide(const Node& n) const { Parent::hide(n); }

1290

1291

    /// \brief Hides the edge of the graph

1358

    /// This function sets the status of the given node.

1359

    /// It is done by simply setting the assigned value of \c n

1360

    /// to \c v in the node filter map.

1361

    void status(const Node& n, bool v) const { Parent::status(n, v); }

1362

1363

    /// \brief Sets the status of the given edge

1292

1364

///

1293

    /// This function hides \c e in the graph, i.e. the iteration

1294

    /// jumps over it. This is done by simply setting the value of \c e

1295

    /// to be false in the corresponding edge-map.

1296

    void hide(const Edge& e) const { Parent::hide(e); }

1297

1298

    /// \brief Unhides the node of the graph

1365

    /// This function sets the status of the given edge.

1366

    /// It is done by simply setting the assigned value of \c e

1367

    /// to \c v in the edge filter map.

1368

    void status(const Edge& e, bool v) const { Parent::status(e, v); }

1369

1370

    /// \brief Returns the status of the given node

1299

1371

///

1300

    /// The value of \c n is set to be true in the node-map which stores

1301

    /// hide information. If \c n was hidden previuosly, then it is shown

1302

    /// again

1303

    void unHide(const Node& n) const { Parent::unHide(n); }

1304

1305

    /// \brief Unhides the edge of the graph

1372

    /// This function returns the status of the given node.

1373

    /// It is \c true if the given node is enabled (i.e. not hidden).

1374

    bool status(const Node& n) const { return Parent::status(n); }

1375

1376

    /// \brief Returns the status of the given edge

1306

1377

///

1307

    /// The value of \c e is set to be true in the edge-map which stores

1308

    /// hide information. If \c e was hidden previuosly, then it is shown

1309

    /// again

1310

    void unHide(const Edge& e) const { Parent::unHide(e); }

1311

1312

    /// \brief Returns true if \c n is hidden.

1378

    /// This function returns the status of the given edge.

1379

    /// It is \c true if the given edge is enabled (i.e. not hidden).

1380

    bool status(const Edge& e) const { return Parent::status(e); }

1381

1382

    /// \brief Disables the given node

1313

1383

///

1314

    /// Returns true if \c n is hidden.

1384

    /// This function disables the given node in the subdigraph,

1385

    /// so the iteration jumps over it.

1386

    /// It is the same as \ref status() "status(n, false)".

1387

    void disable(const Node& n) const { Parent::status(n, false); }

1388

1389

    /// \brief Disables the given edge

1315

1390

///

1316

    bool hidden(const Node& n) const { return Parent::hidden(n); }

1317

1318

    /// \brief Returns true if \c e is hidden.

1391

    /// This function disables the given edge in the subgraph,

1392

    /// so the iteration jumps over it.

1393

    /// It is the same as \ref status() "status(e, false)".

1394

    void disable(const Edge& e) const { Parent::status(e, false); }

1395

1396

    /// \brief Enables the given node

1319

1397

///

1320

    /// Returns true if \c e is hidden.

1398

    /// This function enables the given node in the subdigraph.

1399

    /// It is the same as \ref status() "status(n, true)".

1400

    void enable(const Node& n) const { Parent::status(n, true); }

1401

1402

    /// \brief Enables the given edge

1321

1403

///

1322

    bool hidden(const Edge& e) const { return Parent::hidden(e); }

1404

    /// This function enables the given edge in the subgraph.

1405

    /// It is the same as \ref status() "status(e, true)".

1406

    void enable(const Edge& e) const { Parent::status(e, true); }

1407

1323

1408

};

1324

1409

1325

  /// \brief Just gives back a subgraph

1410

  /// \brief Returns a read-only SubGraph adaptor

1326

1411

///

1327

  /// Just gives back a subgraph

1328

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

1329

  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>

1330

  subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {

1331

    return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);

1412

  /// This function just returns a read-only \ref SubGraph adaptor.

1413

  /// \ingroup graph_adaptors

1414

  /// \relates SubGraph

1415

  template<typename GR, typename NF, typename EF>

1416

  SubGraph<const GR, NF, EF>

1417

  subGraph(const GR& graph,

1418

           NF& node_filter_map, EF& edge_filter_map) {

1419

    return SubGraph<const GR, NF, EF>

1420

      (graph, node_filter_map, edge_filter_map);

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

1335

  SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>

1336

  subGraph(const Graph& graph,

1337

           const NodeFilterMap& nfm, ArcFilterMap& efm) {

1338

    return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>

1339

      (graph, nfm, efm);

1423

  template<typename GR, typename NF, typename EF>

1424

  SubGraph<const GR, const NF, EF>

1425

  subGraph(const GR& graph,

1426

           const NF& node_filter_map, EF& edge_filter_map) {

1427

    return SubGraph<const GR, const NF, EF>

1428

      (graph, node_filter_map, edge_filter_map);

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

1343

  SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>

1344

  subGraph(const Graph& graph,

1345

           NodeFilterMap& nfm, const ArcFilterMap& efm) {

1346

    return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>

1347

      (graph, nfm, efm);

1431

  template<typename GR, typename NF, typename EF>

1432

  SubGraph<const GR, NF, const EF>

1433

  subGraph(const GR& graph,

1434

           NF& node_filter_map, const EF& edge_filter_map) {

1435

    return SubGraph<const GR, NF, const EF>

1436

      (graph, node_filter_map, edge_filter_map);

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

1351

  SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>

1352

  subGraph(const Graph& graph,

1353

           const NodeFilterMap& nfm, const ArcFilterMap& efm) {

1354

    return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>

1355

      (graph, nfm, efm);

1439

  template<typename GR, typename NF, typename EF>

1440

  SubGraph<const GR, const NF, const EF>

1441

  subGraph(const GR& graph,

1442

           const NF& node_filter_map, const EF& edge_filter_map) {

1443

    return SubGraph<const GR, const NF, const EF>

1444

      (graph, node_filter_map, edge_filter_map);

  /// \ingroup graph_adaptors

1359

1449

///

1360

  /// \brief An adaptor for hiding nodes from a digraph or a graph.

1450

  /// \brief Adaptor class for hiding nodes in a digraph or a graph.

1361

1451

///

1362

  /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool

1363

  /// node map must be specified, which defines the filters for

1364

  /// nodes. Just the unfiltered nodes and the arcs or edges incident

1365

  /// to unfiltered nodes are shown in the subdigraph or subgraph. The

1366

  /// FilterNodes is conform to the \ref concepts::Digraph

1367

  /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending

1368

  /// on the \c _Digraph template parameter. If the \c _checked

1369

  /// parameter is true, then the arc or edges incident to filtered nodes

1370

  /// are also filtered out.

1452

  /// FilterNodes adaptor can be used for hiding nodes in a digraph or a

1453

  /// graph. A \c bool node map must be specified, which defines the filter

1454

  /// for the nodes. Only the nodes with \c true filter value and the

1455

  /// arcs/edges incident to nodes both with \c true filter value are shown

1456

  /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph

1457

  /// "Digraph" concept or the \ref concepts::Graph "Graph" concept

1458

  /// depending on the \c GR template parameter.

1371

1459

///

1372

  /// \tparam _Digraph It must be conform to the \ref

1373

  /// concepts::Digraph "Digraph concept" or \ref concepts::Graph

1374

  /// "Graph concept". The type can be specified to be const.

1375

  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.

1376

  /// \tparam _checked If the parameter is false then the arc or edge

1377

  /// filtering is not checked with respect to node filter. In this

1378

  /// case just isolated nodes can be filtered out from the

1379

  /// graph.

1460

  /// The adapted (di)graph can also be modified through this adaptor

1461

  /// by adding or removing nodes or arcs/edges, unless the \c GR template

1462

  /// parameter is set to be \c const.

1463

///

1464

  /// \tparam GR The type of the adapted digraph or graph.

1465

  /// It must conform to the \ref concepts::Digraph "Digraph" concept

1466

  /// or the \ref concepts::Graph "Graph" concept.

1467

  /// It can also be specified to be \c const.

1468

  /// \tparam NF The type of the node filter map.

1469

  /// It must be a \c bool (or convertible) node map of the

1470

  /// adapted (di)graph. The default type is

1471

  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".

1472

///

1473

  /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the

1474

  /// adapted (di)graph are convertible to each other.

1380

1475

#ifdef DOXYGEN

1381

  template<typename _Digraph,

1382

           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,

1383

           bool _checked = true>

1476

  template<typename GR, typename NF>

1477

  class FilterNodes {

1384

1478

#else

1385

  template<typename _Digraph,

1386

           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,

1387

           bool _checked = true,

1479

  template<typename GR,

1480

           typename NF = typename GR::template NodeMap<bool>,

1388

1481

           typename Enable = void>

1482

  class FilterNodes :

1483

    public DigraphAdaptorExtender<

1484

      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > {

1389

1485

#endif

1390

  class FilterNodes

1391

    : public SubDigraph<_Digraph, _NodeFilterMap,

1392

                        ConstMap<typename _Digraph::Arc, bool>, _checked> {

1393

1486

  public:

1394

1487

1395

    typedef _Digraph Digraph;

1396

    typedef _NodeFilterMap NodeFilterMap;

1397

1398

    typedef SubDigraph<Digraph, NodeFilterMap,

1399

                       ConstMap<typename Digraph::Arc, bool>, _checked>

1400

    Parent;

1488

    typedef GR Digraph;

1489

    typedef NF NodeFilterMap;

1490

1491

    typedef DigraphAdaptorExtender<

1492

      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >

1493

      Parent;

    typedef typename Parent::Node Node;

  protected:

1405

1498

    ConstMap<typename Digraph::Arc, bool> const_true_map;

    FilterNodes() : const_true_map(true) {

1408

1501

      Parent::setArcFilterMap(const_true_map);

  public:

    /// \brief Constructor

1414

1507

///

1415

    /// Creates an adaptor for the given digraph or graph with

1508

    /// Creates a subgraph for the given digraph or graph with the

1416

1509

    /// given node filter map.

1417

    FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :

1418

      Parent(), const_true_map(true) {

1419

      Parent::setDigraph(_digraph);

1510

    FilterNodes(GR& graph, NodeFilterMap& node_filter) :

1511

      Parent(), const_true_map(true)

1512

1513

      Parent::setDigraph(graph);

1420

1514

      Parent::setNodeFilterMap(node_filter);

1421

1515

      Parent::setArcFilterMap(const_true_map);

    /// \brief Hides the node of the graph

1518

    /// \brief Sets the status of the given node

1425

1519

///

1426

    /// This function hides \c n in the digraph or graph, i.e. the iteration

1427

    /// jumps over it. This is done by simply setting the value of \c n

1428

    /// to be false in the corresponding node map.

1429

    void hide(const Node& n) const { Parent::hide(n); }

1430

1431

    /// \brief Unhides the node of the graph

1520

    /// This function sets the status of the given node.

1521

    /// It is done by simply setting the assigned value of \c n

1522

    /// to \c v in the node filter map.

1523

    void status(const Node& n, bool v) const { Parent::status(n, v); }

1524

1525

    /// \brief Returns the status of the given node

1432

1526

///

1433

    /// The value of \c n is set to be true in the node-map which stores

1434

    /// hide information. If \c n was hidden previuosly, then it is shown

1435

    /// again

1436

    void unHide(const Node& n) const { Parent::unHide(n); }

1437

1438

    /// \brief Returns true if \c n is hidden.

1527

    /// This function returns the status of the given node.

1528

    /// It is \c true if the given node is enabled (i.e. not hidden).

1529

    bool status(const Node& n) const { return Parent::status(n); }

1530

1531

    /// \brief Disables the given node

1439

1532

///

1440

    /// Returns true if \c n is hidden.

1533

    /// This function disables the given node, so the iteration

1534

    /// jumps over it.

1535

    /// It is the same as \ref status() "status(n, false)".

1536

    void disable(const Node& n) const { Parent::status(n, false); }

1537

1538

    /// \brief Enables the given node

1441

1539

///

1442

    bool hidden(const Node& n) const { return Parent::hidden(n); }

1540

    /// This function enables the given node.

1541

    /// It is the same as \ref status() "status(n, true)".

1542

    void enable(const Node& n) const { Parent::status(n, true); }

};

1445

1545

1446

  template<typename _Graph, typename _NodeFilterMap, bool _checked>

1447

  class FilterNodes<_Graph, _NodeFilterMap, _checked,

1448

                    typename enable_if<UndirectedTagIndicator<_Graph> >::type>

1449

    : public SubGraph<_Graph, _NodeFilterMap,

1450

                      ConstMap<typename _Graph::Edge, bool>, _checked> {

1546

  template<typename GR, typename NF>

1547

  class FilterNodes<GR, NF,

1548

                    typename enable_if<UndirectedTagIndicator<GR> >::type> :

1549

    public GraphAdaptorExtender<

1550

      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > {

1551

1451

1552

  public:

1452

    typedef _Graph Graph;

1453

    typedef _NodeFilterMap NodeFilterMap;

1454

    typedef SubGraph<Graph, NodeFilterMap,

1455

                     ConstMap<typename Graph::Edge, bool> > Parent;

1553

    typedef GR Graph;

1554

    typedef NF NodeFilterMap;

1555

    typedef GraphAdaptorExtender<

1556

      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >

1557

      Parent;

    typedef typename Parent::Node Node;

1458

1560

  protected:

1459

1561

    ConstMap<typename Graph::Edge, bool> const_true_map;

    FilterNodes() : const_true_map(true) {

1462

1564

      Parent::setEdgeFilterMap(const_true_map);

  public:

    FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :

1468

1570

      Parent(), const_true_map(true) {

1469

1571

      Parent::setGraph(_graph);

1470

1572

      Parent::setNodeFilterMap(node_filter_map);

1471

1573

      Parent::setEdgeFilterMap(const_true_map);

    void hide(const Node& n) const { Parent::hide(n); }

1475

    void unHide(const Node& n) const { Parent::unHide(n); }

1476

    bool hidden(const Node& n) const { return Parent::hidden(n); }

1576

    void status(const Node& n, bool v) const { Parent::status(n, v); }

1577

    bool status(const Node& n) const { return Parent::status(n); }

1578

    void disable(const Node& n) const { Parent::status(n, false); }

1579

    void enable(const Node& n) const { Parent::status(n, true); }

};

  /// \brief Just gives back a FilterNodes adaptor

1584

  /// \brief Returns a read-only FilterNodes adaptor

1482

1585

///

1483

  /// Just gives back a FilterNodes adaptor

1484

  template<typename Digraph, typename NodeFilterMap>

1485

  FilterNodes<const Digraph, NodeFilterMap>

1486

  filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {

1487

    return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);

1586

  /// This function just returns a read-only \ref FilterNodes adaptor.

1587

  /// \ingroup graph_adaptors

1588

  /// \relates FilterNodes

1589

  template<typename GR, typename NF>

1590

  FilterNodes<const GR, NF>

1591

  filterNodes(const GR& graph, NF& node_filter_map) {

1592

    return FilterNodes<const GR, NF>(graph, node_filter_map);

  template<typename Digraph, typename NodeFilterMap>

1491

  FilterNodes<const Digraph, const NodeFilterMap>

1492

  filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {

1493

    return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);

1595

  template<typename GR, typename NF>

1596

  FilterNodes<const GR, const NF>

1597

  filterNodes(const GR& graph, const NF& node_filter_map) {

1598

    return FilterNodes<const GR, const NF>(graph, node_filter_map);

  /// \ingroup graph_adaptors

1497

1602

///

1498

  /// \brief An adaptor for hiding arcs from a digraph.

1603

  /// \brief Adaptor class for hiding arcs in a digraph.

1499

1604

///

1500

  /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must

1501

  /// be specified, which defines the filters for arcs. Just the

1502

  /// unfiltered arcs are shown in the subdigraph. The FilterArcs is

1503

  /// conform to the \ref concepts::Digraph "Digraph concept".

1605

  /// FilterArcs adaptor can be used for hiding arcs in a digraph.

1606

  /// A \c bool arc map must be specified, which defines the filter for

1607

  /// the arcs. Only the arcs with \c true filter value are shown in the

1608

  /// subdigraph. This adaptor conforms to the \ref concepts::Digraph

1609

  /// "Digraph" concept.

1504

1610

///

1505

  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph

1506

  /// "Digraph concept". The type can be specified to be const.

1507

  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted

1508

  /// graph.

1509

  template<typename _Digraph, typename _ArcFilterMap>

1611

  /// The adapted digraph can also be modified through this adaptor

1612

  /// by adding or removing nodes or arcs, unless the \c GR template

1613

  /// parameter is set to be \c const.

1614

///

1615

  /// \tparam GR The type of the adapted digraph.

1616

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

1617

  /// It can also be specified to be \c const.

1618

  /// \tparam AF The type of the arc filter map.

1619

  /// It must be a \c bool (or convertible) arc map of the

1620

  /// adapted digraph. The default type is

1621

  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".

1622

///

1623

  /// \note The \c Node and \c Arc types of this adaptor and the adapted

1624

  /// digraph are convertible to each other.

1625

#ifdef DOXYGEN

1626

  template<typename GR,

1627

           typename AF>

1628

  class FilterArcs {

1629

#else

1630

  template<typename GR,

1631

           typename AF = typename GR::template ArcMap<bool> >

1510

1632

  class FilterArcs :

1511

    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,

1512

                      _ArcFilterMap, false> {

1633

    public DigraphAdaptorExtender<

1634

      SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > {

1635

#endif

1513

1636

  public:

1514

    typedef _Digraph Digraph;

1515

    typedef _ArcFilterMap ArcFilterMap;

1516

1517

    typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,

1518

                       ArcFilterMap, false> Parent;

1637

    /// The type of the adapted digraph.

1638

    typedef GR Digraph;

1639

    /// The type of the arc filter map.

1640

    typedef AF ArcFilterMap;

1641

1642

    typedef DigraphAdaptorExtender<

1643

      SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> >

1644

      Parent;

    typedef typename Parent::Arc Arc;

  protected:

1523

1649

    ConstMap<typename Digraph::Node, bool> const_true_map;

    FilterArcs() : const_true_map(true) {

1526

1652

      Parent::setNodeFilterMap(const_true_map);

  public:

    /// \brief Constructor

1532

1658

///

1533

    /// Creates a FilterArcs adaptor for the given graph with

1534

    /// given arc map filter.

1659

    /// Creates a subdigraph for the given digraph with the given arc

1660

    /// filter map.

1535

1661

    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)

1536

1662

      : Parent(), const_true_map(true) {

1537

1663

      Parent::setDigraph(digraph);

1538

1664

      Parent::setNodeFilterMap(const_true_map);

1539

1665

      Parent::setArcFilterMap(arc_filter);

    /// \brief Hides the arc of the graph

1668

    /// \brief Sets the status of the given arc

1543

1669

///

1544

    /// This function hides \c a in the graph, i.e. the iteration

1545

    /// jumps over it. This is done by simply setting the value of \c a

1546

    /// to be false in the corresponding arc map.

1547

    void hide(const Arc& a) const { Parent::hide(a); }

1548

1549

    /// \brief Unhides the arc of the graph

1670

    /// This function sets the status of the given arc.

1671

    /// It is done by simply setting the assigned value of \c a

1672

    /// to \c v in the arc filter map.

1673

    void status(const Arc& a, bool v) const { Parent::status(a, v); }

1674

1675

    /// \brief Returns the status of the given arc

1550

1676

///

1551

    /// The value of \c a is set to be true in the arc-map which stores

1552

    /// hide information. If \c a was hidden previuosly, then it is shown

1553

    /// again

1554

    void unHide(const Arc& a) const { Parent::unHide(a); }

1555

1556

    /// \brief Returns true if \c a is hidden.

1677

    /// This function returns the status of the given arc.

1678

    /// It is \c true if the given arc is enabled (i.e. not hidden).

1679

    bool status(const Arc& a) const { return Parent::status(a); }

1680

1681

    /// \brief Disables the given arc

1557

1682

///

1558

    /// Returns true if \c a is hidden.

1683

    /// This function disables the given arc in the subdigraph,

1684

    /// so the iteration jumps over it.

1685

    /// It is the same as \ref status() "status(a, false)".

1686

    void disable(const Arc& a) const { Parent::status(a, false); }

1687

1688

    /// \brief Enables the given arc

1559

1689

///

1560

    bool hidden(const Arc& a) const { return Parent::hidden(a); }

1690

    /// This function enables the given arc in the subdigraph.

1691

    /// It is the same as \ref status() "status(a, true)".

1692

    void enable(const Arc& a) const { Parent::status(a, true); }

};

1563

1695

1564

  /// \brief Just gives back an FilterArcs adaptor

1696

  /// \brief Returns a read-only FilterArcs adaptor

1565

1697

///

1566

  /// Just gives back an FilterArcs adaptor

1567

  template<typename Digraph, typename ArcFilterMap>

1568

  FilterArcs<const Digraph, ArcFilterMap>

1569

  filterArcs(const Digraph& digraph, ArcFilterMap& afm) {

1570

    return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);

1698

  /// This function just returns a read-only \ref FilterArcs adaptor.

1699

  /// \ingroup graph_adaptors

1700

  /// \relates FilterArcs

1701

  template<typename GR, typename AF>

1702

  FilterArcs<const GR, AF>

1703

  filterArcs(const GR& digraph, AF& arc_filter_map) {

1704

    return FilterArcs<const GR, AF>(digraph, arc_filter_map);

  template<typename Digraph, typename ArcFilterMap>

1574

  FilterArcs<const Digraph, const ArcFilterMap>

1575

  filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {

1576

    return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);

1707

  template<typename GR, typename AF>

1708

  FilterArcs<const GR, const AF>

1709

  filterArcs(const GR& digraph, const AF& arc_filter_map) {

1710

    return FilterArcs<const GR, const AF>(digraph, arc_filter_map);

  /// \ingroup graph_adaptors

1580

1714

///

1581

  /// \brief An adaptor for hiding edges from a graph.

1715

  /// \brief Adaptor class for hiding edges in a graph.

1582

1716

///

1583

  /// FilterEdges adaptor hides edges in a digraph. A bool edge map must

1584

  /// be specified, which defines the filters for edges. Just the

1585

  /// unfiltered edges are shown in the subdigraph. The FilterEdges is

1586

  /// conform to the \ref concepts::Graph "Graph concept".

1717

  /// FilterEdges adaptor can be used for hiding edges in a graph.

1718

  /// A \c bool edge map must be specified, which defines the filter for

1719

  /// the edges. Only the edges with \c true filter value are shown in the

1720

  /// subgraph. This adaptor conforms to the \ref concepts::Graph

1721

  /// "Graph" concept.

1587

1722

///

1588

  /// \tparam _Graph It must be conform to the \ref concepts::Graph

1589

  /// "Graph concept". The type can be specified to be const.

1590

  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted

1591

  /// graph.

1592

  template<typename _Graph, typename _EdgeFilterMap>

1723

  /// The adapted graph can also be modified through this adaptor

1724

  /// by adding or removing nodes or edges, unless the \c GR template

1725

  /// parameter is set to be \c const.

1726

///

1727

  /// \tparam GR The type of the adapted graph.

1728

  /// It must conform to the \ref concepts::Graph "Graph" concept.

1729

  /// It can also be specified to be \c const.

1730

  /// \tparam EF The type of the edge filter map.

1731

  /// It must be a \c bool (or convertible) edge map of the

1732

  /// adapted graph. The default type is

1733

  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".

1734

///

1735

  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the

1736

  /// adapted graph are convertible to each other.

1737

#ifdef DOXYGEN

1738

  template<typename GR,

1739

           typename EF>

1740

  class FilterEdges {

1741

#else

1742

  template<typename GR,

1743

           typename EF = typename GR::template EdgeMap<bool> >

1593

1744

  class FilterEdges :

1594

    public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,

1595

                    _EdgeFilterMap, false> {

1745

    public GraphAdaptorExtender<

1746

      SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > {

1747

#endif

1596

1748

  public:

1597

    typedef _Graph Graph;

1598

    typedef _EdgeFilterMap EdgeFilterMap;

1599

    typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,

1600

                     EdgeFilterMap, false> Parent;

1749

    /// The type of the adapted graph.

1750

    typedef GR Graph;

1751

    /// The type of the edge filter map.

1752

    typedef EF EdgeFilterMap;

1753

1754

    typedef GraphAdaptorExtender<

1755

      SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> >

1756

      Parent;

1757

1601

1758

    typedef typename Parent::Edge Edge;

1759

1602

1760

  protected:

1603

1761

    ConstMap<typename Graph::Node, bool> const_true_map;

    FilterEdges() : const_true_map(true) {

1606

1764

      Parent::setNodeFilterMap(const_true_map);

  public:

    /// \brief Constructor

1612

1770

///

1613

    /// Creates a FilterEdges adaptor for the given graph with

1614

    /// given edge map filters.

1615

    FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :

1771

    /// Creates a subgraph for the given graph with the given edge

1772

    /// filter map.

1773

    FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :

1616

1774

      Parent(), const_true_map(true) {

1617

      Parent::setGraph(_graph);

1775

      Parent::setGraph(graph);

1618

1776

      Parent::setNodeFilterMap(const_true_map);

1619

1777

      Parent::setEdgeFilterMap(edge_filter_map);

    /// \brief Hides the edge of the graph

1780

    /// \brief Sets the status of the given edge

1623

1781

///

1624

    /// This function hides \c e in the graph, i.e. the iteration

1625

    /// jumps over it. This is done by simply setting the value of \c e

1626

    /// to be false in the corresponding edge-map.

1627

    void hide(const Edge& e) const { Parent::hide(e); }

1628

1629

    /// \brief Unhides the edge of the graph

1782

    /// This function sets the status of the given edge.

1783

    /// It is done by simply setting the assigned value of \c e

1784

    /// to \c v in the edge filter map.

1785

    void status(const Edge& e, bool v) const { Parent::status(e, v); }

1786

1787

    /// \brief Returns the status of the given edge

1630

1788

///

1631

    /// The value of \c e is set to be true in the edge-map which stores

1632

    /// hide information. If \c e was hidden previuosly, then it is shown

1633

    /// again

1634

    void unHide(const Edge& e) const { Parent::unHide(e); }

1635

1636

    /// \brief Returns true if \c e is hidden.

1789

    /// This function returns the status of the given edge.

1790

    /// It is \c true if the given edge is enabled (i.e. not hidden).

1791

    bool status(const Edge& e) const { return Parent::status(e); }

1792

1793

    /// \brief Disables the given edge

1637

1794

///

1638

    /// Returns true if \c e is hidden.

1795

    /// This function disables the given edge in the subgraph,

1796

    /// so the iteration jumps over it.

1797

    /// It is the same as \ref status() "status(e, false)".

1798

    void disable(const Edge& e) const { Parent::status(e, false); }

1799

1800

    /// \brief Enables the given edge

1639

1801

///

1640

    bool hidden(const Edge& e) const { return Parent::hidden(e); }

1802

    /// This function enables the given edge in the subgraph.

1803

    /// It is the same as \ref status() "status(e, true)".

1804

    void enable(const Edge& e) const { Parent::status(e, true); }

};

1643

1807

1644

  /// \brief Just gives back a FilterEdges adaptor

1808

  /// \brief Returns a read-only FilterEdges adaptor

1645

1809

///

1646

  /// Just gives back a FilterEdges adaptor

1647

  template<typename Graph, typename EdgeFilterMap>

1648

  FilterEdges<const Graph, EdgeFilterMap>

1649

  filterEdges(const Graph& graph, EdgeFilterMap& efm) {

1650

    return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);

1810

  /// This function just returns a read-only \ref FilterEdges adaptor.

1811

  /// \ingroup graph_adaptors

1812

  /// \relates FilterEdges

1813

  template<typename GR, typename EF>

1814

  FilterEdges<const GR, EF>

1815

  filterEdges(const GR& graph, EF& edge_filter_map) {

1816

    return FilterEdges<const GR, EF>(graph, edge_filter_map);

  template<typename Graph, typename EdgeFilterMap>

1654

  FilterEdges<const Graph, const EdgeFilterMap>

1655

  filterEdges(const Graph& graph, const EdgeFilterMap& efm) {

1656

    return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);

1819

  template<typename GR, typename EF>

1820

  FilterEdges<const GR, const EF>

1821

  filterEdges(const GR& graph, const EF& edge_filter_map) {

1822

    return FilterEdges<const GR, const EF>(graph, edge_filter_map);

  template <typename _Digraph>

1660

1827

  class UndirectorBase {

1661

1828

  public:

1662

1829

    typedef _Digraph Digraph;

1663

1830

    typedef UndirectorBase Adaptor;

    typedef True UndirectedTag;

    typedef typename Digraph::Arc Edge;

1668

1835

    typedef typename Digraph::Node Node;

    class Arc : public Edge {

...

@@ -1686,26 +1853,24 @@

      bool operator!=(const Arc &other) const {

1688

1855

        return _forward != other._forward ||

1689

1856

          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);

      bool operator<(const Arc &other) const {

1692

1859

        return _forward < other._forward ||

1693

1860

          (_forward == other._forward &&

1694

1861

           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));

};

    void first(Node& n) const {

1701

1866

      _digraph->first(n);

    void next(Node& n) const {

1705

1870

      _digraph->next(n);

    void first(Arc& a) const {

1709

1874

      _digraph->first(a);

1710

1875

      a._forward = true;

1711

1876

...

@@ -1836,56 +2001,60 @@

    Node addNode() { return _digraph->addNode(); }

1838

2003

    Edge addEdge(const Node& u, const Node& v) {

1839

2004

      return _digraph->addArc(u, v);

    void erase(const Node& i) { _digraph->erase(i); }

1843

2008

    void erase(const Edge& i) { _digraph->erase(i); }

    void clear() { _digraph->clear(); }

    typedef NodeNumTagIndicator<Digraph> NodeNumTag;

1848

    int nodeNum() const { return 2 * _digraph->arcNum(); }

1849

    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;

2013

    int nodeNum() const { return _digraph->nodeNum(); }

2014

2015

    typedef ArcNumTagIndicator<Digraph> ArcNumTag;

1850

2016

    int arcNum() const { return 2 * _digraph->arcNum(); }

2017

2018

    typedef ArcNumTag EdgeNumTag;

1851

2019

    int edgeNum() const { return _digraph->arcNum(); }

1852

2020

1853

    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;

2021

    typedef FindArcTagIndicator<Digraph> FindArcTag;

1854

2022

    Arc findArc(Node s, Node t, Arc p = INVALID) const {

1855

2023

      if (p == INVALID) {

1856

2024

        Edge arc = _digraph->findArc(s, t);

1857

2025

        if (arc != INVALID) return direct(arc, true);

1858

2026

        arc = _digraph->findArc(t, s);

1859

2027

        if (arc != INVALID) return direct(arc, false);

1860

2028

      } else if (direction(p)) {

1861

2029

        Edge arc = _digraph->findArc(s, t, p);

1862

2030

        if (arc != INVALID) return direct(arc, true);

1863

2031

        arc = _digraph->findArc(t, s);

1864

2032

        if (arc != INVALID) return direct(arc, false);

1865

2033

      } else {

1866

2034

        Edge arc = _digraph->findArc(t, s, p);

1867

2035

        if (arc != INVALID) return direct(arc, false);

      return INVALID;

    typedef FindArcTag FindEdgeTag;

1872

2041

    Edge findEdge(Node s, Node t, Edge p = INVALID) const {

1873

2042

      if (s != t) {

1874

2043

        if (p == INVALID) {

1875

2044

          Edge arc = _digraph->findArc(s, t);

1876

2045

          if (arc != INVALID) return arc;

1877

2046

          arc = _digraph->findArc(t, s);

1878

2047

          if (arc != INVALID) return arc;

1879

        } else if (_digraph->s(p) == s) {

2048

        } else if (_digraph->source(p) == s) {

1880

2049

          Edge arc = _digraph->findArc(s, t, p);

1881

2050

          if (arc != INVALID) return arc;

1882

2051

          arc = _digraph->findArc(t, s);

1883

2052

          if (arc != INVALID) return arc;

1884

2053

        } else {

1885

2054

          Edge arc = _digraph->findArc(t, s, p);

1886

2055

          if (arc != INVALID) return arc;

      } else {

1889

2058

        return _digraph->findArc(s, t, p);

      return INVALID;

...

@@ -1896,50 +2065,52 @@

1896

2065

    template <typename _Value>

1897

2066

    class ArcMapBase {

1898

2067

    private:

      typedef typename Digraph::template ArcMap<_Value> MapImpl;

    public:

      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;

      typedef _Value Value;

1907

2076

      typedef Arc Key;

2077

      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;

2078

      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;

2079

      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;

2080

      typedef typename MapTraits<MapImpl>::ReturnValue Reference;

      ArcMapBase(const Adaptor& adaptor) :

1910

2083

        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}

      ArcMapBase(const Adaptor& adaptor, const Value& v)

1913

2086

        : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}

      void set(const Arc& a, const Value& v) {

1916

2089

        if (direction(a)) {

1917

2090

          _forward.set(a, v);

1918

2091

        } else {

1919

2092

          _backward.set(a, v);

      typename MapTraits<MapImpl>::ConstReturnValue

1924

      operator[](const Arc& a) const {

2096

      ConstReturnValue operator[](const Arc& a) const {

1925

2097

        if (direction(a)) {

1926

2098

          return _forward[a];

1927

2099

        } else {

1928

2100

          return _backward[a];

      typename MapTraits<MapImpl>::ReturnValue

1933

      operator[](const Arc& a) {

2104

      ReturnValue operator[](const Arc& a) {

1934

2105

        if (direction(a)) {

1935

2106

          return _forward[a];

1936

2107

        } else {

1937

2108

          return _backward[a];

    protected:

      MapImpl _forward, _backward;

};

...

@@ -1971,25 +2142,25 @@

};

    template <typename _Value>

1976

2147

    class ArcMap

1977

2148

      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >

    public:

1980

2151

      typedef _Value Value;

1981

2152

      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;

1982

2153

1983

      ArcMap(const Adaptor& adaptor)

2154

      explicit ArcMap(const Adaptor& adaptor)

1984

2155

        : Parent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value)

1987

2158

        : Parent(adaptor, value) {}

    private:

1990

2161

      ArcMap& operator=(const ArcMap& cmap) {

1991

2162

        return operator=<ArcMap>(cmap);

      template <typename CMap>

1995

2166

      ArcMap& operator=(const CMap& cmap) {

...

@@ -2018,133 +2189,147 @@

      template <typename CMap>

2020

2191

      EdgeMap& operator=(const CMap& cmap) {

2021

2192

        Parent::operator=(cmap);

2022

2193

        return *this;

};

    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;

2028

2199

    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }

2029

2200

2201

    typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;

2202

    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }

2203

2030

2204

  protected:

    UndirectorBase() : _digraph(0) {}

    Digraph* _digraph;

    void setDigraph(Digraph& digraph) {

2037

2211

      _digraph = &digraph;

};

  /// \ingroup graph_adaptors

2043

2217

///

2044

  /// \brief Undirect the graph

2218

  /// \brief Adaptor class for viewing a digraph as an undirected graph.

2045

2219

///

2046

  /// This adaptor makes an undirected graph from a directed

2047

  /// graph. All arcs of the underlying digraph will be showed in the

2048

  /// adaptor as an edge. The Orienter adaptor is conform to the \ref

2049

  /// concepts::Graph "Graph concept".

2220

  /// Undirector adaptor can be used for viewing a digraph as an undirected

2221

  /// graph. All arcs of the underlying digraph are showed in the

2222

  /// adaptor as an edge (and also as a pair of arcs, of course).

2223

  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.

2050

2224

///

2051

  /// \tparam _Digraph It must be conform to the \ref

2052

  /// concepts::Digraph "Digraph concept". The type can be specified

2053

  /// to const.

2054

  template<typename _Digraph>

2055

  class Undirector

2056

    : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {

2225

  /// The adapted digraph can also be modified through this adaptor

2226

  /// by adding or removing nodes or edges, unless the \c GR template

2227

  /// parameter is set to be \c const.

2228

///

2229

  /// \tparam GR The type of the adapted digraph.

2230

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

2231

  /// It can also be specified to be \c const.

2232

///

2233

  /// \note The \c Node type of this adaptor and the adapted digraph are

2234

  /// convertible to each other, moreover the \c Edge type of the adaptor

2235

  /// and the \c Arc type of the adapted digraph are also convertible to

2236

  /// each other.

2237

  /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type

2238

  /// of the adapted digraph.)

2239

  template<typename GR>

2240

#ifdef DOXYGEN

2241

  class Undirector {

2242

#else

2243

  class Undirector :

2244

    public GraphAdaptorExtender<UndirectorBase<GR> > {

2245

#endif

2057

2246

  public:

2058

    typedef _Digraph Digraph;

2059

    typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;

2247

    /// The type of the adapted digraph.

2248

    typedef GR Digraph;

2249

    typedef GraphAdaptorExtender<UndirectorBase<GR> > Parent;

2060

2250

  protected:

2061

2251

    Undirector() { }

2062

2252

  public:

    /// \brief Constructor

2065

2255

///

2066

    /// Creates a undirected graph from the given digraph

2067

    Undirector(_Digraph& digraph) {

2256

    /// Creates an undirected graph from the given digraph.

2257

    Undirector(Digraph& digraph) {

2068

2258

      setDigraph(digraph);

    /// \brief ArcMap combined from two original ArcMap

2261

    /// \brief Arc map combined from two original arc maps

2072

2262

///

2073

    /// This class adapts two original digraph ArcMap to

2074

    /// get an arc map on the undirected graph.

2075

    template <typename _ForwardMap, typename _BackwardMap>

2263

    /// This map adaptor class adapts two arc maps of the underlying

2264

    /// digraph to get an arc map of the undirected graph.

2265

    /// Its value type is inherited from the first arc map type

2266

    /// (\c %ForwardMap).

2267

    template <typename ForwardMap, typename BackwardMap>

2076

2268

    class CombinedArcMap {

2077

2269

    public:

2078

2270

2079

      typedef _ForwardMap ForwardMap;

2080

      typedef _BackwardMap BackwardMap;

2271

      /// The key type of the map

2272

      typedef typename Parent::Arc Key;

2273

      /// The value type of the map

2274

      typedef typename ForwardMap::Value Value;

      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;

2083

2277

2084

      typedef typename ForwardMap::Value Value;

2085

      typedef typename Parent::Arc Key;

2086

2087

      /// \brief Constructor

2088

///

2278

      typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;

2279

      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;

2280

      typedef typename MapTraits<ForwardMap>::ReturnValue Reference;

2281

      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;

2282

2089

2283

      /// Constructor

2090

2284

      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)

2091

2285

        : _forward(&forward), _backward(&backward) {}

      /// \brief Sets the value associated with a key.

2095

///

2096

      /// Sets the value associated with a key.

2287

      /// Sets the value associated with the given key.

2097

2288

      void set(const Key& e, const Value& a) {

2098

2289

        if (Parent::direction(e)) {

2099

2290

          _forward->set(e, a);

2100

2291

        } else {

2101

2292

          _backward->set(e, a);

      /// \brief Returns the value associated with a key.

2106

///

2107

      /// Returns the value associated with a key.

2108

      typename MapTraits<ForwardMap>::ConstReturnValue

2109

      operator[](const Key& e) const {

2296

      /// Returns the value associated with the given key.

2297

      ConstReturnValue operator[](const Key& e) const {

2110

2298

        if (Parent::direction(e)) {

2111

2299

          return (*_forward)[e];

2112

2300

        } else {

2113

2301

          return (*_backward)[e];

      /// \brief Returns the value associated with a key.

2118

///

2119

      /// Returns the value associated with a key.

2120

      typename MapTraits<ForwardMap>::ReturnValue

2121

      operator[](const Key& e) {

2305

      /// Returns a reference to the value associated with the given key.

2306

      ReturnValue operator[](const Key& e) {

2122

2307

        if (Parent::direction(e)) {

2123

2308

          return (*_forward)[e];

2124

2309

        } else {

2125

2310

          return (*_backward)[e];

    protected:

      ForwardMap* _forward;

2132

2317

      BackwardMap* _backward;

};

2135

2320

2136

    /// \brief Just gives back a combined arc map

2321

    /// \brief Returns a combined arc map

2137

2322

///

2138

    /// Just gives back a combined arc map

2323

    /// This function just returns a combined arc map.

2139

2324

    template <typename ForwardMap, typename BackwardMap>

2140

2325

    static CombinedArcMap<ForwardMap, BackwardMap>

2141

2326

    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {

2142

2327

      return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);

    template <typename ForwardMap, typename BackwardMap>

2146

2331

    static CombinedArcMap<const ForwardMap, BackwardMap>

2147

2332

    combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {

2148

2333

      return CombinedArcMap<const ForwardMap,

2149

2334

        BackwardMap>(forward, backward);

2150

2335

...

@@ -2156,56 +2341,58 @@

2156

2341

        const BackwardMap>(forward, backward);

    template <typename ForwardMap, typename BackwardMap>

2160

2345

    static CombinedArcMap<const ForwardMap, const BackwardMap>

2161

2346

    combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {

2162

2347

      return CombinedArcMap<const ForwardMap,

2163

2348

        const BackwardMap>(forward, backward);

};

2167

2352

2168

  /// \brief Just gives back an undirected view of the given digraph

2353

  /// \brief Returns a read-only Undirector adaptor

2169

2354

///

2170

  /// Just gives back an undirected view of the given digraph

2171

  template<typename Digraph>

2172

  Undirector<const Digraph>

2173

  undirector(const Digraph& digraph) {

2174

    return Undirector<const Digraph>(digraph);

2355

  /// This function just returns a read-only \ref Undirector adaptor.

2356

  /// \ingroup graph_adaptors

2357

  /// \relates Undirector

2358

  template<typename GR>

2359

  Undirector<const GR> undirector(const GR& digraph) {

2360

    return Undirector<const GR>(digraph);

  template <typename _Graph, typename _DirectionMap>

2178

2365

  class OrienterBase {

2179

2366

  public:

    typedef _Graph Graph;

2182

2369

    typedef _DirectionMap DirectionMap;

    typedef typename Graph::Node Node;

2185

2372

    typedef typename Graph::Edge Arc;

    void reverseArc(const Arc& arc) {

2188

2375

      _direction->set(arc, !(*_direction)[arc]);

    void first(Node& i) const { _graph->first(i); }

2192

2379

    void first(Arc& i) const { _graph->first(i); }

2193

2380

    void firstIn(Arc& i, const Node& n) const {

2194

      bool d;

2381

      bool d = true;

2195

2382

      _graph->firstInc(i, d, n);

2196

2383

      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);

    void firstOut(Arc& i, const Node& n ) const {

2199

      bool d;

2386

      bool d = true;

2200

2387

      _graph->firstInc(i, d, n);

2201

2388

      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);

    void next(Node& i) const { _graph->next(i); }

2205

2392

    void next(Arc& i) const { _graph->next(i); }

2206

2393

    void nextIn(Arc& i) const {

2207

2394

      bool d = !(*_direction)[i];

2208

2395

      _graph->nextInc(i, d);

2209

2396

      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);

    void nextOut(Arc& i) const {

...

@@ -2215,53 +2402,44 @@

    Node source(const Arc& e) const {

2218

2405

      return (*_direction)[e] ? _graph->u(e) : _graph->v(e);

    Node target(const Arc& e) const {

2221

2408

      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);

    typedef NodeNumTagIndicator<Graph> NodeNumTag;

2225

2412

    int nodeNum() const { return _graph->nodeNum(); }

2226

2413

2227

    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

2414

    typedef EdgeNumTagIndicator<Graph> ArcNumTag;

2228

2415

    int arcNum() const { return _graph->edgeNum(); }

2229

2416

2230

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

2417

    typedef FindEdgeTagIndicator<Graph> FindArcTag;

2231

2418

    Arc findArc(const Node& u, const Node& v,

2232

                const Arc& prev = INVALID) {

2233

      Arc arc = prev;

2234

      bool d = arc == INVALID ? true : (*_direction)[arc];

2235

      if (d) {

2419

                const Arc& prev = INVALID) const {

2420

      Arc arc = _graph->findEdge(u, v, prev);

2421

      while (arc != INVALID && source(arc) != u) {

2236

2422

        arc = _graph->findEdge(u, v, arc);

2237

        while (arc != INVALID && !(*_direction)[arc]) {

2238

          _graph->findEdge(u, v, arc);

2239

2240

        if (arc != INVALID) return arc;

2241

2242

      _graph->findEdge(v, u, arc);

2243

      while (arc != INVALID && (*_direction)[arc]) {

2244

        _graph->findEdge(u, v, arc);

      return arc;

    Node addNode() {

2250

2428

      return Node(_graph->addNode());

    Arc addArc(const Node& u, const Node& v) {

2254

      Arc arc = _graph->addArc(u, v);

2255

      _direction->set(arc, _graph->source(arc) == u);

2432

      Arc arc = _graph->addEdge(u, v);

2433

      _direction->set(arc, _graph->u(arc) == u);

2256

2434

      return arc;

    void erase(const Node& i) { _graph->erase(i); }

2260

2438

    void erase(const Arc& i) { _graph->erase(i); }

    void clear() { _graph->clear(); }

    int id(const Node& v) const { return _graph->id(v); }

2265

2443

    int id(const Arc& e) const { return _graph->id(e); }

    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }

...

@@ -2334,318 +2512,379 @@

2334

2512

    void setDirectionMap(DirectionMap& direction) {

2335

2513

      _direction = &direction;

    void setGraph(Graph& graph) {

2339

2517

      _graph = &graph;

};

  /// \ingroup graph_adaptors

2345

2523

///

2346

  /// \brief Orients the edges of the graph to get a digraph

2524

  /// \brief Adaptor class for orienting the edges of a graph to get a digraph

2347

2525

///

2348

  /// This adaptor orients each edge in the undirected graph. The

2349

  /// direction of the arcs stored in an edge node map.  The arcs can

2350

  /// be easily reverted by the \c reverseArc() member function in the

2351

  /// adaptor. The Orienter adaptor is conform to the \ref

2352

  /// concepts::Digraph "Digraph concept".

2526

  /// Orienter adaptor can be used for orienting the edges of a graph to

2527

  /// get a digraph. A \c bool edge map of the underlying graph must be

2528

  /// specified, which define the direction of the arcs in the adaptor.

2529

  /// The arcs can be easily reversed by the \c reverseArc() member function

2530

  /// of the adaptor.

2531

  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.

2353

2532

///

2354

  /// \tparam _Graph It must be conform to the \ref concepts::Graph

2355

  /// "Graph concept". The type can be specified to be const.

2356

  /// \tparam _DirectionMap A bool valued edge map of the the adapted

2357

  /// graph.

2533

  /// The adapted graph can also be modified through this adaptor

2534

  /// by adding or removing nodes or arcs, unless the \c GR template

2535

  /// parameter is set to be \c const.

2358

2536

///

2359

  /// \sa orienter

2360

  template<typename _Graph,

2361

           typename DirectionMap = typename _Graph::template EdgeMap<bool> >

2537

  /// \tparam GR The type of the adapted graph.

2538

  /// It must conform to the \ref concepts::Graph "Graph" concept.

2539

  /// It can also be specified to be \c const.

2540

  /// \tparam DM The type of the direction map.

2541

  /// It must be a \c bool (or convertible) edge map of the

2542

  /// adapted graph. The default type is

2543

  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".

2544

///

2545

  /// \note The \c Node type of this adaptor and the adapted graph are

2546

  /// convertible to each other, moreover the \c Arc type of the adaptor

2547

  /// and the \c Edge type of the adapted graph are also convertible to

2548

  /// each other.

2549

#ifdef DOXYGEN

2550

  template<typename GR,

2551

           typename DM>

2552

  class Orienter {

2553

#else

2554

  template<typename GR,

2555

           typename DM = typename GR::template EdgeMap<bool> >

2362

2556

  class Orienter :

2363

    public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {

2557

    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {

2558

#endif

2364

2559

  public:

2365

    typedef _Graph Graph;

2366

    typedef DigraphAdaptorExtender<

2367

      OrienterBase<_Graph, DirectionMap> > Parent;

2560

2561

    /// The type of the adapted graph.

2562

    typedef GR Graph;

2563

    /// The type of the direction edge map.

2564

    typedef DM DirectionMap;

2565

2566

    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;

2368

2567

    typedef typename Parent::Arc Arc;

2369

2568

  protected:

2370

2569

    Orienter() { }

2371

2570

  public:

2372

2571

2373

    /// \brief Constructor of the adaptor

2572

    /// \brief Constructor

2374

2573

///

2375

    /// Constructor of the adaptor

2574

    /// Constructor of the adaptor.

2376

2575

    Orienter(Graph& graph, DirectionMap& direction) {

2377

2576

      setGraph(graph);

2378

2577

      setDirectionMap(direction);

    /// \brief Reverse arc

2580

    /// \brief Reverses the given arc

2382

2581

///

2383

    /// It reverse the given arc. It simply negate the direction in the map.

2582

    /// This function reverses the given arc.

2583

    /// It is done by simply negate the assigned value of \c a

2584

    /// in the direction map.

2384

2585

    void reverseArc(const Arc& a) {

2385

2586

      Parent::reverseArc(a);

};

2388

2589

2389

  /// \brief Just gives back a Orienter

2590

  /// \brief Returns a read-only Orienter adaptor

2390

2591

///

2391

  /// Just gives back a Orienter

2392

  template<typename Graph, typename DirectionMap>

2393

  Orienter<const Graph, DirectionMap>

2394

  orienter(const Graph& graph, DirectionMap& dm) {

2395

    return Orienter<const Graph, DirectionMap>(graph, dm);

2592

  /// This function just returns a read-only \ref Orienter adaptor.

2593

  /// \ingroup graph_adaptors

2594

  /// \relates Orienter

2595

  template<typename GR, typename DM>

2596

  Orienter<const GR, DM>

2597

  orienter(const GR& graph, DM& direction_map) {

2598

    return Orienter<const GR, DM>(graph, direction_map);

  template<typename Graph, typename DirectionMap>

2399

  Orienter<const Graph, const DirectionMap>

2400

  orienter(const Graph& graph, const DirectionMap& dm) {

2401

    return Orienter<const Graph, const DirectionMap>(graph, dm);

2601

  template<typename GR, typename DM>

2602

  Orienter<const GR, const DM>

2603

  orienter(const GR& graph, const DM& direction_map) {

2604

    return Orienter<const GR, const DM>(graph, direction_map);

  namespace _adaptor_bits {

2405

2608

2406

    template<typename _Digraph,

2407

             typename _CapacityMap = typename _Digraph::template ArcMap<int>,

2408

             typename _FlowMap = _CapacityMap,

2409

             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >

2609

    template<typename Digraph,

2610

             typename CapacityMap,

2611

             typename FlowMap,

2612

             typename Tolerance>

2410

2613

    class ResForwardFilter {

2411

2614

    public:

2412

2615

2413

      typedef _Digraph Digraph;

2414

      typedef _CapacityMap CapacityMap;

2415

      typedef _FlowMap FlowMap;

2416

      typedef _Tolerance Tolerance;

2417

2418

2616

      typedef typename Digraph::Arc Key;

2419

2617

      typedef bool Value;

    private:

      const CapacityMap* _capacity;

2424

2622

      const FlowMap* _flow;

2425

2623

      Tolerance _tolerance;

2426

2624

    public:

      ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,

2429

2627

                       const Tolerance& tolerance = Tolerance())

2430

2628

        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }

      bool operator[](const typename Digraph::Arc& a) const {

2433

2631

        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);

};

2436

2634

2437

    template<typename _Digraph,

2438

             typename _CapacityMap = typename _Digraph::template ArcMap<int>,

2439

             typename _FlowMap = _CapacityMap,

2440

             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >

2635

    template<typename Digraph,

2636

             typename CapacityMap,

2637

             typename FlowMap,

2638

             typename Tolerance>

2441

2639

    class ResBackwardFilter {

2442

2640

    public:

2443

2641

2444

      typedef _Digraph Digraph;

2445

      typedef _CapacityMap CapacityMap;

2446

      typedef _FlowMap FlowMap;

2447

      typedef _Tolerance Tolerance;

2448

2449

2642

      typedef typename Digraph::Arc Key;

2450

2643

      typedef bool Value;

    private:

      const CapacityMap* _capacity;

2455

2648

      const FlowMap* _flow;

2456

2649

      Tolerance _tolerance;

    public:

      ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,

2461

2654

                        const Tolerance& tolerance = Tolerance())

2462

2655

        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }

      bool operator[](const typename Digraph::Arc& a) const {

2465

2658

        return _tolerance.positive((*_flow)[a]);

};

  /// \ingroup graph_adaptors

2472

2665

///

2473

  /// \brief An adaptor for composing the residual graph for directed

2666

  /// \brief Adaptor class for composing the residual digraph for directed

2474

2667

  /// flow and circulation problems.

2475

2668

///

2476

  /// An adaptor for composing the residual graph for directed flow and

2477

  /// circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph

2478

  /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,

2479

  /// be functions on the arc-set.

2669

  /// Residual can be used for composing the \e residual digraph for directed

2670

  /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph

2671

  /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be

2672

  /// functions on the arcs.

2673

  /// This adaptor implements a digraph structure with node set \f$ V \f$

2674

  /// and arc set \f$ A_{forward}\cup A_{backward} \f$,

2675

  /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and

2676

  /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so

2677

  /// called residual digraph.

2678

  /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,

2679

  /// multiplicities are counted, i.e. the adaptor has exactly

2680

  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel

2681

  /// arcs).

2682

  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.

2480

2683

///

2481

  /// Then Residual implements the digraph structure with

2482

  /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,

2483

  /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and

2484

  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so

2485

  /// called residual graph.  When we take the union

2486

  /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,

2487

  /// i.e.  if an arc is in both \f$ A_{forward} \f$ and

2488

  /// \f$ A_{backward} \f$, then in the adaptor it appears in both

2489

  /// orientation.

2684

  /// \tparam GR The type of the adapted digraph.

2685

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

2686

  /// It is implicitly \c const.

2687

  /// \tparam CM The type of the capacity map.

2688

  /// It must be an arc map of some numerical type, which defines

2689

  /// the capacities in the flow problem. It is implicitly \c const.

2690

  /// The default type is

2691

  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

2692

  /// \tparam FM The type of the flow map.

2693

  /// It must be an arc map of some numerical type, which defines

2694

  /// the flow values in the flow problem. The default type is \c CM.

2695

  /// \tparam TL The tolerance type for handling inexact computation.

2696

  /// The default tolerance type depends on the value type of the

2697

  /// capacity map.

2490

2698

///

2491

  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph

2492

  /// "Digraph concept". The type is implicitly const.

2493

  /// \tparam _CapacityMap An arc map of some numeric type, it defines

2494

  /// the capacities in the flow problem. The map is implicitly const.

2495

  /// \tparam _FlowMap An arc map of some numeric type, it defines

2496

  /// the capacities in the flow problem.

2497

  /// \tparam _Tolerance Handler for inexact computation.

2498

  template<typename _Digraph,

2499

           typename _CapacityMap = typename _Digraph::template ArcMap<int>,

2500

           typename _FlowMap = _CapacityMap,

2501

           typename _Tolerance = Tolerance<typename _CapacityMap::Value> >

2699

  /// \note This adaptor is implemented using Undirector and FilterArcs

2700

  /// adaptors.

2701

///

2702

  /// \note The \c Node type of this adaptor and the adapted digraph are

2703

  /// convertible to each other, moreover the \c Arc type of the adaptor

2704

  /// is convertible to the \c Arc type of the adapted digraph.

2705

#ifdef DOXYGEN

2706

  template<typename GR, typename CM, typename FM, typename TL>

2707

  class Residual

2708

#else

2709

  template<typename GR,

2710

           typename CM = typename GR::template ArcMap<int>,

2711

           typename FM = CM,

2712

           typename TL = Tolerance<typename CM::Value> >

2502

2713

  class Residual :

2503

2714

    public FilterArcs<

2504

    Undirector<const _Digraph>,

2505

    typename Undirector<const _Digraph>::template CombinedArcMap<

2506

      _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,

2507

                                      _FlowMap, _Tolerance>,

2508

      _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,

2509

                                       _FlowMap, _Tolerance> > >

2715

      Undirector<const GR>,

2716

      typename Undirector<const GR>::template CombinedArcMap<

2717

        _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>,

2718

        _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > >

2719

#endif

  public:

2512

2722

2513

    typedef _Digraph Digraph;

2514

    typedef _CapacityMap CapacityMap;

2515

    typedef _FlowMap FlowMap;

2516

    typedef _Tolerance Tolerance;

2723

    /// The type of the underlying digraph.

2724

    typedef GR Digraph;

2725

    /// The type of the capacity map.

2726

    typedef CM CapacityMap;

2727

    /// The type of the flow map.

2728

    typedef FM FlowMap;

2729

    /// The tolerance type.

2730

    typedef TL Tolerance;

    typedef typename CapacityMap::Value Value;

2519

2733

    typedef Residual Adaptor;

  protected:

    typedef Undirector<const Digraph> Undirected;

    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,

2526

2740

                                            FlowMap, Tolerance> ForwardFilter;

    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,

2529

2743

                                             FlowMap, Tolerance> BackwardFilter;

    typedef typename Undirected::

2532

    template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;

2746

      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;

    typedef FilterArcs<Undirected, ArcFilter> Parent;

    const CapacityMap* _capacity;

2537

2751

    FlowMap* _flow;

    Undirected _graph;

2540

2754

    ForwardFilter _forward_filter;

2541

2755

    BackwardFilter _backward_filter;

2542

2756

    ArcFilter _arc_filter;

  public:

2545

2759

2546

    /// \brief Constructor of the residual digraph.

2760

    /// \brief Constructor

2547

2761

///

2548

    /// Constructor of the residual graph. The parameters are the digraph,

2549

    /// the flow map, the capacity map and a tolerance object.

2762

    /// Constructor of the residual digraph adaptor. The parameters are the

2763

    /// digraph, the capacity map, the flow map, and a tolerance object.

2550

2764

    Residual(const Digraph& digraph, const CapacityMap& capacity,

2551

2765

             FlowMap& flow, const Tolerance& tolerance = Tolerance())

2552

2766

      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),

2553

2767

        _forward_filter(capacity, flow, tolerance),

2554

2768

        _backward_filter(capacity, flow, tolerance),

2555

2769

        _arc_filter(_forward_filter, _backward_filter)

      Parent::setDigraph(_graph);

2558

2772

      Parent::setArcFilterMap(_arc_filter);

    typedef typename Parent::Arc Arc;

2562

2776

2563

    /// \brief Gives back the residual capacity of the arc.

2777

    /// \brief Returns the residual capacity of the given arc.

2564

2778

///

2565

    /// Gives back the residual capacity of the arc.

2779

    /// Returns the residual capacity of the given arc.

2566

2780

    Value residualCapacity(const Arc& a) const {

2567

2781

      if (Undirected::direction(a)) {

2568

2782

        return (*_capacity)[a] - (*_flow)[a];

2569

2783

      } else {

2570

2784

        return (*_flow)[a];

    /// \brief Augment on the given arc in the residual graph.

2788

    /// \brief Augments on the given arc in the residual digraph.

2575

2789

///

2576

    /// Augment on the given arc in the residual graph. It increase

2577

    /// or decrease the flow on the original arc depend on the direction

2578

    /// of the residual arc.

2790

    /// Augments on the given arc in the residual digraph. It increases

2791

    /// or decreases the flow value on the original arc according to the

2792

    /// direction of the residual arc.

2579

2793

    void augment(const Arc& a, const Value& v) const {

2580

2794

      if (Undirected::direction(a)) {

2581

2795

        _flow->set(a, (*_flow)[a] + v);

2582

2796

      } else {

2583

2797

        _flow->set(a, (*_flow)[a] - v);

    /// \brief Returns the direction of the arc.

2801

    /// \brief Returns \c true if the given residual arc is a forward arc.

2588

2802

///

2589

    /// Returns true when the arc is same oriented as the original arc.

2803

    /// Returns \c true if the given residual arc has the same orientation

2804

    /// as the original arc, i.e. it is a so called forward arc.

2590

2805

    static bool forward(const Arc& a) {

2591

2806

      return Undirected::direction(a);

    /// \brief Returns the direction of the arc.

2809

    /// \brief Returns \c true if the given residual arc is a backward arc.

2595

2810

///

2596

    /// Returns true when the arc is opposite oriented as the original arc.

2811

    /// Returns \c true if the given residual arc has the opposite orientation

2812

    /// than the original arc, i.e. it is a so called backward arc.

2597

2813

    static bool backward(const Arc& a) {

2598

2814

      return !Undirected::direction(a);

    /// \brief Gives back the forward oriented residual arc.

2817

    /// \brief Returns the forward oriented residual arc.

2602

2818

///

2603

    /// Gives back the forward oriented residual arc.

2819

    /// Returns the forward oriented residual arc related to the given

2820

    /// arc of the underlying digraph.

2604

2821

    static Arc forward(const typename Digraph::Arc& a) {

2605

2822

      return Undirected::direct(a, true);

    /// \brief Gives back the backward oriented residual arc.

2825

    /// \brief Returns the backward oriented residual arc.

2609

2826

///

2610

    /// Gives back the backward oriented residual arc.

2827

    /// Returns the backward oriented residual arc related to the given

2828

    /// arc of the underlying digraph.

2611

2829

    static Arc backward(const typename Digraph::Arc& a) {

2612

2830

      return Undirected::direct(a, false);

    /// \brief Residual capacity map.

2616

2834

///

2617

    /// In generic residual graph the residual capacity can be obtained

2618

    /// as a map.

2835

    /// This map adaptor class can be used for obtaining the residual

2836

    /// capacities as an arc map of the residual digraph.

2837

    /// Its value type is inherited from the capacity map.

2619

2838

    class ResidualCapacity {

2620

2839

    protected:

2621

2840

      const Adaptor* _adaptor;

2622

2841

    public:

2623

      /// The Key type

2842

      /// The key type of the map

2624

2843

      typedef Arc Key;

2625

      /// The Value type

2626

      typedef typename _CapacityMap::Value Value;

2844

      /// The value type of the map

2845

      typedef typename CapacityMap::Value Value;

      /// Constructor

2629

2848

      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}

2630

2849

2631

      /// \e

2850

      /// Returns the value associated with the given residual arc

2632

2851

      Value operator[](const Arc& a) const {

2633

2852

        return _adaptor->residualCapacity(a);

};

2637

2856

2857

    /// \brief Returns a residual capacity map

2858

///

2859

    /// This function just returns a residual capacity map.

2860

    ResidualCapacity residualCapacity() const {

2861

      return ResidualCapacity(*this);

};

2639

2865

2866

  /// \brief Returns a (read-only) Residual adaptor

2867

///

2868

  /// This function just returns a (read-only) \ref Residual adaptor.

2869

  /// \ingroup graph_adaptors

2870

  /// \relates Residual

2871

  template<typename GR, typename CM, typename FM>

2872

  Residual<GR, CM, FM> residual(const GR& digraph,

2873

                                const CM& capacity_map,

2874

                                FM& flow_map) {

2875

    return Residual<GR, CM, FM> (digraph, capacity_map, flow_map);

  template <typename _Digraph>

2641

2880

  class SplitNodesBase {

2642

2881

  public:

    typedef _Digraph Digraph;

2645

2884

    typedef DigraphAdaptorBase<const _Digraph> Parent;

2646

2885

    typedef SplitNodesBase Adaptor;

    typedef typename Digraph::Node DigraphNode;

2649

2888

    typedef typename Digraph::Arc DigraphArc;

    class Node;

...

@@ -2875,123 +3114,125 @@

2875

3114

      return Node(n, false);

    static Arc arc(const DigraphNode& n) {

2879

3118

      return Arc(n);

    static Arc arc(const DigraphArc& e) {

2883

3122

      return Arc(e);

    typedef True NodeNumTag;

2887

2888

3126

    int nodeNum() const {

2889

3127

      return  2 * countNodes(*_digraph);

    typedef True EdgeNumTag;

3130

    typedef True ArcNumTag;

2893

3131

    int arcNum() const {

2894

3132

      return countArcs(*_digraph) + countNodes(*_digraph);

    typedef True FindEdgeTag;

3135

    typedef True FindArcTag;

2898

3136

    Arc findArc(const Node& u, const Node& v,

2899

3137

                const Arc& prev = INVALID) const {

2900

      if (inNode(u)) {

2901

        if (outNode(v)) {

2902

          if (static_cast<const DigraphNode&>(u) ==

2903

              static_cast<const DigraphNode&>(v) && prev == INVALID) {

2904

            return Arc(u);

2905

3138

      if (inNode(u) && outNode(v)) {

3139

        if (static_cast<const DigraphNode&>(u) ==

3140

            static_cast<const DigraphNode&>(v) && prev == INVALID) {

3141

          return Arc(u);

2906

3142

2907

      } else {

2908

        if (inNode(v)) {

2909

          return Arc(::lemon::findArc(*_digraph, u, v, prev));

2910

3143

3144

      else if (outNode(u) && inNode(v)) {

3145

        return Arc(::lemon::findArc(*_digraph, u, v, prev));

      return INVALID;

  private:

    template <typename _Value>

2918

3153

    class NodeMapBase

2919

3154

      : public MapTraits<typename Parent::template NodeMap<_Value> > {

2920

3155

      typedef typename Parent::template NodeMap<_Value> NodeImpl;

2921

3156

    public:

2922

3157

      typedef Node Key;

2923

3158

      typedef _Value Value;

3159

      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;

3160

      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;

3161

      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;

3162

      typedef typename MapTraits<NodeImpl>::ReturnValue Reference;

3163

      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;

      NodeMapBase(const Adaptor& adaptor)

2926

3166

        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}

2927

3167

      NodeMapBase(const Adaptor& adaptor, const Value& value)

2928

3168

        : _in_map(*adaptor._digraph, value),

2929

3169

          _out_map(*adaptor._digraph, value) {}

      void set(const Node& key, const Value& val) {

2932

3172

        if (Adaptor::inNode(key)) { _in_map.set(key, val); }

2933

3173

        else {_out_map.set(key, val); }

      typename MapTraits<NodeImpl>::ReturnValue

2937

      operator[](const Node& key) {

3176

      ReturnValue operator[](const Node& key) {

2938

3177

        if (Adaptor::inNode(key)) { return _in_map[key]; }

2939

3178

        else { return _out_map[key]; }

      typename MapTraits<NodeImpl>::ConstReturnValue

2943

      operator[](const Node& key) const {

3181

      ConstReturnValue operator[](const Node& key) const {

2944

3182

        if (Adaptor::inNode(key)) { return _in_map[key]; }

2945

3183

        else { return _out_map[key]; }

    private:

2949

3187

      NodeImpl _in_map, _out_map;

2950

3188

};

    template <typename _Value>

2953

3191

    class ArcMapBase

2954

3192

      : public MapTraits<typename Parent::template ArcMap<_Value> > {

2955

3193

      typedef typename Parent::template ArcMap<_Value> ArcImpl;

2956

3194

      typedef typename Parent::template NodeMap<_Value> NodeImpl;

2957

3195

    public:

2958

3196

      typedef Arc Key;

2959

3197

      typedef _Value Value;

3198

      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;

3199

      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;

3200

      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;

3201

      typedef typename MapTraits<ArcImpl>::ReturnValue Reference;

3202

      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;

      ArcMapBase(const Adaptor& adaptor)

2962

3205

        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}

2963

3206

      ArcMapBase(const Adaptor& adaptor, const Value& value)

2964

3207

        : _arc_map(*adaptor._digraph, value),

2965

3208

          _node_map(*adaptor._digraph, value) {}

      void set(const Arc& key, const Value& val) {

2968

3211

        if (Adaptor::origArc(key)) {

2969

3212

          _arc_map.set(key._item.first(), val);

2970

3213

        } else {

2971

3214

          _node_map.set(key._item.second(), val);

      typename MapTraits<ArcImpl>::ReturnValue

2976

      operator[](const Arc& key) {

3218

      ReturnValue operator[](const Arc& key) {

2977

3219

        if (Adaptor::origArc(key)) {

2978

3220

          return _arc_map[key._item.first()];

2979

3221

        } else {

2980

3222

          return _node_map[key._item.second()];

      typename MapTraits<ArcImpl>::ConstReturnValue

2985

      operator[](const Arc& key) const {

3226

      ConstReturnValue operator[](const Arc& key) const {

2986

3227

        if (Adaptor::origArc(key)) {

2987

3228

          return _arc_map[key._item.first()];

2988

3229

        } else {

2989

3230

          return _node_map[key._item.second()];

    private:

2994

3235

      ArcImpl _arc_map;

2995

3236

      NodeImpl _node_map;

2996

3237

};

2997

3238

...

@@ -3054,180 +3295,198 @@

3054

3295

    SplitNodesBase() : _digraph(0) {}

    Digraph* _digraph;

    void setDigraph(Digraph& digraph) {

3059

3300

      _digraph = &digraph;

};

  /// \ingroup graph_adaptors

3065

3306

///

3066

  /// \brief Split the nodes of a directed graph

3307

  /// \brief Adaptor class for splitting the nodes of a digraph.

3067

3308

///

3068

  /// The SplitNodes adaptor splits each node into an in-node and an

3069

  /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in

3070

  /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node

3071

  /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the

3072

  /// original digraph the new target of the arc will be \f$ u_{in} \f$

3073

  /// and similarly the source of the original \f$ (u, v) \f$ arc

3074

  /// will be \f$ u_{out} \f$.  The adaptor will add for each node in

3075

  /// the original digraph an additional arc which connects

3076

  /// \f$ (u_{in}, u_{out}) \f$.

3309

  /// SplitNodes adaptor can be used for splitting each node into an

3310

  /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor

3311

  /// replaces each node \f$ u \f$ in the digraph with two nodes,

3312

  /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.

3313

  /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the

3314

  /// new target of the arc will be \f$ u_{in} \f$ and similarly the

3315

  /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.

3316

  /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$

3317

  /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.

3077

3318

///

3078

  /// The aim of this class is to run algorithm with node costs if the

3079

  /// algorithm can use directly just arc costs. In this case we should use

3080

  /// a \c SplitNodes and set the node cost of the graph to the

3081

  /// bind arc in the adapted graph.

3319

  /// The aim of this class is running an algorithm with respect to node

3320

  /// costs or capacities if the algorithm considers only arc costs or

3321

  /// capacities directly.

3322

  /// In this case you can use \c SplitNodes adaptor, and set the node

3323

  /// costs/capacities of the original digraph to the \e bind \e arcs

3324

  /// in the adaptor.

3082

3325

///

3083

  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph

3084

  /// "Digraph concept". The type can be specified to be const.

3085

  template <typename _Digraph>

3326

  /// \tparam GR The type of the adapted digraph.

3327

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

3328

  /// It is implicitly \c const.

3329

///

3330

  /// \note The \c Node type of this adaptor is converible to the \c Node

3331

  /// type of the adapted digraph.

3332

  template <typename GR>

3333

#ifdef DOXYGEN

3334

  class SplitNodes {

3335

#else

3086

3336

  class SplitNodes

3087

    : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {

3337

    : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {

3338

#endif

3088

3339

  public:

3089

    typedef _Digraph Digraph;

3090

    typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;

3340

    typedef GR Digraph;

3341

    typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;

    typedef typename Digraph::Node DigraphNode;

3093

3344

    typedef typename Digraph::Arc DigraphArc;

    typedef typename Parent::Node Node;

3096

3347

    typedef typename Parent::Arc Arc;

3097

3348

3098

    /// \brief Constructor of the adaptor.

3349

    /// \brief Constructor

3099

3350

///

3100

3351

    /// Constructor of the adaptor.

3101

    SplitNodes(Digraph& g) {

3352

    SplitNodes(const Digraph& g) {

3102

3353

      Parent::setDigraph(g);

    /// \brief Returns true when the node is in-node.

3356

    /// \brief Returns \c true if the given node is an in-node.

3106

3357

///

3107

    /// Returns true when the node is in-node.

3358

    /// Returns \c true if the given node is an in-node.

3108

3359

    static bool inNode(const Node& n) {

3109

3360

      return Parent::inNode(n);

    /// \brief Returns true when the node is out-node.

3363

    /// \brief Returns \c true if the given node is an out-node.

3113

3364

///

3114

    /// Returns true when the node is out-node.

3365

    /// Returns \c true if the given node is an out-node.

3115

3366

    static bool outNode(const Node& n) {

3116

3367

      return Parent::outNode(n);

    /// \brief Returns true when the arc is arc in the original digraph.

3370

    /// \brief Returns \c true if the given arc is an original arc.

3120

3371

///

3121

    /// Returns true when the arc is arc in the original digraph.

3372

    /// Returns \c true if the given arc is one of the arcs in the

3373

    /// original digraph.

3122

3374

    static bool origArc(const Arc& a) {

3123

3375

      return Parent::origArc(a);

    /// \brief Returns true when the arc binds an in-node and an out-node.

3378

    /// \brief Returns \c true if the given arc is a bind arc.

3127

3379

///

3128

    /// Returns true when the arc binds an in-node and an out-node.

3380

    /// Returns \c true if the given arc is a bind arc, i.e. it connects

3381

    /// an in-node and an out-node.

3129

3382

    static bool bindArc(const Arc& a) {

3130

3383

      return Parent::bindArc(a);

    /// \brief Gives back the in-node created from the \c node.

3386

    /// \brief Returns the in-node created from the given original node.

3134

3387

///

3135

    /// Gives back the in-node created from the \c node.

3388

    /// Returns the in-node created from the given original node.

3136

3389

    static Node inNode(const DigraphNode& n) {

3137

3390

      return Parent::inNode(n);

    /// \brief Gives back the out-node created from the \c node.

3393

    /// \brief Returns the out-node created from the given original node.

3141

3394

///

3142

    /// Gives back the out-node created from the \c node.

3395

    /// Returns the out-node created from the given original node.

3143

3396

    static Node outNode(const DigraphNode& n) {

3144

3397

      return Parent::outNode(n);

    /// \brief Gives back the arc binds the two part of the node.

3400

    /// \brief Returns the bind arc that corresponds to the given

3401

    /// original node.

3148

3402

///

3149

    /// Gives back the arc binds the two part of the node.

3403

    /// Returns the bind arc in the adaptor that corresponds to the given

3404

    /// original node, i.e. the arc connecting the in-node and out-node

3405

    /// of \c n.

3150

3406

    static Arc arc(const DigraphNode& n) {

3151

3407

      return Parent::arc(n);

    /// \brief Gives back the arc of the original arc.

3410

    /// \brief Returns the arc that corresponds to the given original arc.

3155

3411

///

3156

    /// Gives back the arc of the original arc.

3412

    /// Returns the arc in the adaptor that corresponds to the given

3413

    /// original arc.

3157

3414

    static Arc arc(const DigraphArc& a) {

3158

3415

      return Parent::arc(a);

    /// \brief NodeMap combined from two original NodeMap

3418

    /// \brief Node map combined from two original node maps

3162

3419

///

3163

    /// This class adapt two of the original digraph NodeMap to

3164

    /// get a node map on the adapted digraph.

3420

    /// This map adaptor class adapts two node maps of the original digraph

3421

    /// to get a node map of the split digraph.

3422

    /// Its value type is inherited from the first node map type

3423

    /// (\c InNodeMap).

3165

3424

    template <typename InNodeMap, typename OutNodeMap>

3166

3425

    class CombinedNodeMap {

3167

3426

    public:

3168

3427

3428

      /// The key type of the map

3169

3429

      typedef Node Key;

3430

      /// The value type of the map

3170

3431

      typedef typename InNodeMap::Value Value;

3171

3432

3172

      /// \brief Constructor

3173

///

3174

      /// Constructor.

3433

      typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;

3434

      typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;

3435

      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;

3436

      typedef typename MapTraits<InNodeMap>::ReturnValue Reference;

3437

      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;

3438

3439

      /// Constructor

3175

3440

      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)

3176

3441

        : _in_map(in_map), _out_map(out_map) {}

3177

3442

3178

      /// \brief The subscript operator.

3179

///

3180

      /// The subscript operator.

3443

      /// Returns the value associated with the given key.

3444

      Value operator[](const Key& key) const {

3445

        if (Parent::inNode(key)) {

3446

          return _in_map[key];

3447

        } else {

3448

          return _out_map[key];

      /// Returns a reference to the value associated with the given key.

3181

3453

      Value& operator[](const Key& key) {

3182

3454

        if (Parent::inNode(key)) {

3183

3455

          return _in_map[key];

3184

3456

        } else {

3185

3457

          return _out_map[key];

      /// \brief The const subscript operator.

3190

///

3191

      /// The const subscript operator.

3192

      Value operator[](const Key& key) const {

3193

        if (Parent::inNode(key)) {

3194

          return _in_map[key];

3195

        } else {

3196

          return _out_map[key];

      /// \brief The setter function of the map.

3201

///

3202

      /// The setter function of the map.

3461

      /// Sets the value associated with the given key.

3203

3462

      void set(const Key& key, const Value& value) {

3204

3463

        if (Parent::inNode(key)) {

3205

3464

          _in_map.set(key, value);

3206

3465

        } else {

3207

3466

          _out_map.set(key, value);

    private:

      InNodeMap& _in_map;

3214

3473

      OutNodeMap& _out_map;

};

    /// \brief Just gives back a combined node map

3478

    /// \brief Returns a combined node map

3220

3479

///

3221

    /// Just gives back a combined node map

3480

    /// This function just returns a combined node map.

3222

3481

    template <typename InNodeMap, typename OutNodeMap>

3223

3482

    static CombinedNodeMap<InNodeMap, OutNodeMap>

3224

3483

    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {

3225

3484

      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);

    template <typename InNodeMap, typename OutNodeMap>

3229

3488

    static CombinedNodeMap<const InNodeMap, OutNodeMap>

3230

3489

    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {

3231

3490

      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);

@@ -3235,113 +3494,113 @@

3235

3494

    static CombinedNodeMap<InNodeMap, const OutNodeMap>

3236

3495

    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {

3237

3496

      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);

    template <typename InNodeMap, typename OutNodeMap>

3241

3500

    static CombinedNodeMap<const InNodeMap, const OutNodeMap>

3242

3501

    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {

3243

3502

      return CombinedNodeMap<const InNodeMap,

3244

3503

        const OutNodeMap>(in_map, out_map);

    /// \brief ArcMap combined from an original ArcMap and a NodeMap

3506

    /// \brief Arc map combined from an arc map and a node map of the

3507

    /// original digraph.

3248

3508

///

3249

    /// This class adapt an original ArcMap and a NodeMap to get an

3250

    /// arc map on the adapted digraph

3251

    template <typename DigraphArcMap, typename DigraphNodeMap>

3509

    /// This map adaptor class adapts an arc map and a node map of the

3510

    /// original digraph to get an arc map of the split digraph.

3511

    /// Its value type is inherited from the original arc map type

3512

    /// (\c ArcMap).

3513

    template <typename ArcMap, typename NodeMap>

3252

3514

    class CombinedArcMap {

3253

3515

    public:

3254

3516

3517

      /// The key type of the map

3255

3518

      typedef Arc Key;

3256

      typedef typename DigraphArcMap::Value Value;

3257

3258

      /// \brief Constructor

3259

///

3260

      /// Constructor.

3261

      CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)

3519

      /// The value type of the map

3520

      typedef typename ArcMap::Value Value;

3521

3522

      typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;

3523

      typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;

3524

      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;

3525

      typedef typename MapTraits<ArcMap>::ReturnValue Reference;

3526

      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;

3527

3528

      /// Constructor

3529

      CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)

3262

3530

        : _arc_map(arc_map), _node_map(node_map) {}

3263

3531

3264

      /// \brief The subscript operator.

3265

///

3266

      /// The subscript operator.

3532

      /// Returns the value associated with the given key.

3533

      Value operator[](const Key& arc) const {

3534

        if (Parent::origArc(arc)) {

3535

          return _arc_map[arc];

3536

        } else {

3537

          return _node_map[arc];

      /// Returns a reference to the value associated with the given key.

3542

      Value& operator[](const Key& arc) {

3543

        if (Parent::origArc(arc)) {

3544

          return _arc_map[arc];

3545

        } else {

3546

          return _node_map[arc];

      /// Sets the value associated with the given key.

3267

3551

      void set(const Arc& arc, const Value& val) {

3268

3552

        if (Parent::origArc(arc)) {

3269

3553

          _arc_map.set(arc, val);

3270

3554

        } else {

3271

3555

          _node_map.set(arc, val);

      /// \brief The const subscript operator.

3276

///

3277

      /// The const subscript operator.

3278

      Value operator[](const Key& arc) const {

3279

        if (Parent::origArc(arc)) {

3280

          return _arc_map[arc];

3281

        } else {

3282

          return _node_map[arc];

      /// \brief The const subscript operator.

3287

///

3288

      /// The const subscript operator.

3289

      Value& operator[](const Key& arc) {

3290

        if (Parent::origArc(arc)) {

3291

          return _arc_map[arc];

3292

        } else {

3293

          return _node_map[arc];

    private:

3298

      DigraphArcMap& _arc_map;

3299

      DigraphNodeMap& _node_map;

3560

      ArcMap& _arc_map;

3561

      NodeMap& _node_map;

3300

3562

};

3301

3563

3302

    /// \brief Just gives back a combined arc map

3564

    /// \brief Returns a combined arc map

3303

3565

///

3304

    /// Just gives back a combined arc map

3305

    template <typename DigraphArcMap, typename DigraphNodeMap>

3306

    static CombinedArcMap<DigraphArcMap, DigraphNodeMap>

3307

    combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {

3308

      return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);

3566

    /// This function just returns a combined arc map.

3567

    template <typename ArcMap, typename NodeMap>

3568

    static CombinedArcMap<ArcMap, NodeMap>

3569

    combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {

3570

      return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);

    template <typename DigraphArcMap, typename DigraphNodeMap>

3312

    static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>

3313

    combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {

3314

      return CombinedArcMap<const DigraphArcMap,

3315

        DigraphNodeMap>(arc_map, node_map);

3573

    template <typename ArcMap, typename NodeMap>

3574

    static CombinedArcMap<const ArcMap, NodeMap>

3575

    combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {

3576

      return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);

    template <typename DigraphArcMap, typename DigraphNodeMap>

3319

    static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>

3320

    combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {

3321

      return CombinedArcMap<DigraphArcMap,

3322

        const DigraphNodeMap>(arc_map, node_map);

3579

    template <typename ArcMap, typename NodeMap>

3580

    static CombinedArcMap<ArcMap, const NodeMap>

3581

    combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {

3582

      return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);

    template <typename DigraphArcMap, typename DigraphNodeMap>

3326

    static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>

3327

    combinedArcMap(const DigraphArcMap& arc_map,

3328

                   const DigraphNodeMap& node_map) {

3329

      return CombinedArcMap<const DigraphArcMap,

3330

        const DigraphNodeMap>(arc_map, node_map);

3585

    template <typename ArcMap, typename NodeMap>

3586

    static CombinedArcMap<const ArcMap, const NodeMap>

3587

    combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {

3588

      return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);

};

3334

3592

3335

  /// \brief Just gives back a node splitter

3593

  /// \brief Returns a (read-only) SplitNodes adaptor

3336

3594

///

3337

  /// Just gives back a node splitter

3338

  template<typename Digraph>

3339

  SplitNodes<Digraph>

3340

  splitNodes(const Digraph& digraph) {

3341

    return SplitNodes<Digraph>(digraph);

3595

  /// This function just returns a (read-only) \ref SplitNodes adaptor.

3596

  /// \ingroup graph_adaptors

3597

  /// \relates SplitNodes

3598

  template<typename GR>

3599

  SplitNodes<GR>

3600

  splitNodes(const GR& digraph) {

3601

    return SplitNodes<GR>(digraph);

} //namespace lemon

#endif //LEMON_ADAPTORS_H

RhodeCode

Login to your account

@@ -53,91 +53,94 @@
 		LEMON also provides a variety of graphs for these requirements called
 		\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
 		in conjunction with other graph representations.
 		You are free to use the graph structure that fit your requirements
 		the best, most graph algorithms and auxiliary data structures can be used
 		with any graph structure.
 		<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
-		@defgroup graph_adaptors Adaptor Classes for graphs
+		@defgroup graph_adaptors Adaptor Classes for Graphs
 		@ingroup graphs
-		\brief This group contains several adaptor classes for digraphs and graphs
+		\brief Adaptor classes for digraphs and graphs
 		This group contains several useful adaptor classes for digraphs and graphs.
 		The main parts of LEMON are the different graph structures, generic
-		graph algorithms, graph concepts which couple these, and graph
+		graph algorithms, graph concepts, which couple them, and graph
 		adaptors. While the previous notions are more or less clear, the
 		latter one needs further explanation. Graph adaptors are graph classes
 		which serve for considering graph structures in different ways.
 		A short example makes this much clearer.  Suppose that we have an
 		instance \c g of a directed graph type say ListDigraph and an algorithm
+		instance \c g of a directed graph type, say ListDigraph and an algorithm
 		\code
 		template <typename Digraph>
 		int algorithm(const Digraph&);
 		\endcode
 		is needed to run on the reverse oriented graph.  It may be expensive
 		(in time or in memory usage) to copy \c g with the reversed
 		arcs.  In this case, an adaptor class is used, which (according
 		to LEMON digraph concepts) works as a digraph.  The adaptor uses the
 		original digraph structure and digraph operations when methods of the
 		reversed oriented graph are called.  This means that the adaptor have
 		minor memory usage, and do not perform sophisticated algorithmic
 		to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
 		The adaptor uses the original digraph structure and digraph operations when
 		methods of the reversed oriented graph are called.  This means that the adaptor
 		have minor memory usage, and do not perform sophisticated algorithmic
 		actions.  The purpose of it is to give a tool for the cases when a
 		graph have to be used in a specific alteration.  If this alteration is
-		obtained by a usual construction like filtering the arc-set or
+		obtained by a usual construction like filtering the node or the arc set or
 		considering a new orientation, then an adaptor is worthwhile to use.
 		To come back to the reverse oriented graph, in this situation
 		\code
 		template<typename Digraph> class ReverseDigraph;
 		\endcode
 		template class can be used. The code looks as follows
 		\code
 		ListDigraph g;
-		ReverseDigraph<ListGraph> rg(g);
+		ReverseDigraph<ListDigraph> rg(g);
 		int result = algorithm(rg);
 		\endcode
 		After running the algorithm, the original graph \c g is untouched.
 		This techniques gives rise to an elegant code, and based on stable
 		During running the algorithm, the original digraph \c g is untouched.
 		This techniques give rise to an elegant code, and based on stable
 		graph adaptors, complex algorithms can be implemented easily.
-		In flow, circulation and bipartite matching problems, the residual
 		In flow, circulation and matching problems, the residual
 		graph is of particular importance. Combining an adaptor implementing
-		this, shortest path algorithms and minimum mean cycle algorithms,
+		this with shortest path algorithms or minimum mean cycle algorithms,
 		a range of weighted and cardinality optimization algorithms can be
 		obtained. For other examples, the interested user is referred to the
 		detailed documentation of particular adaptors.
 		The behavior of graph adaptors can be very different. Some of them keep
 		capabilities of the original graph while in other cases this would be
 		meaningless. This means that the concepts that they are models of depend
 		on the graph adaptor, and the wrapped graph(s).
 		If an arc of \c rg is deleted, this is carried out by deleting the
 		corresponding arc of \c g, thus the adaptor modifies the original graph.
 		meaningless. This means that the concepts that they meet depend
 		on the graph adaptor, and the wrapped graph.
 		For example, if an arc of a reversed digraph is deleted, this is carried
 		out by deleting the corresponding arc of the original digraph, thus the
 		adaptor modifies the original digraph.
 		However in case of a residual digraph, this operation has no sense.
 		But for a residual graph, this operation has no sense.
 		Let us stand one more example here to simplify your work.
-		RevGraphAdaptor has constructor
+		ReverseDigraph has constructor
 		\code
 		ReverseDigraph(Digraph& digraph);
 		\endcode
 		This means that in a situation, when a <tt>const ListDigraph&</tt>
+		This means that in a situation, when a <tt>const %ListDigraph&</tt>
 		reference to a graph is given, then it have to be instantiated with
 		<tt>Digraph=const ListDigraph</tt>.
+		<tt>Digraph=const %ListDigraph</tt>.
 		\code
 		int algorithm1(const ListDigraph& g) {
-		  RevGraphAdaptor<const ListDigraph> rg(g);
+		  ReverseDigraph<const ListDigraph> rg(g);
 		  return algorithm2(rg);
+		}
 		\endcode
 		*/
 		/**
 		@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
 		@ingroup graphs
 		\brief Graph types between real graphs and graph adaptors.
 		This group describes some graph types between real graphs and graph adaptors.
 		These classes wrap graphs to give new functionality as the adaptors do it.

@@ -164,28 +164,24 @@
 		      return Parent::target(e);
+		    }
 		    Node baseNode(const InArcIt &e) const {
 		      return Parent::target(e);
+		    }
 		    Node runningNode(const InArcIt &e) const {
 		      return Parent::source(e);
+		    }
 		  };
 		  /// \ingroup digraphbits
 		  ///
 		  /// \brief Extender for the GraphAdaptors
 		  template <typename _Graph>
 		  class GraphAdaptorExtender : public _Graph {
 		  public:
 		    typedef _Graph Parent;
 		    typedef _Graph Graph;
 		    typedef GraphAdaptorExtender Adaptor;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;