Sorry, the other half of the move comes here.
2 #ifndef HUGO_LIST_GRAPH_H
3 #define HUGO_LIST_GRAPH_H
10 #include "vector_map_factory.h"
14 template <typename It>
17 for( ; it.valid(); ++it) { ++i; }
33 // template <typename T> class NodeMap;
34 // template <typename T> class EdgeMap;
36 // template <typename T> friend class NodeMap;
37 // template <typename T> friend class EdgeMap;
44 typedef MapBase<ListGraph, Node, NodeIt> NodeMapBase;
45 typedef MapRegistry<ListGraph, Node, NodeIt> NodeMapRegistry;
46 typedef VectorMapFactory<ListGraph, Node, NodeIt> NodeMapFactory;
47 NodeMapRegistry node_maps;
51 typedef MapBase<ListGraph, Edge, EdgeIt> EdgeMapBase;
52 typedef MapRegistry<ListGraph, Edge, EdgeIt> EdgeMapRegistry;
53 typedef VectorMapFactory<ListGraph, Edge, EdgeIt> EdgeMapFactory;
54 EdgeMapRegistry edge_maps;
62 node_item* _first_node;
63 node_item* _last_node;
66 friend class ListGraph;
67 template <typename T> friend class NodeMap;
73 friend class OutEdgeIt;
74 friend class InEdgeIt;
75 friend class SymEdgeIt;
76 friend std::ostream& operator<<(std::ostream& os, const Node& i);
77 friend std::ostream& operator<<(std::ostream& os, const Edge& i);
80 edge_item* _first_out_edge;
81 edge_item* _last_out_edge;
82 edge_item* _first_in_edge;
83 edge_item* _last_in_edge;
84 node_item* _next_node;
85 node_item* _prev_node;
91 friend class ListGraph;
92 template <typename T> friend class EdgeMap;
98 friend class OutEdgeIt;
99 friend class InEdgeIt;
100 friend class SymEdgeIt;
101 friend std::ostream& operator<<(std::ostream& os, const Edge& i);
106 edge_item* _next_out;
107 edge_item* _prev_out;
114 node_item* _add_node() {
115 node_item* p=new node_item;
117 p->_first_out_edge=0;
121 p->_prev_node=_last_node;
123 if (_last_node) _last_node->_next_node=p;
125 if (!_first_node) _first_node=p;
131 edge_item* _add_edge(node_item* _tail, node_item* _head) {
132 edge_item* e=new edge_item;
137 e->_prev_out=_tail->_last_out_edge;
138 if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
139 _tail->_last_out_edge=e;
140 if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
143 e->_prev_in=_head->_last_in_edge;
144 if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
145 _head->_last_in_edge=e;
146 if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
153 //deletes a node which has no out edge and no in edge
154 void _delete_node(node_item* v) {
155 if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else
156 _last_node=v->_prev_node;
157 if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else
158 _first_node=v->_next_node;
164 void _delete_edge(edge_item* e) {
165 if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
166 (e->_tail)->_last_out_edge=e->_prev_out;
167 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
168 (e->_tail)->_first_out_edge=e->_next_out;
169 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
170 (e->_head)->_last_in_edge=e->_prev_in;
171 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
172 (e->_head)->_first_in_edge=e->_next_in;
178 void _set_tail(edge_item* e, node_item* _tail) {
179 if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
180 (e->_tail)->_last_out_edge=e->_prev_out;
181 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
182 (e->_tail)->_first_out_edge=e->_next_out;
186 e->_prev_out=_tail->_last_out_edge;
187 if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
188 _tail->_last_out_edge=e;
189 if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
193 void _set_head(edge_item* e, node_item* _head) {
194 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
195 (e->_head)->_last_in_edge=e->_prev_in;
196 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
197 (e->_head)->_first_in_edge=e->_next_in;
201 e->_prev_in=_head->_last_in_edge;
202 if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
203 _head->_last_in_edge=e;
204 if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
210 /* default constructor */
212 ListGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0){ }
215 while (first<NodeIt>().valid()) erase(first<NodeIt>());
218 int nodeNum() const { return _node_num; }
219 int edgeNum() const { return _edge_num; }
221 /* functions to construct iterators from the graph, or from each other */
223 //NodeIt firstNode() const { return NodeIt(*this); }
224 //EdgeIt firstEdge() const { return EdgeIt(*this); }
226 //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); }
227 //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); }
228 //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); }
229 Node tail(Edge e) const { return e.tailNode(); }
230 Node head(Edge e) const { return e.headNode(); }
232 Node aNode(const OutEdgeIt& e) const { return e.aNode(); }
233 Node aNode(const InEdgeIt& e) const { return e.aNode(); }
234 Node aNode(const SymEdgeIt& e) const { return e.aNode(); }
236 Node bNode(const OutEdgeIt& e) const { return e.bNode(); }
237 Node bNode(const InEdgeIt& e) const { return e.bNode(); }
238 Node bNode(const SymEdgeIt& e) const { return e.bNode(); }
240 //Node invalid_node() { return Node(); }
241 //Edge invalid_edge() { return Edge(); }
242 //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); }
243 //InEdgeIt invalid_in_edge() { return InEdgeIt(); }
244 //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); }
246 /* same methods in other style */
247 /* for experimental purpose */
249 NodeIt& /*getF*/first(NodeIt& v) const {
250 v=NodeIt(*this); return v; }
251 EdgeIt& /*getF*/first(EdgeIt& e) const {
252 e=EdgeIt(*this); return e; }
253 OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const {
254 e=OutEdgeIt(*this, v); return e; }
255 InEdgeIt& /*getF*/first(InEdgeIt& e, Node v) const {
256 e=InEdgeIt(*this, v); return e; }
257 SymEdgeIt& /*getF*/first(SymEdgeIt& e, Node v) const {
258 e=SymEdgeIt(*this, v); return e; }
259 //void getTail(Node& n, const Edge& e) const { n=tail(e); }
260 //void getHead(Node& n, const Edge& e) const { n=head(e); }
262 //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); }
263 //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); }
264 //void getANode(Node& n, const SymEdgeIt& e) const { n=e.aNode(); }
265 //void getBNode(Node& n, const OutEdgeIt& e) const { n=e.bNode(); }
266 //void getBNode(Node& n, const InEdgeIt& e) const { n=e.bNode(); }
267 //void getBNode(Node& n, const SymEdgeIt& e) const { n=e.bNode(); }
268 //void get_invalid(Node& n) { n=Node(); }
269 //void get_invalid(Edge& e) { e=Edge(); }
270 //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }
271 //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }
272 //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
274 template< typename It >
281 template< typename It >
282 It first(Node v) const {
288 bool valid(Node n) const { return n.valid(); }
289 bool valid(Edge e) const { return e.valid(); }
291 template <typename It> It getNext(It it) const {
292 It tmp(it); return next(tmp); }
293 template <typename It> It& next(It& it) const { return ++it; }
296 /* for getting id's of graph objects */
297 /* these are important for the implementation of property vectors */
299 int id(Node v) const { return v.node->id; }
300 int id(Edge e) const { return e.edge->id; }
302 /* adding nodes and edges */
305 Node n = _add_node();
309 Edge addEdge(Node u, Node v) {
310 Edge e = _add_edge(u.node, v.node);
317 while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
318 while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
319 _delete_node(i.node);
324 _delete_edge(e.edge);
328 while (first<NodeIt>().valid()) erase(first<NodeIt>());
331 void setTail(Edge e, Node tail) {
332 _set_tail(e.edge, tail.node);
335 void setHead(Edge e, Node head) {
336 _set_head(e.edge, head.node);
339 /* stream operations, for testing purpose */
341 friend std::ostream& operator<<(std::ostream& os, const Node& i) {
342 os << i.node->id; return os;
344 friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
345 os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
350 friend class ListGraph;
351 template <typename T> friend class NodeMap;
354 friend class OutEdgeIt;
355 friend class InEdgeIt;
356 friend class SymEdgeIt;
357 //public: //FIXME: It is required by op= of NodeIt
361 friend int ListGraph::id(Node v) const;
363 Node() /*: node(0)*/ { }
364 Node(const Invalid&) : node(0) { }
366 Node(node_item* _node) : node(_node) { }
367 bool valid() const { return (node); }
369 //void makeInvalid() { node=0; }
370 friend bool operator==(Node u, Node v) { return v.node==u.node; }
371 friend bool operator!=(Node u, Node v) { return v.node!=u.node; }
372 friend std::ostream& operator<<(std::ostream& os, const Node& i);
375 class NodeIt : public Node {
376 friend class ListGraph;
378 public: //for everybody but marci
379 NodeIt(const ListGraph& G) : Node(G._first_node) { }
381 NodeIt() : Node() { }
382 NodeIt(const Invalid& i) : Node(i) { }
384 NodeIt(node_item* v) : Node(v) { }
385 NodeIt& operator++() { node=node->_next_node; return *this; }
387 // NodeIt& operator=(const Node& e)
388 // { node=e.node; return *this; }
392 friend class ListGraph;
393 template <typename T> friend class EdgeMap;
399 friend int ListGraph::id(Edge e) const;
401 Edge() /*: edge(0)*/ { }
402 Edge(const Invalid&) : edge(0) { }
405 Edge(edge_item* _edge) : edge(_edge) { }
406 bool valid() const { return (edge); }
408 //void makeInvalid() { edge=0; }
409 friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; }
410 friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; }
412 Node tailNode() const { return Node(edge->_tail); }
413 Node headNode() const { return Node(edge->_head); }
415 friend std::ostream& operator<<(std::ostream& os, const Edge& i);
418 class EdgeIt : public Edge {
419 friend class ListGraph;
422 EdgeIt(const ListGraph& G) {
423 node_item* v=G._first_node;
424 if (v) edge=v->_first_out_edge; else edge=0;
425 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
428 EdgeIt() : Edge() { }
429 EdgeIt(const Invalid& i) : Edge(i) { }
431 EdgeIt(edge_item* _e) : Edge(_e) { }
432 EdgeIt& operator++() {
433 node_item* v=edge->_tail;
434 edge=edge->_next_out;
435 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
440 class OutEdgeIt : public Edge {
441 friend class ListGraph;
444 protected: //for alpar
445 OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
447 OutEdgeIt() : Edge()/*, v(0)*/ { }
448 OutEdgeIt(const Invalid& i) : Edge(i) { }
449 OutEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
451 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
453 Node aNode() const { return Node(edge->_tail); }
454 Node bNode() const { return Node(edge->_head); }
457 class InEdgeIt : public Edge {
458 friend class ListGraph;
461 protected: //for alpar
462 InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
464 InEdgeIt() : Edge()/*, v(0)*/ { }
465 InEdgeIt(const Invalid& i) : Edge(i) { }
466 InEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
468 InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
470 Node aNode() const { return Node(edge->_head); }
471 Node bNode() const { return Node(edge->_tail); }
474 class SymEdgeIt : public Edge {
475 friend class ListGraph;
476 bool out_or_in; //1 iff out, 0 iff in
480 SymEdgeIt(const Node& _v) /*: v(_v.node)*/ {
482 edge=_v.node->_first_out_edge;
483 if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
486 SymEdgeIt() : Edge() /*, v(0)*/ { }
487 SymEdgeIt(const Invalid& i) : Edge(i) { }
488 SymEdgeIt(const ListGraph&, 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& operator++() {
496 node_item* v=edge->_tail;
497 edge=edge->_next_out;
498 if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
506 return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); }
508 return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); }
513 // template< typename T >
514 // T ListGraph::first() const {
515 // std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>();" << std::endl;
520 // ListGraph::NodeIt ListGraph::first<ListGraph::NodeIt>() const {
521 // return firstNode();
525 // ListGraph::EdgeIt ListGraph::first<ListGraph::EdgeIt>() const {
526 // return firstEdge();
529 // template< typename T >
530 // T ListGraph::first(ListGraph::Node v) const {
531 // std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>(ListGRaph::Node);" << std::endl;
536 // ListGraph::OutEdgeIt ListGraph::first<ListGraph::OutEdgeIt>(const ListGraph::Node v) const {
537 // return firstOutEdge(v);
541 // ListGraph::InEdgeIt ListGraph::first<ListGraph::InEdgeIt>(const ListGraph::Node v) const {
542 // return firstInEdge(v);
546 // ListGraph::SymEdgeIt ListGraph::first<ListGraph::SymEdgeIt>(const ListGraph::Node v) const {
547 // return firstSymEdge(v);
553 #endif //HUGO_LIST_GRAPH_H