marci@280: #ifndef MARCI_LIST_GRAPH_HH
marci@280: #define MARCI_LIST_GRAPH_HH
marci@280: 
marci@280: #include <iostream>
marci@280: 
marci@280: namespace hugo {
marci@280: 
marci@280:   class list_graph {
marci@280:     class node_item;
marci@280:     class edge_item;
marci@280:   public:
marci@280:     class node_iterator;
marci@280:     class each_node_iterator;
marci@280:     class edge_iterator;
marci@280:     class each_edge_iterator;
marci@280:     class out_edge_iterator;
marci@280:     class in_edge_iterator;
marci@280:     class sym_edge_iterator;
marci@280:   private:
marci@280:     int node_id;
marci@280:     int edge_id;
marci@280:     int _node_num;
marci@280:     int _edge_num;
marci@280: 
marci@280:     node_item* _first_node;
marci@280:     node_item* _last_node;
marci@280: 
marci@280:     class node_item {
marci@280:       friend class list_graph;
marci@280:       friend class node_iterator;
marci@280:       friend class each_node_iterator;
marci@280:       friend class edge_iterator;
marci@280:       friend class each_edge_iterator;
marci@280:       friend class out_edge_iterator;
marci@280:       friend class in_edge_iterator;
marci@280:       friend class sym_edge_iterator;
marci@280:       friend std::ostream& operator<<(std::ostream& os, const node_iterator& i);
marci@280:       friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
marci@280:       list_graph* G;
marci@280:       int id;
marci@280:       edge_item* _first_out_edge;
marci@280:       edge_item* _last_out_edge;
marci@280:       edge_item* _first_in_edge;
marci@280:       edge_item* _last_in_edge;
marci@280:       node_item* _next_node;
marci@280:       node_item* _prev_node;
marci@280:     public:
marci@280:       node_item() { }
marci@280:     };
marci@280: 
marci@280:     class edge_item {
marci@280:       friend class list_graph;
marci@280:       friend class node_iterator;
marci@280:       friend class each_node_iterator;
marci@280:       friend class edge_iterator;
marci@280:       friend class each_edge_iterator;
marci@280:       friend class out_edge_iterator;
marci@280:       friend class in_edge_iterator;
marci@280:       friend class sym_edge_iterator;
marci@280:       friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
marci@280:       list_graph* G;
marci@280:       int id;
marci@280:       node_item* _tail;
marci@280:       node_item* _head;
marci@280:       edge_item* _next_out;
marci@280:       edge_item* _prev_out;
marci@280:       edge_item* _next_in;
marci@280:       edge_item* _prev_in;
marci@280:     public:
marci@280:       edge_item() { }
marci@280:     };
marci@280: 
marci@280:     node_item* _add_node() { 
marci@280:       node_item* p=new node_item;
marci@280:       p->id=node_id++;
marci@280:       p->_first_out_edge=0;
marci@280:       p->_last_out_edge=0;
marci@280:       p->_first_in_edge=0;
marci@280:       p->_last_in_edge=0;
marci@280:       p->_prev_node=_last_node;
marci@280:       p->_next_node=0;
marci@280:       if (_last_node) _last_node->_next_node=p;
marci@280:       _last_node=p;
marci@280:       if (!_first_node) _first_node=p;
marci@280:       ++_node_num;
marci@280:       return p;
marci@280:     }
marci@280: 
marci@280:     edge_item* _add_edge(node_item* _tail, node_item* _head) {
marci@280:       edge_item* e=new edge_item;
marci@280:       e->id=edge_id++;
marci@280:       e->_tail=_tail;
marci@280:       e->_head=_head;
marci@280:       
marci@280:       e->_prev_out=_tail->_last_out_edge;
marci@280:       if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
marci@280:       _tail->_last_out_edge=e;
marci@280:       if (!_tail->_first_out_edge) _tail->_first_out_edge=e; 
marci@280:        
marci@280:       e->_prev_in=_head->_last_in_edge;
marci@280:       if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
marci@280:       _head->_last_in_edge=e;
marci@280:       if (!_head->_first_in_edge) { _head->_first_in_edge=e; } 
marci@280:       ++_edge_num;
marci@280:       return e;
marci@280:     }
marci@280: 
marci@280:   public:
marci@280: 
marci@280:     /* default constructor */
marci@280: 
marci@280:     list_graph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
marci@280:     
marci@280:     int node_num() { return _node_num; }
marci@280:     int edge_num() { return _edge_num; }
marci@280: 
marci@280:     /* functions to construct iterators from the graph, or from each other */
marci@280: 
marci@280:     each_node_iterator first_node() { return each_node_iterator(_first_node); }
marci@280:     each_edge_iterator first_edge() { 
marci@280:       node_item* v=_first_node;
marci@280:       edge_item* edge=v->_first_out_edge;
marci@280:       while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
marci@280:       return each_edge_iterator(v, edge); 
marci@280:     }
marci@280:     
marci@280:     out_edge_iterator first_out_edge(const node_iterator& v) { 
marci@280:       return out_edge_iterator(v); 
marci@280:     }
marci@280:     in_edge_iterator first_in_edge(const node_iterator& v) { 
marci@280:       return in_edge_iterator(v); 
marci@280:     }
marci@280:     sym_edge_iterator first_sym_edge(const node_iterator& v) { 
marci@280:       return sym_edge_iterator(v); 
marci@280:     }
marci@280:     node_iterator tail(const edge_iterator& e) { return e.tail_node(); }
marci@280:     node_iterator head(const edge_iterator& e) { return e.head_node(); }
marci@280: 
marci@280:     node_iterator a_node(const out_edge_iterator& e) { return e.a_node(); }
marci@280:     node_iterator a_node(const in_edge_iterator& e) { return e.a_node(); }
marci@280:     node_iterator a_node(const sym_edge_iterator& e) { return e.a_node(); }
marci@280: 
marci@280:     node_iterator b_node(const out_edge_iterator& e) { return e.b_node(); }
marci@280:     node_iterator b_node(const in_edge_iterator& e) { return e.b_node(); }
marci@280:     node_iterator b_node(const sym_edge_iterator& e) { return e.b_node(); }
marci@280: 
marci@280:     //node_iterator invalid_node() { return node_iterator(); }
marci@280:     //edge_iterator invalid_edge() { return edge_iterator(); }
marci@280:     //out_edge_iterator invalid_out_edge() { return out_edge_iterator(); }
marci@280:     //in_edge_iterator invalid_in_edge() { return in_edge_iterator(); }
marci@280:     //sym_edge_iterator invalid_sym_edge() { return sym_edge_iterator(); }
marci@280: 
marci@280:     /* same methods in other style */
marci@280:     /* for experimental purpose */
marci@280: 
marci@280:     void get_first(each_node_iterator& v) { v=each_node_iterator(_first_node); }
marci@280:     void get_first(each_edge_iterator& e) { e=first_edge(); }
marci@280:     void get_first(out_edge_iterator& e, const node_iterator& v) { 
marci@280:       e=out_edge_iterator(v); 
marci@280:     }
marci@280:     void get_first(in_edge_iterator& e, const node_iterator& v) { 
marci@280:       e=in_edge_iterator(v); 
marci@280:     }
marci@280:     void get_first(sym_edge_iterator& e, const node_iterator& v) { 
marci@280:       e=sym_edge_iterator(v); 
marci@280:     }
marci@280:     void get_tail(node_iterator& n, const edge_iterator& e) { n=tail(e); }
marci@280:     void get_head(node_iterator& n, const edge_iterator& e) { n=head(e); }
marci@280: 
marci@280:     void get_a_node(node_iterator& n, const out_edge_iterator& e) { n=e.a_node(); }
marci@280:     void get_a_node(node_iterator& n, const in_edge_iterator& e) { n=e.a_node(); }
marci@280:     void get_a_node(node_iterator& n, const sym_edge_iterator& e) { n=e.a_node(); }
marci@280:     void get_b_node(node_iterator& n, const out_edge_iterator& e) { n=e.b_node(); }
marci@280:     void get_b_node(node_iterator& n, const in_edge_iterator& e) { n=e.b_node(); }
marci@280:     void get_b_node(node_iterator& n, const sym_edge_iterator& e) { n=e.b_node(); }
marci@280:     //void get_invalid(node_iterator& n) { n=node_iterator(); }
marci@280:     //void get_invalid(edge_iterator& e) { e=edge_iterator(); }
marci@280:     //void get_invalid(out_edge_iterator& e) { e=out_edge_iterator(); }
marci@280:     //void get_invalid(in_edge_iterator& e) { e=in_edge_iterator(); }
marci@280:     //void get_invalid(sym_edge_iterator& e) { e=sym_edge_iterator(); }
marci@280: 
marci@280: 
marci@280:     /* for getting id's of graph objects */
marci@280:     /* these are important for the implementation of property vectors */
marci@280: 
marci@280:     int id(const node_iterator& v) { return v.node->id; }
marci@280:     int id(const edge_iterator& e) { return e.edge->id; }
marci@280: 
marci@280:     /* adding nodes and edges */
marci@280: 
marci@280:     node_iterator add_node() { return node_iterator(_add_node()); }
marci@280:     edge_iterator add_edge(const node_iterator& u, const node_iterator& v) {
marci@280:       return edge_iterator(_add_edge(u.node, v.node)); 
marci@280:     }
marci@280: 
marci@280:     /* stream operations, for testing purpose */
marci@280: 
marci@280:     friend std::ostream& operator<<(std::ostream& os, const node_iterator& i) { 
marci@280:       os << i.node->id; return os; 
marci@280:     }
marci@280:     friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i) { 
marci@280:       os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")"; 
marci@280:       return os; 
marci@280:     }
marci@280: 
marci@280:     class node_iterator {
marci@280:       friend class list_graph;
marci@280: 
marci@280:       friend class edge_iterator;
marci@280:       friend class out_edge_iterator;
marci@280:       friend class in_edge_iterator;
marci@280:       friend class sym_edge_iterator;
marci@280:     protected:
marci@280:       node_item* node;
marci@280:       friend int list_graph::id(const node_iterator& v); 
marci@280:     public:
marci@280:       node_iterator() : node(0) { }
marci@280:       node_iterator(node_item* _node) : node(_node) { }
marci@280:       bool valid() { return (node!=0); }
marci@280:       void make_invalid() { node=0; }
marci@280:       friend bool operator==(const node_iterator& u, const node_iterator& v) { 
marci@280: 	return v.node==u.node; 
marci@280:       } 
marci@280:       friend bool operator!=(const node_iterator& u, const node_iterator& v) { 
marci@280: 	return v.node!=u.node; 
marci@280:       } 
marci@280:       friend std::ostream& operator<<(std::ostream& os, const node_iterator& i);
marci@280:     };
marci@280:     
marci@280:     class each_node_iterator : public node_iterator {
marci@280:       friend class list_graph;
marci@280:     public:
marci@280:       each_node_iterator() : node_iterator() { }
marci@280:       each_node_iterator(node_item* v) : node_iterator(v) { }
marci@280:       each_node_iterator& operator++() { node=node->_next_node; return *this; }
marci@280:     };
marci@280: 
marci@280:     class edge_iterator {
marci@280:       friend class list_graph;
marci@280:       
marci@280:       friend class node_iterator;
marci@280:       friend class each_node_iterator;
marci@280:     protected:
marci@280:       edge_item* edge;
marci@280:       friend int list_graph::id(const edge_iterator& e);
marci@280:     public:
marci@280:       edge_iterator() : edge(0) { }
marci@280:       edge_iterator(edge_item* _edge) : edge(_edge) { }
marci@280:       bool valid() { return (edge!=0); }
marci@280:       void make_invalid() { edge=0; }
marci@280:       friend bool operator==(const edge_iterator& u, const edge_iterator& v) { 
marci@280: 	return v.edge==u.edge; 
marci@280:       } 
marci@280:       friend bool operator!=(const edge_iterator& u, const edge_iterator& v) { 
marci@280: 	return v.edge!=u.edge; 
marci@280:       } 
marci@280:     protected:
marci@280:       node_iterator tail_node() const { return node_iterator(edge->_tail); }
marci@280:       node_iterator head_node() const { return node_iterator(edge->_head); }
marci@280:     public:
marci@280:       friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
marci@280:     };
marci@280:     
marci@280:     class each_edge_iterator : public edge_iterator {
marci@280:       friend class list_graph;
marci@280:       node_item* v;
marci@280:     public:
marci@280:       each_edge_iterator() : edge_iterator(), v(0) { }
marci@280:       each_edge_iterator(node_item* _v, edge_item* _e) : edge_iterator(_e), v(_v) { }
marci@280:       each_edge_iterator& operator++() { 
marci@280: 	edge=edge->_next_out; 
marci@280: 	while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
marci@280: 	return *this;
marci@280:       }
marci@280:     };
marci@280:     
marci@280:     class out_edge_iterator : public edge_iterator {
marci@280:       friend class list_graph;
marci@280:       node_item* v;
marci@280:     public:
marci@280:       out_edge_iterator() : edge_iterator(), v(0) { }
marci@280:     protected:
marci@280:       out_edge_iterator(const node_iterator& _v) : v(_v.node) { edge=v->_first_out_edge; }
marci@280:     public:
marci@280:       out_edge_iterator& operator++() { edge=edge->_next_out; return *this; }
marci@280:     protected:
marci@280:       node_iterator a_node() const { return node_iterator(v); }
marci@280:       node_iterator b_node() const { 
marci@280: 	return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(edge->_tail); }
marci@280:     };
marci@280:     
marci@280:     class in_edge_iterator : public edge_iterator {
marci@280:       friend class list_graph;
marci@280:       node_item* v;
marci@280:     public:
marci@280:       in_edge_iterator() : edge_iterator(), v(0) { }
marci@280:     protected:
marci@280:       in_edge_iterator(const node_iterator& _v) : v(_v.node) { 
marci@280: 	edge=v->_first_in_edge; 
marci@280:       }
marci@280:     public:
marci@280:       in_edge_iterator& operator++() { edge=edge->_next_in; return *this; }
marci@280:     protected:
marci@280:       node_iterator a_node() const { return node_iterator(v); }
marci@280:       node_iterator b_node() const { 
marci@280: 	return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(edge->_tail); }
marci@280:     };
marci@280: 
marci@280:     class sym_edge_iterator : public edge_iterator {
marci@280:       friend class list_graph;
marci@280:       bool out_or_in; //1 iff out, 0 iff in
marci@280:       node_item* v;
marci@280:     public:
marci@280:       sym_edge_iterator() : edge_iterator(), v(0) { }
marci@280:     protected:
marci@280:       sym_edge_iterator(const node_iterator& _v) : v(_v.node) { 
marci@280: 	out_or_in=1;
marci@280: 	edge=v->_first_out_edge; 
marci@280: 	if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
marci@280:       }
marci@280:     public:
marci@280:       sym_edge_iterator& operator++() { 
marci@280: 	if (out_or_in) { 
marci@280: 	  edge=edge->_next_out; 
marci@280: 	  if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
marci@280: 	} else {
marci@280: 	  edge=edge->_next_in; 
marci@280: 	}
marci@280: 	return *this;
marci@280:       }
marci@280:     protected:
marci@280:       node_iterator a_node() const { return node_iterator(v); }
marci@280:       node_iterator b_node() const { 
marci@280: 	return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(edge->_tail); }
marci@280:     };
marci@280: 
marci@280:   };
marci@280: 
marci@280: 
marci@280: 
marci@280: } //namespace hugo
marci@280: 
marci@280: #endif //MARCI_LIST_GRAPH_HH