src/work/marci_list_graph.hh
changeset 106 0508d63fcc96
parent 16 dd19ef4d7ba4
child 107 8d62f0072ff0
equal deleted inserted replaced
2:da82aab642d2 3:e4cb1854c9bc
    17     class in_edge_iterator;
    17     class in_edge_iterator;
    18     class sym_edge_iterator;
    18     class sym_edge_iterator;
    19   private:
    19   private:
    20     int node_id;
    20     int node_id;
    21     int edge_id;
    21     int edge_id;
       
    22     int _node_num;
       
    23     int _edge_num;
    22 
    24 
    23     node_item* _first_node;
    25     node_item* _first_node;
    24     node_item* _last_node;
    26     node_item* _last_node;
    25 
    27 
    26     class node_item {
    28     class node_item {
    78       p->_prev_node=_last_node;
    80       p->_prev_node=_last_node;
    79       p->_next_node=0;
    81       p->_next_node=0;
    80       if (_last_node) _last_node->_next_node=p;
    82       if (_last_node) _last_node->_next_node=p;
    81       _last_node=p;
    83       _last_node=p;
    82       if (!_first_node) _first_node=p;
    84       if (!_first_node) _first_node=p;
       
    85       ++_node_num;
    83       return p;
    86       return p;
    84     }
    87     }
    85 
    88 
    86     edge_item* _add_edge(node_item* _tail, node_item* _head) {
    89     edge_item* _add_edge(node_item* _tail, node_item* _head) {
    87       edge_item* e=new edge_item;
    90       edge_item* e=new edge_item;
    96        
    99        
    97       e->_prev_in=_head->_last_in_edge;
   100       e->_prev_in=_head->_last_in_edge;
    98       if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
   101       if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
    99       _head->_last_in_edge=e;
   102       _head->_last_in_edge=e;
   100       if (!_head->_first_in_edge) { _head->_first_in_edge=e; } 
   103       if (!_head->_first_in_edge) { _head->_first_in_edge=e; } 
       
   104       ++_edge_num;
   101       return e;
   105       return e;
   102     }
   106     }
   103 
   107 
   104   public:
   108   public:
   105 
   109 
   106     /* default constructor */
   110     /* default constructor */
   107 
   111 
   108     list_graph() : node_id(0), edge_id(0), _first_node(0), _last_node(0) { }
   112     list_graph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
   109     
   113     
       
   114     int node_num() { return _node_num; }
       
   115     int edge_num() { return _edge_num; }
       
   116 
   110     /* functions to construct iterators from the graph, or from each other */
   117     /* functions to construct iterators from the graph, or from each other */
   111 
   118 
   112     each_node_iterator first_node() { return each_node_iterator(_first_node); }
   119     each_node_iterator first_node() { return each_node_iterator(_first_node); }
   113     each_edge_iterator first_edge() { 
   120     each_edge_iterator first_edge() { 
   114       node_item* v=_first_node;
   121       node_item* v=_first_node;
   207       node_item* node;
   214       node_item* node;
   208       friend int list_graph::id(const node_iterator& v); 
   215       friend int list_graph::id(const node_iterator& v); 
   209     public:
   216     public:
   210       node_iterator() : node(0) { }
   217       node_iterator() : node(0) { }
   211       node_iterator(node_item* _node) : node(_node) { }
   218       node_iterator(node_item* _node) : node(_node) { }
   212       bool is_valid() { return (node!=0); }
   219       bool valid() { return (node!=0); }
   213       void make_invalid() { node=0; }
   220       void make_invalid() { node=0; }
   214       friend bool operator==(const node_iterator& u, const node_iterator& v) { 
   221       friend bool operator==(const node_iterator& u, const node_iterator& v) { 
   215 	return v.node==u.node; 
   222 	return v.node==u.node; 
   216       } 
   223       } 
   217       friend bool operator!=(const node_iterator& u, const node_iterator& v) { 
   224       friend bool operator!=(const node_iterator& u, const node_iterator& v) { 
   237       edge_item* edge;
   244       edge_item* edge;
   238       friend int list_graph::id(const edge_iterator& e);
   245       friend int list_graph::id(const edge_iterator& e);
   239     public:
   246     public:
   240       edge_iterator() : edge(0) { }
   247       edge_iterator() : edge(0) { }
   241       edge_iterator(edge_item* _edge) : edge(_edge) { }
   248       edge_iterator(edge_item* _edge) : edge(_edge) { }
   242       bool is_valid() { return (edge!=0); }
   249       bool valid() { return (edge!=0); }
   243       void make_invalid() { edge=0; }
   250       void make_invalid() { edge=0; }
   244       friend bool operator==(const edge_iterator& u, const edge_iterator& v) { 
   251       friend bool operator==(const edge_iterator& u, const edge_iterator& v) { 
   245 	return v.edge==u.edge; 
   252 	return v.edge==u.edge; 
   246       } 
   253       } 
   247       friend bool operator!=(const edge_iterator& u, const edge_iterator& v) { 
   254       friend bool operator!=(const edge_iterator& u, const edge_iterator& v) {