Doxygen options changed.
\author's added.
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;
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* _tail, node_item* _head) {
125 edge_item* e=new edge_item;
130 e->_prev_out=_tail->_last_out_edge;
131 if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
132 _tail->_last_out_edge=e;
133 if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
136 e->_prev_in=_head->_last_in_edge;
137 if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
138 _head->_last_in_edge=e;
139 if (!_head->_first_in_edge) { _head->_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->_tail)->_last_out_edge=e->_prev_out;
160 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
161 (e->_tail)->_first_out_edge=e->_next_out;
162 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
163 (e->_head)->_last_in_edge=e->_prev_in;
164 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
165 (e->_head)->_first_in_edge=e->_next_in;
171 void _set_tail(edge_item* e, node_item* _tail) {
172 if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
173 (e->_tail)->_last_out_edge=e->_prev_out;
174 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
175 (e->_tail)->_first_out_edge=e->_next_out;
179 e->_prev_out=_tail->_last_out_edge;
180 if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
181 _tail->_last_out_edge=e;
182 if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
186 void _set_head(edge_item* e, node_item* _head) {
187 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
188 (e->_head)->_last_in_edge=e->_prev_in;
189 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
190 (e->_head)->_first_in_edge=e->_next_in;
194 e->_prev_in=_head->_last_in_edge;
195 if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
196 _head->_last_in_edge=e;
197 if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
203 /* default constructor */
205 ListGraph() : 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 tail(Edge e) const { return e.tailNode(); }
225 Node head(Edge e) const { return e.headNode(); }
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 getTail(Node& n, const Edge& e) const { n=tail(e); }
255 //void getHead(Node& n, const Edge& e) const { n=head(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 setTail(Edge e, Node tail) {
333 _set_tail(e.edge, tail.node);
336 void setHead(Edge e, Node head) {
337 _set_head(e.edge, head.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->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
358 friend class ListGraph;
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 ListGraph::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 ListGraph;
386 public: //for everybody but marci
387 NodeIt(const ListGraph& G) : Node(G._first_node) { }
389 NodeIt() : Node() { }
390 NodeIt(const Invalid& i) : Node(i) { }
392 NodeIt(node_item* v) : Node(v) { }
393 NodeIt& operator++() { node=node->_next_node; return *this; }
395 // NodeIt& operator=(const Node& e)
396 // { node=e.node; return *this; }
400 friend class ListGraph;
401 template <typename T> friend class EdgeMap;
407 friend int ListGraph::id(Edge e) const;
409 Edge() /*: edge(0)*/ { }
410 Edge(const Invalid&) : edge(0) { }
413 Edge(edge_item* _edge) : edge(_edge) { }
414 bool valid() const { return (edge); }
416 //void makeInvalid() { edge=0; }
417 friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; }
418 friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; }
420 Node tailNode() const { return Node(edge->_tail); }
421 Node headNode() const { return Node(edge->_head); }
423 friend std::ostream& operator<<(std::ostream& os, const Edge& i);
426 class EdgeIt : public Edge {
427 friend class ListGraph;
430 EdgeIt(const ListGraph& G) {
431 node_item* v=G._first_node;
432 if (v) edge=v->_first_out_edge; else edge=0;
433 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
436 EdgeIt() : Edge() { }
437 EdgeIt(const Invalid& i) : Edge(i) { }
439 EdgeIt(edge_item* _e) : Edge(_e) { }
440 EdgeIt& operator++() {
441 node_item* v=edge->_tail;
442 edge=edge->_next_out;
443 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
448 class OutEdgeIt : public Edge {
449 friend class ListGraph;
452 protected: //for alpar
453 OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
455 OutEdgeIt() : Edge()/*, v(0)*/ { }
456 OutEdgeIt(const Invalid& i) : Edge(i) { }
457 OutEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
459 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
461 Node aNode() const { return Node(edge->_tail); }
462 Node bNode() const { return Node(edge->_head); }
465 class InEdgeIt : public Edge {
466 friend class ListGraph;
469 protected: //for alpar
470 InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
472 InEdgeIt() : Edge()/*, v(0)*/ { }
473 InEdgeIt(const Invalid& i) : Edge(i) { }
474 InEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
476 InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
478 Node aNode() const { return Node(edge->_head); }
479 Node bNode() const { return Node(edge->_tail); }
482 class SymEdgeIt : public Edge {
483 friend class ListGraph;
484 bool out_or_in; //1 iff out, 0 iff in
487 protected: //for alpar
488 SymEdgeIt(const Node& _v) /*: v(_v.node)*/ {
490 edge=_v.node->_first_out_edge;
491 if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
494 SymEdgeIt() : Edge() /*, v(0)*/ { }
495 SymEdgeIt(const Invalid& i) : Edge(i) { }
496 SymEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ {
498 edge=_v.node->_first_out_edge;
499 if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
502 SymEdgeIt& operator++() {
504 node_item* v=edge->_tail;
505 edge=edge->_next_out;
506 if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
514 return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); }
516 return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); }
521 std::ostream& operator<<(std::ostream& os, const ListGraph::Node& i) {
530 std::ostream& operator<<(std::ostream& os, const ListGraph::Edge& i) {
532 os << "(" << i.tailNode() << "--" << i.edge->id << "->"
533 << i.headNode() << ")";
539 class UndirListGraph : public ListGraph {
541 typedef SymEdgeIt OutEdgeIt;
542 typedef SymEdgeIt InEdgeIt;
547 #endif //HUGO_LIST_GRAPH_H