Concept modification to resolve the item by its ID.
2 #ifndef LEMON_SAGE_GRAPH_H
3 #define LEMON_SAGE_GRAPH_H
8 #include <lemon/invalid.h>
12 // template <typename It>
15 // for( ; it.valid(); ++it) { ++i; }
30 template <typename T> class NodeMap;
31 template <typename T> class EdgeMap;
33 template <typename T> friend class NodeMap;
34 template <typename T> friend class EdgeMap;
39 std::vector<T> container;
43 NodeMap(const SageGraph& _G) : G(_G), container(G.node_id) { }
44 NodeMap(const SageGraph& _G, T a) :
45 G(_G), container(G.node_id, a) { }
46 void set(Node n, T a) { container[/*G.id(n)*/n.node->id]=a; }
47 // T get(Node n) const { return container[/*G.id(n)*/n.node->id]; }
48 typename std::vector<T>::reference operator[](Node n) {
49 return container[/*G.id(n)*/n.node->id]; }
50 typename std::vector<T>::const_reference operator[](Node n) const {
51 return container[/*G.id(n)*/n.node->id];
53 void update() { container.resize(G.node_id); }
54 void update(T a) { container.resize(G.node_id, a); }
60 std::vector<T> container;
64 EdgeMap(const SageGraph& _G) : G(_G), container(G.edge_id) { }
65 EdgeMap(const SageGraph& _G, T a) :
66 G(_G), container(G.edge_id, a) { }
67 void set(Edge e, T a) { container[/*G.id(e)*/e.edge->id]=a; }
68 // T get(Edge e) const { return container[/*G.id(e)*/e.edge->id]; }
69 typename std::vector<T>::reference operator[](Edge e) {
70 return container[/*G.id(e)*/e.edge->id]; }
71 typename std::vector<T>::const_reference operator[](Edge e) const {
72 return container[/*G.id(e)*/e.edge->id];
74 void update() { container.resize(G.edge_id); }
75 void update(T a) { container.resize(G.edge_id, a); }
84 node_item* _first_node;
85 node_item* _last_node;
89 edge_item* _first_out_edge;
90 edge_item* _last_out_edge;
91 edge_item* _first_in_edge;
92 edge_item* _last_in_edge;
93 node_item* _next_node;
94 node_item* _prev_node;
101 edge_item* _next_out;
102 edge_item* _prev_out;
107 node_item* _add_node() {
108 node_item* p=new node_item;
110 p->_first_out_edge=0;
114 p->_prev_node=_last_node;
116 if (_last_node) _last_node->_next_node=p;
118 if (!_first_node) _first_node=p;
124 edge_item* _add_edge(node_item* _source, node_item* _target) {
125 edge_item* e=new edge_item;
130 e->_prev_out=_source->_last_out_edge;
131 if (_source->_last_out_edge) (_source->_last_out_edge)->_next_out=e;
132 _source->_last_out_edge=e;
133 if (!_source->_first_out_edge) _source->_first_out_edge=e;
136 e->_prev_in=_target->_last_in_edge;
137 if (_target->_last_in_edge) (_target->_last_in_edge)->_next_in=e;
138 _target->_last_in_edge=e;
139 if (!_target->_first_in_edge) { _target->_first_in_edge=e; }
146 //deletes a node which has no out edge and no in edge
147 void _delete_node(node_item* v) {
148 if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else
149 _last_node=v->_prev_node;
150 if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else
151 _first_node=v->_next_node;
157 void _delete_edge(edge_item* e) {
158 if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
159 (e->_source)->_last_out_edge=e->_prev_out;
160 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
161 (e->_source)->_first_out_edge=e->_next_out;
162 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
163 (e->_target)->_last_in_edge=e->_prev_in;
164 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
165 (e->_target)->_first_in_edge=e->_next_in;
171 void _set_source(edge_item* e, node_item* _source) {
172 if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
173 (e->_source)->_last_out_edge=e->_prev_out;
174 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
175 (e->_source)->_first_out_edge=e->_next_out;
179 e->_prev_out=_source->_last_out_edge;
180 if (_source->_last_out_edge) (_source->_last_out_edge)->_next_out=e;
181 _source->_last_out_edge=e;
182 if (!_source->_first_out_edge) _source->_first_out_edge=e;
186 void _set_target(edge_item* e, node_item* _target) {
187 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
188 (e->_target)->_last_in_edge=e->_prev_in;
189 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
190 (e->_target)->_first_in_edge=e->_next_in;
194 e->_prev_in=_target->_last_in_edge;
195 if (_target->_last_in_edge) (_target->_last_in_edge)->_next_in=e;
196 _target->_last_in_edge=e;
197 if (!_target->_first_in_edge) { _target->_first_in_edge=e; }
203 /* default constructor */
205 SageGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
209 while (this->valid(first(n))) erase(n);
210 //while (first<NodeIt>().valid()) erase(first<NodeIt>());
213 int nodeNum() const { return _node_num; }
214 int edgeNum() const { return _edge_num; }
216 /* functions to construct iterators from the graph, or from each other */
218 //NodeIt firstNode() const { return NodeIt(*this); }
219 //EdgeIt firstEdge() const { return EdgeIt(*this); }
221 //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); }
222 //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); }
223 //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); }
224 Node source(Edge e) const { return e.sourceNode(); }
225 Node target(Edge e) const { return e.targetNode(); }
227 Node aNode(const OutEdgeIt& e) const { return e.aNode(); }
228 Node aNode(const InEdgeIt& e) const { return e.aNode(); }
229 Node aNode(const SymEdgeIt& e) const { return e.aNode(); }
231 Node bNode(const OutEdgeIt& e) const { return e.bNode(); }
232 Node bNode(const InEdgeIt& e) const { return e.bNode(); }
233 Node bNode(const SymEdgeIt& e) const { return e.bNode(); }
235 //Node invalid_node() { return Node(); }
236 //Edge invalid_edge() { return Edge(); }
237 //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); }
238 //InEdgeIt invalid_in_edge() { return InEdgeIt(); }
239 //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); }
241 /* same methods in other style */
242 /* for experimental purpose */
244 NodeIt& first(NodeIt& v) const {
245 v=NodeIt(*this); return v; }
246 EdgeIt& first(EdgeIt& e) const {
247 e=EdgeIt(*this); return e; }
248 OutEdgeIt& first(OutEdgeIt& e, Node v) const {
249 e=OutEdgeIt(*this, v); return e; }
250 InEdgeIt& first(InEdgeIt& e, Node v) const {
251 e=InEdgeIt(*this, v); return e; }
252 SymEdgeIt& first(SymEdgeIt& e, Node v) const {
253 e=SymEdgeIt(*this, v); return e; }
254 //void getSource(Node& n, const Edge& e) const { n=source(e); }
255 //void getTarget(Node& n, const Edge& e) const { n=target(e); }
257 //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); }
258 //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); }
259 //void getANode(Node& n, const SymEdgeIt& e) const { n=e.aNode(); }
260 //void getBNode(Node& n, const OutEdgeIt& e) const { n=e.bNode(); }
261 //void getBNode(Node& n, const InEdgeIt& e) const { n=e.bNode(); }
262 //void getBNode(Node& n, const SymEdgeIt& e) const { n=e.bNode(); }
263 //void get_invalid(Node& n) { n=Node(); }
264 //void get_invalid(Edge& e) { e=Edge(); }
265 //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }
266 //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }
267 //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
269 // template< typename It >
270 // It first() const {
276 // template< typename It >
277 // It first(Node v) const {
283 bool valid(Node n) const { return n.valid(); }
284 bool valid(Edge e) const { return e.valid(); }
286 // template <typename It> It getNext(It it) const {
287 // It tmp(it); next(tmp); return tmp; }
288 // NodeIt& next(NodeIt& it) const { return ++it; }
289 // EdgeIt& next(EdgeIt& it) const { return ++it; }
290 // OutEdgeIt& next(OutEdgeIt& it) const { return ++it; }
291 // InEdgeIt& next(InEdgeIt& it) const { return ++it; }
292 // SymEdgeIt& next(SymEdgeIt& it) const { return ++it; }
293 // template <typename It> It& next(It& it) const { return ++it; }
294 template <typename It> It& next(It& it) const { ++it; return it; }
297 /* for getting id's of graph objects */
298 /* these are important for the implementation of property vectors */
300 int id(Node v) const { return v.node->id; }
301 int id(Edge e) const { return e.edge->id; }
303 /* adding nodes and edges */
305 Node addNode() { return Node(_add_node()); }
306 Edge addEdge(Node u, Node v) {
307 return Edge(_add_edge(u.node, v.node));
313 while (this->valid(first(e, i))) erase(e);
317 while (this->valid(first(e, i))) erase(e);
319 //while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
320 //while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
321 _delete_node(i.node);
324 void erase(Edge e) { _delete_edge(e.edge); }
328 while (this->valid(first(e))) erase(e);
329 //while (first<NodeIt>().valid()) erase(first<NodeIt>());
332 void setSource(Edge e, Node source) {
333 _set_source(e.edge, source.node);
336 void setTarget(Edge e, Node target) {
337 _set_target(e.edge, target.node);
340 /* stream operations, for testing purpose */
342 // friend std::ostream& operator<<(std::ostream& os, const Node& i) {
349 // friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
351 // os << "(" << i.edge->_source->id << "--" << i.edge->id << "->" << i.edge->_target->id << ")";
358 friend class SageGraph;
359 template <typename T> friend class NodeMap;
362 friend class OutEdgeIt;
363 friend class InEdgeIt;
364 friend class SymEdgeIt;
365 //public: //FIXME: It is required by op= of NodeIt
369 friend int SageGraph::id(Node v) const;
371 Node() /*: node(0)*/ { }
372 Node(const Invalid&) : node(0) { }
374 Node(node_item* _node) : node(_node) { }
375 bool valid() const { return (node); }
377 //void makeInvalid() { node=0; }
378 friend bool operator==(Node u, Node v) { return v.node==u.node; }
379 friend bool operator!=(Node u, Node v) { return v.node!=u.node; }
380 friend std::ostream& operator<<(std::ostream& os, const Node& i);
383 class NodeIt : public Node {
384 friend class SageGraph;
386 public: //for everybody but marci
387 NodeIt(const SageGraph& G) : Node(G._first_node) { }
388 NodeIt(const SageGraph& G, const Node& n) : Node(n) { }
390 NodeIt() : Node() { }
391 NodeIt(const Invalid& i) : Node(i) { }
393 NodeIt(node_item* v) : Node(v) { }
395 NodeIt& operator++() { node=node->_next_node; return *this; }
397 // NodeIt& operator=(const Node& e)
398 // { node=e.node; return *this; }
402 friend class SageGraph;
403 template <typename T> friend class EdgeMap;
409 friend int SageGraph::id(Edge e) const;
411 Edge() /*: edge(0)*/ { }
412 Edge(const Invalid&) : edge(0) { }
415 Edge(edge_item* _edge) : edge(_edge) { }
416 bool valid() const { return (edge); }
418 //void makeInvalid() { edge=0; }
419 friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; }
420 friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; }
422 Node sourceNode() const { return Node(edge->_source); }
423 Node targetNode() const { return Node(edge->_target); }
425 friend std::ostream& operator<<(std::ostream& os, const Edge& i);
428 class EdgeIt : public Edge {
429 friend class SageGraph;
431 EdgeIt() : Edge() { }
432 EdgeIt(const Invalid& i) : Edge(i) { }
433 EdgeIt(const SageGraph& G) {
434 node_item* v=G._first_node;
435 if (v) edge=v->_first_out_edge; else edge=0;
436 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
438 EdgeIt(const SageGraph& G, const Edge& e) : Edge(e) { }
440 // EdgeIt(edge_item* _e) : Edge(_e) { }
442 EdgeIt& operator++() {
443 node_item* v=edge->_source;
444 edge=edge->_next_out;
445 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
450 class OutEdgeIt : public Edge {
451 friend class SageGraph;
453 OutEdgeIt() : Edge() { }
454 OutEdgeIt(const Invalid& i) : Edge(i) { }
455 OutEdgeIt(const SageGraph&, Node _v) : Edge(_v.node->_first_out_edge) { }
456 OutEdgeIt(const SageGraph&, const Edge& e) : Edge(e) { }
457 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
459 Node aNode() const { return Node(edge->_source); }
460 Node bNode() const { return Node(edge->_target); }
463 class InEdgeIt : public Edge {
464 friend class SageGraph;
466 InEdgeIt() : Edge() { }
467 InEdgeIt(Invalid i) : Edge(i) { }
468 InEdgeIt(const SageGraph&, Node _v) : Edge(_v.node->_first_in_edge) { }
469 InEdgeIt(const SageGraph&, const Edge& e) : Edge(e) { }
470 InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
472 Node aNode() const { return Node(edge->_target); }
473 Node bNode() const { return Node(edge->_source); }
476 class SymEdgeIt : public Edge {
477 friend class SageGraph;
478 bool out_or_in; //1 iff out, 0 iff in
481 protected: //for alpar
482 SymEdgeIt(const Node& _v) /*: v(_v.node)*/ {
484 edge=_v.node->_first_out_edge;
485 if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
488 SymEdgeIt() : Edge() /*, v(0)*/ { }
489 SymEdgeIt(const Invalid& i) : Edge(i) { }
490 SymEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ {
492 edge=_v.node->_first_out_edge;
493 if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
496 SymEdgeIt& operator++() {
498 node_item* v=edge->_source;
499 edge=edge->_next_out;
500 if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
508 return (out_or_in) ? Node(edge->_source) : Node(edge->_target); }
510 return (out_or_in) ? Node(edge->_target) : Node(edge->_source); }
515 std::ostream& operator<<(std::ostream& os, const SageGraph::Node& i) {
524 std::ostream& operator<<(std::ostream& os, const SageGraph::Edge& i) {
526 os << "(" << i.sourceNode() << "--" << i.edge->id << "->"
527 << i.targetNode() << ")";
533 class UndirSageGraph : public SageGraph {
535 typedef SymEdgeIt OutEdgeIt;
536 typedef SymEdgeIt InEdgeIt;
541 #endif //LEMON_SAGE_GRAPH_H