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

     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_factory.h"

    12 namespace hugo {

    14   template <typename It>

    15   int count(It it) {

    16     int i=0;

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

    18     return i;

    19   }

    21   class ListGraph {

    22     class node_item;

    23     class edge_item;

    24   public:

    25     class Node;

    26     class NodeIt;

    27     class Edge;

    28     class EdgeIt;

    29     class OutEdgeIt;

    30     class InEdgeIt;

    31     class SymEdgeIt;

    33 //    template <typename T> class NodeMap;

    34 //    template <typename T> class EdgeMap;

    35   private:

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

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

    39   private:

    42 	public:

    44 		typedef MapRegistry<ListGraph, Node, NodeIt> NodeMapRegistry;

    45 		NodeMapRegistry node_maps;

    48 		typedef MapRegistry<ListGraph, Edge, EdgeIt> EdgeMapRegistry;

    49 		EdgeMapRegistry edge_maps;

    51 		typedef VectorMapFactory<ListGraph, Edge, EdgeIt> EdgeMapFactory;

    52 		typedef VectorMapFactory<ListGraph, Node, NodeIt> NodeMapFactory;

    55     int node_id;

    56     int edge_id;

    57     int _node_num;

    58     int _edge_num;

    60     node_item* _first_node;

    61     node_item* _last_node;

    63     class node_item {

    64       friend class ListGraph;

    65       template <typename T> friend class NodeMap;

    67       friend class Node;

    68       friend class NodeIt;

    69       friend class Edge;

    70       friend class EdgeIt;

    71       friend class OutEdgeIt;

    72       friend class InEdgeIt;

    73       friend class SymEdgeIt;

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

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

    76       //ListGraph* G;

    77       int id;

    78       edge_item* _first_out_edge;

    79       edge_item* _last_out_edge;

    80       edge_item* _first_in_edge;

    81       edge_item* _last_in_edge;

    82       node_item* _next_node;

    83       node_item* _prev_node;

    84     public:

    85       node_item() { }

    86     };

    88     class edge_item {

    89       friend class ListGraph;

    90       template <typename T> friend class EdgeMap;

    92       friend class Node;

    93       friend class NodeIt;

    94       friend class Edge;

    95       friend class EdgeIt;

    96       friend class OutEdgeIt;

    97       friend class InEdgeIt;

    98       friend class SymEdgeIt;

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

   100       //ListGraph* G;

   101       int id;

   102       node_item* _tail;

   103       node_item* _head;

   104       edge_item* _next_out;

   105       edge_item* _prev_out;

   106       edge_item* _next_in;

   107       edge_item* _prev_in;

   108     public:

   109       edge_item() { }

   110     };

   112     node_item* _add_node() {

   113       node_item* p=new node_item;

   114       p->id=node_id++;

   115       p->_first_out_edge=0;

   116       p->_last_out_edge=0;

   117       p->_first_in_edge=0;

   118       p->_last_in_edge=0;

   119       p->_prev_node=_last_node;

   120       p->_next_node=0;

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

   122       _last_node=p;

   123       if (!_first_node) _first_node=p;

   125       ++_node_num;

   126       return p;

   127     }

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

   130       edge_item* e=new edge_item;

   131       e->id=edge_id++;

   132       e->_tail=_tail;

   133       e->_head=_head;

   135       e->_prev_out=_tail->_last_out_edge;

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

   137       _tail->_last_out_edge=e;

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

   139       e->_next_out=0;

   141       e->_prev_in=_head->_last_in_edge;

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

   143       _head->_last_in_edge=e;

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

   145       e->_next_in=0;

   147       ++_edge_num;

   148       return e;

   149     }

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

   152     void _delete_node(node_item* v) {

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

   154 	_last_node=v->_prev_node;

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

   156 	_first_node=v->_next_node;

   158       delete v;

   159       --_node_num;

   160     }

   162     void _delete_edge(edge_item* e) {

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

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

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

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

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

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

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

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

   172       delete e;

   173       --_edge_num;

   174     }

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

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

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

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

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

   182       e->_tail=_tail;

   184       e->_prev_out=_tail->_last_out_edge;

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

   186       _tail->_last_out_edge=e;

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

   188       e->_next_out=0;

   189     }

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

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

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

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

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

   197       e->_head=_head;

   199       e->_prev_in=_head->_last_in_edge;

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

   201       _head->_last_in_edge=e;

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

   203       e->_next_in=0;

   204     }

   206   public:

   208     /* default constructor */

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

   212     ~ListGraph() {

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

   214     }

   216     int nodeNum() const { return _node_num; }

   217     int edgeNum() const { return _edge_num; }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   244     /* same methods in other style */

   245     /* for experimental purpose */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   272     template< typename It >

   273     It first() const {

   274       It e;

   275       /*getF*/first(e);

   276       return e;

   277     }

   279     template< typename It >

   280     It first(Node v) const {

   281       It e;

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

   283       return e;

   284     }

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

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

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

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

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

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

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

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

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

   300     /* adding nodes and edges */

   302     Node addNode() {

   303 			Node n = _add_node();

   304 			node_maps.add(n);

   305 			return n;

   306 		}

   307     Edge addEdge(Node u, Node v) {

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

   309 			edge_maps.add(e);

   310       return e;

   311     }

   313     void erase(Node i) {

   314 			node_maps.erase(i);

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

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

   317       _delete_node(i.node);

   318     }

   320     void erase(Edge e) {

   321 			edge_maps.erase(e);

   322 			_delete_edge(e.edge);

   323 		}

   325     void clear() {

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

   327     }

   329     void setTail(Edge e, Node tail) {

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

   331     }

   333     void setHead(Edge e, Node head) {

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

   335     }

   337     /* stream operations, for testing purpose */

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

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

   341     }

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

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

   344       return os;

   345     }

   347     class Node {

   348       friend class ListGraph;

   349       template <typename T> friend class NodeMap;

   351       friend class Edge;

   352       friend class OutEdgeIt;

   353       friend class InEdgeIt;

   354       friend class SymEdgeIt;

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

   356     protected:

   357       node_item* node;

   358     protected:

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

   360     public:

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

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

   363     protected:

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

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

   366     public:

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

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

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

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

   371     };

   373     class NodeIt : public Node {

   374       friend class ListGraph;

   375       //protected:

   376     public: //for everybody but marci

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

   378     public:

   379       NodeIt() : Node() { }

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

   381     protected:

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

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

   384       //FIXME::

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

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

   387     };

   389     class Edge {

   390       friend class ListGraph;

   391       template <typename T> friend class EdgeMap;

   393       friend class Node;

   394       friend class NodeIt;

   395     protected:

   396       edge_item* edge;

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

   398     public:

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

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

   401       //Edge() { }

   402     protected:

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

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

   405     public:

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

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

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

   409     protected:

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

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

   412     public:

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

   414     };

   416     class EdgeIt : public Edge {

   417       friend class ListGraph;

   418       //protected:

   419     public: //for alpar

   420       EdgeIt(const ListGraph& G) {

   421 	node_item* v=G._first_node;

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

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

   424       }

   425     public:

   426       EdgeIt() : Edge() { }

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

   428     protected:

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

   430       EdgeIt& operator++() {

   431 	node_item* v=edge->_tail;

   432 	edge=edge->_next_out;

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

   434 	return *this;

   435       }

   436     };

   438     class OutEdgeIt : public Edge {

   439       friend class ListGraph;

   440       //node_item* v;

   441       //protected:

   442     protected: //for alpar

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

   444     public:

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

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

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

   448     protected:

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

   450     protected:

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

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

   453     };

   455     class InEdgeIt : public Edge {

   456       friend class ListGraph;

   457       //node_item* v;

   458       //protected:

   459     protected: //for alpar

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

   461     public:

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

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

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

   465     protected:

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

   467     protected:

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

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

   470     };

   472     class SymEdgeIt : public Edge {

   473       friend class ListGraph;

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

   475       //node_item* v;

   476       //protected:

   477     public: //for alpar

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

   479 	out_or_in=1;

   480 	edge=_v.node->_first_out_edge;

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

   482       }

   483     public:

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

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

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

   487 	out_or_in=1;

   488 	edge=_v.node->_first_out_edge;

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

   490       }

   491     protected:

   492       SymEdgeIt& operator++() {

   493 	if (out_or_in) {

   494 	  node_item* v=edge->_tail;

   495 	  edge=edge->_next_out;

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

   497 	} else {

   498 	  edge=edge->_next_in;

   499 	}

   500 	return *this;

   501       }

   502     protected:

   503       Node aNode() const {

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

   505       Node bNode() const {

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

   507     };

   509   };

   511 //   template< typename T >

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

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

   514 //     return T();

   515 //   }

   517 //   template<>

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

   519 //     return firstNode();

   520 //   }

   522 //   template<>

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

   524 //     return firstEdge();

   525 //   }

   527 //   template< typename T >

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

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

   530 //     return T();

   531 //   }

   533 //   template<>

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

   535 //     return firstOutEdge(v);

   536 //   }

   538 //   template<>

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

   540 //     return firstInEdge(v);

   541 //   }

   543 //   template<>

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

   545 //     return firstSymEdge(v);

   546 //   }

   549 } //namespace hugo

   551 #endif //HUGO_LIST_GRAPH_H

author	jacint
	Fri, 07 May 2004 10:34:36 +0000
changeset 575	bdf7fb750e0e
parent 378	c3f93631cd24
child 595	e10b5e9419ef
permissions	-rw-r--r--