# HG changeset patch
# User marci
# Date 1084559337 0
# Node ID e812963087f03434d64702ffbdff1fc997958af2
# Parent bfd6c14e2975b5a58480fbc8f692d10527696d4a
To avoid confusion my old ListGraph is can be used under name SageGraph, work/sage_graph.h contains it.
diff -r bfd6c14e2975 -r e812963087f0 src/work/list_graph.h
--- a/src/work/list_graph.h Fri May 14 18:08:29 2004 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,547 +0,0 @@
-// -*- c++ -*-
-#ifndef HUGO_LIST_GRAPH_H
-#define HUGO_LIST_GRAPH_H
-
-#include <iostream>
-#include <vector>
-
-#include <hugo/invalid.h>
-
-namespace hugo {
-
- template <typename It>
- int count(It it) {
- int i=0;
- for( ; it.valid(); ++it) { ++i; }
- return i;
- }
-
- class ListGraph {
- struct node_item;
- struct edge_item;
- public:
- class Node;
- class NodeIt;
- class Edge;
- class EdgeIt;
- class OutEdgeIt;
- class InEdgeIt;
- class SymEdgeIt;
- template <typename T> class NodeMap;
- template <typename T> class EdgeMap;
-// private:
- template <typename T> friend class NodeMap;
- template <typename T> friend class EdgeMap;
-
- template <typename T>
- class NodeMap {
- const ListGraph& G;
- std::vector<T> container;
- public:
- typedef T ValueType;
- typedef Node KeyType;
- NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { }
- NodeMap(const ListGraph& _G, T a) :
- G(_G), container(G.node_id, a) { }
- void set(Node n, T a) { container[/*G.id(n)*/n.node->id]=a; }
-// T get(Node n) const { return container[/*G.id(n)*/n.node->id]; }
- typename std::vector<T>::reference operator[](Node n) {
- return container[/*G.id(n)*/n.node->id]; }
- typename std::vector<T>::const_reference operator[](Node n) const {
- return container[/*G.id(n)*/n.node->id];
- }
- void update() { container.resize(G.node_id); }
- void update(T a) { container.resize(G.node_id, a); }
- };
-
- template <typename T>
- class EdgeMap {
- const ListGraph& G;
- std::vector<T> container;
- public:
- typedef T ValueType;
- typedef Edge KeyType;
- EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { }
- EdgeMap(const ListGraph& _G, T a) :
- G(_G), container(G.edge_id, a) { }
- void set(Edge e, T a) { container[/*G.id(e)*/e.edge->id]=a; }
-// T get(Edge e) const { return container[/*G.id(e)*/e.edge->id]; }
- typename std::vector<T>::reference operator[](Edge e) {
- return container[/*G.id(e)*/e.edge->id]; }
- typename std::vector<T>::const_reference operator[](Edge e) const {
- return container[/*G.id(e)*/e.edge->id];
- }
- void update() { container.resize(G.edge_id); }
- void update(T a) { container.resize(G.edge_id, a); }
- };
-
- private:
- int node_id;
- int edge_id;
- int _node_num;
- int _edge_num;
-
- node_item* _first_node;
- node_item* _last_node;
-
- struct node_item {
- int id;
- edge_item* _first_out_edge;
- edge_item* _last_out_edge;
- edge_item* _first_in_edge;
- edge_item* _last_in_edge;
- node_item* _next_node;
- node_item* _prev_node;
- };
-
- struct edge_item {
- int id;
- node_item* _tail;
- node_item* _head;
- edge_item* _next_out;
- edge_item* _prev_out;
- edge_item* _next_in;
- edge_item* _prev_in;
- };
-
- node_item* _add_node() {
- node_item* p=new node_item;
- p->id=node_id++;
- p->_first_out_edge=0;
- p->_last_out_edge=0;
- p->_first_in_edge=0;
- p->_last_in_edge=0;
- p->_prev_node=_last_node;
- p->_next_node=0;
- if (_last_node) _last_node->_next_node=p;
- _last_node=p;
- if (!_first_node) _first_node=p;
-
- ++_node_num;
- return p;
- }
-
- edge_item* _add_edge(node_item* _tail, node_item* _head) {
- edge_item* e=new edge_item;
- e->id=edge_id++;
- e->_tail=_tail;
- e->_head=_head;
-
- e->_prev_out=_tail->_last_out_edge;
- if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
- _tail->_last_out_edge=e;
- if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
- e->_next_out=0;
-
- e->_prev_in=_head->_last_in_edge;
- if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
- _head->_last_in_edge=e;
- if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
- e->_next_in=0;
-
- ++_edge_num;
- return e;
- }
-
- //deletes a node which has no out edge and no in edge
- void _delete_node(node_item* v) {
- if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else
- _last_node=v->_prev_node;
- if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else
- _first_node=v->_next_node;
-
- delete v;
- --_node_num;
- }
-
- void _delete_edge(edge_item* e) {
- if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
- (e->_tail)->_last_out_edge=e->_prev_out;
- if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
- (e->_tail)->_first_out_edge=e->_next_out;
- if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
- (e->_head)->_last_in_edge=e->_prev_in;
- if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
- (e->_head)->_first_in_edge=e->_next_in;
-
- delete e;
- --_edge_num;
- }
-
- void _set_tail(edge_item* e, node_item* _tail) {
- if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
- (e->_tail)->_last_out_edge=e->_prev_out;
- if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
- (e->_tail)->_first_out_edge=e->_next_out;
-
- e->_tail=_tail;
-
- e->_prev_out=_tail->_last_out_edge;
- if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
- _tail->_last_out_edge=e;
- if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
- e->_next_out=0;
- }
-
- void _set_head(edge_item* e, node_item* _head) {
- if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
- (e->_head)->_last_in_edge=e->_prev_in;
- if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
- (e->_head)->_first_in_edge=e->_next_in;
-
- e->_head=_head;
-
- e->_prev_in=_head->_last_in_edge;
- if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
- _head->_last_in_edge=e;
- if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
- e->_next_in=0;
- }
-
- public:
-
- /* default constructor */
-
- ListGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
-
- ~ListGraph() {
- NodeIt n;
- while (this->valid(first(n))) erase(n);
- //while (first<NodeIt>().valid()) erase(first<NodeIt>());
- }
-
- int nodeNum() const { return _node_num; }
- int edgeNum() const { return _edge_num; }
-
- /* functions to construct iterators from the graph, or from each other */
-
- //NodeIt firstNode() const { return NodeIt(*this); }
- //EdgeIt firstEdge() const { return EdgeIt(*this); }
-
- //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); }
- //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); }
- //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); }
- Node tail(Edge e) const { return e.tailNode(); }
- Node head(Edge e) const { return e.headNode(); }
-
- Node aNode(const OutEdgeIt& e) const { return e.aNode(); }
- Node aNode(const InEdgeIt& e) const { return e.aNode(); }
- Node aNode(const SymEdgeIt& e) const { return e.aNode(); }
-
- Node bNode(const OutEdgeIt& e) const { return e.bNode(); }
- Node bNode(const InEdgeIt& e) const { return e.bNode(); }
- Node bNode(const SymEdgeIt& e) const { return e.bNode(); }
-
- //Node invalid_node() { return Node(); }
- //Edge invalid_edge() { return Edge(); }
- //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); }
- //InEdgeIt invalid_in_edge() { return InEdgeIt(); }
- //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); }
-
- /* same methods in other style */
- /* for experimental purpose */
-
- NodeIt& first(NodeIt& v) const {
- v=NodeIt(*this); return v; }
- EdgeIt& first(EdgeIt& e) const {
- e=EdgeIt(*this); return e; }
- OutEdgeIt& first(OutEdgeIt& e, Node v) const {
- e=OutEdgeIt(*this, v); return e; }
- InEdgeIt& first(InEdgeIt& e, Node v) const {
- e=InEdgeIt(*this, v); return e; }
- SymEdgeIt& first(SymEdgeIt& e, Node v) const {
- e=SymEdgeIt(*this, v); return e; }
- //void getTail(Node& n, const Edge& e) const { n=tail(e); }
- //void getHead(Node& n, const Edge& e) const { n=head(e); }
-
- //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); }
- //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); }
- //void getANode(Node& n, const SymEdgeIt& e) const { n=e.aNode(); }
- //void getBNode(Node& n, const OutEdgeIt& e) const { n=e.bNode(); }
- //void getBNode(Node& n, const InEdgeIt& e) const { n=e.bNode(); }
- //void getBNode(Node& n, const SymEdgeIt& e) const { n=e.bNode(); }
- //void get_invalid(Node& n) { n=Node(); }
- //void get_invalid(Edge& e) { e=Edge(); }
- //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }
- //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }
- //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
-
-// template< typename It >
-// It first() const {
-// It e;
-// first(e);
-// return e;
-// }
-
-// template< typename It >
-// It first(Node v) const {
-// It e;
-// first(e, v);
-// return e;
-// }
-
- bool valid(Node n) const { return n.valid(); }
- bool valid(Edge e) const { return e.valid(); }
-
-// template <typename It> It getNext(It it) const {
-// It tmp(it); next(tmp); return tmp; }
-// NodeIt& next(NodeIt& it) const { return ++it; }
-// EdgeIt& next(EdgeIt& it) const { return ++it; }
-// OutEdgeIt& next(OutEdgeIt& it) const { return ++it; }
-// InEdgeIt& next(InEdgeIt& it) const { return ++it; }
-// SymEdgeIt& next(SymEdgeIt& it) const { return ++it; }
-// template <typename It> It& next(It& it) const { return ++it; }
- template <typename It> It& next(It& it) const { ++it; return it; }
-
-
- /* for getting id's of graph objects */
- /* these are important for the implementation of property vectors */
-
- int id(Node v) const { return v.node->id; }
- int id(Edge e) const { return e.edge->id; }
-
- /* adding nodes and edges */
-
- Node addNode() { return Node(_add_node()); }
- Edge addEdge(Node u, Node v) {
- return Edge(_add_edge(u.node, v.node));
- }
-
- void erase(Node i) {
- {
- OutEdgeIt e;
- while (this->valid(first(e, i))) erase(e);
- }
- {
- InEdgeIt e;
- while (this->valid(first(e, i))) erase(e);
- }
- //while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
- //while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
- _delete_node(i.node);
- }
-
- void erase(Edge e) { _delete_edge(e.edge); }
-
- void clear() {
- NodeIt e;
- while (this->valid(first(e))) erase(e);
- //while (first<NodeIt>().valid()) erase(first<NodeIt>());
- }
-
- void setTail(Edge e, Node tail) {
- _set_tail(e.edge, tail.node);
- }
-
- void setHead(Edge e, Node head) {
- _set_head(e.edge, head.node);
- }
-
- /* stream operations, for testing purpose */
-
-// friend std::ostream& operator<<(std::ostream& os, const Node& i) {
-// if (i.valid())
-// os << i.node->id;
-// else
-// os << "invalid";
-// return os;
-// }
-// friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
-// if (i.valid())
-// os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
-// else
-// os << "invalid";
-// return os;
-// }
-
- class Node {
- friend class ListGraph;
- template <typename T> friend class NodeMap;
-
- friend class Edge;
- friend class OutEdgeIt;
- friend class InEdgeIt;
- friend class SymEdgeIt;
- //public: //FIXME: It is required by op= of NodeIt
- protected:
- node_item* node;
- protected:
- friend int ListGraph::id(Node v) const;
- public:
- Node() /*: node(0)*/ { }
- Node(const Invalid&) : node(0) { }
- protected:
- Node(node_item* _node) : node(_node) { }
- bool valid() const { return (node); }
- public:
- //void makeInvalid() { node=0; }
- friend bool operator==(Node u, Node v) { return v.node==u.node; }
- friend bool operator!=(Node u, Node v) { return v.node!=u.node; }
- friend std::ostream& operator<<(std::ostream& os, const Node& i);
- };
-
- class NodeIt : public Node {
- friend class ListGraph;
- //protected:
- public: //for everybody but marci
- NodeIt(const ListGraph& G) : Node(G._first_node) { }
- public:
- NodeIt() : Node() { }
- NodeIt(const Invalid& i) : Node(i) { }
- protected:
- NodeIt(node_item* v) : Node(v) { }
- NodeIt& operator++() { node=node->_next_node; return *this; }
- //FIXME::
- // NodeIt& operator=(const Node& e)
- // { node=e.node; return *this; }
- };
-
- class Edge {
- friend class ListGraph;
- template <typename T> friend class EdgeMap;
-
- friend class Node;
- friend class NodeIt;
- protected:
- edge_item* edge;
- friend int ListGraph::id(Edge e) const;
- public:
- Edge() /*: edge(0)*/ { }
- Edge(const Invalid&) : edge(0) { }
- //Edge() { }
- protected:
- Edge(edge_item* _edge) : edge(_edge) { }
- bool valid() const { return (edge); }
- public:
- //void makeInvalid() { edge=0; }
- friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; }
- friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; }
- protected:
- Node tailNode() const { return Node(edge->_tail); }
- Node headNode() const { return Node(edge->_head); }
- public:
- friend std::ostream& operator<<(std::ostream& os, const Edge& i);
- };
-
- class EdgeIt : public Edge {
- friend class ListGraph;
- //protected:
- public: //for alpar
- EdgeIt(const ListGraph& G) {
- node_item* v=G._first_node;
- if (v) edge=v->_first_out_edge; else edge=0;
- while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
- }
- public:
- EdgeIt() : Edge() { }
- EdgeIt(const Invalid& i) : Edge(i) { }
- protected:
- EdgeIt(edge_item* _e) : Edge(_e) { }
- EdgeIt& operator++() {
- node_item* v=edge->_tail;
- edge=edge->_next_out;
- while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
- return *this;
- }
- };
-
- class OutEdgeIt : public Edge {
- friend class ListGraph;
- //node_item* v;
- //protected:
- protected: //for alpar
- OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
- public:
- OutEdgeIt() : Edge()/*, v(0)*/ { }
- OutEdgeIt(const Invalid& i) : Edge(i) { }
- OutEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
- protected:
- OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
- protected:
- Node aNode() const { return Node(edge->_tail); }
- Node bNode() const { return Node(edge->_head); }
- };
-
- class InEdgeIt : public Edge {
- friend class ListGraph;
- //node_item* v;
- //protected:
- protected: //for alpar
- InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
- public:
- InEdgeIt() : Edge()/*, v(0)*/ { }
- InEdgeIt(const Invalid& i) : Edge(i) { }
- InEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
- protected:
- InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
- protected:
- Node aNode() const { return Node(edge->_head); }
- Node bNode() const { return Node(edge->_tail); }
- };
-
- class SymEdgeIt : public Edge {
- friend class ListGraph;
- bool out_or_in; //1 iff out, 0 iff in
- //node_item* v;
- //protected:
- protected: //for alpar
- SymEdgeIt(const Node& _v) /*: v(_v.node)*/ {
- out_or_in=1;
- edge=_v.node->_first_out_edge;
- if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
- }
- public:
- SymEdgeIt() : Edge() /*, v(0)*/ { }
- SymEdgeIt(const Invalid& i) : Edge(i) { }
- SymEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ {
- out_or_in=1;
- edge=_v.node->_first_out_edge;
- if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
- }
- protected:
- SymEdgeIt& operator++() {
- if (out_or_in) {
- node_item* v=edge->_tail;
- edge=edge->_next_out;
- if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
- } else {
- edge=edge->_next_in;
- }
- return *this;
- }
- protected:
- Node aNode() const {
- return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); }
- Node bNode() const {
- return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); }
- };
- };
-
- inline
- std::ostream& operator<<(std::ostream& os, const ListGraph::Node& i) {
- if (i.valid())
- os << i.node->id;
- else
- os << "invalid";
- return os;
- }
-
- inline
- std::ostream& operator<<(std::ostream& os, const ListGraph::Edge& i) {
- if (i.valid())
- os << "(" << i.tailNode() << "--" << i.edge->id << "->"
- << i.headNode() << ")";
- else
- os << "invalid";
- return os;
- }
-
- class UndirListGraph : public ListGraph {
- public:
- typedef SymEdgeIt OutEdgeIt;
- typedef SymEdgeIt InEdgeIt;
- };
-
-} //namespace hugo
-
-#endif //HUGO_LIST_GRAPH_H
diff -r bfd6c14e2975 -r e812963087f0 src/work/marci/bfsit_vs_byhand.cc
--- a/src/work/marci/bfsit_vs_byhand.cc Fri May 14 18:08:29 2004 +0000
+++ b/src/work/marci/bfsit_vs_byhand.cc Fri May 14 18:28:57 2004 +0000
@@ -2,7 +2,7 @@
#include <iostream>
#include <fstream>
-#include <list_graph.h>
+#include <sage_graph.h>
//#include <smart_graph.h>
#include <hugo/dimacs.h>
#include <hugo/time_measure.h>
@@ -12,7 +12,7 @@
using namespace hugo;
int main() {
- typedef ListGraph Graph;
+ typedef SageGraph Graph;
typedef Graph::Node Node;
typedef Graph::NodeIt NodeIt;
typedef Graph::Edge Edge;
diff -r bfd6c14e2975 -r e812963087f0 src/work/marci/bipartite_graph_wrapper_test.cc
--- a/src/work/marci/bipartite_graph_wrapper_test.cc Fri May 14 18:08:29 2004 +0000
+++ b/src/work/marci/bipartite_graph_wrapper_test.cc Fri May 14 18:28:57 2004 +0000
@@ -3,7 +3,7 @@
#include <fstream>
#include <vector>
-#include <list_graph.h>
+#include <sage_graph.h>
//#include <smart_graph.h>
//#include <dimacs.h>
#include <hugo/time_measure.h>
@@ -17,7 +17,7 @@
using namespace hugo;
int main() {
- typedef UndirListGraph Graph;
+ typedef UndirSageGraph Graph;
typedef Graph::Node Node;
typedef Graph::NodeIt NodeIt;
typedef Graph::Edge Edge;
diff -r bfd6c14e2975 -r e812963087f0 src/work/marci/bipartite_matching_try.cc
--- a/src/work/marci/bipartite_matching_try.cc Fri May 14 18:08:29 2004 +0000
+++ b/src/work/marci/bipartite_matching_try.cc Fri May 14 18:28:57 2004 +0000
@@ -4,7 +4,7 @@
#include <vector>
#include <cstdlib>
-#include <list_graph.h>
+#include <sage_graph.h>
//#include <smart_graph.h>
//#include <dimacs.h>
#include <hugo/time_measure.h>
@@ -40,7 +40,7 @@
using namespace hugo;
int main() {
- typedef UndirListGraph Graph;
+ typedef UndirSageGraph Graph;
typedef Graph::Node Node;
typedef Graph::NodeIt NodeIt;
typedef Graph::Edge Edge;
@@ -166,7 +166,7 @@
MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
// while (max_flow_test.augmentOnShortestPath()) { }
- typedef ListGraph MutableGraph;
+ typedef SageGraph MutableGraph;
// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
while (max_flow_test.augmentOnBlockingFlow2()) {
std::cout << max_flow_test.flowValue() << std::endl;
diff -r bfd6c14e2975 -r e812963087f0 src/work/marci/bipartite_matching_try_3.cc
--- a/src/work/marci/bipartite_matching_try_3.cc Fri May 14 18:08:29 2004 +0000
+++ b/src/work/marci/bipartite_matching_try_3.cc Fri May 14 18:28:57 2004 +0000
@@ -3,7 +3,7 @@
#include <fstream>
#include <vector>
-#include <list_graph.h>
+#include <sage_graph.h>
//#include <smart_graph.h>
//#include <dimacs.h>
#include <hugo/time_measure.h>
@@ -19,7 +19,7 @@
int main() {
//typedef UndirListGraph Graph;
- typedef BipartiteGraph<ListGraph> Graph;
+ typedef BipartiteGraph<SageGraph> Graph;
typedef Graph::Node Node;
typedef Graph::NodeIt NodeIt;
diff -r bfd6c14e2975 -r e812963087f0 src/work/marci/iterator_bfs_demo.cc
--- a/src/work/marci/iterator_bfs_demo.cc Fri May 14 18:08:29 2004 +0000
+++ b/src/work/marci/iterator_bfs_demo.cc Fri May 14 18:28:57 2004 +0000
@@ -3,7 +3,7 @@
#include <vector>
#include <string>
-#include <list_graph.h>
+#include <sage_graph.h>
//#include <smart_graph.h>
#include <bfs_dfs.h>
#include <hugo/graph_wrapper.h>
@@ -29,7 +29,7 @@
int main (int, char*[])
{
//typedef SmartGraph Graph;
- typedef ListGraph Graph;
+ typedef SageGraph Graph;
typedef Graph::Node Node;
typedef Graph::Edge Edge;
diff -r bfd6c14e2975 -r e812963087f0 src/work/marci/lg_vs_sg.cc
--- a/src/work/marci/lg_vs_sg.cc Fri May 14 18:08:29 2004 +0000
+++ b/src/work/marci/lg_vs_sg.cc Fri May 14 18:28:57 2004 +0000
@@ -3,7 +3,8 @@
#include <fstream>
#include <string>
-#include <list_graph.h>
+#include <sage_graph.h>
+#include <hugo/list_graph.h>
#include <hugo/smart_graph.h>
#include <hugo/dimacs.h>
#include <max_flow.h>
@@ -18,10 +19,10 @@
int main(int, char** argv) {
std::string in=argv[1];
- typedef ListGraph MutableGraph;
+ typedef SageGraph MutableGraph;
{
- typedef ListGraph Graph;
+ typedef SageGraph Graph;
typedef Graph::Node Node;
typedef Graph::EdgeIt EdgeIt;
@@ -37,7 +38,7 @@
MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
max_flow_test(g, s, t, cap, flow/*, true*/);
- std::cout << "ListGraph ..." << std::endl;
+ std::cout << "SageGraph ..." << std::endl;
{
std::cout << "preflow ..." << std::endl;
@@ -92,7 +93,6 @@
}
}
-
{
typedef SmartGraph Graph;
typedef Graph::Node Node;
@@ -112,7 +112,7 @@
// MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
// max_flow_test(g, s, t, cap, flow);
- std::cout << "SmatrGraph ..." << std::endl;
+ std::cout << "SmartGraph ..." << std::endl;
{
std::cout << "preflow ..." << std::endl;
@@ -168,6 +168,81 @@
}
}
+ {
+ typedef ListGraph Graph;
+ typedef Graph::Node Node;
+ typedef Graph::EdgeIt EdgeIt;
+
+ Graph g;
+ Node s, t;
+ Graph::EdgeMap<int> cap(g);
+ std::ifstream ins(in.c_str());
+ //readDimacsMaxFlow(ins, g, s, t, cap);
+ readDimacs(ins, g, cap, s, t);
+
+ Timer ts;
+ Graph::EdgeMap<int> flow(g); //0 flow
+ MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
+ max_flow_test(g, s, t, cap, flow/*, true*/);
+ // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
+ // max_flow_test(g, s, t, cap, flow);
+
+ std::cout << "ListGraph ..." << std::endl;
+
+ {
+ std::cout << "preflow ..." << std::endl;
+ FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ ts.reset();
+ max_flow_test.run();
+ std::cout << "elapsed time: " << ts << std::endl;
+ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+ }
+
+ {
+ std::cout << "physical blocking flow augmentation ..." << std::endl;
+ FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ ts.reset();
+ int i=0;
+ while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
+ std::cout << "elapsed time: " << ts << std::endl;
+ std::cout << "number of augmentation phases: " << i << std::endl;
+ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+ }
+
+// {
+// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
+// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+// ts.reset();
+// int i=0;
+// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
+// std::cout << "elapsed time: " << ts << std::endl;
+// std::cout << "number of augmentation phases: " << i << std::endl;
+// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+// }
+
+ {
+ std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
+ FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ ts.reset();
+ int i=0;
+ while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
+ std::cout << "elapsed time: " << ts << std::endl;
+ std::cout << "number of augmentation phases: " << i << std::endl;
+ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+ }
+
+ {
+ std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
+ FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ ts.reset();
+ int i=0;
+ while (max_flow_test.augmentOnShortestPath()) { ++i; }
+ std::cout << "elapsed time: " << ts << std::endl;
+ std::cout << "number of augmentation phases: " << i << std::endl;
+ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+ }
+ }
+
diff -r bfd6c14e2975 -r e812963087f0 src/work/marci/macro_test.cc
--- a/src/work/marci/macro_test.cc Fri May 14 18:08:29 2004 +0000
+++ b/src/work/marci/macro_test.cc Fri May 14 18:28:57 2004 +0000
@@ -2,14 +2,14 @@
#include <iostream>
#include <fstream>
-#include <list_graph.h>
+#include <sage_graph.h>
#include <hugo/for_each_macros.h>
using namespace hugo;
int main()
{
- typedef ListGraph Graph;
+ typedef SageGraph Graph;
Graph g;
Graph::Node n1=g.addNode();
Graph::Node n2=g.addNode();
diff -r bfd6c14e2975 -r e812963087f0 src/work/marci/max_bipartite_matching_demo.cc
--- a/src/work/marci/max_bipartite_matching_demo.cc Fri May 14 18:08:29 2004 +0000
+++ b/src/work/marci/max_bipartite_matching_demo.cc Fri May 14 18:28:57 2004 +0000
@@ -9,7 +9,7 @@
#include <LEDA/list.h>
#include <leda_graph_wrapper.h>
-#include <list_graph.h>
+#include <sage_graph.h>
#include <dimacs.h>
#include <time_measure.h>
#include <edmonds_karp.h>
diff -r bfd6c14e2975 -r e812963087f0 src/work/marci/max_flow_1.cc
--- a/src/work/marci/max_flow_1.cc Fri May 14 18:08:29 2004 +0000
+++ b/src/work/marci/max_flow_1.cc Fri May 14 18:28:57 2004 +0000
@@ -2,7 +2,7 @@
#include <iostream>
#include <fstream>
-#include <list_graph.h>
+#include <sage_graph.h>
#include <hugo/smart_graph.h>
#include <hugo/dimacs.h>
#include <hugo/time_measure.h>
@@ -19,7 +19,7 @@
int main(int, char **) {
- typedef ListGraph MutableGraph;
+ typedef SageGraph MutableGraph;
typedef SmartGraph Graph;
// typedef ListGraph Graph;
diff -r bfd6c14e2975 -r e812963087f0 src/work/marci/max_flow_demo.cc
--- a/src/work/marci/max_flow_demo.cc Fri May 14 18:08:29 2004 +0000
+++ b/src/work/marci/max_flow_demo.cc Fri May 14 18:28:57 2004 +0000
@@ -2,7 +2,7 @@
#include <iostream>
#include <fstream>
-#include <list_graph.h>
+#include <sage_graph.h>
#include <hugo/smart_graph.h>
#include <hugo/dimacs.h>
#include <hugo/time_measure.h>
@@ -34,10 +34,10 @@
int main(int, char **) {
- typedef ListGraph MutableGraph;
+ typedef SageGraph MutableGraph;
typedef SmartGraph Graph;
- // typedef ListGraph Graph;
+ // typedef SageGraph Graph;
typedef Graph::Node Node;
typedef Graph::EdgeIt EdgeIt;
diff -r bfd6c14e2975 -r e812963087f0 src/work/marci/top_sort_test.cc
--- a/src/work/marci/top_sort_test.cc Fri May 14 18:08:29 2004 +0000
+++ b/src/work/marci/top_sort_test.cc Fri May 14 18:28:57 2004 +0000
@@ -5,7 +5,7 @@
#include <hugo/dimacs.h>
#include <bfs_dfs_misc.h>
-#include <list_graph.h>
+#include <sage_graph.h>
#include <hugo/graph_wrapper.h>
#include <hugo/maps.h>
#include <hugo/for_each_macros.h>
@@ -16,7 +16,7 @@
using std::endl;
int main() {
- typedef ListGraph Graph;
+ typedef SageGraph Graph;
Graph g;
readDimacs(std::cin, g);
diff -r bfd6c14e2975 -r e812963087f0 src/work/sage_graph.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/sage_graph.h Fri May 14 18:28:57 2004 +0000
@@ -0,0 +1,547 @@
+// -*- c++ -*-
+#ifndef HUGO_SAGE_GRAPH_H
+#define HUGO_SAGE_GRAPH_H
+
+#include <iostream>
+#include <vector>
+
+#include <hugo/invalid.h>
+
+namespace hugo {
+
+ template <typename It>
+ int count(It it) {
+ int i=0;
+ for( ; it.valid(); ++it) { ++i; }
+ return i;
+ }
+
+ class SageGraph {
+ struct node_item;
+ struct edge_item;
+ public:
+ class Node;
+ class NodeIt;
+ class Edge;
+ class EdgeIt;
+ class OutEdgeIt;
+ class InEdgeIt;
+ class SymEdgeIt;
+ template <typename T> class NodeMap;
+ template <typename T> class EdgeMap;
+// private:
+ template <typename T> friend class NodeMap;
+ template <typename T> friend class EdgeMap;
+
+ template <typename T>
+ class NodeMap {
+ const SageGraph& G;
+ std::vector<T> container;
+ public:
+ typedef T ValueType;
+ typedef Node KeyType;
+ NodeMap(const SageGraph& _G) : G(_G), container(G.node_id) { }
+ NodeMap(const SageGraph& _G, T a) :
+ G(_G), container(G.node_id, a) { }
+ void set(Node n, T a) { container[/*G.id(n)*/n.node->id]=a; }
+// T get(Node n) const { return container[/*G.id(n)*/n.node->id]; }
+ typename std::vector<T>::reference operator[](Node n) {
+ return container[/*G.id(n)*/n.node->id]; }
+ typename std::vector<T>::const_reference operator[](Node n) const {
+ return container[/*G.id(n)*/n.node->id];
+ }
+ void update() { container.resize(G.node_id); }
+ void update(T a) { container.resize(G.node_id, a); }
+ };
+
+ template <typename T>
+ class EdgeMap {
+ const SageGraph& G;
+ std::vector<T> container;
+ public:
+ typedef T ValueType;
+ typedef Edge KeyType;
+ EdgeMap(const SageGraph& _G) : G(_G), container(G.edge_id) { }
+ EdgeMap(const SageGraph& _G, T a) :
+ G(_G), container(G.edge_id, a) { }
+ void set(Edge e, T a) { container[/*G.id(e)*/e.edge->id]=a; }
+// T get(Edge e) const { return container[/*G.id(e)*/e.edge->id]; }
+ typename std::vector<T>::reference operator[](Edge e) {
+ return container[/*G.id(e)*/e.edge->id]; }
+ typename std::vector<T>::const_reference operator[](Edge e) const {
+ return container[/*G.id(e)*/e.edge->id];
+ }
+ void update() { container.resize(G.edge_id); }
+ void update(T a) { container.resize(G.edge_id, a); }
+ };
+
+ private:
+ int node_id;
+ int edge_id;
+ int _node_num;
+ int _edge_num;
+
+ node_item* _first_node;
+ node_item* _last_node;
+
+ struct node_item {
+ int id;
+ edge_item* _first_out_edge;
+ edge_item* _last_out_edge;
+ edge_item* _first_in_edge;
+ edge_item* _last_in_edge;
+ node_item* _next_node;
+ node_item* _prev_node;
+ };
+
+ struct edge_item {
+ int id;
+ node_item* _tail;
+ node_item* _head;
+ edge_item* _next_out;
+ edge_item* _prev_out;
+ edge_item* _next_in;
+ edge_item* _prev_in;
+ };
+
+ node_item* _add_node() {
+ node_item* p=new node_item;
+ p->id=node_id++;
+ p->_first_out_edge=0;
+ p->_last_out_edge=0;
+ p->_first_in_edge=0;
+ p->_last_in_edge=0;
+ p->_prev_node=_last_node;
+ p->_next_node=0;
+ if (_last_node) _last_node->_next_node=p;
+ _last_node=p;
+ if (!_first_node) _first_node=p;
+
+ ++_node_num;
+ return p;
+ }
+
+ edge_item* _add_edge(node_item* _tail, node_item* _head) {
+ edge_item* e=new edge_item;
+ e->id=edge_id++;
+ e->_tail=_tail;
+ e->_head=_head;
+
+ e->_prev_out=_tail->_last_out_edge;
+ if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
+ _tail->_last_out_edge=e;
+ if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
+ e->_next_out=0;
+
+ e->_prev_in=_head->_last_in_edge;
+ if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
+ _head->_last_in_edge=e;
+ if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
+ e->_next_in=0;
+
+ ++_edge_num;
+ return e;
+ }
+
+ //deletes a node which has no out edge and no in edge
+ void _delete_node(node_item* v) {
+ if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else
+ _last_node=v->_prev_node;
+ if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else
+ _first_node=v->_next_node;
+
+ delete v;
+ --_node_num;
+ }
+
+ void _delete_edge(edge_item* e) {
+ if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
+ (e->_tail)->_last_out_edge=e->_prev_out;
+ if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
+ (e->_tail)->_first_out_edge=e->_next_out;
+ if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
+ (e->_head)->_last_in_edge=e->_prev_in;
+ if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
+ (e->_head)->_first_in_edge=e->_next_in;
+
+ delete e;
+ --_edge_num;
+ }
+
+ void _set_tail(edge_item* e, node_item* _tail) {
+ if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
+ (e->_tail)->_last_out_edge=e->_prev_out;
+ if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
+ (e->_tail)->_first_out_edge=e->_next_out;
+
+ e->_tail=_tail;
+
+ e->_prev_out=_tail->_last_out_edge;
+ if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
+ _tail->_last_out_edge=e;
+ if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
+ e->_next_out=0;
+ }
+
+ void _set_head(edge_item* e, node_item* _head) {
+ if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
+ (e->_head)->_last_in_edge=e->_prev_in;
+ if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
+ (e->_head)->_first_in_edge=e->_next_in;
+
+ e->_head=_head;
+
+ e->_prev_in=_head->_last_in_edge;
+ if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
+ _head->_last_in_edge=e;
+ if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
+ e->_next_in=0;
+ }
+
+ public:
+
+ /* default constructor */
+
+ SageGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
+
+ ~SageGraph() {
+ NodeIt n;
+ while (this->valid(first(n))) erase(n);
+ //while (first<NodeIt>().valid()) erase(first<NodeIt>());
+ }
+
+ int nodeNum() const { return _node_num; }
+ int edgeNum() const { return _edge_num; }
+
+ /* functions to construct iterators from the graph, or from each other */
+
+ //NodeIt firstNode() const { return NodeIt(*this); }
+ //EdgeIt firstEdge() const { return EdgeIt(*this); }
+
+ //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); }
+ //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); }
+ //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); }
+ Node tail(Edge e) const { return e.tailNode(); }
+ Node head(Edge e) const { return e.headNode(); }
+
+ Node aNode(const OutEdgeIt& e) const { return e.aNode(); }
+ Node aNode(const InEdgeIt& e) const { return e.aNode(); }
+ Node aNode(const SymEdgeIt& e) const { return e.aNode(); }
+
+ Node bNode(const OutEdgeIt& e) const { return e.bNode(); }
+ Node bNode(const InEdgeIt& e) const { return e.bNode(); }
+ Node bNode(const SymEdgeIt& e) const { return e.bNode(); }
+
+ //Node invalid_node() { return Node(); }
+ //Edge invalid_edge() { return Edge(); }
+ //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); }
+ //InEdgeIt invalid_in_edge() { return InEdgeIt(); }
+ //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); }
+
+ /* same methods in other style */
+ /* for experimental purpose */
+
+ NodeIt& first(NodeIt& v) const {
+ v=NodeIt(*this); return v; }
+ EdgeIt& first(EdgeIt& e) const {
+ e=EdgeIt(*this); return e; }
+ OutEdgeIt& first(OutEdgeIt& e, Node v) const {
+ e=OutEdgeIt(*this, v); return e; }
+ InEdgeIt& first(InEdgeIt& e, Node v) const {
+ e=InEdgeIt(*this, v); return e; }
+ SymEdgeIt& first(SymEdgeIt& e, Node v) const {
+ e=SymEdgeIt(*this, v); return e; }
+ //void getTail(Node& n, const Edge& e) const { n=tail(e); }
+ //void getHead(Node& n, const Edge& e) const { n=head(e); }
+
+ //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); }
+ //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); }
+ //void getANode(Node& n, const SymEdgeIt& e) const { n=e.aNode(); }
+ //void getBNode(Node& n, const OutEdgeIt& e) const { n=e.bNode(); }
+ //void getBNode(Node& n, const InEdgeIt& e) const { n=e.bNode(); }
+ //void getBNode(Node& n, const SymEdgeIt& e) const { n=e.bNode(); }
+ //void get_invalid(Node& n) { n=Node(); }
+ //void get_invalid(Edge& e) { e=Edge(); }
+ //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }
+ //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }
+ //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
+
+// template< typename It >
+// It first() const {
+// It e;
+// first(e);
+// return e;
+// }
+
+// template< typename It >
+// It first(Node v) const {
+// It e;
+// first(e, v);
+// return e;
+// }
+
+ bool valid(Node n) const { return n.valid(); }
+ bool valid(Edge e) const { return e.valid(); }
+
+// template <typename It> It getNext(It it) const {
+// It tmp(it); next(tmp); return tmp; }
+// NodeIt& next(NodeIt& it) const { return ++it; }
+// EdgeIt& next(EdgeIt& it) const { return ++it; }
+// OutEdgeIt& next(OutEdgeIt& it) const { return ++it; }
+// InEdgeIt& next(InEdgeIt& it) const { return ++it; }
+// SymEdgeIt& next(SymEdgeIt& it) const { return ++it; }
+// template <typename It> It& next(It& it) const { return ++it; }
+ template <typename It> It& next(It& it) const { ++it; return it; }
+
+
+ /* for getting id's of graph objects */
+ /* these are important for the implementation of property vectors */
+
+ int id(Node v) const { return v.node->id; }
+ int id(Edge e) const { return e.edge->id; }
+
+ /* adding nodes and edges */
+
+ Node addNode() { return Node(_add_node()); }
+ Edge addEdge(Node u, Node v) {
+ return Edge(_add_edge(u.node, v.node));
+ }
+
+ void erase(Node i) {
+ {
+ OutEdgeIt e;
+ while (this->valid(first(e, i))) erase(e);
+ }
+ {
+ InEdgeIt e;
+ while (this->valid(first(e, i))) erase(e);
+ }
+ //while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
+ //while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
+ _delete_node(i.node);
+ }
+
+ void erase(Edge e) { _delete_edge(e.edge); }
+
+ void clear() {
+ NodeIt e;
+ while (this->valid(first(e))) erase(e);
+ //while (first<NodeIt>().valid()) erase(first<NodeIt>());
+ }
+
+ void setTail(Edge e, Node tail) {
+ _set_tail(e.edge, tail.node);
+ }
+
+ void setHead(Edge e, Node head) {
+ _set_head(e.edge, head.node);
+ }
+
+ /* stream operations, for testing purpose */
+
+// friend std::ostream& operator<<(std::ostream& os, const Node& i) {
+// if (i.valid())
+// os << i.node->id;
+// else
+// os << "invalid";
+// return os;
+// }
+// friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
+// if (i.valid())
+// os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
+// else
+// os << "invalid";
+// return os;
+// }
+
+ class Node {
+ friend class SageGraph;
+ template <typename T> friend class NodeMap;
+
+ friend class Edge;
+ friend class OutEdgeIt;
+ friend class InEdgeIt;
+ friend class SymEdgeIt;
+ //public: //FIXME: It is required by op= of NodeIt
+ protected:
+ node_item* node;
+ protected:
+ friend int SageGraph::id(Node v) const;
+ public:
+ Node() /*: node(0)*/ { }
+ Node(const Invalid&) : node(0) { }
+ protected:
+ Node(node_item* _node) : node(_node) { }
+ bool valid() const { return (node); }
+ public:
+ //void makeInvalid() { node=0; }
+ friend bool operator==(Node u, Node v) { return v.node==u.node; }
+ friend bool operator!=(Node u, Node v) { return v.node!=u.node; }
+ friend std::ostream& operator<<(std::ostream& os, const Node& i);
+ };
+
+ class NodeIt : public Node {
+ friend class SageGraph;
+ //protected:
+ public: //for everybody but marci
+ NodeIt(const SageGraph& G) : Node(G._first_node) { }
+ public:
+ NodeIt() : Node() { }
+ NodeIt(const Invalid& i) : Node(i) { }
+ protected:
+ NodeIt(node_item* v) : Node(v) { }
+ NodeIt& operator++() { node=node->_next_node; return *this; }
+ //FIXME::
+ // NodeIt& operator=(const Node& e)
+ // { node=e.node; return *this; }
+ };
+
+ class Edge {
+ friend class SageGraph;
+ template <typename T> friend class EdgeMap;
+
+ friend class Node;
+ friend class NodeIt;
+ protected:
+ edge_item* edge;
+ friend int SageGraph::id(Edge e) const;
+ public:
+ Edge() /*: edge(0)*/ { }
+ Edge(const Invalid&) : edge(0) { }
+ //Edge() { }
+ protected:
+ Edge(edge_item* _edge) : edge(_edge) { }
+ bool valid() const { return (edge); }
+ public:
+ //void makeInvalid() { edge=0; }
+ friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; }
+ friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; }
+ protected:
+ Node tailNode() const { return Node(edge->_tail); }
+ Node headNode() const { return Node(edge->_head); }
+ public:
+ friend std::ostream& operator<<(std::ostream& os, const Edge& i);
+ };
+
+ class EdgeIt : public Edge {
+ friend class SageGraph;
+ //protected:
+ public: //for alpar
+ EdgeIt(const SageGraph& G) {
+ node_item* v=G._first_node;
+ if (v) edge=v->_first_out_edge; else edge=0;
+ while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
+ }
+ public:
+ EdgeIt() : Edge() { }
+ EdgeIt(const Invalid& i) : Edge(i) { }
+ protected:
+ EdgeIt(edge_item* _e) : Edge(_e) { }
+ EdgeIt& operator++() {
+ node_item* v=edge->_tail;
+ edge=edge->_next_out;
+ while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
+ return *this;
+ }
+ };
+
+ class OutEdgeIt : public Edge {
+ friend class SageGraph;
+ //node_item* v;
+ //protected:
+ protected: //for alpar
+ OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
+ public:
+ OutEdgeIt() : Edge()/*, v(0)*/ { }
+ OutEdgeIt(const Invalid& i) : Edge(i) { }
+ OutEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
+ protected:
+ OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
+ protected:
+ Node aNode() const { return Node(edge->_tail); }
+ Node bNode() const { return Node(edge->_head); }
+ };
+
+ class InEdgeIt : public Edge {
+ friend class SageGraph;
+ //node_item* v;
+ //protected:
+ protected: //for alpar
+ InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
+ public:
+ InEdgeIt() : Edge()/*, v(0)*/ { }
+ InEdgeIt(const Invalid& i) : Edge(i) { }
+ InEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
+ protected:
+ InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
+ protected:
+ Node aNode() const { return Node(edge->_head); }
+ Node bNode() const { return Node(edge->_tail); }
+ };
+
+ class SymEdgeIt : public Edge {
+ friend class SageGraph;
+ bool out_or_in; //1 iff out, 0 iff in
+ //node_item* v;
+ //protected:
+ protected: //for alpar
+ SymEdgeIt(const Node& _v) /*: v(_v.node)*/ {
+ out_or_in=1;
+ edge=_v.node->_first_out_edge;
+ if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
+ }
+ public:
+ SymEdgeIt() : Edge() /*, v(0)*/ { }
+ SymEdgeIt(const Invalid& i) : Edge(i) { }
+ SymEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ {
+ out_or_in=1;
+ edge=_v.node->_first_out_edge;
+ if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
+ }
+ protected:
+ SymEdgeIt& operator++() {
+ if (out_or_in) {
+ node_item* v=edge->_tail;
+ edge=edge->_next_out;
+ if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
+ } else {
+ edge=edge->_next_in;
+ }
+ return *this;
+ }
+ protected:
+ Node aNode() const {
+ return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); }
+ Node bNode() const {
+ return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); }
+ };
+ };
+
+ inline
+ std::ostream& operator<<(std::ostream& os, const SageGraph::Node& i) {
+ if (i.valid())
+ os << i.node->id;
+ else
+ os << "invalid";
+ return os;
+ }
+
+ inline
+ std::ostream& operator<<(std::ostream& os, const SageGraph::Edge& i) {
+ if (i.valid())
+ os << "(" << i.tailNode() << "--" << i.edge->id << "->"
+ << i.headNode() << ")";
+ else
+ os << "invalid";
+ return os;
+ }
+
+ class UndirSageGraph : public SageGraph {
+ public:
+ typedef SymEdgeIt OutEdgeIt;
+ typedef SymEdgeIt InEdgeIt;
+ };
+
+} //namespace hugo
+
+#endif //HUGO_SAGE_GRAPH_H