LEMON/LEMON-official Changeset - r703:cb38ccedd2c1

@@ -1074,1682 +1074,1679 @@

1074

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

1075

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

1076

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

1077

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

1078

1079

    public:

1080

      typedef V Value;

1081

1082

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

1083

        : Parent(adaptor) {}

1084

1085

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

1086

        : Parent(adaptor, value) {}

1087

1088

    private:

1089

      EdgeMap& operator=(const EdgeMap& cmap) {

1090

        return operator=<EdgeMap>(cmap);

1091

1092

1093

      template <typename CMap>

1094

      EdgeMap& operator=(const CMap& cmap) {

1095

        Parent::operator=(cmap);

1096

        return *this;

1097

1098

};

1099

1100

};

1101

1102

  template <typename GR, typename NF, typename EF>

1103

  class SubGraphBase<GR, NF, EF, false>

1104

    : public GraphAdaptorBase<GR> {

1105

    typedef GraphAdaptorBase<GR> Parent;

1106

  public:

1107

    typedef GR Graph;

1108

    typedef NF NodeFilterMap;

1109

    typedef EF EdgeFilterMap;

1110

1111

    typedef SubGraphBase Adaptor;

1112

  protected:

1113

    NF* _node_filter;

1114

    EF* _edge_filter;

1115

    SubGraphBase()

1116

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

1117

1118

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

1119

      Parent::initialize(graph);

1120

      _node_filter = &node_filter;

1121

      _edge_filter = &edge_filter;

1122

1123

1124

  public:

1125

1126

    typedef typename Parent::Node Node;

1127

    typedef typename Parent::Arc Arc;

1128

    typedef typename Parent::Edge Edge;

1129

1130

    void first(Node& i) const {

1131

      Parent::first(i);

1132

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

1133

1134

1135

    void first(Arc& i) const {

1136

      Parent::first(i);

1137

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

1138

1139

1140

    void first(Edge& i) const {

1141

      Parent::first(i);

1142

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

1143

1144

1145

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

1146

      Parent::firstIn(i, n);

1147

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

1148

1149

1150

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

1151

      Parent::firstOut(i, n);

1152

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

1153

1154

1155

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

1156

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

1157

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

1158

1159

1160

    void next(Node& i) const {

1161

      Parent::next(i);

1162

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

1163

1164

    void next(Arc& i) const {

1165

      Parent::next(i);

1166

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

1167

1168

    void next(Edge& i) const {

1169

      Parent::next(i);

1170

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

1171

1172

    void nextIn(Arc& i) const {

1173

      Parent::nextIn(i);

1174

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

1175

1176

1177

    void nextOut(Arc& i) const {

1178

      Parent::nextOut(i);

1179

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

1180

1181

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

1182

      Parent::nextInc(i, d);

1183

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

1184

1185

1186

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

1187

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

1188

1189

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

1190

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

1191

1192

    typedef False NodeNumTag;

1193

    typedef False ArcNumTag;

1194

    typedef False EdgeNumTag;

1195

1196

    typedef FindArcTagIndicator<Graph> FindArcTag;

1197

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

1198

                const Arc& prev = INVALID) const {

1199

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

1200

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

1201

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

1202

1203

      return arc;

1204

1205

1206

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

1207

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

1208

                  const Edge& prev = INVALID) const {

1209

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

1210

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

1211

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

1212

1213

      return edge;

1214

1215

1216

    template <typename V>

1217

    class NodeMap

1218

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

1219

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

1220

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

1221

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

1222

1223

    public:

1224

      typedef V Value;

1225

1226

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

1227

        : Parent(adaptor) {}

1228

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

1229

        : Parent(adaptor, value) {}

1230

1231

    private:

1232

      NodeMap& operator=(const NodeMap& cmap) {

1233

        return operator=<NodeMap>(cmap);

1234

1235

1236

      template <typename CMap>

1237

      NodeMap& operator=(const CMap& cmap) {

1238

        Parent::operator=(cmap);

1239

        return *this;

1240

1241

};

1242

1243

    template <typename V>

1244

    class ArcMap

1245

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

1246

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

1247

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

1248

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

1249

1250

    public:

1251

      typedef V Value;

1252

1253

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

1254

        : Parent(adaptor) {}

1255

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

1256

        : Parent(adaptor, value) {}

1257

1258

    private:

1259

      ArcMap& operator=(const ArcMap& cmap) {

1260

        return operator=<ArcMap>(cmap);

1261

1262

1263

      template <typename CMap>

1264

      ArcMap& operator=(const CMap& cmap) {

1265

        Parent::operator=(cmap);

1266

        return *this;

1267

1268

};

1269

1270

    template <typename V>

1271

    class EdgeMap

1272

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

1273

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

1274

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

1275

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

1276

1277

    public:

1278

      typedef V Value;

1279

1280

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

1281

        : Parent(adaptor) {}

1282

1283

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

1284

        : Parent(adaptor, value) {}

1285

1286

    private:

1287

      EdgeMap& operator=(const EdgeMap& cmap) {

1288

        return operator=<EdgeMap>(cmap);

1289

1290

1291

      template <typename CMap>

1292

      EdgeMap& operator=(const CMap& cmap) {

1293

        Parent::operator=(cmap);

1294

        return *this;

1295

1296

};

1297

1298

};

1299

1300

  /// \ingroup graph_adaptors

1301

///

1302

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

1303

  /// graph.

1304

///

1305

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

1306

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

1307

  /// define the filters for nodes and edges.

1308

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

1309

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

1310

  /// nodes are also filtered out.

1311

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

1312

///

1313

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

1314

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

1315

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

1316

///

1317

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

1318

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

1319

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

1320

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

1321

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

1322

  /// adapted graph. The default type is

1323

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

1324

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

1325

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

1326

  /// adapted graph. The default type is

1327

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

1328

///

1329

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

1330

  /// adapted graph are convertible to each other.

1331

///

1332

  /// \see FilterNodes

1333

  /// \see FilterEdges

1334

#ifdef DOXYGEN

1335

  template<typename GR, typename NF, typename EF>

1336

  class SubGraph {

1337

#else

1338

  template<typename GR,

1339

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

1340

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

1341

  class SubGraph :

1342

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

1343

#endif

1344

  public:

1345

    /// The type of the adapted graph.

1346

    typedef GR Graph;

1347

    /// The type of the node filter map.

1348

    typedef NF NodeFilterMap;

1349

    /// The type of the edge filter map.

1350

    typedef EF EdgeFilterMap;

1351

1352

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

1353

      Parent;

1354

1355

    typedef typename Parent::Node Node;

1356

    typedef typename Parent::Edge Edge;

1357

1358

  protected:

1359

    SubGraph() { }

1360

  public:

1361

1362

    /// \brief Constructor

1363

///

1364

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

1365

    /// and edge filter maps.

1366

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

1367

      initialize(graph, node_filter, edge_filter);

1368

1369

1370

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

1371

///

1372

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

1373

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

1374

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

1375

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

1376

1377

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

1378

///

1379

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

1380

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

1381

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

1382

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

1383

1384

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

1385

///

1386

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

1387

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

1388

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

1389

1390

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

1391

///

1392

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

1393

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

1394

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

1395

1396

    /// \brief Disables the given node

1397

///

1398

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

1399

    /// so the iteration jumps over it.

1400

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

1401

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

1402

1403

    /// \brief Disables the given edge

1404

///

1405

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

1406

    /// so the iteration jumps over it.

1407

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

1408

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

1409

1410

    /// \brief Enables the given node

1411

///

1412

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

1413

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

1414

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

1415

1416

    /// \brief Enables the given edge

1417

///

1418

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

1419

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

1420

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

1421

1422

};

1423

1424

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

1425

///

1426

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

1427

  /// \ingroup graph_adaptors

1428

  /// \relates SubGraph

1429

  template<typename GR, typename NF, typename EF>

1430

  SubGraph<const GR, NF, EF>

1431

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

1432

    return SubGraph<const GR, NF, EF>

1433

      (graph, node_filter, edge_filter);

1434

1435

1436

  template<typename GR, typename NF, typename EF>

1437

  SubGraph<const GR, const NF, EF>

1438

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

1439

    return SubGraph<const GR, const NF, EF>

1440

      (graph, node_filter, edge_filter);

1441

1442

1443

  template<typename GR, typename NF, typename EF>

1444

  SubGraph<const GR, NF, const EF>

1445

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

1446

    return SubGraph<const GR, NF, const EF>

1447

      (graph, node_filter, edge_filter);

1448

1449

1450

  template<typename GR, typename NF, typename EF>

1451

  SubGraph<const GR, const NF, const EF>

1452

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

1453

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

1454

      (graph, node_filter, edge_filter);

  /// \ingroup graph_adaptors

1459

///

1460

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

1461

///

1462

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

1463

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

1464

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

1465

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

1466

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

1467

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

1468

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

1469

///

1470

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

1471

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

1472

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

1473

///

1474

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

1475

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

1476

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

1477

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

1478

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

1479

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

1480

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

1481

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

1482

///

1483

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

1484

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

1485

#ifdef DOXYGEN

1486

  template<typename GR, typename NF>

1487

  class FilterNodes {

1488

#else

1489

  template<typename GR,

1490

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

1491

           typename Enable = void>

1492

  class FilterNodes :

1493

    public DigraphAdaptorExtender<

1494

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

1495

                     true> > {

1496

#endif

1497

    typedef DigraphAdaptorExtender<

1498

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

1499

                     true> > Parent;

1500

1501

  public:

1502

1503

    typedef GR Digraph;

1504

    typedef NF NodeFilterMap;

1505

1506

    typedef typename Parent::Node Node;

1507

1508

  protected:

1509

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

1510

1511

    FilterNodes() : const_true_map() {}

1512

1513

  public:

1514

1515

    /// \brief Constructor

1516

///

1517

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

1518

    /// given node filter map.

1519

    FilterNodes(GR& graph, NF& node_filter)

1520

      : Parent(), const_true_map()

1521

1522

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

1523

1524

1525

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

1526

///

1527

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

1528

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

1529

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

1530

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

1531

1532

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

1533

///

1534

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

1535

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

1536

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

1537

1538

    /// \brief Disables the given node

1539

///

1540

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

1541

    /// jumps over it.

1542

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

1543

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

1544

1545

    /// \brief Enables the given node

1546

///

1547

    /// This function enables the given node.

1548

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

1549

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

1550

1551

};

1552

1553

  template<typename GR, typename NF>

1554

  class FilterNodes<GR, NF,

1555

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

1556

    public GraphAdaptorExtender<

1557

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

1558

                   true> > {

1559

1560

    typedef GraphAdaptorExtender<

1561

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

1562

                   true> > Parent;

1563

1564

  public:

1565

1566

    typedef GR Graph;

1567

    typedef NF NodeFilterMap;

1568

1569

    typedef typename Parent::Node Node;

1570

1571

  protected:

1572

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

1573

1574

    FilterNodes() : const_true_map() {}

1575

1576

  public:

1577

1578

    FilterNodes(GR& graph, NodeFilterMap& node_filter) :

1579

      Parent(), const_true_map() {

1580

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

1581

1582

1583

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

1584

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

1585

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

1586

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

1587

1588

};

1589

1590

1591

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

1592

///

1593

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

1594

  /// \ingroup graph_adaptors

1595

  /// \relates FilterNodes

1596

  template<typename GR, typename NF>

1597

  FilterNodes<const GR, NF>

1598

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

1599

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

1600

1601

1602

  template<typename GR, typename NF>

1603

  FilterNodes<const GR, const NF>

1604

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

1605

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

1606

1607

1608

  /// \ingroup graph_adaptors

1609

///

1610

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

1611

///

1612

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

1613

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

1614

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

1615

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

1616

  /// "Digraph" concept.

1617

///

1618

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

1619

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

1620

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

1621

///

1622

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

1623

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

1624

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

1625

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

1626

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

1627

  /// adapted digraph. The default type is

1628

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

1629

///

1630

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

1631

  /// digraph are convertible to each other.

1632

#ifdef DOXYGEN

1633

  template<typename DGR,

1634

           typename AF>

1635

  class FilterArcs {

1636

#else

1637

  template<typename DGR,

1638

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

1639

  class FilterArcs :

1640

    public DigraphAdaptorExtender<

1641

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

1642

                     AF, false> > {

1643

#endif

1644

    typedef DigraphAdaptorExtender<

1645

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

1646

                     AF, false> > Parent;

1647

1648

  public:

1649

1650

    /// The type of the adapted digraph.

1651

    typedef DGR Digraph;

1652

    /// The type of the arc filter map.

1653

    typedef AF ArcFilterMap;

1654

1655

    typedef typename Parent::Arc Arc;

1656

1657

  protected:

1658

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

1659

1660

    FilterArcs() : const_true_map() {}

1661

1662

  public:

1663

1664

    /// \brief Constructor

1665

///

1666

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

1667

    /// filter map.

1668

    FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)

1669

      : Parent(), const_true_map() {

1670

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

1671

1672

1673

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

1674

///

1675

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

1676

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

1677

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

1678

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

1679

1680

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

1681

///

1682

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

1683

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

1684

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

1685

1686

    /// \brief Disables the given arc

1687

///

1688

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

1689

    /// so the iteration jumps over it.

1690

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

1691

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

1692

1693

    /// \brief Enables the given arc

1694

///

1695

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

1696

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

1697

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

1698

1699

};

1700

1701

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

1702

///

1703

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

1704

  /// \ingroup graph_adaptors

1705

  /// \relates FilterArcs

1706

  template<typename DGR, typename AF>

1707

  FilterArcs<const DGR, AF>

1708

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

1709

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

1710

1711

1712

  template<typename DGR, typename AF>

1713

  FilterArcs<const DGR, const AF>

1714

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

1715

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

1716

1717

1718

  /// \ingroup graph_adaptors

1719

///

1720

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

1721

///

1722

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

1723

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

1724

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

1725

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

1726

  /// "Graph" concept.

1727

///

1728

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

1729

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

1730

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

1731

///

1732

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

1733

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

1734

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

1735

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

1736

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

1737

  /// adapted graph. The default type is

1738

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

1739

///

1740

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

1741

  /// adapted graph are convertible to each other.

1742

#ifdef DOXYGEN

1743

  template<typename GR,

1744

           typename EF>

1745

  class FilterEdges {

1746

#else

1747

  template<typename GR,

1748

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

1749

  class FilterEdges :

1750

    public GraphAdaptorExtender<

1751

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

1752

                   EF, false> > {

1753

#endif

1754

    typedef GraphAdaptorExtender<

1755

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

1756

                   EF, false> > Parent;

1757

1758

  public:

1759

1760

    /// The type of the adapted graph.

1761

    typedef GR Graph;

1762

    /// The type of the edge filter map.

1763

    typedef EF EdgeFilterMap;

1764

1765

    typedef typename Parent::Edge Edge;

1766

1767

  protected:

1768

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

1769

1770

    FilterEdges() : const_true_map(true) {

1771

      Parent::setNodeFilterMap(const_true_map);

1772

1773

1774

  public:

1775

1776

    /// \brief Constructor

1777

///

1778

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

1779

    /// filter map.

1780

    FilterEdges(GR& graph, EF& edge_filter)

1781

      : Parent(), const_true_map() {

1782

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

1783

1784

1785

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

1786

///

1787

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

1788

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

1789

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

1790

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

1791

1792

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

1793

///

1794

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

1795

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

1796

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

1797

1798

    /// \brief Disables the given edge

1799

///

1800

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

1801

    /// so the iteration jumps over it.

1802

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

1803

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

1804

1805

    /// \brief Enables the given edge

1806

///

1807

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

1808

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

1809

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

1810

1811

};

1812

1813

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

1814

///

1815

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

1816

  /// \ingroup graph_adaptors

1817

  /// \relates FilterEdges

1818

  template<typename GR, typename EF>

1819

  FilterEdges<const GR, EF>

1820

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

1821

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

1822

1823

1824

  template<typename GR, typename EF>

1825

  FilterEdges<const GR, const EF>

1826

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

1827

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

  template <typename DGR>

1832

  class UndirectorBase {

1833

  public:

1834

    typedef DGR Digraph;

1835

    typedef UndirectorBase Adaptor;

1836

1837

    typedef True UndirectedTag;

1838

1839

    typedef typename Digraph::Arc Edge;

1840

    typedef typename Digraph::Node Node;

1841

1842

    class Arc : public Edge {

1842

    class Arc {

1843

      friend class UndirectorBase;

1844

    protected:

1845

      Edge _edge;

1845

1846

      bool _forward;

1846

1847

      Arc(const Edge& edge, bool forward) :

1848

        Edge(edge), _forward(forward) {}

1848

      Arc(const Edge& edge, bool forward)

1849

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

1849

1850

1851

    public:

1851

1852

      Arc() {}

1852

1853

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

1854

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

1855

1856

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

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

1856

        return _forward == other._forward &&

1857

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

1859

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

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

1860

        return _forward != other._forward ||

1861

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

1862

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

1862

1863

1864

      bool operator<(const Arc &other) const {

1864

1865

        return _forward < other._forward ||

1865

          (_forward == other._forward &&

1866

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

1866

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

1867

1868

};

1869

1870

    void first(Node& n) const {

1871

      _digraph->first(n);

1872

1873

1874

    void next(Node& n) const {

1875

      _digraph->next(n);

1876

1877

1878

    void first(Arc& a) const {

1879

      _digraph->first(a);

1879

      _digraph->first(a._edge);

1880

      a._forward = true;

1881

1882

1883

    void next(Arc& a) const {

1884

      if (a._forward) {

1885

        a._forward = false;

1886

      } else {

1887

        _digraph->next(a);

1887

        _digraph->next(a._edge);

1888

        a._forward = true;

    void first(Edge& e) const {

1893

      _digraph->first(e);

1894

1895

1896

    void next(Edge& e) const {

1897

      _digraph->next(e);

1898

1899

1900

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

1901

      _digraph->firstIn(a, n);

1902

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

1901

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

1902

      if (a._edge != INVALID ) {

1903

        a._forward = false;

1904

      } else {

1905

        _digraph->firstOut(a, n);

1905

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

1906

        a._forward = true;

1907

1908

1909

    void nextOut(Arc &a) const {

1910

      if (!a._forward) {

1911

        Node n = _digraph->target(a);

1912

        _digraph->nextIn(a);

1913

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

1914

          _digraph->firstOut(a, n);

1911

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

1912

        _digraph->nextIn(a._edge);

1913

        if (a._edge == INVALID) {

1914

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

1915

          a._forward = true;

1916

1917

1918

      else {

1919

        _digraph->nextOut(a);

1919

        _digraph->nextOut(a._edge);

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

1924

      _digraph->firstOut(a, n);

1925

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

1924

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

1925

      if (a._edge != INVALID ) {

1926

        a._forward = false;

1927

      } else {

1928

        _digraph->firstIn(a, n);

1928

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

1929

        a._forward = true;

1930

1931

1932

    void nextIn(Arc &a) const {

1933

      if (!a._forward) {

1934

        Node n = _digraph->source(a);

1935

        _digraph->nextOut(a);

1936

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

1937

          _digraph->firstIn(a, n);

1934

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

1935

        _digraph->nextOut(a._edge);

1936

        if (a._edge == INVALID ) {

1937

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

1938

          a._forward = true;

1939

1940

1941

      else {

1942

        _digraph->nextIn(a);

1942

        _digraph->nextIn(a._edge);

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

1947

      d = true;

1948

      _digraph->firstOut(e, n);

1949

      if (e != INVALID) return;

1950

      d = false;

1951

      _digraph->firstIn(e, n);

1952

1953

1954

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

1955

      if (d) {

1956

        Node s = _digraph->source(e);

1957

        _digraph->nextOut(e);

1958

        if (e != INVALID) return;

1959

        d = false;

1960

        _digraph->firstIn(e, s);

1961

      } else {

1962

        _digraph->nextIn(e);

    Node u(const Edge& e) const {

1967

      return _digraph->source(e);

1968

1969

1970

    Node v(const Edge& e) const {

1971

      return _digraph->target(e);

1972

1973

1974

    Node source(const Arc &a) const {

1975

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

1975

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

1976

1977

1978

    Node target(const Arc &a) const {

1979

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

1979

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

1980

1981

1982

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

1983

      return Arc(e, d);

1984

1985

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

1986

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

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

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

1992

1989

    Arc arcFromId(int ix) const {

1993

1990

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

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

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

1998

1995

    int id(const Arc &a) const {

1999

1996

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

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

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

2004

2001

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

2005

2002

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

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

2008

2005

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

2009

2006

      return _digraph->addArc(u, v);

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

2013

2010

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

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

    typedef NodeNumTagIndicator<Digraph> NodeNumTag;

2018

2015

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

    typedef ArcNumTagIndicator<Digraph> ArcNumTag;

2021

2018

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

    typedef ArcNumTag EdgeNumTag;

2024

2021

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

    typedef FindArcTagIndicator<Digraph> FindArcTag;

2027

2024

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

2028

2025

      if (p == INVALID) {

2029

2026

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

2030

2027

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

2031

2028

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

2032

2029

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

2033

2030

      } else if (direction(p)) {

2034

2031

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

2035

2032

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

2036

2033

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

2037

2034

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

2038

2035

      } else {

2039

2036

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

2040

2037

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

      return INVALID;

    typedef FindArcTag FindEdgeTag;

2046

2043

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

2047

2044

      if (s != t) {

2048

2045

        if (p == INVALID) {

2049

2046

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

2050

2047

          if (arc != INVALID) return arc;

2051

2048

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

2052

2049

          if (arc != INVALID) return arc;

2053

2050

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

2054

2051

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

2055

2052

          if (arc != INVALID) return arc;

2056

2053

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

2057

2054

          if (arc != INVALID) return arc;

2058

2055

        } else {

2059

2056

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

2060

2057

          if (arc != INVALID) return arc;

      } else {

2063

2060

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

      return INVALID;

  private:

    template <typename V>

2071

2068

    class ArcMapBase {

2072

2069

    private:

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

    public:

      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;

      typedef V Value;

2081

2078

      typedef Arc Key;

2082

2079

      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;

2083

2080

      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;

2084

2081

      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;

2085

2082

      typedef typename MapTraits<MapImpl>::ReturnValue Reference;

      ArcMapBase(const UndirectorBase<DGR>& adaptor) :

2088

2085

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

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

2091

2088

        : _forward(*adaptor._digraph, value),

2092

2089

          _backward(*adaptor._digraph, value) {}

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

2095

2092

        if (direction(a)) {

2096

2093

          _forward.set(a, value);

2097

2094

        } else {

2098

2095

          _backward.set(a, value);

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

2103

2100

        if (direction(a)) {

2104

2101

          return _forward[a];

2105

2102

        } else {

2106

2103

          return _backward[a];

      ReturnValue operator[](const Arc& a) {

2111

2108

        if (direction(a)) {

2112

2109

          return _forward[a];

2113

2110

        } else {

2114

2111

          return _backward[a];

    protected:

      MapImpl _forward, _backward;

};

  public:

    template <typename V>

2127

2124

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

2128

2125

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

    public:

2131

2128

      typedef V Value;

      explicit NodeMap(const UndirectorBase<DGR>& adaptor)

2134

2131

        : Parent(*adaptor._digraph) {}

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

2137

2134

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

    private:

2140

2137

      NodeMap& operator=(const NodeMap& cmap) {

2141

2138

        return operator=<NodeMap>(cmap);

      template <typename CMap>

2145

2142

      NodeMap& operator=(const CMap& cmap) {

2146

2143

        Parent::operator=(cmap);

2147

2144

        return *this;

};

    template <typename V>

2153

2150

    class ArcMap

2154

2151

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

2155

2152

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

    public:

2158

2155

      typedef V Value;

      explicit ArcMap(const UndirectorBase<DGR>& adaptor)

2161

2158

        : Parent(adaptor) {}

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

2164

2161

        : Parent(adaptor, value) {}

    private:

2167

2164

      ArcMap& operator=(const ArcMap& cmap) {

2168

2165

        return operator=<ArcMap>(cmap);

      template <typename CMap>

2172

2169

      ArcMap& operator=(const CMap& cmap) {

2173

2170

        Parent::operator=(cmap);

2174

2171

        return *this;

};

    template <typename V>

2179

2176

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

2180

2177

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

    public:

2183

2180

      typedef V Value;

      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)

2186

2183

        : Parent(*adaptor._digraph) {}

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

2189

2186

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

    private:

2192

2189

      EdgeMap& operator=(const EdgeMap& cmap) {

2193

2190

        return operator=<EdgeMap>(cmap);

      template <typename CMap>

2197

2194

      EdgeMap& operator=(const CMap& cmap) {

2198

2195

        Parent::operator=(cmap);

2199

2196

        return *this;

};

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

2205

2202

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

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

2208

2205

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

    typedef EdgeNotifier ArcNotifier;

2211

2208

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

  protected:

    UndirectorBase() : _digraph(0) {}

    DGR* _digraph;

    void initialize(DGR& digraph) {

2220

2217

      _digraph = &digraph;

};

  /// \ingroup graph_adaptors

2226

2223

///

2227

2224

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

2228

2225

///

2229

2226

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

2230

2227

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

2231

2228

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

2232

2229

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

2233

2230

///

2234

2231

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

2235

2232

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

2236

2233

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

2237

2234

///

2238

2235

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

2239

2236

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

2240

2237

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

2241

2238

///

2242

2239

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

2243

2240

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

2244

2241

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

2245

2242

  /// each other.

2246

2243

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

2247

2244

  /// of the adapted digraph.)

2248

2245

  template<typename DGR>

2249

2246

#ifdef DOXYGEN

2250

2247

  class Undirector {

2251

2248

#else

2252

2249

  class Undirector :

2253

2250

    public GraphAdaptorExtender<UndirectorBase<DGR> > {

2254

2251

#endif

2255

2252

    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;

2256

2253

  public:

2257

2254

    /// The type of the adapted digraph.

2258

2255

    typedef DGR Digraph;

2259

2256

  protected:

2260

2257

    Undirector() { }

2261

2258

  public:

    /// \brief Constructor

2264

2261

///

2265

2262

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

2266

2263

    Undirector(DGR& digraph) {

2267

2264

      initialize(digraph);

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

2271

2268

///

2272

2269

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

2273

2270

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

2274

2271

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

2275

2272

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

2276

2273

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

2277

2274

    template <typename FW, typename BK>

2278

2275

    class CombinedArcMap {

2279

2276

    public:

      /// The key type of the map

2282

2279

      typedef typename Parent::Arc Key;

2283

2280

      /// The value type of the map

2284

2281

      typedef typename FW::Value Value;

      typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;

      typedef typename MapTraits<FW>::ReturnValue ReturnValue;

2289

2286

      typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;

2290

2287

      typedef typename MapTraits<FW>::ReturnValue Reference;

2291

2288

      typedef typename MapTraits<FW>::ConstReturnValue ConstReference;

      /// Constructor

2294

2291

      CombinedArcMap(FW& forward, BK& backward)

2295

2292

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

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

2298

2295

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

2299

2296

        if (Parent::direction(e)) {

2300

2297

          _forward->set(e, a);

2301

2298

        } else {

2302

2299

          _backward->set(e, a);

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

2307

2304

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

2308

2305

        if (Parent::direction(e)) {

2309

2306

          return (*_forward)[e];

2310

2307

        } else {

2311

2308

          return (*_backward)[e];

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

2316

2313

      ReturnValue operator[](const Key& e) {

2317

2314

        if (Parent::direction(e)) {

2318

2315

          return (*_forward)[e];

2319

2316

        } else {

2320

2317

          return (*_backward)[e];

    protected:

      FW* _forward;

2327

2324

      BK* _backward;

};

    /// \brief Returns a combined arc map

2332

2329

///

2333

2330

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

2334

2331

    template <typename FW, typename BK>

2335

2332

    static CombinedArcMap<FW, BK>

2336

2333

    combinedArcMap(FW& forward, BK& backward) {

2337

2334

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

    template <typename FW, typename BK>

2341

2338

    static CombinedArcMap<const FW, BK>

2342

2339

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

2343

2340

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

    template <typename FW, typename BK>

2347

2344

    static CombinedArcMap<FW, const BK>

2348

2345

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

2349

2346

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

    template <typename FW, typename BK>

2353

2350

    static CombinedArcMap<const FW, const BK>

2354

2351

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

2355

2352

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

};

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

2361

2358

///

2362

2359

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

2363

2360

  /// \ingroup graph_adaptors

2364

2361

  /// \relates Undirector

2365

2362

  template<typename DGR>

2366

2363

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

2367

2364

    return Undirector<const DGR>(digraph);

  template <typename GR, typename DM>

2372

2369

  class OrienterBase {

2373

2370

  public:

    typedef GR Graph;

2376

2373

    typedef DM DirectionMap;

    typedef typename GR::Node Node;

2379

2376

    typedef typename GR::Edge Arc;

    void reverseArc(const Arc& arc) {

2382

2379

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

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

2386

2383

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

2387

2384

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

2388

2385

      bool d = true;

2389

2386

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

2390

2387

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

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

2393

2390

      bool d = true;

2394

2391

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

2395

2392

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

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

2399

2396

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

2400

2397

    void nextIn(Arc& i) const {

2401

2398

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

2402

2399

      _graph->nextInc(i, d);

2403

2400

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

    void nextOut(Arc& i) const {

2406

2403

      bool d = (*_direction)[i];

2407

2404

      _graph->nextInc(i, d);

2408

2405

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

    Node source(const Arc& e) const {

2412

2409

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

    Node target(const Arc& e) const {

2415

2412

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

    typedef NodeNumTagIndicator<Graph> NodeNumTag;

2419

2416

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

    typedef EdgeNumTagIndicator<Graph> ArcNumTag;

2422

2419

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

    typedef FindEdgeTagIndicator<Graph> FindArcTag;

2425

2422

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

2426

2423

                const Arc& prev = INVALID) const {

2427

2424

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

2428

2425

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

2429

2426

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

      return arc;

    Node addNode() {

2435

2432

      return Node(_graph->addNode());

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

2439

2436

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

2440

2437

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

2441

2438

      return arc;

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

2445

2442

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

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

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

2450

2447

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

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

2453

2450

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

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

2456

2453

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

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

2459

2456

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

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

2462

2459

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

    template <typename V>

2465

2462

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

2466

2463

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

    public:

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

2471

2468

        : Parent(*adapter._graph) {}

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

2474

2471

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

    private:

2477

2474

      NodeMap& operator=(const NodeMap& cmap) {

2478

2475

        return operator=<NodeMap>(cmap);

      template <typename CMap>

2482

2479

      NodeMap& operator=(const CMap& cmap) {

2483

2480

        Parent::operator=(cmap);

2484

2481

        return *this;

};

    template <typename V>

2490

2487

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

2491

2488

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

    public:

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

2496

2493

        : Parent(*adapter._graph) { }

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

2499

2496

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

    private:

2502

2499

      ArcMap& operator=(const ArcMap& cmap) {

2503

2500

        return operator=<ArcMap>(cmap);

      template <typename CMap>

2507

2504

      ArcMap& operator=(const CMap& cmap) {

2508

2505

        Parent::operator=(cmap);

2509

2506

        return *this;

};

  protected:

2516

2513

    Graph* _graph;

2517

2514

    DM* _direction;

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

2520

2517

      _graph = &graph;

2521

2518

      _direction = &direction;

};

  /// \ingroup graph_adaptors

2527

2524

///

2528

2525

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

2529

2526

///

2530

2527

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

2531

2528

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

2532

2529

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

2533

2530

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

2534

2531

  /// of the adaptor.

2535

2532

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

2536

2533

///

2537

2534

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

2538

2535

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

2539

2536

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

2540

2537

///

2541

2538

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

2542

2539

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

2543

2540

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

2544

2541

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

2545

2542

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

2546

2543

  /// adapted graph. The default type is

2547

2544

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

2548

2545

///

2549

2546

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

2550

2547

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

2551

2548

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

2552

2549

  /// each other.

2553

2550

#ifdef DOXYGEN

2554

2551

  template<typename GR,

2555

2552

           typename DM>

2556

2553

  class Orienter {

2557

2554

#else

2558

2555

  template<typename GR,

2559

2556

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

2560

2557

  class Orienter :

2561

2558

    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {

2562

2559

#endif

2563

2560

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

2564

2561

  public:

    /// The type of the adapted graph.

2567

2564

    typedef GR Graph;

2568

2565

    /// The type of the direction edge map.

2569

2566

    typedef DM DirectionMap;

    typedef typename Parent::Arc Arc;

  protected:

2574

2571

    Orienter() { }

  public:

    /// \brief Constructor

2579

2576

///

2580

2577

    /// Constructor of the adaptor.

2581

2578

    Orienter(GR& graph, DM& direction) {

2582

2579

      Parent::initialize(graph, direction);

    /// \brief Reverses the given arc

2586

2583

///

2587

2584

    /// This function reverses the given arc.

2588

2585

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

2589

2586

    /// in the direction map.

2590

2587

    void reverseArc(const Arc& a) {

2591

2588

      Parent::reverseArc(a);

};

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

2596

2593

///

2597

2594

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

2598

2595

  /// \ingroup graph_adaptors

2599

2596

  /// \relates Orienter

2600

2597

  template<typename GR, typename DM>

2601

2598

  Orienter<const GR, DM>

2602

2599

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

2603

2600

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

  template<typename GR, typename DM>

2607

2604

  Orienter<const GR, const DM>

2608

2605

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

2609

2606

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

  namespace _adaptor_bits {

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

2615

2612

    class ResForwardFilter {

2616

2613

    public:

      typedef typename DGR::Arc Key;

2619

2616

      typedef bool Value;

    private:

      const CM* _capacity;

2624

2621

      const FM* _flow;

2625

2622

      TL _tolerance;

    public:

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

2630

2627

                       const TL& tolerance = TL())

2631

2628

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

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

2634

2631

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

};

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

2639

2636

    class ResBackwardFilter {

2640

2637

    public:

      typedef typename DGR::Arc Key;

2643

2640

      typedef bool Value;

    private:

      const CM* _capacity;

2648

2645

      const FM* _flow;

2649

2646

      TL _tolerance;

    public:

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

2654

2651

                        const TL& tolerance = TL())

2655

2652

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

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

2658

2655

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

};

  /// \ingroup graph_adaptors

2665

2662

///

2666

2663

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

2667

2664

  /// flow and circulation problems.

2668

2665

///

2669

2666

  /// ResidualDigraph can be used for composing the \e residual digraph

2670

2667

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

2671

2668

  /// be a directed graph and let \f$ F \f$ be a number type.

2672

2669

  /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.

2673

2670

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

2674

2671

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

2675

2672

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

2676

2673

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

2677

2674

  /// called residual digraph.

2678

2675

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

2679

2676

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

2680

2677

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

2681

2678

  /// arcs).

2682

2679

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

2683

2680

///

2684

2681

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

2685

2682

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

2686

2683

  /// It is implicitly \c const.

2687

2684

  /// \tparam CM The type of the capacity map.

2688

2685

  /// It must be an arc map of some numerical type, which defines

2689

2686

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

2690

2687

  /// The default type is

2691

2688

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

2692

2689

  /// \tparam FM The type of the flow map.

2693

2690

  /// It must be an arc map of some numerical type, which defines

2694

2691

  /// the flow values in the flow problem. The default type is \c CM.

2695

2692

  /// \tparam TL The tolerance type for handling inexact computation.

2696

2693

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

2697

2694

  /// capacity map.

2698

2695

///

2699

2696

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

2700

2697

  /// adaptors.

2701

2698

///

2702

2699

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

2703

2700

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

2704

2701

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

2705

2702

#ifdef DOXYGEN

2706

2703

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

2707

2704

  class ResidualDigraph

2708

2705

#else

2709

2706

  template<typename DGR,

2710

2707

           typename CM = typename DGR::template ArcMap<int>,

2711

2708

           typename FM = CM,

2712

2709

           typename TL = Tolerance<typename CM::Value> >

2713

2710

  class ResidualDigraph

2714

2711

    : public SubDigraph<

2715

2712

        Undirector<const DGR>,

2716

2713

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

2717

2714

        typename Undirector<const DGR>::template CombinedArcMap<

2718

2715

          _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,

2719

2716

          _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >

2720

2717

#endif

  public:

    /// The type of the underlying digraph.

2725

2722

    typedef DGR Digraph;

2726

2723

    /// The type of the capacity map.

2727

2724

    typedef CM CapacityMap;

2728

2725

    /// The type of the flow map.

2729

2726

    typedef FM FlowMap;

2730

2727

    /// The tolerance type.

2731

2728

    typedef TL Tolerance;

    typedef typename CapacityMap::Value Value;

2734

2731

    typedef ResidualDigraph Adaptor;

  protected:

    typedef Undirector<const Digraph> Undirected;

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

    typedef _adaptor_bits::ResForwardFilter<const DGR, CM,

2743

2740

                                            FM, TL> ForwardFilter;

    typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,

2746

2743

                                             FM, TL> BackwardFilter;

    typedef typename Undirected::

2749

2746

      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;

    typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;

    const CapacityMap* _capacity;

2754

2751

    FlowMap* _flow;

2755

2752

RhodeCode

Login to your account