edge_set.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_EDGE_SET_H
00020 #define LEMON_EDGE_SET_H
00021 
00027 
00028 namespace lemon {
00029 
00030   template <typename _Graph>
00031   class ListEdgeSetBase {
00032   public:
00033 
00034     typedef _Graph Graph;
00035     typedef typename Graph::Node Node;
00036     typedef typename Graph::NodeIt NodeIt;
00037 
00038   protected:
00039 
00040     struct NodeT {
00041       int first_out, first_in;
00042       NodeT() : first_out(-1), first_in(-1) {}
00043     };
00044 
00045     typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
00046 
00047     NodesImplBase* nodes;
00048 
00049     struct EdgeT {
00050       Node source, target;
00051       int next_out, next_in;
00052       int prev_out, prev_in;
00053       EdgeT() : prev_out(-1), prev_in(-1) {}
00054     };
00055 
00056     std::vector<EdgeT> edges;
00057 
00058     int first_edge;
00059     int first_free_edge;
00060 
00061     const Graph* graph;
00062 
00063     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
00064       graph = &_graph;
00065       nodes = &_nodes;
00066     }
00067     
00068   public:
00069 
00070     class Edge {
00071       friend class ListEdgeSetBase<Graph>;
00072     protected:
00073       Edge(int _id) : id(_id) {}
00074       int id;
00075     public:
00076       Edge() {}
00077       Edge(Invalid) : id(-1) {}
00078       bool operator==(const Edge& edge) const { return id == edge.id; }
00079       bool operator!=(const Edge& edge) const { return id != edge.id; }
00080       bool operator<(const Edge& edge) const { return id < edge.id; }
00081     };
00082 
00083     ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {} 
00084 
00085     Edge addEdge(const Node& source, const Node& target) {
00086       int n;
00087       if (first_free_edge == -1) {
00088         n = edges.size();
00089         edges.push_back(EdgeT());
00090       } else {
00091         n = first_free_edge;
00092         first_free_edge = edges[first_free_edge].next_in;
00093       }
00094       edges[n].next_in = (*nodes)[target].first_in;
00095       (*nodes)[target].first_in = n;
00096       edges[n].next_out = (*nodes)[source].first_out;
00097       (*nodes)[source].first_out = n;
00098       edges[n].source = source;
00099       edges[n].target = target;
00100       return Edge(n);
00101     }
00102 
00103     void erase(const Edge& edge) {
00104       int n = edge.id;
00105       if (edges[n].prev_in != -1) {
00106         edges[edges[n].prev_in].next_in = edges[n].next_in;
00107       } else {
00108         (*nodes)[edges[n].target].first_in = edges[n].next_in;
00109       }
00110       if (edges[n].next_in != -1) {
00111         edges[edges[n].next_in].prev_in = edges[n].prev_in;
00112       }
00113 
00114       if (edges[n].prev_out != -1) {
00115         edges[edges[n].prev_out].next_out = edges[n].next_out;
00116       } else {
00117         (*nodes)[edges[n].source].first_out = edges[n].next_out;
00118       }
00119       if (edges[n].next_out != -1) {
00120         edges[edges[n].next_out].prev_out = edges[n].prev_out;
00121       }
00122            
00123     }
00124 
00125     void clear() {
00126       edges.clear();
00127       first_edge = -1;
00128       first_free_edge = -1;
00129     }
00130 
00131     void first(Node& node) const {
00132       graph->first(node);
00133     }
00134 
00135     void next(Node& node) const {
00136       graph->next(node);
00137     }
00138 
00139     void first(Edge& edge) const {
00140       Node node;
00141       for (first(node); node != INVALID && (*nodes)[node].first_in == -1; 
00142            next(node));
00143       edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
00144     }
00145 
00146     void next(Edge& edge) const {
00147       if (edges[edge.id].next_in != -1) {
00148         edge.id = edges[edge.id].next_in;
00149       } else {
00150         Node node = edges[edge.id].target;
00151         for (next(node); node != INVALID && (*nodes)[node].first_in == -1; 
00152              next(node));
00153         edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
00154       }      
00155     }
00156 
00157     void firstOut(Edge& edge, const Node& node) const {
00158       edge.id = (*nodes)[node].first_out;    
00159     }
00160     
00161     void nextOut(Edge& edge) const {
00162       edge.id = edges[edge.id].next_out;        
00163     }
00164 
00165     void firstIn(Edge& edge, const Node& node) const {
00166       edge.id = (*nodes)[node].first_in;          
00167     }
00168 
00169     void nextIn(Edge& edge) const {
00170       edge.id = edges[edge.id].next_in;    
00171     }
00172 
00173     int id(const Node& node) const { return graph->id(node); }
00174     int id(const Edge& edge) const { return edge.id; }
00175 
00176     Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
00177     Edge edgeFromId(int id) const { return Edge(id); }
00178 
00179     int maxNodeId() const { return graph->maxId(Node()); };
00180     int maxEdgeId() const { return edges.size() - 1; }
00181 
00182     Node source(const Edge& edge) const { return edges[edge.id].source;}
00183     Node target(const Edge& edge) const { return edges[edge.id].target;}
00184 
00185     template <typename _Value>
00186     class NodeMap : public Graph::template NodeMap<_Value> {
00187     public:
00188       typedef typename _Graph::template NodeMap<_Value> Parent;
00189       explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset) 
00190         : Parent(*edgeset.graph) { }
00191       NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
00192         : Parent(*edgeset.graph, value) { }
00193     };
00194 
00195   };
00196 
00212   template <typename _Graph>
00213   class ListEdgeSet :
00214     public ErasableEdgeSetExtender<
00215     ClearableEdgeSetExtender<
00216     ExtendableEdgeSetExtender<
00217     MappableEdgeSetExtender<
00218     IterableGraphExtender<
00219     AlterableEdgeSetExtender<
00220     GraphExtender<
00221     ListEdgeSetBase<_Graph> > > > > > > > {
00222 
00223   public:
00224 
00225     typedef ErasableEdgeSetExtender<
00226       ClearableEdgeSetExtender<
00227       ExtendableEdgeSetExtender<
00228       MappableEdgeSetExtender<
00229       IterableGraphExtender<
00230       AlterableEdgeSetExtender<
00231       GraphExtender<
00232       ListEdgeSetBase<_Graph> > > > > > > > Parent;
00233     
00234     typedef typename Parent::Node Node;
00235     typedef typename Parent::Edge Edge;
00236     
00237     typedef _Graph Graph;
00238 
00239 
00240     typedef typename Parent::NodesImplBase NodesImplBase;
00241 
00242     void eraseNode(const Node& node) {
00243       Edge edge;
00244       Parent::firstOut(edge, node);
00245       while (edge != INVALID ) {
00246         erase(edge);
00247         Parent::firstOut(edge, node);
00248       } 
00249 
00250       Parent::firstIn(edge, node);
00251       while (edge != INVALID ) {
00252         erase(edge);
00253         Parent::firstIn(edge, node);
00254       }
00255     }
00256     
00257     void clearNodes() {
00258       Parent::clear();
00259     }
00260 
00261     class NodesImpl : public NodesImplBase {
00262     public:
00263       typedef NodesImplBase Parent;
00264       
00265       NodesImpl(const Graph& graph, ListEdgeSet& edgeset) 
00266         : Parent(graph), _edgeset(edgeset) {}
00267       
00268     protected:
00269 
00270       virtual void erase(const Node& node) {
00271         _edgeset.eraseNode(node);
00272         Parent::erase(node);
00273       }
00274       virtual void clear() {
00275         _edgeset.clearNodes();
00276         Parent::clear();
00277       }
00278 
00279     private:
00280       ListEdgeSet& _edgeset;
00281     };
00282 
00283     NodesImpl nodes;
00284     
00285   public:
00286 
00290     ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
00291       Parent::initalize(graph, nodes);
00292     }
00293     
00294   };
00295 
00311   template <typename _Graph>
00312   class ListUEdgeSet :
00313     public ErasableUEdgeSetExtender<
00314     ClearableUEdgeSetExtender<
00315     ExtendableUEdgeSetExtender<
00316     MappableUEdgeSetExtender<
00317     IterableUGraphExtender<
00318     AlterableUEdgeSetExtender<
00319     UGraphExtender<
00320     ListEdgeSetBase<_Graph> > > > > > > > {
00321 
00322   public:
00323 
00324     typedef ErasableUEdgeSetExtender<
00325       ClearableUEdgeSetExtender<
00326       ExtendableUEdgeSetExtender<
00327       MappableUEdgeSetExtender<
00328       IterableUGraphExtender<
00329       AlterableUEdgeSetExtender<
00330       UGraphExtender<
00331       ListEdgeSetBase<_Graph> > > > > > > > Parent;
00332     
00333     typedef typename Parent::Node Node;
00334     typedef typename Parent::Edge Edge;
00335     
00336     typedef _Graph Graph;
00337 
00338 
00339     typedef typename Parent::NodesImplBase NodesImplBase;
00340 
00341     void eraseNode(const Node& node) {
00342       Edge edge;
00343       Parent::firstOut(edge, node);
00344       while (edge != INVALID ) {
00345         erase(edge);
00346         Parent::firstOut(edge, node);
00347       } 
00348 
00349     }
00350     
00351     void clearNodes() {
00352       Parent::clear();
00353     }
00354 
00355     class NodesImpl : public NodesImplBase {
00356     public:
00357       typedef NodesImplBase Parent;
00358       
00359       NodesImpl(const Graph& graph, ListUEdgeSet& edgeset) 
00360         : Parent(graph), _edgeset(edgeset) {}
00361       
00362     protected:
00363 
00364       virtual void erase(const Node& node) {
00365         _edgeset.eraseNode(node);
00366         Parent::erase(node);
00367       }
00368       virtual void erase(const std::vector<Node>& nodes) {
00369         for (int i = 0; i < nodes.size(); ++i) {
00370           _edgeset.eraseNode(nodes[i]);
00371         }
00372         Parent::erase(nodes);
00373       }
00374       virtual void clear() {
00375         _edgeset.clearNodes();
00376         Parent::clear();
00377       }
00378 
00379     private:
00380       ListUEdgeSet& _edgeset;
00381     };
00382 
00383     NodesImpl nodes;
00384     
00385   public:
00386 
00390     ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
00391       Parent::initalize(graph, nodes);
00392     }
00393     
00394   };
00395 
00396 }
00397 
00398 #endif

Generated on Fri Feb 3 18:36:41 2006 for LEMON by  doxygen 1.4.6