lemon-0.x: comparison src/hugo/graph

equal deleted inserted replaced

-:5f5edb1e7ae5
+:6a891870210a
 GraphWrapper(Graph& _graph) : graph(&_graph) { }
 GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }
 //     Graph& getGraph() const { return *graph; }
 typedef typename Graph::Node Node;
-//     class Node : public Graph::Node {
-//       friend class GraphWrapper<Graph>;
-//     public:
-//       Node() { }
-//       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
-//       // /// \bug construction throughrthr multiple levels should be
-//       // /// handled better
-//       // Node(const typename ParentGraph::ParentGraph::Node& _n) :
-//       // Graph::Node(_n) { }
-//       Node(const Invalid& i) : Graph::Node(i) { }
-//     };
 class NodeIt : public Node {
 const GraphWrapper<Graph>* gw;
 friend class GraphWrapper<Graph>;
 public:
 NodeIt() { }
 	  ++(typename Graph::NodeIt(*(gw->graph), *this));
 	return *this;
 }
 };
 typedef typename Graph::Edge Edge;
-//     class Edge : public Graph::Edge {
-//       friend class GraphWrapper<Graph>;
-//     public:
-//       Edge() { }
-//       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
-//       Edge(const Invalid& i) : Graph::Edge(i) { }
-//     };
 class OutEdgeIt : public Edge {
 const GraphWrapper<Graph>* gw;
 friend class GraphWrapper<Graph>;
 public:
 OutEdgeIt() { }
 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
 RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
 typedef typename GraphWrapper<Graph>::Node Node;
 typedef typename GraphWrapper<Graph>::Edge Edge;
-//If Graph::OutEdgeIt is not defined
+//remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
-//and we do not want to use RevGraphWrapper::InEdgeIt,
+//because this does not work is some of them are not defined in the
-//the typdef techinque does not work.
+//original graph. The problem with this is that typedef-ed stuff
-//Unfortunately all the typedefs are instantiated in templates.
+//are instantiated in c++.
-//typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
-//typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
 class OutEdgeIt : public Edge {
 const RevGraphWrapper<Graph>* gw;
 friend class GraphWrapper<Graph>;
 public:
 OutEdgeIt() { }
 		    EdgeFilterMap& _edge_filter_map) :
 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
 edge_filter_map(&_edge_filter_map) { }
 typedef typename GraphWrapper<Graph>::Node Node;
-//     class NodeIt {
-//       friend class GraphWrapper<Graph>;
-//       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
-//       typename Graph::NodeIt n;
-//      public:
-//       NodeIt() { }
-//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
-//       NodeIt(const Invalid& i) : n(i) { }
-//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
-// 	n(*(_G.graph)) {
-// 	while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
-// 	  _G.graph->next(n);
-//       }
-//       operator Node() const { return Node(typename Graph::Node(n)); }
-//     };
 class NodeIt : public Node {
 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
 public:
 NodeIt() { }
 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
 /// Returns true if \c n is hidden.
 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
-/// This is a linear time operation and works only if
+/// \warning This is a linear time operation and works only if
-/// NodeIt is defined.
+/// \c Graph::NodeIt is defined.
 int nodeNum() const {
 int i=0;
-NodeIt n;
+for (NodeIt n(*this); n!=INVALID; ++n) ++i;
-for (this->first(n); this->valid(n); this->next(n)) ++i;
 return i;
 }
-/// This is a linear time operation and works only if
+/// \warning This is a linear time operation and works only if
-/// EdgeIt is defined.
+/// \c Graph::EdgeIt is defined.
 int edgeNum() const {
 int i=0;
-EdgeIt e;
+for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
-for (this->first(e); this->valid(e); this->next(e)) ++i;
 return i;
 }
 };
 };
 ///\brief A wrapper for composing a subgraph of a
-/// bidirected graph composed from a directed one.
+/// bidirected graph made from a directed one.
-/// experimental, for fezso's sake.
 ///
-/// A wrapper for composing a subgraps of a
+/// Suppose that for a directed graph $G=(V, A)$,
-/// bidirected graph composed from a directed one.
+/// two predicates on the edge-set, $forward_filter$, and $backward_filter$
-/// experimental, for fezso's sake.
+/// is given, and we are dealing with the directed graph
-/// A bidirected graph is composed over the directed one without physical
+/// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$.
-/// storage. As the oppositely directed edges are logically different ones
+/// The purpose of writing + instead of union is because parallel
-/// the maps are able to attach different values for them.
+/// edges can arose.
+/// In other words, a subgraph of the bidirected graph obtained, which
+/// is given by orienting the edges of the original graph in both directions.
+/// An example for such a construction is the \c RevGraphWrapper where the
+/// forward_filter is everywhere false and the backward_filter is
+/// everywhere true. We note that for sake of efficiency,
+/// \c RevGraphWrapper is implemented in a different way.
+/// But BidirGraphWrapper is obtained from
+/// SubBidirGraphWrapper by considering everywhere true
+/// predicates both forward_filter and backward_filter.
+/// Finally, one of the most important applications of SubBidirGraphWrapper
+/// is ResGraphWrapper, which stands for the residual graph in directed
+/// flow and circulation problems.
+/// As wrappers usually, the SubBidirGraphWrapper implements the
+/// above mentioned graph structure without its physical storage,
+/// that is the whole stuff eats constant memory.
+/// As the oppositely directed edges are logical different,
+/// the maps are able to attach different values for them.
 template<typename Graph,
 	   typename ForwardFilterMap, typename BackwardFilterMap>
 class SubBidirGraphWrapper : public GraphWrapper<Graph> {
 public:
 typedef GraphWrapper<Graph> Parent;
 protected:
 ForwardFilterMap* forward_filter;
 BackwardFilterMap* backward_filter;
-SubBidirGraphWrapper() : GraphWrapper<Graph>()/*,
+SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
-						 capacity(0), flow(0)*/ { }
 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
 forward_filter=&_forward_filter;
 }
 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
 backward_filter=&_backward_filter;
 class Edge;
 class OutEdgeIt;
 friend class Edge;
 friend class OutEdgeIt;
-//template<typename T> class NodeMap;
 template<typename T> class EdgeMap;
 typedef typename GraphWrapper<Graph>::Node Node;
-//typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
 typedef typename Graph::Edge GraphEdge;
+/// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
+/// Graph::Edge. It contains an extra bool flag which shows if the
+/// edge is the backward version of the original edge.
 class Edge : public Graph::Edge {
 friend class SubBidirGraphWrapper<Graph,
 					ForwardFilterMap, BackwardFilterMap>;
-///\bug ez nem is kell
-//template<typename T> friend class NodeMap;
 template<typename T> friend class EdgeMap;
 protected:
 bool backward; //true, iff backward
-//      typename Graph::Edge e;
 public:
 Edge() { }
-///\bug =false kell-e? zsoltnak kell az addEdge miatt
+/// \todo =false is needed, or causes problems?
+/// If \c _backward is false, then we get an edge corresponding to the
+/// original one, otherwise its oppositely directed pair is obtained.
 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
 	Graph::Edge(e), backward(_backward) { }
 Edge(Invalid i) : Graph::Edge(i), backward(true) { }
 //the unique invalid iterator
 //       friend bool operator==(const Edge& u, const Edge& v) {
 //       i=NodeIt(*this); return i;
 //     }
 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
 i=OutEdgeIt(*this, p); return i;
 }
-//    FIXME not tested
 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
 i=InEdgeIt(*this, p); return i;
 }
 EdgeIt& first(EdgeIt& i) const {
 i=EdgeIt(*this); return i;
 Edge f=e;
 f.backward=!f.backward;
 return f;
 }
-//    int nodeNum() const { return graph->nodeNum(); }
+/// \warning This is a linear time operation and works only if
-//FIXME
+/// \c Graph::EdgeIt is defined.
-void edgeNum() const { }
+int edgeNum() const {
-//int edgeNum() const { return graph->edgeNum(); }
+int i=0;
+for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
+return i;
-//    int id(Node v) const { return graph->id(v); }
+}
-//     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
-//     bool valid(Edge e) const {
-//       return this->graph->valid(e);
-// 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in);
-//     }
 bool forward(const Edge& e) const { return !e.backward; }
 bool backward(const Edge& e) const { return e.backward; }
-//     void augment(const Edge& e, Number a) const {
-//       if (!e.backward)
-// // 	flow->set(e.out, flow->get(e.out)+a);
-// 	flow->set(e, (*flow)[e]+a);
-//       else
-// // 	flow->set(e.in, flow->get(e.in)-a);
-// 	flow->set(e, (*flow)[e]-a);
-//     }
-//     bool enabled(const Edge& e) const {
-//       if (!e.backward)
-// //	return (capacity->get(e.out)-flow->get(e.out));
-// 	//return ((*capacity)[e]-(*flow)[e]);
-// 	return true;
-//       else
-// //	return (flow->get(e.in));
-// 	//return ((*flow)[e]);
-// 	return true;
-//     }
-//     Number enabled(typename Graph::OutEdgeIt out) const {
-// //      return (capacity->get(out)-flow->get(out));
-//       return ((*capacity)[out]-(*flow)[out]);
-//     }
-//     Number enabled(typename Graph::InEdgeIt in) const {
-// //      return (flow->get(in));
-//       return ((*flow)[in]);
-//     }
 template <typename T>
+/// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
+/// Graph::EdgeMap one for the forward edges and
+/// one for the backward edges.
 class EdgeMap {
 typename Graph::template EdgeMap<T> forward_map, backward_map;
 public:
 typedef T ValueType;
 typedef Edge KeyType;
 EdgeMap(const SubBidirGraphWrapper<Graph,
 	      ForwardFilterMap, BackwardFilterMap>& g, T a) :
 	forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
 void set(Edge e, T a) {
 	if (!e.backward)
-	  forward_map.set(e/*.out*/, a);
+	  forward_map.set(e, a);
 	else
-	  backward_map.set(e/*.in*/, a);
+	  backward_map.set(e, a);
 }
 T operator[](Edge e) const {
 	if (!e.backward)
-	  return forward_map[e/*.out*/];
+	  return forward_map[e];
 	else
-	  return backward_map[e/*.in*/];
+	  return backward_map[e];
 }
 void update() {
 	forward_map.update();
 	backward_map.update();
 }
 //       }
 };
 };
 ///\brief A wrapper for composing bidirected graph from a directed one.
-/// experimental, for fezso's sake.
 ///
 /// A wrapper for composing bidirected graph from a directed one.
-/// experimental, for fezso's sake.
 /// A bidirected graph is composed over the directed one without physical
 /// storage. As the oppositely directed edges are logically different ones
 /// the maps are able to attach different values for them.
 template<typename Graph>
 class BidirGraphWrapper :
 Graph,
 ConstMap<typename Graph::Edge, bool>,
 ConstMap<typename Graph::Edge, bool> > Parent;
 protected:
 ConstMap<typename Graph::Edge, bool> cm;
-//const CapacityMap* capacity;
-//FlowMap* flow;
 BidirGraphWrapper() : Parent(), cm(true) {
 Parent::setForwardFilterMap(cm);
 Parent::setBackwardFilterMap(cm);
 }
-//     void setCapacityMap(const CapacityMap& _capacity) {
+public:
-//       capacity=&_capacity;
-//     }
-//     void setFlowMap(FlowMap& _flow) {
-//       flow=&_flow;
-//     }
-public:
 BidirGraphWrapper(Graph& _graph) : Parent() {
 Parent::setGraph(_graph);
 Parent::setForwardFilterMap(cm);
 Parent::setBackwardFilterMap(cm);
 }
 }
 };
+// this is a direct implementation of the bidirected-graph wrapper.
+// in early hugo, it was implemented that way.
 template<typename Graph>
 class OldBidirGraphWrapper : public GraphWrapper<Graph> {
 public:
 typedef GraphWrapper<Graph> Parent;
 protected:
-//const CapacityMap* capacity;
+OldBidirGraphWrapper() : GraphWrapper<Graph>() { }
-//FlowMap* flow;
+public:
-OldBidirGraphWrapper() : GraphWrapper<Graph>()/*,
-						 capacity(0), flow(0)*/ { }
+OldBidirGraphWrapper(Graph& _graph) :
-//     void setCapacityMap(const CapacityMap& _capacity) {
+GraphWrapper<Graph>(_graph) { }
-//       capacity=&_capacity;
-//     }
-//     void setFlowMap(FlowMap& _flow) {
-//       flow=&_flow;
-//     }
-public:
-OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
-				     FlowMap& _flow*/) :
-GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
 class Edge;
 class OutEdgeIt;
 friend class Edge;
 friend class OutEdgeIt;
 }
 bool forward(const Edge& e) const { return !e.backward; }
 bool backward(const Edge& e) const { return e.backward; }
-//     void augment(const Edge& e, Number a) const {
-//       if (!e.backward)
-// // 	flow->set(e.out, flow->get(e.out)+a);
-// 	flow->set(e, (*flow)[e]+a);
-//       else
-// // 	flow->set(e.in, flow->get(e.in)-a);
-// 	flow->set(e, (*flow)[e]-a);
-//     }
 bool enabled(const Edge& e) const {
 if (!e.backward)
 //	return (capacity->get(e.out)-flow->get(e.out));
 	//return ((*capacity)[e]-(*flow)[e]);
 	return true;
 	return ((*flow)[e]);
 }
 /// \brief Residual capacity map.
 ///
-/// In generic residual graphs the residual capacity can be obtained as a map.
+/// In generic residual graphs the residual capacity can be obtained as a map. Not tested.
 class ResCap {
 protected:
 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
 public:
 typedef Number ValueType;
 /// For blocking flows.
-/// This graph wrapper is used for Dinits blocking flow computations.
+/// This graph wrapper is used for on-the-fly
+/// Dinits blocking flow computations.
 /// For each node, an out-edge is stored which is used when the
 /// \code
 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
 /// \endcode
 /// is called.
 ///
-///\author Marton Makai
+/// \author Marton Makai
 template<typename Graph, typename FirstOutEdgesMap>
 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
 public:
 typedef GraphWrapper<Graph> Parent;
 protected:
 ErasingFirstGraphWrapper(Graph& _graph,
 			     FirstOutEdgesMap& _first_out_edges) :
 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
 typedef typename GraphWrapper<Graph>::Node Node;
-//     class NodeIt {
-//       friend class GraphWrapper<Graph>;
-//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
-//       typename Graph::NodeIt n;
-//      public:
-//       NodeIt() { }
-//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
-//       NodeIt(const Invalid& i) : n(i) { }
-//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
-// 	n(*(_G.graph)) { }
-//       operator Node() const { return Node(typename Graph::Node(n)); }
-//     };
 typedef typename GraphWrapper<Graph>::Edge Edge;
 class OutEdgeIt : public Edge {
 friend class GraphWrapper<Graph>;
 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
 const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;

changeset 808	9cabbdd73375
parent 777	a82713ed19f3
child 838	51dcd224455c