lemon-0.x: src/work/deba/test_graph.h@259ea2d741a2

     1 // -*- c++ -*-

     2 #ifndef HUGO_LIST_GRAPH_H

     3 #define HUGO_LIST_GRAPH_H

     5 #include <iostream>

     6 #include <vector>

     8 #include <invalid.h>

    10 #include "vector_map.h"

    11 #include "edge_map_registry.h"

    12 #include "node_map_registry.h"

    13 #include "edge_map_base.h"

    14 #include "node_map_base.h"

    16 namespace hugo {

    18   template <typename It>

    19   int count(It it) {

    20     int i=0;

    21     for( ; it.valid(); ++it) { ++i; }

    22     return i;

    23   }

    25   class ListGraph {

    26     class node_item;

    27     class edge_item;

    28   public:

    29     class Node;

    30     class NodeIt;

    31     class Edge;

    32     class EdgeIt;

    33     class OutEdgeIt;

    34     class InEdgeIt;

    35     class SymEdgeIt;

    37 //    template <typename T> class NodeMap;

    38 //    template <typename T> class EdgeMap;

    39   private:

    40 //    template <typename T> friend class NodeMap;

    41  //   template <typename T> friend class EdgeMap;

    43 		NodeMapRegistry<ListGraph, Node> node_maps;

    45     template <typename T>

    46     class NodeMap : public VectorMap<ListGraph, Edge, T, EdgeMapBase> {};

    48 		EdgeMapRegistry<ListGraph, Edge> edge_maps;

    50     template <typename T>

    51     class EdgeMap : public VectorMap<Graph, Node, T, NodeMapBase> {};

    54     int node_id;

    55     int edge_id;

    56     int _node_num;

    57     int _edge_num;

    59     node_item* _first_node;

    60     node_item* _last_node;

    62     class node_item {

    63       friend class ListGraph;

    64       template <typename T> friend class NodeMap;

    66       friend class Node;

    67       friend class NodeIt;

    68       friend class Edge;

    69       friend class EdgeIt;

    70       friend class OutEdgeIt;

    71       friend class InEdgeIt;

    72       friend class SymEdgeIt;

    73       friend std::ostream& operator<<(std::ostream& os, const Node& i);

    74       friend std::ostream& operator<<(std::ostream& os, const Edge& i);

    75       //ListGraph* G;

    76       int id;

    77       edge_item* _first_out_edge;

    78       edge_item* _last_out_edge;

    79       edge_item* _first_in_edge;

    80       edge_item* _last_in_edge;

    81       node_item* _next_node;

    82       node_item* _prev_node;

    83     public:

    84       node_item() { }

    85     };

    87     class edge_item {

    88       friend class ListGraph;

    89       template <typename T> friend class EdgeMap;

    91       friend class Node;

    92       friend class NodeIt;

    93       friend class Edge;

    94       friend class EdgeIt;

    95       friend class OutEdgeIt;

    96       friend class InEdgeIt;

    97       friend class SymEdgeIt;

    98       friend std::ostream& operator<<(std::ostream& os, const Edge& i);

    99       //ListGraph* G;

   100       int id;

   101       node_item* _tail;

   102       node_item* _head;

   103       edge_item* _next_out;

   104       edge_item* _prev_out;

   105       edge_item* _next_in;

   106       edge_item* _prev_in;

   107     public:

   108       edge_item() { }

   109     };

   111     node_item* _add_node() {

   112       node_item* p=new node_item;

   113       p->id=node_id++;

   114       p->_first_out_edge=0;

   115       p->_last_out_edge=0;

   116       p->_first_in_edge=0;

   117       p->_last_in_edge=0;

   118       p->_prev_node=_last_node;

   119       p->_next_node=0;

   120       if (_last_node) _last_node->_next_node=p;

   121       _last_node=p;

   122       if (!_first_node) _first_node=p;

   124       ++_node_num;

   125       return p;

   126     }

   128     edge_item* _add_edge(node_item* _tail, node_item* _head) {

   129       edge_item* e=new edge_item;

   130       e->id=edge_id++;

   131       e->_tail=_tail;

   132       e->_head=_head;

   134       e->_prev_out=_tail->_last_out_edge;

   135       if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;

   136       _tail->_last_out_edge=e;

   137       if (!_tail->_first_out_edge) _tail->_first_out_edge=e;

   138       e->_next_out=0;

   140       e->_prev_in=_head->_last_in_edge;

   141       if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;

   142       _head->_last_in_edge=e;

   143       if (!_head->_first_in_edge) { _head->_first_in_edge=e; }

   144       e->_next_in=0;

   146       ++_edge_num;

   147       return e;

   148     }

   150     //deletes a node which has no out edge and no in edge

   151     void _delete_node(node_item* v) {

   152       if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else

   153 	_last_node=v->_prev_node;

   154       if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else

   155 	_first_node=v->_next_node;

   157       delete v;

   158       --_node_num;

   159     }

   161     void _delete_edge(edge_item* e) {

   162       if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else

   163 	(e->_tail)->_last_out_edge=e->_prev_out;

   164       if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else

   165 	(e->_tail)->_first_out_edge=e->_next_out;

   166       if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else

   167 	(e->_head)->_last_in_edge=e->_prev_in;

   168       if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else

   169 	(e->_head)->_first_in_edge=e->_next_in;

   171       delete e;

   172       --_edge_num;

   173     }

   175     void _set_tail(edge_item* e, node_item* _tail) {

   176       if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else

   177 	(e->_tail)->_last_out_edge=e->_prev_out;

   178       if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else

   179 	(e->_tail)->_first_out_edge=e->_next_out;

   181       e->_tail=_tail;

   183       e->_prev_out=_tail->_last_out_edge;

   184       if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;

   185       _tail->_last_out_edge=e;

   186       if (!_tail->_first_out_edge) _tail->_first_out_edge=e;

   187       e->_next_out=0;

   188     }

   190     void _set_head(edge_item* e, node_item* _head) {

   191       if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else

   192 	(e->_head)->_last_in_edge=e->_prev_in;

   193       if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else

   194 	(e->_head)->_first_in_edge=e->_next_in;

   196       e->_head=_head;

   198       e->_prev_in=_head->_last_in_edge;

   199       if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;

   200       _head->_last_in_edge=e;

   201       if (!_head->_first_in_edge) { _head->_first_in_edge=e; }

   202       e->_next_in=0;

   203     }

   205   public:

   207     /* default constructor */

   209     ListGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }

   211     ~ListGraph() {

   212       while (first<NodeIt>().valid()) erase(first<NodeIt>());

   213     }

   215     int nodeNum() const { return _node_num; }

   216     int edgeNum() const { return _edge_num; }

   218     /* functions to construct iterators from the graph, or from each other */

   220     //NodeIt firstNode() const { return NodeIt(*this); }

   221     //EdgeIt firstEdge() const { return EdgeIt(*this); }

   223     //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); }

   224     //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); }

   225     //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); }

   226     Node tail(Edge e) const { return e.tailNode(); }

   227     Node head(Edge e) const { return e.headNode(); }

   229     Node aNode(const OutEdgeIt& e) const { return e.aNode(); }

   230     Node aNode(const InEdgeIt& e) const { return e.aNode(); }

   231     Node aNode(const SymEdgeIt& e) const { return e.aNode(); }

   233     Node bNode(const OutEdgeIt& e) const { return e.bNode(); }

   234     Node bNode(const InEdgeIt& e) const { return e.bNode(); }

   235     Node bNode(const SymEdgeIt& e) const { return e.bNode(); }

   237     //Node invalid_node() { return Node(); }

   238     //Edge invalid_edge() { return Edge(); }

   239     //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); }

   240     //InEdgeIt invalid_in_edge() { return InEdgeIt(); }

   241     //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); }

   243     /* same methods in other style */

   244     /* for experimental purpose */

   246     NodeIt& /*getF*/first(NodeIt& v) const {

   247       v=NodeIt(*this); return v; }

   248     EdgeIt& /*getF*/first(EdgeIt& e) const {

   249       e=EdgeIt(*this); return e; }

   250     OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const {

   251       e=OutEdgeIt(*this, v); return e; }

   252     InEdgeIt& /*getF*/first(InEdgeIt& e, Node v) const {

   253       e=InEdgeIt(*this, v); return e; }

   254     SymEdgeIt& /*getF*/first(SymEdgeIt& e, Node v) const {

   255       e=SymEdgeIt(*this, v); return e; }

   256     //void getTail(Node& n, const Edge& e) const { n=tail(e); }

   257     //void getHead(Node& n, const Edge& e) const { n=head(e); }

   259     //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); }

   260     //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); }

   261     //void getANode(Node& n, const SymEdgeIt& e) const { n=e.aNode(); }

   262     //void getBNode(Node& n, const OutEdgeIt& e) const { n=e.bNode(); }

   263     //void getBNode(Node& n, const InEdgeIt& e) const { n=e.bNode(); }

   264     //void getBNode(Node& n, const SymEdgeIt& e) const { n=e.bNode(); }

   265     //void get_invalid(Node& n) { n=Node(); }

   266     //void get_invalid(Edge& e) { e=Edge(); }

   267     //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }

   268     //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }

   269     //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }

   271     template< typename It >

   272     It first() const {

   273       It e;

   274       /*getF*/first(e);

   275       return e;

   276     }

   278     template< typename It >

   279     It first(Node v) const {

   280       It e;

   281       /*getF*/first(e, v);

   282       return e;

   283     }

   285     bool valid(Node n) const { return n.valid(); }

   286     bool valid(Edge e) const { return e.valid(); }

   288     template <typename It> It getNext(It it) const {

   289       It tmp(it); return next(tmp); }

   290     template <typename It> It& next(It& it) const { return ++it; }

   293     /* for getting id's of graph objects */

   294     /* these are important for the implementation of property vectors */

   296     int id(Node v) const { return v.node->id; }

   297     int id(Edge e) const { return e.edge->id; }

   299     /* adding nodes and edges */

   301     Node addNode() {

   302 			Node n = _add_node();

   303 			node_maps.add(n);

   304 			return n;

   305 		}

   306     Edge addEdge(Node u, Node v) {

   307 			Edge e = _add_edge(u.node, v.node);

   308 			edge_maps.add(e);

   309       return e;

   310     }

   312     void erase(Node i) {

   313 			node_map.erase(i);

   314       while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));

   315       while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));

   316       _delete_node(i.node);

   317     }

   319     void erase(Edge e) {

   320 			edge_maps.erase(e);

   321 			_delete_edge(e.edge);

   322 		}

   324     void clear() {

   325       while (first<NodeIt>().valid()) erase(first<NodeIt>());

   326     }

   328     void setTail(Edge e, Node tail) {

   329       _set_tail(e.edge, tail.node);

   330     }

   332     void setHead(Edge e, Node head) {

   333       _set_head(e.edge, head.node);

   334     }

   336     /* stream operations, for testing purpose */

   338     friend std::ostream& operator<<(std::ostream& os, const Node& i) {

   339       os << i.node->id; return os;

   340     }

   341     friend std::ostream& operator<<(std::ostream& os, const Edge& i) {

   342       os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";

   343       return os;

   344     }

   346     class Node {

   347       friend class ListGraph;

   348       template <typename T> friend class NodeMap;

   350       friend class Edge;

   351       friend class OutEdgeIt;

   352       friend class InEdgeIt;

   353       friend class SymEdgeIt;

   354       //public:  //FIXME: It is required by op= of NodeIt

   355     protected:

   356       node_item* node;

   357     protected:

   358       friend int ListGraph::id(Node v) const;

   359     public:

   360       Node() /*: node(0)*/ { }

   361       Node(const Invalid&) : node(0) { }

   362     protected:

   363       Node(node_item* _node) : node(_node) { }

   364       bool valid() const { return (node); }

   365     public:

   366       //void makeInvalid() { node=0; }

   367       friend bool operator==(Node u, Node v) { return v.node==u.node; }

   368       friend bool operator!=(Node u, Node v) { return v.node!=u.node; }

   369       friend std::ostream& operator<<(std::ostream& os, const Node& i);

   370     };

   372     class NodeIt : public Node {

   373       friend class ListGraph;

   374       //protected:

   375     public: //for everybody but marci

   376       NodeIt(const ListGraph& G) : Node(G._first_node) { }

   377     public:

   378       NodeIt() : Node() { }

   379       NodeIt(const Invalid& i) : Node(i) { }

   380     protected:

   381       NodeIt(node_item* v) : Node(v) { }

   382       NodeIt& operator++() { node=node->_next_node; return *this; }

   383       //FIXME::

   384       //      NodeIt& operator=(const Node& e)

   385       //      { node=e.node; return *this; }

   386     };

   388     class Edge {

   389       friend class ListGraph;

   390       template <typename T> friend class EdgeMap;

   392       friend class Node;

   393       friend class NodeIt;

   394     protected:

   395       edge_item* edge;

   396       friend int ListGraph::id(Edge e) const;

   397     public:

   398       Edge() /*: edge(0)*/ { }

   399       Edge(const Invalid&) : edge(0) { }

   400       //Edge() { }

   401     protected:

   402       Edge(edge_item* _edge) : edge(_edge) { }

   403       bool valid() const { return (edge); }

   404     public:

   405       //void makeInvalid() { edge=0; }

   406       friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; }

   407       friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; }

   408     protected:

   409       Node tailNode() const { return Node(edge->_tail); }

   410       Node headNode() const { return Node(edge->_head); }

   411     public:

   412       friend std::ostream& operator<<(std::ostream& os, const Edge& i);

   413     };

   415     class EdgeIt : public Edge {

   416       friend class ListGraph;

   417       //protected:

   418     public: //for alpar

   419       EdgeIt(const ListGraph& G) {

   420 	node_item* v=G._first_node;

   421 	if (v) edge=v->_first_out_edge; else edge=0;

   422 	while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }

   423       }

   424     public:

   425       EdgeIt() : Edge() { }

   426       EdgeIt(const Invalid& i) : Edge(i) { }

   427     protected:

   428       EdgeIt(edge_item* _e) : Edge(_e) { }

   429       EdgeIt& operator++() {

   430 	node_item* v=edge->_tail;

   431 	edge=edge->_next_out;

   432 	while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }

   433 	return *this;

   434       }

   435     };

   437     class OutEdgeIt : public Edge {

   438       friend class ListGraph;

   439       //node_item* v;

   440       //protected:

   441     protected: //for alpar

   442       OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }

   443     public:

   444       OutEdgeIt() : Edge()/*, v(0)*/ { }

   445       OutEdgeIt(const Invalid& i) : Edge(i) { }

   446       OutEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }

   447     protected:

   448       OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }

   449     protected:

   450       Node aNode() const { return Node(edge->_tail); }

   451       Node bNode() const { return Node(edge->_head); }

   452     };

   454     class InEdgeIt : public Edge {

   455       friend class ListGraph;

   456       //node_item* v;

   457       //protected:

   458     protected: //for alpar

   459       InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }

   460     public:

   461       InEdgeIt() : Edge()/*, v(0)*/ { }

   462       InEdgeIt(const Invalid& i) : Edge(i) { }

   463       InEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }

   464     protected:

   465       InEdgeIt& operator++() { edge=edge->_next_in; return *this; }

   466     protected:

   467       Node aNode() const { return Node(edge->_head); }

   468       Node bNode() const { return Node(edge->_tail); }

   469     };

   471     class SymEdgeIt : public Edge {

   472       friend class ListGraph;

   473       bool out_or_in; //1 iff out, 0 iff in

   474       //node_item* v;

   475       //protected:

   476     public: //for alpar

   477       SymEdgeIt(const Node& _v) /*: v(_v.node)*/ {

   478 	out_or_in=1;

   479 	edge=_v.node->_first_out_edge;

   480 	if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }

   481       }

   482     public:

   483       SymEdgeIt() : Edge() /*, v(0)*/ { }

   484       SymEdgeIt(const Invalid& i) : Edge(i) { }

   485       SymEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ {

   486 	out_or_in=1;

   487 	edge=_v.node->_first_out_edge;

   488 	if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }

   489       }

   490     protected:

   491       SymEdgeIt& operator++() {

   492 	if (out_or_in) {

   493 	  node_item* v=edge->_tail;

   494 	  edge=edge->_next_out;

   495 	  if (!edge) { out_or_in=0; edge=v->_first_in_edge; }

   496 	} else {

   497 	  edge=edge->_next_in;

   498 	}

   499 	return *this;

   500       }

   501     protected:

   502       Node aNode() const {

   503 	return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); }

   504       Node bNode() const {

   505 	return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); }

   506     };

   508   };

   510 //   template< typename T >

   511 //   T ListGraph::first() const {

   512 //     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>();" << std::endl;

   513 //     return T();

   514 //   }

   516 //   template<>

   517 //   ListGraph::NodeIt ListGraph::first<ListGraph::NodeIt>() const {

   518 //     return firstNode();

   519 //   }

   521 //   template<>

   522 //   ListGraph::EdgeIt ListGraph::first<ListGraph::EdgeIt>() const {

   523 //     return firstEdge();

   524 //   }

   526 //   template< typename T >

   527 //   T ListGraph::first(ListGraph::Node v) const {

   528 //     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>(ListGRaph::Node);" << std::endl;

   529 //     return T();

   530 //   }

   532 //   template<>

   533 //   ListGraph::OutEdgeIt ListGraph::first<ListGraph::OutEdgeIt>(const ListGraph::Node v) const {

   534 //     return firstOutEdge(v);

   535 //   }

   537 //   template<>

   538 //   ListGraph::InEdgeIt ListGraph::first<ListGraph::InEdgeIt>(const ListGraph::Node v) const {

   539 //     return firstInEdge(v);

   540 //   }

   542 //   template<>

   543 //   ListGraph::SymEdgeIt ListGraph::first<ListGraph::SymEdgeIt>(const ListGraph::Node v) const {

   544 //     return firstSymEdge(v);

   545 //   }

   548 } //namespace hugo

   550 #endif //HUGO_LIST_GRAPH_H

author	jacint
	Thu, 22 Apr 2004 14:50:24 +0000
changeset 373	259ea2d741a2
parent 262	60de0f16a4a1
child 377	33fe0ee01dc5
permissions	-rw-r--r--