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