To avoid confusion my old ListGraph is can be used under name SageGraph, work/sage_graph.h contains it.
1.1 --- a/src/work/list_graph.h Fri May 14 18:08:29 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,547 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef HUGO_LIST_GRAPH_H
1.6 -#define HUGO_LIST_GRAPH_H
1.7 -
1.8 -#include <iostream>
1.9 -#include <vector>
1.10 -
1.11 -#include <hugo/invalid.h>
1.12 -
1.13 -namespace hugo {
1.14 -
1.15 - template <typename It>
1.16 - int count(It it) {
1.17 - int i=0;
1.18 - for( ; it.valid(); ++it) { ++i; }
1.19 - return i;
1.20 - }
1.21 -
1.22 - class ListGraph {
1.23 - struct node_item;
1.24 - struct edge_item;
1.25 - public:
1.26 - class Node;
1.27 - class NodeIt;
1.28 - class Edge;
1.29 - class EdgeIt;
1.30 - class OutEdgeIt;
1.31 - class InEdgeIt;
1.32 - class SymEdgeIt;
1.33 - template <typename T> class NodeMap;
1.34 - template <typename T> class EdgeMap;
1.35 -// private:
1.36 - template <typename T> friend class NodeMap;
1.37 - template <typename T> friend class EdgeMap;
1.38 -
1.39 - template <typename T>
1.40 - class NodeMap {
1.41 - const ListGraph& G;
1.42 - std::vector<T> container;
1.43 - public:
1.44 - typedef T ValueType;
1.45 - typedef Node KeyType;
1.46 - NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { }
1.47 - NodeMap(const ListGraph& _G, T a) :
1.48 - G(_G), container(G.node_id, a) { }
1.49 - void set(Node n, T a) { container[/*G.id(n)*/n.node->id]=a; }
1.50 -// T get(Node n) const { return container[/*G.id(n)*/n.node->id]; }
1.51 - typename std::vector<T>::reference operator[](Node n) {
1.52 - return container[/*G.id(n)*/n.node->id]; }
1.53 - typename std::vector<T>::const_reference operator[](Node n) const {
1.54 - return container[/*G.id(n)*/n.node->id];
1.55 - }
1.56 - void update() { container.resize(G.node_id); }
1.57 - void update(T a) { container.resize(G.node_id, a); }
1.58 - };
1.59 -
1.60 - template <typename T>
1.61 - class EdgeMap {
1.62 - const ListGraph& G;
1.63 - std::vector<T> container;
1.64 - public:
1.65 - typedef T ValueType;
1.66 - typedef Edge KeyType;
1.67 - EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { }
1.68 - EdgeMap(const ListGraph& _G, T a) :
1.69 - G(_G), container(G.edge_id, a) { }
1.70 - void set(Edge e, T a) { container[/*G.id(e)*/e.edge->id]=a; }
1.71 -// T get(Edge e) const { return container[/*G.id(e)*/e.edge->id]; }
1.72 - typename std::vector<T>::reference operator[](Edge e) {
1.73 - return container[/*G.id(e)*/e.edge->id]; }
1.74 - typename std::vector<T>::const_reference operator[](Edge e) const {
1.75 - return container[/*G.id(e)*/e.edge->id];
1.76 - }
1.77 - void update() { container.resize(G.edge_id); }
1.78 - void update(T a) { container.resize(G.edge_id, a); }
1.79 - };
1.80 -
1.81 - private:
1.82 - int node_id;
1.83 - int edge_id;
1.84 - int _node_num;
1.85 - int _edge_num;
1.86 -
1.87 - node_item* _first_node;
1.88 - node_item* _last_node;
1.89 -
1.90 - struct node_item {
1.91 - int id;
1.92 - edge_item* _first_out_edge;
1.93 - edge_item* _last_out_edge;
1.94 - edge_item* _first_in_edge;
1.95 - edge_item* _last_in_edge;
1.96 - node_item* _next_node;
1.97 - node_item* _prev_node;
1.98 - };
1.99 -
1.100 - struct edge_item {
1.101 - int id;
1.102 - node_item* _tail;
1.103 - node_item* _head;
1.104 - edge_item* _next_out;
1.105 - edge_item* _prev_out;
1.106 - edge_item* _next_in;
1.107 - edge_item* _prev_in;
1.108 - };
1.109 -
1.110 - node_item* _add_node() {
1.111 - node_item* p=new node_item;
1.112 - p->id=node_id++;
1.113 - p->_first_out_edge=0;
1.114 - p->_last_out_edge=0;
1.115 - p->_first_in_edge=0;
1.116 - p->_last_in_edge=0;
1.117 - p->_prev_node=_last_node;
1.118 - p->_next_node=0;
1.119 - if (_last_node) _last_node->_next_node=p;
1.120 - _last_node=p;
1.121 - if (!_first_node) _first_node=p;
1.122 -
1.123 - ++_node_num;
1.124 - return p;
1.125 - }
1.126 -
1.127 - edge_item* _add_edge(node_item* _tail, node_item* _head) {
1.128 - edge_item* e=new edge_item;
1.129 - e->id=edge_id++;
1.130 - e->_tail=_tail;
1.131 - e->_head=_head;
1.132 -
1.133 - e->_prev_out=_tail->_last_out_edge;
1.134 - if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
1.135 - _tail->_last_out_edge=e;
1.136 - if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
1.137 - e->_next_out=0;
1.138 -
1.139 - e->_prev_in=_head->_last_in_edge;
1.140 - if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
1.141 - _head->_last_in_edge=e;
1.142 - if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
1.143 - e->_next_in=0;
1.144 -
1.145 - ++_edge_num;
1.146 - return e;
1.147 - }
1.148 -
1.149 - //deletes a node which has no out edge and no in edge
1.150 - void _delete_node(node_item* v) {
1.151 - if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else
1.152 - _last_node=v->_prev_node;
1.153 - if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else
1.154 - _first_node=v->_next_node;
1.155 -
1.156 - delete v;
1.157 - --_node_num;
1.158 - }
1.159 -
1.160 - void _delete_edge(edge_item* e) {
1.161 - if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
1.162 - (e->_tail)->_last_out_edge=e->_prev_out;
1.163 - if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
1.164 - (e->_tail)->_first_out_edge=e->_next_out;
1.165 - if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
1.166 - (e->_head)->_last_in_edge=e->_prev_in;
1.167 - if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
1.168 - (e->_head)->_first_in_edge=e->_next_in;
1.169 -
1.170 - delete e;
1.171 - --_edge_num;
1.172 - }
1.173 -
1.174 - void _set_tail(edge_item* e, node_item* _tail) {
1.175 - if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
1.176 - (e->_tail)->_last_out_edge=e->_prev_out;
1.177 - if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
1.178 - (e->_tail)->_first_out_edge=e->_next_out;
1.179 -
1.180 - e->_tail=_tail;
1.181 -
1.182 - e->_prev_out=_tail->_last_out_edge;
1.183 - if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
1.184 - _tail->_last_out_edge=e;
1.185 - if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
1.186 - e->_next_out=0;
1.187 - }
1.188 -
1.189 - void _set_head(edge_item* e, node_item* _head) {
1.190 - if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
1.191 - (e->_head)->_last_in_edge=e->_prev_in;
1.192 - if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
1.193 - (e->_head)->_first_in_edge=e->_next_in;
1.194 -
1.195 - e->_head=_head;
1.196 -
1.197 - e->_prev_in=_head->_last_in_edge;
1.198 - if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
1.199 - _head->_last_in_edge=e;
1.200 - if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
1.201 - e->_next_in=0;
1.202 - }
1.203 -
1.204 - public:
1.205 -
1.206 - /* default constructor */
1.207 -
1.208 - ListGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
1.209 -
1.210 - ~ListGraph() {
1.211 - NodeIt n;
1.212 - while (this->valid(first(n))) erase(n);
1.213 - //while (first<NodeIt>().valid()) erase(first<NodeIt>());
1.214 - }
1.215 -
1.216 - int nodeNum() const { return _node_num; }
1.217 - int edgeNum() const { return _edge_num; }
1.218 -
1.219 - /* functions to construct iterators from the graph, or from each other */
1.220 -
1.221 - //NodeIt firstNode() const { return NodeIt(*this); }
1.222 - //EdgeIt firstEdge() const { return EdgeIt(*this); }
1.223 -
1.224 - //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); }
1.225 - //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); }
1.226 - //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); }
1.227 - Node tail(Edge e) const { return e.tailNode(); }
1.228 - Node head(Edge e) const { return e.headNode(); }
1.229 -
1.230 - Node aNode(const OutEdgeIt& e) const { return e.aNode(); }
1.231 - Node aNode(const InEdgeIt& e) const { return e.aNode(); }
1.232 - Node aNode(const SymEdgeIt& e) const { return e.aNode(); }
1.233 -
1.234 - Node bNode(const OutEdgeIt& e) const { return e.bNode(); }
1.235 - Node bNode(const InEdgeIt& e) const { return e.bNode(); }
1.236 - Node bNode(const SymEdgeIt& e) const { return e.bNode(); }
1.237 -
1.238 - //Node invalid_node() { return Node(); }
1.239 - //Edge invalid_edge() { return Edge(); }
1.240 - //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); }
1.241 - //InEdgeIt invalid_in_edge() { return InEdgeIt(); }
1.242 - //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); }
1.243 -
1.244 - /* same methods in other style */
1.245 - /* for experimental purpose */
1.246 -
1.247 - NodeIt& first(NodeIt& v) const {
1.248 - v=NodeIt(*this); return v; }
1.249 - EdgeIt& first(EdgeIt& e) const {
1.250 - e=EdgeIt(*this); return e; }
1.251 - OutEdgeIt& first(OutEdgeIt& e, Node v) const {
1.252 - e=OutEdgeIt(*this, v); return e; }
1.253 - InEdgeIt& first(InEdgeIt& e, Node v) const {
1.254 - e=InEdgeIt(*this, v); return e; }
1.255 - SymEdgeIt& first(SymEdgeIt& e, Node v) const {
1.256 - e=SymEdgeIt(*this, v); return e; }
1.257 - //void getTail(Node& n, const Edge& e) const { n=tail(e); }
1.258 - //void getHead(Node& n, const Edge& e) const { n=head(e); }
1.259 -
1.260 - //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); }
1.261 - //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); }
1.262 - //void getANode(Node& n, const SymEdgeIt& e) const { n=e.aNode(); }
1.263 - //void getBNode(Node& n, const OutEdgeIt& e) const { n=e.bNode(); }
1.264 - //void getBNode(Node& n, const InEdgeIt& e) const { n=e.bNode(); }
1.265 - //void getBNode(Node& n, const SymEdgeIt& e) const { n=e.bNode(); }
1.266 - //void get_invalid(Node& n) { n=Node(); }
1.267 - //void get_invalid(Edge& e) { e=Edge(); }
1.268 - //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }
1.269 - //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }
1.270 - //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
1.271 -
1.272 -// template< typename It >
1.273 -// It first() const {
1.274 -// It e;
1.275 -// first(e);
1.276 -// return e;
1.277 -// }
1.278 -
1.279 -// template< typename It >
1.280 -// It first(Node v) const {
1.281 -// It e;
1.282 -// first(e, v);
1.283 -// return e;
1.284 -// }
1.285 -
1.286 - bool valid(Node n) const { return n.valid(); }
1.287 - bool valid(Edge e) const { return e.valid(); }
1.288 -
1.289 -// template <typename It> It getNext(It it) const {
1.290 -// It tmp(it); next(tmp); return tmp; }
1.291 -// NodeIt& next(NodeIt& it) const { return ++it; }
1.292 -// EdgeIt& next(EdgeIt& it) const { return ++it; }
1.293 -// OutEdgeIt& next(OutEdgeIt& it) const { return ++it; }
1.294 -// InEdgeIt& next(InEdgeIt& it) const { return ++it; }
1.295 -// SymEdgeIt& next(SymEdgeIt& it) const { return ++it; }
1.296 -// template <typename It> It& next(It& it) const { return ++it; }
1.297 - template <typename It> It& next(It& it) const { ++it; return it; }
1.298 -
1.299 -
1.300 - /* for getting id's of graph objects */
1.301 - /* these are important for the implementation of property vectors */
1.302 -
1.303 - int id(Node v) const { return v.node->id; }
1.304 - int id(Edge e) const { return e.edge->id; }
1.305 -
1.306 - /* adding nodes and edges */
1.307 -
1.308 - Node addNode() { return Node(_add_node()); }
1.309 - Edge addEdge(Node u, Node v) {
1.310 - return Edge(_add_edge(u.node, v.node));
1.311 - }
1.312 -
1.313 - void erase(Node i) {
1.314 - {
1.315 - OutEdgeIt e;
1.316 - while (this->valid(first(e, i))) erase(e);
1.317 - }
1.318 - {
1.319 - InEdgeIt e;
1.320 - while (this->valid(first(e, i))) erase(e);
1.321 - }
1.322 - //while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
1.323 - //while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
1.324 - _delete_node(i.node);
1.325 - }
1.326 -
1.327 - void erase(Edge e) { _delete_edge(e.edge); }
1.328 -
1.329 - void clear() {
1.330 - NodeIt e;
1.331 - while (this->valid(first(e))) erase(e);
1.332 - //while (first<NodeIt>().valid()) erase(first<NodeIt>());
1.333 - }
1.334 -
1.335 - void setTail(Edge e, Node tail) {
1.336 - _set_tail(e.edge, tail.node);
1.337 - }
1.338 -
1.339 - void setHead(Edge e, Node head) {
1.340 - _set_head(e.edge, head.node);
1.341 - }
1.342 -
1.343 - /* stream operations, for testing purpose */
1.344 -
1.345 -// friend std::ostream& operator<<(std::ostream& os, const Node& i) {
1.346 -// if (i.valid())
1.347 -// os << i.node->id;
1.348 -// else
1.349 -// os << "invalid";
1.350 -// return os;
1.351 -// }
1.352 -// friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
1.353 -// if (i.valid())
1.354 -// os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
1.355 -// else
1.356 -// os << "invalid";
1.357 -// return os;
1.358 -// }
1.359 -
1.360 - class Node {
1.361 - friend class ListGraph;
1.362 - template <typename T> friend class NodeMap;
1.363 -
1.364 - friend class Edge;
1.365 - friend class OutEdgeIt;
1.366 - friend class InEdgeIt;
1.367 - friend class SymEdgeIt;
1.368 - //public: //FIXME: It is required by op= of NodeIt
1.369 - protected:
1.370 - node_item* node;
1.371 - protected:
1.372 - friend int ListGraph::id(Node v) const;
1.373 - public:
1.374 - Node() /*: node(0)*/ { }
1.375 - Node(const Invalid&) : node(0) { }
1.376 - protected:
1.377 - Node(node_item* _node) : node(_node) { }
1.378 - bool valid() const { return (node); }
1.379 - public:
1.380 - //void makeInvalid() { node=0; }
1.381 - friend bool operator==(Node u, Node v) { return v.node==u.node; }
1.382 - friend bool operator!=(Node u, Node v) { return v.node!=u.node; }
1.383 - friend std::ostream& operator<<(std::ostream& os, const Node& i);
1.384 - };
1.385 -
1.386 - class NodeIt : public Node {
1.387 - friend class ListGraph;
1.388 - //protected:
1.389 - public: //for everybody but marci
1.390 - NodeIt(const ListGraph& G) : Node(G._first_node) { }
1.391 - public:
1.392 - NodeIt() : Node() { }
1.393 - NodeIt(const Invalid& i) : Node(i) { }
1.394 - protected:
1.395 - NodeIt(node_item* v) : Node(v) { }
1.396 - NodeIt& operator++() { node=node->_next_node; return *this; }
1.397 - //FIXME::
1.398 - // NodeIt& operator=(const Node& e)
1.399 - // { node=e.node; return *this; }
1.400 - };
1.401 -
1.402 - class Edge {
1.403 - friend class ListGraph;
1.404 - template <typename T> friend class EdgeMap;
1.405 -
1.406 - friend class Node;
1.407 - friend class NodeIt;
1.408 - protected:
1.409 - edge_item* edge;
1.410 - friend int ListGraph::id(Edge e) const;
1.411 - public:
1.412 - Edge() /*: edge(0)*/ { }
1.413 - Edge(const Invalid&) : edge(0) { }
1.414 - //Edge() { }
1.415 - protected:
1.416 - Edge(edge_item* _edge) : edge(_edge) { }
1.417 - bool valid() const { return (edge); }
1.418 - public:
1.419 - //void makeInvalid() { edge=0; }
1.420 - friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; }
1.421 - friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; }
1.422 - protected:
1.423 - Node tailNode() const { return Node(edge->_tail); }
1.424 - Node headNode() const { return Node(edge->_head); }
1.425 - public:
1.426 - friend std::ostream& operator<<(std::ostream& os, const Edge& i);
1.427 - };
1.428 -
1.429 - class EdgeIt : public Edge {
1.430 - friend class ListGraph;
1.431 - //protected:
1.432 - public: //for alpar
1.433 - EdgeIt(const ListGraph& G) {
1.434 - node_item* v=G._first_node;
1.435 - if (v) edge=v->_first_out_edge; else edge=0;
1.436 - while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
1.437 - }
1.438 - public:
1.439 - EdgeIt() : Edge() { }
1.440 - EdgeIt(const Invalid& i) : Edge(i) { }
1.441 - protected:
1.442 - EdgeIt(edge_item* _e) : Edge(_e) { }
1.443 - EdgeIt& operator++() {
1.444 - node_item* v=edge->_tail;
1.445 - edge=edge->_next_out;
1.446 - while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
1.447 - return *this;
1.448 - }
1.449 - };
1.450 -
1.451 - class OutEdgeIt : public Edge {
1.452 - friend class ListGraph;
1.453 - //node_item* v;
1.454 - //protected:
1.455 - protected: //for alpar
1.456 - OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
1.457 - public:
1.458 - OutEdgeIt() : Edge()/*, v(0)*/ { }
1.459 - OutEdgeIt(const Invalid& i) : Edge(i) { }
1.460 - OutEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
1.461 - protected:
1.462 - OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
1.463 - protected:
1.464 - Node aNode() const { return Node(edge->_tail); }
1.465 - Node bNode() const { return Node(edge->_head); }
1.466 - };
1.467 -
1.468 - class InEdgeIt : public Edge {
1.469 - friend class ListGraph;
1.470 - //node_item* v;
1.471 - //protected:
1.472 - protected: //for alpar
1.473 - InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
1.474 - public:
1.475 - InEdgeIt() : Edge()/*, v(0)*/ { }
1.476 - InEdgeIt(const Invalid& i) : Edge(i) { }
1.477 - InEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
1.478 - protected:
1.479 - InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
1.480 - protected:
1.481 - Node aNode() const { return Node(edge->_head); }
1.482 - Node bNode() const { return Node(edge->_tail); }
1.483 - };
1.484 -
1.485 - class SymEdgeIt : public Edge {
1.486 - friend class ListGraph;
1.487 - bool out_or_in; //1 iff out, 0 iff in
1.488 - //node_item* v;
1.489 - //protected:
1.490 - protected: //for alpar
1.491 - SymEdgeIt(const Node& _v) /*: v(_v.node)*/ {
1.492 - out_or_in=1;
1.493 - edge=_v.node->_first_out_edge;
1.494 - if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
1.495 - }
1.496 - public:
1.497 - SymEdgeIt() : Edge() /*, v(0)*/ { }
1.498 - SymEdgeIt(const Invalid& i) : Edge(i) { }
1.499 - SymEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ {
1.500 - out_or_in=1;
1.501 - edge=_v.node->_first_out_edge;
1.502 - if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
1.503 - }
1.504 - protected:
1.505 - SymEdgeIt& operator++() {
1.506 - if (out_or_in) {
1.507 - node_item* v=edge->_tail;
1.508 - edge=edge->_next_out;
1.509 - if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
1.510 - } else {
1.511 - edge=edge->_next_in;
1.512 - }
1.513 - return *this;
1.514 - }
1.515 - protected:
1.516 - Node aNode() const {
1.517 - return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); }
1.518 - Node bNode() const {
1.519 - return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); }
1.520 - };
1.521 - };
1.522 -
1.523 - inline
1.524 - std::ostream& operator<<(std::ostream& os, const ListGraph::Node& i) {
1.525 - if (i.valid())
1.526 - os << i.node->id;
1.527 - else
1.528 - os << "invalid";
1.529 - return os;
1.530 - }
1.531 -
1.532 - inline
1.533 - std::ostream& operator<<(std::ostream& os, const ListGraph::Edge& i) {
1.534 - if (i.valid())
1.535 - os << "(" << i.tailNode() << "--" << i.edge->id << "->"
1.536 - << i.headNode() << ")";
1.537 - else
1.538 - os << "invalid";
1.539 - return os;
1.540 - }
1.541 -
1.542 - class UndirListGraph : public ListGraph {
1.543 - public:
1.544 - typedef SymEdgeIt OutEdgeIt;
1.545 - typedef SymEdgeIt InEdgeIt;
1.546 - };
1.547 -
1.548 -} //namespace hugo
1.549 -
1.550 -#endif //HUGO_LIST_GRAPH_H
2.1 --- a/src/work/marci/bfsit_vs_byhand.cc Fri May 14 18:08:29 2004 +0000
2.2 +++ b/src/work/marci/bfsit_vs_byhand.cc Fri May 14 18:28:57 2004 +0000
2.3 @@ -2,7 +2,7 @@
2.4 #include <iostream>
2.5 #include <fstream>
2.6
2.7 -#include <list_graph.h>
2.8 +#include <sage_graph.h>
2.9 //#include <smart_graph.h>
2.10 #include <hugo/dimacs.h>
2.11 #include <hugo/time_measure.h>
2.12 @@ -12,7 +12,7 @@
2.13 using namespace hugo;
2.14
2.15 int main() {
2.16 - typedef ListGraph Graph;
2.17 + typedef SageGraph Graph;
2.18 typedef Graph::Node Node;
2.19 typedef Graph::NodeIt NodeIt;
2.20 typedef Graph::Edge Edge;
3.1 --- a/src/work/marci/bipartite_graph_wrapper_test.cc Fri May 14 18:08:29 2004 +0000
3.2 +++ b/src/work/marci/bipartite_graph_wrapper_test.cc Fri May 14 18:28:57 2004 +0000
3.3 @@ -3,7 +3,7 @@
3.4 #include <fstream>
3.5 #include <vector>
3.6
3.7 -#include <list_graph.h>
3.8 +#include <sage_graph.h>
3.9 //#include <smart_graph.h>
3.10 //#include <dimacs.h>
3.11 #include <hugo/time_measure.h>
3.12 @@ -17,7 +17,7 @@
3.13 using namespace hugo;
3.14
3.15 int main() {
3.16 - typedef UndirListGraph Graph;
3.17 + typedef UndirSageGraph Graph;
3.18 typedef Graph::Node Node;
3.19 typedef Graph::NodeIt NodeIt;
3.20 typedef Graph::Edge Edge;
4.1 --- a/src/work/marci/bipartite_matching_try.cc Fri May 14 18:08:29 2004 +0000
4.2 +++ b/src/work/marci/bipartite_matching_try.cc Fri May 14 18:28:57 2004 +0000
4.3 @@ -4,7 +4,7 @@
4.4 #include <vector>
4.5 #include <cstdlib>
4.6
4.7 -#include <list_graph.h>
4.8 +#include <sage_graph.h>
4.9 //#include <smart_graph.h>
4.10 //#include <dimacs.h>
4.11 #include <hugo/time_measure.h>
4.12 @@ -40,7 +40,7 @@
4.13 using namespace hugo;
4.14
4.15 int main() {
4.16 - typedef UndirListGraph Graph;
4.17 + typedef UndirSageGraph Graph;
4.18 typedef Graph::Node Node;
4.19 typedef Graph::NodeIt NodeIt;
4.20 typedef Graph::Edge Edge;
4.21 @@ -166,7 +166,7 @@
4.22 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
4.23 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
4.24 // while (max_flow_test.augmentOnShortestPath()) { }
4.25 - typedef ListGraph MutableGraph;
4.26 + typedef SageGraph MutableGraph;
4.27 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
4.28 while (max_flow_test.augmentOnBlockingFlow2()) {
4.29 std::cout << max_flow_test.flowValue() << std::endl;
5.1 --- a/src/work/marci/bipartite_matching_try_3.cc Fri May 14 18:08:29 2004 +0000
5.2 +++ b/src/work/marci/bipartite_matching_try_3.cc Fri May 14 18:28:57 2004 +0000
5.3 @@ -3,7 +3,7 @@
5.4 #include <fstream>
5.5 #include <vector>
5.6
5.7 -#include <list_graph.h>
5.8 +#include <sage_graph.h>
5.9 //#include <smart_graph.h>
5.10 //#include <dimacs.h>
5.11 #include <hugo/time_measure.h>
5.12 @@ -19,7 +19,7 @@
5.13
5.14 int main() {
5.15 //typedef UndirListGraph Graph;
5.16 - typedef BipartiteGraph<ListGraph> Graph;
5.17 + typedef BipartiteGraph<SageGraph> Graph;
5.18
5.19 typedef Graph::Node Node;
5.20 typedef Graph::NodeIt NodeIt;
6.1 --- a/src/work/marci/iterator_bfs_demo.cc Fri May 14 18:08:29 2004 +0000
6.2 +++ b/src/work/marci/iterator_bfs_demo.cc Fri May 14 18:28:57 2004 +0000
6.3 @@ -3,7 +3,7 @@
6.4 #include <vector>
6.5 #include <string>
6.6
6.7 -#include <list_graph.h>
6.8 +#include <sage_graph.h>
6.9 //#include <smart_graph.h>
6.10 #include <bfs_dfs.h>
6.11 #include <hugo/graph_wrapper.h>
6.12 @@ -29,7 +29,7 @@
6.13 int main (int, char*[])
6.14 {
6.15 //typedef SmartGraph Graph;
6.16 - typedef ListGraph Graph;
6.17 + typedef SageGraph Graph;
6.18
6.19 typedef Graph::Node Node;
6.20 typedef Graph::Edge Edge;
7.1 --- a/src/work/marci/lg_vs_sg.cc Fri May 14 18:08:29 2004 +0000
7.2 +++ b/src/work/marci/lg_vs_sg.cc Fri May 14 18:28:57 2004 +0000
7.3 @@ -3,7 +3,8 @@
7.4 #include <fstream>
7.5 #include <string>
7.6
7.7 -#include <list_graph.h>
7.8 +#include <sage_graph.h>
7.9 +#include <hugo/list_graph.h>
7.10 #include <hugo/smart_graph.h>
7.11 #include <hugo/dimacs.h>
7.12 #include <max_flow.h>
7.13 @@ -18,10 +19,10 @@
7.14 int main(int, char** argv) {
7.15
7.16 std::string in=argv[1];
7.17 - typedef ListGraph MutableGraph;
7.18 + typedef SageGraph MutableGraph;
7.19
7.20 {
7.21 - typedef ListGraph Graph;
7.22 + typedef SageGraph Graph;
7.23 typedef Graph::Node Node;
7.24 typedef Graph::EdgeIt EdgeIt;
7.25
7.26 @@ -37,7 +38,7 @@
7.27 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
7.28 max_flow_test(g, s, t, cap, flow/*, true*/);
7.29
7.30 - std::cout << "ListGraph ..." << std::endl;
7.31 + std::cout << "SageGraph ..." << std::endl;
7.32
7.33 {
7.34 std::cout << "preflow ..." << std::endl;
7.35 @@ -92,7 +93,6 @@
7.36 }
7.37 }
7.38
7.39 -
7.40 {
7.41 typedef SmartGraph Graph;
7.42 typedef Graph::Node Node;
7.43 @@ -112,7 +112,7 @@
7.44 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
7.45 // max_flow_test(g, s, t, cap, flow);
7.46
7.47 - std::cout << "SmatrGraph ..." << std::endl;
7.48 + std::cout << "SmartGraph ..." << std::endl;
7.49
7.50 {
7.51 std::cout << "preflow ..." << std::endl;
7.52 @@ -168,6 +168,81 @@
7.53 }
7.54 }
7.55
7.56 + {
7.57 + typedef ListGraph Graph;
7.58 + typedef Graph::Node Node;
7.59 + typedef Graph::EdgeIt EdgeIt;
7.60 +
7.61 + Graph g;
7.62 + Node s, t;
7.63 + Graph::EdgeMap<int> cap(g);
7.64 + std::ifstream ins(in.c_str());
7.65 + //readDimacsMaxFlow(ins, g, s, t, cap);
7.66 + readDimacs(ins, g, cap, s, t);
7.67 +
7.68 + Timer ts;
7.69 + Graph::EdgeMap<int> flow(g); //0 flow
7.70 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
7.71 + max_flow_test(g, s, t, cap, flow/*, true*/);
7.72 + // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
7.73 + // max_flow_test(g, s, t, cap, flow);
7.74 +
7.75 + std::cout << "ListGraph ..." << std::endl;
7.76 +
7.77 + {
7.78 + std::cout << "preflow ..." << std::endl;
7.79 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.80 + ts.reset();
7.81 + max_flow_test.run();
7.82 + std::cout << "elapsed time: " << ts << std::endl;
7.83 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
7.84 + }
7.85 +
7.86 + {
7.87 + std::cout << "physical blocking flow augmentation ..." << std::endl;
7.88 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.89 + ts.reset();
7.90 + int i=0;
7.91 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
7.92 + std::cout << "elapsed time: " << ts << std::endl;
7.93 + std::cout << "number of augmentation phases: " << i << std::endl;
7.94 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
7.95 + }
7.96 +
7.97 +// {
7.98 +// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
7.99 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.100 +// ts.reset();
7.101 +// int i=0;
7.102 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
7.103 +// std::cout << "elapsed time: " << ts << std::endl;
7.104 +// std::cout << "number of augmentation phases: " << i << std::endl;
7.105 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
7.106 +// }
7.107 +
7.108 + {
7.109 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
7.110 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.111 + ts.reset();
7.112 + int i=0;
7.113 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
7.114 + std::cout << "elapsed time: " << ts << std::endl;
7.115 + std::cout << "number of augmentation phases: " << i << std::endl;
7.116 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
7.117 + }
7.118 +
7.119 + {
7.120 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
7.121 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.122 + ts.reset();
7.123 + int i=0;
7.124 + while (max_flow_test.augmentOnShortestPath()) { ++i; }
7.125 + std::cout << "elapsed time: " << ts << std::endl;
7.126 + std::cout << "number of augmentation phases: " << i << std::endl;
7.127 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
7.128 + }
7.129 + }
7.130 +
7.131
7.132
7.133
8.1 --- a/src/work/marci/macro_test.cc Fri May 14 18:08:29 2004 +0000
8.2 +++ b/src/work/marci/macro_test.cc Fri May 14 18:28:57 2004 +0000
8.3 @@ -2,14 +2,14 @@
8.4 #include <iostream>
8.5 #include <fstream>
8.6
8.7 -#include <list_graph.h>
8.8 +#include <sage_graph.h>
8.9 #include <hugo/for_each_macros.h>
8.10
8.11 using namespace hugo;
8.12
8.13 int main()
8.14 {
8.15 - typedef ListGraph Graph;
8.16 + typedef SageGraph Graph;
8.17 Graph g;
8.18 Graph::Node n1=g.addNode();
8.19 Graph::Node n2=g.addNode();
9.1 --- a/src/work/marci/max_bipartite_matching_demo.cc Fri May 14 18:08:29 2004 +0000
9.2 +++ b/src/work/marci/max_bipartite_matching_demo.cc Fri May 14 18:28:57 2004 +0000
9.3 @@ -9,7 +9,7 @@
9.4 #include <LEDA/list.h>
9.5
9.6 #include <leda_graph_wrapper.h>
9.7 -#include <list_graph.h>
9.8 +#include <sage_graph.h>
9.9 #include <dimacs.h>
9.10 #include <time_measure.h>
9.11 #include <edmonds_karp.h>
10.1 --- a/src/work/marci/max_flow_1.cc Fri May 14 18:08:29 2004 +0000
10.2 +++ b/src/work/marci/max_flow_1.cc Fri May 14 18:28:57 2004 +0000
10.3 @@ -2,7 +2,7 @@
10.4 #include <iostream>
10.5 #include <fstream>
10.6
10.7 -#include <list_graph.h>
10.8 +#include <sage_graph.h>
10.9 #include <hugo/smart_graph.h>
10.10 #include <hugo/dimacs.h>
10.11 #include <hugo/time_measure.h>
10.12 @@ -19,7 +19,7 @@
10.13
10.14 int main(int, char **) {
10.15
10.16 - typedef ListGraph MutableGraph;
10.17 + typedef SageGraph MutableGraph;
10.18
10.19 typedef SmartGraph Graph;
10.20 // typedef ListGraph Graph;
11.1 --- a/src/work/marci/max_flow_demo.cc Fri May 14 18:08:29 2004 +0000
11.2 +++ b/src/work/marci/max_flow_demo.cc Fri May 14 18:28:57 2004 +0000
11.3 @@ -2,7 +2,7 @@
11.4 #include <iostream>
11.5 #include <fstream>
11.6
11.7 -#include <list_graph.h>
11.8 +#include <sage_graph.h>
11.9 #include <hugo/smart_graph.h>
11.10 #include <hugo/dimacs.h>
11.11 #include <hugo/time_measure.h>
11.12 @@ -34,10 +34,10 @@
11.13
11.14 int main(int, char **) {
11.15
11.16 - typedef ListGraph MutableGraph;
11.17 + typedef SageGraph MutableGraph;
11.18
11.19 typedef SmartGraph Graph;
11.20 - // typedef ListGraph Graph;
11.21 + // typedef SageGraph Graph;
11.22 typedef Graph::Node Node;
11.23 typedef Graph::EdgeIt EdgeIt;
11.24
12.1 --- a/src/work/marci/top_sort_test.cc Fri May 14 18:08:29 2004 +0000
12.2 +++ b/src/work/marci/top_sort_test.cc Fri May 14 18:28:57 2004 +0000
12.3 @@ -5,7 +5,7 @@
12.4
12.5 #include <hugo/dimacs.h>
12.6 #include <bfs_dfs_misc.h>
12.7 -#include <list_graph.h>
12.8 +#include <sage_graph.h>
12.9 #include <hugo/graph_wrapper.h>
12.10 #include <hugo/maps.h>
12.11 #include <hugo/for_each_macros.h>
12.12 @@ -16,7 +16,7 @@
12.13 using std::endl;
12.14
12.15 int main() {
12.16 - typedef ListGraph Graph;
12.17 + typedef SageGraph Graph;
12.18 Graph g;
12.19 readDimacs(std::cin, g);
12.20
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
13.2 +++ b/src/work/sage_graph.h Fri May 14 18:28:57 2004 +0000
13.3 @@ -0,0 +1,547 @@
13.4 +// -*- c++ -*-
13.5 +#ifndef HUGO_SAGE_GRAPH_H
13.6 +#define HUGO_SAGE_GRAPH_H
13.7 +
13.8 +#include <iostream>
13.9 +#include <vector>
13.10 +
13.11 +#include <hugo/invalid.h>
13.12 +
13.13 +namespace hugo {
13.14 +
13.15 + template <typename It>
13.16 + int count(It it) {
13.17 + int i=0;
13.18 + for( ; it.valid(); ++it) { ++i; }
13.19 + return i;
13.20 + }
13.21 +
13.22 + class SageGraph {
13.23 + struct node_item;
13.24 + struct edge_item;
13.25 + public:
13.26 + class Node;
13.27 + class NodeIt;
13.28 + class Edge;
13.29 + class EdgeIt;
13.30 + class OutEdgeIt;
13.31 + class InEdgeIt;
13.32 + class SymEdgeIt;
13.33 + template <typename T> class NodeMap;
13.34 + template <typename T> class EdgeMap;
13.35 +// private:
13.36 + template <typename T> friend class NodeMap;
13.37 + template <typename T> friend class EdgeMap;
13.38 +
13.39 + template <typename T>
13.40 + class NodeMap {
13.41 + const SageGraph& G;
13.42 + std::vector<T> container;
13.43 + public:
13.44 + typedef T ValueType;
13.45 + typedef Node KeyType;
13.46 + NodeMap(const SageGraph& _G) : G(_G), container(G.node_id) { }
13.47 + NodeMap(const SageGraph& _G, T a) :
13.48 + G(_G), container(G.node_id, a) { }
13.49 + void set(Node n, T a) { container[/*G.id(n)*/n.node->id]=a; }
13.50 +// T get(Node n) const { return container[/*G.id(n)*/n.node->id]; }
13.51 + typename std::vector<T>::reference operator[](Node n) {
13.52 + return container[/*G.id(n)*/n.node->id]; }
13.53 + typename std::vector<T>::const_reference operator[](Node n) const {
13.54 + return container[/*G.id(n)*/n.node->id];
13.55 + }
13.56 + void update() { container.resize(G.node_id); }
13.57 + void update(T a) { container.resize(G.node_id, a); }
13.58 + };
13.59 +
13.60 + template <typename T>
13.61 + class EdgeMap {
13.62 + const SageGraph& G;
13.63 + std::vector<T> container;
13.64 + public:
13.65 + typedef T ValueType;
13.66 + typedef Edge KeyType;
13.67 + EdgeMap(const SageGraph& _G) : G(_G), container(G.edge_id) { }
13.68 + EdgeMap(const SageGraph& _G, T a) :
13.69 + G(_G), container(G.edge_id, a) { }
13.70 + void set(Edge e, T a) { container[/*G.id(e)*/e.edge->id]=a; }
13.71 +// T get(Edge e) const { return container[/*G.id(e)*/e.edge->id]; }
13.72 + typename std::vector<T>::reference operator[](Edge e) {
13.73 + return container[/*G.id(e)*/e.edge->id]; }
13.74 + typename std::vector<T>::const_reference operator[](Edge e) const {
13.75 + return container[/*G.id(e)*/e.edge->id];
13.76 + }
13.77 + void update() { container.resize(G.edge_id); }
13.78 + void update(T a) { container.resize(G.edge_id, a); }
13.79 + };
13.80 +
13.81 + private:
13.82 + int node_id;
13.83 + int edge_id;
13.84 + int _node_num;
13.85 + int _edge_num;
13.86 +
13.87 + node_item* _first_node;
13.88 + node_item* _last_node;
13.89 +
13.90 + struct node_item {
13.91 + int id;
13.92 + edge_item* _first_out_edge;
13.93 + edge_item* _last_out_edge;
13.94 + edge_item* _first_in_edge;
13.95 + edge_item* _last_in_edge;
13.96 + node_item* _next_node;
13.97 + node_item* _prev_node;
13.98 + };
13.99 +
13.100 + struct edge_item {
13.101 + int id;
13.102 + node_item* _tail;
13.103 + node_item* _head;
13.104 + edge_item* _next_out;
13.105 + edge_item* _prev_out;
13.106 + edge_item* _next_in;
13.107 + edge_item* _prev_in;
13.108 + };
13.109 +
13.110 + node_item* _add_node() {
13.111 + node_item* p=new node_item;
13.112 + p->id=node_id++;
13.113 + p->_first_out_edge=0;
13.114 + p->_last_out_edge=0;
13.115 + p->_first_in_edge=0;
13.116 + p->_last_in_edge=0;
13.117 + p->_prev_node=_last_node;
13.118 + p->_next_node=0;
13.119 + if (_last_node) _last_node->_next_node=p;
13.120 + _last_node=p;
13.121 + if (!_first_node) _first_node=p;
13.122 +
13.123 + ++_node_num;
13.124 + return p;
13.125 + }
13.126 +
13.127 + edge_item* _add_edge(node_item* _tail, node_item* _head) {
13.128 + edge_item* e=new edge_item;
13.129 + e->id=edge_id++;
13.130 + e->_tail=_tail;
13.131 + e->_head=_head;
13.132 +
13.133 + e->_prev_out=_tail->_last_out_edge;
13.134 + if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
13.135 + _tail->_last_out_edge=e;
13.136 + if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
13.137 + e->_next_out=0;
13.138 +
13.139 + e->_prev_in=_head->_last_in_edge;
13.140 + if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
13.141 + _head->_last_in_edge=e;
13.142 + if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
13.143 + e->_next_in=0;
13.144 +
13.145 + ++_edge_num;
13.146 + return e;
13.147 + }
13.148 +
13.149 + //deletes a node which has no out edge and no in edge
13.150 + void _delete_node(node_item* v) {
13.151 + if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else
13.152 + _last_node=v->_prev_node;
13.153 + if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else
13.154 + _first_node=v->_next_node;
13.155 +
13.156 + delete v;
13.157 + --_node_num;
13.158 + }
13.159 +
13.160 + void _delete_edge(edge_item* e) {
13.161 + if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
13.162 + (e->_tail)->_last_out_edge=e->_prev_out;
13.163 + if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
13.164 + (e->_tail)->_first_out_edge=e->_next_out;
13.165 + if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
13.166 + (e->_head)->_last_in_edge=e->_prev_in;
13.167 + if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
13.168 + (e->_head)->_first_in_edge=e->_next_in;
13.169 +
13.170 + delete e;
13.171 + --_edge_num;
13.172 + }
13.173 +
13.174 + void _set_tail(edge_item* e, node_item* _tail) {
13.175 + if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
13.176 + (e->_tail)->_last_out_edge=e->_prev_out;
13.177 + if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
13.178 + (e->_tail)->_first_out_edge=e->_next_out;
13.179 +
13.180 + e->_tail=_tail;
13.181 +
13.182 + e->_prev_out=_tail->_last_out_edge;
13.183 + if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
13.184 + _tail->_last_out_edge=e;
13.185 + if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
13.186 + e->_next_out=0;
13.187 + }
13.188 +
13.189 + void _set_head(edge_item* e, node_item* _head) {
13.190 + if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
13.191 + (e->_head)->_last_in_edge=e->_prev_in;
13.192 + if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
13.193 + (e->_head)->_first_in_edge=e->_next_in;
13.194 +
13.195 + e->_head=_head;
13.196 +
13.197 + e->_prev_in=_head->_last_in_edge;
13.198 + if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
13.199 + _head->_last_in_edge=e;
13.200 + if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
13.201 + e->_next_in=0;
13.202 + }
13.203 +
13.204 + public:
13.205 +
13.206 + /* default constructor */
13.207 +
13.208 + SageGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
13.209 +
13.210 + ~SageGraph() {
13.211 + NodeIt n;
13.212 + while (this->valid(first(n))) erase(n);
13.213 + //while (first<NodeIt>().valid()) erase(first<NodeIt>());
13.214 + }
13.215 +
13.216 + int nodeNum() const { return _node_num; }
13.217 + int edgeNum() const { return _edge_num; }
13.218 +
13.219 + /* functions to construct iterators from the graph, or from each other */
13.220 +
13.221 + //NodeIt firstNode() const { return NodeIt(*this); }
13.222 + //EdgeIt firstEdge() const { return EdgeIt(*this); }
13.223 +
13.224 + //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); }
13.225 + //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); }
13.226 + //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); }
13.227 + Node tail(Edge e) const { return e.tailNode(); }
13.228 + Node head(Edge e) const { return e.headNode(); }
13.229 +
13.230 + Node aNode(const OutEdgeIt& e) const { return e.aNode(); }
13.231 + Node aNode(const InEdgeIt& e) const { return e.aNode(); }
13.232 + Node aNode(const SymEdgeIt& e) const { return e.aNode(); }
13.233 +
13.234 + Node bNode(const OutEdgeIt& e) const { return e.bNode(); }
13.235 + Node bNode(const InEdgeIt& e) const { return e.bNode(); }
13.236 + Node bNode(const SymEdgeIt& e) const { return e.bNode(); }
13.237 +
13.238 + //Node invalid_node() { return Node(); }
13.239 + //Edge invalid_edge() { return Edge(); }
13.240 + //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); }
13.241 + //InEdgeIt invalid_in_edge() { return InEdgeIt(); }
13.242 + //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); }
13.243 +
13.244 + /* same methods in other style */
13.245 + /* for experimental purpose */
13.246 +
13.247 + NodeIt& first(NodeIt& v) const {
13.248 + v=NodeIt(*this); return v; }
13.249 + EdgeIt& first(EdgeIt& e) const {
13.250 + e=EdgeIt(*this); return e; }
13.251 + OutEdgeIt& first(OutEdgeIt& e, Node v) const {
13.252 + e=OutEdgeIt(*this, v); return e; }
13.253 + InEdgeIt& first(InEdgeIt& e, Node v) const {
13.254 + e=InEdgeIt(*this, v); return e; }
13.255 + SymEdgeIt& first(SymEdgeIt& e, Node v) const {
13.256 + e=SymEdgeIt(*this, v); return e; }
13.257 + //void getTail(Node& n, const Edge& e) const { n=tail(e); }
13.258 + //void getHead(Node& n, const Edge& e) const { n=head(e); }
13.259 +
13.260 + //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); }
13.261 + //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); }
13.262 + //void getANode(Node& n, const SymEdgeIt& e) const { n=e.aNode(); }
13.263 + //void getBNode(Node& n, const OutEdgeIt& e) const { n=e.bNode(); }
13.264 + //void getBNode(Node& n, const InEdgeIt& e) const { n=e.bNode(); }
13.265 + //void getBNode(Node& n, const SymEdgeIt& e) const { n=e.bNode(); }
13.266 + //void get_invalid(Node& n) { n=Node(); }
13.267 + //void get_invalid(Edge& e) { e=Edge(); }
13.268 + //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }
13.269 + //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }
13.270 + //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
13.271 +
13.272 +// template< typename It >
13.273 +// It first() const {
13.274 +// It e;
13.275 +// first(e);
13.276 +// return e;
13.277 +// }
13.278 +
13.279 +// template< typename It >
13.280 +// It first(Node v) const {
13.281 +// It e;
13.282 +// first(e, v);
13.283 +// return e;
13.284 +// }
13.285 +
13.286 + bool valid(Node n) const { return n.valid(); }
13.287 + bool valid(Edge e) const { return e.valid(); }
13.288 +
13.289 +// template <typename It> It getNext(It it) const {
13.290 +// It tmp(it); next(tmp); return tmp; }
13.291 +// NodeIt& next(NodeIt& it) const { return ++it; }
13.292 +// EdgeIt& next(EdgeIt& it) const { return ++it; }
13.293 +// OutEdgeIt& next(OutEdgeIt& it) const { return ++it; }
13.294 +// InEdgeIt& next(InEdgeIt& it) const { return ++it; }
13.295 +// SymEdgeIt& next(SymEdgeIt& it) const { return ++it; }
13.296 +// template <typename It> It& next(It& it) const { return ++it; }
13.297 + template <typename It> It& next(It& it) const { ++it; return it; }
13.298 +
13.299 +
13.300 + /* for getting id's of graph objects */
13.301 + /* these are important for the implementation of property vectors */
13.302 +
13.303 + int id(Node v) const { return v.node->id; }
13.304 + int id(Edge e) const { return e.edge->id; }
13.305 +
13.306 + /* adding nodes and edges */
13.307 +
13.308 + Node addNode() { return Node(_add_node()); }
13.309 + Edge addEdge(Node u, Node v) {
13.310 + return Edge(_add_edge(u.node, v.node));
13.311 + }
13.312 +
13.313 + void erase(Node i) {
13.314 + {
13.315 + OutEdgeIt e;
13.316 + while (this->valid(first(e, i))) erase(e);
13.317 + }
13.318 + {
13.319 + InEdgeIt e;
13.320 + while (this->valid(first(e, i))) erase(e);
13.321 + }
13.322 + //while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
13.323 + //while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
13.324 + _delete_node(i.node);
13.325 + }
13.326 +
13.327 + void erase(Edge e) { _delete_edge(e.edge); }
13.328 +
13.329 + void clear() {
13.330 + NodeIt e;
13.331 + while (this->valid(first(e))) erase(e);
13.332 + //while (first<NodeIt>().valid()) erase(first<NodeIt>());
13.333 + }
13.334 +
13.335 + void setTail(Edge e, Node tail) {
13.336 + _set_tail(e.edge, tail.node);
13.337 + }
13.338 +
13.339 + void setHead(Edge e, Node head) {
13.340 + _set_head(e.edge, head.node);
13.341 + }
13.342 +
13.343 + /* stream operations, for testing purpose */
13.344 +
13.345 +// friend std::ostream& operator<<(std::ostream& os, const Node& i) {
13.346 +// if (i.valid())
13.347 +// os << i.node->id;
13.348 +// else
13.349 +// os << "invalid";
13.350 +// return os;
13.351 +// }
13.352 +// friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
13.353 +// if (i.valid())
13.354 +// os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
13.355 +// else
13.356 +// os << "invalid";
13.357 +// return os;
13.358 +// }
13.359 +
13.360 + class Node {
13.361 + friend class SageGraph;
13.362 + template <typename T> friend class NodeMap;
13.363 +
13.364 + friend class Edge;
13.365 + friend class OutEdgeIt;
13.366 + friend class InEdgeIt;
13.367 + friend class SymEdgeIt;
13.368 + //public: //FIXME: It is required by op= of NodeIt
13.369 + protected:
13.370 + node_item* node;
13.371 + protected:
13.372 + friend int SageGraph::id(Node v) const;
13.373 + public:
13.374 + Node() /*: node(0)*/ { }
13.375 + Node(const Invalid&) : node(0) { }
13.376 + protected:
13.377 + Node(node_item* _node) : node(_node) { }
13.378 + bool valid() const { return (node); }
13.379 + public:
13.380 + //void makeInvalid() { node=0; }
13.381 + friend bool operator==(Node u, Node v) { return v.node==u.node; }
13.382 + friend bool operator!=(Node u, Node v) { return v.node!=u.node; }
13.383 + friend std::ostream& operator<<(std::ostream& os, const Node& i);
13.384 + };
13.385 +
13.386 + class NodeIt : public Node {
13.387 + friend class SageGraph;
13.388 + //protected:
13.389 + public: //for everybody but marci
13.390 + NodeIt(const SageGraph& G) : Node(G._first_node) { }
13.391 + public:
13.392 + NodeIt() : Node() { }
13.393 + NodeIt(const Invalid& i) : Node(i) { }
13.394 + protected:
13.395 + NodeIt(node_item* v) : Node(v) { }
13.396 + NodeIt& operator++() { node=node->_next_node; return *this; }
13.397 + //FIXME::
13.398 + // NodeIt& operator=(const Node& e)
13.399 + // { node=e.node; return *this; }
13.400 + };
13.401 +
13.402 + class Edge {
13.403 + friend class SageGraph;
13.404 + template <typename T> friend class EdgeMap;
13.405 +
13.406 + friend class Node;
13.407 + friend class NodeIt;
13.408 + protected:
13.409 + edge_item* edge;
13.410 + friend int SageGraph::id(Edge e) const;
13.411 + public:
13.412 + Edge() /*: edge(0)*/ { }
13.413 + Edge(const Invalid&) : edge(0) { }
13.414 + //Edge() { }
13.415 + protected:
13.416 + Edge(edge_item* _edge) : edge(_edge) { }
13.417 + bool valid() const { return (edge); }
13.418 + public:
13.419 + //void makeInvalid() { edge=0; }
13.420 + friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; }
13.421 + friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; }
13.422 + protected:
13.423 + Node tailNode() const { return Node(edge->_tail); }
13.424 + Node headNode() const { return Node(edge->_head); }
13.425 + public:
13.426 + friend std::ostream& operator<<(std::ostream& os, const Edge& i);
13.427 + };
13.428 +
13.429 + class EdgeIt : public Edge {
13.430 + friend class SageGraph;
13.431 + //protected:
13.432 + public: //for alpar
13.433 + EdgeIt(const SageGraph& G) {
13.434 + node_item* v=G._first_node;
13.435 + if (v) edge=v->_first_out_edge; else edge=0;
13.436 + while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
13.437 + }
13.438 + public:
13.439 + EdgeIt() : Edge() { }
13.440 + EdgeIt(const Invalid& i) : Edge(i) { }
13.441 + protected:
13.442 + EdgeIt(edge_item* _e) : Edge(_e) { }
13.443 + EdgeIt& operator++() {
13.444 + node_item* v=edge->_tail;
13.445 + edge=edge->_next_out;
13.446 + while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
13.447 + return *this;
13.448 + }
13.449 + };
13.450 +
13.451 + class OutEdgeIt : public Edge {
13.452 + friend class SageGraph;
13.453 + //node_item* v;
13.454 + //protected:
13.455 + protected: //for alpar
13.456 + OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
13.457 + public:
13.458 + OutEdgeIt() : Edge()/*, v(0)*/ { }
13.459 + OutEdgeIt(const Invalid& i) : Edge(i) { }
13.460 + OutEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
13.461 + protected:
13.462 + OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
13.463 + protected:
13.464 + Node aNode() const { return Node(edge->_tail); }
13.465 + Node bNode() const { return Node(edge->_head); }
13.466 + };
13.467 +
13.468 + class InEdgeIt : public Edge {
13.469 + friend class SageGraph;
13.470 + //node_item* v;
13.471 + //protected:
13.472 + protected: //for alpar
13.473 + InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
13.474 + public:
13.475 + InEdgeIt() : Edge()/*, v(0)*/ { }
13.476 + InEdgeIt(const Invalid& i) : Edge(i) { }
13.477 + InEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
13.478 + protected:
13.479 + InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
13.480 + protected:
13.481 + Node aNode() const { return Node(edge->_head); }
13.482 + Node bNode() const { return Node(edge->_tail); }
13.483 + };
13.484 +
13.485 + class SymEdgeIt : public Edge {
13.486 + friend class SageGraph;
13.487 + bool out_or_in; //1 iff out, 0 iff in
13.488 + //node_item* v;
13.489 + //protected:
13.490 + protected: //for alpar
13.491 + SymEdgeIt(const Node& _v) /*: v(_v.node)*/ {
13.492 + out_or_in=1;
13.493 + edge=_v.node->_first_out_edge;
13.494 + if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
13.495 + }
13.496 + public:
13.497 + SymEdgeIt() : Edge() /*, v(0)*/ { }
13.498 + SymEdgeIt(const Invalid& i) : Edge(i) { }
13.499 + SymEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ {
13.500 + out_or_in=1;
13.501 + edge=_v.node->_first_out_edge;
13.502 + if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
13.503 + }
13.504 + protected:
13.505 + SymEdgeIt& operator++() {
13.506 + if (out_or_in) {
13.507 + node_item* v=edge->_tail;
13.508 + edge=edge->_next_out;
13.509 + if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
13.510 + } else {
13.511 + edge=edge->_next_in;
13.512 + }
13.513 + return *this;
13.514 + }
13.515 + protected:
13.516 + Node aNode() const {
13.517 + return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); }
13.518 + Node bNode() const {
13.519 + return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); }
13.520 + };
13.521 + };
13.522 +
13.523 + inline
13.524 + std::ostream& operator<<(std::ostream& os, const SageGraph::Node& i) {
13.525 + if (i.valid())
13.526 + os << i.node->id;
13.527 + else
13.528 + os << "invalid";
13.529 + return os;
13.530 + }
13.531 +
13.532 + inline
13.533 + std::ostream& operator<<(std::ostream& os, const SageGraph::Edge& i) {
13.534 + if (i.valid())
13.535 + os << "(" << i.tailNode() << "--" << i.edge->id << "->"
13.536 + << i.headNode() << ")";
13.537 + else
13.538 + os << "invalid";
13.539 + return os;
13.540 + }
13.541 +
13.542 + class UndirSageGraph : public SageGraph {
13.543 + public:
13.544 + typedef SymEdgeIt OutEdgeIt;
13.545 + typedef SymEdgeIt InEdgeIt;
13.546 + };
13.547 +
13.548 +} //namespace hugo
13.549 +
13.550 +#endif //HUGO_SAGE_GRAPH_H