src/work/marci/oldies/list_graph.hh
changeset 1218 5331168bbb18
equal deleted inserted replaced
-1:000000000000 0:65d39caa143a
       
     1 #ifndef LIST_GRAPH_HH
       
     2 #define LIST_GRAPH_HH
       
     3 
       
     4 #include <iostream>
       
     5 #include <vector>
       
     6 
       
     7 namespace hugo {
       
     8 
       
     9   template <typename It>
       
    10   int count(It it) { 
       
    11     int i=0;
       
    12     for( ; it.valid(); ++it) { ++i; } 
       
    13     return i;
       
    14   }
       
    15 
       
    16   class ListGraph {
       
    17 
       
    18     class node_item;
       
    19     class edge_item;
       
    20 
       
    21   public:
       
    22 
       
    23     class NodeIt;
       
    24     class EachNodeIt;
       
    25     class EdgeIt;
       
    26     class EachEdgeIt;
       
    27     class OutEdgeIt;
       
    28     class InEdgeIt;
       
    29     class SymEdgeIt;
       
    30     template <typename T> class NodeMap;
       
    31     template <typename T> class EdgeMap;
       
    32     
       
    33   private:
       
    34     
       
    35     template <typename T> friend class NodeMap;
       
    36     template <typename T> friend class EdgeMap;
       
    37 
       
    38     template <typename T>
       
    39     class NodeMap {
       
    40       const ListGraph& G; 
       
    41       std::vector<T> container;
       
    42     public:
       
    43       typedef T ValueType;
       
    44       typedef NodeIt KeyType;
       
    45       NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { }
       
    46       NodeMap(const ListGraph& _G, T a) : 
       
    47 	G(_G), container(G.node_id, a) { }
       
    48       void set(NodeIt n, T a) { container[/*G.id(n)*/n.node->id]=a; }
       
    49       T get(NodeIt n) const { return container[/*G.id(n)*/n.node->id]; }
       
    50       T& operator[](NodeIt n) { return container[/*G.id(n)*/n.node->id]; }
       
    51       const T& operator[](NodeIt n) const { return container[/*G.id(n)*/n.node->id]; }
       
    52       void update() { container.resize(G.node_id); }
       
    53       void update(T a) { container.resize(G.node_id, a); }
       
    54     };
       
    55 
       
    56     template <typename T>
       
    57     class EdgeMap {
       
    58       const ListGraph& G; 
       
    59       std::vector<T> container;
       
    60     public:
       
    61       typedef T ValueType;
       
    62       typedef EdgeIt KeyType;
       
    63       EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { }
       
    64       EdgeMap(const ListGraph& _G, T a) : 
       
    65 	G(_G), container(G.edge_id, a) { }
       
    66       void set(EdgeIt e, T a) { container[/*G.id(e)*/e.edge->id]=a; }
       
    67       T get(EdgeIt e) const { return container[/*G.id(e)*/e.edge->id]; }
       
    68       T& operator[](EdgeIt e) { return container[/*G.id(e)*/e.edge->id]; } 
       
    69       const T& operator[](EdgeIt e) const { return container[/*G.id(e)*/e.edge->id]; } 
       
    70       void update() { container.resize(G.edge_id); }
       
    71       void update(T a) { container.resize(G.edge_id, a); }
       
    72     };
       
    73 
       
    74     int node_id;
       
    75     int edge_id;
       
    76     int _node_num;
       
    77     int _edge_num;
       
    78 
       
    79     node_item* _first_node;
       
    80     node_item* _last_node;
       
    81 
       
    82     class node_item {
       
    83       friend class ListGraph;
       
    84       template <typename T> friend class NodeMap;
       
    85       
       
    86       friend class NodeIt;
       
    87       friend class EachNodeIt;
       
    88       friend class EdgeIt;
       
    89       friend class EachEdgeIt;
       
    90       friend class OutEdgeIt;
       
    91       friend class InEdgeIt;
       
    92       friend class SymEdgeIt;
       
    93       friend std::ostream& operator<<(std::ostream& os, const NodeIt& i);
       
    94       friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
       
    95       //ListGraph* G;
       
    96       int id;
       
    97       edge_item* _first_out_edge;
       
    98       edge_item* _last_out_edge;
       
    99       edge_item* _first_in_edge;
       
   100       edge_item* _last_in_edge;
       
   101       node_item* _next_node;
       
   102       node_item* _prev_node;
       
   103     public:
       
   104       node_item() { }
       
   105     };
       
   106 
       
   107     class edge_item {
       
   108       friend class ListGraph;
       
   109       template <typename T> friend class EdgeMap;
       
   110 
       
   111       friend class NodeIt;
       
   112       friend class EachNodeIt;
       
   113       friend class EdgeIt;
       
   114       friend class EachEdgeIt;
       
   115       friend class OutEdgeIt;
       
   116       friend class InEdgeIt;
       
   117       friend class SymEdgeIt;
       
   118       friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
       
   119       //ListGraph* G;
       
   120       int id;
       
   121       node_item* _tail;
       
   122       node_item* _head;
       
   123       edge_item* _next_out;
       
   124       edge_item* _prev_out;
       
   125       edge_item* _next_in;
       
   126       edge_item* _prev_in;
       
   127     public:
       
   128       edge_item() { }
       
   129     };
       
   130 
       
   131     node_item* _add_node() { 
       
   132       node_item* p=new node_item;
       
   133       p->id=node_id++;
       
   134       p->_first_out_edge=0;
       
   135       p->_last_out_edge=0;
       
   136       p->_first_in_edge=0;
       
   137       p->_last_in_edge=0;
       
   138       p->_prev_node=_last_node;
       
   139       p->_next_node=0;
       
   140       if (_last_node) _last_node->_next_node=p;
       
   141       _last_node=p;
       
   142       if (!_first_node) _first_node=p;
       
   143 
       
   144       ++_node_num;
       
   145       return p;
       
   146     }
       
   147 
       
   148     edge_item* _add_edge(node_item* _tail, node_item* _head) {
       
   149       edge_item* e=new edge_item;
       
   150       e->id=edge_id++;
       
   151       e->_tail=_tail;
       
   152       e->_head=_head;
       
   153       
       
   154       e->_prev_out=_tail->_last_out_edge;
       
   155       if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
       
   156       _tail->_last_out_edge=e;
       
   157       if (!_tail->_first_out_edge) _tail->_first_out_edge=e; 
       
   158       e->_next_out=0;
       
   159  
       
   160       e->_prev_in=_head->_last_in_edge;
       
   161       if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
       
   162       _head->_last_in_edge=e;
       
   163       if (!_head->_first_in_edge) { _head->_first_in_edge=e; } 
       
   164       e->_next_in=0;
       
   165 
       
   166       ++_edge_num;
       
   167       return e;
       
   168     }
       
   169 
       
   170     //deletes a node which has no out edge and no in edge
       
   171     void _delete_node(node_item* v) {
       
   172       if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else 
       
   173 	_last_node=v->_prev_node;
       
   174       if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else 
       
   175 	_first_node=v->_next_node;
       
   176 
       
   177       delete v;
       
   178       --_node_num;
       
   179     }
       
   180 
       
   181     void _delete_edge(edge_item* e) {
       
   182       if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else 
       
   183 	(e->_tail)->_last_out_edge=e->_prev_out;
       
   184       if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else 
       
   185 	(e->_tail)->_first_out_edge=e->_next_out;
       
   186       if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else 
       
   187 	(e->_head)->_last_in_edge=e->_prev_in;
       
   188       if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else 
       
   189 	(e->_head)->_first_in_edge=e->_next_in;
       
   190 
       
   191       delete e;
       
   192       --_edge_num;
       
   193     }
       
   194 
       
   195     void _set_tail(edge_item* e, node_item* _tail) {
       
   196       if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else 
       
   197 	(e->_tail)->_last_out_edge=e->_prev_out;
       
   198       if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else 
       
   199 	(e->_tail)->_first_out_edge=e->_next_out;
       
   200       
       
   201       e->_tail=_tail;
       
   202       
       
   203       e->_prev_out=_tail->_last_out_edge;
       
   204       if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
       
   205       _tail->_last_out_edge=e;
       
   206       if (!_tail->_first_out_edge) _tail->_first_out_edge=e; 
       
   207       e->_next_out=0;
       
   208     }
       
   209 
       
   210     void _set_head(edge_item* e, node_item* _head) {
       
   211       if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else 
       
   212 	(e->_head)->_last_in_edge=e->_prev_in;
       
   213       if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else 
       
   214 	(e->_head)->_first_in_edge=e->_next_in;
       
   215       
       
   216       e->_head=_head;
       
   217       
       
   218       e->_prev_in=_head->_last_in_edge;
       
   219       if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
       
   220       _head->_last_in_edge=e;
       
   221       if (!_head->_first_in_edge) { _head->_first_in_edge=e; } 
       
   222       e->_next_in=0;
       
   223     }
       
   224 
       
   225   public:
       
   226 
       
   227     /* default constructor */
       
   228 
       
   229     ListGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
       
   230     
       
   231     ~ListGraph() { 
       
   232       while (first<EachNodeIt>().valid()) erase(first<EachNodeIt>());
       
   233     }
       
   234 
       
   235     int nodeNum() const { return _node_num; }
       
   236     int edgeNum() const { return _edge_num; }
       
   237 
       
   238     /* functions to construct iterators from the graph, or from each other */
       
   239 
       
   240     //EachNodeIt firstNode() const { return EachNodeIt(*this); }
       
   241     //EachEdgeIt firstEdge() const { return EachEdgeIt(*this); }
       
   242     
       
   243     //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); }
       
   244     //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
       
   245     //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
       
   246     NodeIt tail(EdgeIt e) const { return e.tailNode(); }
       
   247     NodeIt head(EdgeIt e) const { return e.headNode(); }
       
   248 
       
   249     NodeIt aNode(const OutEdgeIt& e) const { return e.aNode(); }
       
   250     NodeIt aNode(const InEdgeIt& e) const { return e.aNode(); }
       
   251     NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
       
   252 
       
   253     NodeIt bNode(const OutEdgeIt& e) const { return e.bNode(); }
       
   254     NodeIt bNode(const InEdgeIt& e) const { return e.bNode(); }
       
   255     NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
       
   256 
       
   257     //NodeIt invalid_node() { return NodeIt(); }
       
   258     //EdgeIt invalid_edge() { return EdgeIt(); }
       
   259     //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); }
       
   260     //InEdgeIt invalid_in_edge() { return InEdgeIt(); }
       
   261     //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); }
       
   262 
       
   263     /* same methods in other style */
       
   264     /* for experimental purpose */
       
   265 
       
   266     EachNodeIt& getFirst(EachNodeIt& v) const { 
       
   267       v=EachNodeIt(*this); return v; }
       
   268     EachEdgeIt& getFirst(EachEdgeIt& e) const { 
       
   269       e=EachEdgeIt(*this); return e; }
       
   270     OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const { 
       
   271       e=OutEdgeIt(v); return e; }
       
   272     InEdgeIt& getFirst(InEdgeIt& e, NodeIt v) const { 
       
   273       e=InEdgeIt(v); return e; }
       
   274     SymEdgeIt& getFirst(SymEdgeIt& e, NodeIt v) const { 
       
   275       e=SymEdgeIt(v); return e; }
       
   276     //void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); }
       
   277     //void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); }
       
   278 
       
   279     //void getANode(NodeIt& n, const OutEdgeIt& e) const { n=e.aNode(); }
       
   280     //void getANode(NodeIt& n, const InEdgeIt& e) const { n=e.aNode(); }
       
   281     //void getANode(NodeIt& n, const SymEdgeIt& e) const { n=e.aNode(); }
       
   282     //void getBNode(NodeIt& n, const OutEdgeIt& e) const { n=e.bNode(); }
       
   283     //void getBNode(NodeIt& n, const InEdgeIt& e) const { n=e.bNode(); }
       
   284     //void getBNode(NodeIt& n, const SymEdgeIt& e) const { n=e.bNode(); }
       
   285     //void get_invalid(NodeIt& n) { n=NodeIt(); }
       
   286     //void get_invalid(EdgeIt& e) { e=EdgeIt(); }
       
   287     //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }
       
   288     //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }
       
   289     //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
       
   290 
       
   291     template< typename It >
       
   292     It first() const { 
       
   293       It e;
       
   294       getFirst(e);
       
   295       return e; 
       
   296     }
       
   297 
       
   298     template< typename It >
       
   299     It first(NodeIt v) const { 
       
   300       It e;
       
   301       getFirst(e, v);
       
   302       return e; 
       
   303     }
       
   304 
       
   305     bool valid(NodeIt n) const { return n.valid(); }
       
   306     bool valid(EdgeIt e) const { return e.valid(); }
       
   307     
       
   308     template <typename It> It getNext(It it) const { 
       
   309       It tmp(it); return next(tmp); }
       
   310     template <typename It> It& next(It& it) const { return ++it; }
       
   311    
       
   312 
       
   313     /* for getting id's of graph objects */
       
   314     /* these are important for the implementation of property vectors */
       
   315 
       
   316     int id(NodeIt v) const { return v.node->id; }
       
   317     int id(EdgeIt e) const { return e.edge->id; }
       
   318 
       
   319     /* adding nodes and edges */
       
   320 
       
   321     NodeIt addNode() { return NodeIt(_add_node()); }
       
   322     EdgeIt addEdge(NodeIt u, NodeIt v) {
       
   323       return EdgeIt(_add_edge(u.node, v.node)); 
       
   324     }
       
   325 
       
   326     void erase(NodeIt i) { 
       
   327       while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
       
   328       while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
       
   329       _delete_node(i.node); 
       
   330     }
       
   331   
       
   332     void erase(EdgeIt e) { _delete_edge(e.edge); }
       
   333 
       
   334     void clear() { 
       
   335       while (first<EachNodeIt>().valid()) erase(first<EachNodeIt>());
       
   336     }
       
   337 
       
   338     void setTail(EdgeIt e, NodeIt tail) {
       
   339       _set_tail(e.edge, tail.node); 
       
   340     }
       
   341 
       
   342     void setHead(EdgeIt e, NodeIt head) {
       
   343       _set_head(e.edge, head.node); 
       
   344     }
       
   345 
       
   346     /* stream operations, for testing purpose */
       
   347 
       
   348     friend std::ostream& operator<<(std::ostream& os, const NodeIt& i) { 
       
   349       os << i.node->id; return os; 
       
   350     }
       
   351     friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i) { 
       
   352       os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")"; 
       
   353       return os; 
       
   354     }
       
   355 
       
   356     class NodeIt {
       
   357       friend class ListGraph;
       
   358       template <typename T> friend class NodeMap;
       
   359 
       
   360       friend class EdgeIt;
       
   361       friend class OutEdgeIt;
       
   362       friend class InEdgeIt;
       
   363       friend class SymEdgeIt;
       
   364       //public:  //FIXME: It is required by op= of EachNodeIt
       
   365     protected:
       
   366       node_item* node;
       
   367     protected:
       
   368       friend int ListGraph::id(NodeIt v) const; 
       
   369     public:
       
   370       NodeIt() : node(0) { }
       
   371       NodeIt(node_item* _node) : node(_node) { }
       
   372       bool valid() const { return (node!=0); }
       
   373       //void makeInvalid() { node=0; }
       
   374       friend bool operator==(const NodeIt& u, const NodeIt& v) { 
       
   375 	return v.node==u.node; 
       
   376       } 
       
   377       friend bool operator!=(const NodeIt& u, const NodeIt& v) { 
       
   378 	return v.node!=u.node; 
       
   379       } 
       
   380       friend std::ostream& operator<<(std::ostream& os, const NodeIt& i);
       
   381     };
       
   382     
       
   383     class EachNodeIt : public NodeIt {
       
   384       friend class ListGraph;
       
   385       //protected:
       
   386     public: //for everybody but marci
       
   387       EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }
       
   388     public:
       
   389       EachNodeIt() : NodeIt() { }
       
   390       EachNodeIt(node_item* v) : NodeIt(v) { }
       
   391       EachNodeIt& operator++() { node=node->_next_node; return *this; }
       
   392       //FIXME::
       
   393       //      EachNodeIt& operator=(const NodeIt& e)
       
   394       //      { node=e.node; return *this; }
       
   395     };
       
   396 
       
   397     class EdgeIt {
       
   398       friend class ListGraph;
       
   399       template <typename T> friend class EdgeMap;
       
   400       
       
   401       friend class NodeIt;
       
   402       friend class EachNodeIt;
       
   403     protected:
       
   404       edge_item* edge;
       
   405       friend int ListGraph::id(EdgeIt e) const;
       
   406     public:
       
   407       EdgeIt() : edge(0) { }
       
   408       //EdgeIt() { }
       
   409       EdgeIt(edge_item* _edge) : edge(_edge) { }
       
   410       bool valid() const { return (edge!=0); }
       
   411       //void makeInvalid() { edge=0; }
       
   412       friend bool operator==(const EdgeIt& u, const EdgeIt& v) { 
       
   413 	return v.edge==u.edge; 
       
   414       } 
       
   415       friend bool operator!=(const EdgeIt& u, const EdgeIt& v) { 
       
   416 	return v.edge!=u.edge; 
       
   417       } 
       
   418     protected:
       
   419       NodeIt tailNode() const { return NodeIt(edge->_tail); }
       
   420       NodeIt headNode() const { return NodeIt(edge->_head); }
       
   421     public:
       
   422       friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
       
   423     };
       
   424     
       
   425     class EachEdgeIt : public EdgeIt {
       
   426       friend class ListGraph;
       
   427       //protected: 
       
   428     public: //for alpar
       
   429       EachEdgeIt(const ListGraph& G) {
       
   430 	node_item* v=G._first_node;
       
   431 	if (v) edge=v->_first_out_edge; else edge=0;
       
   432 	while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
       
   433       }
       
   434     public:
       
   435       EachEdgeIt() : EdgeIt() { }
       
   436       EachEdgeIt(edge_item* _e) : EdgeIt(_e) { }
       
   437       EachEdgeIt& operator++() { 
       
   438 	node_item* v=edge->_tail;
       
   439 	edge=edge->_next_out; 
       
   440 	while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
       
   441 	return *this;
       
   442       }
       
   443     };
       
   444     
       
   445     class OutEdgeIt : public EdgeIt {
       
   446       friend class ListGraph;
       
   447       //node_item* v;
       
   448       //protected: 
       
   449     public: //for alpar
       
   450       OutEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
       
   451     public:
       
   452       OutEdgeIt() : EdgeIt()/*, v(0)*/ { }
       
   453       OutEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
       
   454       OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
       
   455     protected:
       
   456       NodeIt aNode() const { return NodeIt(edge->_tail); }
       
   457       NodeIt bNode() const { return NodeIt(edge->_head); }
       
   458     };
       
   459     
       
   460     class InEdgeIt : public EdgeIt {
       
   461       friend class ListGraph;
       
   462       //node_item* v;
       
   463       //protected:
       
   464     public: //for alpar
       
   465       InEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
       
   466     public:
       
   467       InEdgeIt() : EdgeIt()/*, v(0)*/ { }
       
   468       InEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
       
   469       InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
       
   470     protected:
       
   471       NodeIt aNode() const { return NodeIt(edge->_head); }
       
   472       NodeIt bNode() const { return NodeIt(edge->_tail); }
       
   473     };
       
   474 
       
   475     class SymEdgeIt : public EdgeIt {
       
   476       friend class ListGraph;
       
   477       bool out_or_in; //1 iff out, 0 iff in
       
   478       //node_item* v;
       
   479       //protected:
       
   480     public: //for alpar
       
   481       SymEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { 
       
   482 	out_or_in=1;
       
   483 	edge=_v.node->_first_out_edge; 
       
   484 	if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
       
   485       }
       
   486     public:
       
   487       SymEdgeIt() : EdgeIt() /*, v(0)*/ { }
       
   488       SymEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { 
       
   489 	out_or_in=1;
       
   490 	edge=_v.node->_first_out_edge; 
       
   491 	if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
       
   492       }
       
   493       SymEdgeIt& operator++() { 
       
   494 	if (out_or_in) { 
       
   495 	  node_item* v=edge->_tail;
       
   496 	  edge=edge->_next_out; 
       
   497 	  if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
       
   498 	} else {
       
   499 	  edge=edge->_next_in; 
       
   500 	}
       
   501 	return *this;
       
   502       }
       
   503     protected:
       
   504       NodeIt aNode() const { 
       
   505 	return (out_or_in) ? NodeIt(edge->_tail) : NodeIt(edge->_head); }
       
   506       NodeIt bNode() const { 
       
   507 	return (out_or_in) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
       
   508     };
       
   509 
       
   510   };
       
   511 
       
   512 //   template< typename T >
       
   513 //   T ListGraph::first() const { 
       
   514 //     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>();" << std::endl; 
       
   515 //     return T(); 
       
   516 //   }
       
   517 
       
   518 //   template<>
       
   519 //   ListGraph::EachNodeIt ListGraph::first<ListGraph::EachNodeIt>() const { 
       
   520 //     return firstNode(); 
       
   521 //   }
       
   522 
       
   523 //   template<>
       
   524 //   ListGraph::EachEdgeIt ListGraph::first<ListGraph::EachEdgeIt>() const { 
       
   525 //     return firstEdge(); 
       
   526 //   }
       
   527 
       
   528 //   template< typename T >
       
   529 //   T ListGraph::first(ListGraph::NodeIt v) const {
       
   530 //     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>(ListGRaph::NodeIt);" << std::endl; 
       
   531 //     return T(); 
       
   532 //   } 
       
   533 
       
   534 //   template<>
       
   535 //   ListGraph::OutEdgeIt ListGraph::first<ListGraph::OutEdgeIt>(const ListGraph::NodeIt v) const { 
       
   536 //     return firstOutEdge(v); 
       
   537 //   }
       
   538 
       
   539 //   template<>
       
   540 //   ListGraph::InEdgeIt ListGraph::first<ListGraph::InEdgeIt>(const ListGraph::NodeIt v) const { 
       
   541 //     return firstInEdge(v); 
       
   542 //   }
       
   543 
       
   544 //   template<>
       
   545 //   ListGraph::SymEdgeIt ListGraph::first<ListGraph::SymEdgeIt>(const ListGraph::NodeIt v) const { 
       
   546 //     return firstSymEdge(v); 
       
   547 //   }
       
   548 
       
   549 
       
   550 } //namespace hugo
       
   551 
       
   552 #endif //LIST_GRAPH_HH