Mercuriallemon-main / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/edge_set.h
changeset 550 20e3acc1a757
parent 468 68fe66e2b34a
child 559 c5fd2d996909
equal deleted inserted replaced
0:156cf2b3e5a3 1:539ef86d6577 
    27 /// \brief ArcSet and EdgeSet classes.
 
    27 /// \brief ArcSet and EdgeSet classes.
 
    28 ///
 
    28 ///
 
    29 /// Graphs which use another graph's node-set as own.
 
    29 /// Graphs which use another graph's node-set as own.
 
    30 namespace lemon {
 
    30 namespace lemon {
 
    31 
    31 
    32   template <typename _Graph>
 
    32   template <typename GR>
 
    33   class ListArcSetBase {
 
    33   class ListArcSetBase {
 
    34   public:
 
    34   public:
 
    35 
    35 
    36     typedef _Graph Graph;
 
    36     typedef GR Graph;
 
    37     typedef typename Graph::Node Node;
 
    37     typedef typename GR::Node Node;
 
    38     typedef typename Graph::NodeIt NodeIt;
 
    38     typedef typename GR::NodeIt NodeIt;
 
    39 
    39 
    40   protected:
 
    40   protected:
 
    41 
    41 
    42     struct NodeT {
 
    42     struct NodeT {
 
    43       int first_out, first_in;
 
    43       int first_out, first_in;
 
    44       NodeT() : first_out(-1), first_in(-1) {}
 
    44       NodeT() : first_out(-1), first_in(-1) {}
 
    45     };
 
    45     };
 
    46 
    46 
    47     typedef typename ItemSetTraits<Graph, Node>::
 
    47     typedef typename ItemSetTraits<GR, Node>::
 
    48     template Map<NodeT>::Type NodesImplBase;
 
    48     template Map<NodeT>::Type NodesImplBase;
 
    49 
    49 
    50     NodesImplBase* nodes;
 
    50     NodesImplBase* _nodes;
 
    51 
    51 
    52     struct ArcT {
 
    52     struct ArcT {
 
    53       Node source, target;
 
    53       Node source, target;
 
    54       int next_out, next_in;
 
    54       int next_out, next_in;
 
    55       int prev_out, prev_in;
 
    55       int prev_out, prev_in;
 
    59     std::vector<ArcT> arcs;
 
    59     std::vector<ArcT> arcs;
 
    60 
    60 
    61     int first_arc;
 
    61     int first_arc;
 
    62     int first_free_arc;
 
    62     int first_free_arc;
 
    63 
    63 
    64     const Graph* graph;
 
    64     const GR* _graph;
 
    65 
    65 
    66     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
 
    66     void initalize(const GR& graph, NodesImplBase& nodes) {
 
    67       graph = &_graph;
 
    67       _graph = &graph;
 
    68       nodes = &_nodes;
 
    68       _nodes = &nodes;
 
    69     }
 
    69     }
 
    70 
    70 
    71   public:
 
    71   public:
 
    72 
    72 
    73     class Arc {
 
    73     class Arc {
 
    74       friend class ListArcSetBase<Graph>;
 
    74       friend class ListArcSetBase<GR>;
 
    75     protected:
 
    75     protected:
 
    76       Arc(int _id) : id(_id) {}
 
    76       Arc(int _id) : id(_id) {}
 
    77       int id;
 
    77       int id;
 
    78     public:
 
    78     public:
 
    79       Arc() {}
 
    79       Arc() {}
 
    92         arcs.push_back(ArcT());
 
    92         arcs.push_back(ArcT());
 
    93       } else {
 
    93       } else {
 
    94         n = first_free_arc;
 
    94         n = first_free_arc;
 
    95         first_free_arc = arcs[first_free_arc].next_in;
 
    95         first_free_arc = arcs[first_free_arc].next_in;
 
    96       }
 
    96       }
 
    97       arcs[n].next_in = (*nodes)[v].first_in;
 
    97       arcs[n].next_in = (*_nodes)[v].first_in;
 
    98       if ((*nodes)[v].first_in != -1) {
 
    98       if ((*_nodes)[v].first_in != -1) {
 
    99         arcs[(*nodes)[v].first_in].prev_in = n;
 
    99         arcs[(*_nodes)[v].first_in].prev_in = n;
 
   100       }
 
   100       }
 
   101       (*nodes)[v].first_in = n;
 
   101       (*_nodes)[v].first_in = n;
 
   102       arcs[n].next_out = (*nodes)[u].first_out;
 
   102       arcs[n].next_out = (*_nodes)[u].first_out;
 
   103       if ((*nodes)[u].first_out != -1) {
 
   103       if ((*_nodes)[u].first_out != -1) {
 
   104         arcs[(*nodes)[u].first_out].prev_out = n;
 
   104         arcs[(*_nodes)[u].first_out].prev_out = n;
 
   105       }
 
   105       }
 
   106       (*nodes)[u].first_out = n;
 
   106       (*_nodes)[u].first_out = n;
 
   107       arcs[n].source = u;
 
   107       arcs[n].source = u;
 
   108       arcs[n].target = v;
 
   108       arcs[n].target = v;
 
   109       return Arc(n);
 
   109       return Arc(n);
 
   110     }
 
   110     }
 
   111 
   111 
   112     void erase(const Arc& arc) {
 
   112     void erase(const Arc& arc) {
 
   113       int n = arc.id;
 
   113       int n = arc.id;
 
   114       if (arcs[n].prev_in != -1) {
 
   114       if (arcs[n].prev_in != -1) {
 
   115         arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
 
   115         arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
 
   116       } else {
 
   116       } else {
 
   117         (*nodes)[arcs[n].target].first_in = arcs[n].next_in;
 
   117         (*_nodes)[arcs[n].target].first_in = arcs[n].next_in;
 
   118       }
 
   118       }
 
   119       if (arcs[n].next_in != -1) {
 
   119       if (arcs[n].next_in != -1) {
 
   120         arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
 
   120         arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
 
   121       }
 
   121       }
 
   122 
   122 
   123       if (arcs[n].prev_out != -1) {
 
   123       if (arcs[n].prev_out != -1) {
 
   124         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 
   124         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 
   125       } else {
 
   125       } else {
 
   126         (*nodes)[arcs[n].source].first_out = arcs[n].next_out;
 
   126         (*_nodes)[arcs[n].source].first_out = arcs[n].next_out;
 
   127       }
 
   127       }
 
   128       if (arcs[n].next_out != -1) {
 
   128       if (arcs[n].next_out != -1) {
 
   129         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
 
   129         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
 
   130       }
 
   130       }
 
   131 
   131 
   132     }
 
   132     }
 
   133 
   133 
   134     void clear() {
 
   134     void clear() {
 
   135       Node node;
 
   135       Node node;
 
   136       for (first(node); node != INVALID; next(node)) {
 
   136       for (first(node); node != INVALID; next(node)) {
 
   137         (*nodes)[node].first_in = -1;
 
   137         (*_nodes)[node].first_in = -1;
 
   138         (*nodes)[node].first_out = -1;
 
   138         (*_nodes)[node].first_out = -1;
 
   139       }
 
   139       }
 
   140       arcs.clear();
 
   140       arcs.clear();
 
   141       first_arc = -1;
 
   141       first_arc = -1;
 
   142       first_free_arc = -1;
 
   142       first_free_arc = -1;
 
   143     }
 
   143     }
 
   144 
   144 
   145     void first(Node& node) const {
 
   145     void first(Node& node) const {
 
   146       graph->first(node);
 
   146       _graph->first(node);
 
   147     }
 
   147     }
 
   148 
   148 
   149     void next(Node& node) const {
 
   149     void next(Node& node) const {
 
   150       graph->next(node);
 
   150       _graph->next(node);
 
   151     }
 
   151     }
 
   152 
   152 
   153     void first(Arc& arc) const {
 
   153     void first(Arc& arc) const {
 
   154       Node node;
 
   154       Node node;
 
   155       first(node);
 
   155       first(node);
 
   156       while (node != INVALID && (*nodes)[node].first_in == -1) {
 
   156       while (node != INVALID && (*_nodes)[node].first_in == -1) {
 
   157         next(node);
 
   157         next(node);
 
   158       }
 
   158       }
 
   159       arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
 
   159       arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
 
   160     }
 
   160     }
 
   161 
   161 
   162     void next(Arc& arc) const {
 
   162     void next(Arc& arc) const {
 
   163       if (arcs[arc.id].next_in != -1) {
 
   163       if (arcs[arc.id].next_in != -1) {
 
   164         arc.id = arcs[arc.id].next_in;
 
   164         arc.id = arcs[arc.id].next_in;
 
   165       } else {
 
   165       } else {
 
   166         Node node = arcs[arc.id].target;
 
   166         Node node = arcs[arc.id].target;
 
   167         next(node);
 
   167         next(node);
 
   168         while (node != INVALID && (*nodes)[node].first_in == -1) {
 
   168         while (node != INVALID && (*_nodes)[node].first_in == -1) {
 
   169           next(node);
 
   169           next(node);
 
   170         }
 
   170         }
 
   171         arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
 
   171         arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
 
   172       }
 
   172       }
 
   173     }
 
   173     }
 
   174 
   174 
   175     void firstOut(Arc& arc, const Node& node) const {
 
   175     void firstOut(Arc& arc, const Node& node) const {
 
   176       arc.id = (*nodes)[node].first_out;
 
   176       arc.id = (*_nodes)[node].first_out;
 
   177     }
 
   177     }
 
   178 
   178 
   179     void nextOut(Arc& arc) const {
 
   179     void nextOut(Arc& arc) const {
 
   180       arc.id = arcs[arc.id].next_out;
 
   180       arc.id = arcs[arc.id].next_out;
 
   181     }
 
   181     }
 
   182 
   182 
   183     void firstIn(Arc& arc, const Node& node) const {
 
   183     void firstIn(Arc& arc, const Node& node) const {
 
   184       arc.id = (*nodes)[node].first_in;
 
   184       arc.id = (*_nodes)[node].first_in;
 
   185     }
 
   185     }
 
   186 
   186 
   187     void nextIn(Arc& arc) const {
 
   187     void nextIn(Arc& arc) const {
 
   188       arc.id = arcs[arc.id].next_in;
 
   188       arc.id = arcs[arc.id].next_in;
 
   189     }
 
   189     }
 
   190 
   190 
   191     int id(const Node& node) const { return graph->id(node); }
 
   191     int id(const Node& node) const { return _graph->id(node); }
 
   192     int id(const Arc& arc) const { return arc.id; }
 
   192     int id(const Arc& arc) const { return arc.id; }
 
   193 
   193 
   194     Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
 
   194     Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
 
   195     Arc arcFromId(int ix) const { return Arc(ix); }
 
   195     Arc arcFromId(int ix) const { return Arc(ix); }
 
   196 
   196 
   197     int maxNodeId() const { return graph->maxNodeId(); };
 
   197     int maxNodeId() const { return _graph->maxNodeId(); };
 
   198     int maxArcId() const { return arcs.size() - 1; }
 
   198     int maxArcId() const { return arcs.size() - 1; }
 
   199 
   199 
   200     Node source(const Arc& arc) const { return arcs[arc.id].source;}
 
   200     Node source(const Arc& arc) const { return arcs[arc.id].source;}
 
   201     Node target(const Arc& arc) const { return arcs[arc.id].target;}
 
   201     Node target(const Arc& arc) const { return arcs[arc.id].target;}
 
   202 
   202 
   203     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
 
   203     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 
   204 
   204 
   205     NodeNotifier& notifier(Node) const {
 
   205     NodeNotifier& notifier(Node) const {
 
   206       return graph->notifier(Node());
 
   206       return _graph->notifier(Node());
 
   207     }
 
   207     }
 
   208 
   208 
   209     template <typename _Value>
 
   209     template <typename V>
 
   210     class NodeMap : public Graph::template NodeMap<_Value> {
 
   210     class NodeMap : public GR::template NodeMap<V> {
 
   211     public:
 
   211     public:
 
   212 
   212 
   213       typedef typename _Graph::template NodeMap<_Value> Parent;
 
   213       typedef typename GR::template NodeMap<V> Parent;
 
   214 
   214 
   215       explicit NodeMap(const ListArcSetBase<Graph>& arcset)
 
   215       explicit NodeMap(const ListArcSetBase<GR>& arcset)
 
   216         : Parent(*arcset.graph) {}
 
   216         : Parent(*arcset._graph) {}
 
   217 
   217 
   218       NodeMap(const ListArcSetBase<Graph>& arcset, const _Value& value)
 
   218       NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
 
   219         : Parent(*arcset.graph, value) {}
 
   219         : Parent(*arcset._graph, value) {}
 
   220 
   220 
   221       NodeMap& operator=(const NodeMap& cmap) {
 
   221       NodeMap& operator=(const NodeMap& cmap) {
 
   222         return operator=<NodeMap>(cmap);
 
   222         return operator=<NodeMap>(cmap);
 
   223       }
 
   223       }
 
   224 
   224 
   248   /// node the outgoing and the incoming arcs make up lists, therefore
 
   248   /// node the outgoing and the incoming arcs make up lists, therefore
 
   249   /// one arc can be erased in constant time. It also makes possible,
 
   249   /// one arc can be erased in constant time. It also makes possible,
 
   250   /// that node can be removed from the underlying graph, in this case
 
   250   /// that node can be removed from the underlying graph, in this case
 
   251   /// all arcs incident to the given node is erased from the arc set.
 
   251   /// all arcs incident to the given node is erased from the arc set.
 
   252   ///
 
   252   ///
 
   253   /// \param _Graph The type of the graph which shares its node set with
 
   253   /// \param GR The type of the graph which shares its node set with
 
   254   /// this class. Its interface must conform to the
 
   254   /// this class. Its interface must conform to the
 
   255   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 
   255   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 
   256   /// concept.
 
   256   /// concept.
 
   257   ///
 
   257   ///
 
   258   /// This class is fully conform to the \ref concepts::Digraph
 
   258   /// This class is fully conform to the \ref concepts::Digraph
 
   259   /// "Digraph" concept.
 
   259   /// "Digraph" concept.
 
   260   template <typename _Graph>
 
   260   template <typename GR>
 
   261   class ListArcSet : public ArcSetExtender<ListArcSetBase<_Graph> > {
 
   261   class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
 
   262 
   262 
   263   public:
 
   263   public:
 
   264 
   264 
   265     typedef ArcSetExtender<ListArcSetBase<_Graph> > Parent;
 
   265     typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
 
   266 
   266 
   267     typedef typename Parent::Node Node;
 
   267     typedef typename Parent::Node Node;
 
   268     typedef typename Parent::Arc Arc;
 
   268     typedef typename Parent::Arc Arc;
 
   269 
   269 
   270     typedef _Graph Graph;
 
   270     typedef GR Graph;
 
   271 
   271 
   272 
   272 
   273     typedef typename Parent::NodesImplBase NodesImplBase;
 
   273     typedef typename Parent::NodesImplBase NodesImplBase;
 
   274 
   274 
   275     void eraseNode(const Node& node) {
 
   275     void eraseNode(const Node& node) {
 
   293 
   293 
   294     class NodesImpl : public NodesImplBase {
 
   294     class NodesImpl : public NodesImplBase {
 
   295     public:
 
   295     public:
 
   296       typedef NodesImplBase Parent;
 
   296       typedef NodesImplBase Parent;
 
   297 
   297 
   298       NodesImpl(const Graph& graph, ListArcSet& arcset)
 
   298       NodesImpl(const GR& graph, ListArcSet& arcset)
 
   299         : Parent(graph), _arcset(arcset) {}
 
   299         : Parent(graph), _arcset(arcset) {}
 
   300 
   300 
   301       virtual ~NodesImpl() {}
 
   301       virtual ~NodesImpl() {}
 
   302 
   302 
   303     protected:
 
   303     protected:
 
   319 
   319 
   320     private:
 
   320     private:
 
   321       ListArcSet& _arcset;
 
   321       ListArcSet& _arcset;
 
   322     };
 
   322     };
 
   323 
   323 
   324     NodesImpl nodes;
 
   324     NodesImpl _nodes;
 
   325 
   325 
   326   public:
 
   326   public:
 
   327 
   327 
   328     /// \brief Constructor of the ArcSet.
 
   328     /// \brief Constructor of the ArcSet.
 
   329     ///
 
   329     ///
 
   330     /// Constructor of the ArcSet.
 
   330     /// Constructor of the ArcSet.
 
   331     ListArcSet(const Graph& graph) : nodes(graph, *this) {
 
   331     ListArcSet(const GR& graph) : _nodes(graph, *this) {
 
   332       Parent::initalize(graph, nodes);
 
   332       Parent::initalize(graph, _nodes);
 
   333     }
 
   333     }
 
   334 
   334 
   335     /// \brief Add a new arc to the digraph.
 
   335     /// \brief Add a new arc to the digraph.
 
   336     ///
 
   336     ///
 
   337     /// Add a new arc to the digraph with source node \c s
 
   337     /// Add a new arc to the digraph with source node \c s
 
   348       return Parent::erase(a);
 
   348       return Parent::erase(a);
 
   349     }
 
   349     }
 
   350 
   350 
   351   };
 
   351   };
 
   352 
   352 
   353   template <typename _Graph>
 
   353   template <typename GR>
 
   354   class ListEdgeSetBase {
 
   354   class ListEdgeSetBase {
 
   355   public:
 
   355   public:
 
   356 
   356 
   357     typedef _Graph Graph;
 
   357     typedef GR Graph;
 
   358     typedef typename Graph::Node Node;
 
   358     typedef typename GR::Node Node;
 
   359     typedef typename Graph::NodeIt NodeIt;
 
   359     typedef typename GR::NodeIt NodeIt;
 
   360 
   360 
   361   protected:
 
   361   protected:
 
   362 
   362 
   363     struct NodeT {
 
   363     struct NodeT {
 
   364       int first_out;
 
   364       int first_out;
 
   365       NodeT() : first_out(-1) {}
 
   365       NodeT() : first_out(-1) {}
 
   366     };
 
   366     };
 
   367 
   367 
   368     typedef typename ItemSetTraits<Graph, Node>::
 
   368     typedef typename ItemSetTraits<GR, Node>::
 
   369     template Map<NodeT>::Type NodesImplBase;
 
   369     template Map<NodeT>::Type NodesImplBase;
 
   370 
   370 
   371     NodesImplBase* nodes;
 
   371     NodesImplBase* _nodes;
 
   372 
   372 
   373     struct ArcT {
 
   373     struct ArcT {
 
   374       Node target;
 
   374       Node target;
 
   375       int prev_out, next_out;
 
   375       int prev_out, next_out;
 
   376       ArcT() : prev_out(-1), next_out(-1) {}
 
   376       ArcT() : prev_out(-1), next_out(-1) {}
 
   379     std::vector<ArcT> arcs;
 
   379     std::vector<ArcT> arcs;
 
   380 
   380 
   381     int first_arc;
 
   381     int first_arc;
 
   382     int first_free_arc;
 
   382     int first_free_arc;
 
   383 
   383 
   384     const Graph* graph;
 
   384     const GR* _graph;
 
   385 
   385 
   386     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
 
   386     void initalize(const GR& graph, NodesImplBase& nodes) {
 
   387       graph = &_graph;
 
   387       _graph = &graph;
 
   388       nodes = &_nodes;
 
   388       _nodes = &nodes;
 
   389     }
 
   389     }
 
   390 
   390 
   391   public:
 
   391   public:
 
   392 
   392 
   393     class Edge {
 
   393     class Edge {
 
   435       }
 
   435       }
 
   436 
   436 
   437       arcs[n].target = u;
 
   437       arcs[n].target = u;
 
   438       arcs[n | 1].target = v;
 
   438       arcs[n | 1].target = v;
 
   439 
   439 
   440       arcs[n].next_out = (*nodes)[v].first_out;
 
   440       arcs[n].next_out = (*_nodes)[v].first_out;
 
   441       if ((*nodes)[v].first_out != -1) {
 
   441       if ((*_nodes)[v].first_out != -1) {
 
   442         arcs[(*nodes)[v].first_out].prev_out = n;
 
   442         arcs[(*_nodes)[v].first_out].prev_out = n;
 
   443       }
 
   443       }
 
   444       (*nodes)[v].first_out = n;
 
   444       (*_nodes)[v].first_out = n;
 
   445       arcs[n].prev_out = -1;
 
   445       arcs[n].prev_out = -1;
 
   446 
   446 
   447       if ((*nodes)[u].first_out != -1) {
 
   447       if ((*_nodes)[u].first_out != -1) {
 
   448         arcs[(*nodes)[u].first_out].prev_out = (n | 1);
 
   448         arcs[(*_nodes)[u].first_out].prev_out = (n | 1);
 
   449       }
 
   449       }
 
   450       arcs[n | 1].next_out = (*nodes)[u].first_out;
 
   450       arcs[n | 1].next_out = (*_nodes)[u].first_out;
 
   451       (*nodes)[u].first_out = (n | 1);
 
   451       (*_nodes)[u].first_out = (n | 1);
 
   452       arcs[n | 1].prev_out = -1;
 
   452       arcs[n | 1].prev_out = -1;
 
   453 
   453 
   454       return Edge(n / 2);
 
   454       return Edge(n / 2);
 
   455     }
 
   455     }
 
   456 
   456 
   462       }
 
   462       }
 
   463 
   463 
   464       if (arcs[n].prev_out != -1) {
 
   464       if (arcs[n].prev_out != -1) {
 
   465         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 
   465         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 
   466       } else {
 
   466       } else {
 
   467         (*nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
 
   467         (*_nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
 
   468       }
 
   468       }
 
   469 
   469 
   470       if (arcs[n | 1].next_out != -1) {
 
   470       if (arcs[n | 1].next_out != -1) {
 
   471         arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
 
   471         arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
 
   472       }
 
   472       }
 
   473 
   473 
   474       if (arcs[n | 1].prev_out != -1) {
 
   474       if (arcs[n | 1].prev_out != -1) {
 
   475         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
 
   475         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
 
   476       } else {
 
   476       } else {
 
   477         (*nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
 
   477         (*_nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
 
   478       }
 
   478       }
 
   479 
   479 
   480       arcs[n].next_out = first_free_arc;
 
   480       arcs[n].next_out = first_free_arc;
 
   481       first_free_arc = n;
 
   481       first_free_arc = n;
 
   482 
   482 
   483     }
 
   483     }
 
   484 
   484 
   485     void clear() {
 
   485     void clear() {
 
   486       Node node;
 
   486       Node node;
 
   487       for (first(node); node != INVALID; next(node)) {
 
   487       for (first(node); node != INVALID; next(node)) {
 
   488         (*nodes)[node].first_out = -1;
 
   488         (*_nodes)[node].first_out = -1;
 
   489       }
 
   489       }
 
   490       arcs.clear();
 
   490       arcs.clear();
 
   491       first_arc = -1;
 
   491       first_arc = -1;
 
   492       first_free_arc = -1;
 
   492       first_free_arc = -1;
 
   493     }
 
   493     }
 
   494 
   494 
   495     void first(Node& node) const {
 
   495     void first(Node& node) const {
 
   496       graph->first(node);
 
   496       _graph->first(node);
 
   497     }
 
   497     }
 
   498 
   498 
   499     void next(Node& node) const {
 
   499     void next(Node& node) const {
 
   500       graph->next(node);
 
   500       _graph->next(node);
 
   501     }
 
   501     }
 
   502 
   502 
   503     void first(Arc& arc) const {
 
   503     void first(Arc& arc) const {
 
   504       Node node;
 
   504       Node node;
 
   505       first(node);
 
   505       first(node);
 
   506       while (node != INVALID && (*nodes)[node].first_out == -1) {
 
   506       while (node != INVALID && (*_nodes)[node].first_out == -1) {
 
   507         next(node);
 
   507         next(node);
 
   508       }
 
   508       }
 
   509       arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
 
   509       arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
 
   510     }
 
   510     }
 
   511 
   511 
   512     void next(Arc& arc) const {
 
   512     void next(Arc& arc) const {
 
   513       if (arcs[arc.id].next_out != -1) {
 
   513       if (arcs[arc.id].next_out != -1) {
 
   514         arc.id = arcs[arc.id].next_out;
 
   514         arc.id = arcs[arc.id].next_out;
 
   515       } else {
 
   515       } else {
 
   516         Node node = arcs[arc.id ^ 1].target;
 
   516         Node node = arcs[arc.id ^ 1].target;
 
   517         next(node);
 
   517         next(node);
 
   518         while(node != INVALID && (*nodes)[node].first_out == -1) {
 
   518         while(node != INVALID && (*_nodes)[node].first_out == -1) {
 
   519           next(node);
 
   519           next(node);
 
   520         }
 
   520         }
 
   521         arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
 
   521         arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
 
   522       }
 
   522       }
 
   523     }
 
   523     }
 
   524 
   524 
   525     void first(Edge& edge) const {
 
   525     void first(Edge& edge) const {
 
   526       Node node;
 
   526       Node node;
 
   527       first(node);
 
   527       first(node);
 
   528       while (node != INVALID) {
 
   528       while (node != INVALID) {
 
   529         edge.id = (*nodes)[node].first_out;
 
   529         edge.id = (*_nodes)[node].first_out;
 
   530         while ((edge.id & 1) != 1) {
 
   530         while ((edge.id & 1) != 1) {
 
   531           edge.id = arcs[edge.id].next_out;
 
   531           edge.id = arcs[edge.id].next_out;
 
   532         }
 
   532         }
 
   533         if (edge.id != -1) {
 
   533         if (edge.id != -1) {
 
   534           edge.id /= 2;
 
   534           edge.id /= 2;
 
   549         edge.id /= 2;
 
   549         edge.id /= 2;
 
   550         return;
 
   550         return;
 
   551       }
 
   551       }
 
   552       next(node);
 
   552       next(node);
 
   553       while (node != INVALID) {
 
   553       while (node != INVALID) {
 
   554         edge.id = (*nodes)[node].first_out;
 
   554         edge.id = (*_nodes)[node].first_out;
 
   555         while ((edge.id & 1) != 1) {
 
   555         while ((edge.id & 1) != 1) {
 
   556           edge.id = arcs[edge.id].next_out;
 
   556           edge.id = arcs[edge.id].next_out;
 
   557         }
 
   557         }
 
   558         if (edge.id != -1) {
 
   558         if (edge.id != -1) {
 
   559           edge.id /= 2;
 
   559           edge.id /= 2;
 
   563       }
 
   563       }
 
   564       edge.id = -1;
 
   564       edge.id = -1;
 
   565     }
 
   565     }
 
   566 
   566 
   567     void firstOut(Arc& arc, const Node& node) const {
 
   567     void firstOut(Arc& arc, const Node& node) const {
 
   568       arc.id = (*nodes)[node].first_out;
 
   568       arc.id = (*_nodes)[node].first_out;
 
   569     }
 
   569     }
 
   570 
   570 
   571     void nextOut(Arc& arc) const {
 
   571     void nextOut(Arc& arc) const {
 
   572       arc.id = arcs[arc.id].next_out;
 
   572       arc.id = arcs[arc.id].next_out;
 
   573     }
 
   573     }
 
   574 
   574 
   575     void firstIn(Arc& arc, const Node& node) const {
 
   575     void firstIn(Arc& arc, const Node& node) const {
 
   576       arc.id = (((*nodes)[node].first_out) ^ 1);
 
   576       arc.id = (((*_nodes)[node].first_out) ^ 1);
 
   577       if (arc.id == -2) arc.id = -1;
 
   577       if (arc.id == -2) arc.id = -1;
 
   578     }
 
   578     }
 
   579 
   579 
   580     void nextIn(Arc& arc) const {
 
   580     void nextIn(Arc& arc) const {
 
   581       arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
 
   581       arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
 
   582       if (arc.id == -2) arc.id = -1;
 
   582       if (arc.id == -2) arc.id = -1;
 
   583     }
 
   583     }
 
   584 
   584 
   585     void firstInc(Edge &arc, bool& dir, const Node& node) const {
 
   585     void firstInc(Edge &arc, bool& dir, const Node& node) const {
 
   586       int de = (*nodes)[node].first_out;
 
   586       int de = (*_nodes)[node].first_out;
 
   587       if (de != -1 ) {
 
   587       if (de != -1 ) {
 
   588         arc.id = de / 2;
 
   588         arc.id = de / 2;
 
   589         dir = ((de & 1) == 1);
 
   589         dir = ((de & 1) == 1);
 
   590       } else {
 
   590       } else {
 
   591         arc.id = -1;
 
   591         arc.id = -1;
 
   609 
   609 
   610     static Arc direct(Edge edge, bool dir) {
 
   610     static Arc direct(Edge edge, bool dir) {
 
   611       return Arc(edge.id * 2 + (dir ? 1 : 0));
 
   611       return Arc(edge.id * 2 + (dir ? 1 : 0));
 
   612     }
 
   612     }
 
   613 
   613 
   614     int id(const Node& node) const { return graph->id(node); }
 
   614     int id(const Node& node) const { return _graph->id(node); }
 
   615     static int id(Arc e) { return e.id; }
 
   615     static int id(Arc e) { return e.id; }
 
   616     static int id(Edge e) { return e.id; }
 
   616     static int id(Edge e) { return e.id; }
 
   617 
   617 
   618     Node nodeFromId(int id) const { return graph->nodeFromId(id); }
 
   618     Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
 
   619     static Arc arcFromId(int id) { return Arc(id);}
 
   619     static Arc arcFromId(int id) { return Arc(id);}
 
   620     static Edge edgeFromId(int id) { return Edge(id);}
 
   620     static Edge edgeFromId(int id) { return Edge(id);}
 
   621 
   621 
   622     int maxNodeId() const { return graph->maxNodeId(); };
 
   622     int maxNodeId() const { return _graph->maxNodeId(); };
 
   623     int maxEdgeId() const { return arcs.size() / 2 - 1; }
 
   623     int maxEdgeId() const { return arcs.size() / 2 - 1; }
 
   624     int maxArcId() const { return arcs.size()-1; }
 
   624     int maxArcId() const { return arcs.size()-1; }
 
   625 
   625 
   626     Node source(Arc e) const { return arcs[e.id ^ 1].target; }
 
   626     Node source(Arc e) const { return arcs[e.id ^ 1].target; }
 
   627     Node target(Arc e) const { return arcs[e.id].target; }
 
   627     Node target(Arc e) const { return arcs[e.id].target; }
 
   628 
   628 
   629     Node u(Edge e) const { return arcs[2 * e.id].target; }
 
   629     Node u(Edge e) const { return arcs[2 * e.id].target; }
 
   630     Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
 
   630     Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
 
   631 
   631 
   632     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
 
   632     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 
   633 
   633 
   634     NodeNotifier& notifier(Node) const {
 
   634     NodeNotifier& notifier(Node) const {
 
   635       return graph->notifier(Node());
 
   635       return _graph->notifier(Node());
 
   636     }
 
   636     }
 
   637 
   637 
   638     template <typename _Value>
 
   638     template <typename V>
 
   639     class NodeMap : public Graph::template NodeMap<_Value> {
 
   639     class NodeMap : public GR::template NodeMap<V> {
 
   640     public:
 
   640     public:
 
   641 
   641 
   642       typedef typename _Graph::template NodeMap<_Value> Parent;
 
   642       typedef typename GR::template NodeMap<V> Parent;
 
   643 
   643 
   644       explicit NodeMap(const ListEdgeSetBase<Graph>& arcset)
 
   644       explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
 
   645         : Parent(*arcset.graph) {}
 
   645         : Parent(*arcset._graph) {}
 
   646 
   646 
   647       NodeMap(const ListEdgeSetBase<Graph>& arcset, const _Value& value)
 
   647       NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
 
   648         : Parent(*arcset.graph, value) {}
 
   648         : Parent(*arcset._graph, value) {}
 
   649 
   649 
   650       NodeMap& operator=(const NodeMap& cmap) {
 
   650       NodeMap& operator=(const NodeMap& cmap) {
 
   651         return operator=<NodeMap>(cmap);
 
   651         return operator=<NodeMap>(cmap);
 
   652       }
 
   652       }
 
   653 
   653 
   677   /// node the incident edges make up lists, therefore one edge can be
 
   677   /// node the incident edges make up lists, therefore one edge can be
 
   678   /// erased in constant time. It also makes possible, that node can
 
   678   /// erased in constant time. It also makes possible, that node can
 
   679   /// be removed from the underlying graph, in this case all edges
 
   679   /// be removed from the underlying graph, in this case all edges
 
   680   /// incident to the given node is erased from the arc set.
 
   680   /// incident to the given node is erased from the arc set.
 
   681   ///
 
   681   ///
 
   682   /// \param _Graph The type of the graph which shares its node set
 
   682   /// \param GR The type of the graph which shares its node set
 
   683   /// with this class. Its interface must conform to the
 
   683   /// with this class. Its interface must conform to the
 
   684   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 
   684   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 
   685   /// concept.
 
   685   /// concept.
 
   686   ///
 
   686   ///
 
   687   /// This class is fully conform to the \ref concepts::Graph "Graph"
 
   687   /// This class is fully conform to the \ref concepts::Graph "Graph"
 
   688   /// concept.
 
   688   /// concept.
 
   689   template <typename _Graph>
 
   689   template <typename GR>
 
   690   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
 
   690   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
 
   691 
   691 
   692   public:
 
   692   public:
 
   693 
   693 
   694     typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
 
   694     typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
 
   695 
   695 
   696     typedef typename Parent::Node Node;
 
   696     typedef typename Parent::Node Node;
 
   697     typedef typename Parent::Arc Arc;
 
   697     typedef typename Parent::Arc Arc;
 
   698     typedef typename Parent::Edge Edge;
 
   698     typedef typename Parent::Edge Edge;
 
   699 
   699 
   700     typedef _Graph Graph;
 
   700     typedef GR Graph;
 
   701 
   701 
   702 
   702 
   703     typedef typename Parent::NodesImplBase NodesImplBase;
 
   703     typedef typename Parent::NodesImplBase NodesImplBase;
 
   704 
   704 
   705     void eraseNode(const Node& node) {
 
   705     void eraseNode(const Node& node) {
 
   718 
   718 
   719     class NodesImpl : public NodesImplBase {
 
   719     class NodesImpl : public NodesImplBase {
 
   720     public:
 
   720     public:
 
   721       typedef NodesImplBase Parent;
 
   721       typedef NodesImplBase Parent;
 
   722 
   722 
   723       NodesImpl(const Graph& graph, ListEdgeSet& arcset)
 
   723       NodesImpl(const GR& graph, ListEdgeSet& arcset)
 
   724         : Parent(graph), _arcset(arcset) {}
 
   724         : Parent(graph), _arcset(arcset) {}
 
   725 
   725 
   726       virtual ~NodesImpl() {}
 
   726       virtual ~NodesImpl() {}
 
   727 
   727 
   728     protected:
 
   728     protected:
 
   744 
   744 
   745     private:
 
   745     private:
 
   746       ListEdgeSet& _arcset;
 
   746       ListEdgeSet& _arcset;
 
   747     };
 
   747     };
 
   748 
   748 
   749     NodesImpl nodes;
 
   749     NodesImpl _nodes;
 
   750 
   750 
   751   public:
 
   751   public:
 
   752 
   752 
   753     /// \brief Constructor of the EdgeSet.
 
   753     /// \brief Constructor of the EdgeSet.
 
   754     ///
 
   754     ///
 
   755     /// Constructor of the EdgeSet.
 
   755     /// Constructor of the EdgeSet.
 
   756     ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
 
   756     ListEdgeSet(const GR& graph) : _nodes(graph, *this) {
 
   757       Parent::initalize(graph, nodes);
 
   757       Parent::initalize(graph, _nodes);
 
   758     }
 
   758     }
 
   759 
   759 
   760     /// \brief Add a new edge to the graph.
 
   760     /// \brief Add a new edge to the graph.
 
   761     ///
 
   761     ///
 
   762     /// Add a new edge to the graph with node \c u
 
   762     /// Add a new edge to the graph with node \c u
 
   773       return Parent::erase(e);
 
   773       return Parent::erase(e);
 
   774     }
 
   774     }
 
   775 
   775 
   776   };
 
   776   };
 
   777 
   777 
   778   template <typename _Graph>
 
   778   template <typename GR>
 
   779   class SmartArcSetBase {
 
   779   class SmartArcSetBase {
 
   780   public:
 
   780   public:
 
   781 
   781 
   782     typedef _Graph Graph;
 
   782     typedef GR Graph;
 
   783     typedef typename Graph::Node Node;
 
   783     typedef typename Graph::Node Node;
 
   784     typedef typename Graph::NodeIt NodeIt;
 
   784     typedef typename Graph::NodeIt NodeIt;
 
   785 
   785 
   786   protected:
 
   786   protected:
 
   787 
   787 
   788     struct NodeT {
 
   788     struct NodeT {
 
   789       int first_out, first_in;
 
   789       int first_out, first_in;
 
   790       NodeT() : first_out(-1), first_in(-1) {}
 
   790       NodeT() : first_out(-1), first_in(-1) {}
 
   791     };
 
   791     };
 
   792 
   792 
   793     typedef typename ItemSetTraits<Graph, Node>::
 
   793     typedef typename ItemSetTraits<GR, Node>::
 
   794     template Map<NodeT>::Type NodesImplBase;
 
   794     template Map<NodeT>::Type NodesImplBase;
 
   795 
   795 
   796     NodesImplBase* nodes;
 
   796     NodesImplBase* _nodes;
 
   797 
   797 
   798     struct ArcT {
 
   798     struct ArcT {
 
   799       Node source, target;
 
   799       Node source, target;
 
   800       int next_out, next_in;
 
   800       int next_out, next_in;
 
   801       ArcT() {}
 
   801       ArcT() {}
 
   802     };
 
   802     };
 
   803 
   803 
   804     std::vector<ArcT> arcs;
 
   804     std::vector<ArcT> arcs;
 
   805 
   805 
   806     const Graph* graph;
 
   806     const GR* _graph;
 
   807 
   807 
   808     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
 
   808     void initalize(const GR& graph, NodesImplBase& nodes) {
 
   809       graph = &_graph;
 
   809       _graph = &graph;
 
   810       nodes = &_nodes;
 
   810       _nodes = &nodes;
 
   811     }
 
   811     }
 
   812 
   812 
   813   public:
 
   813   public:
 
   814 
   814 
   815     class Arc {
 
   815     class Arc {
 
   816       friend class SmartArcSetBase<Graph>;
 
   816       friend class SmartArcSetBase<GR>;
 
   817     protected:
 
   817     protected:
 
   818       Arc(int _id) : id(_id) {}
 
   818       Arc(int _id) : id(_id) {}
 
   819       int id;
 
   819       int id;
 
   820     public:
 
   820     public:
 
   821       Arc() {}
 
   821       Arc() {}
 
   828     SmartArcSetBase() {}
 
   828     SmartArcSetBase() {}
 
   829 
   829 
   830     Arc addArc(const Node& u, const Node& v) {
 
   830     Arc addArc(const Node& u, const Node& v) {
 
   831       int n = arcs.size();
 
   831       int n = arcs.size();
 
   832       arcs.push_back(ArcT());
 
   832       arcs.push_back(ArcT());
 
   833       arcs[n].next_in = (*nodes)[v].first_in;
 
   833       arcs[n].next_in = (*_nodes)[v].first_in;
 
   834       (*nodes)[v].first_in = n;
 
   834       (*_nodes)[v].first_in = n;
 
   835       arcs[n].next_out = (*nodes)[u].first_out;
 
   835       arcs[n].next_out = (*_nodes)[u].first_out;
 
   836       (*nodes)[u].first_out = n;
 
   836       (*_nodes)[u].first_out = n;
 
   837       arcs[n].source = u;
 
   837       arcs[n].source = u;
 
   838       arcs[n].target = v;
 
   838       arcs[n].target = v;
 
   839       return Arc(n);
 
   839       return Arc(n);
 
   840     }
 
   840     }
 
   841 
   841 
   842     void clear() {
 
   842     void clear() {
 
   843       Node node;
 
   843       Node node;
 
   844       for (first(node); node != INVALID; next(node)) {
 
   844       for (first(node); node != INVALID; next(node)) {
 
   845         (*nodes)[node].first_in = -1;
 
   845         (*_nodes)[node].first_in = -1;
 
   846         (*nodes)[node].first_out = -1;
 
   846         (*_nodes)[node].first_out = -1;
 
   847       }
 
   847       }
 
   848       arcs.clear();
 
   848       arcs.clear();
 
   849     }
 
   849     }
 
   850 
   850 
   851     void first(Node& node) const {
 
   851     void first(Node& node) const {
 
   852       graph->first(node);
 
   852       _graph->first(node);
 
   853     }
 
   853     }
 
   854 
   854 
   855     void next(Node& node) const {
 
   855     void next(Node& node) const {
 
   856       graph->next(node);
 
   856       _graph->next(node);
 
   857     }
 
   857     }
 
   858 
   858 
   859     void first(Arc& arc) const {
 
   859     void first(Arc& arc) const {
 
   860       arc.id = arcs.size() - 1;
 
   860       arc.id = arcs.size() - 1;
 
   861     }
 
   861     }
 
   863     void next(Arc& arc) const {
 
   863     void next(Arc& arc) const {
 
   864       --arc.id;
 
   864       --arc.id;
 
   865     }
 
   865     }
 
   866 
   866 
   867     void firstOut(Arc& arc, const Node& node) const {
 
   867     void firstOut(Arc& arc, const Node& node) const {
 
   868       arc.id = (*nodes)[node].first_out;
 
   868       arc.id = (*_nodes)[node].first_out;
 
   869     }
 
   869     }
 
   870 
   870 
   871     void nextOut(Arc& arc) const {
 
   871     void nextOut(Arc& arc) const {
 
   872       arc.id = arcs[arc.id].next_out;
 
   872       arc.id = arcs[arc.id].next_out;
 
   873     }
 
   873     }
 
   874 
   874 
   875     void firstIn(Arc& arc, const Node& node) const {
 
   875     void firstIn(Arc& arc, const Node& node) const {
 
   876       arc.id = (*nodes)[node].first_in;
 
   876       arc.id = (*_nodes)[node].first_in;
 
   877     }
 
   877     }
 
   878 
   878 
   879     void nextIn(Arc& arc) const {
 
   879     void nextIn(Arc& arc) const {
 
   880       arc.id = arcs[arc.id].next_in;
 
   880       arc.id = arcs[arc.id].next_in;
 
   881     }
 
   881     }
 
   882 
   882 
   883     int id(const Node& node) const { return graph->id(node); }
 
   883     int id(const Node& node) const { return _graph->id(node); }
 
   884     int id(const Arc& arc) const { return arc.id; }
 
   884     int id(const Arc& arc) const { return arc.id; }
 
   885 
   885 
   886     Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
 
   886     Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
 
   887     Arc arcFromId(int ix) const { return Arc(ix); }
 
   887     Arc arcFromId(int ix) const { return Arc(ix); }
 
   888 
   888 
   889     int maxNodeId() const { return graph->maxNodeId(); };
 
   889     int maxNodeId() const { return _graph->maxNodeId(); };
 
   890     int maxArcId() const { return arcs.size() - 1; }
 
   890     int maxArcId() const { return arcs.size() - 1; }
 
   891 
   891 
   892     Node source(const Arc& arc) const { return arcs[arc.id].source;}
 
   892     Node source(const Arc& arc) const { return arcs[arc.id].source;}
 
   893     Node target(const Arc& arc) const { return arcs[arc.id].target;}
 
   893     Node target(const Arc& arc) const { return arcs[arc.id].target;}
 
   894 
   894 
   895     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
 
   895     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 
   896 
   896 
   897     NodeNotifier& notifier(Node) const {
 
   897     NodeNotifier& notifier(Node) const {
 
   898       return graph->notifier(Node());
 
   898       return _graph->notifier(Node());
 
   899     }
 
   899     }
 
   900 
   900 
   901     template <typename _Value>
 
   901     template <typename V>
 
   902     class NodeMap : public Graph::template NodeMap<_Value> {
 
   902     class NodeMap : public GR::template NodeMap<V> {
 
   903     public:
 
   903     public:
 
   904 
   904 
   905       typedef typename _Graph::template NodeMap<_Value> Parent;
 
   905       typedef typename GR::template NodeMap<V> Parent;
 
   906 
   906 
   907       explicit NodeMap(const SmartArcSetBase<Graph>& arcset)
 
   907       explicit NodeMap(const SmartArcSetBase<GR>& arcset)
 
   908         : Parent(*arcset.graph) { }
 
   908         : Parent(*arcset._graph) { }
 
   909 
   909 
   910       NodeMap(const SmartArcSetBase<Graph>& arcset, const _Value& value)
 
   910       NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
 
   911         : Parent(*arcset.graph, value) { }
 
   911         : Parent(*arcset._graph, value) { }
 
   912 
   912 
   913       NodeMap& operator=(const NodeMap& cmap) {
 
   913       NodeMap& operator=(const NodeMap& cmap) {
 
   914         return operator=<NodeMap>(cmap);
 
   914         return operator=<NodeMap>(cmap);
 
   915       }
 
   915       }
 
   916 
   916 
   935   /// original graph is valid in this arc set, therefore the node
 
   935   /// original graph is valid in this arc set, therefore the node
 
   936   /// objects of the original graph can be used directly with this
 
   936   /// objects of the original graph can be used directly with this
 
   937   /// class. The node handling functions (id handling, observing, and
 
   937   /// class. The node handling functions (id handling, observing, and
 
   938   /// iterators) works equivalently as in the original graph.
 
   938   /// iterators) works equivalently as in the original graph.
 
   939   ///
 
   939   ///
 
   940   /// \param _Graph The type of the graph which shares its node set with
 
   940   /// \param GR The type of the graph which shares its node set with
 
   941   /// this class. Its interface must conform to the
 
   941   /// this class. Its interface must conform to the
 
   942   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 
   942   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 
   943   /// concept.
 
   943   /// concept.
 
   944   ///
 
   944   ///
 
   945   /// This implementation is slightly faster than the \c ListArcSet,
 
   945   /// This implementation is slightly faster than the \c ListArcSet,
 
   952   /// the arc set is invalidated, and it cannot be used anymore. The
 
   952   /// the arc set is invalidated, and it cannot be used anymore. The
 
   953   /// validity can be checked with the \c valid() member function.
 
   953   /// validity can be checked with the \c valid() member function.
 
   954   ///
 
   954   ///
 
   955   /// This class is fully conform to the \ref concepts::Digraph
 
   955   /// This class is fully conform to the \ref concepts::Digraph
 
   956   /// "Digraph" concept.
 
   956   /// "Digraph" concept.
 
   957   template <typename _Graph>
 
   957   template <typename GR>
 
   958   class SmartArcSet : public ArcSetExtender<SmartArcSetBase<_Graph> > {
 
   958   class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
 
   959 
   959 
   960   public:
 
   960   public:
 
   961 
   961 
   962     typedef ArcSetExtender<SmartArcSetBase<_Graph> > Parent;
 
   962     typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
 
   963 
   963 
   964     typedef typename Parent::Node Node;
 
   964     typedef typename Parent::Node Node;
 
   965     typedef typename Parent::Arc Arc;
 
   965     typedef typename Parent::Arc Arc;
 
   966 
   966 
   967     typedef _Graph Graph;
 
   967     typedef GR Graph;
 
   968 
   968 
   969   protected:
 
   969   protected:
 
   970 
   970 
   971     typedef typename Parent::NodesImplBase NodesImplBase;
 
   971     typedef typename Parent::NodesImplBase NodesImplBase;
 
   972 
   972 
   984 
   984 
   985     class NodesImpl : public NodesImplBase {
 
   985     class NodesImpl : public NodesImplBase {
 
   986     public:
 
   986     public:
 
   987       typedef NodesImplBase Parent;
 
   987       typedef NodesImplBase Parent;
 
   988 
   988 
   989       NodesImpl(const Graph& graph, SmartArcSet& arcset)
 
   989       NodesImpl(const GR& graph, SmartArcSet& arcset)
 
   990         : Parent(graph), _arcset(arcset) {}
 
   990         : Parent(graph), _arcset(arcset) {}
 
   991 
   991 
   992       virtual ~NodesImpl() {}
 
   992       virtual ~NodesImpl() {}
 
   993 
   993 
   994       bool attached() const {
 
   994       bool attached() const {
 
  1024 
  1024 
  1025     private:
 
  1025     private:
 
  1026       SmartArcSet& _arcset;
 
  1026       SmartArcSet& _arcset;
 
  1027     };
 
  1027     };
 
  1028 
  1028 
  1029     NodesImpl nodes;
 
  1029     NodesImpl _nodes;
 
  1030 
  1030 
  1031   public:
 
  1031   public:
 
  1032 
  1032 
  1033     /// \brief Constructor of the ArcSet.
 
  1033     /// \brief Constructor of the ArcSet.
 
  1034     ///
 
  1034     ///
 
  1035     /// Constructor of the ArcSet.
 
  1035     /// Constructor of the ArcSet.
 
  1036     SmartArcSet(const Graph& graph) : nodes(graph, *this) {
 
  1036     SmartArcSet(const GR& graph) : _nodes(graph, *this) {
 
  1037       Parent::initalize(graph, nodes);
 
  1037       Parent::initalize(graph, _nodes);
 
  1038     }
 
  1038     }
 
  1039 
  1039 
  1040     /// \brief Add a new arc to the digraph.
 
  1040     /// \brief Add a new arc to the digraph.
 
  1041     ///
 
  1041     ///
 
  1042     /// Add a new arc to the digraph with source node \c s
 
  1042     /// Add a new arc to the digraph with source node \c s
 
  1050     ///
 
  1050     ///
 
  1051     /// This functions gives back false if the ArcSet is
 
  1051     /// This functions gives back false if the ArcSet is
 
  1052     /// invalidated. It occurs when a node in the underlying graph is
 
  1052     /// invalidated. It occurs when a node in the underlying graph is
 
  1053     /// erased and it is not isolated in the ArcSet.
 
  1053     /// erased and it is not isolated in the ArcSet.
 
  1054     bool valid() const {
 
  1054     bool valid() const {
 
  1055       return nodes.attached();
 
  1055       return _nodes.attached();
 
  1056     }
 
  1056     }
 
  1057 
  1057 
  1058   };
 
  1058   };
 
  1059 
  1059 
  1060 
  1060 
  1061   template <typename _Graph>
 
  1061   template <typename GR>
 
  1062   class SmartEdgeSetBase {
 
  1062   class SmartEdgeSetBase {
 
  1063   public:
 
  1063   public:
 
  1064 
  1064 
  1065     typedef _Graph Graph;
 
  1065     typedef GR Graph;
 
  1066     typedef typename Graph::Node Node;
 
  1066     typedef typename GR::Node Node;
 
  1067     typedef typename Graph::NodeIt NodeIt;
 
  1067     typedef typename GR::NodeIt NodeIt;
 
  1068 
  1068 
  1069   protected:
 
  1069   protected:
 
  1070 
  1070 
  1071     struct NodeT {
 
  1071     struct NodeT {
 
  1072       int first_out;
 
  1072       int first_out;
 
  1073       NodeT() : first_out(-1) {}
 
  1073       NodeT() : first_out(-1) {}
 
  1074     };
 
  1074     };
 
  1075 
  1075 
  1076     typedef typename ItemSetTraits<Graph, Node>::
 
  1076     typedef typename ItemSetTraits<GR, Node>::
 
  1077     template Map<NodeT>::Type NodesImplBase;
 
  1077     template Map<NodeT>::Type NodesImplBase;
 
  1078 
  1078 
  1079     NodesImplBase* nodes;
 
  1079     NodesImplBase* _nodes;
 
  1080 
  1080 
  1081     struct ArcT {
 
  1081     struct ArcT {
 
  1082       Node target;
 
  1082       Node target;
 
  1083       int next_out;
 
  1083       int next_out;
 
  1084       ArcT() {}
 
  1084       ArcT() {}
 
  1085     };
 
  1085     };
 
  1086 
  1086 
  1087     std::vector<ArcT> arcs;
 
  1087     std::vector<ArcT> arcs;
 
  1088 
  1088 
  1089     const Graph* graph;
 
  1089     const GR* _graph;
 
  1090 
  1090 
  1091     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
 
  1091     void initalize(const GR& graph, NodesImplBase& nodes) {
 
  1092       graph = &_graph;
 
  1092       _graph = &graph;
 
  1093       nodes = &_nodes;
 
  1093       _nodes = &nodes;
 
  1094     }
 
  1094     }
 
  1095 
  1095 
  1096   public:
 
  1096   public:
 
  1097 
  1097 
  1098     class Edge {
 
  1098     class Edge {
 
  1133       arcs.push_back(ArcT());
 
  1133       arcs.push_back(ArcT());
 
  1134 
  1134 
  1135       arcs[n].target = u;
 
  1135       arcs[n].target = u;
 
  1136       arcs[n | 1].target = v;
 
  1136       arcs[n | 1].target = v;
 
  1137 
  1137 
  1138       arcs[n].next_out = (*nodes)[v].first_out;
 
  1138       arcs[n].next_out = (*_nodes)[v].first_out;
 
  1139       (*nodes)[v].first_out = n;
 
  1139       (*_nodes)[v].first_out = n;
 
  1140 
  1140 
  1141       arcs[n | 1].next_out = (*nodes)[u].first_out;
 
  1141       arcs[n | 1].next_out = (*_nodes)[u].first_out;
 
  1142       (*nodes)[u].first_out = (n | 1);
 
  1142       (*_nodes)[u].first_out = (n | 1);
 
  1143 
  1143 
  1144       return Edge(n / 2);
 
  1144       return Edge(n / 2);
 
  1145     }
 
  1145     }
 
  1146 
  1146 
  1147     void clear() {
 
  1147     void clear() {
 
  1148       Node node;
 
  1148       Node node;
 
  1149       for (first(node); node != INVALID; next(node)) {
 
  1149       for (first(node); node != INVALID; next(node)) {
 
  1150         (*nodes)[node].first_out = -1;
 
  1150         (*_nodes)[node].first_out = -1;
 
  1151       }
 
  1151       }
 
  1152       arcs.clear();
 
  1152       arcs.clear();
 
  1153     }
 
  1153     }
 
  1154 
  1154 
  1155     void first(Node& node) const {
 
  1155     void first(Node& node) const {
 
  1156       graph->first(node);
 
  1156       _graph->first(node);
 
  1157     }
 
  1157     }
 
  1158 
  1158 
  1159     void next(Node& node) const {
 
  1159     void next(Node& node) const {
 
  1160       graph->next(node);
 
  1160       _graph->next(node);
 
  1161     }
 
  1161     }
 
  1162 
  1162 
  1163     void first(Arc& arc) const {
 
  1163     void first(Arc& arc) const {
 
  1164       arc.id = arcs.size() - 1;
 
  1164       arc.id = arcs.size() - 1;
 
  1165     }
 
  1165     }
 
  1175     void next(Edge& arc) const {
 
  1175     void next(Edge& arc) const {
 
  1176       --arc.id;
 
  1176       --arc.id;
 
  1177     }
 
  1177     }
 
  1178 
  1178 
  1179     void firstOut(Arc& arc, const Node& node) const {
 
  1179     void firstOut(Arc& arc, const Node& node) const {
 
  1180       arc.id = (*nodes)[node].first_out;
 
  1180       arc.id = (*_nodes)[node].first_out;
 
  1181     }
 
  1181     }
 
  1182 
  1182 
  1183     void nextOut(Arc& arc) const {
 
  1183     void nextOut(Arc& arc) const {
 
  1184       arc.id = arcs[arc.id].next_out;
 
  1184       arc.id = arcs[arc.id].next_out;
 
  1185     }
 
  1185     }
 
  1186 
  1186 
  1187     void firstIn(Arc& arc, const Node& node) const {
 
  1187     void firstIn(Arc& arc, const Node& node) const {
 
  1188       arc.id = (((*nodes)[node].first_out) ^ 1);
 
  1188       arc.id = (((*_nodes)[node].first_out) ^ 1);
 
  1189       if (arc.id == -2) arc.id = -1;
 
  1189       if (arc.id == -2) arc.id = -1;
 
  1190     }
 
  1190     }
 
  1191 
  1191 
  1192     void nextIn(Arc& arc) const {
 
  1192     void nextIn(Arc& arc) const {
 
  1193       arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
 
  1193       arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
 
  1194       if (arc.id == -2) arc.id = -1;
 
  1194       if (arc.id == -2) arc.id = -1;
 
  1195     }
 
  1195     }
 
  1196 
  1196 
  1197     void firstInc(Edge &arc, bool& dir, const Node& node) const {
 
  1197     void firstInc(Edge &arc, bool& dir, const Node& node) const {
 
  1198       int de = (*nodes)[node].first_out;
 
  1198       int de = (*_nodes)[node].first_out;
 
  1199       if (de != -1 ) {
 
  1199       if (de != -1 ) {
 
  1200         arc.id = de / 2;
 
  1200         arc.id = de / 2;
 
  1201         dir = ((de & 1) == 1);
 
  1201         dir = ((de & 1) == 1);
 
  1202       } else {
 
  1202       } else {
 
  1203         arc.id = -1;
 
  1203         arc.id = -1;
 
  1221 
  1221 
  1222     static Arc direct(Edge edge, bool dir) {
 
  1222     static Arc direct(Edge edge, bool dir) {
 
  1223       return Arc(edge.id * 2 + (dir ? 1 : 0));
 
  1223       return Arc(edge.id * 2 + (dir ? 1 : 0));
 
  1224     }
 
  1224     }
 
  1225 
  1225 
  1226     int id(Node node) const { return graph->id(node); }
 
  1226     int id(Node node) const { return _graph->id(node); }
 
  1227     static int id(Arc arc) { return arc.id; }
 
  1227     static int id(Arc arc) { return arc.id; }
 
  1228     static int id(Edge arc) { return arc.id; }
 
  1228     static int id(Edge arc) { return arc.id; }
 
  1229 
  1229 
  1230     Node nodeFromId(int id) const { return graph->nodeFromId(id); }
 
  1230     Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
 
  1231     static Arc arcFromId(int id) { return Arc(id); }
 
  1231     static Arc arcFromId(int id) { return Arc(id); }
 
  1232     static Edge edgeFromId(int id) { return Edge(id);}
 
  1232     static Edge edgeFromId(int id) { return Edge(id);}
 
  1233 
  1233 
  1234     int maxNodeId() const { return graph->maxNodeId(); };
 
  1234     int maxNodeId() const { return _graph->maxNodeId(); };
 
  1235     int maxArcId() const { return arcs.size() - 1; }
 
  1235     int maxArcId() const { return arcs.size() - 1; }
 
  1236     int maxEdgeId() const { return arcs.size() / 2 - 1; }
 
  1236     int maxEdgeId() const { return arcs.size() / 2 - 1; }
 
  1237 
  1237 
  1238     Node source(Arc e) const { return arcs[e.id ^ 1].target; }
 
  1238     Node source(Arc e) const { return arcs[e.id ^ 1].target; }
 
  1239     Node target(Arc e) const { return arcs[e.id].target; }
 
  1239     Node target(Arc e) const { return arcs[e.id].target; }
 
  1240 
  1240 
  1241     Node u(Edge e) const { return arcs[2 * e.id].target; }
 
  1241     Node u(Edge e) const { return arcs[2 * e.id].target; }
 
  1242     Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
 
  1242     Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
 
  1243 
  1243 
  1244     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
 
  1244     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 
  1245 
  1245 
  1246     NodeNotifier& notifier(Node) const {
 
  1246     NodeNotifier& notifier(Node) const {
 
  1247       return graph->notifier(Node());
 
  1247       return _graph->notifier(Node());
 
  1248     }
 
  1248     }
 
  1249 
  1249 
  1250     template <typename _Value>
 
  1250     template <typename V>
 
  1251     class NodeMap : public Graph::template NodeMap<_Value> {
 
  1251     class NodeMap : public GR::template NodeMap<V> {
 
  1252     public:
 
  1252     public:
 
  1253 
  1253 
  1254       typedef typename _Graph::template NodeMap<_Value> Parent;
 
  1254       typedef typename GR::template NodeMap<V> Parent;
 
  1255 
  1255 
  1256       explicit NodeMap(const SmartEdgeSetBase<Graph>& arcset)
 
  1256       explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
 
  1257         : Parent(*arcset.graph) { }
 
  1257         : Parent(*arcset._graph) { }
 
  1258 
  1258 
  1259       NodeMap(const SmartEdgeSetBase<Graph>& arcset, const _Value& value)
 
  1259       NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
 
  1260         : Parent(*arcset.graph, value) { }
 
  1260         : Parent(*arcset._graph, value) { }
 
  1261 
  1261 
  1262       NodeMap& operator=(const NodeMap& cmap) {
 
  1262       NodeMap& operator=(const NodeMap& cmap) {
 
  1263         return operator=<NodeMap>(cmap);
 
  1263         return operator=<NodeMap>(cmap);
 
  1264       }
 
  1264       }
 
  1265 
  1265 
  1283   /// graph is valid in this arc set, therefore the node objects of
 
  1283   /// graph is valid in this arc set, therefore the node objects of
 
  1284   /// the original graph can be used directly with this class. The
 
  1284   /// the original graph can be used directly with this class. The
 
  1285   /// node handling functions (id handling, observing, and iterators)
 
  1285   /// node handling functions (id handling, observing, and iterators)
 
  1286   /// works equivalently as in the original graph.
 
  1286   /// works equivalently as in the original graph.
 
  1287   ///
 
  1287   ///
 
  1288   /// \param _Graph The type of the graph which shares its node set
 
  1288   /// \param GR The type of the graph which shares its node set
 
  1289   /// with this class. Its interface must conform to the
 
  1289   /// with this class. Its interface must conform to the
 
  1290   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 
  1290   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 
  1291   ///  concept.
 
  1291   ///  concept.
 
  1292   ///
 
  1292   ///
 
  1293   /// This implementation is slightly faster than the \c ListEdgeSet,
 
  1293   /// This implementation is slightly faster than the \c ListEdgeSet,
 
  1300   /// is invalidated, and it cannot be used anymore. The validity can
 
  1300   /// is invalidated, and it cannot be used anymore. The validity can
 
  1301   /// be checked with the \c valid() member function.
 
  1301   /// be checked with the \c valid() member function.
 
  1302   ///
 
  1302   ///
 
  1303   /// This class is fully conform to the \ref concepts::Graph
 
  1303   /// This class is fully conform to the \ref concepts::Graph
 
  1304   /// "Graph" concept.
 
  1304   /// "Graph" concept.
 
  1305   template <typename _Graph>
 
  1305   template <typename GR>
 
  1306   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
 
  1306   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
 
  1307 
  1307 
  1308   public:
 
  1308   public:
 
  1309 
  1309 
  1310     typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
 
  1310     typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
 
  1311 
  1311 
  1312     typedef typename Parent::Node Node;
 
  1312     typedef typename Parent::Node Node;
 
  1313     typedef typename Parent::Arc Arc;
 
  1313     typedef typename Parent::Arc Arc;
 
  1314     typedef typename Parent::Edge Edge;
 
  1314     typedef typename Parent::Edge Edge;
 
  1315 
  1315 
  1316     typedef _Graph Graph;
 
  1316     typedef GR Graph;
 
  1317 
  1317 
  1318   protected:
 
  1318   protected:
 
  1319 
  1319 
  1320     typedef typename Parent::NodesImplBase NodesImplBase;
 
  1320     typedef typename Parent::NodesImplBase NodesImplBase;
 
  1321 
  1321 
  1332 
  1332 
  1333     class NodesImpl : public NodesImplBase {
 
  1333     class NodesImpl : public NodesImplBase {
 
  1334     public:
 
  1334     public:
 
  1335       typedef NodesImplBase Parent;
 
  1335       typedef NodesImplBase Parent;
 
  1336 
  1336 
  1337       NodesImpl(const Graph& graph, SmartEdgeSet& arcset)
 
  1337       NodesImpl(const GR& graph, SmartEdgeSet& arcset)
 
  1338         : Parent(graph), _arcset(arcset) {}
 
  1338         : Parent(graph), _arcset(arcset) {}
 
  1339 
  1339 
  1340       virtual ~NodesImpl() {}
 
  1340       virtual ~NodesImpl() {}
 
  1341 
  1341 
  1342       bool attached() const {
 
  1342       bool attached() const {
 
  1372 
  1372 
  1373     private:
 
  1373     private:
 
  1374       SmartEdgeSet& _arcset;
 
  1374       SmartEdgeSet& _arcset;
 
  1375     };
 
  1375     };
 
  1376 
  1376 
  1377     NodesImpl nodes;
 
  1377     NodesImpl _nodes;
 
  1378 
  1378 
  1379   public:
 
  1379   public:
 
  1380 
  1380 
  1381     /// \brief Constructor of the EdgeSet.
 
  1381     /// \brief Constructor of the EdgeSet.
 
  1382     ///
 
  1382     ///
 
  1383     /// Constructor of the EdgeSet.
 
  1383     /// Constructor of the EdgeSet.
 
  1384     SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
 
  1384     SmartEdgeSet(const GR& graph) : _nodes(graph, *this) {
 
  1385       Parent::initalize(graph, nodes);
 
  1385       Parent::initalize(graph, _nodes);
 
  1386     }
 
  1386     }
 
  1387 
  1387 
  1388     /// \brief Add a new edge to the graph.
 
  1388     /// \brief Add a new edge to the graph.
 
  1389     ///
 
  1389     ///
 
  1390     /// Add a new edge to the graph with node \c u
 
  1390     /// Add a new edge to the graph with node \c u
 
  1398     ///
 
  1398     ///
 
  1399     /// This functions gives back false if the EdgeSet is
 
  1399     /// This functions gives back false if the EdgeSet is
 
  1400     /// invalidated. It occurs when a node in the underlying graph is
 
  1400     /// invalidated. It occurs when a node in the underlying graph is
 
  1401     /// erased and it is not isolated in the EdgeSet.
 
  1401     /// erased and it is not isolated in the EdgeSet.
 
  1402     bool valid() const {
 
  1402     bool valid() const {
 
  1403       return nodes.attached();
 
  1403       return _nodes.attached();
 
  1404     }
 
  1404     }
 
  1405 
  1405 
  1406   };
 
  1406   };
 
  1407 
  1407 
  1408 }
 
  1408 }
lemon-main