lemon/edge_set.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 16 Oct 2009 09:50:18 +0200
changeset 772 f964a00b9068
parent 660 d9cf3b5858ae
child 778 a143f19f465b
permissions -rw-r--r--
Small fix in the doc (#179)
deba@468
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@468
     2
 *
deba@468
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@468
     4
 *
deba@468
     5
 * Copyright (C) 2003-2008
deba@468
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@468
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@468
     8
 *
deba@468
     9
 * Permission to use, modify and distribute this software is granted
deba@468
    10
 * provided that this copyright notice appears in all copies. For
deba@468
    11
 * precise terms see the accompanying LICENSE file.
deba@468
    12
 *
deba@468
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@468
    14
 * express or implied, and with no claim as to its suitability for any
deba@468
    15
 * purpose.
deba@468
    16
 *
deba@468
    17
 */
deba@468
    18
deba@468
    19
#ifndef LEMON_EDGE_SET_H
deba@468
    20
#define LEMON_EDGE_SET_H
deba@468
    21
deba@468
    22
#include <lemon/core.h>
deba@468
    23
#include <lemon/bits/edge_set_extender.h>
deba@468
    24
kpeter@660
    25
/// \ingroup graphs
deba@468
    26
/// \file
deba@468
    27
/// \brief ArcSet and EdgeSet classes.
deba@468
    28
///
deba@468
    29
/// Graphs which use another graph's node-set as own.
deba@468
    30
namespace lemon {
deba@468
    31
deba@512
    32
  template <typename GR>
deba@468
    33
  class ListArcSetBase {
deba@468
    34
  public:
deba@468
    35
deba@512
    36
    typedef typename GR::Node Node;
deba@512
    37
    typedef typename GR::NodeIt NodeIt;
deba@468
    38
deba@468
    39
  protected:
deba@468
    40
deba@468
    41
    struct NodeT {
deba@468
    42
      int first_out, first_in;
deba@468
    43
      NodeT() : first_out(-1), first_in(-1) {}
deba@468
    44
    };
deba@468
    45
deba@512
    46
    typedef typename ItemSetTraits<GR, Node>::
deba@468
    47
    template Map<NodeT>::Type NodesImplBase;
deba@468
    48
deba@512
    49
    NodesImplBase* _nodes;
deba@468
    50
deba@468
    51
    struct ArcT {
deba@468
    52
      Node source, target;
deba@468
    53
      int next_out, next_in;
deba@468
    54
      int prev_out, prev_in;
deba@468
    55
      ArcT() : prev_out(-1), prev_in(-1) {}
deba@468
    56
    };
deba@468
    57
deba@468
    58
    std::vector<ArcT> arcs;
deba@468
    59
deba@468
    60
    int first_arc;
deba@468
    61
    int first_free_arc;
deba@468
    62
deba@512
    63
    const GR* _graph;
deba@468
    64
deba@512
    65
    void initalize(const GR& graph, NodesImplBase& nodes) {
deba@512
    66
      _graph = &graph;
deba@512
    67
      _nodes = &nodes;
deba@468
    68
    }
deba@468
    69
deba@468
    70
  public:
deba@468
    71
deba@468
    72
    class Arc {
deba@512
    73
      friend class ListArcSetBase<GR>;
deba@468
    74
    protected:
deba@468
    75
      Arc(int _id) : id(_id) {}
deba@468
    76
      int id;
deba@468
    77
    public:
deba@468
    78
      Arc() {}
deba@468
    79
      Arc(Invalid) : id(-1) {}
deba@468
    80
      bool operator==(const Arc& arc) const { return id == arc.id; }
deba@468
    81
      bool operator!=(const Arc& arc) const { return id != arc.id; }
deba@468
    82
      bool operator<(const Arc& arc) const { return id < arc.id; }
deba@468
    83
    };
deba@468
    84
deba@468
    85
    ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
deba@468
    86
kpeter@670
    87
    Node addNode() {
kpeter@670
    88
      LEMON_ASSERT(false,
kpeter@670
    89
        "This graph structure does not support node insertion");
kpeter@670
    90
      return INVALID; // avoid warning
kpeter@670
    91
    }
kpeter@670
    92
deba@468
    93
    Arc addArc(const Node& u, const Node& v) {
deba@468
    94
      int n;
deba@468
    95
      if (first_free_arc == -1) {
deba@468
    96
        n = arcs.size();
deba@468
    97
        arcs.push_back(ArcT());
deba@468
    98
      } else {
deba@468
    99
        n = first_free_arc;
deba@468
   100
        first_free_arc = arcs[first_free_arc].next_in;
deba@468
   101
      }
deba@512
   102
      arcs[n].next_in = (*_nodes)[v].first_in;
deba@512
   103
      if ((*_nodes)[v].first_in != -1) {
deba@512
   104
        arcs[(*_nodes)[v].first_in].prev_in = n;
deba@468
   105
      }
deba@512
   106
      (*_nodes)[v].first_in = n;
deba@512
   107
      arcs[n].next_out = (*_nodes)[u].first_out;
deba@512
   108
      if ((*_nodes)[u].first_out != -1) {
deba@512
   109
        arcs[(*_nodes)[u].first_out].prev_out = n;
deba@468
   110
      }
deba@512
   111
      (*_nodes)[u].first_out = n;
deba@468
   112
      arcs[n].source = u;
deba@468
   113
      arcs[n].target = v;
deba@468
   114
      return Arc(n);
deba@468
   115
    }
deba@468
   116
deba@468
   117
    void erase(const Arc& arc) {
deba@468
   118
      int n = arc.id;
deba@468
   119
      if (arcs[n].prev_in != -1) {
deba@468
   120
        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
deba@468
   121
      } else {
deba@512
   122
        (*_nodes)[arcs[n].target].first_in = arcs[n].next_in;
deba@468
   123
      }
deba@468
   124
      if (arcs[n].next_in != -1) {
deba@468
   125
        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
deba@468
   126
      }
deba@468
   127
deba@468
   128
      if (arcs[n].prev_out != -1) {
deba@468
   129
        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
deba@468
   130
      } else {
deba@512
   131
        (*_nodes)[arcs[n].source].first_out = arcs[n].next_out;
deba@468
   132
      }
deba@468
   133
      if (arcs[n].next_out != -1) {
deba@468
   134
        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
deba@468
   135
      }
deba@468
   136
deba@468
   137
    }
deba@468
   138
deba@468
   139
    void clear() {
deba@468
   140
      Node node;
deba@468
   141
      for (first(node); node != INVALID; next(node)) {
deba@512
   142
        (*_nodes)[node].first_in = -1;
deba@512
   143
        (*_nodes)[node].first_out = -1;
deba@468
   144
      }
deba@468
   145
      arcs.clear();
deba@468
   146
      first_arc = -1;
deba@468
   147
      first_free_arc = -1;
deba@468
   148
    }
deba@468
   149
deba@468
   150
    void first(Node& node) const {
deba@512
   151
      _graph->first(node);
deba@468
   152
    }
deba@468
   153
deba@468
   154
    void next(Node& node) const {
deba@512
   155
      _graph->next(node);
deba@468
   156
    }
deba@468
   157
deba@468
   158
    void first(Arc& arc) const {
deba@468
   159
      Node node;
deba@468
   160
      first(node);
deba@512
   161
      while (node != INVALID && (*_nodes)[node].first_in == -1) {
deba@468
   162
        next(node);
deba@468
   163
      }
deba@512
   164
      arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
deba@468
   165
    }
deba@468
   166
deba@468
   167
    void next(Arc& arc) const {
deba@468
   168
      if (arcs[arc.id].next_in != -1) {
deba@468
   169
        arc.id = arcs[arc.id].next_in;
deba@468
   170
      } else {
deba@468
   171
        Node node = arcs[arc.id].target;
deba@468
   172
        next(node);
deba@512
   173
        while (node != INVALID && (*_nodes)[node].first_in == -1) {
deba@468
   174
          next(node);
deba@468
   175
        }
deba@512
   176
        arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
deba@468
   177
      }
deba@468
   178
    }
deba@468
   179
deba@468
   180
    void firstOut(Arc& arc, const Node& node) const {
deba@512
   181
      arc.id = (*_nodes)[node].first_out;
deba@468
   182
    }
deba@468
   183
deba@468
   184
    void nextOut(Arc& arc) const {
deba@468
   185
      arc.id = arcs[arc.id].next_out;
deba@468
   186
    }
deba@468
   187
deba@468
   188
    void firstIn(Arc& arc, const Node& node) const {
deba@512
   189
      arc.id = (*_nodes)[node].first_in;
deba@468
   190
    }
deba@468
   191
deba@468
   192
    void nextIn(Arc& arc) const {
deba@468
   193
      arc.id = arcs[arc.id].next_in;
deba@468
   194
    }
deba@468
   195
deba@512
   196
    int id(const Node& node) const { return _graph->id(node); }
deba@468
   197
    int id(const Arc& arc) const { return arc.id; }
deba@468
   198
deba@512
   199
    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
deba@468
   200
    Arc arcFromId(int ix) const { return Arc(ix); }
deba@468
   201
deba@512
   202
    int maxNodeId() const { return _graph->maxNodeId(); };
deba@468
   203
    int maxArcId() const { return arcs.size() - 1; }
deba@468
   204
deba@468
   205
    Node source(const Arc& arc) const { return arcs[arc.id].source;}
deba@468
   206
    Node target(const Arc& arc) const { return arcs[arc.id].target;}
deba@468
   207
deba@512
   208
    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
deba@468
   209
deba@468
   210
    NodeNotifier& notifier(Node) const {
deba@512
   211
      return _graph->notifier(Node());
deba@468
   212
    }
deba@468
   213
deba@512
   214
    template <typename V>
deba@512
   215
    class NodeMap : public GR::template NodeMap<V> {
kpeter@617
   216
      typedef typename GR::template NodeMap<V> Parent;
kpeter@617
   217
deba@468
   218
    public:
deba@468
   219
deba@512
   220
      explicit NodeMap(const ListArcSetBase<GR>& arcset)
deba@512
   221
        : Parent(*arcset._graph) {}
deba@468
   222
deba@512
   223
      NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
deba@512
   224
        : Parent(*arcset._graph, value) {}
deba@468
   225
deba@468
   226
      NodeMap& operator=(const NodeMap& cmap) {
deba@468
   227
        return operator=<NodeMap>(cmap);
deba@468
   228
      }
deba@468
   229
deba@468
   230
      template <typename CMap>
deba@468
   231
      NodeMap& operator=(const CMap& cmap) {
deba@468
   232
        Parent::operator=(cmap);
deba@468
   233
        return *this;
deba@468
   234
      }
deba@468
   235
    };
deba@468
   236
deba@468
   237
  };
deba@468
   238
kpeter@660
   239
  /// \ingroup graphs
deba@468
   240
  ///
deba@468
   241
  /// \brief Digraph using a node set of another digraph or graph and
deba@468
   242
  /// an own arc set.
deba@468
   243
  ///
deba@468
   244
  /// This structure can be used to establish another directed graph
deba@468
   245
  /// over a node set of an existing one. This class uses the same
deba@468
   246
  /// Node type as the underlying graph, and each valid node of the
deba@468
   247
  /// original graph is valid in this arc set, therefore the node
deba@468
   248
  /// objects of the original graph can be used directly with this
deba@468
   249
  /// class. The node handling functions (id handling, observing, and
deba@468
   250
  /// iterators) works equivalently as in the original graph.
deba@468
   251
  ///
deba@468
   252
  /// This implementation is based on doubly-linked lists, from each
deba@468
   253
  /// node the outgoing and the incoming arcs make up lists, therefore
deba@468
   254
  /// one arc can be erased in constant time. It also makes possible,
deba@468
   255
  /// that node can be removed from the underlying graph, in this case
deba@468
   256
  /// all arcs incident to the given node is erased from the arc set.
deba@468
   257
  ///
deba@512
   258
  /// \param GR The type of the graph which shares its node set with
deba@468
   259
  /// this class. Its interface must conform to the
deba@468
   260
  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
deba@468
   261
  /// concept.
deba@468
   262
  ///
kpeter@559
   263
  /// This class fully conforms to the \ref concepts::Digraph
deba@468
   264
  /// "Digraph" concept.
deba@512
   265
  template <typename GR>
deba@512
   266
  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
kpeter@617
   267
    typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
deba@468
   268
deba@468
   269
  public:
deba@468
   270
deba@468
   271
    typedef typename Parent::Node Node;
deba@468
   272
    typedef typename Parent::Arc Arc;
deba@468
   273
deba@468
   274
    typedef typename Parent::NodesImplBase NodesImplBase;
deba@468
   275
deba@468
   276
    void eraseNode(const Node& node) {
deba@468
   277
      Arc arc;
deba@468
   278
      Parent::firstOut(arc, node);
deba@468
   279
      while (arc != INVALID ) {
deba@468
   280
        erase(arc);
deba@468
   281
        Parent::firstOut(arc, node);
deba@468
   282
      }
deba@468
   283
deba@468
   284
      Parent::firstIn(arc, node);
deba@468
   285
      while (arc != INVALID ) {
deba@468
   286
        erase(arc);
deba@468
   287
        Parent::firstIn(arc, node);
deba@468
   288
      }
deba@468
   289
    }
deba@468
   290
deba@468
   291
    void clearNodes() {
deba@468
   292
      Parent::clear();
deba@468
   293
    }
deba@468
   294
deba@468
   295
    class NodesImpl : public NodesImplBase {
deba@468
   296
      typedef NodesImplBase Parent;
deba@468
   297
kpeter@617
   298
    public:
deba@512
   299
      NodesImpl(const GR& graph, ListArcSet& arcset)
deba@468
   300
        : Parent(graph), _arcset(arcset) {}
deba@468
   301
deba@468
   302
      virtual ~NodesImpl() {}
deba@468
   303
deba@468
   304
    protected:
deba@468
   305
deba@468
   306
      virtual void erase(const Node& node) {
deba@468
   307
        _arcset.eraseNode(node);
deba@468
   308
        Parent::erase(node);
deba@468
   309
      }
deba@468
   310
      virtual void erase(const std::vector<Node>& nodes) {
deba@468
   311
        for (int i = 0; i < int(nodes.size()); ++i) {
deba@468
   312
          _arcset.eraseNode(nodes[i]);
deba@468
   313
        }
deba@468
   314
        Parent::erase(nodes);
deba@468
   315
      }
deba@468
   316
      virtual void clear() {
deba@468
   317
        _arcset.clearNodes();
deba@468
   318
        Parent::clear();
deba@468
   319
      }
deba@468
   320
deba@468
   321
    private:
deba@468
   322
      ListArcSet& _arcset;
deba@468
   323
    };
deba@468
   324
deba@512
   325
    NodesImpl _nodes;
deba@468
   326
deba@468
   327
  public:
deba@468
   328
deba@468
   329
    /// \brief Constructor of the ArcSet.
deba@468
   330
    ///
deba@468
   331
    /// Constructor of the ArcSet.
deba@512
   332
    ListArcSet(const GR& graph) : _nodes(graph, *this) {
deba@512
   333
      Parent::initalize(graph, _nodes);
deba@468
   334
    }
deba@468
   335
deba@468
   336
    /// \brief Add a new arc to the digraph.
deba@468
   337
    ///
deba@468
   338
    /// Add a new arc to the digraph with source node \c s
deba@468
   339
    /// and target node \c t.
kpeter@559
   340
    /// \return The new arc.
deba@468
   341
    Arc addArc(const Node& s, const Node& t) {
deba@468
   342
      return Parent::addArc(s, t);
deba@468
   343
    }
deba@468
   344
deba@468
   345
    /// \brief Erase an arc from the digraph.
deba@468
   346
    ///
deba@468
   347
    /// Erase an arc \c a from the digraph.
deba@468
   348
    void erase(const Arc& a) {
deba@468
   349
      return Parent::erase(a);
deba@468
   350
    }
deba@468
   351
deba@468
   352
  };
deba@468
   353
deba@512
   354
  template <typename GR>
deba@468
   355
  class ListEdgeSetBase {
deba@468
   356
  public:
deba@468
   357
deba@512
   358
    typedef typename GR::Node Node;
deba@512
   359
    typedef typename GR::NodeIt NodeIt;
deba@468
   360
deba@468
   361
  protected:
deba@468
   362
deba@468
   363
    struct NodeT {
deba@468
   364
      int first_out;
deba@468
   365
      NodeT() : first_out(-1) {}
deba@468
   366
    };
deba@468
   367
deba@512
   368
    typedef typename ItemSetTraits<GR, Node>::
deba@468
   369
    template Map<NodeT>::Type NodesImplBase;
deba@468
   370
deba@512
   371
    NodesImplBase* _nodes;
deba@468
   372
deba@468
   373
    struct ArcT {
deba@468
   374
      Node target;
deba@468
   375
      int prev_out, next_out;
deba@468
   376
      ArcT() : prev_out(-1), next_out(-1) {}
deba@468
   377
    };
deba@468
   378
deba@468
   379
    std::vector<ArcT> arcs;
deba@468
   380
deba@468
   381
    int first_arc;
deba@468
   382
    int first_free_arc;
deba@468
   383
deba@512
   384
    const GR* _graph;
deba@468
   385
deba@512
   386
    void initalize(const GR& graph, NodesImplBase& nodes) {
deba@512
   387
      _graph = &graph;
deba@512
   388
      _nodes = &nodes;
deba@468
   389
    }
deba@468
   390
deba@468
   391
  public:
deba@468
   392
deba@468
   393
    class Edge {
deba@468
   394
      friend class ListEdgeSetBase;
deba@468
   395
    protected:
deba@468
   396
deba@468
   397
      int id;
deba@468
   398
      explicit Edge(int _id) { id = _id;}
deba@468
   399
deba@468
   400
    public:
deba@468
   401
      Edge() {}
deba@468
   402
      Edge (Invalid) { id = -1; }
deba@468
   403
      bool operator==(const Edge& arc) const {return id == arc.id;}
deba@468
   404
      bool operator!=(const Edge& arc) const {return id != arc.id;}
deba@468
   405
      bool operator<(const Edge& arc) const {return id < arc.id;}
deba@468
   406
    };
deba@468
   407
deba@468
   408
    class Arc {
deba@468
   409
      friend class ListEdgeSetBase;
deba@468
   410
    protected:
deba@468
   411
      Arc(int _id) : id(_id) {}
deba@468
   412
      int id;
deba@468
   413
    public:
deba@468
   414
      operator Edge() const { return edgeFromId(id / 2); }
deba@468
   415
deba@468
   416
      Arc() {}
deba@468
   417
      Arc(Invalid) : id(-1) {}
deba@468
   418
      bool operator==(const Arc& arc) const { return id == arc.id; }
deba@468
   419
      bool operator!=(const Arc& arc) const { return id != arc.id; }
deba@468
   420
      bool operator<(const Arc& arc) const { return id < arc.id; }
deba@468
   421
    };
deba@468
   422
deba@468
   423
    ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
deba@468
   424
kpeter@670
   425
    Node addNode() {
kpeter@670
   426
      LEMON_ASSERT(false,
kpeter@670
   427
        "This graph structure does not support node insertion");
kpeter@670
   428
      return INVALID; // avoid warning
kpeter@670
   429
    }
kpeter@670
   430
deba@468
   431
    Edge addEdge(const Node& u, const Node& v) {
deba@468
   432
      int n;
deba@468
   433
deba@468
   434
      if (first_free_arc == -1) {
deba@468
   435
        n = arcs.size();
deba@468
   436
        arcs.push_back(ArcT());
deba@468
   437
        arcs.push_back(ArcT());
deba@468
   438
      } else {
deba@468
   439
        n = first_free_arc;
deba@468
   440
        first_free_arc = arcs[n].next_out;
deba@468
   441
      }
deba@468
   442
deba@468
   443
      arcs[n].target = u;
deba@468
   444
      arcs[n | 1].target = v;
deba@468
   445
deba@512
   446
      arcs[n].next_out = (*_nodes)[v].first_out;
deba@512
   447
      if ((*_nodes)[v].first_out != -1) {
deba@512
   448
        arcs[(*_nodes)[v].first_out].prev_out = n;
deba@468
   449
      }
deba@512
   450
      (*_nodes)[v].first_out = n;
deba@468
   451
      arcs[n].prev_out = -1;
deba@468
   452
deba@512
   453
      if ((*_nodes)[u].first_out != -1) {
deba@512
   454
        arcs[(*_nodes)[u].first_out].prev_out = (n | 1);
deba@468
   455
      }
deba@512
   456
      arcs[n | 1].next_out = (*_nodes)[u].first_out;
deba@512
   457
      (*_nodes)[u].first_out = (n | 1);
deba@468
   458
      arcs[n | 1].prev_out = -1;
deba@468
   459
deba@468
   460
      return Edge(n / 2);
deba@468
   461
    }
deba@468
   462
deba@468
   463
    void erase(const Edge& arc) {
deba@468
   464
      int n = arc.id * 2;
deba@468
   465
deba@468
   466
      if (arcs[n].next_out != -1) {
deba@468
   467
        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
deba@468
   468
      }
deba@468
   469
deba@468
   470
      if (arcs[n].prev_out != -1) {
deba@468
   471
        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
deba@468
   472
      } else {
deba@512
   473
        (*_nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
deba@468
   474
      }
deba@468
   475
deba@468
   476
      if (arcs[n | 1].next_out != -1) {
deba@468
   477
        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
deba@468
   478
      }
deba@468
   479
deba@468
   480
      if (arcs[n | 1].prev_out != -1) {
deba@468
   481
        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
deba@468
   482
      } else {
deba@512
   483
        (*_nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
deba@468
   484
      }
deba@468
   485
deba@468
   486
      arcs[n].next_out = first_free_arc;
deba@468
   487
      first_free_arc = n;
deba@468
   488
deba@468
   489
    }
deba@468
   490
deba@468
   491
    void clear() {
deba@468
   492
      Node node;
deba@468
   493
      for (first(node); node != INVALID; next(node)) {
deba@512
   494
        (*_nodes)[node].first_out = -1;
deba@468
   495
      }
deba@468
   496
      arcs.clear();
deba@468
   497
      first_arc = -1;
deba@468
   498
      first_free_arc = -1;
deba@468
   499
    }
deba@468
   500
deba@468
   501
    void first(Node& node) const {
deba@512
   502
      _graph->first(node);
deba@468
   503
    }
deba@468
   504
deba@468
   505
    void next(Node& node) const {
deba@512
   506
      _graph->next(node);
deba@468
   507
    }
deba@468
   508
deba@468
   509
    void first(Arc& arc) const {
deba@468
   510
      Node node;
deba@468
   511
      first(node);
deba@512
   512
      while (node != INVALID && (*_nodes)[node].first_out == -1) {
deba@468
   513
        next(node);
deba@468
   514
      }
deba@512
   515
      arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
deba@468
   516
    }
deba@468
   517
deba@468
   518
    void next(Arc& arc) const {
deba@468
   519
      if (arcs[arc.id].next_out != -1) {
deba@468
   520
        arc.id = arcs[arc.id].next_out;
deba@468
   521
      } else {
deba@468
   522
        Node node = arcs[arc.id ^ 1].target;
deba@468
   523
        next(node);
deba@512
   524
        while(node != INVALID && (*_nodes)[node].first_out == -1) {
deba@468
   525
          next(node);
deba@468
   526
        }
deba@512
   527
        arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
deba@468
   528
      }
deba@468
   529
    }
deba@468
   530
deba@468
   531
    void first(Edge& edge) const {
deba@468
   532
      Node node;
deba@468
   533
      first(node);
deba@468
   534
      while (node != INVALID) {
deba@512
   535
        edge.id = (*_nodes)[node].first_out;
deba@468
   536
        while ((edge.id & 1) != 1) {
deba@468
   537
          edge.id = arcs[edge.id].next_out;
deba@468
   538
        }
deba@468
   539
        if (edge.id != -1) {
deba@468
   540
          edge.id /= 2;
deba@468
   541
          return;
deba@468
   542
        }
deba@468
   543
        next(node);
deba@468
   544
      }
deba@468
   545
      edge.id = -1;
deba@468
   546
    }
deba@468
   547
deba@468
   548
    void next(Edge& edge) const {
deba@468
   549
      Node node = arcs[edge.id * 2].target;
deba@468
   550
      edge.id = arcs[(edge.id * 2) | 1].next_out;
deba@468
   551
      while ((edge.id & 1) != 1) {
deba@468
   552
        edge.id = arcs[edge.id].next_out;
deba@468
   553
      }
deba@468
   554
      if (edge.id != -1) {
deba@468
   555
        edge.id /= 2;
deba@468
   556
        return;
deba@468
   557
      }
deba@468
   558
      next(node);
deba@468
   559
      while (node != INVALID) {
deba@512
   560
        edge.id = (*_nodes)[node].first_out;
deba@468
   561
        while ((edge.id & 1) != 1) {
deba@468
   562
          edge.id = arcs[edge.id].next_out;
deba@468
   563
        }
deba@468
   564
        if (edge.id != -1) {
deba@468
   565
          edge.id /= 2;
deba@468
   566
          return;
deba@468
   567
        }
deba@468
   568
        next(node);
deba@468
   569
      }
deba@468
   570
      edge.id = -1;
deba@468
   571
    }
deba@468
   572
deba@468
   573
    void firstOut(Arc& arc, const Node& node) const {
deba@512
   574
      arc.id = (*_nodes)[node].first_out;
deba@468
   575
    }
deba@468
   576
deba@468
   577
    void nextOut(Arc& arc) const {
deba@468
   578
      arc.id = arcs[arc.id].next_out;
deba@468
   579
    }
deba@468
   580
deba@468
   581
    void firstIn(Arc& arc, const Node& node) const {
deba@512
   582
      arc.id = (((*_nodes)[node].first_out) ^ 1);
deba@468
   583
      if (arc.id == -2) arc.id = -1;
deba@468
   584
    }
deba@468
   585
deba@468
   586
    void nextIn(Arc& arc) const {
deba@468
   587
      arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
deba@468
   588
      if (arc.id == -2) arc.id = -1;
deba@468
   589
    }
deba@468
   590
deba@468
   591
    void firstInc(Edge &arc, bool& dir, const Node& node) const {
deba@512
   592
      int de = (*_nodes)[node].first_out;
deba@468
   593
      if (de != -1 ) {
deba@468
   594
        arc.id = de / 2;
deba@468
   595
        dir = ((de & 1) == 1);
deba@468
   596
      } else {
deba@468
   597
        arc.id = -1;
deba@468
   598
        dir = true;
deba@468
   599
      }
deba@468
   600
    }
deba@468
   601
    void nextInc(Edge &arc, bool& dir) const {
deba@468
   602
      int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
deba@468
   603
      if (de != -1 ) {
deba@468
   604
        arc.id = de / 2;
deba@468
   605
        dir = ((de & 1) == 1);
deba@468
   606
      } else {
deba@468
   607
        arc.id = -1;
deba@468
   608
        dir = true;
deba@468
   609
      }
deba@468
   610
    }
deba@468
   611
deba@468
   612
    static bool direction(Arc arc) {
deba@468
   613
      return (arc.id & 1) == 1;
deba@468
   614
    }
deba@468
   615
deba@468
   616
    static Arc direct(Edge edge, bool dir) {
deba@468
   617
      return Arc(edge.id * 2 + (dir ? 1 : 0));
deba@468
   618
    }
deba@468
   619
deba@512
   620
    int id(const Node& node) const { return _graph->id(node); }
deba@468
   621
    static int id(Arc e) { return e.id; }
deba@468
   622
    static int id(Edge e) { return e.id; }
deba@468
   623
deba@512
   624
    Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
deba@468
   625
    static Arc arcFromId(int id) { return Arc(id);}
deba@468
   626
    static Edge edgeFromId(int id) { return Edge(id);}
deba@468
   627
deba@512
   628
    int maxNodeId() const { return _graph->maxNodeId(); };
deba@468
   629
    int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@468
   630
    int maxArcId() const { return arcs.size()-1; }
deba@468
   631
deba@468
   632
    Node source(Arc e) const { return arcs[e.id ^ 1].target; }
deba@468
   633
    Node target(Arc e) const { return arcs[e.id].target; }
deba@468
   634
deba@468
   635
    Node u(Edge e) const { return arcs[2 * e.id].target; }
deba@468
   636
    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
deba@468
   637
deba@512
   638
    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
deba@468
   639
deba@468
   640
    NodeNotifier& notifier(Node) const {
deba@512
   641
      return _graph->notifier(Node());
deba@468
   642
    }
deba@468
   643
deba@512
   644
    template <typename V>
deba@512
   645
    class NodeMap : public GR::template NodeMap<V> {
kpeter@617
   646
      typedef typename GR::template NodeMap<V> Parent;
kpeter@617
   647
deba@468
   648
    public:
deba@468
   649
deba@512
   650
      explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
deba@512
   651
        : Parent(*arcset._graph) {}
deba@468
   652
deba@512
   653
      NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
deba@512
   654
        : Parent(*arcset._graph, value) {}
deba@468
   655
deba@468
   656
      NodeMap& operator=(const NodeMap& cmap) {
deba@468
   657
        return operator=<NodeMap>(cmap);
deba@468
   658
      }
deba@468
   659
deba@468
   660
      template <typename CMap>
deba@468
   661
      NodeMap& operator=(const CMap& cmap) {
deba@468
   662
        Parent::operator=(cmap);
deba@468
   663
        return *this;
deba@468
   664
      }
deba@468
   665
    };
deba@468
   666
deba@468
   667
  };
deba@468
   668
kpeter@660
   669
  /// \ingroup graphs
deba@468
   670
  ///
deba@468
   671
  /// \brief Graph using a node set of another digraph or graph and an
deba@468
   672
  /// own edge set.
deba@468
   673
  ///
deba@468
   674
  /// This structure can be used to establish another graph over a
deba@468
   675
  /// node set of an existing one. This class uses the same Node type
deba@468
   676
  /// as the underlying graph, and each valid node of the original
deba@468
   677
  /// graph is valid in this arc set, therefore the node objects of
deba@468
   678
  /// the original graph can be used directly with this class. The
deba@468
   679
  /// node handling functions (id handling, observing, and iterators)
deba@468
   680
  /// works equivalently as in the original graph.
deba@468
   681
  ///
deba@468
   682
  /// This implementation is based on doubly-linked lists, from each
deba@468
   683
  /// node the incident edges make up lists, therefore one edge can be
deba@468
   684
  /// erased in constant time. It also makes possible, that node can
deba@468
   685
  /// be removed from the underlying graph, in this case all edges
deba@468
   686
  /// incident to the given node is erased from the arc set.
deba@468
   687
  ///
deba@512
   688
  /// \param GR The type of the graph which shares its node set
deba@468
   689
  /// with this class. Its interface must conform to the
deba@468
   690
  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
deba@468
   691
  /// concept.
deba@468
   692
  ///
kpeter@559
   693
  /// This class fully conforms to the \ref concepts::Graph "Graph"
deba@468
   694
  /// concept.
deba@512
   695
  template <typename GR>
deba@512
   696
  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
kpeter@617
   697
    typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
deba@468
   698
deba@468
   699
  public:
deba@468
   700
deba@468
   701
    typedef typename Parent::Node Node;
deba@468
   702
    typedef typename Parent::Arc Arc;
deba@468
   703
    typedef typename Parent::Edge Edge;
deba@468
   704
deba@468
   705
    typedef typename Parent::NodesImplBase NodesImplBase;
deba@468
   706
deba@468
   707
    void eraseNode(const Node& node) {
deba@468
   708
      Arc arc;
deba@468
   709
      Parent::firstOut(arc, node);
deba@468
   710
      while (arc != INVALID ) {
deba@468
   711
        erase(arc);
deba@468
   712
        Parent::firstOut(arc, node);
deba@468
   713
      }
deba@468
   714
deba@468
   715
    }
deba@468
   716
deba@468
   717
    void clearNodes() {
deba@468
   718
      Parent::clear();
deba@468
   719
    }
deba@468
   720
deba@468
   721
    class NodesImpl : public NodesImplBase {
deba@468
   722
      typedef NodesImplBase Parent;
deba@468
   723
kpeter@617
   724
    public:
deba@512
   725
      NodesImpl(const GR& graph, ListEdgeSet& arcset)
deba@468
   726
        : Parent(graph), _arcset(arcset) {}
deba@468
   727
deba@468
   728
      virtual ~NodesImpl() {}
deba@468
   729
deba@468
   730
    protected:
deba@468
   731
deba@468
   732
      virtual void erase(const Node& node) {
deba@468
   733
        _arcset.eraseNode(node);
deba@468
   734
        Parent::erase(node);
deba@468
   735
      }
deba@468
   736
      virtual void erase(const std::vector<Node>& nodes) {
deba@468
   737
        for (int i = 0; i < int(nodes.size()); ++i) {
deba@468
   738
          _arcset.eraseNode(nodes[i]);
deba@468
   739
        }
deba@468
   740
        Parent::erase(nodes);
deba@468
   741
      }
deba@468
   742
      virtual void clear() {
deba@468
   743
        _arcset.clearNodes();
deba@468
   744
        Parent::clear();
deba@468
   745
      }
deba@468
   746
deba@468
   747
    private:
deba@468
   748
      ListEdgeSet& _arcset;
deba@468
   749
    };
deba@468
   750
deba@512
   751
    NodesImpl _nodes;
deba@468
   752
deba@468
   753
  public:
deba@468
   754
deba@468
   755
    /// \brief Constructor of the EdgeSet.
deba@468
   756
    ///
deba@468
   757
    /// Constructor of the EdgeSet.
deba@512
   758
    ListEdgeSet(const GR& graph) : _nodes(graph, *this) {
deba@512
   759
      Parent::initalize(graph, _nodes);
deba@468
   760
    }
deba@468
   761
deba@468
   762
    /// \brief Add a new edge to the graph.
deba@468
   763
    ///
deba@468
   764
    /// Add a new edge to the graph with node \c u
deba@468
   765
    /// and node \c v endpoints.
kpeter@559
   766
    /// \return The new edge.
deba@468
   767
    Edge addEdge(const Node& u, const Node& v) {
deba@468
   768
      return Parent::addEdge(u, v);
deba@468
   769
    }
deba@468
   770
deba@468
   771
    /// \brief Erase an edge from the graph.
deba@468
   772
    ///
deba@468
   773
    /// Erase the edge \c e from the graph.
deba@468
   774
    void erase(const Edge& e) {
deba@468
   775
      return Parent::erase(e);
deba@468
   776
    }
deba@468
   777
deba@468
   778
  };
deba@468
   779
deba@512
   780
  template <typename GR>
deba@468
   781
  class SmartArcSetBase {
deba@468
   782
  public:
deba@468
   783
kpeter@617
   784
    typedef typename GR::Node Node;
kpeter@617
   785
    typedef typename GR::NodeIt NodeIt;
deba@468
   786
deba@468
   787
  protected:
deba@468
   788
deba@468
   789
    struct NodeT {
deba@468
   790
      int first_out, first_in;
deba@468
   791
      NodeT() : first_out(-1), first_in(-1) {}
deba@468
   792
    };
deba@468
   793
deba@512
   794
    typedef typename ItemSetTraits<GR, Node>::
deba@468
   795
    template Map<NodeT>::Type NodesImplBase;
deba@468
   796
deba@512
   797
    NodesImplBase* _nodes;
deba@468
   798
deba@468
   799
    struct ArcT {
deba@468
   800
      Node source, target;
deba@468
   801
      int next_out, next_in;
deba@468
   802
      ArcT() {}
deba@468
   803
    };
deba@468
   804
deba@468
   805
    std::vector<ArcT> arcs;
deba@468
   806
deba@512
   807
    const GR* _graph;
deba@468
   808
deba@512
   809
    void initalize(const GR& graph, NodesImplBase& nodes) {
deba@512
   810
      _graph = &graph;
deba@512
   811
      _nodes = &nodes;
deba@468
   812
    }
deba@468
   813
deba@468
   814
  public:
deba@468
   815
deba@468
   816
    class Arc {
deba@512
   817
      friend class SmartArcSetBase<GR>;
deba@468
   818
    protected:
deba@468
   819
      Arc(int _id) : id(_id) {}
deba@468
   820
      int id;
deba@468
   821
    public:
deba@468
   822
      Arc() {}
deba@468
   823
      Arc(Invalid) : id(-1) {}
deba@468
   824
      bool operator==(const Arc& arc) const { return id == arc.id; }
deba@468
   825
      bool operator!=(const Arc& arc) const { return id != arc.id; }
deba@468
   826
      bool operator<(const Arc& arc) const { return id < arc.id; }
deba@468
   827
    };
deba@468
   828
deba@468
   829
    SmartArcSetBase() {}
deba@468
   830
kpeter@670
   831
    Node addNode() {
kpeter@670
   832
      LEMON_ASSERT(false,
kpeter@670
   833
        "This graph structure does not support node insertion");
kpeter@670
   834
      return INVALID; // avoid warning
kpeter@670
   835
    }
kpeter@670
   836
deba@468
   837
    Arc addArc(const Node& u, const Node& v) {
deba@468
   838
      int n = arcs.size();
deba@468
   839
      arcs.push_back(ArcT());
deba@512
   840
      arcs[n].next_in = (*_nodes)[v].first_in;
deba@512
   841
      (*_nodes)[v].first_in = n;
deba@512
   842
      arcs[n].next_out = (*_nodes)[u].first_out;
deba@512
   843
      (*_nodes)[u].first_out = n;
deba@468
   844
      arcs[n].source = u;
deba@468
   845
      arcs[n].target = v;
deba@468
   846
      return Arc(n);
deba@468
   847
    }
deba@468
   848
deba@468
   849
    void clear() {
deba@468
   850
      Node node;
deba@468
   851
      for (first(node); node != INVALID; next(node)) {
deba@512
   852
        (*_nodes)[node].first_in = -1;
deba@512
   853
        (*_nodes)[node].first_out = -1;
deba@468
   854
      }
deba@468
   855
      arcs.clear();
deba@468
   856
    }
deba@468
   857
deba@468
   858
    void first(Node& node) const {
deba@512
   859
      _graph->first(node);
deba@468
   860
    }
deba@468
   861
deba@468
   862
    void next(Node& node) const {
deba@512
   863
      _graph->next(node);
deba@468
   864
    }
deba@468
   865
deba@468
   866
    void first(Arc& arc) const {
deba@468
   867
      arc.id = arcs.size() - 1;
deba@468
   868
    }
deba@468
   869
deba@468
   870
    void next(Arc& arc) const {
deba@468
   871
      --arc.id;
deba@468
   872
    }
deba@468
   873
deba@468
   874
    void firstOut(Arc& arc, const Node& node) const {
deba@512
   875
      arc.id = (*_nodes)[node].first_out;
deba@468
   876
    }
deba@468
   877
deba@468
   878
    void nextOut(Arc& arc) const {
deba@468
   879
      arc.id = arcs[arc.id].next_out;
deba@468
   880
    }
deba@468
   881
deba@468
   882
    void firstIn(Arc& arc, const Node& node) const {
deba@512
   883
      arc.id = (*_nodes)[node].first_in;
deba@468
   884
    }
deba@468
   885
deba@468
   886
    void nextIn(Arc& arc) const {
deba@468
   887
      arc.id = arcs[arc.id].next_in;
deba@468
   888
    }
deba@468
   889
deba@512
   890
    int id(const Node& node) const { return _graph->id(node); }
deba@468
   891
    int id(const Arc& arc) const { return arc.id; }
deba@468
   892
deba@512
   893
    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
deba@468
   894
    Arc arcFromId(int ix) const { return Arc(ix); }
deba@468
   895
deba@512
   896
    int maxNodeId() const { return _graph->maxNodeId(); };
deba@468
   897
    int maxArcId() const { return arcs.size() - 1; }
deba@468
   898
deba@468
   899
    Node source(const Arc& arc) const { return arcs[arc.id].source;}
deba@468
   900
    Node target(const Arc& arc) const { return arcs[arc.id].target;}
deba@468
   901
deba@512
   902
    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
deba@468
   903
deba@468
   904
    NodeNotifier& notifier(Node) const {
deba@512
   905
      return _graph->notifier(Node());
deba@468
   906
    }
deba@468
   907
deba@512
   908
    template <typename V>
deba@512
   909
    class NodeMap : public GR::template NodeMap<V> {
kpeter@617
   910
      typedef typename GR::template NodeMap<V> Parent;
kpeter@617
   911
deba@468
   912
    public:
deba@468
   913
deba@512
   914
      explicit NodeMap(const SmartArcSetBase<GR>& arcset)
deba@512
   915
        : Parent(*arcset._graph) { }
deba@468
   916
deba@512
   917
      NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
deba@512
   918
        : Parent(*arcset._graph, value) { }
deba@468
   919
deba@468
   920
      NodeMap& operator=(const NodeMap& cmap) {
deba@468
   921
        return operator=<NodeMap>(cmap);
deba@468
   922
      }
deba@468
   923
deba@468
   924
      template <typename CMap>
deba@468
   925
      NodeMap& operator=(const CMap& cmap) {
deba@468
   926
        Parent::operator=(cmap);
deba@468
   927
        return *this;
deba@468
   928
      }
deba@468
   929
    };
deba@468
   930
deba@468
   931
  };
deba@468
   932
deba@468
   933
kpeter@660
   934
  /// \ingroup graphs
deba@468
   935
  ///
deba@468
   936
  /// \brief Digraph using a node set of another digraph or graph and
deba@468
   937
  /// an own arc set.
deba@468
   938
  ///
deba@468
   939
  /// This structure can be used to establish another directed graph
deba@468
   940
  /// over a node set of an existing one. This class uses the same
deba@468
   941
  /// Node type as the underlying graph, and each valid node of the
deba@468
   942
  /// original graph is valid in this arc set, therefore the node
deba@468
   943
  /// objects of the original graph can be used directly with this
deba@468
   944
  /// class. The node handling functions (id handling, observing, and
deba@468
   945
  /// iterators) works equivalently as in the original graph.
deba@468
   946
  ///
deba@512
   947
  /// \param GR The type of the graph which shares its node set with
deba@468
   948
  /// this class. Its interface must conform to the
deba@468
   949
  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
deba@468
   950
  /// concept.
deba@468
   951
  ///
deba@468
   952
  /// This implementation is slightly faster than the \c ListArcSet,
deba@468
   953
  /// because it uses continuous storage for arcs and it uses just
deba@468
   954
  /// single-linked lists for enumerate outgoing and incoming
deba@468
   955
  /// arcs. Therefore the arcs cannot be erased from the arc sets.
deba@468
   956
  ///
deba@468
   957
  /// \warning If a node is erased from the underlying graph and this
deba@468
   958
  /// node is the source or target of one arc in the arc set, then
deba@468
   959
  /// the arc set is invalidated, and it cannot be used anymore. The
deba@468
   960
  /// validity can be checked with the \c valid() member function.
deba@468
   961
  ///
kpeter@559
   962
  /// This class fully conforms to the \ref concepts::Digraph
deba@468
   963
  /// "Digraph" concept.
deba@512
   964
  template <typename GR>
deba@512
   965
  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
kpeter@617
   966
    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
deba@468
   967
deba@468
   968
  public:
deba@468
   969
deba@468
   970
    typedef typename Parent::Node Node;
deba@468
   971
    typedef typename Parent::Arc Arc;
deba@468
   972
deba@468
   973
  protected:
deba@468
   974
deba@468
   975
    typedef typename Parent::NodesImplBase NodesImplBase;
deba@468
   976
deba@468
   977
    void eraseNode(const Node& node) {
deba@468
   978
      if (typename Parent::InArcIt(*this, node) == INVALID &&
deba@468
   979
          typename Parent::OutArcIt(*this, node) == INVALID) {
deba@468
   980
        return;
deba@468
   981
      }
deba@468
   982
      throw typename NodesImplBase::Notifier::ImmediateDetach();
deba@468
   983
    }
deba@468
   984
deba@468
   985
    void clearNodes() {
deba@468
   986
      Parent::clear();
deba@468
   987
    }
deba@468
   988
deba@468
   989
    class NodesImpl : public NodesImplBase {
deba@468
   990
      typedef NodesImplBase Parent;
deba@468
   991
kpeter@617
   992
    public:
deba@512
   993
      NodesImpl(const GR& graph, SmartArcSet& arcset)
deba@468
   994
        : Parent(graph), _arcset(arcset) {}
deba@468
   995
deba@468
   996
      virtual ~NodesImpl() {}
deba@468
   997
deba@468
   998
      bool attached() const {
deba@468
   999
        return Parent::attached();
deba@468
  1000
      }
deba@468
  1001
deba@468
  1002
    protected:
deba@468
  1003
deba@468
  1004
      virtual void erase(const Node& node) {
deba@468
  1005
        try {
deba@468
  1006
          _arcset.eraseNode(node);
deba@468
  1007
          Parent::erase(node);
deba@468
  1008
        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
deba@468
  1009
          Parent::clear();
deba@468
  1010
          throw;
deba@468
  1011
        }
deba@468
  1012
      }
deba@468
  1013
      virtual void erase(const std::vector<Node>& nodes) {
deba@468
  1014
        try {
deba@468
  1015
          for (int i = 0; i < int(nodes.size()); ++i) {
deba@468
  1016
            _arcset.eraseNode(nodes[i]);
deba@468
  1017
          }
deba@468
  1018
          Parent::erase(nodes);
deba@468
  1019
        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
deba@468
  1020
          Parent::clear();
deba@468
  1021
          throw;
deba@468
  1022
        }
deba@468
  1023
      }
deba@468
  1024
      virtual void clear() {
deba@468
  1025
        _arcset.clearNodes();
deba@468
  1026
        Parent::clear();
deba@468
  1027
      }
deba@468
  1028
deba@468
  1029
    private:
deba@468
  1030
      SmartArcSet& _arcset;
deba@468
  1031
    };
deba@468
  1032
deba@512
  1033
    NodesImpl _nodes;
deba@468
  1034
deba@468
  1035
  public:
deba@468
  1036
deba@468
  1037
    /// \brief Constructor of the ArcSet.
deba@468
  1038
    ///
deba@468
  1039
    /// Constructor of the ArcSet.
deba@512
  1040
    SmartArcSet(const GR& graph) : _nodes(graph, *this) {
deba@512
  1041
      Parent::initalize(graph, _nodes);
deba@468
  1042
    }
deba@468
  1043
deba@468
  1044
    /// \brief Add a new arc to the digraph.
deba@468
  1045
    ///
deba@468
  1046
    /// Add a new arc to the digraph with source node \c s
deba@468
  1047
    /// and target node \c t.
kpeter@559
  1048
    /// \return The new arc.
deba@468
  1049
    Arc addArc(const Node& s, const Node& t) {
deba@468
  1050
      return Parent::addArc(s, t);
deba@468
  1051
    }
deba@468
  1052
deba@468
  1053
    /// \brief Validity check
deba@468
  1054
    ///
deba@468
  1055
    /// This functions gives back false if the ArcSet is
deba@468
  1056
    /// invalidated. It occurs when a node in the underlying graph is
deba@468
  1057
    /// erased and it is not isolated in the ArcSet.
deba@468
  1058
    bool valid() const {
deba@512
  1059
      return _nodes.attached();
deba@468
  1060
    }
deba@468
  1061
deba@468
  1062
  };
deba@468
  1063
deba@468
  1064
deba@512
  1065
  template <typename GR>
deba@468
  1066
  class SmartEdgeSetBase {
deba@468
  1067
  public:
deba@468
  1068
deba@512
  1069
    typedef typename GR::Node Node;
deba@512
  1070
    typedef typename GR::NodeIt NodeIt;
deba@468
  1071
deba@468
  1072
  protected:
deba@468
  1073
deba@468
  1074
    struct NodeT {
deba@468
  1075
      int first_out;
deba@468
  1076
      NodeT() : first_out(-1) {}
deba@468
  1077
    };
deba@468
  1078
deba@512
  1079
    typedef typename ItemSetTraits<GR, Node>::
deba@468
  1080
    template Map<NodeT>::Type NodesImplBase;
deba@468
  1081
deba@512
  1082
    NodesImplBase* _nodes;
deba@468
  1083
deba@468
  1084
    struct ArcT {
deba@468
  1085
      Node target;
deba@468
  1086
      int next_out;
deba@468
  1087
      ArcT() {}
deba@468
  1088
    };
deba@468
  1089
deba@468
  1090
    std::vector<ArcT> arcs;
deba@468
  1091
deba@512
  1092
    const GR* _graph;
deba@468
  1093
deba@512
  1094
    void initalize(const GR& graph, NodesImplBase& nodes) {
deba@512
  1095
      _graph = &graph;
deba@512
  1096
      _nodes = &nodes;
deba@468
  1097
    }
deba@468
  1098
deba@468
  1099
  public:
deba@468
  1100
deba@468
  1101
    class Edge {
deba@468
  1102
      friend class SmartEdgeSetBase;
deba@468
  1103
    protected:
deba@468
  1104
deba@468
  1105
      int id;
deba@468
  1106
      explicit Edge(int _id) { id = _id;}
deba@468
  1107
deba@468
  1108
    public:
deba@468
  1109
      Edge() {}
deba@468
  1110
      Edge (Invalid) { id = -1; }
deba@468
  1111
      bool operator==(const Edge& arc) const {return id == arc.id;}
deba@468
  1112
      bool operator!=(const Edge& arc) const {return id != arc.id;}
deba@468
  1113
      bool operator<(const Edge& arc) const {return id < arc.id;}
deba@468
  1114
    };
deba@468
  1115
deba@468
  1116
    class Arc {
deba@468
  1117
      friend class SmartEdgeSetBase;
deba@468
  1118
    protected:
deba@468
  1119
      Arc(int _id) : id(_id) {}
deba@468
  1120
      int id;
deba@468
  1121
    public:
deba@468
  1122
      operator Edge() const { return edgeFromId(id / 2); }
deba@468
  1123
deba@468
  1124
      Arc() {}
deba@468
  1125
      Arc(Invalid) : id(-1) {}
deba@468
  1126
      bool operator==(const Arc& arc) const { return id == arc.id; }
deba@468
  1127
      bool operator!=(const Arc& arc) const { return id != arc.id; }
deba@468
  1128
      bool operator<(const Arc& arc) const { return id < arc.id; }
deba@468
  1129
    };
deba@468
  1130
deba@468
  1131
    SmartEdgeSetBase() {}
deba@468
  1132
kpeter@670
  1133
    Node addNode() {
kpeter@670
  1134
      LEMON_ASSERT(false,
kpeter@670
  1135
        "This graph structure does not support node insertion");
kpeter@670
  1136
      return INVALID; // avoid warning
kpeter@670
  1137
    }
kpeter@670
  1138
deba@468
  1139
    Edge addEdge(const Node& u, const Node& v) {
deba@468
  1140
      int n = arcs.size();
deba@468
  1141
      arcs.push_back(ArcT());
deba@468
  1142
      arcs.push_back(ArcT());
deba@468
  1143
deba@468
  1144
      arcs[n].target = u;
deba@468
  1145
      arcs[n | 1].target = v;
deba@468
  1146
deba@512
  1147
      arcs[n].next_out = (*_nodes)[v].first_out;
deba@512
  1148
      (*_nodes)[v].first_out = n;
deba@468
  1149
deba@512
  1150
      arcs[n | 1].next_out = (*_nodes)[u].first_out;
deba@512
  1151
      (*_nodes)[u].first_out = (n | 1);
deba@468
  1152
deba@468
  1153
      return Edge(n / 2);
deba@468
  1154
    }
deba@468
  1155
deba@468
  1156
    void clear() {
deba@468
  1157
      Node node;
deba@468
  1158
      for (first(node); node != INVALID; next(node)) {
deba@512
  1159
        (*_nodes)[node].first_out = -1;
deba@468
  1160
      }
deba@468
  1161
      arcs.clear();
deba@468
  1162
    }
deba@468
  1163
deba@468
  1164
    void first(Node& node) const {
deba@512
  1165
      _graph->first(node);
deba@468
  1166
    }
deba@468
  1167
deba@468
  1168
    void next(Node& node) const {
deba@512
  1169
      _graph->next(node);
deba@468
  1170
    }
deba@468
  1171
deba@468
  1172
    void first(Arc& arc) const {
deba@468
  1173
      arc.id = arcs.size() - 1;
deba@468
  1174
    }
deba@468
  1175
deba@468
  1176
    void next(Arc& arc) const {
deba@468
  1177
      --arc.id;
deba@468
  1178
    }
deba@468
  1179
deba@468
  1180
    void first(Edge& arc) const {
deba@468
  1181
      arc.id = arcs.size() / 2 - 1;
deba@468
  1182
    }
deba@468
  1183
deba@468
  1184
    void next(Edge& arc) const {
deba@468
  1185
      --arc.id;
deba@468
  1186
    }
deba@468
  1187
deba@468
  1188
    void firstOut(Arc& arc, const Node& node) const {
deba@512
  1189
      arc.id = (*_nodes)[node].first_out;
deba@468
  1190
    }
deba@468
  1191
deba@468
  1192
    void nextOut(Arc& arc) const {
deba@468
  1193
      arc.id = arcs[arc.id].next_out;
deba@468
  1194
    }
deba@468
  1195
deba@468
  1196
    void firstIn(Arc& arc, const Node& node) const {
deba@512
  1197
      arc.id = (((*_nodes)[node].first_out) ^ 1);
deba@468
  1198
      if (arc.id == -2) arc.id = -1;
deba@468
  1199
    }
deba@468
  1200
deba@468
  1201
    void nextIn(Arc& arc) const {
deba@468
  1202
      arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
deba@468
  1203
      if (arc.id == -2) arc.id = -1;
deba@468
  1204
    }
deba@468
  1205
deba@468
  1206
    void firstInc(Edge &arc, bool& dir, const Node& node) const {
deba@512
  1207
      int de = (*_nodes)[node].first_out;
deba@468
  1208
      if (de != -1 ) {
deba@468
  1209
        arc.id = de / 2;
deba@468
  1210
        dir = ((de & 1) == 1);
deba@468
  1211
      } else {
deba@468
  1212
        arc.id = -1;
deba@468
  1213
        dir = true;
deba@468
  1214
      }
deba@468
  1215
    }
deba@468
  1216
    void nextInc(Edge &arc, bool& dir) const {
deba@468
  1217
      int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
deba@468
  1218
      if (de != -1 ) {
deba@468
  1219
        arc.id = de / 2;
deba@468
  1220
        dir = ((de & 1) == 1);
deba@468
  1221
      } else {
deba@468
  1222
        arc.id = -1;
deba@468
  1223
        dir = true;
deba@468
  1224
      }
deba@468
  1225
    }
deba@468
  1226
deba@468
  1227
    static bool direction(Arc arc) {
deba@468
  1228
      return (arc.id & 1) == 1;
deba@468
  1229
    }
deba@468
  1230
deba@468
  1231
    static Arc direct(Edge edge, bool dir) {
deba@468
  1232
      return Arc(edge.id * 2 + (dir ? 1 : 0));
deba@468
  1233
    }
deba@468
  1234
deba@512
  1235
    int id(Node node) const { return _graph->id(node); }
deba@468
  1236
    static int id(Arc arc) { return arc.id; }
deba@468
  1237
    static int id(Edge arc) { return arc.id; }
deba@468
  1238
deba@512
  1239
    Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
deba@468
  1240
    static Arc arcFromId(int id) { return Arc(id); }
deba@468
  1241
    static Edge edgeFromId(int id) { return Edge(id);}
deba@468
  1242
deba@512
  1243
    int maxNodeId() const { return _graph->maxNodeId(); };
deba@468
  1244
    int maxArcId() const { return arcs.size() - 1; }
deba@468
  1245
    int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@468
  1246
deba@468
  1247
    Node source(Arc e) const { return arcs[e.id ^ 1].target; }
deba@468
  1248
    Node target(Arc e) const { return arcs[e.id].target; }
deba@468
  1249
deba@468
  1250
    Node u(Edge e) const { return arcs[2 * e.id].target; }
deba@468
  1251
    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
deba@468
  1252
deba@512
  1253
    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
deba@468
  1254
deba@468
  1255
    NodeNotifier& notifier(Node) const {
deba@512
  1256
      return _graph->notifier(Node());
deba@468
  1257
    }
deba@468
  1258
deba@512
  1259
    template <typename V>
deba@512
  1260
    class NodeMap : public GR::template NodeMap<V> {
kpeter@617
  1261
      typedef typename GR::template NodeMap<V> Parent;
kpeter@617
  1262
deba@468
  1263
    public:
deba@468
  1264
deba@512
  1265
      explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
deba@512
  1266
        : Parent(*arcset._graph) { }
deba@468
  1267
deba@512
  1268
      NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
deba@512
  1269
        : Parent(*arcset._graph, value) { }
deba@468
  1270
deba@468
  1271
      NodeMap& operator=(const NodeMap& cmap) {
deba@468
  1272
        return operator=<NodeMap>(cmap);
deba@468
  1273
      }
deba@468
  1274
deba@468
  1275
      template <typename CMap>
deba@468
  1276
      NodeMap& operator=(const CMap& cmap) {
deba@468
  1277
        Parent::operator=(cmap);
deba@468
  1278
        return *this;
deba@468
  1279
      }
deba@468
  1280
    };
deba@468
  1281
deba@468
  1282
  };
deba@468
  1283
kpeter@660
  1284
  /// \ingroup graphs
deba@468
  1285
  ///
deba@468
  1286
  /// \brief Graph using a node set of another digraph or graph and an
deba@468
  1287
  /// own edge set.
deba@468
  1288
  ///
deba@468
  1289
  /// This structure can be used to establish another graph over a
deba@468
  1290
  /// node set of an existing one. This class uses the same Node type
deba@468
  1291
  /// as the underlying graph, and each valid node of the original
deba@468
  1292
  /// graph is valid in this arc set, therefore the node objects of
deba@468
  1293
  /// the original graph can be used directly with this class. The
deba@468
  1294
  /// node handling functions (id handling, observing, and iterators)
deba@468
  1295
  /// works equivalently as in the original graph.
deba@468
  1296
  ///
deba@512
  1297
  /// \param GR The type of the graph which shares its node set
deba@468
  1298
  /// with this class. Its interface must conform to the
deba@468
  1299
  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
deba@468
  1300
  ///  concept.
deba@468
  1301
  ///
deba@468
  1302
  /// This implementation is slightly faster than the \c ListEdgeSet,
deba@468
  1303
  /// because it uses continuous storage for edges and it uses just
deba@468
  1304
  /// single-linked lists for enumerate incident edges. Therefore the
deba@468
  1305
  /// edges cannot be erased from the edge sets.
deba@468
  1306
  ///
deba@468
  1307
  /// \warning If a node is erased from the underlying graph and this
deba@468
  1308
  /// node is incident to one edge in the edge set, then the edge set
deba@468
  1309
  /// is invalidated, and it cannot be used anymore. The validity can
deba@468
  1310
  /// be checked with the \c valid() member function.
deba@468
  1311
  ///
kpeter@559
  1312
  /// This class fully conforms to the \ref concepts::Graph
deba@468
  1313
  /// "Graph" concept.
deba@512
  1314
  template <typename GR>
deba@512
  1315
  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
kpeter@617
  1316
    typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
deba@468
  1317
deba@468
  1318
  public:
deba@468
  1319
deba@468
  1320
    typedef typename Parent::Node Node;
deba@468
  1321
    typedef typename Parent::Arc Arc;
deba@468
  1322
    typedef typename Parent::Edge Edge;
deba@468
  1323
deba@468
  1324
  protected:
deba@468
  1325
deba@468
  1326
    typedef typename Parent::NodesImplBase NodesImplBase;
deba@468
  1327
deba@468
  1328
    void eraseNode(const Node& node) {
deba@468
  1329
      if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
deba@468
  1330
        return;
deba@468
  1331
      }
deba@468
  1332
      throw typename NodesImplBase::Notifier::ImmediateDetach();
deba@468
  1333
    }
deba@468
  1334
deba@468
  1335
    void clearNodes() {
deba@468
  1336
      Parent::clear();
deba@468
  1337
    }
deba@468
  1338
deba@468
  1339
    class NodesImpl : public NodesImplBase {
deba@468
  1340
      typedef NodesImplBase Parent;
deba@468
  1341
kpeter@617
  1342
    public:
deba@512
  1343
      NodesImpl(const GR& graph, SmartEdgeSet& arcset)
deba@468
  1344
        : Parent(graph), _arcset(arcset) {}
deba@468
  1345
deba@468
  1346
      virtual ~NodesImpl() {}
deba@468
  1347
deba@468
  1348
      bool attached() const {
deba@468
  1349
        return Parent::attached();
deba@468
  1350
      }
deba@468
  1351
deba@468
  1352
    protected:
deba@468
  1353
deba@468
  1354
      virtual void erase(const Node& node) {
deba@468
  1355
        try {
deba@468
  1356
          _arcset.eraseNode(node);
deba@468
  1357
          Parent::erase(node);
deba@468
  1358
        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
deba@468
  1359
          Parent::clear();
deba@468
  1360
          throw;
deba@468
  1361
        }
deba@468
  1362
      }
deba@468
  1363
      virtual void erase(const std::vector<Node>& nodes) {
deba@468
  1364
        try {
deba@468
  1365
          for (int i = 0; i < int(nodes.size()); ++i) {
deba@468
  1366
            _arcset.eraseNode(nodes[i]);
deba@468
  1367
          }
deba@468
  1368
          Parent::erase(nodes);
deba@468
  1369
        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
deba@468
  1370
          Parent::clear();
deba@468
  1371
          throw;
deba@468
  1372
        }
deba@468
  1373
      }
deba@468
  1374
      virtual void clear() {
deba@468
  1375
        _arcset.clearNodes();
deba@468
  1376
        Parent::clear();
deba@468
  1377
      }
deba@468
  1378
deba@468
  1379
    private:
deba@468
  1380
      SmartEdgeSet& _arcset;
deba@468
  1381
    };
deba@468
  1382
deba@512
  1383
    NodesImpl _nodes;
deba@468
  1384
deba@468
  1385
  public:
deba@468
  1386
deba@468
  1387
    /// \brief Constructor of the EdgeSet.
deba@468
  1388
    ///
deba@468
  1389
    /// Constructor of the EdgeSet.
deba@512
  1390
    SmartEdgeSet(const GR& graph) : _nodes(graph, *this) {
deba@512
  1391
      Parent::initalize(graph, _nodes);
deba@468
  1392
    }
deba@468
  1393
deba@468
  1394
    /// \brief Add a new edge to the graph.
deba@468
  1395
    ///
deba@468
  1396
    /// Add a new edge to the graph with node \c u
deba@468
  1397
    /// and node \c v endpoints.
kpeter@559
  1398
    /// \return The new edge.
deba@468
  1399
    Edge addEdge(const Node& u, const Node& v) {
deba@468
  1400
      return Parent::addEdge(u, v);
deba@468
  1401
    }
deba@468
  1402
deba@468
  1403
    /// \brief Validity check
deba@468
  1404
    ///
deba@468
  1405
    /// This functions gives back false if the EdgeSet is
deba@468
  1406
    /// invalidated. It occurs when a node in the underlying graph is
deba@468
  1407
    /// erased and it is not isolated in the EdgeSet.
deba@468
  1408
    bool valid() const {
deba@512
  1409
      return _nodes.attached();
deba@468
  1410
    }
deba@468
  1411
deba@468
  1412
  };
deba@468
  1413
deba@468
  1414
}
deba@468
  1415
deba@468
  1416
#endif