107 // typedef SubGraphAdaptor<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW; |
107 // typedef SubGraphAdaptor<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW; |
108 typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW; |
108 typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW; |
109 SubGW gw(g, tight_edge_filter); |
109 SubGW gw(g, tight_edge_filter); |
110 |
110 |
111 ConstMap<Edge, int> const_1_map(1); |
111 ConstMap<Edge, int> const_1_map(1); |
112 Graph::EdgeMap<int> flow(g, 0); |
|
113 // Max flow between s and t in the graph of tight edges. |
112 // Max flow between s and t in the graph of tight edges. |
114 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > |
113 Preflow<SubGW, ConstMap<Edge, int> > preflow(gw, const_1_map, s, t); |
115 preflow(gw, s, t, const_1_map, flow); |
|
116 preflow.run(); |
114 preflow.run(); |
117 |
115 |
118 cout << "maximum number of edge-disjoint shortest paths: " |
116 cout << "maximum number of edge-disjoint shortest paths: " |
119 << preflow.flowValue() << endl; |
117 << preflow.flowValue() << endl; |
120 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " |
118 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " |
121 << endl; |
119 << endl; |
122 for(EdgeIt e(g); e!=INVALID; ++e) |
120 for(EdgeIt e(g); e!=INVALID; ++e) |
123 if (flow[e]) |
121 if (preflow.flow(e) != 0) |
124 cout << " " << g.id(e) << ", " |
122 cout << " " << g.id(e) << ", " |
125 << g.id(g.source(e)) << "--" |
123 << g.id(g.source(e)) << "--" |
126 << length[e] << "->" << g.id(g.target(e)) << endl; |
124 << length[e] << "->" << g.id(g.target(e)) << endl; |
127 } |
125 } |