lemon-0.x: src/work/list_graph.hh@0f1aacd7867b

     1 #ifndef MARCI_LIST_GRAPH_HH

     2 #define MARCI_LIST_GRAPH_HH

     4 #include <iostream>

     6 namespace marci {

     8   template <typename It>

     9   int number_of(It _it) {

    10     int i=0;

    11     for( ; _it.valid(); ++_it) { ++i; }

    12     return i;

    13   }

    15   template <typename It>

    16   int count(It it) {

    17     int i=0;

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

    19     return i;

    20   }

    22   class ListGraph {

    23     class node_item;

    24     class edge_item;

    25   public:

    26     class NodeIt;

    27     class EachNodeIt;

    28     class EdgeIt;

    29     class EachEdgeIt;

    30     class OutEdgeIt;

    31     class InEdgeIt;

    32     class SymEdgeIt;

    34     template <typename T>

    35     class NodeMap {

    36       //typedef typename Graph::NodeIt NodeIt;

    37       //typedef typename Graph::EachNodeIt EachNodeIt;

    38       const ListGraph& G;

    39       std::vector<T> container;

    40     public:

    41       NodeMap(const ListGraph& _G) : G(_G) {

    42 	int i=0;

    43 	for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) ++i;

    44 	container.resize(i);

    45       }

    46       NodeMap(const ListGraph& _G, const T a) : G(_G) {

    47 	for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) {

    48 	  container.push_back(a);

    49 	}

    50       }

    51       void set(const NodeIt nit, const T a) { container[G.id(nit)]=a; }

    52       T get(const NodeIt nit) const { return container[G.id(nit)]; }

    53     };

    55     template <typename T>

    56     class EdgeMap {

    57       //typedef typename Graph::EdgeIt EdgeIt;

    58       //typedef typename Graph::EachEdgeIt EachEdgeIt;

    59       const ListGraph& G;

    60       std::vector<T> container;

    61     public:

    62       EdgeMap(const ListGraph& _G) : G(_G) {

    63 	int i=0;

    64 	for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) ++i;

    65 	container.resize(i);

    66       }

    67       EdgeMap(const ListGraph& _G, const T a) : G(_G) {

    68 	for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) {

    69 	  container.push_back(a);

    70 	}

    71       }

    72       void set(const EdgeIt eit, const T a) { container[G.id(eit)]=a; }

    73       T get(const EdgeIt eit) const { return container[G.id(eit)]; }

    74     };

    76     //typedef template<typename T> NodePropertyVector<ListGraph, T> NodeMap;

    77     //template <typename T>

    78     //typedef NodePropertyVector<ListGraph, T> NodeMap;

    79     //template <typename T>

    80     //typedef typename NodePropertyVector<ListGraph, T> NodeMap;

    81     //template <typename T>

    82     //typedef NodePropertyVector<typename ListGraph, T> NodeMap;

    83     //template <typename T>

    84     //typedef typename NodePropertyVector<typename ListGraph, T> NodeMap;

    85     //template <typename T>

    86     //typedef template NodePropertyVector<ListGraph, T> NodeMap;

    87     //template <typename T>

    88     //typedef template typename NodePropertyVector<ListGraph, T> NodeMap;

    89     //template <typename T>

    90     //typedef template NodePropertyVector<typename ListGraph, T> NodeMap;

    91     //template <typename T>

    92     //typedef template typename NodePropertyVector<typename ListGraph, T> NodeMap;

    93     //template <typename T>

    94     //typedef EdgePropertyVector<ListGraph, T> EdgeMap;

    96   private:

    97     int node_id;

    98     int edge_id;

    99     int _node_num;

   100     int _edge_num;

   102     node_item* _first_node;

   103     node_item* _last_node;

   105     class node_item {

   106       friend class ListGraph;

   107       friend class NodeIt;

   108       friend class EachNodeIt;

   109       friend class EdgeIt;

   110       friend class EachEdgeIt;

   111       friend class OutEdgeIt;

   112       friend class InEdgeIt;

   113       friend class SymEdgeIt;

   114       friend std::ostream& operator<<(std::ostream& os, const NodeIt& i);

   115       friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);

   116       ListGraph* G;

   117       int id;

   118       edge_item* _first_out_edge;

   119       edge_item* _last_out_edge;

   120       edge_item* _first_in_edge;

   121       edge_item* _last_in_edge;

   122       node_item* _next_node;

   123       node_item* _prev_node;

   124     public:

   125       node_item() { }

   126     };

   128     class edge_item {

   129       friend class ListGraph;

   130       friend class NodeIt;

   131       friend class EachNodeIt;

   132       friend class EdgeIt;

   133       friend class EachEdgeIt;

   134       friend class OutEdgeIt;

   135       friend class InEdgeIt;

   136       friend class SymEdgeIt;

   137       friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);

   138       ListGraph* G;

   139       int id;

   140       node_item* _tail;

   141       node_item* _head;

   142       edge_item* _next_out;

   143       edge_item* _prev_out;

   144       edge_item* _next_in;

   145       edge_item* _prev_in;

   146     public:

   147       edge_item() { }

   148     };

   150     node_item* _add_node() {

   151       node_item* p=new node_item;

   152       p->id=node_id++;

   153       p->_first_out_edge=0;

   154       p->_last_out_edge=0;

   155       p->_first_in_edge=0;

   156       p->_last_in_edge=0;

   157       p->_prev_node=_last_node;

   158       p->_next_node=0;

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

   160       _last_node=p;

   161       if (!_first_node) _first_node=p;

   163       ++_node_num;

   164       return p;

   165     }

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

   168       edge_item* e=new edge_item;

   169       e->id=edge_id++;

   170       e->_tail=_tail;

   171       e->_head=_head;

   173       e->_prev_out=_tail->_last_out_edge;

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

   175       _tail->_last_out_edge=e;

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

   177       e->_next_out=0;

   179       e->_prev_in=_head->_last_in_edge;

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

   181       _head->_last_in_edge=e;

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

   183       e->_next_in=0;

   185       ++_edge_num;

   186       return e;

   187     }

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

   190     void _delete_node(node_item* v) {

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

   192 	_last_node=v->_prev_node;

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

   194 	_first_node=v->_next_node;

   196       delete v;

   197       --_node_num;

   198     }

   200     void _delete_edge(edge_item* e) {

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

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

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

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

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

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

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

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

   210       delete e;

   211       --_edge_num;

   212     }

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

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

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

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

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

   220       e->_tail=_tail;

   222       e->_prev_out=_tail->_last_out_edge;

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

   224       _tail->_last_out_edge=e;

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

   226       e->_next_out=0;

   227     }

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

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

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

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

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

   235       e->_head=_head;

   237       e->_prev_in=_head->_last_in_edge;

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

   239       _head->_last_in_edge=e;

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

   241       e->_next_in=0;

   242     }

   244   public:

   246     /* default constructor */

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

   250     ~ListGraph() {

   251       while (first<EachNodeIt>().valid()) deleteNode(first<EachNodeIt>());

   252     }

   254     int nodeNum() const { return _node_num; }

   255     int edgeNum() const { return _edge_num; }

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

   259     EachNodeIt firstNode() const { return EachNodeIt(_first_node); }

   260     EachEdgeIt firstEdge() const {

   261       node_item* v=_first_node;

   262       edge_item* edge=v->_first_out_edge;

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

   264       return EachEdgeIt(v, edge);

   265     }

   267     //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); }

   268     InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }

   269     SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }

   270     NodeIt tail(const EdgeIt e) const { return e.tailNode(); }

   271     NodeIt head(const EdgeIt e) const { return e.headNode(); }

   273     NodeIt aNode(const OutEdgeIt& e) const { return e.aNode(); }

   274     NodeIt aNode(const InEdgeIt& e) const { return e.aNode(); }

   275     NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }

   277     NodeIt bNode(const OutEdgeIt& e) const { return e.bNode(); }

   278     NodeIt bNode(const InEdgeIt& e) const { return e.bNode(); }

   279     NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }

   281     //NodeIt invalid_node() { return NodeIt(); }

   282     //EdgeIt invalid_edge() { return EdgeIt(); }

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

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

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

   287     /* same methods in other style */

   288     /* for experimental purpose */

   290     void getFirst(EachNodeIt& v) const { v=EachNodeIt(_first_node); }

   291     void getFirst(EachEdgeIt& e) const { e=firstEdge(); }

   292     void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); }

   293     void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); }

   294     void getFirst(SymEdgeIt& e, const NodeIt& v) const { e=SymEdgeIt(v); }

   295     void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); }

   296     void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); }

   298     void getANode(NodeIt& n, const OutEdgeIt& e) const { n=e.aNode(); }

   299     void getANode(NodeIt& n, const InEdgeIt& e) const { n=e.aNode(); }

   300     void getANode(NodeIt& n, const SymEdgeIt& e) const { n=e.aNode(); }

   301     void getBNode(NodeIt& n, const OutEdgeIt& e) const { n=e.bNode(); }

   302     void getBNode(NodeIt& n, const InEdgeIt& e) const { n=e.bNode(); }

   303     void getBNode(NodeIt& n, const SymEdgeIt& e) const { n=e.bNode(); }

   304     //void get_invalid(NodeIt& n) { n=NodeIt(); }

   305     //void get_invalid(EdgeIt& e) { e=EdgeIt(); }

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

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

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

   310     template< typename It >

   311     It first() const {

   312       It e;

   313       getFirst(e);

   314       return e;

   315     }

   317     template< typename It >

   318     It first(const NodeIt v) const {

   319       It e;

   320       getFirst(e, v);

   321       return e;

   322     }

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

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

   327     int id(const NodeIt v) const { return v.node->id; }

   328     int id(const EdgeIt e) const { return e.edge->id; }

   330     /* adding nodes and edges */

   332     NodeIt addNode() { return NodeIt(_add_node()); }

   333     EdgeIt addEdge(const NodeIt u, const NodeIt v) {

   334       return EdgeIt(_add_edge(u.node, v.node));

   335     }

   337     void deleteNode(const NodeIt i) {

   338       while (first<OutEdgeIt>(i).valid()) deleteEdge(first<OutEdgeIt>(i));

   339       while (first<InEdgeIt>(i).valid()) deleteEdge(first<InEdgeIt>(i));

   340       _delete_node(i.node);

   341     }

   343     void deleteEdge(const EdgeIt e) { _delete_edge(e.edge); }

   345     void setTail(const EdgeIt e, const NodeIt tail) {

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

   347     }

   349     void setHead(const EdgeIt e, const NodeIt head) {

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

   351     }

   353     /* stream operations, for testing purpose */

   355     friend std::ostream& operator<<(std::ostream& os, const NodeIt& i) {

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

   357     }

   358     friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i) {

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

   360       return os;

   361     }

   363     class NodeIt {

   364       friend class ListGraph;

   366       friend class EdgeIt;

   367       friend class OutEdgeIt;

   368       friend class InEdgeIt;

   369       friend class SymEdgeIt;

   370     protected:

   371       node_item* node;

   372       friend int ListGraph::id(const NodeIt v) const;

   373     public:

   374       NodeIt() : node(0) { }

   375       NodeIt(node_item* _node) : node(_node) { }

   376       bool valid() const { return (node!=0); }

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

   378       friend bool operator==(const NodeIt& u, const NodeIt& v) {

   379 	return v.node==u.node;

   380       }

   381       friend bool operator!=(const NodeIt& u, const NodeIt& v) {

   382 	return v.node!=u.node;

   383       }

   384       friend std::ostream& operator<<(std::ostream& os, const NodeIt& i);

   385     };

   387     class EachNodeIt : public NodeIt {

   388       friend class ListGraph;

   389     public:

   390       EachNodeIt() : NodeIt() { }

   391       EachNodeIt(node_item* v) : NodeIt(v) { }

   392       EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }

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

   394     };

   396     class EdgeIt {

   397       friend class ListGraph;

   399       friend class NodeIt;

   400       friend class EachNodeIt;

   401     protected:

   402       edge_item* edge;

   403       friend int ListGraph::id(const EdgeIt e) const;

   404     public:

   405       EdgeIt() : edge(0) { }

   406       //EdgeIt() { }

   407       EdgeIt(edge_item* _edge) : edge(_edge) { }

   408       bool valid() const { return (edge!=0); }

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

   410       friend bool operator==(const EdgeIt& u, const EdgeIt& v) {

   411 	return v.edge==u.edge;

   412       }

   413       friend bool operator!=(const EdgeIt& u, const EdgeIt& v) {

   414 	return v.edge!=u.edge;

   415       }

   416     protected:

   417       NodeIt tailNode() const { return NodeIt(edge->_tail); }

   418       NodeIt headNode() const { return NodeIt(edge->_head); }

   419     public:

   420       friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);

   421     };

   423     class EachEdgeIt : public EdgeIt {

   424       friend class ListGraph;

   425       node_item* v;

   426     public:

   427       EachEdgeIt() : EdgeIt(), v(0) { }

   428       EachEdgeIt(node_item* _v, edge_item* _e) : EdgeIt(_e), v(_v) { }

   429       EachEdgeIt(const ListGraph& G) {

   430 	v=G._first_node;

   431 	edge=v->_first_out_edge;

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

   433       }

   434       EachEdgeIt& operator++() {

   435 	edge=edge->_next_out;

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

   437 	return *this;

   438       }

   439     };

   441     class OutEdgeIt : public EdgeIt {

   442       friend class ListGraph;

   443       node_item* v;

   444     public:

   445       OutEdgeIt() : EdgeIt(), v(0) { }

   446     protected:

   447       OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }

   448     public:

   449       OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }

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

   451     protected:

   452       NodeIt aNode() const { return NodeIt(v); }

   453       NodeIt bNode() const {

   454 	return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }

   455     };

   457     class InEdgeIt : public EdgeIt {

   458       friend class ListGraph;

   459       node_item* v;

   460     public:

   461       InEdgeIt() : EdgeIt(), v(0) { }

   462     protected:

   463       InEdgeIt(const NodeIt& _v) : v(_v.node) {

   464 	edge=v->_first_in_edge;

   465       }

   466     public:

   467       InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }

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

   469     protected:

   470       NodeIt aNode() const { return NodeIt(v); }

   471       NodeIt bNode() const {

   472 	return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }

   473     };

   475     class SymEdgeIt : public EdgeIt {

   476       friend class ListGraph;

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

   478       node_item* v;

   479     public:

   480       SymEdgeIt() : EdgeIt(), v(0) { }

   481     protected:

   482       SymEdgeIt(const NodeIt& _v) : v(_v.node) {

   483 	out_or_in=1;

   484 	edge=v->_first_out_edge;

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

   486       }

   487     public:

   488       SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) {

   489 	out_or_in=1;

   490 	edge=v->_first_out_edge;

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

   492       }

   493       SymEdgeIt& operator++() {

   494 	if (out_or_in) {

   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       NodeIt aNode() const { return NodeIt(v); }

   504       NodeIt bNode() const {

   505 	return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }

   506     };

   508   };

   510   /*

   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::EachNodeIt ListGraph::first<ListGraph::EachNodeIt>() const {

   519     return firstNode();

   520   }

   522   template<>

   523   ListGraph::EachEdgeIt ListGraph::first<ListGraph::EachEdgeIt>() const {

   524     return firstEdge();

   525   }

   527   template< typename T >

   528   T ListGraph::first(ListGraph::NodeIt v) const {

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

   530     return T();

   531   }

   533   template<>

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

   535     return firstOutEdge(v);

   536   }

   538   template<>

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

   540     return firstInEdge(v);

   541   }

   543   template<>

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

   545     return firstSymEdge(v);

   546   }

   547   */

   550 } //namespace marci

   552 #endif //MARCI_LIST_GRAPH_HH

author	marci
	Fri, 30 Jan 2004 14:52:04 +0000
changeset 46	0f1aacd7867b
child 59	41c7f9c09a12
permissions	-rw-r--r--