LEMON/LEMON-official Changeset - r703:cb38ccedd2c1

/* -*- mode: C++; indent-tabs-mode: nil; -*-

2

3

 * This file is a part of LEMON, a generic C++ optimization library.

4

5

 * Copyright (C) 2003-2009

6

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

7

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

8

9

 * Permission to use, modify and distribute this software is granted

10

 * provided that this copyright notice appears in all copies. For

11

 * precise terms see the accompanying LICENSE file.

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 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/bits/map_extender.h>

34

#include <lemon/tolerance.h>

35

36

#include <algorithm>

37

38

namespace lemon {

39

40

#ifdef _MSC_VER

41

#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED

42

#else

43

#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED

44

#endif

45

46

  template<typename DGR>

47

  class DigraphAdaptorBase {

48

  public:

49

    typedef DGR Digraph;

50

    typedef DigraphAdaptorBase Adaptor;

51

52

  protected:

53

    DGR* _digraph;

54

    DigraphAdaptorBase() : _digraph(0) { }

55

    void initialize(DGR& digraph) { _digraph = &digraph; }

56

57

  public:

58

    DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }

59

60

    typedef typename DGR::Node Node;

61

    typedef typename DGR::Arc Arc;

62

63

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

64

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

65

    void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }

66

    void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }

67

68

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

69

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

70

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

71

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

72

73

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

74

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

75

76

    typedef NodeNumTagIndicator<DGR> NodeNumTag;

77

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

78

79

    typedef ArcNumTagIndicator<DGR> ArcNumTag;

80

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

81

82

    typedef FindArcTagIndicator<DGR> FindArcTag;

83

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

84

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

85

86

87

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

88

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

89

90

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

91

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

92

93

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

94

95

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

96

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

97

98

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

99

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

100

101

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

102

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

103

104

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

105

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

106

107

    typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;

108

    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }

109

110

    template <typename V>

111

    class NodeMap : public DGR::template NodeMap<V> {

112

      typedef typename DGR::template NodeMap<V> Parent;

113

114

    public:

115

      explicit NodeMap(const Adaptor& adaptor)

116

        : Parent(*adaptor._digraph) {}

117

      NodeMap(const Adaptor& adaptor, const V& value)

118

        : Parent(*adaptor._digraph, value) { }

119

120

    private:

121

      NodeMap& operator=(const NodeMap& cmap) {

122

        return operator=<NodeMap>(cmap);

123

124

125

      template <typename CMap>

126

      NodeMap& operator=(const CMap& cmap) {

127

        Parent::operator=(cmap);

128

        return *this;

129

130

131

};

132

133

    template <typename V>

134

    class ArcMap : public DGR::template ArcMap<V> {

135

      typedef typename DGR::template ArcMap<V> Parent;

136

137

    public:

138

      explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)

139

        : Parent(*adaptor._digraph) {}

140

      ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)

141

        : Parent(*adaptor._digraph, value) {}

142

143

    private:

144

      ArcMap& operator=(const ArcMap& cmap) {

145

        return operator=<ArcMap>(cmap);

146

147

148

      template <typename CMap>

149

      ArcMap& operator=(const CMap& cmap) {

150

        Parent::operator=(cmap);

151

        return *this;

152

153

154

};

155

156

};

157

158

  template<typename GR>

159

  class GraphAdaptorBase {

160

  public:

161

    typedef GR Graph;

162

163

  protected:

164

    GR* _graph;

165

166

    GraphAdaptorBase() : _graph(0) {}

167

168

    void initialize(GR& graph) { _graph = &graph; }

169

170

  public:

171

    GraphAdaptorBase(GR& graph) : _graph(&graph) {}

172

173

    typedef typename GR::Node Node;

174

    typedef typename GR::Arc Arc;

175

    typedef typename GR::Edge Edge;

176

177

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

178

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

179

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

180

    void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }

181

    void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }

182

    void firstInc(Edge &i, bool &d, const Node &n) const {

183

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

184

185

186

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

187

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

188

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

189

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

190

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

191

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

192

193

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

194

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

195

196

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

197

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

198

199

    typedef NodeNumTagIndicator<Graph> NodeNumTag;

200

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

201

202

    typedef ArcNumTagIndicator<Graph> ArcNumTag;

203

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

204

205

    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

206

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

207

208

    typedef FindArcTagIndicator<Graph> FindArcTag;

209

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

210

                const Arc& prev = INVALID) const {

211

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

212

213

214

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

215

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

216

                  const Edge& prev = INVALID) const {

217

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

218

219

220

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

221

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

222

223

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

224

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

225

226

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

227

228

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

229

    Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }

230

231

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

232

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

233

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

234

235

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

236

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

237

    Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }

238

239

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

240

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

241

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

242

243

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

244

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

245

246

    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;

247

    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }

248

249

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

250

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

251

252

    template <typename V>

253

    class NodeMap : public GR::template NodeMap<V> {

254

      typedef typename GR::template NodeMap<V> Parent;

255

256

    public:

257

      explicit NodeMap(const GraphAdaptorBase<GR>& adapter)

258

        : Parent(*adapter._graph) {}

259

      NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)

260

        : Parent(*adapter._graph, value) {}

261

262

    private:

263

      NodeMap& operator=(const NodeMap& cmap) {

264

        return operator=<NodeMap>(cmap);

265

266

267

      template <typename CMap>

268

      NodeMap& operator=(const CMap& cmap) {

269

        Parent::operator=(cmap);

270

        return *this;

271

272

273

};

274

275

    template <typename V>

276

    class ArcMap : public GR::template ArcMap<V> {

277

      typedef typename GR::template ArcMap<V> Parent;

278

279

    public:

280

      explicit ArcMap(const GraphAdaptorBase<GR>& adapter)

281

        : Parent(*adapter._graph) {}

282

      ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)

283

        : Parent(*adapter._graph, value) {}

284

285

    private:

286

      ArcMap& operator=(const ArcMap& cmap) {

287

        return operator=<ArcMap>(cmap);

288

289

290

      template <typename CMap>

291

      ArcMap& operator=(const CMap& cmap) {

292

        Parent::operator=(cmap);

293

        return *this;

294

295

};

296

297

    template <typename V>

298

    class EdgeMap : public GR::template EdgeMap<V> {

299

      typedef typename GR::template EdgeMap<V> Parent;

300

301

    public:

302

      explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)

303

        : Parent(*adapter._graph) {}

304

      EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)

305

        : Parent(*adapter._graph, value) {}

306

307

    private:

308

      EdgeMap& operator=(const EdgeMap& cmap) {

309

        return operator=<EdgeMap>(cmap);

310

311

312

      template <typename CMap>

313

      EdgeMap& operator=(const CMap& cmap) {

314

        Parent::operator=(cmap);

315

        return *this;

316

317

};

318

319

};

320

321

  template <typename DGR>

322

  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {

323

    typedef DigraphAdaptorBase<DGR> Parent;

324

  public:

325

    typedef DGR Digraph;

326

  protected:

327

    ReverseDigraphBase() : Parent() { }

328

  public:

329

    typedef typename Parent::Node Node;

330

    typedef typename Parent::Arc Arc;

331

332

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

333

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

334

335

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

336

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

337

338

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

339

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

340

341

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

342

343

    typedef FindArcTagIndicator<DGR> FindArcTag;

344

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

345

                const Arc& prev = INVALID) const {

346

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

347

348

349

};

350

351

  /// \ingroup graph_adaptors

352

///

353

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

354

  /// a digraph.

355

///

356

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

357

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

358

///

359

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

360

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

361

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

362

///

363

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

364

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

365

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

366

///

367

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

368

  /// digraph are convertible to each other.

369

  template<typename DGR>

370

#ifdef DOXYGEN

371

  class ReverseDigraph {

372

#else

373

  class ReverseDigraph :

374

    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {

375

#endif

376

    typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;

377

  public:

378

    /// The type of the adapted digraph.

379

    typedef DGR Digraph;

380

  protected:

381

    ReverseDigraph() { }

382

  public:

383

384

    /// \brief Constructor

385

///

386

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

387

    explicit ReverseDigraph(DGR& digraph) {

388

      Parent::initialize(digraph);

389

390

};

391

392

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

393

///

394

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

395

  /// \ingroup graph_adaptors

396

  /// \relates ReverseDigraph

397

  template<typename DGR>

398

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

399

    return ReverseDigraph<const DGR>(digraph);

  template <typename DGR, typename NF, typename AF, bool ch = true>

404

  class SubDigraphBase : public DigraphAdaptorBase<DGR> {

405

    typedef DigraphAdaptorBase<DGR> Parent;

406

  public:

407

    typedef DGR Digraph;

408

    typedef NF NodeFilterMap;

409

    typedef AF ArcFilterMap;

410

411

    typedef SubDigraphBase Adaptor;

412

  protected:

413

    NF* _node_filter;

414

    AF* _arc_filter;

415

    SubDigraphBase()

416

      : Parent(), _node_filter(0), _arc_filter(0) { }

417

418

    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {

419

      Parent::initialize(digraph);

420

      _node_filter = &node_filter;

421

      _arc_filter = &arc_filter;

422

423

424

  public:

425

426

    typedef typename Parent::Node Node;

427

    typedef typename Parent::Arc Arc;

428

429

    void first(Node& i) const {

430

      Parent::first(i);

431

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

432

433

434

    void first(Arc& i) const {

435

      Parent::first(i);

436

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

437

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

438

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

439

        Parent::next(i);

440

441

442

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

443

      Parent::firstIn(i, n);

444

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

445

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

446

        Parent::nextIn(i);

447

448

449

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

450

      Parent::firstOut(i, n);

451

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

452

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

453

        Parent::nextOut(i);

454

455

456

    void next(Node& i) const {

457

      Parent::next(i);

458

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

459

460

461

    void next(Arc& i) const {

462

      Parent::next(i);

463

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

464

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

465

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

466

        Parent::next(i);

467

468

469

    void nextIn(Arc& i) const {

470

      Parent::nextIn(i);

471

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

472

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

473

        Parent::nextIn(i);

474

475

476

    void nextOut(Arc& i) const {

477

      Parent::nextOut(i);

478

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

479

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

480

        Parent::nextOut(i);

481

482

483

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

484

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

485

486

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

487

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

488

489

    typedef False NodeNumTag;

490

    typedef False ArcNumTag;

491

492

    typedef FindArcTagIndicator<DGR> FindArcTag;

493

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

494

                const Arc& prev = INVALID) const {

495

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

496

        return INVALID;

497

498

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

499

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

500

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

501

502

      return arc;

503

504

505

  public:

506

507

    template <typename V>

508

    class NodeMap

509

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

510

	      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {

511

      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

512

	LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;

513

514

    public:

515

      typedef V Value;

516

517

      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)

518

        : Parent(adaptor) {}

519

      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)

520

        : Parent(adaptor, value) {}

521

522

    private:

523

      NodeMap& operator=(const NodeMap& cmap) {

524

        return operator=<NodeMap>(cmap);

525

526

527

      template <typename CMap>

528

      NodeMap& operator=(const CMap& cmap) {

529

        Parent::operator=(cmap);

530

        return *this;

531

532

};

533

534

    template <typename V>

535

    class ArcMap

536

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

537

	      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {

538

      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

539

        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;

540

541

    public:

542

      typedef V Value;

543

544

      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)

545

        : Parent(adaptor) {}

546

      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)

547

        : Parent(adaptor, value) {}

548

549

    private:

550

      ArcMap& operator=(const ArcMap& cmap) {

551

        return operator=<ArcMap>(cmap);

552

553

554

      template <typename CMap>

555

      ArcMap& operator=(const CMap& cmap) {

556

        Parent::operator=(cmap);

557

        return *this;

558

559

};

560

561

};

562

563

  template <typename DGR, typename NF, typename AF>

564

  class SubDigraphBase<DGR, NF, AF, false>

565

    : public DigraphAdaptorBase<DGR> {

566

    typedef DigraphAdaptorBase<DGR> Parent;

567

  public:

568

    typedef DGR Digraph;

569

    typedef NF NodeFilterMap;

570

    typedef AF ArcFilterMap;

571

572

    typedef SubDigraphBase Adaptor;

573

  protected:

574

    NF* _node_filter;

575

    AF* _arc_filter;

576

    SubDigraphBase()

577

      : Parent(), _node_filter(0), _arc_filter(0) { }

578

579

    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {

580

      Parent::initialize(digraph);

581

      _node_filter = &node_filter;

582

      _arc_filter = &arc_filter;

583

584

585

  public:

586

587

    typedef typename Parent::Node Node;

588

    typedef typename Parent::Arc Arc;

589

590

    void first(Node& i) const {

591

      Parent::first(i);

592

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

593

594

595

    void first(Arc& i) const {

596

      Parent::first(i);

597

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

598

599

600

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

601

      Parent::firstIn(i, n);

602

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

603

604

605

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

606

      Parent::firstOut(i, n);

607

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

608

609

610

    void next(Node& i) const {

611

      Parent::next(i);

612

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

613

614

    void next(Arc& i) const {

615

      Parent::next(i);

616

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

617

618

    void nextIn(Arc& i) const {

619

      Parent::nextIn(i);

620

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

621

622

623

    void nextOut(Arc& i) const {

624

      Parent::nextOut(i);

625

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

626

627

628

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

629

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

630

631

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

632

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

633

634

    typedef False NodeNumTag;

635

    typedef False ArcNumTag;

636

637

    typedef FindArcTagIndicator<DGR> FindArcTag;

638

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

639

                const Arc& prev = INVALID) const {

640

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

641

        return INVALID;

642

643

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

644

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

645

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

646

647

      return arc;

648

649

650

    template <typename V>

651

    class NodeMap

652

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

653

          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {

654

      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

655

        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;

656

657

    public:

658

      typedef V Value;

659

660

      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)

661

        : Parent(adaptor) {}

662

      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)

663

        : Parent(adaptor, value) {}

664

665

    private:

666

      NodeMap& operator=(const NodeMap& cmap) {

667

        return operator=<NodeMap>(cmap);

668

669

670

      template <typename CMap>

671

      NodeMap& operator=(const CMap& cmap) {

672

        Parent::operator=(cmap);

673

        return *this;

674

675

};

676

677

    template <typename V>

678

    class ArcMap

679

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

680

          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {

681

      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

682

        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;

683

684

    public:

685

      typedef V Value;

686

687

      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)

688

        : Parent(adaptor) {}

689

      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)

690

        : Parent(adaptor, value) {}

691

692

    private:

693

      ArcMap& operator=(const ArcMap& cmap) {

694

        return operator=<ArcMap>(cmap);

695

696

697

      template <typename CMap>

698

      ArcMap& operator=(const CMap& cmap) {

699

        Parent::operator=(cmap);

700

        return *this;

701

702

};

703

704

};

705

706

  /// \ingroup graph_adaptors

707

///

708

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

709

///

710

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

711

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

712

  /// define the filters for nodes and arcs.

713

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

714

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

715

  /// nodes are also filtered out.

716

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

717

///

718

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

719

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

720

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

721

///

722

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

723

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

724

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

725

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

726

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

727

  /// adapted digraph. The default type is

728

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

729

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

730

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

731

  /// adapted digraph. The default type is

732

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

733

///

734

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

735

  /// digraph are convertible to each other.

736

///

737

  /// \see FilterNodes

738

  /// \see FilterArcs

739

#ifdef DOXYGEN

740

  template<typename DGR, typename NF, typename AF>

741

  class SubDigraph {

742

#else

743

  template<typename DGR,

744

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

745

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

746

  class SubDigraph :

747

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

748

#endif

749

  public:

750

    /// The type of the adapted digraph.

751

    typedef DGR Digraph;

752

    /// The type of the node filter map.

753

    typedef NF NodeFilterMap;

754

    /// The type of the arc filter map.

755

    typedef AF ArcFilterMap;

756

757

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

758

      Parent;

759

760

    typedef typename Parent::Node Node;

761

    typedef typename Parent::Arc Arc;

762

763

  protected:

764

    SubDigraph() { }

765

  public:

766

767

    /// \brief Constructor

768

///

769

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

770

    /// given node and arc filter maps.

771

    SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {

772

      Parent::initialize(digraph, node_filter, arc_filter);

773

774

775

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

776

///

777

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

778

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

779

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

780

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

781

782

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

783

///

784

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

785

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

786

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

787

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

788

789

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

790

///

791

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

792

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

793

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

794

795

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

796

///

797

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

798

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

799

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

800

801

    /// \brief Disables the given node

802

///

803

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

804

    /// so the iteration jumps over it.

805

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

806

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

807

808

    /// \brief Disables the given arc

809

///

810

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

811

    /// so the iteration jumps over it.

812

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

813

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

814

815

    /// \brief Enables the given node

816

///

817

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

818

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

819

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

820

821

    /// \brief Enables the given arc

822

///

823

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

824

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

825

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

826

827

};

828

829

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

830

///

831

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

832

  /// \ingroup graph_adaptors

833

  /// \relates SubDigraph

834

  template<typename DGR, typename NF, typename AF>

835

  SubDigraph<const DGR, NF, AF>

836

  subDigraph(const DGR& digraph,

837

             NF& node_filter, AF& arc_filter) {

838

    return SubDigraph<const DGR, NF, AF>

839

      (digraph, node_filter, arc_filter);

840

841

842

  template<typename DGR, typename NF, typename AF>

843

  SubDigraph<const DGR, const NF, AF>

844

  subDigraph(const DGR& digraph,

845

             const NF& node_filter, AF& arc_filter) {

846

    return SubDigraph<const DGR, const NF, AF>

847

      (digraph, node_filter, arc_filter);

848

849

850

  template<typename DGR, typename NF, typename AF>

851

  SubDigraph<const DGR, NF, const AF>

852

  subDigraph(const DGR& digraph,

853

             NF& node_filter, const AF& arc_filter) {

854

    return SubDigraph<const DGR, NF, const AF>

855

      (digraph, node_filter, arc_filter);

856

857

858

  template<typename DGR, typename NF, typename AF>

859

  SubDigraph<const DGR, const NF, const AF>

860

  subDigraph(const DGR& digraph,

861

             const NF& node_filter, const AF& arc_filter) {

862

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

863

      (digraph, node_filter, arc_filter);

  template <typename GR, typename NF, typename EF, bool ch = true>

868

  class SubGraphBase : public GraphAdaptorBase<GR> {

869

    typedef GraphAdaptorBase<GR> Parent;

870

  public:

871

    typedef GR Graph;

872

    typedef NF NodeFilterMap;

873

    typedef EF EdgeFilterMap;

874

875

    typedef SubGraphBase Adaptor;

876

  protected:

877

878

    NF* _node_filter;

879

    EF* _edge_filter;

880

881

    SubGraphBase()

882

      : Parent(), _node_filter(0), _edge_filter(0) { }

883

884

    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {

885

      Parent::initialize(graph);

886

      _node_filter = &node_filter;

887

      _edge_filter = &edge_filter;

888

889

890

  public:

891

892

    typedef typename Parent::Node Node;

893

    typedef typename Parent::Arc Arc;

894

    typedef typename Parent::Edge Edge;

895

896

    void first(Node& i) const {

897

      Parent::first(i);

898

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

899

900

901

    void first(Arc& i) const {

902

      Parent::first(i);

903

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

904

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

905

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

906

        Parent::next(i);

907

908

909

    void first(Edge& i) const {

910

      Parent::first(i);

911

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

912

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

913

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

914

        Parent::next(i);

915

916

917

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

918

      Parent::firstIn(i, n);

919

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

920

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

921

        Parent::nextIn(i);

922

923

924

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

925

      Parent::firstOut(i, n);

926

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

927

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

928

        Parent::nextOut(i);

929

930

931

    void firstInc(Edge& i, bool& d, const Node& n) const {

932

      Parent::firstInc(i, d, n);

933

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

934

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

935

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

936

        Parent::nextInc(i, d);

937

938

939

    void next(Node& i) const {

940

      Parent::next(i);

941

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

942

943

944

    void next(Arc& i) const {

945

      Parent::next(i);

946

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

947

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

948

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

949

        Parent::next(i);

950

951

952

    void next(Edge& i) const {

953

      Parent::next(i);

954

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

955

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

956

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

957

        Parent::next(i);

958

959

960

    void nextIn(Arc& i) const {

961

      Parent::nextIn(i);

962

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

963

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

964

        Parent::nextIn(i);

965

966

967

    void nextOut(Arc& i) const {

968

      Parent::nextOut(i);

969

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

970

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

971

        Parent::nextOut(i);

972

973

974

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

975

      Parent::nextInc(i, d);

976

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

977

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

978

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

979

        Parent::nextInc(i, d);

980

981

982

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

983

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

984

985

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

986

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

987

988

    typedef False NodeNumTag;

989

    typedef False ArcNumTag;

990

    typedef False EdgeNumTag;

991

992

    typedef FindArcTagIndicator<Graph> FindArcTag;

993

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

994

                const Arc& prev = INVALID) const {

995

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

996

        return INVALID;

997

998

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

999

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

1000

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

1001

1002

      return arc;

1003

1004

1005

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

1006

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

1007

                  const Edge& prev = INVALID) const {

1008

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

1009

        return INVALID;

1010

1011

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

1012

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

1013

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

1014

1015

      return edge;

1016

1017

1018

    template <typename V>

1019

    class NodeMap

1020

      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

1021

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {

1022

      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

1023

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;

1024

1025

    public:

1026

      typedef V Value;

1027

1028

      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)

1029

        : Parent(adaptor) {}

1030

      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)

1031

        : Parent(adaptor, value) {}

1032

1033

    private:

1034

      NodeMap& operator=(const NodeMap& cmap) {

1035

        return operator=<NodeMap>(cmap);

1036

1037

1038

      template <typename CMap>

1039

      NodeMap& operator=(const CMap& cmap) {

1040

        Parent::operator=(cmap);

1041

        return *this;

1042

1043

};

1044

1045

    template <typename V>

1046

    class ArcMap

1047

      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

1048

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {

1049

      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

1050

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;

1051

1052

    public:

1053

      typedef V Value;

1054

1055

      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)

1056

        : Parent(adaptor) {}

1057

      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)

1058

        : Parent(adaptor, value) {}

1059

1060

    private:

1061

      ArcMap& operator=(const ArcMap& cmap) {

1062

        return operator=<ArcMap>(cmap);

1063

1064

1065

      template <typename CMap>

1066

      ArcMap& operator=(const CMap& cmap) {

1067

        Parent::operator=(cmap);

1068

        return *this;

1069

1070

};

1071

1072

    template <typename V>

1073

    class EdgeMap

1074

      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

1075

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {

1076

      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

1077

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;

1078

1079

    public:

1080

      typedef V Value;

1081

1082

      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)

1083

        : Parent(adaptor) {}

1084

1085

      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)

1086

        : Parent(adaptor, value) {}

1087

1088

    private:

1089

      EdgeMap& operator=(const EdgeMap& cmap) {

1090

        return operator=<EdgeMap>(cmap);

1091

1092

1093

      template <typename CMap>

1094

      EdgeMap& operator=(const CMap& cmap) {

1095

        Parent::operator=(cmap);

1096

        return *this;

1097

1098

};

1099

1100

};

1101

1102

  template <typename GR, typename NF, typename EF>

1103

  class SubGraphBase<GR, NF, EF, false>

1104

    : public GraphAdaptorBase<GR> {

1105

    typedef GraphAdaptorBase<GR> Parent;

1106

  public:

1107

    typedef GR Graph;

1108

    typedef NF NodeFilterMap;

1109

    typedef EF EdgeFilterMap;

1110

1111

    typedef SubGraphBase Adaptor;

1112

  protected:

1113

    NF* _node_filter;

1114

    EF* _edge_filter;

1115

    SubGraphBase()

1116

	  : Parent(), _node_filter(0), _edge_filter(0) { }

1117

1118

    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {

1119

      Parent::initialize(graph);

1120

      _node_filter = &node_filter;

1121

      _edge_filter = &edge_filter;

1122

1123

1124

  public:

1125

1126

    typedef typename Parent::Node Node;

1127

    typedef typename Parent::Arc Arc;

1128

    typedef typename Parent::Edge Edge;

1129

1130

    void first(Node& i) const {

1131

      Parent::first(i);

1132

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

1133

1134

1135

    void first(Arc& i) const {

1136

      Parent::first(i);

1137

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

1138

1139

1140

    void first(Edge& i) const {

1141

      Parent::first(i);

1142

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

1143

1144

1145

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

1146

      Parent::firstIn(i, n);

1147

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

1148

1149

1150

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

1151

      Parent::firstOut(i, n);

1152

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

1153

1154

1155

    void firstInc(Edge& i, bool& d, const Node& n) const {

1156

      Parent::firstInc(i, d, n);

1157

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

1158

1159

1160

    void next(Node& i) const {

1161

      Parent::next(i);

1162

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

1163

1164

    void next(Arc& i) const {

1165

      Parent::next(i);

1166

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

1167

1168

    void next(Edge& i) const {

1169

      Parent::next(i);

1170

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

1171

1172

    void nextIn(Arc& i) const {

1173

      Parent::nextIn(i);

1174

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

1175

1176

1177

    void nextOut(Arc& i) const {

1178

      Parent::nextOut(i);

1179

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

1180

1181

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

1182

      Parent::nextInc(i, d);

1183

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

1184

1185

1186

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

1187

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

1188

1189

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

1190

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

1191

1192

    typedef False NodeNumTag;

1193

    typedef False ArcNumTag;

1194

    typedef False EdgeNumTag;

1195

1196

    typedef FindArcTagIndicator<Graph> FindArcTag;

1197

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

1198

                const Arc& prev = INVALID) const {

1199

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

1200

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

1201

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

1202

1203

      return arc;

1204

1205

1206

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

1207

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

1208

                  const Edge& prev = INVALID) const {

1209

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

1210

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

1211

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

1212

1213

      return edge;

1214

1215

1216

    template <typename V>

1217

    class NodeMap

1218

      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

1219

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {

1220

      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,

1221

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;

1222

1223

    public:

1224

      typedef V Value;

1225

1226

      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)

1227

        : Parent(adaptor) {}

1228

      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)

1229

        : Parent(adaptor, value) {}

1230

1231

    private:

1232

      NodeMap& operator=(const NodeMap& cmap) {

1233

        return operator=<NodeMap>(cmap);

1234

1235

1236

      template <typename CMap>

1237

      NodeMap& operator=(const CMap& cmap) {

1238

        Parent::operator=(cmap);

1239

        return *this;

1240

1241

};

1242

1243

    template <typename V>

1244

    class ArcMap

1245

      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

1246

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {

1247

      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,

1248

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;

1249

1250

    public:

1251

      typedef V Value;

1252

1253

      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)

1254

        : Parent(adaptor) {}

1255

      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)

1256

        : Parent(adaptor, value) {}

1257

1258

    private:

1259

      ArcMap& operator=(const ArcMap& cmap) {

1260

        return operator=<ArcMap>(cmap);

1261

1262

1263

      template <typename CMap>

1264

      ArcMap& operator=(const CMap& cmap) {

1265

        Parent::operator=(cmap);

1266

        return *this;

1267

1268

};

1269

1270

    template <typename V>

1271

    class EdgeMap

1272

      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

1273

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {

1274

      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,

1275

	LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;

1276

1277

    public:

1278

      typedef V Value;

1279

1280

      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)

1281

        : Parent(adaptor) {}

1282

1283

      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)

1284

        : Parent(adaptor, value) {}

1285

1286

    private:

1287

      EdgeMap& operator=(const EdgeMap& cmap) {

1288

        return operator=<EdgeMap>(cmap);

1289

1290

1291

      template <typename CMap>

1292

      EdgeMap& operator=(const CMap& cmap) {

1293

        Parent::operator=(cmap);

1294

        return *this;

1295

1296

};

1297

1298

};

1299

1300

  /// \ingroup graph_adaptors

1301

///

1302

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

1303

  /// graph.

1304

///

1305

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

1306

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

1307

  /// define the filters for nodes and edges.

1308

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

1309

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

1310

  /// nodes are also filtered out.

1311

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

1312

///

1313

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

1314

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

1315

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

1316

///

1317

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

1318

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

1319

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

1320

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

1321

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

1322

  /// adapted graph. The default type is

1323

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

1324

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

1325

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

1326

  /// adapted graph. The default type is

1327

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

1328

///

1329

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

1330

  /// adapted graph are convertible to each other.

1331

///

1332

  /// \see FilterNodes

1333

  /// \see FilterEdges

1334

#ifdef DOXYGEN

1335

  template<typename GR, typename NF, typename EF>

1336

  class SubGraph {

1337

#else

1338

  template<typename GR,

1339

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

1340

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

1341

  class SubGraph :

1342

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

1343

#endif

1344

  public:

1345

    /// The type of the adapted graph.

1346

    typedef GR Graph;

1347

    /// The type of the node filter map.

1348

    typedef NF NodeFilterMap;

1349

    /// The type of the edge filter map.

1350

    typedef EF EdgeFilterMap;

1351

1352

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

1353

      Parent;

1354

1355

    typedef typename Parent::Node Node;

1356

    typedef typename Parent::Edge Edge;

1357

1358

  protected:

1359

    SubGraph() { }

1360

  public:

1361

1362

    /// \brief Constructor

1363

///

1364

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

1365

    /// and edge filter maps.

1366

    SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {

1367

      initialize(graph, node_filter, edge_filter);

1368

1369

1370

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

1371

///

1372

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

1373

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

1374

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

1375

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

1376

1377

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

1378

///

1379

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

1380

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

1381

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

1382

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

1383

1384

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

1385

///

1386

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

1387

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

1388

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

1389

1390

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

1391

///

1392

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

1393

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

1394

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

1395

1396

    /// \brief Disables the given node

1397

///

1398

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

1399

    /// so the iteration jumps over it.

1400

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

1401

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

1402

1403

    /// \brief Disables the given edge

1404

///

1405

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

1406

    /// so the iteration jumps over it.

1407

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

1408

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

1409

1410

    /// \brief Enables the given node

1411

///

1412

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

1413

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

1414

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

1415

1416

    /// \brief Enables the given edge

1417

///

1418

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

1419

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

1420

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

1421

1422

};

1423

1424

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

1425

///

1426

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

1427

  /// \ingroup graph_adaptors

1428

  /// \relates SubGraph

1429

  template<typename GR, typename NF, typename EF>

1430

  SubGraph<const GR, NF, EF>

1431

  subGraph(const GR& graph, NF& node_filter, EF& edge_filter) {

1432

    return SubGraph<const GR, NF, EF>

1433

      (graph, node_filter, edge_filter);

1434

1435

1436

  template<typename GR, typename NF, typename EF>

1437

  SubGraph<const GR, const NF, EF>

1438

  subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) {

1439

    return SubGraph<const GR, const NF, EF>

1440

      (graph, node_filter, edge_filter);

1441

1442

1443

  template<typename GR, typename NF, typename EF>

1444

  SubGraph<const GR, NF, const EF>

1445

  subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) {

1446

    return SubGraph<const GR, NF, const EF>

1447

      (graph, node_filter, edge_filter);

1448

1449

1450

  template<typename GR, typename NF, typename EF>

1451

  SubGraph<const GR, const NF, const EF>

1452

  subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) {

1453

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

1454

      (graph, node_filter, edge_filter);

  /// \ingroup graph_adaptors

1459

///

1460

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

1461

///

1462

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

1463

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

1464

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

1465

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

1466

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

1467

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

1468

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

1469

///

1470

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

1471

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

1472

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

1473

///

1474

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

1475

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

1476

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

1477

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

1478

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

1479

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

1480

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

1481

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

1482

///

1483

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

1484

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

1485

#ifdef DOXYGEN

1486

  template<typename GR, typename NF>

1487

  class FilterNodes {

1488

#else

1489

  template<typename GR,

1490

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

1491

           typename Enable = void>

1492

  class FilterNodes :

1493

    public DigraphAdaptorExtender<

1494

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

1495

                     true> > {

1496

#endif

1497

    typedef DigraphAdaptorExtender<

1498

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

1499

                     true> > Parent;

1500

1501

  public:

1502

1503

    typedef GR Digraph;

1504

    typedef NF NodeFilterMap;

1505

1506

    typedef typename Parent::Node Node;

1507

1508

  protected:

1509

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

1510

1511

    FilterNodes() : const_true_map() {}

1512

1513

  public:

1514

1515

    /// \brief Constructor

1516

///

1517

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

1518

    /// given node filter map.

1519

    FilterNodes(GR& graph, NF& node_filter)

1520

      : Parent(), const_true_map()

1521

1522

      Parent::initialize(graph, node_filter, const_true_map);

1523

1524

1525

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

1526

///

1527

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

1528

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

1529

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

1530

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

1531

1532

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

1533

///

1534

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

1535

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

1536

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

1537

1538

    /// \brief Disables the given node

1539

///

1540

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

1541

    /// jumps over it.

1542

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

1543

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

1544

1545

    /// \brief Enables the given node

1546

///

1547

    /// This function enables the given node.

1548

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

1549

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

1550

1551

};

1552

1553

  template<typename GR, typename NF>

1554

  class FilterNodes<GR, NF,

1555

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

1556

    public GraphAdaptorExtender<

1557

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

1558

                   true> > {

1559

1560

    typedef GraphAdaptorExtender<

1561

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

1562

                   true> > Parent;

1563

1564

  public:

1565

1566

    typedef GR Graph;

1567

    typedef NF NodeFilterMap;

1568

1569

    typedef typename Parent::Node Node;

1570

1571

  protected:

1572

    ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;

1573

1574

    FilterNodes() : const_true_map() {}

1575

1576

  public:

1577

1578

    FilterNodes(GR& graph, NodeFilterMap& node_filter) :

1579

      Parent(), const_true_map() {

1580

      Parent::initialize(graph, node_filter, const_true_map);

1581

1582

1583

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

1584

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

1585

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

1586

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

1587

1588

};

1589

1590

1591

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

1592

///

1593

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

1594

  /// \ingroup graph_adaptors

1595

  /// \relates FilterNodes

1596

  template<typename GR, typename NF>

1597

  FilterNodes<const GR, NF>

1598

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

1599

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

1600

1601

1602

  template<typename GR, typename NF>

1603

  FilterNodes<const GR, const NF>

1604

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

1605

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

1606

1607

1608

  /// \ingroup graph_adaptors

1609

///

1610

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

1611

///

1612

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

1613

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

1614

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

1615

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

1616

  /// "Digraph" concept.

1617

///

1618

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

1619

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

1620

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

1621

///

1622

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

1623

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

1624

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

1625

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

1626

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

1627

  /// adapted digraph. The default type is

1628

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

1629

///

1630

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

1631

  /// digraph are convertible to each other.

1632

#ifdef DOXYGEN

1633

  template<typename DGR,

1634

           typename AF>

1635

  class FilterArcs {

1636

#else

1637

  template<typename DGR,

1638

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

1639

  class FilterArcs :

1640

    public DigraphAdaptorExtender<

1641

      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,

1642

                     AF, false> > {

1643

#endif

1644

    typedef DigraphAdaptorExtender<

1645

      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,

1646

                     AF, false> > Parent;

1647

1648

  public:

1649

1650

    /// The type of the adapted digraph.

1651

    typedef DGR Digraph;

1652

    /// The type of the arc filter map.

1653

    typedef AF ArcFilterMap;

1654

1655

    typedef typename Parent::Arc Arc;

1656

1657

  protected:

1658

    ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;

1659

1660

    FilterArcs() : const_true_map() {}

1661

1662

  public:

1663

1664

    /// \brief Constructor

1665

///

1666

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

1667

    /// filter map.

1668

    FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)

1669

      : Parent(), const_true_map() {

1670

      Parent::initialize(digraph, const_true_map, arc_filter);

1671

1672

1673

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

1674

///

1675

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

1676

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

1677

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

1678

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

1679

1680

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

1681

///

1682

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

1683

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

1684

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

1685

1686

    /// \brief Disables the given arc

1687

///

1688

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

1689

    /// so the iteration jumps over it.

1690

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

1691

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

1692

1693

    /// \brief Enables the given arc

1694

///

1695

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

1696

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

1697

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

1698

1699

};

1700

1701

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

1702

///

1703

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

1704

  /// \ingroup graph_adaptors

1705

  /// \relates FilterArcs

1706

  template<typename DGR, typename AF>

1707

  FilterArcs<const DGR, AF>

1708

  filterArcs(const DGR& digraph, AF& arc_filter) {

1709

    return FilterArcs<const DGR, AF>(digraph, arc_filter);

1710

1711

1712

  template<typename DGR, typename AF>

1713

  FilterArcs<const DGR, const AF>

1714

  filterArcs(const DGR& digraph, const AF& arc_filter) {

1715

    return FilterArcs<const DGR, const AF>(digraph, arc_filter);

1716

1717

1718

  /// \ingroup graph_adaptors

1719

///

1720

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

1721

///

1722

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

1723

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

1724

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

1725

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

1726

  /// "Graph" concept.

1727

///

1728

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

1729

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

1730

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

1731

///

1732

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

1733

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

1734

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

1735

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

1736

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

1737

  /// adapted graph. The default type is

1738

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

1739

///

1740

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

1741

  /// adapted graph are convertible to each other.

1742

#ifdef DOXYGEN

1743

  template<typename GR,

1744

           typename EF>

1745

  class FilterEdges {

1746

#else

1747

  template<typename GR,

1748

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

1749

  class FilterEdges :

1750

    public GraphAdaptorExtender<

1751

      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,

1752

                   EF, false> > {

1753

#endif

1754

    typedef GraphAdaptorExtender<

1755

      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,

1756

                   EF, false> > Parent;

1757

1758

  public:

1759

1760

    /// The type of the adapted graph.

1761

    typedef GR Graph;

1762

    /// The type of the edge filter map.

1763

    typedef EF EdgeFilterMap;

1764

1765

    typedef typename Parent::Edge Edge;

1766

1767

  protected:

1768

    ConstMap<typename GR::Node, Const<bool, true> > const_true_map;

1769

1770

    FilterEdges() : const_true_map(true) {

1771

      Parent::setNodeFilterMap(const_true_map);

1772

1773

1774

  public:

1775

1776

    /// \brief Constructor

1777

///

1778

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

1779

    /// filter map.

1780

    FilterEdges(GR& graph, EF& edge_filter)

1781

      : Parent(), const_true_map() {

1782

      Parent::initialize(graph, const_true_map, edge_filter);

1783

1784

1785

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

1786

///

1787

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

1788

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

1789

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

1790

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

1791

1792

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

1793

///

1794

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

1795

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

1796

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

1797

1798

    /// \brief Disables the given edge

1799

///

1800

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

1801

    /// so the iteration jumps over it.

1802

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

1803

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

1804

1805

    /// \brief Enables the given edge

1806

///

1807

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

1808

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

1809

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

1810

1811

};

1812

1813

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

1814

///

1815

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

1816

  /// \ingroup graph_adaptors

1817

  /// \relates FilterEdges

1818

  template<typename GR, typename EF>

1819

  FilterEdges<const GR, EF>

1820

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

1821

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

1822

1823

1824

  template<typename GR, typename EF>

1825

  FilterEdges<const GR, const EF>

1826

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

1827

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

  template <typename DGR>

1832

  class UndirectorBase {

1833

  public:

1834

    typedef DGR Digraph;

1835

    typedef UndirectorBase Adaptor;

1836

1837

    typedef True UndirectedTag;

1838

1839

    typedef typename Digraph::Arc Edge;

1840

    typedef typename Digraph::Node Node;

1841

1842

    class Arc : public Edge {

1842

    class Arc {

1843

      friend class UndirectorBase;

1844

    protected:

1845

      Edge _edge;

1845

1846

      bool _forward;

1846

1847

      Arc(const Edge& edge, bool forward) :

1848

        Edge(edge), _forward(forward) {}

1848

      Arc(const Edge& edge, bool forward)

1849

        : _edge(edge), _forward(forward) {}

1849

1850

1851

    public:

1851

1852

      Arc() {}

1852

1853

      Arc(Invalid) : Edge(INVALID), _forward(true) {}

1854

      Arc(Invalid) : _edge(INVALID), _forward(true) {}

1855

1856

      operator const Edge&() const { return _edge; }

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

1856

        return _forward == other._forward &&

1857

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

1859

        return _forward == other._forward && _edge == other._edge;

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

1860

        return _forward != other._forward ||

1861

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

1862

        return _forward != other._forward || _edge != other._edge;

1862

1863

1864

      bool operator<(const Arc &other) const {

1864

1865

        return _forward < other._forward ||

1865

          (_forward == other._forward &&

1866

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

1866

          (_forward == other._forward && _edge < other._edge);

1867

1868

};

1869

1870

    void first(Node& n) const {

1871

      _digraph->first(n);

1872

1873

1874

    void next(Node& n) const {

1875

      _digraph->next(n);

1876

1877

1878

    void first(Arc& a) const {

1879

      _digraph->first(a);

1879

      _digraph->first(a._edge);

1880

      a._forward = true;

1881

1882

1883

    void next(Arc& a) const {

1884

      if (a._forward) {

1885

        a._forward = false;

1886

      } else {

1887

        _digraph->next(a);

1887

        _digraph->next(a._edge);

1888

        a._forward = true;

    void first(Edge& e) const {

1893

      _digraph->first(e);

1894

1895

1896

    void next(Edge& e) const {

1897

      _digraph->next(e);

1898

1899

1900

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

1901

      _digraph->firstIn(a, n);

1902

      if( static_cast<const Edge&>(a) != INVALID ) {

1901

      _digraph->firstIn(a._edge, n);

1902

      if (a._edge != INVALID ) {

1903

        a._forward = false;

1904

      } else {

1905

        _digraph->firstOut(a, n);

1905

        _digraph->firstOut(a._edge, n);

1906

        a._forward = true;

1907

1908

1909

    void nextOut(Arc &a) const {

1910

      if (!a._forward) {

1911

        Node n = _digraph->target(a);

1912

        _digraph->nextIn(a);

1913

        if (static_cast<const Edge&>(a) == INVALID ) {

1914

          _digraph->firstOut(a, n);

1911

        Node n = _digraph->target(a._edge);

1912

        _digraph->nextIn(a._edge);

1913

        if (a._edge == INVALID) {

1914

          _digraph->firstOut(a._edge, n);

1915

          a._forward = true;

1916

1917

1918

      else {

1919

        _digraph->nextOut(a);

1919

        _digraph->nextOut(a._edge);

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

1924

      _digraph->firstOut(a, n);

1925

      if (static_cast<const Edge&>(a) != INVALID ) {

1924

      _digraph->firstOut(a._edge, n);

1925

      if (a._edge != INVALID ) {

1926

        a._forward = false;

1927

      } else {

1928

        _digraph->firstIn(a, n);

1928

        _digraph->firstIn(a._edge, n);

1929

        a._forward = true;

1930

1931

1932

    void nextIn(Arc &a) const {

1933

      if (!a._forward) {

1934

        Node n = _digraph->source(a);

1935

        _digraph->nextOut(a);

1936

        if( static_cast<const Edge&>(a) == INVALID ) {

1937

          _digraph->firstIn(a, n);

1934

        Node n = _digraph->source(a._edge);

1935

        _digraph->nextOut(a._edge);

1936

        if (a._edge == INVALID ) {

1937

          _digraph->firstIn(a._edge, n);

1938

          a._forward = true;

1939

1940

1941

      else {

1942

        _digraph->nextIn(a);

1942

        _digraph->nextIn(a._edge);

    void firstInc(Edge &e, bool &d, const Node &n) const {

1947

      d = true;

1948

      _digraph->firstOut(e, n);

1949

      if (e != INVALID) return;

1950

      d = false;

1951

      _digraph->firstIn(e, n);

1952

1953

1954

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

1955

      if (d) {

1956

        Node s = _digraph->source(e);

1957

        _digraph->nextOut(e);

1958

        if (e != INVALID) return;

1959

        d = false;

1960

        _digraph->firstIn(e, s);

1961

      } else {

1962

        _digraph->nextIn(e);

    Node u(const Edge& e) const {

1967

      return _digraph->source(e);

1968

1969

1970

    Node v(const Edge& e) const {

1971

      return _digraph->target(e);

1972

1973

1974

    Node source(const Arc &a) const {

1975

      return a._forward ? _digraph->source(a) : _digraph->target(a);

1975

      return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);

1976

1977

1978

    Node target(const Arc &a) const {

1979

      return a._forward ? _digraph->target(a) : _digraph->source(a);

1979

      return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);

1980

1981

1982

    static Arc direct(const Edge &e, bool d) {

1983

      return Arc(e, d);

1984

1985

    Arc direct(const Edge &e, const Node& n) const {

1986

      return Arc(e, _digraph->source(e) == n);

    static bool direction(const Arc &a) { return a._forward; }

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

1992

1989

    Arc arcFromId(int ix) const {

1993

1990

      return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));

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

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

1998

1995

    int id(const Arc &a) const {

1999

1996

      return  (_digraph->id(a) << 1) | (a._forward ? 1 : 0);

    int id(const Edge &e) const { return _digraph->id(e); }

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

2004

2001

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

2005

2002

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

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

2008

2005

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

2009

2006

      return _digraph->addArc(u, v);

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

2013

2010

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

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

    typedef NodeNumTagIndicator<Digraph> NodeNumTag;

2018

2015

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

    typedef ArcNumTagIndicator<Digraph> ArcNumTag;

2021

2018

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

    typedef ArcNumTag EdgeNumTag;

2024

2021

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

    typedef FindArcTagIndicator<Digraph> FindArcTag;

2027

2024

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

2028

2025

      if (p == INVALID) {

2029

2026

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

2030

2027

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

2031

2028

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

2032

2029

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

2033

2030

      } else if (direction(p)) {

2034

2031

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

2035

2032

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

2036

2033

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

2037

2034

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

2038

2035

      } else {

2039

2036

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

2040

2037

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

      return INVALID;

    typedef FindArcTag FindEdgeTag;

2046

2043

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

2047

2044

      if (s != t) {

2048

2045

        if (p == INVALID) {

2049

2046

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

2050

2047

          if (arc != INVALID) return arc;

2051

2048

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

2052

2049

          if (arc != INVALID) return arc;

2053

2050

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

2054

2051

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

2055

2052

          if (arc != INVALID) return arc;

2056

2053

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

2057

2054

          if (arc != INVALID) return arc;

2058

2055

        } else {

2059

2056

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

2060

2057

          if (arc != INVALID) return arc;

      } else {

2063

2060

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

      return INVALID;

  private:

    template <typename V>

2071

2068

    class ArcMapBase {

2072

2069

    private:

      typedef typename DGR::template ArcMap<V> MapImpl;

    public:

      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;

      typedef V Value;

2081

2078

      typedef Arc Key;

2082

2079

      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;

2083

2080

      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;

2084

2081

      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;

2085

2082

      typedef typename MapTraits<MapImpl>::ReturnValue Reference;

      ArcMapBase(const UndirectorBase<DGR>& adaptor) :

2088

2085

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

      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)

2091

2088

        : _forward(*adaptor._digraph, value),

2092

2089

          _backward(*adaptor._digraph, value) {}

      void set(const Arc& a, const V& value) {

2095

2092

        if (direction(a)) {

2096

2093

          _forward.set(a, value);

2097

2094

        } else {

2098

2095

          _backward.set(a, value);

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

2103

2100

        if (direction(a)) {

2104

2101

          return _forward[a];

2105

2102

        } else {

2106

2103

          return _backward[a];

      ReturnValue operator[](const Arc& a) {

2111

2108

        if (direction(a)) {

2112

2109

          return _forward[a];

2113

2110

        } else {

2114

2111

          return _backward[a];

    protected:

      MapImpl _forward, _backward;

};

  public:

    template <typename V>

2127

2124

    class NodeMap : public DGR::template NodeMap<V> {

2128

2125

      typedef typename DGR::template NodeMap<V> Parent;

    public:

2131

2128

      typedef V Value;

      explicit NodeMap(const UndirectorBase<DGR>& adaptor)

2134

2131

        : Parent(*adaptor._digraph) {}

      NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)

2137

2134

        : Parent(*adaptor._digraph, value) { }

    private:

2140

2137

      NodeMap& operator=(const NodeMap& cmap) {

2141

2138

        return operator=<NodeMap>(cmap);

      template <typename CMap>

2145

2142

      NodeMap& operator=(const CMap& cmap) {

2146

2143

        Parent::operator=(cmap);

2147

2144

        return *this;

};

    template <typename V>

2153

2150

    class ArcMap

2154

2151

      : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {

2155

2152

      typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;

    public:

2158

2155

      typedef V Value;

      explicit ArcMap(const UndirectorBase<DGR>& adaptor)

2161

2158

        : Parent(adaptor) {}

      ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)

2164

2161

        : Parent(adaptor, value) {}

    private:

2167

2164

      ArcMap& operator=(const ArcMap& cmap) {

2168

2165

        return operator=<ArcMap>(cmap);

      template <typename CMap>

2172

2169

      ArcMap& operator=(const CMap& cmap) {

2173

2170

        Parent::operator=(cmap);

2174

2171

        return *this;

};

    template <typename V>

2179

2176

    class EdgeMap : public Digraph::template ArcMap<V> {

2180

2177

      typedef typename Digraph::template ArcMap<V> Parent;

    public:

2183

2180

      typedef V Value;

      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)

2186

2183

        : Parent(*adaptor._digraph) {}

      EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)

2189

2186

        : Parent(*adaptor._digraph, value) {}

    private:

2192

2189

      EdgeMap& operator=(const EdgeMap& cmap) {

2193

2190

        return operator=<EdgeMap>(cmap);

      template <typename CMap>

2197

2194

      EdgeMap& operator=(const CMap& cmap) {

2198

2195

        Parent::operator=(cmap);

2199

2196

        return *this;

};

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

2205

2202

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

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

2208

2205

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

    typedef EdgeNotifier ArcNotifier;

2211

2208

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

  protected:

    UndirectorBase() : _digraph(0) {}

    DGR* _digraph;

    void initialize(DGR& digraph) {

2220

2217

      _digraph = &digraph;

};

  /// \ingroup graph_adaptors

2226

2223

///

2227

2224

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

2228

2225

///

2229

2226

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

2230

2227

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

2231

2228

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

2232

2229

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

2233

2230

///

2234

2231

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

2235

2232

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

2236

2233

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

2237

2234

///

2238

2235

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

2239

2236

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

2240

2237

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

2241

2238

///

2242

2239

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

2243

2240

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

2244

2241

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

2245

2242

  /// each other.

2246

2243

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

2247

2244

  /// of the adapted digraph.)

2248

2245

  template<typename DGR>

2249

2246

#ifdef DOXYGEN

2250

2247

  class Undirector {

2251

2248

#else

2252

2249

  class Undirector :

2253

2250

    public GraphAdaptorExtender<UndirectorBase<DGR> > {

2254

2251

#endif

2255

2252

    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;

2256

2253

  public:

2257

2254

    /// The type of the adapted digraph.

2258

2255

    typedef DGR Digraph;

2259

2256

  protected:

2260

2257

    Undirector() { }

2261

2258

  public:

    /// \brief Constructor

2264

2261

///

2265

2262

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

2266

2263

    Undirector(DGR& digraph) {

2267

2264

      initialize(digraph);

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

2271

2268

///

2272

2269

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

2273

2270

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

2274

2271

    /// Its value type is inherited from the first arc map type (\c FW).

2275

2272

    /// \tparam FW The type of the "foward" arc map.

2276

2273

    /// \tparam BK The type of the "backward" arc map.

2277

2274

    template <typename FW, typename BK>

2278

2275

    class CombinedArcMap {

2279

2276

    public:

      /// The key type of the map

2282

2279

      typedef typename Parent::Arc Key;

2283

2280

      /// The value type of the map

2284

2281

      typedef typename FW::Value Value;

      typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;

      typedef typename MapTraits<FW>::ReturnValue ReturnValue;

2289

2286

      typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;

2290

2287

      typedef typename MapTraits<FW>::ReturnValue Reference;

2291

2288

      typedef typename MapTraits<FW>::ConstReturnValue ConstReference;

      /// Constructor

2294

2291

      CombinedArcMap(FW& forward, BK& backward)

2295

2292

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

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

2298

2295

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

2299

2296

        if (Parent::direction(e)) {

2300

2297

          _forward->set(e, a);

2301

2298

        } else {

2302

2299

          _backward->set(e, a);

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

2307

2304

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

2308

2305

        if (Parent::direction(e)) {

2309

2306

          return (*_forward)[e];

2310

2307

        } else {

2311

2308

          return (*_backward)[e];

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

2316

2313

      ReturnValue operator[](const Key& e) {

2317

2314

        if (Parent::direction(e)) {

2318

2315

          return (*_forward)[e];

2319

2316

        } else {

2320

2317

          return (*_backward)[e];

    protected:

      FW* _forward;

2327

2324

      BK* _backward;

};

    /// \brief Returns a combined arc map

2332

2329

///

2333

2330

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

2334

2331

    template <typename FW, typename BK>

2335

2332

    static CombinedArcMap<FW, BK>

2336

2333

    combinedArcMap(FW& forward, BK& backward) {

2337

2334

      return CombinedArcMap<FW, BK>(forward, backward);

    template <typename FW, typename BK>

2341

2338

    static CombinedArcMap<const FW, BK>

2342

2339

    combinedArcMap(const FW& forward, BK& backward) {

2343

2340

      return CombinedArcMap<const FW, BK>(forward, backward);

    template <typename FW, typename BK>

2347

2344

    static CombinedArcMap<FW, const BK>

2348

2345

    combinedArcMap(FW& forward, const BK& backward) {

2349

2346

      return CombinedArcMap<FW, const BK>(forward, backward);

    template <typename FW, typename BK>

2353

2350

    static CombinedArcMap<const FW, const BK>

2354

2351

    combinedArcMap(const FW& forward, const BK& backward) {

2355

2352

      return CombinedArcMap<const FW, const BK>(forward, backward);

};

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

2361

2358

///

2362

2359

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

2363

2360

  /// \ingroup graph_adaptors

2364

2361

  /// \relates Undirector

2365

2362

  template<typename DGR>

2366

2363

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

2367

2364

    return Undirector<const DGR>(digraph);

  template <typename GR, typename DM>

2372

2369

  class OrienterBase {

2373

2370

  public:

    typedef GR Graph;

2376

2373

    typedef DM DirectionMap;

    typedef typename GR::Node Node;

2379

2376

    typedef typename GR::Edge Arc;

    void reverseArc(const Arc& arc) {

2382

2379

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

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

2386

2383

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

2387

2384

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

2388

2385

      bool d = true;

2389

2386

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

2390

2387

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

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

2393

2390

      bool d = true;

2394

2391

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

2395

2392

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

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

2399

2396

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

2400

2397

    void nextIn(Arc& i) const {

2401

2398

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

2402

2399

      _graph->nextInc(i, d);

2403

2400

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

    void nextOut(Arc& i) const {

2406

2403

      bool d = (*_direction)[i];

2407

2404

      _graph->nextInc(i, d);

2408

2405

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

    Node source(const Arc& e) const {

2412

2409

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

    Node target(const Arc& e) const {

2415

2412

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

    typedef NodeNumTagIndicator<Graph> NodeNumTag;

2419

2416

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

    typedef EdgeNumTagIndicator<Graph> ArcNumTag;

2422

2419

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

    typedef FindEdgeTagIndicator<Graph> FindArcTag;

2425

2422

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

2426

2423

                const Arc& prev = INVALID) const {

2427

2424

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

2428

2425

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

2429

2426

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

      return arc;

    Node addNode() {

2435

2432

      return Node(_graph->addNode());

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

2439

2436

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

2440

2437

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

2441

2438

      return arc;

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

2445

2442

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

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

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

2450

2447

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

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

2453

2450

    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }

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

2456

2453

    int maxArcId() const { return _graph->maxEdgeId(); }

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

2459

2456

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

    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;

2462

2459

    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }

    template <typename V>

2465

2462

    class NodeMap : public GR::template NodeMap<V> {

2466

2463

      typedef typename GR::template NodeMap<V> Parent;

    public:

      explicit NodeMap(const OrienterBase<GR, DM>& adapter)

2471

2468

        : Parent(*adapter._graph) {}

      NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)

2474

2471

        : Parent(*adapter._graph, value) {}

    private:

2477

2474

      NodeMap& operator=(const NodeMap& cmap) {

2478

2475

        return operator=<NodeMap>(cmap);

      template <typename CMap>

2482

2479

      NodeMap& operator=(const CMap& cmap) {

2483

2480

        Parent::operator=(cmap);

2484

2481

        return *this;

};

    template <typename V>

2490

2487

    class ArcMap : public GR::template EdgeMap<V> {

2491

2488

      typedef typename Graph::template EdgeMap<V> Parent;

    public:

      explicit ArcMap(const OrienterBase<GR, DM>& adapter)

2496

2493

        : Parent(*adapter._graph) { }

      ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)

2499

2496

        : Parent(*adapter._graph, value) { }

    private:

2502

2499

      ArcMap& operator=(const ArcMap& cmap) {

2503

2500

        return operator=<ArcMap>(cmap);

      template <typename CMap>

2507

2504

      ArcMap& operator=(const CMap& cmap) {

2508

2505

        Parent::operator=(cmap);

2509

2506

        return *this;

};

  protected:

2516

2513

    Graph* _graph;

2517

2514

    DM* _direction;

    void initialize(GR& graph, DM& direction) {

2520

2517

      _graph = &graph;

2521

2518

      _direction = &direction;

};

  /// \ingroup graph_adaptors

2527

2524

///

2528

2525

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

2529

2526

///

2530

2527

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

2531

2528

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

2532

2529

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

2533

2530

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

2534

2531

  /// of the adaptor.

2535

2532

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

2536

2533

///

2537

2534

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

2538

2535

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

2539

2536

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

2540

2537

///

2541

2538

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

2542

2539

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

2543

2540

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

2544

2541

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

2545

2542

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

2546

2543

  /// adapted graph. The default type is

2547

2544

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

2548

2545

///

2549

2546

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

2550

2547

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

2551

2548

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

2552

2549

  /// each other.

2553

2550

#ifdef DOXYGEN

2554

2551

  template<typename GR,

2555

2552

           typename DM>

2556

2553

  class Orienter {

2557

2554

#else

2558

2555

  template<typename GR,

2559

2556

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

2560

2557

  class Orienter :

2561

2558

    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {

2562

2559

#endif

2563

2560

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

2564

2561

  public:

    /// The type of the adapted graph.

2567

2564

    typedef GR Graph;

2568

2565

    /// The type of the direction edge map.

2569

2566

    typedef DM DirectionMap;

    typedef typename Parent::Arc Arc;

  protected:

2574

2571

    Orienter() { }

  public:

    /// \brief Constructor

2579

2576

///

2580

2577

    /// Constructor of the adaptor.

2581

2578

    Orienter(GR& graph, DM& direction) {

2582

2579

      Parent::initialize(graph, direction);

    /// \brief Reverses the given arc

2586

2583

///

2587

2584

    /// This function reverses the given arc.

2588

2585

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

2589

2586

    /// in the direction map.

2590

2587

    void reverseArc(const Arc& a) {

2591

2588

      Parent::reverseArc(a);

};

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

2596

2593

///

2597

2594

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

2598

2595

  /// \ingroup graph_adaptors

2599

2596

  /// \relates Orienter

2600

2597

  template<typename GR, typename DM>

2601

2598

  Orienter<const GR, DM>

2602

2599

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

2603

2600

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

  template<typename GR, typename DM>

2607

2604

  Orienter<const GR, const DM>

2608

2605

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

2609

2606

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

  namespace _adaptor_bits {

    template <typename DGR, typename CM, typename FM, typename TL>

2615

2612

    class ResForwardFilter {

2616

2613

    public:

      typedef typename DGR::Arc Key;

2619

2616

      typedef bool Value;

    private:

      const CM* _capacity;

2624

2621

      const FM* _flow;

2625

2622

      TL _tolerance;

    public:

      ResForwardFilter(const CM& capacity, const FM& flow,

2630

2627

                       const TL& tolerance = TL())

2631

2628

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

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

2634

2631

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

};

    template<typename DGR,typename CM, typename FM, typename TL>

2639

2636

    class ResBackwardFilter {

2640

2637

    public:

      typedef typename DGR::Arc Key;

2643

2640

      typedef bool Value;

    private:

      const CM* _capacity;

2648

2645

      const FM* _flow;

2649

2646

      TL _tolerance;

    public:

      ResBackwardFilter(const CM& capacity, const FM& flow,

2654

2651

                        const TL& tolerance = TL())

2655

2652

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

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

2658

2655

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

};

  /// \ingroup graph_adaptors

2665

2662

///

2666

2663

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

2667

2664

  /// flow and circulation problems.

2668

2665

///

2669

2666

  /// ResidualDigraph can be used for composing the \e residual digraph

2670

2667

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

2671

2668

  /// be a directed graph and let \f$ F \f$ be a number type.

2672

2669

  /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.

2673

2670

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

2674

2671

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

2675

2672

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

2676

2673

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

2677

2674

  /// called residual digraph.

2678

2675

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

2679

2676

  /// multiplicities are counted, i.e. the adaptor has exactly

2680

2677

  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel

2681

2678

  /// arcs).

2682

2679

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

2683

2680

///

2684

2681

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

2685

2682

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

2686

2683

  /// It is implicitly \c const.

2687

2684

  /// \tparam CM The type of the capacity map.

2688

2685

  /// It must be an arc map of some numerical type, which defines

2689

2686

  /// the capacities in the flow problem. It is implicitly \c const.

2690

2687

  /// The default type is

2691

2688

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

2692

2689

  /// \tparam FM The type of the flow map.

2693

2690

  /// It must be an arc map of some numerical type, which defines

2694

2691

  /// the flow values in the flow problem. The default type is \c CM.

2695

2692

  /// \tparam TL The tolerance type for handling inexact computation.

2696

2693

  /// The default tolerance type depends on the value type of the

2697

2694

  /// capacity map.

2698

2695

///

2699

2696

  /// \note This adaptor is implemented using Undirector and FilterArcs

2700

2697

  /// adaptors.

2701

2698

///

2702

2699

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

2703

2700

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

2704

2701

  /// is convertible to the \c Arc type of the adapted digraph.

2705

2702

#ifdef DOXYGEN

2706

2703

  template<typename DGR, typename CM, typename FM, typename TL>

2707

2704

  class ResidualDigraph

2708

2705

#else

2709

2706

  template<typename DGR,

2710

2707

           typename CM = typename DGR::template ArcMap<int>,

2711

2708

           typename FM = CM,

2712

2709

           typename TL = Tolerance<typename CM::Value> >

2713

2710

  class ResidualDigraph

2714

2711

    : public SubDigraph<

2715

2712

        Undirector<const DGR>,

2716

2713

        ConstMap<typename DGR::Node, Const<bool, true> >,

2717

2714

        typename Undirector<const DGR>::template CombinedArcMap<

2718

2715

          _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,

2719

2716

          _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >

2720

2717

#endif

  public:

    /// The type of the underlying digraph.

2725

2722

    typedef DGR Digraph;

2726

2723

    /// The type of the capacity map.

2727

2724

    typedef CM CapacityMap;

2728

2725

    /// The type of the flow map.

2729

2726

    typedef FM FlowMap;

2730

2727

    /// The tolerance type.

2731

2728

    typedef TL Tolerance;

    typedef typename CapacityMap::Value Value;

2734

2731

    typedef ResidualDigraph Adaptor;

  protected:

    typedef Undirector<const Digraph> Undirected;

    typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;

    typedef _adaptor_bits::ResForwardFilter<const DGR, CM,

2743

2740

                                            FM, TL> ForwardFilter;

    typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,

2746

2743

                                             FM, TL> BackwardFilter;

    typedef typename Undirected::

2749

2746

      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;

    typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;

    const CapacityMap* _capacity;

2754

2751

    FlowMap* _flow;

    Undirected _graph;

2757

2754

    NodeFilter _node_filter;

2758

2755

    ForwardFilter _forward_filter;

2759

2756

    BackwardFilter _backward_filter;

2760

2757

    ArcFilter _arc_filter;

  public:

    /// \brief Constructor

2765

2762

///

2766

2763

    /// Constructor of the residual digraph adaptor. The parameters are the

2767

2764

    /// digraph, the capacity map, the flow map, and a tolerance object.

2768

2765

    ResidualDigraph(const DGR& digraph, const CM& capacity,

2769

2766

                    FM& flow, const TL& tolerance = Tolerance())

2770

2767

      : Parent(), _capacity(&capacity), _flow(&flow),

2771

2768

        _graph(digraph), _node_filter(),

2772

2769

        _forward_filter(capacity, flow, tolerance),

2773

2770

        _backward_filter(capacity, flow, tolerance),

2774

2771

        _arc_filter(_forward_filter, _backward_filter)

      Parent::initialize(_graph, _node_filter, _arc_filter);

    typedef typename Parent::Arc Arc;

    /// \brief Returns the residual capacity of the given arc.

2782

2779

///

2783

2780

    /// Returns the residual capacity of the given arc.

2784

2781

    Value residualCapacity(const Arc& a) const {

2785

2782

      if (Undirected::direction(a)) {

2786

2783

        return (*_capacity)[a] - (*_flow)[a];

2787

2784

      } else {

2788

2785

        return (*_flow)[a];

    /// \brief Augments on the given arc in the residual digraph.

2793

2790

///

2794

2791

    /// Augments on the given arc in the residual digraph. It increases

2795

2792

    /// or decreases the flow value on the original arc according to the

2796

2793

    /// direction of the residual arc.

2797

2794

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

2798

2795

      if (Undirected::direction(a)) {

2799

2796

        _flow->set(a, (*_flow)[a] + v);

2800

2797

      } else {

2801

2798

        _flow->set(a, (*_flow)[a] - v);

    /// \brief Returns \c true if the given residual arc is a forward arc.

2806

2803

///

2807

2804

    /// Returns \c true if the given residual arc has the same orientation

2808

2805

    /// as the original arc, i.e. it is a so called forward arc.

2809

2806

    static bool forward(const Arc& a) {

2810

2807

      return Undirected::direction(a);

    /// \brief Returns \c true if the given residual arc is a backward arc.

2814

2811

///

2815

2812

    /// Returns \c true if the given residual arc has the opposite orientation

2816

2813

    /// than the original arc, i.e. it is a so called backward arc.

2817

2814

    static bool backward(const Arc& a) {

2818

2815

      return !Undirected::direction(a);

    /// \brief Returns the forward oriented residual arc.

2822

2819

///

2823

2820

    /// Returns the forward oriented residual arc related to the given

2824

2821

    /// arc of the underlying digraph.

2825

2822

    static Arc forward(const typename Digraph::Arc& a) {

2826

2823

      return Undirected::direct(a, true);

    /// \brief Returns the backward oriented residual arc.

2830

2827

///

2831

2828

    /// Returns the backward oriented residual arc related to the given

2832

2829

    /// arc of the underlying digraph.

2833

2830

    static Arc backward(const typename Digraph::Arc& a) {

2834

2831

      return Undirected::direct(a, false);

    /// \brief Residual capacity map.

2838

2835

///

2839

2836

    /// This map adaptor class can be used for obtaining the residual

2840

2837

    /// capacities as an arc map of the residual digraph.

2841

2838

    /// Its value type is inherited from the capacity map.

2842

2839

    class ResidualCapacity {

2843

2840

    protected:

2844

2841

      const Adaptor* _adaptor;

2845

2842

    public:

2846

2843

      /// The key type of the map

2847

2844

      typedef Arc Key;

2848

2845

      /// The value type of the map

2849

2846

      typedef typename CapacityMap::Value Value;

      /// Constructor

2852

2849

      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)

2853

2850

        : _adaptor(&adaptor) {}

      /// Returns the value associated with the given residual arc

2856

2853

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

2857

2854

        return _adaptor->residualCapacity(a);

};

    /// \brief Returns a residual capacity map

2863

2860

///

2864

2861

    /// This function just returns a residual capacity map.

2865

2862

    ResidualCapacity residualCapacity() const {

2866

2863

      return ResidualCapacity(*this);

};

  /// \brief Returns a (read-only) Residual adaptor

2872

2869

///

2873

2870

  /// This function just returns a (read-only) \ref ResidualDigraph adaptor.

2874

2871

  /// \ingroup graph_adaptors

2875

2872

  /// \relates ResidualDigraph

2876

2873

    template<typename DGR, typename CM, typename FM>

2877

2874

  ResidualDigraph<DGR, CM, FM>

2878

2875

  residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {

2879

2876

    return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);

  template <typename DGR>

2884

2881

  class SplitNodesBase {

2885

2882

    typedef DigraphAdaptorBase<const DGR> Parent;

  public:

    typedef DGR Digraph;

2890

2887

    typedef SplitNodesBase Adaptor;

    typedef typename DGR::Node DigraphNode;

2893

2890

    typedef typename DGR::Arc DigraphArc;

    class Node;

2896

2893

    class Arc;

  private:

    template <typename T> class NodeMapBase;

2901

2898

    template <typename T> class ArcMapBase;

  public:

    class Node : public DigraphNode {

2906

2903

      friend class SplitNodesBase;

2907

2904

      template <typename T> friend class NodeMapBase;

2908

2905

    private:

      bool _in;

2911

2908

      Node(DigraphNode node, bool in)

2912

2909

        : DigraphNode(node), _in(in) {}

    public:

      Node() {}

2917

2914

      Node(Invalid) : DigraphNode(INVALID), _in(true) {}

      bool operator==(const Node& node) const {

2920

2917

        return DigraphNode::operator==(node) && _in == node._in;

      bool operator!=(const Node& node) const {

2924

2921

        return !(*this == node);

      bool operator<(const Node& node) const {

2928

2925

        return DigraphNode::operator<(node) ||

2929

2926

          (DigraphNode::operator==(node) && _in < node._in);

};

    class Arc {

2934

2931

      friend class SplitNodesBase;

2935

2932

      template <typename T> friend class ArcMapBase;

2936

2933

    private:

2937

2934

      typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;

      explicit Arc(const DigraphArc& arc) : _item(arc) {}

2940

2937

      explicit Arc(const DigraphNode& node) : _item(node) {}

      ArcImpl _item;

    public:

2945

2942

      Arc() {}

2946

2943

      Arc(Invalid) : _item(DigraphArc(INVALID)) {}

      bool operator==(const Arc& arc) const {

2949

2946

        if (_item.firstState()) {

2950

2947

          if (arc._item.firstState()) {

2951

2948

            return _item.first() == arc._item.first();

        } else {

2954

2951

          if (arc._item.secondState()) {

2955

2952

            return _item.second() == arc._item.second();

        return false;

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

2962

2959

        return !(*this == arc);

      bool operator<(const Arc& arc) const {

2966

2963

        if (_item.firstState()) {

2967

2964

          if (arc._item.firstState()) {

2968

2965

            return _item.first() < arc._item.first();

          return false;

2971

2968

        } else {

2972

2969

          if (arc._item.secondState()) {

2973

2970

            return _item.second() < arc._item.second();

          return true;

      operator DigraphArc() const { return _item.first(); }

2980

2977

      operator DigraphNode() const { return _item.second(); }

};

    void first(Node& n) const {

2985

2982

      _digraph->first(n);

2986

2983

      n._in = true;

    void next(Node& n) const {

2990

2987

      if (n._in) {

2991

2988

        n._in = false;

2992

2989

      } else {

2993

2990

        n._in = true;

2994

2991

        _digraph->next(n);

    void first(Arc& e) const {

2999

2996

      e._item.setSecond();

3000

2997

      _digraph->first(e._item.second());

3001

2998

      if (e._item.second() == INVALID) {

3002

2999

        e._item.setFirst();

3003

3000

        _digraph->first(e._item.first());

    void next(Arc& e) const {

3008

3005

      if (e._item.secondState()) {

3009

3006

        _digraph->next(e._item.second());

3010

3007

        if (e._item.second() == INVALID) {

3011

3008

          e._item.setFirst();

3012

3009

          _digraph->first(e._item.first());

      } else {

3015

3012

        _digraph->next(e._item.first());

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

3020

3017

      if (n._in) {

3021

3018

        e._item.setSecond(n);

3022

3019

      } else {

3023

3020

        e._item.setFirst();

3024

3021

        _digraph->firstOut(e._item.first(), n);

    void nextOut(Arc& e) const {

3029

3026

      if (!e._item.firstState()) {

3030

3027

        e._item.setFirst(INVALID);

3031

3028

      } else {

3032

3029

        _digraph->nextOut(e._item.first());

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

3037

3034

      if (!n._in) {

3038

3035

        e._item.setSecond(n);

3039

3036

      } else {

3040

3037

        e._item.setFirst();

3041

3038

        _digraph->firstIn(e._item.first(), n);

    void nextIn(Arc& e) const {

3046

3043

      if (!e._item.firstState()) {

3047

3044

        e._item.setFirst(INVALID);

3048

3045

      } else {

3049

3046

        _digraph->nextIn(e._item.first());

    Node source(const Arc& e) const {

3054

3051

      if (e._item.firstState()) {

3055

3052

        return Node(_digraph->source(e._item.first()), false);

3056

3053

      } else {

3057

3054

        return Node(e._item.second(), true);

    Node target(const Arc& e) const {

3062

3059

      if (e._item.firstState()) {

3063

3060

        return Node(_digraph->target(e._item.first()), true);

3064

3061

      } else {

3065

3062

        return Node(e._item.second(), false);

    int id(const Node& n) const {

3070

3067

      return (_digraph->id(n) << 1) | (n._in ? 0 : 1);

    Node nodeFromId(int ix) const {

3073

3070

      return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);

    int maxNodeId() const {

3076

3073

      return 2 * _digraph->maxNodeId() + 1;

    int id(const Arc& e) const {

3080

3077

      if (e._item.firstState()) {

3081

3078

        return _digraph->id(e._item.first()) << 1;

3082

3079

      } else {

3083

3080

        return (_digraph->id(e._item.second()) << 1) | 1;

    Arc arcFromId(int ix) const {

3087

3084

      if ((ix & 1) == 0) {

3088

3085

        return Arc(_digraph->arcFromId(ix >> 1));

3089

3086

      } else {

3090

3087

        return Arc(_digraph->nodeFromId(ix >> 1));

    int maxArcId() const {

3094

3091

      return std::max(_digraph->maxNodeId() << 1,

3095

3092

                      (_digraph->maxArcId() << 1) | 1);

    static bool inNode(const Node& n) {

3099

3096

      return n._in;

    static bool outNode(const Node& n) {

3103

3100

      return !n._in;

    static bool origArc(const Arc& e) {

3107

3104

      return e._item.firstState();

    static bool bindArc(const Arc& e) {

3111

3108

      return e._item.secondState();

    static Node inNode(const DigraphNode& n) {

3115

3112

      return Node(n, true);

    static Node outNode(const DigraphNode& n) {

3119

3116

      return Node(n, false);

    static Arc arc(const DigraphNode& n) {

3123

3120

      return Arc(n);

    static Arc arc(const DigraphArc& e) {

3127

3124

      return Arc(e);

    typedef True NodeNumTag;

3131

3128

    int nodeNum() const {

3132

3129

      return  2 * countNodes(*_digraph);

    typedef True ArcNumTag;

3136

3133

    int arcNum() const {

3137

3134

      return countArcs(*_digraph) + countNodes(*_digraph);

    typedef True FindArcTag;

3141

3138

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

3142

3139

                const Arc& prev = INVALID) const {

3143

3140

      if (inNode(u) && outNode(v)) {

3144

3141

        if (static_cast<const DigraphNode&>(u) ==

3145

3142

            static_cast<const DigraphNode&>(v) && prev == INVALID) {

3146

3143

          return Arc(u);

      else if (outNode(u) && inNode(v)) {

3150

3147

        return Arc(::lemon::findArc(*_digraph, u, v, prev));

      return INVALID;

  private:

    template <typename V>

3158

3155

    class NodeMapBase

3159

3156

      : public MapTraits<typename Parent::template NodeMap<V> > {

3160

3157

      typedef typename Parent::template NodeMap<V> NodeImpl;

3161

3158

    public:

3162

3159

      typedef Node Key;

3163

3160

      typedef V Value;

3164

3161

      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;

3165

3162

      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;

3166

3163

      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;

3167

3164

      typedef typename MapTraits<NodeImpl>::ReturnValue Reference;

3168

3165

      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;

      NodeMapBase(const SplitNodesBase<DGR>& adaptor)

3171

3168

        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}

3172

3169

      NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)

3173

3170

        : _in_map(*adaptor._digraph, value),

3174

3171

          _out_map(*adaptor._digraph, value) {}

      void set(const Node& key, const V& val) {

3177

3174

        if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }

3178

3175

        else {_out_map.set(key, val); }

      ReturnValue operator[](const Node& key) {

3182

3179

        if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }

3183

3180

        else { return _out_map[key]; }

      ConstReturnValue operator[](const Node& key) const {

3187

3184

        if (Adaptor::inNode(key)) { return _in_map[key]; }

3188

3185

        else { return _out_map[key]; }

    private:

3192

3189

      NodeImpl _in_map, _out_map;

3193

3190

};

    template <typename V>

3196

3193

    class ArcMapBase

3197

3194

      : public MapTraits<typename Parent::template ArcMap<V> > {

3198

3195

      typedef typename Parent::template ArcMap<V> ArcImpl;

3199

3196

      typedef typename Parent::template NodeMap<V> NodeImpl;

3200

3197

    public:

3201

3198

      typedef Arc Key;

3202

3199

      typedef V Value;

3203

3200

      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;

3204

3201

      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;

3205

3202

      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;

3206

3203

      typedef typename MapTraits<ArcImpl>::ReturnValue Reference;

3207

3204

      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;

      ArcMapBase(const SplitNodesBase<DGR>& adaptor)

3210

3207

        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}

3211

3208

      ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)

3212

3209

        : _arc_map(*adaptor._digraph, value),

3213

3210

          _node_map(*adaptor._digraph, value) {}

      void set(const Arc& key, const V& val) {

3216

3213

        if (SplitNodesBase<DGR>::origArc(key)) {

3217

3214

          _arc_map.set(static_cast<const DigraphArc&>(key), val);

3218

3215

        } else {

3219

3216

          _node_map.set(static_cast<const DigraphNode&>(key), val);

      ReturnValue operator[](const Arc& key) {

3224

3221

        if (SplitNodesBase<DGR>::origArc(key)) {

3225

3222

          return _arc_map[static_cast<const DigraphArc&>(key)];

3226

3223

        } else {

3227

3224

          return _node_map[static_cast<const DigraphNode&>(key)];

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

3232

3229

        if (SplitNodesBase<DGR>::origArc(key)) {

3233

3230

          return _arc_map[static_cast<const DigraphArc&>(key)];

3234

3231

        } else {

3235

3232

          return _node_map[static_cast<const DigraphNode&>(key)];

    private:

3240

3237

      ArcImpl _arc_map;

3241

3238

      NodeImpl _node_map;

3242

3239

};

  public:

    template <typename V>

3247

3244

    class NodeMap

3248

3245

      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {

3249

3246

      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;

    public:

3252

3249

      typedef V Value;

      NodeMap(const SplitNodesBase<DGR>& adaptor)

3255

3252

        : Parent(adaptor) {}

      NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)

3258

3255

        : Parent(adaptor, value) {}

    private:

3261

3258

      NodeMap& operator=(const NodeMap& cmap) {

3262

3259

        return operator=<NodeMap>(cmap);

      template <typename CMap>

3266

3263

      NodeMap& operator=(const CMap& cmap) {

3267

3264

        Parent::operator=(cmap);

3268

3265

        return *this;

};

    template <typename V>

3273

3270

    class ArcMap

3274

3271

      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {

3275

3272

      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;

    public:

3278

3275

      typedef V Value;

      ArcMap(const SplitNodesBase<DGR>& adaptor)

3281

3278

        : Parent(adaptor) {}

      ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)

3284

3281

        : Parent(adaptor, value) {}

    private:

3287

3284

      ArcMap& operator=(const ArcMap& cmap) {

3288

3285

        return operator=<ArcMap>(cmap);

      template <typename CMap>

3292

3289

      ArcMap& operator=(const CMap& cmap) {

3293

3290

        Parent::operator=(cmap);

3294

3291

        return *this;

};

  protected:

    SplitNodesBase() : _digraph(0) {}

    DGR* _digraph;

    void initialize(Digraph& digraph) {

3305

3302

      _digraph = &digraph;

};

  /// \ingroup graph_adaptors

3311

3308

///

3312

3309

  /// \brief Adaptor class for splitting the nodes of a digraph.

3313

3310

///

3314

3311

  /// SplitNodes adaptor can be used for splitting each node into an

3315

3312

  /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor

3316

3313

  /// replaces each node \f$ u \f$ in the digraph with two nodes,

3317

3314

  /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.

3318

3315

  /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the

3319

3316

  /// new target of the arc will be \f$ u_{in} \f$ and similarly the

3320

3317

  /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.

3321

3318

  /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$

3322

3319

  /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.

3323

3320

///

3324

3321

  /// The aim of this class is running an algorithm with respect to node

3325

3322

  /// costs or capacities if the algorithm considers only arc costs or

3326

3323

  /// capacities directly.

3327

3324

  /// In this case you can use \c SplitNodes adaptor, and set the node

3328

3325

  /// costs/capacities of the original digraph to the \e bind \e arcs

3329

3326

  /// in the adaptor.

3330

3327

///

3331

3328

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

3332

3329

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

3333

3330

  /// It is implicitly \c const.

3334

3331

///

3335

3332

  /// \note The \c Node type of this adaptor is converible to the \c Node

3336

3333

  /// type of the adapted digraph.

3337

3334

  template <typename DGR>

3338

3335

#ifdef DOXYGEN

3339

3336

  class SplitNodes {

3340

3337

#else

3341

3338

  class SplitNodes

3342

3339

    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {

3343

3340

#endif

3344

3341

    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;

  public:

3347

3344

    typedef DGR Digraph;

    typedef typename DGR::Node DigraphNode;

3350

3347

    typedef typename DGR::Arc DigraphArc;

    typedef typename Parent::Node Node;

3353

3350

    typedef typename Parent::Arc Arc;

    /// \brief Constructor

3356

3353

///

3357

3354

    /// Constructor of the adaptor.

3358

3355

    SplitNodes(const DGR& g) {

3359

3356

      Parent::initialize(g);

    /// \brief Returns \c true if the given node is an in-node.

3363

3360

///

3364

3361

    /// Returns \c true if the given node is an in-node.

3365

3362

    static bool inNode(const Node& n) {

3366

3363

      return Parent::inNode(n);

    /// \brief Returns \c true if the given node is an out-node.

3370

3367

///

3371

3368

    /// Returns \c true if the given node is an out-node.

3372

3369

    static bool outNode(const Node& n) {

3373

3370

      return Parent::outNode(n);

    /// \brief Returns \c true if the given arc is an original arc.

3377

3374

///

3378

3375

    /// Returns \c true if the given arc is one of the arcs in the

3379

3376

    /// original digraph.

3380

3377

    static bool origArc(const Arc& a) {

3381

3378

      return Parent::origArc(a);

    /// \brief Returns \c true if the given arc is a bind arc.

3385

3382

///

3386

3383

    /// Returns \c true if the given arc is a bind arc, i.e. it connects

3387

3384

    /// an in-node and an out-node.

3388

3385

    static bool bindArc(const Arc& a) {

3389

3386

      return Parent::bindArc(a);

    /// \brief Returns the in-node created from the given original node.

3393

3390

///

3394

3391

    /// Returns the in-node created from the given original node.

3395

3392

    static Node inNode(const DigraphNode& n) {

3396

3393

      return Parent::inNode(n);

    /// \brief Returns the out-node created from the given original node.

3400

3397

///

3401

3398

    /// Returns the out-node created from the given original node.

3402

3399

    static Node outNode(const DigraphNode& n) {

3403

3400

      return Parent::outNode(n);

    /// \brief Returns the bind arc that corresponds to the given

3407

3404

    /// original node.

3408

3405

///

3409

3406

    /// Returns the bind arc in the adaptor that corresponds to the given

3410

3407

    /// original node, i.e. the arc connecting the in-node and out-node

3411

3408

    /// of \c n.

3412

3409

    static Arc arc(const DigraphNode& n) {

3413

3410

      return Parent::arc(n);

    /// \brief Returns the arc that corresponds to the given original arc.

3417

3414

///

3418

3415

    /// Returns the arc in the adaptor that corresponds to the given

3419

3416

    /// original arc.

3420

3417

    static Arc arc(const DigraphArc& a) {

3421

3418

      return Parent::arc(a);

    /// \brief Node map combined from two original node maps

3425

3422

///

3426

3423

    /// This map adaptor class adapts two node maps of the original digraph

3427

3424

    /// to get a node map of the split digraph.

3428

3425

    /// Its value type is inherited from the first node map type (\c IN).

3429

3426

    /// \tparam IN The type of the node map for the in-nodes.

3430

3427

    /// \tparam OUT The type of the node map for the out-nodes.

3431

3428

    template <typename IN, typename OUT>

3432

3429

    class CombinedNodeMap {

3433

3430

    public:

      /// The key type of the map

3436

3433

      typedef Node Key;

3437

3434

      /// The value type of the map

3438

3435

      typedef typename IN::Value Value;

      typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;

3441

3438

      typedef typename MapTraits<IN>::ReturnValue ReturnValue;

3442

3439

      typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;

3443

3440

      typedef typename MapTraits<IN>::ReturnValue Reference;

3444

3441

      typedef typename MapTraits<IN>::ConstReturnValue ConstReference;

      /// Constructor

3447

3444

      CombinedNodeMap(IN& in_map, OUT& out_map)

3448

3445

        : _in_map(in_map), _out_map(out_map) {}

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

3451

3448

      Value operator[](const Key& key) const {

3452

3449

        if (SplitNodesBase<const DGR>::inNode(key)) {

3453

3450

          return _in_map[key];

3454

3451

        } else {

3455

3452

          return _out_map[key];

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

3460

3457

      Value& operator[](const Key& key) {

3461

3458

        if (SplitNodesBase<const DGR>::inNode(key)) {

3462

3459

          return _in_map[key];

3463

3460

        } else {

3464

3461

          return _out_map[key];

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

3469

3466

      void set(const Key& key, const Value& value) {

3470

3467

        if (SplitNodesBase<const DGR>::inNode(key)) {

3471

3468

          _in_map.set(key, value);

3472

3469

        } else {

3473

3470

          _out_map.set(key, value);

    private:

      IN& _in_map;

3480

3477

      OUT& _out_map;

};

    /// \brief Returns a combined node map

3486

3483

///

3487

3484

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

3488

3485

    template <typename IN, typename OUT>

3489

3486

    static CombinedNodeMap<IN, OUT>

3490

3487

    combinedNodeMap(IN& in_map, OUT& out_map) {

3491

3488

      return CombinedNodeMap<IN, OUT>(in_map, out_map);

    template <typename IN, typename OUT>

3495

3492

    static CombinedNodeMap<const IN, OUT>

3496

3493

    combinedNodeMap(const IN& in_map, OUT& out_map) {

3497

3494

      return CombinedNodeMap<const IN, OUT>(in_map, out_map);

    template <typename IN, typename OUT>

3501

3498

    static CombinedNodeMap<IN, const OUT>

3502

3499

    combinedNodeMap(IN& in_map, const OUT& out_map) {

3503

3500

      return CombinedNodeMap<IN, const OUT>(in_map, out_map);

    template <typename IN, typename OUT>

3507

3504

    static CombinedNodeMap<const IN, const OUT>

3508

3505

    combinedNodeMap(const IN& in_map, const OUT& out_map) {

3509

3506

      return CombinedNodeMap<const IN, const OUT>(in_map, out_map);

    /// \brief Arc map combined from an arc map and a node map of the

3513

3510

    /// original digraph.

3514

3511

///

3515

3512

    /// This map adaptor class adapts an arc map and a node map of the

3516

3513

    /// original digraph to get an arc map of the split digraph.

3517

3514

    /// Its value type is inherited from the original arc map type (\c AM).

3518

3515

    /// \tparam AM The type of the arc map.

3519

3516

    /// \tparam NM the type of the node map.

3520

3517

    template <typename AM, typename NM>

3521

3518

    class CombinedArcMap {

3522

3519

    public:

      /// The key type of the map

3525

3522

      typedef Arc Key;

3526

3523

      /// The value type of the map

3527

3524

      typedef typename AM::Value Value;

      typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;

3530

3527

      typedef typename MapTraits<AM>::ReturnValue ReturnValue;

3531

3528

      typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;

3532

3529

      typedef typename MapTraits<AM>::ReturnValue Reference;

3533

3530

      typedef typename MapTraits<AM>::ConstReturnValue ConstReference;

      /// Constructor

3536

3533

      CombinedArcMap(AM& arc_map, NM& node_map)

3537

3534

        : _arc_map(arc_map), _node_map(node_map) {}

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

3540

3537

      Value operator[](const Key& arc) const {

3541

3538

        if (SplitNodesBase<const DGR>::origArc(arc)) {

3542

3539

          return _arc_map[arc];

3543

3540

        } else {

3544

3541

          return _node_map[arc];

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

3549

3546

      Value& operator[](const Key& arc) {

3550

3547

        if (SplitNodesBase<const DGR>::origArc(arc)) {

3551

3548

          return _arc_map[arc];

3552

3549

        } else {

3553

3550

          return _node_map[arc];

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

3558

3555

      void set(const Arc& arc, const Value& val) {

3559

3556

        if (SplitNodesBase<const DGR>::origArc(arc)) {

3560

3557

          _arc_map.set(arc, val);

3561

3558

        } else {

3562

3559

          _node_map.set(arc, val);

    private:

      AM& _arc_map;

3569

3566

      NM& _node_map;

};

    /// \brief Returns a combined arc map

3574

3571

///

3575

3572

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

3576

3573

    template <typename ArcMap, typename NodeMap>

3577

3574

    static CombinedArcMap<ArcMap, NodeMap>

3578

3575

    combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {

3579

3576

      return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);

    template <typename ArcMap, typename NodeMap>

3583

3580

    static CombinedArcMap<const ArcMap, NodeMap>

3584

3581

    combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {

3585

3582

      return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);

    template <typename ArcMap, typename NodeMap>

3589

3586

    static CombinedArcMap<ArcMap, const NodeMap>

3590

3587

    combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {

3591

3588

      return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);

    template <typename ArcMap, typename NodeMap>

3595

3592

    static CombinedArcMap<const ArcMap, const NodeMap>

3596

3593

    combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {

3597

3594

      return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);

};

  /// \brief Returns a (read-only) SplitNodes adaptor

3603

3600

///

3604

3601

  /// This function just returns a (read-only) \ref SplitNodes adaptor.

3605

3602

  /// \ingroup graph_adaptors

3606

3603

  /// \relates SplitNodes

3607

3604

  template<typename DGR>

3608

3605

  SplitNodes<DGR>

3609

3606

  splitNodes(const DGR& digraph) {

3610

3607

    return SplitNodes<DGR>(digraph);

#undef LEMON_SCOPE_FIX

} //namespace lemon

#endif //LEMON_ADAPTORS_H

RhodeCode

Login to your account