LEMON/LEMON-official Changeset - r435:9afe81e4c543

@@ -17,6 +17,6 @@

17

*/

18

19

#ifndef LEMON_TOPOLOGY_H

20

#define LEMON_TOPOLOGY_H

19

#ifndef LEMON_CONNECTIVITY_H

20

#define LEMON_CONNECTIVITY_H

21

22

#include <lemon/dfs.h>

...

@@ -155,5 +155,5 @@

155

156

157

  namespace _topology_bits {

157

  namespace _connectivity_bits {

158

159

    template <typename Digraph, typename Iterator >

...

@@ -189,17 +189,17 @@

189

190

    template <typename Digraph, typename ArcMap>

191

    struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {

191

    struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {

192

    public:

193

      typedef typename Digraph::Node Node;

194

      typedef typename Digraph::Arc Arc;

195

196

      StronglyConnectedCutEdgesVisitor(const Digraph& digraph,

197

                                       ArcMap& cutMap,

198

                                       int& cutNum)

196

      StronglyConnectedCutArcsVisitor(const Digraph& digraph,

197

                                      ArcMap& cutMap,

198

                                      int& cutNum)

199

        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),

200

          _compMap(digraph), _num(0) {

200

          _compMap(digraph, -1), _num(-1) {

201

202

203

      void stop(const Node&) {

203

      void start(const Node&) {

204

        ++_num;

205

...

@@ -249,5 +249,5 @@

249

    if (source == INVALID) return true;

250

251

    using namespace _topology_bits;

251

    using namespace _connectivity_bits;

252

253

    typedef DfsVisitor<Digraph> Visitor;

...

@@ -266,4 +266,5 @@

266

267

    typedef ReverseDigraph<const Digraph> RDigraph;

268

    typedef typename RDigraph::NodeIt RNodeIt;

268

269

    RDigraph rdigraph(digraph);

269

270

...

@@ -276,5 +277,5 @@

276

277

    rdfs.start();

277

278

    for (NodeIt it(rdigraph); it != INVALID; ++it) {

279

    for (RNodeIt it(rdigraph); it != INVALID; ++it) {

279

280

      if (!rdfs.reached(it)) {

280

281

        return false;

...

@@ -303,5 +304,5 @@

303

304

    checkConcept<concepts::Digraph, Digraph>();

304

305

    using namespace _topology_bits;

306

    using namespace _connectivity_bits;

306

307

308

    typedef typename Digraph::Node Node;

...

@@ -375,5 +376,5 @@

375

376

    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();

376

377

    using namespace _topology_bits;

378

    using namespace _connectivity_bits;

378

379

380

    typedef std::vector<Node> Container;

...

@@ -439,5 +440,5 @@

439

440

    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();

440

441

    using namespace _topology_bits;

442

    using namespace _connectivity_bits;

442

443

444

    typedef std::vector<Node> Container;

...

@@ -464,5 +465,5 @@

464

465

    int cutNum = 0;

465

466

    typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;

467

    typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;

467

468

    RVisitor rvisitor(rgraph, cutMap, cutNum);

468

469

...

@@ -479,5 +480,5 @@

479

480

481

  namespace _topology_bits {

482

  namespace _connectivity_bits {

482

483

484

    template <typename Digraph>

...

@@ -731,5 +732,5 @@

731

732

    typedef typename Graph::NodeIt NodeIt;

732

733

    using namespace _topology_bits;

734

    using namespace _connectivity_bits;

734

735

736

    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;

...

@@ -774,5 +775,5 @@

774

775

    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();

775

776

    using namespace _topology_bits;

777

    using namespace _connectivity_bits;

777

778

779

    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;

...

@@ -814,5 +815,5 @@

814

815

    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();

815

816

    using namespace _topology_bits;

817

    using namespace _connectivity_bits;

817

818

819

    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;

...

@@ -833,5 +834,5 @@

833

834

835

  namespace _topology_bits {

836

  namespace _connectivity_bits {

836

837

838

    template <typename Digraph>

...

@@ -1054,5 +1055,5 @@

1054

1055

    typedef typename Graph::NodeIt NodeIt;

1055

1056

    using namespace _topology_bits;

1057

    using namespace _connectivity_bits;

1057

1058

1059

    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;

...

@@ -1096,5 +1097,5 @@

1096

1097

    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();

1097

1098

    using namespace _topology_bits;

1099

    using namespace _connectivity_bits;

1099

1100

1101

    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;

...

@@ -1137,5 +1138,5 @@

1137

1138

    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();

1138

1139

    using namespace _topology_bits;

1140

    using namespace _connectivity_bits;

1140

1141

1142

    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;

...

@@ -1157,5 +1158,5 @@

1157

1158

1159

  namespace _topology_bits {

1160

  namespace _connectivity_bits {

1160

1161

1162

    template <typename Digraph, typename IntNodeMap>

...

@@ -1194,5 +1195,5 @@

1194

1195

  template <typename Digraph, typename NodeMap>

1195

1196

  void topologicalSort(const Digraph& graph, NodeMap& order) {

1196

    using namespace _topology_bits;

1197

    using namespace _connectivity_bits;

1197

1198

1199

    checkConcept<concepts::Digraph, Digraph>();

...

@@ -1235,6 +1236,6 @@

1235

1236

  /// \see dag

1236

1237

  template <typename Digraph, typename NodeMap>

1237

  bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) {

1238

    using namespace _topology_bits;

1238

  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {

1239

    using namespace _connectivity_bits;

1239

1240

1241

    checkConcept<concepts::Digraph, Digraph>();

...

@@ -1246,19 +1247,21 @@

1246

1247

    typedef typename Digraph::Arc Arc;

1247

1248

    order = constMap<Node, int, -1>();

1249

    for (NodeIt it(digraph); it != INVALID; ++it) {

1250

      order.set(it, -1);

    TopologicalSortVisitor<Digraph, NodeMap>

1251

      visitor(order, countNodes(graph));

1254

      visitor(order, countNodes(digraph));

    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >

1254

      dfs(graph, visitor);

1257

      dfs(digraph, visitor);

    dfs.init();

1257

    for (NodeIt it(graph); it != INVALID; ++it) {

1260

    for (NodeIt it(digraph); it != INVALID; ++it) {

1258

1261

      if (!dfs.reached(it)) {

1259

1262

        dfs.addSource(it);

1260

1263

        while (!dfs.emptyQueue()) {

1261

           Arc edge = dfs.nextArc();

1262

           Node target = graph.target(edge);

1264

           Arc arc = dfs.nextArc();

1265

           Node target = digraph.target(arc);

1263

1266

           if (dfs.reached(target) && order[target] == -1) {

1264

1267

             return false;

...

@@ -1280,5 +1283,5 @@

1280

1283

  /// \see acyclic

1281

1284

  template <typename Digraph>

1282

  bool dag(const Digraph& graph) {

1285

  bool dag(const Digraph& digraph) {

    checkConcept<concepts::Digraph, Digraph>();

...

@@ -1291,16 +1294,16 @@

    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::

1293

      Create dfs(graph);

1296

      Create dfs(digraph);

1294

1297

1295

    ProcessedMap processed(graph);

1298

    ProcessedMap processed(digraph);

1296

1299

    dfs.processedMap(processed);

    dfs.init();

1299

    for (NodeIt it(graph); it != INVALID; ++it) {

1302

    for (NodeIt it(digraph); it != INVALID; ++it) {

1300

1303

      if (!dfs.reached(it)) {

1301

1304

        dfs.addSource(it);

1302

1305

        while (!dfs.emptyQueue()) {

1303

1306

          Arc edge = dfs.nextArc();

1304

          Node target = graph.target(edge);

1307

          Node target = digraph.target(edge);

1305

1308

          if (dfs.reached(target) && !processed[target]) {

1306

1309

            return false;

...

@@ -1381,5 +1384,5 @@

  namespace _topology_bits {

1386

  namespace _connectivity_bits {

    template <typename Digraph>

...

@@ -1450,5 +1453,5 @@

1450

1453

  template<typename Graph>

1451

1454

  inline bool bipartite(const Graph &graph){

1452

    using namespace _topology_bits;

1455

    using namespace _connectivity_bits;

    checkConcept<concepts::Graph, Graph>();

...

@@ -1490,5 +1493,5 @@

1490

1493

  template<typename Graph, typename NodeMap>

1491

1494

  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){

1492

    using namespace _topology_bits;

1495

    using namespace _connectivity_bits;

    checkConcept<concepts::Graph, Graph>();

...

@@ -1521,7 +1524,7 @@

1521

1524

  /// Returns true when there are not loop edges in the graph.

1522

1525

  template <typename Digraph>

1523

  bool loopFree(const Digraph& graph) {

1524

    for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) {

1525

      if (graph.source(it) == graph.target(it)) return false;

1526

  bool loopFree(const Digraph& digraph) {

1527

    for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {

1528

      if (digraph.source(it) == digraph.target(it)) return false;

    return true;

...

@@ -1532,13 +1535,13 @@

1532

1535

  /// Returns true when there are not parallel edges in the graph.

1533

1536

  template <typename Digraph>

1534

  bool parallelFree(const Digraph& graph) {

1535

    typename Digraph::template NodeMap<bool> reached(graph, false);

1536

    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {

1537

      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {

1538

        if (reached[graph.target(e)]) return false;

1539

        reached.set(graph.target(e), true);

1537

  bool parallelFree(const Digraph& digraph) {

1538

    typename Digraph::template NodeMap<bool> reached(digraph, false);

1539

    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {

1540

      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {

1541

        if (reached[digraph.target(a)]) return false;

1542

        reached.set(digraph.target(a), true);

1540

1543

1541

      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {

1542

        reached.set(graph.target(e), false);

1544

      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {

1545

        reached.set(digraph.target(a), false);

@@ -1552,14 +1555,14 @@

1552

1555

  /// the graph.

1553

1556

  template <typename Digraph>

1554

  bool simpleDigraph(const Digraph& graph) {

1555

    typename Digraph::template NodeMap<bool> reached(graph, false);

1556

    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {

1557

  bool simpleDigraph(const Digraph& digraph) {

1558

    typename Digraph::template NodeMap<bool> reached(digraph, false);

1559

    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {

1557

1560

      reached.set(n, true);

1558

      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {

1559

        if (reached[graph.target(e)]) return false;

1560

        reached.set(graph.target(e), true);

1561

      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {

1562

        if (reached[digraph.target(a)]) return false;

1563

        reached.set(digraph.target(a), true);

1561

1564

1562

      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {

1563

        reached.set(graph.target(e), false);

1565

      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {

1566

        reached.set(digraph.target(a), false);

      reached.set(n, false);

...

@@ -1570,3 +1573,3 @@

1570

1573

} //namespace lemon

1571

1574

1572

#endif //LEMON_TOPOLOGY_H

1575

#endif //LEMON_CONNECTIVITY_H

...	...	@@ -1411,4 +1411,5 @@
1411	1411	} else {
1412	1412	_visitor->leave(s);
	1413	_visitor->stop(s);
1413	1414	}
1414	1415	}

RhodeCode

Login to your account