32 #include <lemon/maps.h> |
32 #include <lemon/maps.h> |
33 |
33 |
34 #include <lemon/bits/base_extender.h> |
34 #include <lemon/bits/base_extender.h> |
35 #include <lemon/bits/graph_adaptor_extender.h> |
35 #include <lemon/bits/graph_adaptor_extender.h> |
36 #include <lemon/bits/graph_extender.h> |
36 #include <lemon/bits/graph_extender.h> |
37 |
|
38 #include <lemon/tolerance.h> |
37 #include <lemon/tolerance.h> |
39 |
38 |
40 #include <algorithm> |
39 #include <algorithm> |
41 |
40 |
42 namespace lemon { |
41 namespace lemon { |
945 ///with a max flow algorithm Preflow. |
944 ///with a max flow algorithm Preflow. |
946 ///\code |
945 ///\code |
947 ///ConstMap<Edge, int> const_1_map(1); |
946 ///ConstMap<Edge, int> const_1_map(1); |
948 ///Graph::EdgeMap<int> flow(g, 0); |
947 ///Graph::EdgeMap<int> flow(g, 0); |
949 /// |
948 /// |
950 ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > |
949 ///Preflow<SubGA, ConstMap<Edge, int>, Graph::EdgeMap<int> > |
951 /// preflow(ga, s, t, const_1_map, flow); |
950 /// preflow(ga, const_1_map, s, t); |
952 ///preflow.run(); |
951 ///preflow.run(); |
953 ///\endcode |
952 ///\endcode |
954 ///Last, the output is: |
953 ///Last, the output is: |
955 ///\code |
954 ///\code |
956 ///cout << "maximum number of edge-disjoint shortest path: " |
955 ///cout << "maximum number of edge-disjoint shortest path: " |
957 /// << preflow.flowValue() << endl; |
956 /// << preflow.flowValue() << endl; |
958 ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " |
957 ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " |
959 /// << endl; |
958 /// << endl; |
960 ///for(EdgeIt e(g); e!=INVALID; ++e) |
959 ///for(EdgeIt e(g); e!=INVALID; ++e) |
961 /// if (flow[e]) |
960 /// if (preflow.flow(e)) |
962 /// cout << " " << g.id(g.source(e)) << "--" |
961 /// cout << " " << g.id(g.source(e)) << "--" |
963 /// << length[e] << "->" << g.id(g.target(e)) << endl; |
962 /// << length[e] << "->" << g.id(g.target(e)) << endl; |
964 ///\endcode |
963 ///\endcode |
965 ///The program has the following (expected :-)) output: |
964 ///The program has the following (expected :-)) output: |
966 ///\code |
965 ///\code |
2019 return Edge(findEdge(*Parent::graph, u, v, prev)); |
2018 return Edge(findEdge(*Parent::graph, u, v, prev)); |
2020 } |
2019 } |
2021 } |
2020 } |
2022 return INVALID; |
2021 return INVALID; |
2023 } |
2022 } |
|
2023 |
2024 |
2024 |
2025 template <typename T> |
2025 template <typename T> |
2026 class NodeMap : public MapBase<Node, T> { |
2026 class NodeMap : public MapBase<Node, T> { |
2027 typedef typename Parent::template NodeMap<T> NodeImpl; |
2027 typedef typename Parent::template NodeMap<T> NodeImpl; |
2028 public: |
2028 public: |
2029 NodeMap(const SplitGraphAdaptorBase& _graph) |
2029 NodeMap(const SplitGraphAdaptorBase& _graph) |
2030 : inNodeMap(_graph), outNodeMap(_graph) {} |
2030 : inNodeMap(_graph), outNodeMap(_graph) {} |
2031 NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) |
2031 NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) |
2032 : inNodeMap(_graph, t), outNodeMap(_graph, t) {} |
2032 : inNodeMap(_graph, t), outNodeMap(_graph, t) {} |
2033 |
2033 NodeMap& operator=(const NodeMap& cmap) { |
|
2034 return operator=<NodeMap>(cmap); |
|
2035 } |
|
2036 template <typename CMap> |
|
2037 NodeMap& operator=(const CMap& cmap) { |
|
2038 Parent::operator=(cmap); |
|
2039 return *this; |
|
2040 } |
|
2041 |
2034 void set(const Node& key, const T& val) { |
2042 void set(const Node& key, const T& val) { |
2035 if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); } |
2043 if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); } |
2036 else {outNodeMap.set(key, val); } |
2044 else {outNodeMap.set(key, val); } |
2037 } |
2045 } |
2038 |
2046 |
2060 |
2068 |
2061 EdgeMap(const SplitGraphAdaptorBase& _graph) |
2069 EdgeMap(const SplitGraphAdaptorBase& _graph) |
2062 : edge_map(_graph), node_map(_graph) {} |
2070 : edge_map(_graph), node_map(_graph) {} |
2063 EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) |
2071 EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) |
2064 : edge_map(_graph, t), node_map(_graph, t) {} |
2072 : edge_map(_graph, t), node_map(_graph, t) {} |
|
2073 EdgeMap& operator=(const EdgeMap& cmap) { |
|
2074 return operator=<EdgeMap>(cmap); |
|
2075 } |
|
2076 template <typename CMap> |
|
2077 EdgeMap& operator=(const CMap& cmap) { |
|
2078 Parent::operator=(cmap); |
|
2079 return *this; |
|
2080 } |
2065 |
2081 |
2066 void set(const Edge& key, const T& val) { |
2082 void set(const Edge& key, const T& val) { |
2067 if (SplitGraphAdaptorBase::origEdge(key)) { |
2083 if (SplitGraphAdaptorBase::origEdge(key)) { |
2068 edge_map.set(key.item.first(), val); |
2084 edge_map.set(key.item.first(), val); |
2069 } else { |
2085 } else { |
2468 /// typedef ConstMap<SGraph::Edge, int> SCapacity; |
2484 /// typedef ConstMap<SGraph::Edge, int> SCapacity; |
2469 /// SCapacity scapacity(1); |
2485 /// SCapacity scapacity(1); |
2470 /// |
2486 /// |
2471 /// SGraph::EdgeMap<int> sflow(sgraph); |
2487 /// SGraph::EdgeMap<int> sflow(sgraph); |
2472 /// |
2488 /// |
2473 /// Preflow<SGraph, int, SCapacity> |
2489 /// Preflow<SGraph, SCapacity> |
2474 /// spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target), |
2490 /// spreflow(sgraph, scapacity, |
2475 /// scapacity, sflow); |
2491 /// SGraph::outNode(source), SGraph::inNode(target)); |
2476 /// |
2492 /// |
2477 /// spreflow.run(); |
2493 /// spreflow.run(); |
2478 /// |
2494 /// |
2479 ///\endcode |
2495 ///\endcode |
2480 /// |
2496 /// |