time_measure.h went to src/include.
2 #ifndef HUGO_LIST_GRAPH_H
3 #define HUGO_LIST_GRAPH_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 ListGraph& _G) : G(_G), container(G.node_id) { }
44 NodeMap(const ListGraph& _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 ListGraph& _G) : G(_G), container(G.edge_id) { }
65 EdgeMap(const ListGraph& _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;
88 friend class ListGraph;
89 template <typename T> friend class NodeMap;
95 friend class OutEdgeIt;
96 friend class InEdgeIt;
97 friend class SymEdgeIt;
98 friend std::ostream& operator<<(std::ostream& os, const Node& i);
99 friend std::ostream& operator<<(std::ostream& os, const Edge& i);
102 edge_item* _first_out_edge;
103 edge_item* _last_out_edge;
104 edge_item* _first_in_edge;
105 edge_item* _last_in_edge;
106 node_item* _next_node;
107 node_item* _prev_node;
113 friend class ListGraph;
114 template <typename T> friend class EdgeMap;
120 friend class OutEdgeIt;
121 friend class InEdgeIt;
122 friend class SymEdgeIt;
123 friend std::ostream& operator<<(std::ostream& os, const Edge& i);
128 edge_item* _next_out;
129 edge_item* _prev_out;
136 node_item* _add_node() {
137 node_item* p=new node_item;
139 p->_first_out_edge=0;
143 p->_prev_node=_last_node;
145 if (_last_node) _last_node->_next_node=p;
147 if (!_first_node) _first_node=p;
153 edge_item* _add_edge(node_item* _tail, node_item* _head) {
154 edge_item* e=new edge_item;
159 e->_prev_out=_tail->_last_out_edge;
160 if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
161 _tail->_last_out_edge=e;
162 if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
165 e->_prev_in=_head->_last_in_edge;
166 if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
167 _head->_last_in_edge=e;
168 if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
175 //deletes a node which has no out edge and no in edge
176 void _delete_node(node_item* v) {
177 if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else
178 _last_node=v->_prev_node;
179 if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else
180 _first_node=v->_next_node;
186 void _delete_edge(edge_item* e) {
187 if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
188 (e->_tail)->_last_out_edge=e->_prev_out;
189 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
190 (e->_tail)->_first_out_edge=e->_next_out;
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;
200 void _set_tail(edge_item* e, node_item* _tail) {
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;
208 e->_prev_out=_tail->_last_out_edge;
209 if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
210 _tail->_last_out_edge=e;
211 if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
215 void _set_head(edge_item* e, node_item* _head) {
216 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
217 (e->_head)->_last_in_edge=e->_prev_in;
218 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
219 (e->_head)->_first_in_edge=e->_next_in;
223 e->_prev_in=_head->_last_in_edge;
224 if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
225 _head->_last_in_edge=e;
226 if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
232 /* default constructor */
234 ListGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
238 while (this->valid(first(n))) erase(n);
239 //while (first<NodeIt>().valid()) erase(first<NodeIt>());
242 int nodeNum() const { return _node_num; }
243 int edgeNum() const { return _edge_num; }
245 /* functions to construct iterators from the graph, or from each other */
247 //NodeIt firstNode() const { return NodeIt(*this); }
248 //EdgeIt firstEdge() const { return EdgeIt(*this); }
250 //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); }
251 //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); }
252 //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); }
253 Node tail(Edge e) const { return e.tailNode(); }
254 Node head(Edge e) const { return e.headNode(); }
256 Node aNode(const OutEdgeIt& e) const { return e.aNode(); }
257 Node aNode(const InEdgeIt& e) const { return e.aNode(); }
258 Node aNode(const SymEdgeIt& e) const { return e.aNode(); }
260 Node bNode(const OutEdgeIt& e) const { return e.bNode(); }
261 Node bNode(const InEdgeIt& e) const { return e.bNode(); }
262 Node bNode(const SymEdgeIt& e) const { return e.bNode(); }
264 //Node invalid_node() { return Node(); }
265 //Edge invalid_edge() { return Edge(); }
266 //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); }
267 //InEdgeIt invalid_in_edge() { return InEdgeIt(); }
268 //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); }
270 /* same methods in other style */
271 /* for experimental purpose */
273 NodeIt& first(NodeIt& v) const {
274 v=NodeIt(*this); return v; }
275 EdgeIt& first(EdgeIt& e) const {
276 e=EdgeIt(*this); return e; }
277 OutEdgeIt& first(OutEdgeIt& e, Node v) const {
278 e=OutEdgeIt(*this, v); return e; }
279 InEdgeIt& first(InEdgeIt& e, Node v) const {
280 e=InEdgeIt(*this, v); return e; }
281 SymEdgeIt& first(SymEdgeIt& e, Node v) const {
282 e=SymEdgeIt(*this, v); return e; }
283 //void getTail(Node& n, const Edge& e) const { n=tail(e); }
284 //void getHead(Node& n, const Edge& e) const { n=head(e); }
286 //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); }
287 //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); }
288 //void getANode(Node& n, const SymEdgeIt& e) const { n=e.aNode(); }
289 //void getBNode(Node& n, const OutEdgeIt& e) const { n=e.bNode(); }
290 //void getBNode(Node& n, const InEdgeIt& e) const { n=e.bNode(); }
291 //void getBNode(Node& n, const SymEdgeIt& e) const { n=e.bNode(); }
292 //void get_invalid(Node& n) { n=Node(); }
293 //void get_invalid(Edge& e) { e=Edge(); }
294 //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }
295 //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }
296 //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
298 // template< typename It >
299 // It first() const {
305 // template< typename It >
306 // It first(Node v) const {
312 bool valid(Node n) const { return n.valid(); }
313 bool valid(Edge e) const { return e.valid(); }
315 // template <typename It> It getNext(It it) const {
316 // It tmp(it); next(tmp); return tmp; }
317 // NodeIt& next(NodeIt& it) const { return ++it; }
318 // EdgeIt& next(EdgeIt& it) const { return ++it; }
319 // OutEdgeIt& next(OutEdgeIt& it) const { return ++it; }
320 // InEdgeIt& next(InEdgeIt& it) const { return ++it; }
321 // SymEdgeIt& next(SymEdgeIt& it) const { return ++it; }
322 // template <typename It> It& next(It& it) const { return ++it; }
323 template <typename It> It& next(It& it) const { ++it; return it; }
326 /* for getting id's of graph objects */
327 /* these are important for the implementation of property vectors */
329 int id(Node v) const { return v.node->id; }
330 int id(Edge e) const { return e.edge->id; }
332 /* adding nodes and edges */
334 Node addNode() { return Node(_add_node()); }
335 Edge addEdge(Node u, Node v) {
336 return Edge(_add_edge(u.node, v.node));
342 while (this->valid(first(e, i))) erase(e);
346 while (this->valid(first(e, i))) erase(e);
348 //while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
349 //while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
350 _delete_node(i.node);
353 void erase(Edge e) { _delete_edge(e.edge); }
357 while (this->valid(first(e))) erase(e);
358 //while (first<NodeIt>().valid()) erase(first<NodeIt>());
361 void setTail(Edge e, Node tail) {
362 _set_tail(e.edge, tail.node);
365 void setHead(Edge e, Node head) {
366 _set_head(e.edge, head.node);
369 /* stream operations, for testing purpose */
371 friend std::ostream& operator<<(std::ostream& os, const Node& i) {
378 friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
380 os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
387 friend class ListGraph;
388 template <typename T> friend class NodeMap;
391 friend class OutEdgeIt;
392 friend class InEdgeIt;
393 friend class SymEdgeIt;
394 //public: //FIXME: It is required by op= of NodeIt
398 friend int ListGraph::id(Node v) const;
400 Node() /*: node(0)*/ { }
401 Node(const Invalid&) : node(0) { }
403 Node(node_item* _node) : node(_node) { }
404 bool valid() const { return (node); }
406 //void makeInvalid() { node=0; }
407 friend bool operator==(Node u, Node v) { return v.node==u.node; }
408 friend bool operator!=(Node u, Node v) { return v.node!=u.node; }
409 friend std::ostream& operator<<(std::ostream& os, const Node& i);
412 class NodeIt : public Node {
413 friend class ListGraph;
415 public: //for everybody but marci
416 NodeIt(const ListGraph& G) : Node(G._first_node) { }
418 NodeIt() : Node() { }
419 NodeIt(const Invalid& i) : Node(i) { }
421 NodeIt(node_item* v) : Node(v) { }
422 NodeIt& operator++() { node=node->_next_node; return *this; }
424 // NodeIt& operator=(const Node& e)
425 // { node=e.node; return *this; }
429 friend class ListGraph;
430 template <typename T> friend class EdgeMap;
436 friend int ListGraph::id(Edge e) const;
438 Edge() /*: edge(0)*/ { }
439 Edge(const Invalid&) : edge(0) { }
442 Edge(edge_item* _edge) : edge(_edge) { }
443 bool valid() const { return (edge); }
445 //void makeInvalid() { edge=0; }
446 friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; }
447 friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; }
449 Node tailNode() const { return Node(edge->_tail); }
450 Node headNode() const { return Node(edge->_head); }
452 friend std::ostream& operator<<(std::ostream& os, const Edge& i);
455 class EdgeIt : public Edge {
456 friend class ListGraph;
459 EdgeIt(const ListGraph& G) {
460 node_item* v=G._first_node;
461 if (v) edge=v->_first_out_edge; else edge=0;
462 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
465 EdgeIt() : Edge() { }
466 EdgeIt(const Invalid& i) : Edge(i) { }
468 EdgeIt(edge_item* _e) : Edge(_e) { }
469 EdgeIt& operator++() {
470 node_item* v=edge->_tail;
471 edge=edge->_next_out;
472 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
477 class OutEdgeIt : public Edge {
478 friend class ListGraph;
481 protected: //for alpar
482 OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
484 OutEdgeIt() : Edge()/*, v(0)*/ { }
485 OutEdgeIt(const Invalid& i) : Edge(i) { }
486 OutEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
488 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
490 Node aNode() const { return Node(edge->_tail); }
491 Node bNode() const { return Node(edge->_head); }
494 class InEdgeIt : public Edge {
495 friend class ListGraph;
498 protected: //for alpar
499 InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
501 InEdgeIt() : Edge()/*, v(0)*/ { }
502 InEdgeIt(const Invalid& i) : Edge(i) { }
503 InEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
505 InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
507 Node aNode() const { return Node(edge->_head); }
508 Node bNode() const { return Node(edge->_tail); }
511 class SymEdgeIt : public Edge {
512 friend class ListGraph;
513 bool out_or_in; //1 iff out, 0 iff in
516 protected: //for alpar
517 SymEdgeIt(const Node& _v) /*: v(_v.node)*/ {
519 edge=_v.node->_first_out_edge;
520 if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
523 SymEdgeIt() : Edge() /*, v(0)*/ { }
524 SymEdgeIt(const Invalid& i) : Edge(i) { }
525 SymEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ {
527 edge=_v.node->_first_out_edge;
528 if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
531 SymEdgeIt& operator++() {
533 node_item* v=edge->_tail;
534 edge=edge->_next_out;
535 if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
543 return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); }
545 return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); }
549 class UndirListGraph : public ListGraph {
551 typedef SymEdgeIt OutEdgeIt;
552 typedef SymEdgeIt InEdgeIt;
557 #endif //HUGO_LIST_GRAPH_H