lemon/list_graph.h
author deba
Fri, 24 Feb 2006 11:02:11 +0000
changeset 1983 a60527609489
parent 1979 c2992fd74dad
child 1984 d4cbd10e1256
permissions -rw-r--r--
Bugfix
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_LIST_GRAPH_H
    20 #define LEMON_LIST_GRAPH_H
    21 
    22 ///\ingroup graphs
    23 ///\file
    24 ///\brief ListGraph, ListUGraph classes.
    25 
    26 #include <lemon/bits/graph_extender.h>
    27 
    28 #include <lemon/error.h>
    29 
    30 #include <vector>
    31 #include <list>
    32 
    33 namespace lemon {
    34 
    35   class ListGraphBase {
    36 
    37   protected:
    38     struct NodeT {
    39       int first_in, first_out;
    40       int prev, next;
    41     };
    42  
    43     struct EdgeT {
    44       int target, source;
    45       int prev_in, prev_out;
    46       int next_in, next_out;
    47     };
    48 
    49     std::vector<NodeT> nodes;
    50 
    51     int first_node;
    52 
    53     int first_free_node;
    54 
    55     std::vector<EdgeT> edges;
    56 
    57     int first_free_edge;
    58     
    59   public:
    60     
    61     typedef ListGraphBase Graph;
    62     
    63     class Node {
    64       friend class ListGraphBase;
    65     protected:
    66 
    67       int id;
    68       Node(int pid) { id = pid;}
    69 
    70     public:
    71       Node() {}
    72       Node (Invalid) { id = -1; }
    73       bool operator==(const Node& node) const {return id == node.id;}
    74       bool operator!=(const Node& node) const {return id != node.id;}
    75       bool operator<(const Node& node) const {return id < node.id;}
    76     };
    77 
    78     class Edge {
    79       friend class ListGraphBase;
    80     protected:
    81 
    82       int id;
    83       Edge(int pid) { id = pid;}
    84 
    85     public:
    86       Edge() {}
    87       Edge (Invalid) { id = -1; }
    88       bool operator==(const Edge& edge) const {return id == edge.id;}
    89       bool operator!=(const Edge& edge) const {return id != edge.id;}
    90       bool operator<(const Edge& edge) const {return id < edge.id;}
    91     };
    92 
    93 
    94 
    95     ListGraphBase()
    96       : nodes(), first_node(-1),
    97 	first_free_node(-1), edges(), first_free_edge(-1) {}
    98 
    99     
   100     /// Maximum node ID.
   101     
   102     /// Maximum node ID.
   103     ///\sa id(Node)
   104     int maxNodeId() const { return nodes.size()-1; } 
   105 
   106     /// Maximum edge ID.
   107     
   108     /// Maximum edge ID.
   109     ///\sa id(Edge)
   110     int maxEdgeId() const { return edges.size()-1; }
   111 
   112     Node source(Edge e) const { return edges[e.id].source; }
   113     Node target(Edge e) const { return edges[e.id].target; }
   114 
   115 
   116     void first(Node& node) const { 
   117       node.id = first_node;
   118     }
   119 
   120     void next(Node& node) const {
   121       node.id = nodes[node.id].next;
   122     }
   123 
   124 
   125     void first(Edge& e) const { 
   126       int n;
   127       for(n = first_node; 
   128 	  n!=-1 && nodes[n].first_in == -1; 
   129 	  n = nodes[n].next);
   130       e.id = (n == -1) ? -1 : nodes[n].first_in;
   131     }
   132 
   133     void next(Edge& edge) const {
   134       if (edges[edge.id].next_in != -1) {
   135 	edge.id = edges[edge.id].next_in;
   136       } else {
   137 	int n;
   138 	for(n = nodes[edges[edge.id].target].next;
   139 	  n!=-1 && nodes[n].first_in == -1; 
   140 	  n = nodes[n].next);
   141 	edge.id = (n == -1) ? -1 : nodes[n].first_in;
   142       }      
   143     }
   144 
   145     void firstOut(Edge &e, const Node& v) const {
   146       e.id = nodes[v.id].first_out;
   147     }
   148     void nextOut(Edge &e) const {
   149       e.id=edges[e.id].next_out;
   150     }
   151 
   152     void firstIn(Edge &e, const Node& v) const {
   153       e.id = nodes[v.id].first_in;
   154     }
   155     void nextIn(Edge &e) const {
   156       e.id=edges[e.id].next_in;
   157     }
   158 
   159     
   160     static int id(Node v) { return v.id; }
   161     static int id(Edge e) { return e.id; }
   162 
   163     static Node nodeFromId(int id) { return Node(id);}
   164     static Edge edgeFromId(int id) { return Edge(id);}
   165 
   166     /// Adds a new node to the graph.
   167 
   168     /// \warning It adds the new node to the front of the list.
   169     /// (i.e. the lastly added node becomes the first.)
   170     Node addNode() {     
   171       int n;
   172       
   173       if(first_free_node==-1) {
   174 	n = nodes.size();
   175 	nodes.push_back(NodeT());
   176       } else {
   177 	n = first_free_node;
   178 	first_free_node = nodes[n].next;
   179       }
   180       
   181       nodes[n].next = first_node;
   182       if(first_node != -1) nodes[first_node].prev = n;
   183       first_node = n;
   184       nodes[n].prev = -1;
   185       
   186       nodes[n].first_in = nodes[n].first_out = -1;
   187       
   188       return Node(n);
   189     }
   190     
   191     Edge addEdge(Node u, Node v) {
   192       int n;      
   193 
   194       if (first_free_edge == -1) {
   195 	n = edges.size();
   196 	edges.push_back(EdgeT());
   197       } else {
   198 	n = first_free_edge;
   199 	first_free_edge = edges[n].next_in;
   200       }
   201       
   202       edges[n].source = u.id; 
   203       edges[n].target = v.id;
   204 
   205       edges[n].next_out = nodes[u.id].first_out;
   206       if(nodes[u.id].first_out != -1) {
   207 	edges[nodes[u.id].first_out].prev_out = n;
   208       }
   209       
   210       edges[n].next_in = nodes[v.id].first_in;
   211       if(nodes[v.id].first_in != -1) {
   212 	edges[nodes[v.id].first_in].prev_in = n;
   213       }
   214       
   215       edges[n].prev_in = edges[n].prev_out = -1;
   216 	
   217       nodes[u.id].first_out = nodes[v.id].first_in = n;
   218 
   219       return Edge(n);
   220     }
   221     
   222     void erase(const Node& node) {
   223       int n = node.id;
   224       
   225       if(nodes[n].next != -1) {
   226 	nodes[nodes[n].next].prev = nodes[n].prev;
   227       }
   228       
   229       if(nodes[n].prev != -1) {
   230 	nodes[nodes[n].prev].next = nodes[n].next;
   231       } else {
   232 	first_node = nodes[n].next;
   233       }
   234       
   235       nodes[n].next = first_free_node;
   236       first_free_node = n;
   237 
   238     }
   239     
   240     void erase(const Edge& edge) {
   241       int n = edge.id;
   242       
   243       if(edges[n].next_in!=-1) {
   244 	edges[edges[n].next_in].prev_in = edges[n].prev_in;
   245       }
   246 
   247       if(edges[n].prev_in!=-1) {
   248 	edges[edges[n].prev_in].next_in = edges[n].next_in;
   249       } else {
   250 	nodes[edges[n].target].first_in = edges[n].next_in;
   251       }
   252 
   253       
   254       if(edges[n].next_out!=-1) {
   255 	edges[edges[n].next_out].prev_out = edges[n].prev_out;
   256       } 
   257 
   258       if(edges[n].prev_out!=-1) {
   259 	edges[edges[n].prev_out].next_out = edges[n].next_out;
   260       } else {
   261 	nodes[edges[n].source].first_out = edges[n].next_out;
   262       }
   263       
   264       edges[n].next_in = first_free_edge;
   265       first_free_edge = n;      
   266 
   267     }
   268 
   269     void clear() {
   270       edges.clear();
   271       nodes.clear();
   272       first_node = first_free_node = first_free_edge = -1;
   273     }
   274 
   275   protected:
   276     void _changeTarget(Edge e, Node n) 
   277     {
   278       if(edges[e.id].next_in != -1)
   279 	edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
   280       if(edges[e.id].prev_in != -1)
   281 	edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
   282       else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
   283       if (nodes[n.id].first_in != -1) {
   284 	edges[nodes[n.id].first_in].prev_in = e.id;
   285       }
   286       edges[e.id].target = n.id;
   287       edges[e.id].prev_in = -1;
   288       edges[e.id].next_in = nodes[n.id].first_in;
   289       nodes[n.id].first_in = e.id;
   290     }
   291     void _changeSource(Edge e, Node n) 
   292     {
   293       if(edges[e.id].next_out != -1)
   294 	edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
   295       if(edges[e.id].prev_out != -1)
   296 	edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
   297       else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
   298       if (nodes[n.id].first_out != -1) {
   299 	edges[nodes[n.id].first_out].prev_out = e.id;
   300       }
   301       edges[e.id].source = n.id;
   302       edges[e.id].prev_out = -1;
   303       edges[e.id].next_out = nodes[n.id].first_out;
   304       nodes[n.id].first_out = e.id;
   305     }
   306 
   307   };
   308 
   309   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
   310 
   311   /// \addtogroup graphs
   312   /// @{
   313 
   314   ///A list graph class.
   315 
   316   ///This is a simple and fast erasable graph implementation.
   317   ///
   318   ///It addition that it conforms to the
   319   ///\ref concept::ErasableGraph "ErasableGraph" concept,
   320   ///it also provides several additional useful extra functionalities.
   321   ///\sa concept::ErasableGraph.
   322 
   323   class ListGraph : public ExtendedListGraphBase 
   324   {
   325   public:
   326     /// Changes the target of \c e to \c n
   327 
   328     /// Changes the target of \c e to \c n
   329     ///
   330     ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
   331     ///referencing the changed edge remain
   332     ///valid. However <tt>InEdge</tt>'s are invalidated.
   333     void changeTarget(Edge e, Node n) { 
   334       _changeTarget(e,n); 
   335     }
   336     /// Changes the source of \c e to \c n
   337 
   338     /// Changes the source of \c e to \c n
   339     ///
   340     ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
   341     ///referencing the changed edge remain
   342     ///valid. However <tt>OutEdge</tt>'s are invalidated.
   343     void changeSource(Edge e, Node n) { 
   344       _changeSource(e,n);
   345     }
   346 
   347     /// Invert the direction of an edge.
   348 
   349     ///\note The <tt>Edge</tt>'s
   350     ///referencing the changed edge remain
   351     ///valid. However <tt>OutEdge</tt>'s  and <tt>InEdge</tt>'s are invalidated.
   352     void reverseEdge(Edge e) {
   353       Node t=target(e);
   354       _changeTarget(e,source(e));
   355       _changeSource(e,t);
   356     }
   357 
   358     ///Using this it possible to avoid the superfluous memory allocation.
   359 
   360     ///Using this it possible to avoid the superfluous memory allocation.
   361     ///\todo more docs...
   362     void reserveEdge(int n) { edges.reserve(n); };
   363 
   364     ///Contract two nodes.
   365 
   366     ///This function contracts two nodes.
   367     ///
   368     ///Node \p b will be removed but instead of deleting
   369     ///its neighboring edges, they will be joined to \p a.
   370     ///The last parameter \p r controls whether to remove loops. \c true
   371     ///means that loops will be removed.
   372     ///
   373     ///\note The <tt>Edge</tt>s
   374     ///referencing a moved edge remain
   375     ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
   376     ///may be invalidated.
   377     void contract(Node a, Node b, bool r = true) 
   378     {
   379       for(OutEdgeIt e(*this,b);e!=INVALID;) {
   380 	OutEdgeIt f=e;
   381 	++f;
   382 	if(r && target(e)==a) erase(e);
   383 	else changeSource(e,a);
   384 	e=f;
   385       }
   386       for(InEdgeIt e(*this,b);e!=INVALID;) {
   387 	InEdgeIt f=e;
   388 	++f;
   389 	if(r && source(e)==a) erase(e);
   390 	else changeTarget(e,a);
   391 	e=f;
   392       }
   393       erase(b);
   394     }
   395 
   396     ///Split a node.
   397 
   398     ///This function splits a node. First a new node is added to the graph,
   399     ///then the source of each outgoing edge of \c n is moved to this new node.
   400     ///If \c connect is \c true (this is the default value), then a new edge
   401     ///from \c n to the newly created node is also added.
   402     ///\return The newly created node.
   403     ///
   404     ///\note The <tt>Edge</tt>s
   405     ///referencing a moved edge remain
   406     ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
   407     ///may be invalidated.
   408     ///\warning This functionality cannot be used together with the Snapshot
   409     ///feature.
   410     ///\todo It could be implemented in a bit faster way.
   411     Node split(Node n, bool connect = true) 
   412     {
   413       Node b = addNode();
   414       for(OutEdgeIt e(*this,n);e!=INVALID;) {
   415  	OutEdgeIt f=e;
   416 	++f;
   417 	changeSource(e,b);
   418 	e=f;
   419       }
   420       if(connect) addEdge(n,b);
   421       return b;
   422     }
   423       
   424     ///Split an edge.
   425 
   426     ///This function splits an edge. First a new node \c b is added to the graph,
   427     ///then the original edge is re-targetes to \c b. Finally an edge
   428     ///from \c b to the original target is added.
   429     ///\return The newly created node.
   430     ///\warning This functionality cannot be used together with the Snapshot
   431     ///feature.
   432     Node split(Edge e) 
   433     {
   434       Node b = addNode();
   435       addEdge(b,target(e));
   436       changeTarget(e,b);
   437       return b;
   438     }
   439       
   440     ///Class to make a snapshot of the graph and to restrore to it later.
   441 
   442     ///Class to make a snapshot of the graph and to restrore to it later.
   443     ///
   444     ///The newly added nodes and edges can be removed using the
   445     ///restore() function.
   446     ///
   447     ///\warning Edge and node deletions cannot be restored.
   448     ///\warning Snapshots cannot be nested.
   449     class Snapshot : protected AlterationNotifier<Node>::ObserverBase,
   450 		     protected AlterationNotifier<Edge>::ObserverBase
   451     {
   452     public:
   453       
   454       class UnsupportedOperation : public LogicError {
   455       public:
   456 	virtual const char* exceptionName() const {
   457 	  return "lemon::ListGraph::Snapshot::UnsupportedOperation";
   458 	}
   459       };
   460             
   461 
   462       protected:
   463       
   464       ListGraph *g;
   465       std::list<Node> added_nodes;
   466       std::list<Edge> added_edges;
   467       
   468       bool active;
   469       virtual void add(const Node& n) {
   470 	added_nodes.push_back(n);
   471       };
   472       virtual void erase(const Node&) 
   473       {
   474 	throw UnsupportedOperation();
   475       }
   476       virtual void add(const Edge& n) {
   477 	added_edges.push_back(n);
   478       };
   479       virtual void erase(const Edge&) 
   480       {
   481 	throw UnsupportedOperation();
   482       }
   483 
   484       ///\bug What is this used for?
   485       ///
   486       virtual void build() {}
   487       ///\bug What is this used for?
   488       ///
   489       virtual void clear() {}
   490 
   491       void regist(ListGraph &_g) {
   492 	g=&_g;
   493 	AlterationNotifier<Node>::ObserverBase::
   494 	  attach(g->getNotifier(Node()));
   495 	AlterationNotifier<Edge>::ObserverBase::
   496 	  attach(g->getNotifier(Edge()));
   497       }
   498             
   499       void deregist() {
   500 	AlterationNotifier<Node>::ObserverBase::
   501 	  detach();
   502 	AlterationNotifier<Edge>::ObserverBase::
   503 	  detach();
   504 	g=0;
   505       }
   506 
   507     public:
   508       ///Default constructur.
   509       
   510       ///Default constructur.
   511       ///To actually make a snapshot you must call save().
   512       ///
   513       Snapshot() : g(0) {}
   514       ///Constructor that immediately makes a snapshot.
   515       
   516       ///This constructor immediately makes a snapshot of the graph.
   517       ///\param _g The graph we make a snapshot of.
   518       Snapshot(ListGraph &_g) {
   519 	regist(_g);
   520       }
   521       ///\bug Is it necessary?
   522       ///
   523       ~Snapshot() 
   524       {
   525 	if(g) deregist();
   526       }
   527       
   528       ///Make a snapshot.
   529 
   530       ///Make a snapshot of the graph.
   531       ///
   532       ///This function can be called more than once. In case of a repeated
   533       ///call, the previous snapshot gets lost.
   534       ///\param _g The graph we make the snapshot of.
   535       void save(ListGraph &_g) 
   536       {
   537 	if(g!=&_g) {
   538 	  if(g) deregist();
   539 	  regist(_g);
   540 	}
   541 	added_nodes.clear();
   542 	added_edges.clear();
   543       }
   544       
   545     ///Undo the changes until the last snapshot.
   546 
   547     ///Undo the changes until last snapshot created by save().
   548     ///
   549     ///\todo This function might be called undo().
   550       void restore() {
   551 	ListGraph &old_g=*g;
   552 	deregist();
   553 	while(!added_edges.empty()) {
   554 	  old_g.erase(added_edges.front());
   555 	  added_edges.pop_front();
   556 	}
   557  	while(!added_nodes.empty()) {
   558 	  old_g.erase(added_nodes.front());
   559 	  added_nodes.pop_front();
   560 	}
   561       }
   562     };
   563     
   564   };
   565 
   566   ///@}
   567 
   568   /**************** Undirected List Graph ****************/
   569 
   570   typedef UGraphExtender<UGraphBaseExtender<
   571     ListGraphBase> > ExtendedListUGraphBase;
   572 
   573   /// \addtogroup graphs
   574   /// @{
   575 
   576   ///An undirected list graph class.
   577 
   578   ///This is a simple and fast erasable undirected graph implementation.
   579   ///
   580   ///It conforms to the
   581   ///\ref concept::UGraph "UGraph" concept.
   582   ///
   583   ///\sa concept::UGraph.
   584   ///
   585   ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
   586   ///haven't been implemented yet.
   587   ///
   588   class ListUGraph : public ExtendedListUGraphBase {
   589   public:
   590     typedef ExtendedListUGraphBase Parent;
   591     /// \brief Changes the target of \c e to \c n
   592     ///
   593     /// Changes the target of \c e to \c n
   594     ///
   595     /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
   596     /// referencing the changed edge remain
   597     /// valid. However <tt>InEdge</tt>'s are invalidated.
   598     void changeTarget(UEdge e, Node n) { 
   599       _changeTarget(e,n); 
   600     }
   601     /// Changes the source of \c e to \c n
   602     ///
   603     /// Changes the source of \c e to \c n
   604     ///
   605     ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
   606     ///referencing the changed edge remain
   607     ///valid. However <tt>OutEdge</tt>'s are invalidated.
   608     void changeSource(UEdge e, Node n) { 
   609       _changeSource(e,n); 
   610     }
   611     /// \brief Contract two nodes.
   612     ///
   613     /// This function contracts two nodes.
   614     ///
   615     /// Node \p b will be removed but instead of deleting
   616     /// its neighboring edges, they will be joined to \p a.
   617     /// The last parameter \p r controls whether to remove loops. \c true
   618     /// means that loops will be removed.
   619     ///
   620     /// \note The <tt>Edge</tt>s
   621     /// referencing a moved edge remain
   622     /// valid.
   623     void contract(Node a, Node b, bool r = true) {
   624       for(IncEdgeIt e(*this, b); e!=INVALID;) {
   625 	IncEdgeIt f = e; ++f;
   626 	if (r && runningNode(e) == a) {
   627 	  erase(e);
   628 	} else if (source(e) == b) {
   629 	  changeSource(e, a);
   630 	} else {
   631 	  changeTarget(e, a);
   632 	}
   633 	e = f;
   634       }
   635       erase(b);
   636     }
   637   };
   638 
   639 
   640   class ListBpUGraphBase {
   641   public:
   642 
   643     class NodeSetError : public LogicError {
   644       virtual const char* exceptionName() const { 
   645 	return "lemon::ListBpUGraph::NodeSetError";
   646       }
   647     };
   648 
   649   protected:
   650 
   651     struct NodeT {
   652       int first_edge, next_node;
   653     };
   654 
   655     struct EdgeT {
   656       int aNode, prev_out, next_out;
   657       int bNode, prev_in, next_in;
   658     };
   659 
   660     std::vector<NodeT> aNodes;
   661     std::vector<NodeT> bNodes;
   662 
   663     std::vector<EdgeT> edges;
   664 
   665     int first_anode;
   666     int first_free_anode;
   667 
   668     int first_bnode;
   669     int first_free_bnode;
   670 
   671     int first_free_edge;
   672 
   673   public:
   674   
   675     class Node {
   676       friend class ListBpUGraphBase;
   677     protected:
   678       int id;
   679 
   680       Node(int _id) : id(_id) {}
   681     public:
   682       Node() {}
   683       Node(Invalid) { id = -1; }
   684       bool operator==(const Node i) const {return id==i.id;}
   685       bool operator!=(const Node i) const {return id!=i.id;}
   686       bool operator<(const Node i) const {return id<i.id;}
   687     };
   688 
   689     class Edge {
   690       friend class ListBpUGraphBase;
   691     protected:
   692       int id;
   693 
   694       Edge(int _id) { id = _id;}
   695     public:
   696       Edge() {}
   697       Edge (Invalid) { id = -1; }
   698       bool operator==(const Edge i) const {return id==i.id;}
   699       bool operator!=(const Edge i) const {return id!=i.id;}
   700       bool operator<(const Edge i) const {return id<i.id;}
   701     };
   702 
   703     ListBpUGraphBase()
   704       : first_anode(-1), first_free_anode(-1),
   705         first_bnode(-1), first_free_bnode(-1),
   706         first_free_edge(-1) {}
   707 
   708     void firstANode(Node& node) const {
   709       node.id = first_anode != -1 ? (first_anode << 1) : -1;
   710     }
   711     void nextANode(Node& node) const {
   712       node.id = aNodes[node.id >> 1].next_node;
   713     }
   714 
   715     void firstBNode(Node& node) const {
   716       node.id =  first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
   717     }
   718     void nextBNode(Node& node) const {
   719       node.id = aNodes[node.id >> 1].next_node;
   720     }
   721 
   722     void first(Node& node) const {
   723       if (first_anode != -1) {
   724         node.id = (first_anode << 1);
   725       } else if (first_bnode != -1) {
   726         node.id = (first_bnode << 1) + 1;
   727       } else {
   728         node.id = -1;
   729       }
   730     }
   731     void next(Node& node) const {
   732       if (aNode(node)) {
   733         node.id = aNodes[node.id >> 1].next_node;
   734         if (node.id == -1) {
   735           if (first_bnode != -1) {
   736             node.id = (first_bnode << 1) + 1;
   737           }
   738         }
   739       } else {
   740         node.id = bNodes[node.id >> 1].next_node;
   741       }
   742     }
   743   
   744     void first(Edge& edge) const {
   745       int aNodeId = first_anode;
   746       while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
   747         aNodeId = aNodes[aNodeId].next_node != -1 ? 
   748           aNodes[aNodeId].next_node >> 1 : -1;
   749       }
   750       if (aNodeId != -1) {
   751         edge.id = aNodes[aNodeId].first_edge;
   752       } else {
   753         edge.id = -1;
   754       }
   755     }
   756     void next(Edge& edge) const {
   757       int aNodeId = edges[edge.id].aNode >> 1;
   758       edge.id = edges[edge.id].next_out;
   759       if (edge.id == -1) {
   760         aNodeId = aNodes[aNodeId].next_node != -1 ? 
   761           aNodes[aNodeId].next_node >> 1 : -1;
   762         while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
   763           aNodeId = aNodes[aNodeId].next_node != -1 ? 
   764           aNodes[aNodeId].next_node >> 1 : -1;
   765         }
   766         if (aNodeId != -1) {
   767           edge.id = aNodes[aNodeId].first_edge;
   768         } else {
   769           edge.id = -1;
   770         }
   771       }
   772     }
   773 
   774     void firstOut(Edge& edge, const Node& node) const {
   775       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
   776       edge.id = aNodes[node.id >> 1].first_edge;
   777     }
   778     void nextOut(Edge& edge) const {
   779       edge.id = edges[edge.id].next_out;
   780     }
   781 
   782     void firstIn(Edge& edge, const Node& node) const {
   783       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
   784       edge.id = bNodes[node.id >> 1].first_edge;
   785     }
   786     void nextIn(Edge& edge) const {
   787       edge.id = edges[edge.id].next_in;
   788     }
   789 
   790     static int id(const Node& node) {
   791       return node.id;
   792     }
   793     static Node nodeFromId(int id) {
   794       return Node(id);
   795     }
   796     int maxNodeId() const {
   797       return aNodes.size() > bNodes.size() ?
   798 	aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
   799     }
   800   
   801     static int id(const Edge& edge) {
   802       return edge.id;
   803     }
   804     static Edge edgeFromId(int id) {
   805       return Edge(id);
   806     }
   807     int maxEdgeId() const {
   808       return edges.size();
   809     }
   810   
   811     static int aNodeId(const Node& node) {
   812       return node.id >> 1;
   813     }
   814     static Node fromANodeId(int id, Node) {
   815       return Node(id << 1);
   816     }
   817     int maxANodeId() const {
   818       return aNodes.size();
   819     }
   820 
   821     static int bNodeId(const Node& node) {
   822       return node.id >> 1;
   823     }
   824     static Node fromBNodeId(int id) {
   825       return Node((id << 1) + 1);
   826     }
   827     int maxBNodeId() const {
   828       return bNodes.size();
   829     }
   830 
   831     Node aNode(const Edge& edge) const {
   832       return Node(edges[edge.id].aNode);
   833     }
   834     Node bNode(const Edge& edge) const {
   835       return Node(edges[edge.id].bNode);
   836     }
   837 
   838     static bool aNode(const Node& node) {
   839       return (node.id & 1) == 0;
   840     }
   841 
   842     static bool bNode(const Node& node) {
   843       return (node.id & 1) == 1;
   844     }
   845 
   846     Node addANode() {
   847       int aNodeId;
   848       if (first_free_anode == -1) {
   849         aNodeId = aNodes.size();
   850         aNodes.push_back(NodeT());
   851       } else {
   852         aNodeId = first_free_anode;
   853         first_free_anode = aNodes[first_free_anode].next_node;
   854       }
   855       aNodes[aNodeId].next_node = 
   856         first_anode != -1 ? (first_anode << 1) : -1;
   857       first_anode = aNodeId;
   858       aNodes[aNodeId].first_edge = -1;
   859       return Node(aNodeId << 1);
   860     }
   861 
   862     Node addBNode() {
   863       int bNodeId;
   864       if (first_free_anode == -1) {
   865         bNodeId = bNodes.size();
   866         bNodes.push_back(NodeT());
   867       } else {
   868         bNodeId = first_free_bnode;
   869         first_free_bnode = bNodes[first_free_bnode].next_node;
   870       }
   871       bNodes[bNodeId].next_node = 
   872         first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
   873       first_bnode = bNodeId;
   874       bNodes[bNodeId].first_edge = -1;
   875       return Node((bNodeId << 1) + 1);
   876     }
   877 
   878     Edge addEdge(const Node& source, const Node& target) {
   879       LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
   880       int edgeId;
   881       if (first_free_edge != -1) {
   882         edgeId = first_free_edge;
   883         first_free_edge = edges[edgeId].next_out;
   884       } else {
   885         edgeId = edges.size();
   886         edges.push_back(EdgeT());
   887       }
   888       if ((source.id & 1) == 0) {
   889 	edges[edgeId].aNode = source.id;
   890 	edges[edgeId].bNode = target.id;
   891       } else {
   892 	edges[edgeId].aNode = target.id;
   893 	edges[edgeId].bNode = source.id;
   894       }
   895       edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
   896       edges[edgeId].prev_out = -1;
   897       if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
   898         edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
   899       }
   900       aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
   901       edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
   902       edges[edgeId].prev_in = -1;
   903       if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
   904         edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
   905       }
   906       bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
   907       return Edge(edgeId);
   908     }
   909 
   910     void erase(const Node& node) {
   911       if (aNode(node)) {
   912         int aNodeId = node.id >> 1;
   913         aNodes[aNodeId].next_node = first_free_anode;
   914         first_free_anode = aNodeId;
   915       } else {
   916         int bNodeId = node.id >> 1;
   917         bNodes[bNodeId].next_node = first_free_bnode;
   918         first_free_bnode = bNodeId;
   919       }
   920     }
   921 
   922     void erase(const Edge& edge) {
   923       if (edges[edge.id].prev_out != -1) {
   924         edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
   925       } else {
   926         aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out;
   927       }
   928       if (edges[edge.id].next_out != -1) {
   929         edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
   930       }
   931       if (edges[edge.id].prev_in != -1) {
   932         edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
   933       } else {
   934         bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in;
   935       }
   936       if (edges[edge.id].next_in != -1) {
   937         edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
   938       }
   939       edges[edge.id].next_out = first_free_edge;
   940       first_free_edge = edge.id;
   941     }
   942 
   943     void clear() {
   944       aNodes.clear();
   945       bNodes.clear();
   946       edges.clear();
   947       first_anode = -1;
   948       first_free_anode = -1;
   949       first_bnode = -1;
   950       first_free_bnode = -1;
   951       first_free_edge = -1;
   952     }
   953 
   954   };
   955 
   956 
   957   typedef BpUGraphExtender< BpUGraphBaseExtender<
   958     ListBpUGraphBase> > ExtendedListBpUGraphBase;
   959 
   960   /// \ingroup graphs
   961   ///
   962   /// \brief A smart bipartite undirected graph class.
   963   ///
   964   /// This is a bipartite undirected graph implementation.
   965   /// Except from this it conforms to 
   966   /// the \ref concept::BpUGraph "BpUGraph" concept.
   967   /// \sa concept::BpUGraph.
   968   ///
   969   class ListBpUGraph : public ExtendedListBpUGraphBase {};
   970 
   971   
   972   /// @}  
   973 } //namespace lemon
   974   
   975 
   976 #endif