Wiselib: wiselib.testing/util/graph/adjacency

Wiselib
00001 /*
00002  * adjacency_list.h
00003  *
00004  *  Created on: 27-ago-2009
00005  *      Author: Juan Farré, jafarre@lsi.upc.edu
00006  */
00007 
00008 #ifndef ADJACENCY_LIST_H_
00009 #define ADJACENCY_LIST_H_
00010 
00011 #include "util/pstl/pair.h"
00012 
00013 namespace wiselib{
00014 
00015 template<class OsModel_P,
00016    typename OsModel_P::size_t N,
00017    typename OsModel_P::size_t M,
00018    class VData,
00019    class EData>
00020 class AdjacencyList {
00021 public:
00022    typedef OsModel_P OsModel;
00023    typedef VData VertexData;
00024    typedef EData EdgeData;
00025    typedef typename OsModel::size_t size_t;
00026    typedef size_t VerticesSize;
00027    typedef size_t EdgesSize;
00028    typedef EdgesSize DegreeSize;
00029    class VertexDescriptor;
00030    class EdgeDescriptor;
00031    class VertexIterator;
00032    class EdgeIterator;
00033    typedef pair<VertexIterator,VertexIterator> VertexIteratorRange;
00034    typedef pair<EdgeIterator,EdgeIterator> EdgeIteratorRange;
00035 
00036    AdjacencyList();
00037 
00038    VerticesSize num_vertices();
00039    EdgesSize num_edges();
00040    VertexIteratorRange vertices();
00041    EdgeIteratorRange edges();
00042    VertexDescriptor add_vertex();
00043    EdgeDescriptor add_edge(VertexDescriptor,VertexDescriptor);
00044    void remove_vertex(VertexDescriptor,bool remove_edges=false);
00045    void remove_edge(EdgeDescriptor);
00046 
00047    static VerticesSize const max_vertices=N;
00048    static EdgesSize const max_edges=M;
00049    static VertexDescriptor const null_vertex;
00050    static EdgeDescriptor const null_edge;
00051 
00052 private:
00053    struct VertexEntry;
00054    struct EdgeEntry;
00055    VertexEntry vertex_set[max_vertices];
00056    EdgeEntry edge_set[max_edges];
00057    VerticesSize first_vertex;
00058    VerticesSize first_unused_vertex;
00059    EdgesSize first_edge;
00060    EdgesSize first_unused_edge;
00061    VerticesSize nvertices;
00062    EdgesSize nedges;
00063 };
00064 
00065 template<class OsModel_P,
00066    typename OsModel_P::size_t N,
00067    typename OsModel_P::size_t M,
00068    class VData,
00069    class EData>
00070 AdjacencyList<OsModel_P,N,M,VData,EData>::AdjacencyList():
00071    first_vertex(max_vertices),
00072    first_unused_vertex(0),
00073    first_edge(max_edges),
00074    first_unused_edge(0),
00075    nvertices(0),
00076    nedges(0){
00077    for(VerticesSize i=0;i<max_vertices;i++)
00078       vertex_set[i].next=i+1;
00079    for(EdgesSize i=0;i<max_edges;i++)
00080       edge_set[i].next=i+1;
00081 }
00082 
00083 template<class OsModel_P,
00084    typename OsModel_P::size_t N,
00085    typename OsModel_P::size_t M,
00086    class VData,
00087    class EData>
00088 struct AdjacencyList<OsModel_P,N,M,VData,EData>::VertexEntry {
00089    VertexEntry();
00090 
00091    VertexData data;
00092    EdgesSize out_edges;
00093    EdgesSize in_edges;
00094    DegreeSize out_degree;
00095    DegreeSize in_degree;
00096    VerticesSize next;
00097    VerticesSize prev;
00098 };
00099 
00100 template<class OsModel_P,
00101    typename OsModel_P::size_t N,
00102    typename OsModel_P::size_t M,
00103    class VData,
00104    class EData>
00105 AdjacencyList<OsModel_P,N,M,VData,EData>::VertexEntry::VertexEntry():
00106    out_degree(max_edges){
00107 }
00108 
00109 template<class OsModel_P,
00110    typename OsModel_P::size_t N,
00111    typename OsModel_P::size_t M,
00112    class VData,
00113    class EData>
00114 struct AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeEntry {
00115    EdgeEntry();
00116 
00117    VerticesSize source;
00118    VerticesSize target;
00119    EdgeData data;
00120    EdgesSize next;
00121    EdgesSize prev;
00122    EdgesSize next_out;
00123    EdgesSize prev_out;
00124    EdgesSize next_in;
00125    EdgesSize prev_in;
00126 };
00127 
00128 template<class OsModel_P,
00129    typename OsModel_P::size_t N,
00130    typename OsModel_P::size_t M,
00131    class VData,
00132    class EData>
00133 AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeEntry::EdgeEntry():
00134    source(max_vertices){
00135 }
00136 
00137 template<class OsModel_P,
00138    typename OsModel_P::size_t N,
00139    typename OsModel_P::size_t M,
00140    class VData,
00141    class EData>
00142 class AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor {
00143 public:
00144    class OutEdgeIterator;
00145    class InEdgeIterator;
00146    typedef pair<OutEdgeIterator,OutEdgeIterator> OutEdgeIteratorRange;
00147    typedef pair<InEdgeIterator,InEdgeIterator> InEdgeIteratorRange;
00148 
00149    DegreeSize out_degree() const;
00150    DegreeSize in_degree() const;
00151    DegreeSize degree() const;
00152    OutEdgeIteratorRange out_edges();
00153    InEdgeIteratorRange in_edges();
00154    VertexData operator*();
00155    bool operator==(VertexDescriptor);
00156    bool operator!=(VertexDescriptor);
00157 
00158 protected:
00159    VertexDescriptor(AdjacencyList &);
00160    VertexDescriptor(AdjacencyList &,VerticesSize);
00161 
00162    AdjacencyList &g;
00163    VerticesSize v;
00164 
00165    friend class AdjacencyList;
00166    friend class OutEdgeIterator;
00167    friend class InEdgeIterator;
00168 };
00169 
00170 template<class OsModel_P,
00171    typename OsModel_P::size_t N,
00172    typename OsModel_P::size_t M,
00173    class VData,
00174    class EData>
00175 AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::VertexDescriptor(AdjacencyList &graph):
00176    g(graph),
00177    v(max_vertices){
00178 }
00179 
00180 template<class OsModel_P,
00181    typename OsModel_P::size_t N,
00182    typename OsModel_P::size_t M,
00183    class VData,
00184    class EData>
00185 AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::VertexDescriptor(AdjacencyList &graph,VerticesSize i):
00186    g(graph),
00187    v(i){
00188 }
00189 
00190 template<class OsModel_P,
00191    typename OsModel_P::size_t N,
00192    typename OsModel_P::size_t M,
00193    class VData,
00194    class EData>
00195 typename AdjacencyList<OsModel_P,N,M,VData,EData>::DegreeSize AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::out_degree() const {
00196    return g.vertex_set[v].out_degree;
00197 }
00198 
00199 template<class OsModel_P,
00200    typename OsModel_P::size_t N,
00201    typename OsModel_P::size_t M,
00202    class VData,
00203    class EData>
00204 typename AdjacencyList<OsModel_P,N,M,VData,EData>::DegreeSize AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::in_degree() const {
00205    return g.vertex_set[v].in_degree;
00206 }
00207 
00208 template<class OsModel_P,
00209    typename OsModel_P::size_t N,
00210    typename OsModel_P::size_t M,
00211    class VData,
00212    class EData>
00213 typename AdjacencyList<OsModel_P,N,M,VData,EData>::DegreeSize AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::degree() const {
00214    return out_degree()+in_degree();
00215 }
00216 
00217 template<class OsModel_P,
00218    typename OsModel_P::size_t N,
00219    typename OsModel_P::size_t M,
00220    class VData,
00221    class EData>
00222 typename AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::OutEdgeIteratorRange AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::out_edges() {
00223    return OutEdgeIteratorRange(OutEdgeIterator(*this),OutEdgeIterator(*this,max_edges));
00224 }
00225 
00226 template<class OsModel_P,
00227    typename OsModel_P::size_t N,
00228    typename OsModel_P::size_t M,
00229    class VData,
00230    class EData>
00231 typename AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::InEdgeIteratorRange AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::in_edges() {
00232    return InEdgeIteratorRange(InEdgeIterator(*this),InEdgeIterator(*this,max_edges));
00233 }
00234 
00235 template<class OsModel_P,
00236    typename OsModel_P::size_t N,
00237    typename OsModel_P::size_t M,
00238    class VData,
00239    class EData>
00240 VData AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::operator*(){
00241    return g.vertex_set[v].data;
00242 }
00243 
00244 template<class OsModel_P,
00245    typename OsModel_P::size_t N,
00246    typename OsModel_P::size_t M,
00247    class VData,
00248    class EData>
00249 bool AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::operator==(VertexDescriptor u){
00250    return u.v==v;
00251 }
00252 
00253 template<class OsModel_P,
00254    typename OsModel_P::size_t N,
00255    typename OsModel_P::size_t M,
00256    class VData,
00257    class EData>
00258 bool AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::operator!=(VertexDescriptor u){
00259    return !operator==(u);
00260 }
00261 
00262 template<class OsModel_P,
00263    typename OsModel_P::size_t N,
00264    typename OsModel_P::size_t M,
00265    class VData,
00266    class EData>
00267 class AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeDescriptor {
00268 public:
00269    VertexDescriptor source();
00270    VertexDescriptor target();
00271    EdgeData operator*();
00272    bool operator==(EdgeDescriptor);
00273    bool operator!=(EdgeDescriptor);
00274 
00275 protected:
00276    EdgeDescriptor(AdjacencyList &);
00277    EdgeDescriptor(AdjacencyList &,EdgesSize);
00278 
00279    AdjacencyList &g;
00280    EdgesSize e;
00281 
00282    friend class AdjacencyList;
00283 };
00284 
00285 template<class OsModel_P,
00286    typename OsModel_P::size_t N,
00287    typename OsModel_P::size_t M,
00288    class VData,
00289    class EData>
00290 AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeDescriptor::EdgeDescriptor(AdjacencyList &graph):
00291    g(graph),
00292    e(max_edges){
00293 }
00294 
00295 template<class OsModel_P,
00296    typename OsModel_P::size_t N,
00297    typename OsModel_P::size_t M,
00298    class VData,
00299    class EData>
00300 AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeDescriptor::EdgeDescriptor(AdjacencyList &graph,EdgesSize i):
00301    g(graph),
00302    e(i){
00303 }
00304 
00305 template<class OsModel_P,
00306    typename OsModel_P::size_t N,
00307    typename OsModel_P::size_t M,
00308    class VData,
00309    class EData>
00310 typename AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeDescriptor::source(){
00311    return VertexDescriptor(g,g.edge_set[e].source);
00312 }
00313 
00314 template<class OsModel_P,
00315    typename OsModel_P::size_t N,
00316    typename OsModel_P::size_t M,
00317    class VData,
00318    class EData>
00319 typename AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeDescriptor::target(){
00320    return VertexDescriptor(g,g.edge_set[e].target);
00321 }
00322 
00323 template<class OsModel_P,
00324    typename OsModel_P::size_t N,
00325    typename OsModel_P::size_t M,
00326    class VData,
00327    class EData>
00328 EData AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeDescriptor::operator*(){
00329    return g.edge_set[e].data;
00330 }
00331 
00332 template<class OsModel_P,
00333    typename OsModel_P::size_t N,
00334    typename OsModel_P::size_t M,
00335    class VData,
00336    class EData>
00337 bool AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeDescriptor::operator==(EdgeDescriptor e2){
00338    return e2.e==e;
00339 }
00340 
00341 template<class OsModel_P,
00342    typename OsModel_P::size_t N,
00343    typename OsModel_P::size_t M,
00344    class VData,
00345    class EData>
00346 bool AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeDescriptor::operator!=(EdgeDescriptor e2){
00347    return !operator==(e2);
00348 }
00349 
00350 template<class OsModel_P,
00351    typename OsModel_P::size_t N,
00352    typename OsModel_P::size_t M,
00353    class VData,
00354    class EData>
00355 class AdjacencyList<OsModel_P,N,M,VData,EData>::VertexIterator: public VertexDescriptor {
00356 public:
00357    VertexIterator operator++();
00358 
00359 private:
00360    VertexIterator(AdjacencyList &);
00361    VertexIterator(AdjacencyList &,VerticesSize);
00362 
00363    friend class AdjacencyList;
00364 };
00365 
00366 template<class OsModel_P,
00367    typename OsModel_P::size_t N,
00368    typename OsModel_P::size_t M,
00369    class VData,
00370    class EData>
00371 AdjacencyList<OsModel_P,N,M,VData,EData>::VertexIterator::VertexIterator(AdjacencyList &g):
00372    VertexDescriptor(g,g.first_vertex) {
00373 }
00374 
00375 template<class OsModel_P,
00376    typename OsModel_P::size_t N,
00377    typename OsModel_P::size_t M,
00378    class VData,
00379    class EData>
00380 AdjacencyList<OsModel_P,N,M,VData,EData>::VertexIterator::VertexIterator(AdjacencyList &g,VerticesSize v):
00381    VertexDescriptor(g,v) {
00382 }
00383 
00384 template<class OsModel_P,
00385    typename OsModel_P::size_t N,
00386    typename OsModel_P::size_t M,
00387    class VData,
00388    class EData>
00389 typename AdjacencyList<OsModel_P,N,M,VData,EData>::VertexIterator AdjacencyList<OsModel_P,N,M,VData,EData>::VertexIterator::operator++(){
00390    if(operator!=(null_vertex))
00391       VertexDescriptor::v=vertex_set[VertexDescriptor::v].next;
00392    return *this;
00393 }
00394 
00395 template<class OsModel_P,
00396    typename OsModel_P::size_t N,
00397    typename OsModel_P::size_t M,
00398    class VData,
00399    class EData>
00400 class AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeIterator: public EdgeDescriptor {
00401 public:
00402    EdgeIterator operator++();
00403 
00404 private:
00405    EdgeIterator(AdjacencyList &);
00406    EdgeIterator(AdjacencyList &,EdgesSize);
00407 
00408    friend class AdjacencyList;
00409 };
00410 
00411 template<class OsModel_P,
00412    typename OsModel_P::size_t N,
00413    typename OsModel_P::size_t M,
00414    class VData,
00415    class EData>
00416 AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeIterator::EdgeIterator(AdjacencyList &g):
00417    EdgeDescriptor(g,g.first_edge) {
00418 }
00419 
00420 template<class OsModel_P,
00421    typename OsModel_P::size_t N,
00422    typename OsModel_P::size_t M,
00423    class VData,
00424    class EData>
00425 AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeIterator::EdgeIterator(AdjacencyList &g,EdgesSize e):
00426    EdgeDescriptor(g,e) {
00427 }
00428 
00429 template<class OsModel_P,
00430    typename OsModel_P::size_t N,
00431    typename OsModel_P::size_t M,
00432    class VData,
00433    class EData>
00434 typename AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeIterator AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeIterator::operator++(){
00435    if(operator!=(null_edge))
00436       EdgeDescriptor::e=edge_set[EdgeDescriptor::e].next;
00437    return *this;
00438 }
00439 
00440 template<class OsModel_P,
00441    typename OsModel_P::size_t N,
00442    typename OsModel_P::size_t M,
00443    class VData,
00444    class EData>
00445 class AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::OutEdgeIterator: public EdgeDescriptor {
00446 public:
00447    OutEdgeIterator operator++();
00448 
00449 private:
00450    OutEdgeIterator(VertexDescriptor &);
00451    OutEdgeIterator(VertexDescriptor &,EdgesSize);
00452 
00453    VertexDescriptor &v;
00454 
00455    friend class AdjacencyList;
00456 };
00457 
00458 template<class OsModel_P,
00459    typename OsModel_P::size_t N,
00460    typename OsModel_P::size_t M,
00461    class VData,
00462    class EData>
00463 AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::OutEdgeIterator::OutEdgeIterator(VertexDescriptor& vertex):
00464    EdgeDescriptor(vertex.g,vertex.g.vertex_set[vertex.v].out_edges),
00465    v(vertex){
00466 }
00467 
00468 template<class OsModel_P,
00469    typename OsModel_P::size_t N,
00470    typename OsModel_P::size_t M,
00471    class VData,
00472    class EData>
00473 AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::OutEdgeIterator::OutEdgeIterator(VertexDescriptor& vertex,EdgesSize e):
00474    EdgeDescriptor(vertex.g,e),
00475    v(vertex){
00476 }
00477 
00478 template<class OsModel_P,
00479    typename OsModel_P::size_t N,
00480    typename OsModel_P::size_t M,
00481    class VData,
00482    class EData>
00483 typename AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::OutEdgeIterator AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::OutEdgeIterator::operator++(){
00484    if(operator!=(null_edge))
00485       EdgeDescriptor::e=edge_set[EdgeDescriptor::e].next_out;
00486    return *this;
00487 }
00488 
00489 template<class OsModel_P,
00490    typename OsModel_P::size_t N,
00491    typename OsModel_P::size_t M,
00492    class VData,
00493    class EData>
00494 class AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::InEdgeIterator: public EdgeDescriptor {
00495 public:
00496    InEdgeIterator operator++();
00497 
00498 private:
00499    InEdgeIterator(VertexDescriptor &);
00500    InEdgeIterator(VertexDescriptor &,EdgesSize);
00501 
00502    VertexDescriptor &v;
00503 
00504    friend class AdjacencyList;
00505 };
00506 
00507 template<class OsModel_P,
00508    typename OsModel_P::size_t N,
00509    typename OsModel_P::size_t M,
00510    class VData,
00511    class EData>
00512 AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::InEdgeIterator::InEdgeIterator(VertexDescriptor &vertex):
00513    EdgeDescriptor(vertex.g,vertex.g.vertex_set[vertex.v].in_edges),
00514    v(vertex){
00515 }
00516 
00517 template<class OsModel_P,
00518    typename OsModel_P::size_t N,
00519    typename OsModel_P::size_t M,
00520    class VData,
00521    class EData>
00522 AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::InEdgeIterator::InEdgeIterator(VertexDescriptor &vertex,EdgesSize e):
00523    EdgeDescriptor(vertex.g,e),
00524    v(vertex){
00525 }
00526 
00527 template<class OsModel_P,
00528    typename OsModel_P::size_t N,
00529    typename OsModel_P::size_t M,
00530    class VData,
00531    class EData>
00532 typename AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::InEdgeIterator AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor::InEdgeIterator::operator++(){
00533    if(operator!=(null_edge))
00534       EdgeDescriptor::e=edge_set[EdgeDescriptor::e].next_in;
00535    return *this;
00536 }
00537 
00538 template<class OsModel_P,
00539    typename OsModel_P::size_t N,
00540    typename OsModel_P::size_t M,
00541    class VData,
00542    class EData>
00543 typename AdjacencyList<OsModel_P,N,M,VData,EData>::VertexIteratorRange AdjacencyList<OsModel_P,N,M,VData,EData>::vertices() {
00544    return VertexIteratorRange(VertexIterator(*this),VertexIterator(*this,max_vertices));
00545 }
00546 
00547 template<class OsModel_P,
00548    typename OsModel_P::size_t N,
00549    typename OsModel_P::size_t M,
00550    class VData,
00551    class EData>
00552 typename AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeIteratorRange AdjacencyList<OsModel_P,N,M,VData,EData>::edges() {
00553    return EdgeIteratorRange(EdgeIterator(*this),EdgeIterator(*this,max_edges));
00554 }
00555 
00556 template<class OsModel_P,
00557    typename OsModel_P::size_t N,
00558    typename OsModel_P::size_t M,
00559    class VData,
00560    class EData>
00561 typename AdjacencyList<OsModel_P,N,M,VData,EData>::VerticesSize AdjacencyList<OsModel_P,N,M,VData,EData>::num_vertices() {
00562    return nvertices;
00563 }
00564 
00565 template<class OsModel_P,
00566    typename OsModel_P::size_t N,
00567    typename OsModel_P::size_t M,
00568    class VData,
00569    class EData>
00570 typename AdjacencyList<OsModel_P,N,M,VData,EData>::EdgesSize AdjacencyList<OsModel_P,N,M,VData,EData>::num_edges() {
00571    return nedges;
00572 }
00573 
00574 template<class OsModel_P,
00575    typename OsModel_P::size_t N,
00576    typename OsModel_P::size_t M,
00577    class VData,
00578    class EData>
00579 typename AdjacencyList<OsModel_P,N,M,VData,EData>::VertexDescriptor AdjacencyList<OsModel_P,N,M,VData,EData>::add_vertex() {
00580    if(nvertices==max_vertices)
00581       return null_vertex;
00582    ++nvertices;
00583    VerticesSize const v=first_unused_vertex;
00584    first_unused_vertex=vertex_set[v].next;
00585    vertex_set[v].prev=max_vertices;
00586    vertex_set[v].next=first_vertex;
00587    if(first_vertex!=max_vertices)
00588       vertex_set[first_vertex].prev=v;
00589    first_vertex=v;
00590    vertex_set[v].out_edges=vertex_set[v].in_edges=max_edges;
00591    vertex_set[v].in_degree=vertex_set[v].out_degree=0;
00592    return VertexDescriptor(*this,v);
00593 }
00594 
00595 template<class OsModel_P,
00596    typename OsModel_P::size_t N,
00597    typename OsModel_P::size_t M,
00598    class VData,
00599    class EData>
00600 typename AdjacencyList<OsModel_P,N,M,VData,EData>::EdgeDescriptor AdjacencyList<OsModel_P,N,M,VData,EData>::add_edge(VertexDescriptor source,VertexDescriptor target) {
00601    if(nedges==max_edges||source==null_vertex||target==null_vertex)
00602       return null_edge;
00603    EdgesSize const e=first_unused_edge;
00604    first_unused_edge=edge_set[e].next;
00605    edge_set[e].source=source.v;
00606    edge_set[e].target=target.v;
00607    edge_set[e].prev=max_edges;
00608    edge_set[e].next_out=first_edge;
00609    if(first_edge!=max_edges)
00610       edge_set[first_edge].prev_out=e;
00611    first_edge=e;
00612    ++nedges;
00613    edge_set[e].prev_out=max_edges;
00614    {
00615       EdgesSize &first=vertex_set[source.v].out_edges;
00616       edge_set[e].next_out=first;
00617       if(first!=max_edges)
00618          edge_set[first].prev_out=e;
00619       first=e;
00620    }
00621    vertex_set[source.v].out_degree++;
00622    edge_set[e].prev_in=max_edges;
00623    {
00624       EdgesSize &first=vertex_set[target.v].in_edges;
00625       edge_set[e].next_in=first;
00626       if(first!=max_edges)
00627          edge_set[first].prev_in=e;
00628       first=e;
00629    }
00630    vertex_set[target.v].in_degree++;
00631    return EdgeDescriptor(*this,e);
00632 }
00633 
00634 template<class OsModel_P,
00635    typename OsModel_P::size_t N,
00636    typename OsModel_P::size_t M,
00637    class VData,
00638    class EData>
00639 void AdjacencyList<OsModel_P,N,M,VData,EData>::remove_edge(EdgeDescriptor edge) {
00640    if(edge==null_edge||edge_set[edge.e].source==max_vertices)
00641       return;
00642    EdgesSize const e=edge.e;
00643    edge_set[e].source=max_vertices;
00644    edge_set[e].next=first_unused_edge;
00645    first_unused_edge=e;
00646    {
00647       EdgesSize const prev=edge_set[e].prev_out;
00648       EdgesSize const next=edge_set[e].next_out;
00649       if(prev==max_edges)
00650          vertex_set[edge_set[e].source].out_edges=next;
00651       else
00652          edge_set[prev].next_out=next;
00653       if(next!=max_edges)
00654          edge_set[next].prev_out=prev;
00655    }
00656    vertex_set[edge_set[e].source].out_degree--;
00657    {
00658       EdgesSize const prev=edge_set[e].prev_in;
00659       EdgesSize const next=edge_set[e].next_in;
00660       if(prev==max_edges)
00661          vertex_set[edge_set[e].source].in_edges=next;
00662       else
00663          edge_set[prev].next_in=next;
00664       if(next!=max_edges)
00665          edge_set[next].prev_in=prev;
00666    }
00667    vertex_set[edge_set[e].target].in_degree--;
00668    {
00669       EdgesSize const prev=edge_set[e].prev;
00670       EdgesSize const next=edge_set[e].next;
00671       if(prev==max_edges)
00672          first_edge=next;
00673       else
00674          edge_set[prev].next=next;
00675       if(next!=max_edges)
00676          edge_set[next].prev=prev;
00677    }
00678    --nedges;
00679 }
00680 
00681 template<class OsModel_P,
00682    typename OsModel_P::size_t N,
00683    typename OsModel_P::size_t M,
00684    class VData,
00685    class EData>
00686 void AdjacencyList<OsModel_P,N,M,VData,EData>::remove_vertex(VertexDescriptor vertex,bool remove_edges) {
00687    if(vertex==null_vertex||vertex_set[vertex.v].out_degree==max_edges)
00688       return;
00689    VerticesSize const v=vertex.v;
00690    vertex_set[v].out_degree=max_edges;
00691    vertex_set[v].next=first_unused_vertex;
00692    first_unused_vertex=v;
00693    {
00694       VerticesSize const prev=vertex_set[v].prev;
00695       VerticesSize const next=vertex_set[v].next;
00696       if(prev==max_vertices)
00697          first_vertex=next;
00698       else
00699          vertex_set[prev].next=next;
00700       if(next!=max_vertices)
00701          vertex_set[next].prev=prev;
00702    }
00703    --nvertices;
00704    if(remove_edges){
00705       while(vertex_set[v].out_edges!=max_edges)
00706          remove_edge(EdgeDescriptor(*this,vertex_set[v].out_edges));
00707       while(vertex_set[v].in_edges!=max_edges)
00708          remove_edge(EdgeDescriptor(*this,vertex_set[v].in_edges));
00709    }
00710 }
00711 
00712 }
00713 
00714 #endif /* ADJACENCY_LIST_H_ */