# HG changeset patch
# User marci
# Date 1093974862 0
# Node ID a82713ed19f37c8b6c2c0a7bd9305e385606f7af
# Parent f2994a2b10b2f44327a4e0dfd0cf639069d27917
graph_wrapper.h is ready for hugo 0.2
diff -r f2994a2b10b2 -r a82713ed19f3 src/hugo/graph_wrapper.h
--- a/src/hugo/graph_wrapper.h Tue Aug 31 13:40:07 2004 +0000
+++ b/src/hugo/graph_wrapper.h Tue Aug 31 17:54:22 2004 +0000
@@ -181,7 +181,7 @@
EdgeIt(const GraphWrapper<Graph>& _gw) :
Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
- Edge(w), gw(&_gw) { }
+ Edge(e), gw(&_gw) { }
EdgeIt& operator++() {
*(static_cast<Edge*>(this))=
++(typename Graph::EdgeIt(*(gw->graph), *this));
@@ -428,7 +428,7 @@
// OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
OutEdgeIt(Invalid i) : Edge(i) { }
OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
- Edge(typename Graph::OutEdgeIt(*(_gw.graph)), n), gw(&_gw) { }
+ Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
const Edge& e) :
Edge(e), gw(&_gw) { }
@@ -450,7 +450,7 @@
// InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
InEdgeIt(Invalid i) : Edge(i) { }
InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
- Edge(typename Graph::InEdgeIt(*(_gw.graph)), n), gw(&_gw) { }
+ Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
const Edge& e) :
Edge(e), gw(&_gw) { }
@@ -2040,48 +2040,54 @@
// operator Node() const { return Node(typename Graph::Node(n)); }
// };
typedef typename GraphWrapper<Graph>::Edge Edge;
- class OutEdgeIt {
+ class OutEdgeIt : public Edge {
friend class GraphWrapper<Graph>;
friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
-// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
- typename Graph::OutEdgeIt e;
+ const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
public:
OutEdgeIt() { }
- OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
- OutEdgeIt(const Invalid& i) : e(i) { }
- OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
- const Node& _n) :
- e((*_G.first_out_edges)[_n]) { }
- operator Edge() const { return Edge(typename Graph::Edge(e)); }
+ //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
+ OutEdgeIt(Invalid i) : Edge(i) { }
+ OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
+ const Node& n) :
+ Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
+ OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
+ const Edge& e) :
+ Edge(e), gw(&_gw) { }
+ OutEdgeIt& operator++() {
+ *(static_cast<Edge*>(this))=
+ ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
+ return *this;
+ }
};
- class InEdgeIt {
- friend class GraphWrapper<Graph>;
- friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
-// typedef typename Graph::InEdgeIt GraphInEdgeIt;
- typename Graph::InEdgeIt e;
- public:
- InEdgeIt() { }
- InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
- InEdgeIt(const Invalid& i) : e(i) { }
- InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
- const Node& _n) :
- e(*(_G.graph), typename Graph::Node(_n)) { }
- operator Edge() const { return Edge(typename Graph::Edge(e)); }
- };
+// class InEdgeIt {
+// friend class GraphWrapper<Graph>;
+// friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
+// // typedef typename Graph::InEdgeIt GraphInEdgeIt;
+// typename Graph::InEdgeIt e;
+// public:
+// InEdgeIt() { }
+// InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
+// InEdgeIt(const Invalid& i) : e(i) { }
+// InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
+// const Node& _n) :
+// e(*(_G.graph), typename Graph::Node(_n)) { }
+// operator Edge() const { return Edge(typename Graph::Edge(e)); }
+// };
//typedef typename Graph::SymEdgeIt SymEdgeIt;
- class EdgeIt {
- friend class GraphWrapper<Graph>;
- friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
-// typedef typename Graph::EdgeIt GraphEdgeIt;
- typename Graph::EdgeIt e;
- public:
- EdgeIt() { }
- EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
- EdgeIt(const Invalid& i) : e(i) { }
- EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
- e(*(_G.graph)) { }
- operator Edge() const { return Edge(typename Graph::Edge(e)); }
- };
+// class EdgeIt {
+// friend class GraphWrapper<Graph>;
+// friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
+// // typedef typename Graph::EdgeIt GraphEdgeIt;
+// typename Graph::EdgeIt e;
+// public:
+// EdgeIt() { }
+// EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
+// EdgeIt(const Invalid& i) : e(i) { }
+// EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
+// e(*(_G.graph)) { }
+// operator Edge() const { return Edge(typename Graph::Edge(e)); }
+// };
using GraphWrapper<Graph>::first;
// NodeIt& first(NodeIt& i) const {
@@ -2090,32 +2096,33 @@
OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
i=OutEdgeIt(*this, p); return i;
}
- InEdgeIt& first(InEdgeIt& i, const Node& p) const {
- i=InEdgeIt(*this, p); return i;
- }
- EdgeIt& first(EdgeIt& i) const {
- i=EdgeIt(*this); return i;
- }
+// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
+// i=InEdgeIt(*this, p); return i;
+// }
+// EdgeIt& first(EdgeIt& i) const {
+// i=EdgeIt(*this); return i;
+// }
- using GraphWrapper<Graph>::next;
-// NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
- OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
- InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
- EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
+// using GraphWrapper<Graph>::next;
+// // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
+// OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
+// InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
+// EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
- Node aNode(const OutEdgeIt& e) const {
- return Node(this->graph->aNode(e.e)); }
- Node aNode(const InEdgeIt& e) const {
- return Node(this->graph->aNode(e.e)); }
- Node bNode(const OutEdgeIt& e) const {
- return Node(this->graph->bNode(e.e)); }
- Node bNode(const InEdgeIt& e) const {
- return Node(this->graph->bNode(e.e)); }
+// Node aNode(const OutEdgeIt& e) const {
+// return Node(this->graph->aNode(e.e)); }
+// Node aNode(const InEdgeIt& e) const {
+// return Node(this->graph->aNode(e.e)); }
+// Node bNode(const OutEdgeIt& e) const {
+// return Node(this->graph->bNode(e.e)); }
+// Node bNode(const InEdgeIt& e) const {
+// return Node(this->graph->bNode(e.e)); }
- void erase(const OutEdgeIt& e) const {
- OutEdgeIt f=e;
- this->next(f);
- first_out_edges->set(this->tail(e), f.e);
+ void erase(const Edge& e) const {
+ Node n=tail(e);
+ typename Graph::OutEdgeIt f(*graph, n);
+ ++f;
+ first_out_edges->set(n, f);
}
};
diff -r f2994a2b10b2 -r a82713ed19f3 src/work/marci/augmenting_flow.h
--- a/src/work/marci/augmenting_flow.h Tue Aug 31 13:40:07 2004 +0000
+++ b/src/work/marci/augmenting_flow.h Tue Aug 31 17:54:22 2004 +0000
@@ -11,7 +11,7 @@
#include <bfs_dfs.h>
#include <hugo/invalid.h>
#include <hugo/maps.h>
-#include <for_each_macros.h>
+//#include <for_each_macros.h>
/// \file
/// \brief Maximum flow algorithms.
@@ -1082,8 +1082,8 @@
Num flowValue() const {
Num a=0;
- FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e];
- FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e];
+ for (InEdgeIt e(*g, t); e!=INVALID; ++e) a+=(*flow)[e];
+ for (OutEdgeIt e(*g, t); e!=INVALID; ++e) a-=(*flow)[e];
return a;
//marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan
}
@@ -1121,7 +1121,7 @@
bool _augment=false;
//ReachedMap level(res_graph);
- FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+ for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
bfs.pushAndSetReached(s);
@@ -1132,7 +1132,7 @@
//searching for augmenting path
while ( !bfs.finished() ) {
- ResGWOutEdgeIt e=bfs;
+ ResGWEdge e=bfs;
if (e!=INVALID && bfs.isBNodeNewlyReached()) {
Node v=res_graph.tail(e);
Node w=res_graph.head(e);
@@ -1169,7 +1169,7 @@
bool _augment=false;
if (status!=AFTER_FAST_AUGMENTING) {
- FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+ for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
number_of_augmentations=1;
} else {
++number_of_augmentations;
@@ -1189,7 +1189,7 @@
//searching for augmenting path
while ( !bfs.finished() ) {
- ResGWOutEdgeIt e=bfs;
+ ResGWEdge e=bfs;
if (e!=INVALID && bfs.isBNodeNewlyReached()) {
Node v=res_graph.tail(e);
Node w=res_graph.head(e);
@@ -1231,7 +1231,7 @@
//bfs for distances on the residual graph
//ReachedMap level(res_graph);
- FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+ for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
bfs.pushAndSetReached(s);
typename ResGW::template NodeMap<int>
@@ -1255,7 +1255,7 @@
typename MG::template EdgeMap<Num> residual_capacity(F);
while ( !bfs.finished() ) {
- ResGWOutEdgeIt e=bfs;
+ ResGWEdge e=bfs;
if (e!=INVALID) {
if (bfs.isBNodeNewlyReached()) {
dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
@@ -1296,8 +1296,8 @@
++dfs;
if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
if (dfs.isBNodeNewlyReached()) {
- typename MG::Node v=F.aNode(dfs);
- typename MG::Node w=F.bNode(dfs);
+ typename MG::Node v=F.tail(dfs);
+ typename MG::Node w=F.head(dfs);
pred.set(w, dfs);
if (pred[v]!=INVALID) {
free.set(w, std::min(free[v], residual_capacity[dfs]));
@@ -1345,20 +1345,20 @@
ResGW res_graph(*g, *capacity, *flow);
//ReachedMap level(res_graph);
- FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+ for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
bfs.pushAndSetReached(s);
DistanceMap<ResGW> dist(res_graph);
while ( !bfs.finished() ) {
- ResGWOutEdgeIt e=bfs;
+ ResGWEdge e=bfs;
if (e!=INVALID && bfs.isBNodeNewlyReached()) {
dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
}
++bfs;
} //computing distances from s in the residual graph
- //Subgraph containing the edges on some shortest paths
+ //Subgraph containing the edges on some shortest paths
ConstMap<typename ResGW::Node, bool> true_map(true);
typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
DistanceMap<ResGW> > FilterResGW;
@@ -1366,17 +1366,17 @@
//Subgraph, which is able to delete edges which are already
//met by the dfs
- typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
+ typename FilterResGW::template NodeMap<typename FilterResGW::Edge>
first_out_edges(filter_res_graph);
typename FilterResGW::NodeIt v;
for(filter_res_graph.first(v); v!=INVALID; ++v)
{
- typename FilterResGW::OutEdgeIt e;
- filter_res_graph.first(e, v);
- first_out_edges.set(v, e);
+ typename FilterResGW::OutEdgeIt e;
+ filter_res_graph.first(e, v);
+ first_out_edges.set(v, e);
}
typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
- template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
+ template NodeMap<typename FilterResGW::Edge> > ErasingResGW;
ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
bool __augment=true;
@@ -1389,8 +1389,7 @@
typename ErasingResGW::template NodeMap<bool> >
dfs(erasing_res_graph);
typename ErasingResGW::
- template NodeMap<typename ErasingResGW::OutEdgeIt>
- pred(erasing_res_graph);
+ template NodeMap<typename ErasingResGW::Edge> pred(erasing_res_graph);
pred.set(s, INVALID);
//invalid iterators for sources
@@ -1398,31 +1397,32 @@
free1(erasing_res_graph);
dfs.pushAndSetReached
- ///\bug hugo 0.2
+ /// \bug hugo 0.2
(typename ErasingResGW::Node
(typename FilterResGW::Node
(typename ResGW::Node(s)
)
)
);
+
while (!dfs.finished()) {
++dfs;
- if (erasing_res_graph.valid(typename ErasingResGW::OutEdgeIt(dfs)))
+ if (typename ErasingResGW::Edge(dfs)!=INVALID)
{
if (dfs.isBNodeNewlyReached()) {
- typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
- typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
+ typename ErasingResGW::Node v=erasing_res_graph.tail(dfs);
+ typename ErasingResGW::Node w=erasing_res_graph.head(dfs);
- pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
+ pred.set(w, typename ErasingResGW::Edge(dfs));
if (pred[v]!=INVALID) {
free1.set
(w, std::min(free1[v], res_graph.resCap
- (typename ErasingResGW::OutEdgeIt(dfs))));
+ (typename ErasingResGW::Edge(dfs))));
} else {
free1.set
(w, res_graph.resCap
- (typename ErasingResGW::OutEdgeIt(dfs)));
+ (typename ErasingResGW::Edge(dfs)));
}
if (w==t) {
@@ -1449,8 +1449,8 @@
// typename ErasingResGW::Node b2;
// Num j2=a2[b2];
Num augment_value=free1[n];
- while (erasing_res_graph.valid(pred[n])) {
- typename ErasingResGW::OutEdgeIt e=pred[n];
+ while (pred[n]!=INVALID) {
+ typename ErasingResGW::Edge e=pred[n];
res_graph.augment(e, augment_value);
n=erasing_res_graph.tail(e);
if (res_graph.resCap(e)==0)
diff -r f2994a2b10b2 -r a82713ed19f3 src/work/marci/bfs_dfs.h
--- a/src/work/marci/bfs_dfs.h Tue Aug 31 13:40:07 2004 +0000
+++ b/src/work/marci/bfs_dfs.h Tue Aug 31 17:54:22 2004 +0000
@@ -27,12 +27,13 @@
class BfsIterator {
protected:
typedef typename Graph::Node Node;
+ typedef typename Graph::Edge Edge;
typedef typename Graph::OutEdgeIt OutEdgeIt;
const Graph* graph;
std::queue<Node> bfs_queue;
ReachedMap& reached;
bool b_node_newly_reached;
- OutEdgeIt actual_edge;
+ Edge actual_edge;
bool own_reached_map;
public:
/// In that constructor \c _reached have to be a reference
@@ -55,11 +56,12 @@
/// If the queue is empty, then \c s is pushed in the bfs queue
/// and the first out-edge is processed.
/// If the queue is not empty, then \c s is simply pushed.
- void pushAndSetReached(Node s) {
+ BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
reached.set(s, true);
if (bfs_queue.empty()) {
bfs_queue.push(s);
- graph->first(actual_edge, s);
+ actual_edge=OutEdgeIt(*graph, s);
+ //graph->first(actual_edge, s);
if (actual_edge!=INVALID) {
Node w=graph->head(actual_edge);
if (!reached[w]) {
@@ -73,13 +75,15 @@
} else {
bfs_queue.push(s);
}
+ return *this;
}
/// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
/// its \c operator++() iterates on the edges in a bfs order.
BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
operator++() {
if (actual_edge!=INVALID) {
- ++actual_edge;
+ actual_edge=++OutEdgeIt(*graph, actual_edge);
+ //++actual_edge;
if (actual_edge!=INVALID) {
Node w=graph->head(actual_edge);
if (!reached[w]) {
@@ -93,7 +97,8 @@
} else {
bfs_queue.pop();
if (!bfs_queue.empty()) {
- graph->first(actual_edge, bfs_queue.front());
+ actual_edge=OutEdgeIt(*graph, bfs_queue.front());
+ //graph->first(actual_edge, bfs_queue.front());
if (actual_edge!=INVALID) {
Node w=graph->head(actual_edge);
if (!reached[w]) {
@@ -113,15 +118,15 @@
/// The conversion operator makes for converting the bfs-iterator
/// to an \c out-edge-iterator.
///\bug Edge have to be in HUGO 0.2
- operator OutEdgeIt() const { return actual_edge; }
+ operator Edge() const { return actual_edge; }
/// Returns if b-node has been reached just now.
bool isBNodeNewlyReached() const { return b_node_newly_reached; }
/// Returns if a-node is examined.
bool isANodeExamined() const { return actual_edge==INVALID; }
/// Returns a-node of the actual edge, so does if the edge is invalid.
- Node aNode() const { return bfs_queue.front(); }
+ Node tail() const { return bfs_queue.front(); }
/// \pre The actual edge have to be valid.
- Node bNode() const { return graph->bNode(actual_edge); }
+ Node head() const { return graph->head(actual_edge); }
/// Guess what?
/// \deprecated
const ReachedMap& getReachedMap() const { return reached; }
@@ -159,7 +164,7 @@
/// If \c s was not marked previously, then
/// in addition its pred is set to be \c INVALID, and dist to \c 0.
/// if \c s was marked previuosly, then it is simply pushed.
- void push(Node s) {
+ Bfs<Graph, ReachedMap, PredMap, DistMap>& push(Node s) {
if (this->reached[s]) {
Parent::pushAndSetReached(s);
} else {
@@ -167,11 +172,13 @@
pred.set(s, INVALID);
dist.set(s, 0);
}
+ return *this;
}
/// A bfs is processed from \c s.
- void run(Node s) {
+ Bfs<Graph, ReachedMap, PredMap, DistMap>& run(Node s) {
push(s);
while (!this->finished()) this->operator++();
+ return *this;
}
/// Beside the bfs iteration, \c pred and \dist are saved in a
/// newly reached node.
@@ -179,8 +186,8 @@
Parent::operator++();
if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
{
- pred.set(this->bNode(), this->actual_edge);
- dist.set(this->bNode(), dist[this->aNode()]);
+ pred.set(this->head(), this->actual_edge);
+ dist.set(this->head(), dist[this->tail()]);
}
return *this;
}
@@ -201,11 +208,12 @@
class DfsIterator {
protected:
typedef typename Graph::Node Node;
+ typedef typename Graph::Edge Edge;
typedef typename Graph::OutEdgeIt OutEdgeIt;
const Graph* graph;
std::stack<OutEdgeIt> dfs_stack;
bool b_node_newly_reached;
- OutEdgeIt actual_edge;
+ Edge actual_edge;
Node actual_node;
ReachedMap& reached;
bool own_reached_map;
@@ -224,25 +232,25 @@
own_reached_map(true) { }
~DfsIterator() { if (own_reached_map) delete &reached; }
/// This method markes s reached and first out-edge is processed.
- void pushAndSetReached(Node s) {
+ DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
actual_node=s;
reached.set(s, true);
- OutEdgeIt e;
- graph->first(e, s);
+ OutEdgeIt e(*graph, s);
+ //graph->first(e, s);
dfs_stack.push(e);
+ return *this;
}
/// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
/// its \c operator++() iterates on the edges in a dfs order.
DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
operator++() {
actual_edge=dfs_stack.top();
- //actual_node=G.aNode(actual_edge);
if (actual_edge!=INVALID/*.valid()*/) {
Node w=graph->head(actual_edge);
actual_node=w;
if (!reached[w]) {
- OutEdgeIt e;
- graph->first(e, w);
+ OutEdgeIt e(*graph, w);
+ //graph->first(e, w);
dfs_stack.push(e);
reached.set(w, true);
b_node_newly_reached=true;
@@ -262,16 +270,16 @@
/// The conversion operator makes for converting the bfs-iterator
/// to an \c out-edge-iterator.
///\bug Edge have to be in HUGO 0.2
- operator OutEdgeIt() const { return actual_edge; }
+ operator Edge() const { return actual_edge; }
/// Returns if b-node has been reached just now.
bool isBNodeNewlyReached() const { return b_node_newly_reached; }
/// Returns if a-node is examined.
bool isANodeExamined() const { return actual_edge==INVALID; }
/// Returns a-node of the actual edge, so does if the edge is invalid.
- Node aNode() const { return actual_node; /*FIXME*/}
+ Node tail() const { return actual_node; /*FIXME*/}
/// Returns b-node of the actual edge.
/// \pre The actual edge have to be valid.
- Node bNode() const { return graph->bNode(actual_edge); }
+ Node head() const { return graph->head(actual_edge); }
/// Guess what?
/// \deprecated
const ReachedMap& getReachedMap() const { return reached; }
@@ -304,18 +312,20 @@
/// If \c s was not marked previously, then
/// in addition its pred is set to be \c INVALID.
/// if \c s was marked previuosly, then it is simply pushed.
- void push(Node s) {
+ Dfs<Graph, ReachedMap, PredMap>& push(Node s) {
if (this->reached[s]) {
Parent::pushAndSetReached(s);
} else {
Parent::pushAndSetReached(s);
pred.set(s, INVALID);
}
+ return *this;
}
/// A bfs is processed from \c s.
- void run(Node s) {
+ Dfs<Graph, ReachedMap, PredMap>& run(Node s) {
push(s);
while (!this->finished()) this->operator++();
+ return *this;
}
/// Beside the dfs iteration, \c pred is saved in a
/// newly reached node.
@@ -323,7 +333,7 @@
Parent::operator++();
if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
{
- pred.set(this->bNode(), this->actual_edge);
+ pred.set(this->head(), this->actual_edge);
}
return *this;
}
diff -r f2994a2b10b2 -r a82713ed19f3 src/work/marci/bfsit_vs_byhand.cc
--- a/src/work/marci/bfsit_vs_byhand.cc Tue Aug 31 13:40:07 2004 +0000
+++ b/src/work/marci/bfsit_vs_byhand.cc Tue Aug 31 17:54:22 2004 +0000
@@ -33,7 +33,7 @@
cout << g.nodeNum() << endl;
cout << g.edgeNum() << endl;
- Graph::NodeMap<OutEdgeIt> pred(g);
+ Graph::NodeMap<Edge> pred(g);
cout << "iteration time of bfs written by hand..." << endl;
Timer ts;
{
@@ -69,7 +69,7 @@
while (!bfs.finished()) {
++bfs;
if (g.valid(bfs) && bfs.isBNodeNewlyReached())
- pred.set(bfs.bNode(), bfs);
+ pred.set(bfs.head(), Graph::Edge(bfs));
}
std::cout << ts << std::endl;
}
diff -r f2994a2b10b2 -r a82713ed19f3 src/work/marci/graph_wrapper_time.cc
--- a/src/work/marci/graph_wrapper_time.cc Tue Aug 31 13:40:07 2004 +0000
+++ b/src/work/marci/graph_wrapper_time.cc Tue Aug 31 17:54:22 2004 +0000
@@ -1,5 +1,8 @@
// -*- c++ -*-
+// Use a DIMACS max flow file as follows:
+// graph_wrapper_time dimacs_max_flow_file
+
#include <iostream>
#include <fstream>
#include <string>
@@ -28,8 +31,7 @@
readDimacs(is, g, cap, s, t);
Timer ts;
ts.reset();
- cout << g.nodeNum() << endl;
- cout << g.edgeNum() << endl;
+
typedef MaxFlow<Graph, int, FlowMap, FlowMap> MyMaxFlow;
MyMaxFlow max_flow(g, s, t, cap, flow);
max_flow.run(MyMaxFlow::NO_FLOW);
@@ -41,17 +43,9 @@
typedef ListGraph Graph;
Graph g;
-// cout << g.id(g.addNode()) << endl;
-// cout << g.id(g.addNode()) << endl;
-// cout << g.nodeNum() << endl;
timeTest<Graph>(in, g);
typedef GraphWrapper<Graph> Graph1;
Graph1 g1(g);
-// g1.clear();
-// cout << g.id(g1.addNode()) << endl;
-// cout << g.id(g1.addNode()) << endl;
-// cout << g1.nodeNum() << endl;
-// g1.clear();
timeTest<Graph1>(in, g1);
typedef GraphWrapper<Graph1> Graph2;
Graph2 g2(g1);
@@ -59,18 +53,18 @@
typedef GraphWrapper<Graph2> Graph3;
Graph3 g3(g2);
timeTest<Graph3>(in, g3);
-// typedef GraphWrapper<Graph3> Graph4;
-// Graph4 g4(g3);
-// timeTest<Graph4>(in, g4);
-// typedef GraphWrapper<Graph4> Graph5;
-// Graph5 g5(g4);
-// timeTest<Graph5>(in, g5);
-// typedef GraphWrapper<Graph5> Graph6;
-// Graph6 g6(g5);
-// timeTest<Graph6>(in, g6);
-// typedef GraphWrapper<Graph6> Graph7;
-// Graph7 g7(g6);
-// timeTest<Graph7>(in, g7);
+ typedef GraphWrapper<Graph3> Graph4;
+ Graph4 g4(g3);
+ timeTest<Graph4>(in, g4);
+ typedef GraphWrapper<Graph4> Graph5;
+ Graph5 g5(g4);
+ timeTest<Graph5>(in, g5);
+ typedef GraphWrapper<Graph5> Graph6;
+ Graph6 g6(g5);
+ timeTest<Graph6>(in, g6);
+ typedef GraphWrapper<Graph6> Graph7;
+ Graph7 g7(g6);
+ timeTest<Graph7>(in, g7);
return 0;
}
diff -r f2994a2b10b2 -r a82713ed19f3 src/work/marci/iterator_bfs_demo.cc
--- a/src/work/marci/iterator_bfs_demo.cc Tue Aug 31 13:40:07 2004 +0000
+++ b/src/work/marci/iterator_bfs_demo.cc Tue Aug 31 17:54:22 2004 +0000
@@ -9,6 +9,7 @@
#include <hugo/graph_wrapper.h>
using namespace hugo;
+
using std::cout;
using std::endl;
using std::string;
@@ -72,21 +73,6 @@
cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
cout << " \\--> -------------> "<< endl;
-// typedef TrivGraphWrapper<const Graph> CGW;
-// CGW gw(G);
-
-// cout << "bfs and dfs demo on the directed graph" << endl;
-// for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) {
-// cout << n << ": ";
-// cout << "out edges: ";
-// for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
-// cout << e << " ";
-// cout << "in edges: ";
-// for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e)
-// cout << e << " ";
-// cout << endl;
-// }
-
{
EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
@@ -107,7 +93,7 @@
bfs.pushAndSetReached(s);
while (!bfs.finished()) {
//cout << "edge: ";
- if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) {
+ if (Graph::Edge(bfs)!=INVALID) {
cout << edge_name[bfs] << /*endl*/", " <<
node_name[G.tail(bfs)] <<
(bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
@@ -116,7 +102,7 @@
": is not newly reached.");
} else {
cout << "invalid" << /*endl*/", " <<
- node_name[bfs.aNode()] <<
+ node_name[bfs.tail()] <<
(bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
"invalid.";
@@ -141,7 +127,7 @@
while (!dfs.finished()) {
++dfs;
//cout << "edge: ";
- if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) {
+ if (Graph::Edge(dfs)!=INVALID) {
cout << edge_name[dfs] << /*endl*/", " <<
node_name[G.tail(dfs)] <<
(dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
@@ -150,7 +136,7 @@
": is not newly reached.");
} else {
cout << "invalid" << /*endl*/", " <<
- node_name[dfs.aNode()] <<
+ node_name[dfs.tail()] <<
(dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
"invalid.";
@@ -183,8 +169,8 @@
bfs.pushAndSetReached(t);
while (!bfs.finished()) {
//cout << "edge: ";
- if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) {
- cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
+ if (GW::Edge(bfs)!=INVALID) {
+ cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<
node_name[gw.tail(bfs)] <<
(bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
node_name[gw.head(bfs)] <<
@@ -192,7 +178,7 @@
": is not newly reached.");
} else {
cout << "invalid" << /*endl*/", " <<
- node_name[bfs.aNode()] <<
+ node_name[bfs.tail()] <<
(bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
"invalid.";
@@ -217,8 +203,8 @@
while (!dfs.finished()) {
++dfs;
//cout << "edge: ";
- if (GW::OutEdgeIt(dfs)!=INVALID) {
- cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
+ if (GW::Edge(dfs)!=INVALID) {
+ cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<
node_name[gw.tail(dfs)] <<
(dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
node_name[gw.head(dfs)] <<
@@ -226,7 +212,7 @@
": is not newly reached.");
} else {
cout << "invalid" << /*endl*/", " <<
- node_name[dfs.aNode()] <<
+ node_name[dfs.tail()] <<
(dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
"invalid.";
@@ -346,8 +332,8 @@
bfs.pushAndSetReached(t);
while (!bfs.finished()) {
//cout << "edge: ";
- if (GW::OutEdgeIt(bfs)!=INVALID) {
- cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
+ if (GW::Edge(bfs)!=INVALID) {
+ cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<
node_name[gw.tail(bfs)] <<
(bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
node_name[gw.head(bfs)] <<
@@ -355,7 +341,7 @@
": is not newly reached.");
} else {
cout << "invalid" << /*endl*/", " <<
- node_name[bfs.aNode()] <<
+ node_name[bfs.tail()] <<
(bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
"invalid.";
@@ -380,8 +366,8 @@
while (!dfs.finished()) {
++dfs;
//cout << "edge: ";
- if (GW::OutEdgeIt(dfs)!=INVALID) {
- cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
+ if (GW::Edge(dfs)!=INVALID) {
+ cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<
node_name[gw.tail(dfs)] <<
(dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
node_name[gw.head(dfs)] <<
@@ -389,7 +375,7 @@
": is not newly reached.");
} else {
cout << "invalid" << /*endl*/", " <<
- node_name[dfs.aNode()] <<
+ node_name[dfs.tail()] <<
(dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
"invalid.";
diff -r f2994a2b10b2 -r a82713ed19f3 src/work/marci/lg_vs_sg_vs_sg.cc
--- a/src/work/marci/lg_vs_sg_vs_sg.cc Tue Aug 31 13:40:07 2004 +0000
+++ b/src/work/marci/lg_vs_sg_vs_sg.cc Tue Aug 31 17:54:22 2004 +0000
@@ -53,7 +53,7 @@
{
std::cout << "physical blocking flow augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
@@ -75,7 +75,7 @@
{
std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
@@ -86,7 +86,7 @@
{
std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
@@ -121,7 +121,7 @@
{
std::cout << "preflow ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
max_flow_test.run();
std::cout << "elapsed time: " << ts << std::endl;
@@ -130,7 +130,7 @@
{
std::cout << "physical blocking flow augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
@@ -152,7 +152,7 @@
{
std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
@@ -163,7 +163,7 @@
{
std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
@@ -198,7 +198,7 @@
{
std::cout << "preflow ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
max_flow_test.run();
std::cout << "elapsed time: " << ts << std::endl;
@@ -207,7 +207,7 @@
{
std::cout << "physical blocking flow augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
@@ -229,7 +229,7 @@
{
std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
@@ -240,7 +240,7 @@
{
std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
diff -r f2994a2b10b2 -r a82713ed19f3 src/work/marci/max_flow_demo.cc
--- a/src/work/marci/max_flow_demo.cc Tue Aug 31 13:40:07 2004 +0000
+++ b/src/work/marci/max_flow_demo.cc Tue Aug 31 17:54:22 2004 +0000
@@ -1,4 +1,9 @@
// -*- c++ -*-
+
+// Use a DIMACS max flow file as stdin.
+// max_flow_demo < dimacs_max_flow_file
+
+
#include <iostream>
#include <fstream>
@@ -15,9 +20,6 @@
using namespace hugo;
-// Use a DIMACS max flow file as stdin.
-// max_flow_demo < dimacs_max_flow_file
-
int main(int, char **) {
typedef SageGraph MutableGraph;
@@ -102,23 +104,23 @@
}
}
-// {
-// 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 (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
-// std::cout << "elapsed time: " << ts << std::endl;
-// std::cout << "number of augmentation phases: " << i << std::endl;
-// std::cout << "flow value: "<< augmenting_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 (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
+ std::cout << "elapsed time: " << ts << std::endl;
+ std::cout << "number of augmentation phases: " << i << std::endl;
+ std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
-// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
-// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
-// std::cout << "Slackness does not hold!" << std::endl;
-// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
-// std::cout << "Slackness does not hold!" << std::endl;
-// }
-// }
+ FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+ if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
+ std::cout << "Slackness does not hold!" << std::endl;
+ if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
+ std::cout << "Slackness does not hold!" << std::endl;
+ }
+ }
{
std::cout << "on-the-fly shortest path augmentation ..." << std::endl;