LEMON/LEMON-main Changeset - r452:aea2dc0518ce

@@ -285,1683 +285,1715 @@

285

286

287

      template <typename CMap>

288

      ArcMap& operator=(const CMap& cmap) {

289

        Parent::operator=(cmap);

290

        return *this;

291

292

};

293

294

    template <typename _Value>

295

    class EdgeMap : public Graph::template EdgeMap<_Value> {

296

    public:

297

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

298

      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)

299

        : Parent(*adapter._graph) {}

300

      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)

301

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

302

303

    private:

304

      EdgeMap& operator=(const EdgeMap& cmap) {

305

        return operator=<EdgeMap>(cmap);

306

307

308

      template <typename CMap>

309

      EdgeMap& operator=(const CMap& cmap) {

310

        Parent::operator=(cmap);

311

        return *this;

312

313

};

314

315

};

316

317

  template <typename _Digraph>

318

  class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {

319

  public:

320

    typedef _Digraph Digraph;

321

    typedef DigraphAdaptorBase<_Digraph> Parent;

322

  protected:

323

    ReverseDigraphBase() : Parent() { }

324

  public:

325

    typedef typename Parent::Node Node;

326

    typedef typename Parent::Arc Arc;

327

328

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

329

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

330

331

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

332

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

333

334

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

335

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

336

337

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

338

339

    typedef FindArcTagIndicator<Digraph> FindArcTag;

340

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

341

                const Arc& prev = INVALID) const {

342

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

343

344

345

};

346

347

  /// \ingroup graph_adaptors

348

///

349

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

350

  /// a digraph.

351

///

352

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

353

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

354

///

355

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

356

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

357

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

358

///

359

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

360

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

361

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

362

///

363

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

364

  /// digraph are convertible to each other.

365

  template<typename _Digraph>

366

  class ReverseDigraph :

367

    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {

368

  public:

369

    typedef _Digraph Digraph;

370

    typedef DigraphAdaptorExtender<

371

      ReverseDigraphBase<_Digraph> > Parent;

372

  protected:

373

    ReverseDigraph() { }

374

  public:

375

376

    /// \brief Constructor

377

///

378

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

379

    explicit ReverseDigraph(Digraph& digraph) {

380

      Parent::setDigraph(digraph);

381

382

};

383

384

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

385

///

386

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

387

  /// \ingroup graph_adaptors

388

  /// \relates ReverseDigraph

389

  template<typename Digraph>

390

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

391

    return ReverseDigraph<const Digraph>(digraph);

  template <typename _Digraph, typename _NodeFilterMap,

396

            typename _ArcFilterMap, bool _checked = true>

397

  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {

398

  public:

399

    typedef _Digraph Digraph;

400

    typedef _NodeFilterMap NodeFilterMap;

401

    typedef _ArcFilterMap ArcFilterMap;

402

403

    typedef SubDigraphBase Adaptor;

404

    typedef DigraphAdaptorBase<_Digraph> Parent;

405

  protected:

406

    NodeFilterMap* _node_filter;

407

    ArcFilterMap* _arc_filter;

408

    SubDigraphBase()

409

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

410

411

    void setNodeFilterMap(NodeFilterMap& node_filter) {

412

      _node_filter = &node_filter;

413

414

    void setArcFilterMap(ArcFilterMap& arc_filter) {

415

      _arc_filter = &arc_filter;

416

417

418

  public:

419

420

    typedef typename Parent::Node Node;

421

    typedef typename Parent::Arc Arc;

422

423

    void first(Node& i) const {

424

      Parent::first(i);

425

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

426

427

428

    void first(Arc& i) const {

429

      Parent::first(i);

430

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

431

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

432

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

433

        Parent::next(i);

434

435

436

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

437

      Parent::firstIn(i, n);

438

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

439

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

440

        Parent::nextIn(i);

441

442

443

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

444

      Parent::firstOut(i, n);

445

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

446

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

447

        Parent::nextOut(i);

448

449

450

    void next(Node& i) const {

451

      Parent::next(i);

452

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

453

454

455

    void next(Arc& i) const {

456

      Parent::next(i);

457

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

458

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

459

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

460

        Parent::next(i);

461

462

463

    void nextIn(Arc& i) const {

464

      Parent::nextIn(i);

465

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

466

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

467

        Parent::nextIn(i);

468

469

470

    void nextOut(Arc& i) const {

471

      Parent::nextOut(i);

472

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

473

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

474

        Parent::nextOut(i);

475

476

477

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

478

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

479

480

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

481

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

482

483

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

484

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

477

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

478

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

479

480

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

481

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

    typedef False NodeNumTag;

487

484

    typedef False ArcNumTag;

    typedef FindArcTagIndicator<Digraph> FindArcTag;

490

487

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

491

488

                const Arc& prev = INVALID) const {

492

489

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

493

490

        return INVALID;

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

496

493

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

497

494

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

      return arc;

    template <typename _Value>

503

500

    class NodeMap : public SubMapExtender<Adaptor,

504

501

      typename Parent::template NodeMap<_Value> > {

505

502

    public:

506

503

      typedef _Value Value;

507

504

      typedef SubMapExtender<Adaptor, typename Parent::

508

505

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

511

508

        : MapParent(adaptor) {}

512

509

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

513

510

        : MapParent(adaptor, value) {}

    private:

516

513

      NodeMap& operator=(const NodeMap& cmap) {

517

514

        return operator=<NodeMap>(cmap);

      template <typename CMap>

521

518

      NodeMap& operator=(const CMap& cmap) {

522

519

        MapParent::operator=(cmap);

523

520

        return *this;

};

    template <typename _Value>

528

525

    class ArcMap : public SubMapExtender<Adaptor,

529

526

      typename Parent::template ArcMap<_Value> > {

530

527

    public:

531

528

      typedef _Value Value;

532

529

      typedef SubMapExtender<Adaptor, typename Parent::

533

530

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor)

536

533

        : MapParent(adaptor) {}

537

534

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

538

535

        : MapParent(adaptor, value) {}

    private:

541

538

      ArcMap& operator=(const ArcMap& cmap) {

542

539

        return operator=<ArcMap>(cmap);

      template <typename CMap>

546

543

      ArcMap& operator=(const CMap& cmap) {

547

544

        MapParent::operator=(cmap);

548

545

        return *this;

};

};

  template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>

555

552

  class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>

556

553

    : public DigraphAdaptorBase<_Digraph> {

557

554

  public:

558

555

    typedef _Digraph Digraph;

559

556

    typedef _NodeFilterMap NodeFilterMap;

560

557

    typedef _ArcFilterMap ArcFilterMap;

    typedef SubDigraphBase Adaptor;

563

560

    typedef DigraphAdaptorBase<Digraph> Parent;

564

561

  protected:

565

562

    NodeFilterMap* _node_filter;

566

563

    ArcFilterMap* _arc_filter;

567

564

    SubDigraphBase()

568

565

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

    void setNodeFilterMap(NodeFilterMap& node_filter) {

571

568

      _node_filter = &node_filter;

    void setArcFilterMap(ArcFilterMap& arc_filter) {

574

571

      _arc_filter = &arc_filter;

  public:

    typedef typename Parent::Node Node;

580

577

    typedef typename Parent::Arc Arc;

    void first(Node& i) const {

583

580

      Parent::first(i);

584

581

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

    void first(Arc& i) const {

588

585

      Parent::first(i);

589

586

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

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

593

590

      Parent::firstIn(i, n);

594

591

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

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

598

595

      Parent::firstOut(i, n);

599

596

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

    void next(Node& i) const {

603

600

      Parent::next(i);

604

601

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

    void next(Arc& i) const {

607

604

      Parent::next(i);

608

605

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

    void nextIn(Arc& i) const {

611

608

      Parent::nextIn(i);

612

609

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

    void nextOut(Arc& i) const {

616

613

      Parent::nextOut(i);

617

614

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

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

621

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

622

623

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

624

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

625

626

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

627

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

617

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

618

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

619

620

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

621

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

    typedef False NodeNumTag;

630

624

    typedef False ArcNumTag;

    typedef FindArcTagIndicator<Digraph> FindArcTag;

633

627

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

634

628

                const Arc& prev = INVALID) const {

635

629

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

636

630

        return INVALID;

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

639

633

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

640

634

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

      return arc;

    template <typename _Value>

646

640

    class NodeMap : public SubMapExtender<Adaptor,

647

641

      typename Parent::template NodeMap<_Value> > {

648

642

    public:

649

643

      typedef _Value Value;

650

644

      typedef SubMapExtender<Adaptor, typename Parent::

651

645

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

654

648

        : MapParent(adaptor) {}

655

649

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

656

650

        : MapParent(adaptor, value) {}

    private:

659

653

      NodeMap& operator=(const NodeMap& cmap) {

660

654

        return operator=<NodeMap>(cmap);

      template <typename CMap>

664

658

      NodeMap& operator=(const CMap& cmap) {

665

659

        MapParent::operator=(cmap);

666

660

        return *this;

};

    template <typename _Value>

671

665

    class ArcMap : public SubMapExtender<Adaptor,

672

666

      typename Parent::template ArcMap<_Value> > {

673

667

    public:

674

668

      typedef _Value Value;

675

669

      typedef SubMapExtender<Adaptor, typename Parent::

676

670

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor)

679

673

        : MapParent(adaptor) {}

680

674

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

681

675

        : MapParent(adaptor, value) {}

    private:

684

678

      ArcMap& operator=(const ArcMap& cmap) {

685

679

        return operator=<ArcMap>(cmap);

      template <typename CMap>

689

683

      ArcMap& operator=(const CMap& cmap) {

690

684

        MapParent::operator=(cmap);

691

685

        return *this;

};

};

  /// \ingroup graph_adaptors

698

692

///

699

693

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

700

694

///

701

695

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

702

696

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

703

697

  /// define the filters for nodes and arcs.

704

698

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

705

699

  /// shown in the subdigraph. This adaptor conforms to the \ref

706

700

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

707

701

  /// is \c true, then the arcs incident to hidden nodes are also

708

702

  /// filtered out.

709

703

///

710

704

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

711

705

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

712

706

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

713

707

///

714

708

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

715

709

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

716

710

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

717

711

  /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the

718

712

  /// adapted digraph. The default map type is

719

713

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

720

714

  /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the

721

715

  /// adapted digraph. The default map type is

722

716

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

723

717

  /// \tparam _checked If this parameter is set to \c false, then the arc

724

718

  /// filtering is not checked with respect to the node filter.

725

719

  /// Otherwise, each arc that is incident to a hidden node is automatically

726

720

  /// filtered out. This is the default option.

727

721

///

728

722

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

729

723

  /// digraph are convertible to each other.

730

724

///

731

725

  /// \see FilterNodes

732

726

  /// \see FilterArcs

733

727

#ifdef DOXYGEN

734

728

  template<typename _Digraph,

735

729

           typename _NodeFilterMap,

736

730

           typename _ArcFilterMap,

737

731

           bool _checked>

738

732

#else

739

733

  template<typename _Digraph,

740

734

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

741

735

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

742

736

           bool _checked = true>

743

737

#endif

744

738

  class SubDigraph

745

739

    : public DigraphAdaptorExtender<

746

740

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

747

741

  public:

748

742

    /// The type of the adapted digraph.

749

743

    typedef _Digraph Digraph;

750

744

    /// The type of the node filter map.

751

745

    typedef _NodeFilterMap NodeFilterMap;

752

746

    /// The type of the arc filter map.

753

747

    typedef _ArcFilterMap ArcFilterMap;

    typedef DigraphAdaptorExtender<

756

750

      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> >

757

751

    Parent;

    typedef typename Parent::Node Node;

760

754

    typedef typename Parent::Arc Arc;

  protected:

763

757

    SubDigraph() { }

764

758

  public:

    /// \brief Constructor

767

761

///

768

762

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

769

763

    /// given node and arc filter maps.

770

764

    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,

771

765

               ArcFilterMap& arc_filter) {

772

766

      setDigraph(digraph);

773

767

      setNodeFilterMap(node_filter);

774

768

      setArcFilterMap(arc_filter);

    /// \brief Hides the given node

771

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

778

772

///

779

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

780

    /// i.e. the iteration jumps over it.

773

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

781

774

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

782

    /// to be \c false in the node filter map.

783

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

784

785

    /// \brief Hides the given arc

775

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

776

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

777

778

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

786

779

///

787

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

788

    /// i.e. the iteration jumps over it.

780

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

789

781

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

790

    /// to be \c false in the arc filter map.

791

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

792

793

    /// \brief Shows the given node

782

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

783

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

784

785

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

794

786

///

795

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

796

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

797

    /// to be \c true in the node filter map.

798

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

799

800

    /// \brief Shows the given arc

787

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

788

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

789

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

790

791

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

801

792

///

802

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

803

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

804

    /// to be \c true in the arc filter map.

805

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

806

807

    /// \brief Returns \c true if the given node is hidden.

793

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

794

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

795

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

796

797

    /// \brief Disables the given node

808

798

///

809

    /// This function returns \c true if the given node is hidden.

810

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

811

812

    /// \brief Returns \c true if the given arc is hidden.

799

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

800

    /// so the iteration jumps over it.

801

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

802

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

803

804

    /// \brief Disables the given arc

813

805

///

814

    /// This function returns \c true if the given arc is hidden.

815

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

806

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

807

    /// so the iteration jumps over it.

808

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

809

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

810

811

    /// \brief Enables the given node

812

///

813

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

814

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

815

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

816

817

    /// \brief Enables the given arc

818

///

819

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

820

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

821

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

};

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

820

826

///

821

827

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

822

828

  /// \ingroup graph_adaptors

823

829

  /// \relates SubDigraph

824

830

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

825

831

  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>

826

832

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

827

833

    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>

828

834

      (digraph, nfm, afm);

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

832

838

  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>

833

839

  subDigraph(const Digraph& digraph,

834

840

             const NodeFilterMap& nfm, ArcFilterMap& afm) {

835

841

    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>

836

842

      (digraph, nfm, afm);

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

840

846

  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>

841

847

  subDigraph(const Digraph& digraph,

842

848

             NodeFilterMap& nfm, const ArcFilterMap& afm) {

843

849

    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>

844

850

      (digraph, nfm, afm);

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

848

854

  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>

849

855

  subDigraph(const Digraph& digraph,

850

856

             const NodeFilterMap& nfm, const ArcFilterMap& afm) {

851

857

    return SubDigraph<const Digraph, const NodeFilterMap,

852

858

      const ArcFilterMap>(digraph, nfm, afm);

  template <typename _Graph, typename _NodeFilterMap,

857

863

            typename _EdgeFilterMap, bool _checked = true>

858

864

  class SubGraphBase : public GraphAdaptorBase<_Graph> {

859

865

  public:

860

866

    typedef _Graph Graph;

861

867

    typedef _NodeFilterMap NodeFilterMap;

862

868

    typedef _EdgeFilterMap EdgeFilterMap;

    typedef SubGraphBase Adaptor;

865

871

    typedef GraphAdaptorBase<_Graph> Parent;

866

872

  protected:

    NodeFilterMap* _node_filter_map;

869

875

    EdgeFilterMap* _edge_filter_map;

    SubGraphBase()

872

878

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

    void setNodeFilterMap(NodeFilterMap& node_filter_map) {

875

881

      _node_filter_map=&node_filter_map;

    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {

878

884

      _edge_filter_map=&edge_filter_map;

  public:

    typedef typename Parent::Node Node;

884

890

    typedef typename Parent::Arc Arc;

885

891

    typedef typename Parent::Edge Edge;

    void first(Node& i) const {

888

894

      Parent::first(i);

889

895

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

    void first(Arc& i) const {

893

899

      Parent::first(i);

894

900

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

895

901

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

896

902

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

897

903

        Parent::next(i);

    void first(Edge& i) const {

901

907

      Parent::first(i);

902

908

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

903

909

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

904

910

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

905

911

        Parent::next(i);

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

909

915

      Parent::firstIn(i, n);

910

916

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

911

917

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

912

918

        Parent::nextIn(i);

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

916

922

      Parent::firstOut(i, n);

917

923

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

918

924

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

919

925

        Parent::nextOut(i);

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

923

929

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

924

930

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

925

931

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

926

932

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

927

933

        Parent::nextInc(i, d);

    void next(Node& i) const {

931

937

      Parent::next(i);

932

938

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

    void next(Arc& i) const {

936

942

      Parent::next(i);

937

943

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

938

944

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

939

945

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

940

946

        Parent::next(i);

    void next(Edge& i) const {

944

950

      Parent::next(i);

945

951

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

946

952

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

947

953

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

948

954

        Parent::next(i);

    void nextIn(Arc& i) const {

952

958

      Parent::nextIn(i);

953

959

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

954

960

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

955

961

        Parent::nextIn(i);

    void nextOut(Arc& i) const {

959

965

      Parent::nextOut(i);

960

966

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

961

967

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

962

968

        Parent::nextOut(i);

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

966

972

      Parent::nextInc(i, d);

967

973

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

968

974

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

969

975

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

970

976

        Parent::nextInc(i, d);

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

974

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

975

976

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

977

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

978

979

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

980

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

979

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

980

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

981

982

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

983

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

    typedef False NodeNumTag;

983

986

    typedef False ArcNumTag;

984

987

    typedef False EdgeNumTag;

    typedef FindArcTagIndicator<Graph> FindArcTag;

987

990

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

988

991

                const Arc& prev = INVALID) const {

989

992

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

990

993

        return INVALID;

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

993

996

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

994

997

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

      return arc;

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

1000

1003

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

1001

1004

                  const Edge& prev = INVALID) const {

1002

1005

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

1003

1006

        return INVALID;

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

1006

1009

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

1007

1010

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

      return edge;

    template <typename _Value>

1013

1016

    class NodeMap : public SubMapExtender<Adaptor,

1014

1017

      typename Parent::template NodeMap<_Value> > {

1015

1018

    public:

1016

1019

      typedef _Value Value;

1017

1020

      typedef SubMapExtender<Adaptor, typename Parent::

1018

1021

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

1021

1024

        : MapParent(adaptor) {}

1022

1025

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

1023

1026

        : MapParent(adaptor, value) {}

    private:

1026

1029

      NodeMap& operator=(const NodeMap& cmap) {

1027

1030

        return operator=<NodeMap>(cmap);

      template <typename CMap>

1031

1034

      NodeMap& operator=(const CMap& cmap) {

1032

1035

        MapParent::operator=(cmap);

1033

1036

        return *this;

};

    template <typename _Value>

1038

1041

    class ArcMap : public SubMapExtender<Adaptor,

1039

1042

      typename Parent::template ArcMap<_Value> > {

1040

1043

    public:

1041

1044

      typedef _Value Value;

1042

1045

      typedef SubMapExtender<Adaptor, typename Parent::

1043

1046

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor)

1046

1049

        : MapParent(adaptor) {}

1047

1050

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

1048

1051

        : MapParent(adaptor, value) {}

    private:

1051

1054

      ArcMap& operator=(const ArcMap& cmap) {

1052

1055

        return operator=<ArcMap>(cmap);

      template <typename CMap>

1056

1059

      ArcMap& operator=(const CMap& cmap) {

1057

1060

        MapParent::operator=(cmap);

1058

1061

        return *this;

};

    template <typename _Value>

1063

1066

    class EdgeMap : public SubMapExtender<Adaptor,

1064

1067

      typename Parent::template EdgeMap<_Value> > {

1065

1068

    public:

1066

1069

      typedef _Value Value;

1067

1070

      typedef SubMapExtender<Adaptor, typename Parent::

1068

1071

                             template EdgeMap<Value> > MapParent;

      EdgeMap(const Adaptor& adaptor)

1071

1074

        : MapParent(adaptor) {}

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

1074

1077

        : MapParent(adaptor, value) {}

    private:

1077

1080

      EdgeMap& operator=(const EdgeMap& cmap) {

1078

1081

        return operator=<EdgeMap>(cmap);

      template <typename CMap>

1082

1085

      EdgeMap& operator=(const CMap& cmap) {

1083

1086

        MapParent::operator=(cmap);

1084

1087

        return *this;

};

};

  template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>

1091

1094

  class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>

1092

1095

    : public GraphAdaptorBase<_Graph> {

1093

1096

  public:

1094

1097

    typedef _Graph Graph;

1095

1098

    typedef _NodeFilterMap NodeFilterMap;

1096

1099

    typedef _EdgeFilterMap EdgeFilterMap;

    typedef SubGraphBase Adaptor;

1099

1102

    typedef GraphAdaptorBase<_Graph> Parent;

1100

1103

  protected:

1101

1104

    NodeFilterMap* _node_filter_map;

1102

1105

    EdgeFilterMap* _edge_filter_map;

1103

1106

    SubGraphBase() : Parent(),

1104

1107

                     _node_filter_map(0), _edge_filter_map(0) { }

    void setNodeFilterMap(NodeFilterMap& node_filter_map) {

1107

1110

      _node_filter_map=&node_filter_map;

    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {

1110

1113

      _edge_filter_map=&edge_filter_map;

  public:

    typedef typename Parent::Node Node;

1116

1119

    typedef typename Parent::Arc Arc;

1117

1120

    typedef typename Parent::Edge Edge;

    void first(Node& i) const {

1120

1123

      Parent::first(i);

1121

1124

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

    void first(Arc& i) const {

1125

1128

      Parent::first(i);

1126

1129

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

    void first(Edge& i) const {

1130

1133

      Parent::first(i);

1131

1134

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

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

1135

1138

      Parent::firstIn(i, n);

1136

1139

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

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

1140

1143

      Parent::firstOut(i, n);

1141

1144

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

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

1145

1148

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

1146

1149

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

    void next(Node& i) const {

1150

1153

      Parent::next(i);

1151

1154

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

    void next(Arc& i) const {

1154

1157

      Parent::next(i);

1155

1158

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

    void next(Edge& i) const {

1158

1161

      Parent::next(i);

1159

1162

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

    void nextIn(Arc& i) const {

1162

1165

      Parent::nextIn(i);

1163

1166

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

    void nextOut(Arc& i) const {

1167

1170

      Parent::nextOut(i);

1168

1171

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

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

1171

1174

      Parent::nextInc(i, d);

1172

1175

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

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

1176

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

1177

1178

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

1179

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

1180

1181

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

1182

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

1178

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

1179

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

1180

1181

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

1182

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

1183

1184

    typedef False NodeNumTag;

1185

    typedef False ArcNumTag;

1186

    typedef False EdgeNumTag;

1187

1188

    typedef FindArcTagIndicator<Graph> FindArcTag;

1189

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

1190

                const Arc& prev = INVALID) const {

1191

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

1192

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

1193

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

1194

1195

      return arc;

1196

1197

1198

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

1199

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

1200

                  const Edge& prev = INVALID) const {

1201

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

1202

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

1203

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

1204

1205

      return edge;

1206

1207

1208

    template <typename _Value>

1209

    class NodeMap : public SubMapExtender<Adaptor,

1210

      typename Parent::template NodeMap<_Value> > {

1211

    public:

1212

      typedef _Value Value;

1213

      typedef SubMapExtender<Adaptor, typename Parent::

1214

                             template NodeMap<Value> > MapParent;

1215

1216

      NodeMap(const Adaptor& adaptor)

1217

        : MapParent(adaptor) {}

1218

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

1219

        : MapParent(adaptor, value) {}

1220

1221

    private:

1222

      NodeMap& operator=(const NodeMap& cmap) {

1223

        return operator=<NodeMap>(cmap);

1224

1225

1226

      template <typename CMap>

1227

      NodeMap& operator=(const CMap& cmap) {

1228

        MapParent::operator=(cmap);

1229

        return *this;

1230

1231

};

1232

1233

    template <typename _Value>

1234

    class ArcMap : public SubMapExtender<Adaptor,

1235

      typename Parent::template ArcMap<_Value> > {

1236

    public:

1237

      typedef _Value Value;

1238

      typedef SubMapExtender<Adaptor, typename Parent::

1239

                             template ArcMap<Value> > MapParent;

1240

1241

      ArcMap(const Adaptor& adaptor)

1242

        : MapParent(adaptor) {}

1243

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

1244

        : MapParent(adaptor, value) {}

1245

1246

    private:

1247

      ArcMap& operator=(const ArcMap& cmap) {

1248

        return operator=<ArcMap>(cmap);

1249

1250

1251

      template <typename CMap>

1252

      ArcMap& operator=(const CMap& cmap) {

1253

        MapParent::operator=(cmap);

1254

        return *this;

1255

1256

};

1257

1258

    template <typename _Value>

1259

    class EdgeMap : public SubMapExtender<Adaptor,

1260

      typename Parent::template EdgeMap<_Value> > {

1261

    public:

1262

      typedef _Value Value;

1263

      typedef SubMapExtender<Adaptor, typename Parent::

1264

                             template EdgeMap<Value> > MapParent;

1265

1266

      EdgeMap(const Adaptor& adaptor)

1267

        : MapParent(adaptor) {}

1268

1269

      EdgeMap(const Adaptor& adaptor, const _Value& value)

1270

        : MapParent(adaptor, value) {}

1271

1272

    private:

1273

      EdgeMap& operator=(const EdgeMap& cmap) {

1274

        return operator=<EdgeMap>(cmap);

1275

1276

1277

      template <typename CMap>

1278

      EdgeMap& operator=(const CMap& cmap) {

1279

        MapParent::operator=(cmap);

1280

        return *this;

1281

1282

};

1283

1284

};

1285

1286

  /// \ingroup graph_adaptors

1287

///

1288

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

1289

  /// graph.

1290

///

1291

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

1292

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

1293

  /// define the filters for nodes and edges.

1294

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

1295

  /// shown in the subgraph. This adaptor conforms to the \ref

1296

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

1297

  /// \c true, then the edges incident to hidden nodes are also

1298

  /// filtered out.

1299

///

1300

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

1301

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

1302

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

1303

///

1304

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

1305

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

1306

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

1307

  /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the

1308

  /// adapted graph. The default map type is

1309

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

1310

  /// \tparam _EdgeFilterMap A \c bool (or convertible) edge map of the

1311

  /// adapted graph. The default map type is

1312

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

1313

  /// \tparam _checked If this parameter is set to \c false, then the edge

1314

  /// filtering is not checked with respect to the node filter.

1315

  /// Otherwise, each edge that is incident to a hidden node is automatically

1316

  /// filtered out. This is the default option.

1317

///

1318

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

1319

  /// adapted graph are convertible to each other.

1320

///

1321

  /// \see FilterNodes

1322

  /// \see FilterEdges

1323

#ifdef DOXYGEN

1324

  template<typename _Graph,

1325

           typename _NodeFilterMap,

1326

           typename _EdgeFilterMap,

1327

           bool _checked>

1328

#else

1329

  template<typename _Graph,

1330

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

1331

           typename _EdgeFilterMap = typename _Graph::template EdgeMap<bool>,

1332

           bool _checked = true>

1333

#endif

1334

  class SubGraph

1335

    : public GraphAdaptorExtender<

1336

      SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > {

1337

  public:

1338

    /// The type of the adapted graph.

1339

    typedef _Graph Graph;

1340

    /// The type of the node filter map.

1341

    typedef _NodeFilterMap NodeFilterMap;

1342

    /// The type of the edge filter map.

1343

    typedef _EdgeFilterMap EdgeFilterMap;

1344

1345

    typedef GraphAdaptorExtender<

1346

      SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > Parent;

1347

1348

    typedef typename Parent::Node Node;

1349

    typedef typename Parent::Edge Edge;

1350

1351

  protected:

1352

    SubGraph() { }

1353

  public:

1354

1355

    /// \brief Constructor

1356

///

1357

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

1358

    /// and edge filter maps.

1359

    SubGraph(Graph& graph, NodeFilterMap& node_filter_map,

1360

             EdgeFilterMap& edge_filter_map) {

1361

      setGraph(graph);

1362

      setNodeFilterMap(node_filter_map);

1363

      setEdgeFilterMap(edge_filter_map);

1364

1365

1366

    /// \brief Hides the given node

1366

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

1367

///

1368

    /// This function hides the given node in the subgraph,

1369

    /// i.e. the iteration jumps over it.

1368

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

1370

1369

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

1371

    /// to be \c false in the node filter map.

1372

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

1373

1374

    /// \brief Hides the given edge

1370

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

1371

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

1372

1373

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

1375

1374

///

1376

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

1377

    /// i.e. the iteration jumps over it.

1375

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

1378

1376

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

1379

    /// to be \c false in the edge filter map.

1380

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

1381

1382

    /// \brief Shows the given node

1377

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

1378

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

1379

1380

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

1383

1381

///

1384

    /// This function shows the given node in the subgraph.

1385

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

1386

    /// to be \c true in the node filter map.

1387

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

1388

1389

    /// \brief Shows the given edge

1382

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

1383

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

1384

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

1385

1386

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

1390

1387

///

1391

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

1392

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

1393

    /// to be \c true in the edge filter map.

1394

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

1395

1396

    /// \brief Returns \c true if the given node is hidden.

1388

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

1389

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

1390

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

1391

1392

    /// \brief Disables the given node

1397

1393

///

1398

    /// This function returns \c true if the given node is hidden.

1399

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

1400

1401

    /// \brief Returns \c true if the given edge is hidden.

1394

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

1395

    /// so the iteration jumps over it.

1396

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

1397

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

1398

1399

    /// \brief Disables the given edge

1402

1400

///

1403

    /// This function returns \c true if the given edge is hidden.

1404

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

1401

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

1402

    /// so the iteration jumps over it.

1403

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

1404

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

1405

1406

    /// \brief Enables the given node

1407

///

1408

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

1409

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

1410

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

1411

1412

    /// \brief Enables the given edge

1413

///

1414

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

1415

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

1416

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

1417

1405

1418

};

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

1408

1421

///

1409

1422

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

1410

1423

  /// \ingroup graph_adaptors

1411

1424

  /// \relates SubGraph

1412

1425

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

1413

1426

  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>

1414

1427

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

1415

1428

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

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

1419

1432

  SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>

1420

1433

  subGraph(const Graph& graph,

1421

1434

           const NodeFilterMap& nfm, ArcFilterMap& efm) {

1422

1435

    return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>

1423

1436

      (graph, nfm, efm);

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

1427

1440

  SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>

1428

1441

  subGraph(const Graph& graph,

1429

1442

           NodeFilterMap& nfm, const ArcFilterMap& efm) {

1430

1443

    return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>

1431

1444

      (graph, nfm, efm);

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

1435

1448

  SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>

1436

1449

  subGraph(const Graph& graph,

1437

1450

           const NodeFilterMap& nfm, const ArcFilterMap& efm) {

1438

1451

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

1439

1452

      (graph, nfm, efm);

  /// \ingroup graph_adaptors

1444

1457

///

1445

1458

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

1446

1459

///

1447

1460

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

1448

1461

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

1449

1462

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

1450

1463

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

1451

1464

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

1452

1465

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

1453

1466

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

1454

1467

///

1455

1468

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

1456

1469

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

1457

1470

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

1458

1471

///

1459

1472

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

1460

1473

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

1461

1474

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

1462

1475

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

1463

1476

  /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the

1464

1477

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

1465

1478

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

1466

1479

  /// \tparam _checked If this parameter is set to \c false then the arc/edge

1467

1480

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

1468

1481

  /// case only isolated nodes can be filtered out from the graph.

1469

1482

  /// Otherwise, each arc/edge that is incident to a hidden node is

1470

1483

  /// automatically filtered out. This is the default option.

1471

1484

///

1472

1485

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

1473

1486

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

1474

1487

#ifdef DOXYGEN

1475

1488

  template<typename _Graph,

1476

1489

           typename _NodeFilterMap,

1477

1490

           bool _checked>

1478

1491

#else

1479

1492

  template<typename _Digraph,

1480

1493

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

1481

1494

           bool _checked = true,

1482

1495

           typename Enable = void>

1483

1496

#endif

1484

1497

  class FilterNodes

1485

1498

    : public SubDigraph<_Digraph, _NodeFilterMap,

1486

1499

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

1487

1500

  public:

    typedef _Digraph Digraph;

1490

1503

    typedef _NodeFilterMap NodeFilterMap;

    typedef SubDigraph<Digraph, NodeFilterMap,

1493

1506

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

1494

1507

    Parent;

    typedef typename Parent::Node Node;

  protected:

1499

1512

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

    FilterNodes() : const_true_map(true) {

1502

1515

      Parent::setArcFilterMap(const_true_map);

  public:

    /// \brief Constructor

1508

1521

///

1509

1522

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

1510

1523

    /// given node filter map.

1511

1524

#ifdef DOXYGEN

1512

1525

    FilterNodes(_Graph& graph, _NodeFilterMap& node_filter) :

1513

1526

#else

1514

1527

    FilterNodes(Digraph& graph, NodeFilterMap& node_filter) :

1515

1528

#endif

1516

1529

      Parent(), const_true_map(true) {

1517

1530

      Parent::setDigraph(graph);

1518

1531

      Parent::setNodeFilterMap(node_filter);

1519

1532

      Parent::setArcFilterMap(const_true_map);

    /// \brief Hides the given node

1535

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

1523

1536

///

1524

    /// This function hides the given node in the subgraph,

1525

    /// i.e. the iteration jumps over it.

1537

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

1526

1538

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

1527

    /// to be \c false in the node filter map.

1528

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

1529

1530

    /// \brief Shows the given node

1539

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

1540

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

1541

1542

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

1531

1543

///

1532

    /// This function shows the given node in the subgraph.

1533

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

1534

    /// to be \c true in the node filter map.

1535

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

1536

1537

    /// \brief Returns \c true if the given node is hidden.

1544

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

1545

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

1546

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

1547

1548

    /// \brief Disables the given node

1538

1549

///

1539

    /// This function returns \c true if the given node is hidden.

1540

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

1550

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

1551

    /// jumps over it.

1552

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

1553

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

1554

1555

    /// \brief Enables the given node

1556

///

1557

    /// This function enables the given node.

1558

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

1559

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

};

  template<typename _Graph, typename _NodeFilterMap, bool _checked>

1545

1564

  class FilterNodes<_Graph, _NodeFilterMap, _checked,

1546

1565

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

1547

1566

    : public SubGraph<_Graph, _NodeFilterMap,

1548

1567

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

1549

1568

  public:

1550

1569

    typedef _Graph Graph;

1551

1570

    typedef _NodeFilterMap NodeFilterMap;

1552

1571

    typedef SubGraph<Graph, NodeFilterMap,

1553

1572

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

    typedef typename Parent::Node Node;

1556

1575

  protected:

1557

1576

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

    FilterNodes() : const_true_map(true) {

1560

1579

      Parent::setEdgeFilterMap(const_true_map);

  public:

    FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :

1566

1585

      Parent(), const_true_map(true) {

1567

1586

      Parent::setGraph(_graph);

1568

1587

      Parent::setNodeFilterMap(node_filter_map);

1569

1588

      Parent::setEdgeFilterMap(const_true_map);

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

1573

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

1574

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

1591

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

1592

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

1593

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

1594

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

};

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

1580

1600

///

1581

1601

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

1582

1602

  /// \ingroup graph_adaptors

1583

1603

  /// \relates FilterNodes

1584

1604

  template<typename Digraph, typename NodeFilterMap>

1585

1605

  FilterNodes<const Digraph, NodeFilterMap>

1586

1606

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

1587

1607

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

  template<typename Digraph, typename NodeFilterMap>

1591

1611

  FilterNodes<const Digraph, const NodeFilterMap>

1592

1612

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

1593

1613

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

  /// \ingroup graph_adaptors

1597

1617

///

1598

1618

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

1599

1619

///

1600

1620

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

1601

1621

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

1602

1622

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

1603

1623

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

1604

1624

  /// "Digraph" concept.

1605

1625

///

1606

1626

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

1607

1627

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

1608

1628

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

1609

1629

///

1610

1630

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

1611

1631

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

1612

1632

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

1613

1633

  /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the

1614

1634

  /// adapted digraph. The default map type is

1615

1635

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

1616

1636

///

1617

1637

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

1618

1638

  /// digraph are convertible to each other.

1619

1639

#ifdef DOXYGEN

1620

1640

  template<typename _Digraph,

1621

1641

           typename _ArcFilterMap>

1622

1642

#else

1623

1643

  template<typename _Digraph,

1624

1644

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

1625

1645

#endif

1626

1646

  class FilterArcs :

1627

1647

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

1628

1648

                      _ArcFilterMap, false> {

1629

1649

  public:

    typedef _Digraph Digraph;

1632

1652

    typedef _ArcFilterMap ArcFilterMap;

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

1635

1655

                       ArcFilterMap, false> Parent;

    typedef typename Parent::Arc Arc;

  protected:

1640

1660

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

    FilterArcs() : const_true_map(true) {

1643

1663

      Parent::setNodeFilterMap(const_true_map);

  public:

    /// \brief Constructor

1649

1669

///

1650

1670

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

1651

1671

    /// filter map.

1652

1672

    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)

1653

1673

      : Parent(), const_true_map(true) {

1654

1674

      Parent::setDigraph(digraph);

1655

1675

      Parent::setNodeFilterMap(const_true_map);

1656

1676

      Parent::setArcFilterMap(arc_filter);

    /// \brief Hides the given arc

1679

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

1660

1680

///

1661

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

1662

    /// i.e. the iteration jumps over it.

1681

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

1663

1682

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

1664

    /// to be \c false in the arc filter map.

1665

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

1666

1667

    /// \brief Shows the given arc

1683

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

1684

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

1685

1686

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

1668

1687

///

1669

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

1670

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

1671

    /// to be \c true in the arc filter map.

1672

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

1673

1674

    /// \brief Returns \c true if the given arc is hidden.

1688

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

1689

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

1690

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

1691

1692

    /// \brief Disables the given arc

1675

1693

///

1676

    /// This function returns \c true if the given arc is hidden.

1677

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

1694

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

1695

    /// so the iteration jumps over it.

1696

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

1697

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

1698

1699

    /// \brief Enables the given arc

1700

///

1701

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

1702

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

1703

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

};

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

1682

1708

///

1683

1709

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

1684

1710

  /// \ingroup graph_adaptors

1685

1711

  /// \relates FilterArcs

1686

1712

  template<typename Digraph, typename ArcFilterMap>

1687

1713

  FilterArcs<const Digraph, ArcFilterMap>

1688

1714

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

1689

1715

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

  template<typename Digraph, typename ArcFilterMap>

1693

1719

  FilterArcs<const Digraph, const ArcFilterMap>

1694

1720

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

1695

1721

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

  /// \ingroup graph_adaptors

1699

1725

///

1700

1726

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

1701

1727

///

1702

1728

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

1703

1729

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

1704

1730

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

1705

1731

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

1706

1732

  /// "Graph" concept.

1707

1733

///

1708

1734

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

1709

1735

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

1710

1736

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

1711

1737

///

1712

1738

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

1713

1739

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

1714

1740

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

1715

1741

  /// \tparam _EdgeFilterMap A \c bool (or convertible) edge map of the

1716

1742

  /// adapted graph. The default map type is

1717

1743

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

1718

1744

///

1719

1745

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

1720

1746

  /// adapted graph are convertible to each other.

1721

1747

#ifdef DOXYGEN

1722

1748

  template<typename _Graph,

1723

1749

           typename _EdgeFilterMap>

1724

1750

#else

1725

1751

  template<typename _Graph,

1726

1752

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

1727

1753

#endif

1728

1754

  class FilterEdges :

1729

1755

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

1730

1756

                    _EdgeFilterMap, false> {

1731

1757

  public:

1732

1758

    typedef _Graph Graph;

1733

1759

    typedef _EdgeFilterMap EdgeFilterMap;

1734

1760

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

1735

1761

                     EdgeFilterMap, false> Parent;

1736

1762

    typedef typename Parent::Edge Edge;

1737

1763

  protected:

1738

1764

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

    FilterEdges() : const_true_map(true) {

1741

1767

      Parent::setNodeFilterMap(const_true_map);

  public:

    /// \brief Constructor

1747

1773

///

1748

1774

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

1749

1775

    /// filter map.

1750

1776

    FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :

1751

1777

      Parent(), const_true_map(true) {

1752

1778

      Parent::setGraph(graph);

1753

1779

      Parent::setNodeFilterMap(const_true_map);

1754

1780

      Parent::setEdgeFilterMap(edge_filter_map);

    /// \brief Hides the given edge

1783

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

1758

1784

///

1759

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

1760

    /// i.e. the iteration jumps over it.

1785

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

1761

1786

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

1762

    /// to be \c false in the edge filter map.

1763

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

1764

1765

    /// \brief Shows the given edge

1787

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

1788

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

1789

1790

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

1766

1791

///

1767

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

1768

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

1769

    /// to be \c true in the edge filter map.

1770

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

1771

1772

    /// \brief Returns \c true if the given edge is hidden.

1792

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

1793

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

1794

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

1795

1796

    /// \brief Disables the given edge

1773

1797

///

1774

    /// This function returns \c true if the given edge is hidden.

1775

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

1798

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

1799

    /// so the iteration jumps over it.

1800

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

1801

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

1802

1803

    /// \brief Enables the given edge

1804

///

1805

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

1806

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

1807

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

};

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

1780

1812

///

1781

1813

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

1782

1814

  /// \ingroup graph_adaptors

1783

1815

  /// \relates FilterEdges

1784

1816

  template<typename Graph, typename EdgeFilterMap>

1785

1817

  FilterEdges<const Graph, EdgeFilterMap>

1786

1818

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

1787

1819

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

  template<typename Graph, typename EdgeFilterMap>

1791

1823

  FilterEdges<const Graph, const EdgeFilterMap>

1792

1824

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

1793

1825

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

  template <typename _Digraph>

1798

1830

  class UndirectorBase {

1799

1831

  public:

1800

1832

    typedef _Digraph Digraph;

1801

1833

    typedef UndirectorBase Adaptor;

    typedef True UndirectedTag;

    typedef typename Digraph::Arc Edge;

1806

1838

    typedef typename Digraph::Node Node;

    class Arc : public Edge {

1809

1841

      friend class UndirectorBase;

1810

1842

    protected:

1811

1843

      bool _forward;

      Arc(const Edge& edge, bool forward) :

1814

1846

        Edge(edge), _forward(forward) {}

    public:

1817

1849

      Arc() {}

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

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

1822

1854

        return _forward == other._forward &&

1823

1855

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

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

1826

1858

        return _forward != other._forward ||

1827

1859

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

      bool operator<(const Arc &other) const {

1830

1862

        return _forward < other._forward ||

1831

1863

          (_forward == other._forward &&

1832

1864

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

};

    void first(Node& n) const {

1837

1869

      _digraph->first(n);

    void next(Node& n) const {

1841

1873

      _digraph->next(n);

    void first(Arc& a) const {

1845

1877

      _digraph->first(a);

1846

1878

      a._forward = true;

    void next(Arc& a) const {

1850

1882

      if (a._forward) {

1851

1883

        a._forward = false;

1852

1884

      } else {

1853

1885

        _digraph->next(a);

1854

1886

        a._forward = true;

    void first(Edge& e) const {

1859

1891

      _digraph->first(e);

    void next(Edge& e) const {

1863

1895

      _digraph->next(e);

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

1867

1899

      _digraph->firstIn(a, n);

1868

1900

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

1869

1901

        a._forward = false;

1870

1902

      } else {

1871

1903

        _digraph->firstOut(a, n);

1872

1904

        a._forward = true;

    void nextOut(Arc &a) const {

1876

1908

      if (!a._forward) {

1877

1909

        Node n = _digraph->target(a);

1878

1910

        _digraph->nextIn(a);

1879

1911

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

1880

1912

          _digraph->firstOut(a, n);

1881

1913

          a._forward = true;

      else {

1885

1917

        _digraph->nextOut(a);

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

1890

1922

      _digraph->firstOut(a, n);

1891

1923

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

1892

1924

        a._forward = false;

1893

1925

      } else {

1894

1926

        _digraph->firstIn(a, n);

1895

1927

        a._forward = true;

    void nextIn(Arc &a) const {

1899

1931

      if (!a._forward) {

1900

1932

        Node n = _digraph->source(a);

1901

1933

        _digraph->nextOut(a);

1902

1934

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

1903

1935

          _digraph->firstIn(a, n);

1904

1936

          a._forward = true;

      else {

1908

1940

        _digraph->nextIn(a);

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

1913

1945

      d = true;

1914

1946

      _digraph->firstOut(e, n);

1915

1947

      if (e != INVALID) return;

1916

1948

      d = false;

1917

1949

      _digraph->firstIn(e, n);

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

1921

1953

      if (d) {

1922

1954

        Node s = _digraph->source(e);

1923

1955

        _digraph->nextOut(e);

1924

1956

        if (e != INVALID) return;

1925

1957

        d = false;

1926

1958

        _digraph->firstIn(e, s);

1927

1959

      } else {

1928

1960

        _digraph->nextIn(e);

    Node u(const Edge& e) const {

1933

1965

      return _digraph->source(e);

    Node v(const Edge& e) const {

1937

1969

      return _digraph->target(e);

    Node source(const Arc &a) const {

1941

1973

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

    Node target(const Arc &a) const {

1945

1977

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

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

1949

1981

      return Arc(e, d);

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

1952

1984

      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); }

1958

1990

    Arc arcFromId(int ix) const {

1959

1991

      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); }

1964

1996

    int id(const Arc &a) const {

1965

1997

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

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

...

@@ -2578,387 +2610,387 @@

2578

2610

    template<typename _Digraph,

2579

2611

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

2580

2612

             typename _FlowMap = _CapacityMap,

2581

2613

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

2582

2614

    class ResForwardFilter {

2583

2615

    public:

      typedef _Digraph Digraph;

2586

2618

      typedef _CapacityMap CapacityMap;

2587

2619

      typedef _FlowMap FlowMap;

2588

2620

      typedef _Tolerance Tolerance;

      typedef typename Digraph::Arc Key;

2591

2623

      typedef bool Value;

    private:

      const CapacityMap* _capacity;

2596

2628

      const FlowMap* _flow;

2597

2629

      Tolerance _tolerance;

2598

2630

    public:

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

2601

2633

                       const Tolerance& tolerance = Tolerance())

2602

2634

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

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

2605

2637

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

};

    template<typename _Digraph,

2610

2642

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

2611

2643

             typename _FlowMap = _CapacityMap,

2612

2644

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

2613

2645

    class ResBackwardFilter {

2614

2646

    public:

      typedef _Digraph Digraph;

2617

2649

      typedef _CapacityMap CapacityMap;

2618

2650

      typedef _FlowMap FlowMap;

2619

2651

      typedef _Tolerance Tolerance;

      typedef typename Digraph::Arc Key;

2622

2654

      typedef bool Value;

    private:

      const CapacityMap* _capacity;

2627

2659

      const FlowMap* _flow;

2628

2660

      Tolerance _tolerance;

    public:

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

2633

2665

                        const Tolerance& tolerance = Tolerance())

2634

2666

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

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

2637

2669

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

};

  /// \ingroup graph_adaptors

2644

2676

///

2645

2677

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

2646

2678

  /// flow and circulation problems.

2647

2679

///

2648

2680

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

2649

2681

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

2650

2682

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

2651

2683

  /// functions on the arcs.

2652

2684

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

2653

2685

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

2654

2686

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

2655

2687

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

2656

2688

  /// called residual digraph.

2657

2689

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

2658

2690

  /// multiplicities are counted, i.e. the adaptor has exactly

2659

2691

  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel

2660

2692

  /// arcs).

2661

2693

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

2662

2694

///

2663

2695

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

2664

2696

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

2665

2697

  /// It is implicitly \c const.

2666

2698

  /// \tparam _CapacityMap An arc map of some numerical type, which defines

2667

2699

  /// the capacities in the flow problem. It is implicitly \c const.

2668

2700

  /// The default map type is

2669

2701

  /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".

2670

2702

  /// \tparam _FlowMap An arc map of some numerical type, which defines

2671

2703

  /// the flow values in the flow problem.

2672

2704

  /// The default map type is \c _CapacityMap.

2673

2705

  /// \tparam _Tolerance Tolerance type for handling inexact computation.

2674

2706

  /// The default tolerance type depends on the value type of the

2675

2707

  /// capacity map.

2676

2708

///

2677

2709

  /// \note This adaptor is implemented using Undirector and FilterArcs

2678

2710

  /// adaptors.

2679

2711

///

2680

2712

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

2681

2713

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

2682

2714

  /// is convertible to the \c Arc type of the adapted digraph.

2683

2715

#ifdef DOXYGEN

2684

2716

  template<typename _Digraph,

2685

2717

           typename _CapacityMap,

2686

2718

           typename _FlowMap,

2687

2719

           typename _Tolerance>

2688

2720

  class Residual

2689

2721

#else

2690

2722

  template<typename _Digraph,

2691

2723

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

2692

2724

           typename _FlowMap = _CapacityMap,

2693

2725

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

2694

2726

  class Residual :

2695

2727

    public FilterArcs<

2696

2728

    Undirector<const _Digraph>,

2697

2729

    typename Undirector<const _Digraph>::template CombinedArcMap<

2698

2730

      _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,

2699

2731

                                      _FlowMap, _Tolerance>,

2700

2732

      _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,

2701

2733

                                       _FlowMap, _Tolerance> > >

2702

2734

#endif

  public:

    /// The type of the underlying digraph.

2707

2739

    typedef _Digraph Digraph;

2708

2740

    /// The type of the capacity map.

2709

2741

    typedef _CapacityMap CapacityMap;

2710

2742

    /// The type of the flow map.

2711

2743

    typedef _FlowMap FlowMap;

2712

2744

    typedef _Tolerance Tolerance;

    typedef typename CapacityMap::Value Value;

2715

2747

    typedef Residual Adaptor;

  protected:

    typedef Undirector<const Digraph> Undirected;

    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,

2722

2754

                                            FlowMap, Tolerance> ForwardFilter;

    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,

2725

2757

                                             FlowMap, Tolerance> BackwardFilter;

    typedef typename Undirected::

2728

2760

    template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;

    typedef FilterArcs<Undirected, ArcFilter> Parent;

    const CapacityMap* _capacity;

2733

2765

    FlowMap* _flow;

    Undirected _graph;

2736

2768

    ForwardFilter _forward_filter;

2737

2769

    BackwardFilter _backward_filter;

2738

2770

    ArcFilter _arc_filter;

  public:

    /// \brief Constructor

2743

2775

///

2744

2776

    /// Constructor of the residual digraph adaptor. The parameters are the

2745

2777

    /// digraph, the capacity map, the flow map, and a tolerance object.

2746

2778

    Residual(const Digraph& digraph, const CapacityMap& capacity,

2747

2779

             FlowMap& flow, const Tolerance& tolerance = Tolerance())

2748

2780

      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),

2749

2781

        _forward_filter(capacity, flow, tolerance),

2750

2782

        _backward_filter(capacity, flow, tolerance),

2751

2783

        _arc_filter(_forward_filter, _backward_filter)

      Parent::setDigraph(_graph);

2754

2786

      Parent::setArcFilterMap(_arc_filter);

    typedef typename Parent::Arc Arc;

    /// \brief Returns the residual capacity of the given arc.

2760

2792

///

2761

2793

    /// Returns the residual capacity of the given arc.

2762

2794

    Value residualCapacity(const Arc& a) const {

2763

2795

      if (Undirected::direction(a)) {

2764

2796

        return (*_capacity)[a] - (*_flow)[a];

2765

2797

      } else {

2766

2798

        return (*_flow)[a];

    /// \brief Augment on the given arc in the residual digraph.

2802

    /// \brief Augments on the given arc in the residual digraph.

2771

2803

///

2772

    /// Augment on the given arc in the residual digraph. It increases

2804

    /// Augments on the given arc in the residual digraph. It increases

2773

2805

    /// or decreases the flow value on the original arc according to the

2774

2806

    /// direction of the residual arc.

2775

2807

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

2776

2808

      if (Undirected::direction(a)) {

2777

2809

        _flow->set(a, (*_flow)[a] + v);

2778

2810

      } else {

2779

2811

        _flow->set(a, (*_flow)[a] - v);

    /// \brief Returns \c true if the given residual arc is a forward arc.

2784

2816

///

2785

2817

    /// Returns \c true if the given residual arc has the same orientation

2786

2818

    /// as the original arc, i.e. it is a so called forward arc.

2787

2819

    static bool forward(const Arc& a) {

2788

2820

      return Undirected::direction(a);

    /// \brief Returns \c true if the given residual arc is a backward arc.

2792

2824

///

2793

2825

    /// Returns \c true if the given residual arc has the opposite orientation

2794

2826

    /// than the original arc, i.e. it is a so called backward arc.

2795

2827

    static bool backward(const Arc& a) {

2796

2828

      return !Undirected::direction(a);

    /// \brief Returns the forward oriented residual arc.

2800

2832

///

2801

2833

    /// Returns the forward oriented residual arc related to the given

2802

2834

    /// arc of the underlying digraph.

2803

2835

    static Arc forward(const typename Digraph::Arc& a) {

2804

2836

      return Undirected::direct(a, true);

    /// \brief Returns the backward oriented residual arc.

2808

2840

///

2809

2841

    /// Returns the backward oriented residual arc related to the given

2810

2842

    /// arc of the underlying digraph.

2811

2843

    static Arc backward(const typename Digraph::Arc& a) {

2812

2844

      return Undirected::direct(a, false);

    /// \brief Residual capacity map.

2816

2848

///

2817

2849

    /// This map adaptor class can be used for obtaining the residual

2818

2850

    /// capacities as an arc map of the residual digraph.

2819

2851

    /// Its value type is inherited from the capacity map.

2820

2852

    class ResidualCapacity {

2821

2853

    protected:

2822

2854

      const Adaptor* _adaptor;

2823

2855

    public:

2824

2856

      /// The key type of the map

2825

2857

      typedef Arc Key;

2826

2858

      /// The value type of the map

2827

2859

      typedef typename _CapacityMap::Value Value;

      /// Constructor

2830

2862

      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}

      /// Returns the value associated with the given residual arc

2833

2865

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

2834

2866

        return _adaptor->residualCapacity(a);

};

    /// \brief Returns a residual capacity map

2840

2872

///

2841

2873

    /// This function just returns a residual capacity map.

2842

2874

    ResidualCapacity residualCapacity() const {

2843

2875

      return ResidualCapacity(*this);

};

  /// \brief Returns a (read-only) Residual adaptor

2849

2881

///

2850

2882

  /// This function just returns a (read-only) \ref Residual adaptor.

2851

2883

  /// \ingroup graph_adaptors

2852

2884

  /// \relates Residual

2853

2885

  template<typename Digraph, typename CapacityMap, typename FlowMap>

2854

2886

  Residual<Digraph, CapacityMap, FlowMap>

2855

2887

  residual(const Digraph& digraph,

2856

2888

           const CapacityMap& capacity,

2857

2889

           FlowMap& flow)

    return Residual<Digraph, CapacityMap, FlowMap> (digraph, capacity, flow);

  template <typename _Digraph>

2864

2896

  class SplitNodesBase {

2865

2897

  public:

    typedef _Digraph Digraph;

2868

2900

    typedef DigraphAdaptorBase<const _Digraph> Parent;

2869

2901

    typedef SplitNodesBase Adaptor;

    typedef typename Digraph::Node DigraphNode;

2872

2904

    typedef typename Digraph::Arc DigraphArc;

    class Node;

2875

2907

    class Arc;

  private:

    template <typename T> class NodeMapBase;

2880

2912

    template <typename T> class ArcMapBase;

  public:

    class Node : public DigraphNode {

2885

2917

      friend class SplitNodesBase;

2886

2918

      template <typename T> friend class NodeMapBase;

2887

2919

    private:

      bool _in;

2890

2922

      Node(DigraphNode node, bool in)

2891

2923

        : DigraphNode(node), _in(in) {}

    public:

      Node() {}

2896

2928

      Node(Invalid) : DigraphNode(INVALID), _in(true) {}

      bool operator==(const Node& node) const {

2899

2931

        return DigraphNode::operator==(node) && _in == node._in;

      bool operator!=(const Node& node) const {

2903

2935

        return !(*this == node);

      bool operator<(const Node& node) const {

2907

2939

        return DigraphNode::operator<(node) ||

2908

2940

          (DigraphNode::operator==(node) && _in < node._in);

};

    class Arc {

2913

2945

      friend class SplitNodesBase;

2914

2946

      template <typename T> friend class ArcMapBase;

2915

2947

    private:

2916

2948

      typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;

      explicit Arc(const DigraphArc& arc) : _item(arc) {}

2919

2951

      explicit Arc(const DigraphNode& node) : _item(node) {}

      ArcImpl _item;

    public:

2924

2956

      Arc() {}

2925

2957

      Arc(Invalid) : _item(DigraphArc(INVALID)) {}

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

2928

2960

        if (_item.firstState()) {

2929

2961

          if (arc._item.firstState()) {

2930

2962

            return _item.first() == arc._item.first();

        } else {

2933

2965

          if (arc._item.secondState()) {

2934

2966

            return _item.second() == arc._item.second();

        return false;

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

2941

2973

        return !(*this == arc);

      bool operator<(const Arc& arc) const {

2945

2977

        if (_item.firstState()) {

2946

2978

          if (arc._item.firstState()) {

2947

2979

            return _item.first() < arc._item.first();

          return false;

2950

2982

        } else {

2951

2983

          if (arc._item.secondState()) {

2952

2984

            return _item.second() < arc._item.second();

          return true;

      operator DigraphArc() const { return _item.first(); }

2959

2991

      operator DigraphNode() const { return _item.second(); }

};

    void first(Node& n) const {

2964

2996

      _digraph->first(n);

RhodeCode

Login to your account