LEMON/LEMON-official Changeset - r474:fbd6e04acf44

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

12

13

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

14

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

15

 * purpose.

16

17

*/

18

19

#ifndef LEMON_ADAPTORS_H

20

#define LEMON_ADAPTORS_H

21

22

/// \ingroup graph_adaptors

23

/// \file

24

/// \brief Several graph adaptors

24

/// \brief Adaptor classes for digraphs and graphs

25

///

26

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

27

28

#include <lemon/core.h>

29

#include <lemon/maps.h>

30

#include <lemon/bits/variant.h>

31

32

#include <lemon/bits/graph_adaptor_extender.h>

33

#include <lemon/tolerance.h>

34

35

#include <algorithm>

36

...

@@ -337,59 +337,70 @@

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 A digraph adaptor which reverses the orientation of the arcs.

349

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

350

  /// a digraph.

350

351

///

351

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

352

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

353

  /// "Digraph concept".

352

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

353

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

354

///

355

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

356

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

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.

357

365

  template<typename _Digraph>

358

366

  class ReverseDigraph :

359

367

    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {

360

368

  public:

361

369

    typedef _Digraph Digraph;

362

370

    typedef DigraphAdaptorExtender<

363

371

      ReverseDigraphBase<_Digraph> > Parent;

364

372

  protected:

365

373

    ReverseDigraph() { }

366

374

  public:

    /// \brief Constructor

369

377

///

370

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

378

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

371

379

    explicit ReverseDigraph(Digraph& digraph) {

372

380

      Parent::setDigraph(digraph);

};

375

383

376

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

384

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

377

385

///

378

  /// Just gives back a reverse digraph adaptor

386

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

387

  /// \ingroup graph_adaptors

388

  /// \relates ReverseDigraph

379

389

  template<typename Digraph>

380

390

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

381

391

    return ReverseDigraph<const Digraph>(digraph);

  template <typename _Digraph, typename _NodeFilterMap,

385

396

            typename _ArcFilterMap, bool _checked = true>

386

397

  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {

387

398

  public:

388

399

    typedef _Digraph Digraph;

389

400

    typedef _NodeFilterMap NodeFilterMap;

390

401

    typedef _ArcFilterMap ArcFilterMap;

    typedef SubDigraphBase Adaptor;

393

404

    typedef DigraphAdaptorBase<_Digraph> Parent;

394

405

  protected:

395

406

    NodeFilterMap* _node_filter;

...

@@ -676,124 +687,149 @@

      template <typename CMap>

678

689

      ArcMap& operator=(const CMap& cmap) {

679

690

        MapParent::operator=(cmap);

680

691

        return *this;

};

};

  /// \ingroup graph_adaptors

687

698

///

688

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

699

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

689

700

///

690

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

691

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

692

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

693

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

694

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

695

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

701

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

702

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

703

  /// define the filters for nodes and arcs.

704

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

705

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

706

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

707

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

696

708

  /// filtered out.

697

709

///

698

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

699

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

700

  /// to const.

701

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

702

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

703

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

704

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

705

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

710

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

711

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

712

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

713

///

714

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

715

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

716

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

717

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

718

  /// adapted digraph. The default map type is

719

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

720

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

721

  /// adapted digraph. The default map type is

722

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

723

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

724

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

725

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

726

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

727

///

728

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

729

  /// digraph are convertible to each other.

706

730

///

707

731

  /// \see FilterNodes

708

732

  /// \see FilterArcs

733

#ifdef DOXYGEN

734

  template<typename _Digraph,

735

           typename _NodeFilterMap,

736

           typename _ArcFilterMap,

737

           bool _checked>

738

#else

709

739

  template<typename _Digraph,

710

740

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

711

741

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

712

742

           bool _checked = true>

743

#endif

713

744

  class SubDigraph

714

745

    : public DigraphAdaptorExtender<

715

746

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

716

747

  public:

748

    /// The type of the adapted digraph.

717

749

    typedef _Digraph Digraph;

750

    /// The type of the node filter map.

718

751

    typedef _NodeFilterMap NodeFilterMap;

752

    /// The type of the arc filter map.

719

753

    typedef _ArcFilterMap ArcFilterMap;

    typedef DigraphAdaptorExtender<

722

      SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >

756

      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> >

723

757

    Parent;

    typedef typename Parent::Node Node;

726

760

    typedef typename Parent::Arc Arc;

  protected:

729

763

    SubDigraph() { }

730

764

  public:

    /// \brief Constructor

733

767

///

734

    /// Creates a subdigraph for the given digraph with

735

    /// given node and arc map filters.

768

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

769

    /// given node and arc filter maps.

736

770

    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,

737

771

               ArcFilterMap& arc_filter) {

738

772

      setDigraph(digraph);

739

773

      setNodeFilterMap(node_filter);

740

774

      setArcFilterMap(arc_filter);

    /// \brief Hides the node of the graph

777

    /// \brief Hides the given node

744

778

///

745

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

746

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

747

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

779

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

780

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

781

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

782

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

748

783

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

749

784

750

    /// \brief Hides the arc of the graph

785

    /// \brief Hides the given arc

751

786

///

752

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

753

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

754

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

787

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

788

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

789

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

790

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

755

791

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

756

792

757

    /// \brief Unhides the node of the graph

793

    /// \brief Shows the given node

758

794

///

759

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

760

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

761

    /// again

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.

762

798

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

763

799

764

    /// \brief Unhides the arc of the graph

800

    /// \brief Shows the given arc

765

801

///

766

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

767

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

768

    /// again

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.

769

805

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

770

806

771

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

807

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

772

808

///

773

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

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.

774

813

///

775

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

776

777

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

778

///

779

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

780

///

814

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

781

815

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

};

784

818

785

  /// \brief Just gives back a subdigraph

819

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

786

820

///

787

  /// Just gives back a subdigraph

821

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

822

  /// \ingroup graph_adaptors

823

  /// \relates SubDigraph

788

824

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

789

825

  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>

790

826

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

791

827

    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>

792

828

      (digraph, nfm, afm);

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

796

832

  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>

797

833

  subDigraph(const Digraph& digraph,

798

834

             const NodeFilterMap& nfm, ArcFilterMap& afm) {

799

835

    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>

...

@@ -1240,118 +1276,148 @@

      template <typename CMap>

1242

1278

      EdgeMap& operator=(const CMap& cmap) {

1243

1279

        MapParent::operator=(cmap);

1244

1280

        return *this;

};

};

  /// \ingroup graph_adaptors

1251

1287

///

1252

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

1253

  /// undirected graph.

1288

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

1289

  /// graph.

1254

1290

///

1255

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

1256

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

1257

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

1258

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

1259

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

1260

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

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

1261

1298

  /// filtered out.

1262

1299

///

1263

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

1264

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

1265

  /// to const.

1266

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

1267

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

1268

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

1269

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

1270

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

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.

1271

1320

///

1272

1321

  /// \see FilterNodes

1273

1322

  /// \see FilterEdges

1274

  template<typename _Graph, typename NodeFilterMap,

1275

           typename EdgeFilterMap, bool _checked = true>

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

1276

1334

  class SubGraph

1277

1335

    : public GraphAdaptorExtender<

1278

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

1336

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

1279

1337

  public:

1338

    /// The type of the adapted graph.

1280

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

1281

1345

    typedef GraphAdaptorExtender<

1282

      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;

1346

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

    typedef typename Parent::Node Node;

1285

1349

    typedef typename Parent::Edge Edge;

  protected:

1288

1352

    SubGraph() { }

1289

1353

  public:

    /// \brief Constructor

1292

1356

///

1293

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

1294

    /// edge map filters.

1295

    SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,

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,

1296

1360

             EdgeFilterMap& edge_filter_map) {

1297

      setGraph(_graph);

1361

      setGraph(graph);

1298

1362

      setNodeFilterMap(node_filter_map);

1299

1363

      setEdgeFilterMap(edge_filter_map);

    /// \brief Hides the node of the graph

1366

    /// \brief Hides the given node

1303

1367

///

1304

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

1305

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

1306

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

1368

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

1369

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

1370

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

1371

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

1307

1372

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

1308

1373

1309

    /// \brief Hides the edge of the graph

1374

    /// \brief Hides the given edge

1310

1375

///

1311

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

1312

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

1313

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

1376

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

1377

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

1378

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

1379

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

1314

1380

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

1315

1381

1316

    /// \brief Unhides the node of the graph

1382

    /// \brief Shows the given node

1317

1383

///

1318

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

1319

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

1320

    /// again

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.

1321

1387

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

1322

1388

1323

    /// \brief Unhides the edge of the graph

1389

    /// \brief Shows the given edge

1324

1390

///

1325

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

1326

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

1327

    /// again

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.

1328

1394

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

1329

1395

1330

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

1396

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

1331

1397

///

1332

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

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.

1333

1402

///

1334

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

1335

1336

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

1337

///

1338

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

1339

///

1403

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

1340

1404

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

1341

1405

};

1342

1406

1343

  /// \brief Just gives back a subgraph

1407

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

1344

1408

///

1345

  /// Just gives back a subgraph

1409

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

1410

  /// \ingroup graph_adaptors

1411

  /// \relates SubGraph

1346

1412

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

1347

1413

  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>

1348

1414

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

1349

1415

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

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

1353

1419

  SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>

1354

1420

  subGraph(const Graph& graph,

1355

1421

           const NodeFilterMap& nfm, ArcFilterMap& efm) {

1356

1422

    return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>

1357

1423

      (graph, nfm, efm);

...

@@ -1364,50 +1430,60 @@

1364

1430

    return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>

1365

1431

      (graph, nfm, efm);

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

1369

1435

  SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>

1370

1436

  subGraph(const Graph& graph,

1371

1437

           const NodeFilterMap& nfm, const ArcFilterMap& efm) {

1372

1438

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

1373

1439

      (graph, nfm, efm);

  /// \ingroup graph_adaptors

1377

1444

///

1378

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

1445

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

1379

1446

///

1380

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

1381

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

1382

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

1383

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

1384

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

1385

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

1386

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

1387

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

1388

  /// are also filtered out.

1447

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

1448

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

1449

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

1450

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

1451

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

1452

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

1453

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

1389

1454

///

1390

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

1391

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

1392

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

1393

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

1394

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

1395

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

1396

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

1397

  /// graph.

1455

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

1456

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

1457

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

1458

///

1459

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

1460

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

1461

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

1462

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

1463

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

1464

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

1465

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

1466

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

1467

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

1468

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

1469

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

1470

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

1471

///

1472

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

1473

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

1398

1474

#ifdef DOXYGEN

1399

  template<typename _Digraph,

1400

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

1401

           bool _checked = true>

1475

  template<typename _Graph,

1476

           typename _NodeFilterMap,

1477

           bool _checked>

1402

1478

#else

1403

1479

  template<typename _Digraph,

1404

1480

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

1405

1481

           bool _checked = true,

1406

1482

           typename Enable = void>

1407

1483

#endif

1408

1484

  class FilterNodes

1409

1485

    : public SubDigraph<_Digraph, _NodeFilterMap,

1410

1486

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

1411

1487

  public:

    typedef _Digraph Digraph;

...

@@ -1421,51 +1497,55 @@

  protected:

1423

1499

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

    FilterNodes() : const_true_map(true) {

1426

1502

      Parent::setArcFilterMap(const_true_map);

  public:

    /// \brief Constructor

1432

1508

///

1433

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

1509

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

1434

1510

    /// given node filter map.

1435

    FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :

1511

#ifdef DOXYGEN

1512

    FilterNodes(_Graph& graph, _NodeFilterMap& node_filter) :

1513

#else

1514

    FilterNodes(Digraph& graph, NodeFilterMap& node_filter) :

1515

#endif

1436

1516

      Parent(), const_true_map(true) {

1437

      Parent::setDigraph(_digraph);

1517

      Parent::setDigraph(graph);

1438

1518

      Parent::setNodeFilterMap(node_filter);

1439

1519

      Parent::setArcFilterMap(const_true_map);

    /// \brief Hides the node of the graph

1522

    /// \brief Hides the given node

1443

1523

///

1444

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

1445

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

1446

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

1524

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

1525

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

1526

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

1527

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

1447

1528

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

1448

1529

1449

    /// \brief Unhides the node of the graph

1530

    /// \brief Shows the given node

1450

1531

///

1451

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

1452

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

1453

    /// again

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.

1454

1535

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

1455

1536

1456

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

1537

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

1457

1538

///

1458

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

1459

///

1539

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

1460

1540

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

};

  template<typename _Graph, typename _NodeFilterMap, bool _checked>

1465

1545

  class FilterNodes<_Graph, _NodeFilterMap, _checked,

1466

1546

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

1467

1547

    : public SubGraph<_Graph, _NodeFilterMap,

1468

1548

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

1469

1549

  public:

1470

1550

    typedef _Graph Graph;

1471

1551

    typedef _NodeFilterMap NodeFilterMap;

...

@@ -1487,202 +1567,242 @@

1487

1567

      Parent::setGraph(_graph);

1488

1568

      Parent::setNodeFilterMap(node_filter_map);

1489

1569

      Parent::setEdgeFilterMap(const_true_map);

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

1493

1573

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

1494

1574

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

};

  /// \brief Just gives back a FilterNodes adaptor

1579

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

1500

1580

///

1501

  /// Just gives back a FilterNodes adaptor

1581

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

1582

  /// \ingroup graph_adaptors

1583

  /// \relates FilterNodes

1502

1584

  template<typename Digraph, typename NodeFilterMap>

1503

1585

  FilterNodes<const Digraph, NodeFilterMap>

1504

1586

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

1505

1587

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

  template<typename Digraph, typename NodeFilterMap>

1509

1591

  FilterNodes<const Digraph, const NodeFilterMap>

1510

1592

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

1511

1593

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

  /// \ingroup graph_adaptors

1515

1597

///

1516

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

1598

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

1517

1599

///

1518

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

1519

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

1520

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

1521

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

1600

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

1601

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

1602

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

1603

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

1604

  /// "Digraph" concept.

1522

1605

///

1523

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

1524

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

1525

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

1526

  /// graph.

1527

  template<typename _Digraph, typename _ArcFilterMap>

1606

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

1607

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

1608

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

1609

///

1610

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

1611

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

1612

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

1613

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

1614

  /// adapted digraph. The default map type is

1615

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

1616

///

1617

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

1618

  /// digraph are convertible to each other.

1619

#ifdef DOXYGEN

1620

  template<typename _Digraph,

1621

           typename _ArcFilterMap>

1622

#else

1623

  template<typename _Digraph,

1624

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

1625

#endif

1528

1626

  class FilterArcs :

1529

1627

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

1530

1628

                      _ArcFilterMap, false> {

1531

1629

  public:

1630

1532

1631

    typedef _Digraph Digraph;

1533

1632

    typedef _ArcFilterMap ArcFilterMap;

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

1536

1635

                       ArcFilterMap, false> Parent;

    typedef typename Parent::Arc Arc;

  protected:

1541

1640

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

    FilterArcs() : const_true_map(true) {

1544

1643

      Parent::setNodeFilterMap(const_true_map);

  public:

    /// \brief Constructor

1550

1649

///

1551

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

1552

    /// given arc map filter.

1650

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

1651

    /// filter map.

1553

1652

    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)

1554

1653

      : Parent(), const_true_map(true) {

1555

1654

      Parent::setDigraph(digraph);

1556

1655

      Parent::setNodeFilterMap(const_true_map);

1557

1656

      Parent::setArcFilterMap(arc_filter);

    /// \brief Hides the arc of the graph

1659

    /// \brief Hides the given arc

1561

1660

///

1562

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

1563

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

1564

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

1661

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

1662

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

1663

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

1664

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

1565

1665

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

1566

1666

1567

    /// \brief Unhides the arc of the graph

1667

    /// \brief Shows the given arc

1568

1668

///

1569

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

1570

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

1571

    /// again

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.

1572

1672

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

1573

1673

1574

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

1674

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

1575

1675

///

1576

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

1577

///

1676

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

1578

1677

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

};

1581

1680

1582

  /// \brief Just gives back an FilterArcs adaptor

1681

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

1583

1682

///

1584

  /// Just gives back an FilterArcs adaptor

1683

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

1684

  /// \ingroup graph_adaptors

1685

  /// \relates FilterArcs

1585

1686

  template<typename Digraph, typename ArcFilterMap>

1586

1687

  FilterArcs<const Digraph, ArcFilterMap>

1587

1688

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

1588

1689

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

  template<typename Digraph, typename ArcFilterMap>

1592

1693

  FilterArcs<const Digraph, const ArcFilterMap>

1593

1694

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

1594

1695

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

  /// \ingroup graph_adaptors

1598

1699

///

1599

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

1700

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

1600

1701

///

1601

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

1602

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

1603

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

1604

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

1702

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

1703

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

1704

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

1705

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

1706

  /// "Graph" concept.

1605

1707

///

1606

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

1607

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

1608

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

1609

  /// graph.

1610

  template<typename _Graph, typename _EdgeFilterMap>

1708

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

1709

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

1710

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

1711

///

1712

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

1713

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

1714

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

1715

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

1716

  /// adapted graph. The default map type is

1717

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

1718

///

1719

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

1720

  /// adapted graph are convertible to each other.

1721

#ifdef DOXYGEN

1722

  template<typename _Graph,

1723

           typename _EdgeFilterMap>

1724

#else

1725

  template<typename _Graph,

1726

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

1727

#endif

1611

1728

  class FilterEdges :

1612

1729

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

1613

1730

                    _EdgeFilterMap, false> {

1614

1731

  public:

1615

1732

    typedef _Graph Graph;

1616

1733

    typedef _EdgeFilterMap EdgeFilterMap;

1617

1734

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

1618

1735

                     EdgeFilterMap, false> Parent;

1619

1736

    typedef typename Parent::Edge Edge;

1620

1737

  protected:

1621

1738

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

    FilterEdges() : const_true_map(true) {

1624

1741

      Parent::setNodeFilterMap(const_true_map);

  public:

    /// \brief Constructor

1630

1747

///

1631

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

1632

    /// given edge map filters.

1633

    FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :

1748

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

1749

    /// filter map.

1750

    FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :

1634

1751

      Parent(), const_true_map(true) {

1635

      Parent::setGraph(_graph);

1752

      Parent::setGraph(graph);

1636

1753

      Parent::setNodeFilterMap(const_true_map);

1637

1754

      Parent::setEdgeFilterMap(edge_filter_map);

    /// \brief Hides the edge of the graph

1757

    /// \brief Hides the given edge

1641

1758

///

1642

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

1643

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

1644

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

1759

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

1760

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

1761

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

1762

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

1645

1763

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

1646

1764

1647

    /// \brief Unhides the edge of the graph

1765

    /// \brief Shows the given edge

1648

1766

///

1649

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

1650

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

1651

    /// again

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.

1652

1770

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

1653

1771

1654

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

1772

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

1655

1773

///

1656

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

1657

///

1774

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

1658

1775

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

};

1661

1778

1662

  /// \brief Just gives back a FilterEdges adaptor

1779

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

1663

1780

///

1664

  /// Just gives back a FilterEdges adaptor

1781

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

1782

  /// \ingroup graph_adaptors

1783

  /// \relates FilterEdges

1665

1784

  template<typename Graph, typename EdgeFilterMap>

1666

1785

  FilterEdges<const Graph, EdgeFilterMap>

1667

1786

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

1668

1787

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

  template<typename Graph, typename EdgeFilterMap>

1672

1791

  FilterEdges<const Graph, const EdgeFilterMap>

1673

1792

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

1674

1793

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

  template <typename _Digraph>

1678

1798

  class UndirectorBase {

1679

1799

  public:

1680

1800

    typedef _Digraph Digraph;

1681

1801

    typedef UndirectorBase Adaptor;

    typedef True UndirectedTag;

    typedef typename Digraph::Arc Edge;

1686

1806

    typedef typename Digraph::Node Node;

    class Arc : public Edge {

...

@@ -1704,26 +1824,24 @@

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

1706

1826

        return _forward != other._forward ||

1707

1827

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

      bool operator<(const Arc &other) const {

1710

1830

        return _forward < other._forward ||

1711

1831

          (_forward == other._forward &&

1712

1832

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

};

    void first(Node& n) const {

1719

1837

      _digraph->first(n);

    void next(Node& n) const {

1723

1841

      _digraph->next(n);

    void first(Arc& a) const {

1727

1845

      _digraph->first(a);

1728

1846

      a._forward = true;

1729

1847

...

@@ -2059,122 +2177,128 @@

2059

2177

    UndirectorBase() : _digraph(0) {}

    Digraph* _digraph;

    void setDigraph(Digraph& digraph) {

2064

2182

      _digraph = &digraph;

};

  /// \ingroup graph_adaptors

2070

2188

///

2071

  /// \brief Undirect the graph

2189

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

2072

2190

///

2073

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

2074

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

2075

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

2076

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

2191

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

2192

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

2193

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

2194

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

2077

2195

///

2078

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

2079

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

2080

  /// to const.

2196

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

2197

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

2198

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

2199

///

2200

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

2201

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

2202

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

2203

///

2204

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

2205

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

2206

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

2207

  /// each other.

2208

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

2209

  /// of the adapted digraph.)

2081

2210

  template<typename _Digraph>

2082

2211

  class Undirector

2083

2212

    : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {

2084

2213

  public:

2085

2214

    typedef _Digraph Digraph;

2086

2215

    typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;

2087

2216

  protected:

2088

2217

    Undirector() { }

2089

2218

  public:

    /// \brief Constructor

2092

2221

///

2093

    /// Creates a undirected graph from the given digraph

2222

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

2094

2223

    Undirector(_Digraph& digraph) {

2095

2224

      setDigraph(digraph);

    /// \brief ArcMap combined from two original ArcMap

2227

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

2099

2228

///

2100

    /// This class adapts two original digraph ArcMap to

2101

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

2229

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

2230

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

2231

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

2232

    /// (\c %ForwardMap).

2102

2233

    template <typename _ForwardMap, typename _BackwardMap>

2103

2234

    class CombinedArcMap {

2104

2235

    public:

      typedef _ForwardMap ForwardMap;

2107

2238

      typedef _BackwardMap BackwardMap;

      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;

2110

2241

2242

      /// The key type of the map

2243

      typedef typename Parent::Arc Key;

2244

      /// The value type of the map

2111

2245

      typedef typename ForwardMap::Value Value;

2112

      typedef typename Parent::Arc Key;

      typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;

2115

2248

      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;

2116

2249

      typedef typename MapTraits<ForwardMap>::ReturnValue Reference;

2117

2250

      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;

2118

2251

2119

      /// \brief Constructor

2120

///

2121

2252

      /// Constructor

2122

2253

      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)

2123

2254

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

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

2127

///

2128

      /// Sets the value associated with a key.

2256

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

2129

2257

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

2130

2258

        if (Parent::direction(e)) {

2131

2259

          _forward->set(e, a);

2132

2260

        } else {

2133

2261

          _backward->set(e, a);

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

2138

///

2139

      /// Returns the value associated with a key.

2265

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

2140

2266

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

2141

2267

        if (Parent::direction(e)) {

2142

2268

          return (*_forward)[e];

2143

2269

        } else {

2144

2270

          return (*_backward)[e];

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

2149

///

2150

      /// Returns the value associated with a key.

2274

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

2151

2275

      ReturnValue operator[](const Key& e) {

2152

2276

        if (Parent::direction(e)) {

2153

2277

          return (*_forward)[e];

2154

2278

        } else {

2155

2279

          return (*_backward)[e];

    protected:

      ForwardMap* _forward;

2162

2286

      BackwardMap* _backward;

};

2165

2289

2166

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

2290

    /// \brief Returns a combined arc map

2167

2291

///

2168

    /// Just gives back a combined arc map

2292

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

2169

2293

    template <typename ForwardMap, typename BackwardMap>

2170

2294

    static CombinedArcMap<ForwardMap, BackwardMap>

2171

2295

    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {

2172

2296

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

    template <typename ForwardMap, typename BackwardMap>

2176

2300

    static CombinedArcMap<const ForwardMap, BackwardMap>

2177

2301

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

2178

2302

      return CombinedArcMap<const ForwardMap,

2179

2303

        BackwardMap>(forward, backward);

2180

2304

...

@@ -2186,33 +2310,36 @@

2186

2310

        const BackwardMap>(forward, backward);

    template <typename ForwardMap, typename BackwardMap>

2190

2314

    static CombinedArcMap<const ForwardMap, const BackwardMap>

2191

2315

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

2192

2316

      return CombinedArcMap<const ForwardMap,

2193

2317

        const BackwardMap>(forward, backward);

};

2197

2321

2198

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

2322

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

2199

2323

///

2200

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

2324

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

2325

  /// \ingroup graph_adaptors

2326

  /// \relates Undirector

2201

2327

  template<typename Digraph>

2202

2328

  Undirector<const Digraph>

2203

2329

  undirector(const Digraph& digraph) {

2204

2330

    return Undirector<const Digraph>(digraph);

  template <typename _Graph, typename _DirectionMap>

2208

2335

  class OrienterBase {

2209

2336

  public:

    typedef _Graph Graph;

2212

2339

    typedef _DirectionMap DirectionMap;

    typedef typename Graph::Node Node;

2215

2342

    typedef typename Graph::Edge Arc;

    void reverseArc(const Arc& arc) {

2218

2345

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

...

@@ -2355,70 +2482,94 @@

2355

2482

    void setDirectionMap(DirectionMap& direction) {

2356

2483

      _direction = &direction;

    void setGraph(Graph& graph) {

2360

2487

      _graph = &graph;

};

  /// \ingroup graph_adaptors

2366

2493

///

2367

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

2494

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

2368

2495

///

2369

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

2370

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

2371

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

2372

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

2373

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

2496

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

2497

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

2498

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

2499

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

2500

  /// of the adaptor.

2501

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

2374

2502

///

2375

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

2376

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

2377

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

2378

  /// graph.

2503

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

2504

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

2505

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

2379

2506

///

2380

  /// \sa orienter

2507

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

2508

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

2509

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

2510

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

2511

  /// adapted graph. The default map type is

2512

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

2513

///

2514

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

2515

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

2516

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

2517

  /// each other.

2518

#ifdef DOXYGEN

2381

2519

  template<typename _Graph,

2382

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

2520

           typename _DirectionMap>

2521

#else

2522

  template<typename _Graph,

2523

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

2524

#endif

2383

2525

  class Orienter :

2384

    public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {

2526

    public DigraphAdaptorExtender<OrienterBase<_Graph, _DirectionMap> > {

2385

2527

  public:

2528

2529

    /// The type of the adapted graph.

2386

2530

    typedef _Graph Graph;

2531

    /// The type of the direction edge map.

2532

    typedef _DirectionMap DirectionMap;

2533

2387

2534

    typedef DigraphAdaptorExtender<

2388

      OrienterBase<_Graph, DirectionMap> > Parent;

2535

      OrienterBase<_Graph, _DirectionMap> > Parent;

2389

2536

    typedef typename Parent::Arc Arc;

2390

2537

  protected:

2391

2538

    Orienter() { }

2392

2539

  public:

2393

2540

2394

    /// \brief Constructor of the adaptor

2541

    /// \brief Constructor

2395

2542

///

2396

    /// Constructor of the adaptor

2543

    /// Constructor of the adaptor.

2397

2544

    Orienter(Graph& graph, DirectionMap& direction) {

2398

2545

      setGraph(graph);

2399

2546

      setDirectionMap(direction);

    /// \brief Reverse arc

2549

    /// \brief Reverses the given arc

2403

2550

///

2404

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

2551

    /// This function reverses the given arc.

2552

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

2553

    /// in the direction map.

2405

2554

    void reverseArc(const Arc& a) {

2406

2555

      Parent::reverseArc(a);

};

2409

2558

2410

  /// \brief Just gives back a Orienter

2559

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

2411

2560

///

2412

  /// Just gives back a Orienter

2561

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

2562

  /// \ingroup graph_adaptors

2563

  /// \relates Orienter

2413

2564

  template<typename Graph, typename DirectionMap>

2414

2565

  Orienter<const Graph, DirectionMap>

2415

2566

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

2416

2567

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

  template<typename Graph, typename DirectionMap>

2420

2571

  Orienter<const Graph, const DirectionMap>

2421

2572

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

2422

2573

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

@@ -2482,66 +2633,90 @@

2482

2633

                        const Tolerance& tolerance = Tolerance())

2483

2634

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

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

2486

2637

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

};

  /// \ingroup graph_adaptors

2493

2644

///

2494

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

2645

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

2495

2646

  /// flow and circulation problems.

2496

2647

///

2497

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

2498

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

2499

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

2500

  /// be functions on the arc-set.

2648

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

2649

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

2650

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

2651

  /// functions on the arcs.

2652

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

2653

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

2654

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

2655

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

2656

  /// called residual digraph.

2657

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

2658

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

2659

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

2660

  /// arcs).

2661

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

2501

2662

///

2502

  /// Then Residual implements the digraph structure with

2503

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

2504

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

2505

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

2506

  /// called residual graph.  When we take the union

2507

  /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,

2508

  /// i.e.  if an arc is in both \f$ A_{forward} \f$ and

2509

  /// \f$ A_{backward} \f$, then in the adaptor it appears in both

2510

  /// orientation.

2663

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

2664

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

2665

  /// It is implicitly \c const.

2666

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

2667

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

2668

  /// The default map type is

2669

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

2670

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

2671

  /// the flow values in the flow problem.

2672

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

2673

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

2674

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

2675

  /// capacity map.

2511

2676

///

2512

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

2513

  /// "Digraph concept". The type is implicitly const.

2514

  /// \tparam _CapacityMap An arc map of some numeric type, it defines

2515

  /// the capacities in the flow problem. The map is implicitly const.

2516

  /// \tparam _FlowMap An arc map of some numeric type, it defines

2517

  /// the capacities in the flow problem.

2518

  /// \tparam _Tolerance Handler for inexact computation.

2677

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

2678

  /// adaptors.

2679

///

2680

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

2681

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

2682

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

2683

#ifdef DOXYGEN

2684

  template<typename _Digraph,

2685

           typename _CapacityMap,

2686

           typename _FlowMap,

2687

           typename _Tolerance>

2688

  class Residual

2689

#else

2519

2690

  template<typename _Digraph,

2520

2691

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

2521

2692

           typename _FlowMap = _CapacityMap,

2522

2693

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

2523

2694

  class Residual :

2524

2695

    public FilterArcs<

2525

2696

    Undirector<const _Digraph>,

2526

2697

    typename Undirector<const _Digraph>::template CombinedArcMap<

2527

2698

      _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,

2528

2699

                                      _FlowMap, _Tolerance>,

2529

2700

      _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,

2530

2701

                                       _FlowMap, _Tolerance> > >

2702

#endif

  public:

2533

2705

2706

    /// The type of the underlying digraph.

2534

2707

    typedef _Digraph Digraph;

2708

    /// The type of the capacity map.

2535

2709

    typedef _CapacityMap CapacityMap;

2710

    /// The type of the flow map.

2536

2711

    typedef _FlowMap FlowMap;

2537

2712

    typedef _Tolerance Tolerance;

    typedef typename CapacityMap::Value Value;

2540

2715

    typedef Residual Adaptor;

  protected:

    typedef Undirector<const Digraph> Undirected;

    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,

2547

2722

                                            FlowMap, Tolerance> ForwardFilter;

...

@@ -2555,110 +2730,115 @@

2555

2730

    typedef FilterArcs<Undirected, ArcFilter> Parent;

    const CapacityMap* _capacity;

2558

2733

    FlowMap* _flow;

    Undirected _graph;

2561

2736

    ForwardFilter _forward_filter;

2562

2737

    BackwardFilter _backward_filter;

2563

2738

    ArcFilter _arc_filter;

  public:

2566

2741

2567

    /// \brief Constructor of the residual digraph.

2742

    /// \brief Constructor

2568

2743

///

2569

    /// Constructor of the residual graph. The parameters are the digraph,

2570

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

2744

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

2745

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

2571

2746

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

2572

2747

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

2573

2748

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

2574

2749

        _forward_filter(capacity, flow, tolerance),

2575

2750

        _backward_filter(capacity, flow, tolerance),

2576

2751

        _arc_filter(_forward_filter, _backward_filter)

      Parent::setDigraph(_graph);

2579

2754

      Parent::setArcFilterMap(_arc_filter);

    typedef typename Parent::Arc Arc;

2583

2758

2584

    /// \brief Gives back the residual capacity of the arc.

2759

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

2585

2760

///

2586

    /// Gives back the residual capacity of the arc.

2761

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

2587

2762

    Value residualCapacity(const Arc& a) const {

2588

2763

      if (Undirected::direction(a)) {

2589

2764

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

2590

2765

      } else {

2591

2766

        return (*_flow)[a];

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

2770

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

2596

2771

///

2597

    /// Augment on the given arc in the residual graph. It increase

2598

    /// or decrease the flow on the original arc depend on the direction

2599

    /// of the residual arc.

2772

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

2773

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

2774

    /// direction of the residual arc.

2600

2775

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

2601

2776

      if (Undirected::direction(a)) {

2602

2777

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

2603

2778

      } else {

2604

2779

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

    /// \brief Returns the direction of the arc.

2783

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

2609

2784

///

2610

    /// Returns true when the arc is same oriented as the original arc.

2785

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

2786

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

2611

2787

    static bool forward(const Arc& a) {

2612

2788

      return Undirected::direction(a);

    /// \brief Returns the direction of the arc.

2791

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

2616

2792

///

2617

    /// Returns true when the arc is opposite oriented as the original arc.

2793

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

2794

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

2618

2795

    static bool backward(const Arc& a) {

2619

2796

      return !Undirected::direction(a);

    /// \brief Gives back the forward oriented residual arc.

2799

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

2623

2800

///

2624

    /// Gives back the forward oriented residual arc.

2801

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

2802

    /// arc of the underlying digraph.

2625

2803

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

2626

2804

      return Undirected::direct(a, true);

    /// \brief Gives back the backward oriented residual arc.

2807

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

2630

2808

///

2631

    /// Gives back the backward oriented residual arc.

2809

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

2810

    /// arc of the underlying digraph.

2632

2811

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

2633

2812

      return Undirected::direct(a, false);

    /// \brief Residual capacity map.

2637

2816

///

2638

    /// In generic residual graph the residual capacity can be obtained

2639

    /// as a map.

2817

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

2818

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

2819

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

2640

2820

    class ResidualCapacity {

2641

2821

    protected:

2642

2822

      const Adaptor* _adaptor;

2643

2823

    public:

2644

      /// The Key type

2824

      /// The key type of the map

2645

2825

      typedef Arc Key;

2646

      /// The Value type

2826

      /// The value type of the map

2647

2827

      typedef typename _CapacityMap::Value Value;

      /// Constructor

2650

2830

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

2651

2831

2652

      /// \e

2832

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

2653

2833

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

2654

2834

        return _adaptor->residualCapacity(a);

};

    /// \brief Returns a residual capacity map

2660

2840

///

2661

2841

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

2662

2842

    ResidualCapacity residualCapacity() const {

2663

2843

      return ResidualCapacity(*this);

2664

2844

...

@@ -3099,186 +3279,194 @@

3099

3279

    SplitNodesBase() : _digraph(0) {}

    Digraph* _digraph;

    void setDigraph(Digraph& digraph) {

3104

3284

      _digraph = &digraph;

};

  /// \ingroup graph_adaptors

3110

3290

///

3111

  /// \brief Split the nodes of a directed graph

3291

  /// \brief Adaptor class for splitting the nodes of a digraph.

3112

3292

///

3113

  /// The SplitNodes adaptor splits each node into an in-node and an

3114

  /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in

3115

  /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node

3116

  /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the

3117

  /// original digraph the new target of the arc will be \f$ u_{in} \f$

3118

  /// and similarly the source of the original \f$ (u, v) \f$ arc

3119

  /// will be \f$ u_{out} \f$.  The adaptor will add for each node in

3120

  /// the original digraph an additional arc which connects

3121

  /// \f$ (u_{in}, u_{out}) \f$.

3293

  /// SplitNodes adaptor can be used for splitting each node into an

3294

  /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor

3295

  /// replaces each node \f$ u \f$ in the digraph with two nodes,

3296

  /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.

3297

  /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the

3298

  /// new target of the arc will be \f$ u_{in} \f$ and similarly the

3299

  /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.

3300

  /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$

3301

  /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.

3122

3302

///

3123

  /// The aim of this class is to run algorithm with node costs if the

3124

  /// algorithm can use directly just arc costs. In this case we should use

3125

  /// a \c SplitNodes and set the node cost of the graph to the

3126

  /// bind arc in the adapted graph.

3303

  /// The aim of this class is running an algorithm with respect to node

3304

  /// costs or capacities if the algorithm considers only arc costs or

3305

  /// capacities directly.

3306

  /// In this case you can use \c SplitNodes adaptor, and set the node

3307

  /// costs/capacities of the original digraph to the \e bind \e arcs

3308

  /// in the adaptor.

3127

3309

///

3128

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

3129

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

3310

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

3311

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

3312

  /// It is implicitly \c const.

3313

///

3314

  /// \note The \c Node type of this adaptor is converible to the \c Node

3315

  /// type of the adapted digraph.

3130

3316

  template <typename _Digraph>

3131

3317

  class SplitNodes

3132

3318

    : public DigraphAdaptorExtender<SplitNodesBase<const _Digraph> > {

3133

3319

  public:

3134

3320

    typedef _Digraph Digraph;

3135

3321

    typedef DigraphAdaptorExtender<SplitNodesBase<const Digraph> > Parent;

    typedef typename Digraph::Node DigraphNode;

3138

3324

    typedef typename Digraph::Arc DigraphArc;

    typedef typename Parent::Node Node;

3141

3327

    typedef typename Parent::Arc Arc;

3142

3328

3143

    /// \brief Constructor of the adaptor.

3329

    /// \brief Constructor

3144

3330

///

3145

3331

    /// Constructor of the adaptor.

3146

3332

    SplitNodes(const Digraph& g) {

3147

3333

      Parent::setDigraph(g);

    /// \brief Returns true when the node is in-node.

3336

    /// \brief Returns \c true if the given node is an in-node.

3151

3337

///

3152

    /// Returns true when the node is in-node.

3338

    /// Returns \c true if the given node is an in-node.

3153

3339

    static bool inNode(const Node& n) {

3154

3340

      return Parent::inNode(n);

    /// \brief Returns true when the node is out-node.

3343

    /// \brief Returns \c true if the given node is an out-node.

3158

3344

///

3159

    /// Returns true when the node is out-node.

3345

    /// Returns \c true if the given node is an out-node.

3160

3346

    static bool outNode(const Node& n) {

3161

3347

      return Parent::outNode(n);

    /// \brief Returns true when the arc is arc in the original digraph.

3350

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

3165

3351

///

3166

    /// Returns true when the arc is arc in the original digraph.

3352

    /// Returns \c true if the given arc is one of the arcs in the

3353

    /// original digraph.

3167

3354

    static bool origArc(const Arc& a) {

3168

3355

      return Parent::origArc(a);

    /// \brief Returns true when the arc binds an in-node and an out-node.

3358

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

3172

3359

///

3173

    /// Returns true when the arc binds an in-node and an out-node.

3360

    /// Returns \c true if the given arc is a bind arc, i.e. it connects

3361

    /// an in-node and an out-node.

3174

3362

    static bool bindArc(const Arc& a) {

3175

3363

      return Parent::bindArc(a);

    /// \brief Gives back the in-node created from the \c node.

3366

    /// \brief Returns the in-node created from the given original node.

3179

3367

///

3180

    /// Gives back the in-node created from the \c node.

3368

    /// Returns the in-node created from the given original node.

3181

3369

    static Node inNode(const DigraphNode& n) {

3182

3370

      return Parent::inNode(n);

    /// \brief Gives back the out-node created from the \c node.

3373

    /// \brief Returns the out-node created from the given original node.

3186

3374

///

3187

    /// Gives back the out-node created from the \c node.

3375

    /// Returns the out-node created from the given original node.

3188

3376

    static Node outNode(const DigraphNode& n) {

3189

3377

      return Parent::outNode(n);

    /// \brief Gives back the arc binds the two part of the node.

3380

    /// \brief Returns the bind arc that corresponds to the given

3381

    /// original node.

3193

3382

///

3194

    /// Gives back the arc binds the two part of the node.

3383

    /// Returns the bind arc in the adaptor that corresponds to the given

3384

    /// original node, i.e. the arc connecting the in-node and out-node

3385

    /// of \c n.

3195

3386

    static Arc arc(const DigraphNode& n) {

3196

3387

      return Parent::arc(n);

    /// \brief Gives back the arc of the original arc.

3390

    /// \brief Returns the arc that corresponds to the given original arc.

3200

3391

///

3201

    /// Gives back the arc of the original arc.

3392

    /// Returns the arc in the adaptor that corresponds to the given

3393

    /// original arc.

3202

3394

    static Arc arc(const DigraphArc& a) {

3203

3395

      return Parent::arc(a);

    /// \brief NodeMap combined from two original NodeMap

3398

    /// \brief Node map combined from two original node maps

3207

3399

///

3208

    /// This class adapt two of the original digraph NodeMap to

3209

    /// get a node map on the adapted digraph.

3400

    /// This map adaptor class adapts two node maps of the original digraph

3401

    /// to get a node map of the split digraph.

3402

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

3403

    /// (\c InNodeMap).

3210

3404

    template <typename InNodeMap, typename OutNodeMap>

3211

3405

    class CombinedNodeMap {

3212

3406

    public:

3213

3407

3408

      /// The key type of the map

3214

3409

      typedef Node Key;

3410

      /// The value type of the map

3215

3411

      typedef typename InNodeMap::Value Value;

      typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;

3218

3414

      typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;

3219

3415

      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;

3220

3416

      typedef typename MapTraits<InNodeMap>::ReturnValue Reference;

3221

3417

      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;

3222

3418

3223

      /// \brief Constructor

3224

///

3225

      /// Constructor.

3419

      /// Constructor

3226

3420

      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)

3227

3421

        : _in_map(in_map), _out_map(out_map) {}

3228

3422

3229

      /// \brief The subscript operator.

3230

///

3231

      /// The subscript operator.

3423

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

3424

      Value operator[](const Key& key) const {

3425

        if (Parent::inNode(key)) {

3426

          return _in_map[key];

3427

        } else {

3428

          return _out_map[key];

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

3232

3433

      Value& operator[](const Key& key) {

3233

3434

        if (Parent::inNode(key)) {

3234

3435

          return _in_map[key];

3235

3436

        } else {

3236

3437

          return _out_map[key];

      /// \brief The const subscript operator.

3241

///

3242

      /// The const subscript operator.

3243

      Value operator[](const Key& key) const {

3244

        if (Parent::inNode(key)) {

3245

          return _in_map[key];

3246

        } else {

3247

          return _out_map[key];

      /// \brief The setter function of the map.

3252

///

3253

      /// The setter function of the map.

3441

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

3254

3442

      void set(const Key& key, const Value& value) {

3255

3443

        if (Parent::inNode(key)) {

3256

3444

          _in_map.set(key, value);

3257

3445

        } else {

3258

3446

          _out_map.set(key, value);

    private:

      InNodeMap& _in_map;

3265

3453

      OutNodeMap& _out_map;

};

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

3458

    /// \brief Returns a combined node map

3271

3459

///

3272

    /// Just gives back a combined node map

3460

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

3273

3461

    template <typename InNodeMap, typename OutNodeMap>

3274

3462

    static CombinedNodeMap<InNodeMap, OutNodeMap>

3275

3463

    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {

3276

3464

      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);

    template <typename InNodeMap, typename OutNodeMap>

3280

3468

    static CombinedNodeMap<const InNodeMap, OutNodeMap>

3281

3469

    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {

3282

3470

      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);

@@ -3286,93 +3474,90 @@

3286

3474

    static CombinedNodeMap<InNodeMap, const OutNodeMap>

3287

3475

    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {

3288

3476

      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);

    template <typename InNodeMap, typename OutNodeMap>

3292

3480

    static CombinedNodeMap<const InNodeMap, const OutNodeMap>

3293

3481

    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {

3294

3482

      return CombinedNodeMap<const InNodeMap,

3295

3483

        const OutNodeMap>(in_map, out_map);

    /// \brief ArcMap combined from an original ArcMap and a NodeMap

3486

    /// \brief Arc map combined from an arc map and a node map of the

3487

    /// original digraph.

3299

3488

///

3300

    /// This class adapt an original ArcMap and a NodeMap to get an

3301

    /// arc map on the adapted digraph

3489

    /// This map adaptor class adapts an arc map and a node map of the

3490

    /// original digraph to get an arc map of the split digraph.

3491

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

3492

    /// (\c DigraphArcMap).

3302

3493

    template <typename DigraphArcMap, typename DigraphNodeMap>

3303

3494

    class CombinedArcMap {

3304

3495

    public:

3305

3496

3497

      /// The key type of the map

3306

3498

      typedef Arc Key;

3499

      /// The value type of the map

3307

3500

      typedef typename DigraphArcMap::Value Value;

      typedef typename MapTraits<DigraphArcMap>::ReferenceMapTag

3310

3503

        ReferenceMapTag;

3311

3504

      typedef typename MapTraits<DigraphArcMap>::ReturnValue

3312

3505

        ReturnValue;

3313

3506

      typedef typename MapTraits<DigraphArcMap>::ConstReturnValue

3314

3507

        ConstReturnValue;

3315

3508

      typedef typename MapTraits<DigraphArcMap>::ReturnValue

3316

3509

        Reference;

3317

3510

      typedef typename MapTraits<DigraphArcMap>::ConstReturnValue

3318

3511

        ConstReference;

3319

3512

3320

      /// \brief Constructor

3321

///

3322

      /// Constructor.

3513

      /// Constructor

3323

3514

      CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)

3324

3515

        : _arc_map(arc_map), _node_map(node_map) {}

3325

3516

3326

      /// \brief The subscript operator.

3327

///

3328

      /// The subscript operator.

3517

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

3518

      Value operator[](const Key& arc) const {

3519

        if (Parent::origArc(arc)) {

3520

          return _arc_map[arc];

3521

        } else {

3522

          return _node_map[arc];

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

3527

      Value& operator[](const Key& arc) {

3528

        if (Parent::origArc(arc)) {

3529

          return _arc_map[arc];

3530

        } else {

3531

          return _node_map[arc];

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

3329

3536

      void set(const Arc& arc, const Value& val) {

3330

3537

        if (Parent::origArc(arc)) {

3331

3538

          _arc_map.set(arc, val);

3332

3539

        } else {

3333

3540

          _node_map.set(arc, val);

      /// \brief The const subscript operator.

3338

///

3339

      /// The const subscript operator.

3340

      Value operator[](const Key& arc) const {

3341

        if (Parent::origArc(arc)) {

3342

          return _arc_map[arc];

3343

        } else {

3344

          return _node_map[arc];

      /// \brief The const subscript operator.

3349

///

3350

      /// The const subscript operator.

3351

      Value& operator[](const Key& arc) {

3352

        if (Parent::origArc(arc)) {

3353

          return _arc_map[arc];

3354

        } else {

3355

          return _node_map[arc];

    private:

3360

3545

      DigraphArcMap& _arc_map;

3361

3546

      DigraphNodeMap& _node_map;

3362

3547

};

3363

3548

3364

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

3549

    /// \brief Returns a combined arc map

3365

3550

///

3366

    /// Just gives back a combined arc map

3551

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

3367

3552

    template <typename DigraphArcMap, typename DigraphNodeMap>

3368

3553

    static CombinedArcMap<DigraphArcMap, DigraphNodeMap>

3369

3554

    combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {

3370

3555

      return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);

    template <typename DigraphArcMap, typename DigraphNodeMap>

3374

3559

    static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>

3375

3560

    combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {

3376

3561

      return CombinedArcMap<const DigraphArcMap,

3377

3562

        DigraphNodeMap>(arc_map, node_map);

3378

3563

...

@@ -3385,25 +3570,27 @@

    template <typename DigraphArcMap, typename DigraphNodeMap>

3388

3573

    static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>

3389

3574

    combinedArcMap(const DigraphArcMap& arc_map,

3390

3575

                   const DigraphNodeMap& node_map) {

3391

3576

      return CombinedArcMap<const DigraphArcMap,

3392

3577

        const DigraphNodeMap>(arc_map, node_map);

};

3396

3581

3397

  /// \brief Just gives back a node splitter

3582

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

3398

3583

///

3399

  /// Just gives back a node splitter

3584

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

3585

  /// \ingroup graph_adaptors

3586

  /// \relates SplitNodes

3400

3587

  template<typename Digraph>

3401

3588

  SplitNodes<Digraph>

3402

3589

  splitNodes(const Digraph& digraph) {

3403

3590

    return SplitNodes<Digraph>(digraph);

} //namespace lemon

#endif //LEMON_ADAPTORS_H

RhodeCode

Login to your account

@@ -53,91 +53,94 @@
 		LEMON also provides a variety of graphs for these requirements called
 		\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
 		in conjunction with other graph representations.
 		You are free to use the graph structure that fit your requirements
 		the best, most graph algorithms and auxiliary data structures can be used
 		with any graph structure.
 		<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
-		@defgroup graph_adaptors Adaptor Classes for graphs
+		@defgroup graph_adaptors Adaptor Classes for Graphs
 		@ingroup graphs
-		\brief This group contains several adaptor classes for digraphs and graphs
+		\brief Adaptor classes for digraphs and graphs
 		This group contains several useful adaptor classes for digraphs and graphs.
 		The main parts of LEMON are the different graph structures, generic
-		graph algorithms, graph concepts which couple these, and graph
+		graph algorithms, graph concepts, which couple them, and graph
 		adaptors. While the previous notions are more or less clear, the
 		latter one needs further explanation. Graph adaptors are graph classes
 		which serve for considering graph structures in different ways.
 		A short example makes this much clearer.  Suppose that we have an
 		instance \c g of a directed graph type say ListDigraph and an algorithm
+		instance \c g of a directed graph type, say ListDigraph and an algorithm
 		\code
 		template <typename Digraph>
 		int algorithm(const Digraph&);
 		\endcode
 		is needed to run on the reverse oriented graph.  It may be expensive
 		(in time or in memory usage) to copy \c g with the reversed
 		arcs.  In this case, an adaptor class is used, which (according
 		to LEMON digraph concepts) works as a digraph.  The adaptor uses the
 		original digraph structure and digraph operations when methods of the
 		reversed oriented graph are called.  This means that the adaptor have
 		minor memory usage, and do not perform sophisticated algorithmic
 		to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
 		The adaptor uses the original digraph structure and digraph operations when
 		methods of the reversed oriented graph are called.  This means that the adaptor
 		have minor memory usage, and do not perform sophisticated algorithmic
 		actions.  The purpose of it is to give a tool for the cases when a
 		graph have to be used in a specific alteration.  If this alteration is
-		obtained by a usual construction like filtering the arc-set or
+		obtained by a usual construction like filtering the node or the arc set or
 		considering a new orientation, then an adaptor is worthwhile to use.
 		To come back to the reverse oriented graph, in this situation
 		\code
 		template<typename Digraph> class ReverseDigraph;
 		\endcode
 		template class can be used. The code looks as follows
 		\code
 		ListDigraph g;
-		ReverseDigraph<ListGraph> rg(g);
+		ReverseDigraph<ListDigraph> rg(g);
 		int result = algorithm(rg);
 		\endcode
 		After running the algorithm, the original graph \c g is untouched.
 		This techniques gives rise to an elegant code, and based on stable
 		During running the algorithm, the original digraph \c g is untouched.
 		This techniques give rise to an elegant code, and based on stable
 		graph adaptors, complex algorithms can be implemented easily.
-		In flow, circulation and bipartite matching problems, the residual
 		In flow, circulation and matching problems, the residual
 		graph is of particular importance. Combining an adaptor implementing
-		this, shortest path algorithms and minimum mean cycle algorithms,
+		this with shortest path algorithms or minimum mean cycle algorithms,
 		a range of weighted and cardinality optimization algorithms can be
 		obtained. For other examples, the interested user is referred to the
 		detailed documentation of particular adaptors.
 		The behavior of graph adaptors can be very different. Some of them keep
 		capabilities of the original graph while in other cases this would be
 		meaningless. This means that the concepts that they are models of depend
 		on the graph adaptor, and the wrapped graph(s).
 		If an arc of \c rg is deleted, this is carried out by deleting the
 		corresponding arc of \c g, thus the adaptor modifies the original graph.
 		meaningless. This means that the concepts that they meet depend
 		on the graph adaptor, and the wrapped graph.
 		For example, if an arc of a reversed digraph is deleted, this is carried
 		out by deleting the corresponding arc of the original digraph, thus the
 		adaptor modifies the original digraph.
 		However in case of a residual digraph, this operation has no sense.
 		But for a residual graph, this operation has no sense.
 		Let us stand one more example here to simplify your work.
-		RevGraphAdaptor has constructor
+		ReverseDigraph has constructor
 		\code
 		ReverseDigraph(Digraph& digraph);
 		\endcode
 		This means that in a situation, when a <tt>const ListDigraph&</tt>
+		This means that in a situation, when a <tt>const %ListDigraph&</tt>
 		reference to a graph is given, then it have to be instantiated with
 		<tt>Digraph=const ListDigraph</tt>.
+		<tt>Digraph=const %ListDigraph</tt>.
 		\code
 		int algorithm1(const ListDigraph& g) {
-		  RevGraphAdaptor<const ListDigraph> rg(g);
+		  ReverseDigraph<const ListDigraph> rg(g);
 		  return algorithm2(rg);
+		}
 		\endcode
 		*/
 		/**
 		@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
 		@ingroup graphs
 		\brief Graph types between real graphs and graph adaptors.
 		This group describes some graph types between real graphs and graph adaptors.
 		These classes wrap graphs to give new functionality as the adaptors do it.