# Changeset 78:ecc1171307be in lemon-0.x for src

Ignore:
Timestamp:
02/16/04 17:15:58 (18 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@101
Message:

modern valtozat

Location:
src/work/jacint
Files:
2 added
4 edited

Unmodified
Added
Removed
• ## src/work/jacint/dijkstra.hh

 r50 *dijkstra *by jacint *Performs Dijkstra's algorithm from node s. *Performs Dijkstra's algorithm from Node s. * *Constructor: * *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance) *dijkstra(graph_type& G, NodeIt s, EdgeMap& distance) * * * * *T dist(node_iterator v) : returns the distance from s to v. *T dist(NodeIt v) : returns the distance from s to v. *   It is 0 if v is not reachable from s. * * *edge_iterator pred(node_iterator v) *   Returns the last edge of a shortest s-v path. *EdgeIt pred(NodeIt v) *   Returns the last Edge of a shortest s-v path. *   Returns an invalid iterator if v=s or v is not *   reachable from s. * * *bool reach(node_iterator v) : true if v is reachable from s *bool reach(NodeIt v) : true if v is reachable from s * * #include #include #include template class dijkstra{ typedef typename graph_traits::node_iterator node_iterator; typedef typename graph_traits::edge_iterator edge_iterator; typedef typename graph_traits::each_node_iterator each_node_iterator; typedef typename graph_traits::in_edge_iterator in_edge_iterator; typedef typename graph_traits::out_edge_iterator out_edge_iterator; typedef typename graph_traits::NodeIt NodeIt; typedef typename graph_traits::EdgeIt EdgeIt; typedef typename graph_traits::EachNodeIt EachNodeIt; typedef typename graph_traits::InEdgeIt InEdgeIt; typedef typename graph_traits::OutEdgeIt OutEdgeIt; graph_type& G; node_iterator s; node_property_vector predecessor; node_property_vector distance; edge_property_vector length; node_property_vector reached; NodeIt s; NodeMap predecessor; NodeMap distance; EdgeMap length; NodeMap reached; public : /* The distance of all the nodes is 0. The distance of all the Nodes is 0. */ dijkstra(graph_type& _G, node_iterator _s, edge_property_vector& _length) : dijkstra(graph_type& _G, NodeIt _s, EdgeMap& _length) : G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { } /*By Misi.*/ struct node_dist_comp struct Node_dist_comp { node_property_vector &d; node_dist_comp(node_property_vector &_d) : d(_d) {} NodeMap &d; Node_dist_comp(NodeMap &_d) : d(_d) {} bool operator()(const node_iterator& u, const node_iterator& v) const bool operator()(const NodeIt& u, const NodeIt& v) const { return d.get(u) < d.get(v); } }; void run() { node_property_vector scanned(G, false); std::priority_queue, node_dist_comp> heap(( node_dist_comp(distance) )); NodeMap scanned(G, false); std::priority_queue, Node_dist_comp> heap(( Node_dist_comp(distance) )); heap.push(s); while (!heap.empty()) { node_iterator v=heap.top(); NodeIt v=heap.top(); heap.pop(); if (!scanned.get(v)) { for(out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) { node_iterator w=G.head(e); for(OutEdgeIt e=G.template first(v); e.valid(); ++e) { NodeIt w=G.head(e); if (!scanned.get(w)) { /* *Returns the distance of the node v. *It is 0 for the root and for the nodes not *Returns the distance of the Node v. *It is 0 for the root and for the Nodes not *reachable form the root. */ T dist(node_iterator v) { T dist(NodeIt v) { return -distance.get(v); } /* *  Returns the last edge of a shortest s-v path. *  Returns the last Edge of a shortest s-v path. *  Returns an invalid iterator if v=root or v is not *  reachable from the root. */ edge_iterator pred(node_iterator v) { EdgeIt pred(NodeIt v) { if (v!=s) { return predecessor.get(v);} else {return edge_iterator();} else {return EdgeIt();} } bool reach(node_iterator v) { bool reach(NodeIt v) { return reached.get(v); }
• ## src/work/jacint/flow_test.cc

 r72 #include #include #include #include #include #include #include //#include #include #include #include #include //#include using namespace marci; int main (int, char*[]) { typedef graph_traits::node_iterator node_iterator; typedef graph_traits::edge_iterator edge_iterator; typedef graph_traits::each_node_iterator each_node_iterator; typedef graph_traits::each_edge_iterator each_edge_iterator; typedef graph_traits::out_edge_iterator out_edge_iterator; typedef graph_traits::in_edge_iterator in_edge_iterator; typedef graph_traits::sym_edge_iterator sym_edge_iterator; list_graph flow_test; typedef ListGraph::NodeIt NodeIt; typedef ListGraph::EdgeIt EdgeIt; typedef ListGraph::EachNodeIt EachNodeIt; typedef ListGraph::EachEdgeIt EachEdgeIt; typedef ListGraph::OutEdgeIt OutEdgeIt; typedef ListGraph::InEdgeIt InEdgeIt; ListGraph flow_test; //Ahuja könyv példája, maxflowvalue=13 node_iterator s=flow_test.add_node(); node_iterator v1=flow_test.add_node(); node_iterator v2=flow_test.add_node(); node_iterator v3=flow_test.add_node(); node_iterator v4=flow_test.add_node(); node_iterator v5=flow_test.add_node(); node_iterator t=flow_test.add_node(); node_property_vector node_name(flow_test); node_name.put(s, "s"); node_name.put(v1, "v1"); node_name.put(v2, "v2"); node_name.put(v3, "v3"); node_name.put(v4, "v4"); node_name.put(v5, "v5"); node_name.put(t, "t"); edge_iterator s_v1=flow_test.add_edge(s, v1); edge_iterator s_v2=flow_test.add_edge(s, v2); edge_iterator s_v3=flow_test.add_edge(s, v3); edge_iterator v2_v4=flow_test.add_edge(v2, v4); edge_iterator v2_v5=flow_test.add_edge(v2, v5); edge_iterator v3_v5=flow_test.add_edge(v3, v5); edge_iterator v4_t=flow_test.add_edge(v4, t); edge_iterator v5_t=flow_test.add_edge(v5, t); edge_iterator v2_s=flow_test.add_edge(v2, s); edge_property_vector cap(flow_test); cap.put(s_v1, 0); cap.put(s_v2, 10); cap.put(s_v3, 10); cap.put(v2_v4, 5); cap.put(v2_v5, 8); cap.put(v3_v5, 5); cap.put(v4_t, 8); cap.put(v5_t, 8); cap.put(v2_s, 0); NodeIt s=flow_test.addNode(); NodeIt v1=flow_test.addNode(); NodeIt v2=flow_test.addNode(); NodeIt v3=flow_test.addNode(); NodeIt v4=flow_test.addNode(); NodeIt v5=flow_test.addNode(); NodeIt t=flow_test.addNode(); ListGraph::NodeMap Node_name(flow_test); Node_name.set(s, "s"); Node_name.set(v1, "v1"); Node_name.set(v2, "v2"); Node_name.set(v3, "v3"); Node_name.set(v4, "v4"); Node_name.set(v5, "v5"); Node_name.set(t, "t"); EdgeIt s_v1=flow_test.addEdge(s, v1); EdgeIt s_v2=flow_test.addEdge(s, v2); EdgeIt s_v3=flow_test.addEdge(s, v3); EdgeIt v2_v4=flow_test.addEdge(v2, v4); EdgeIt v2_v5=flow_test.addEdge(v2, v5); EdgeIt v3_v5=flow_test.addEdge(v3, v5); EdgeIt v4_t=flow_test.addEdge(v4, t); EdgeIt v5_t=flow_test.addEdge(v5, t); EdgeIt v2_s=flow_test.addEdge(v2, s); ListGraph::EdgeMap cap(flow_test); cap.set(s_v1, 0); cap.set(s_v2, 10); cap.set(s_v3, 10); cap.set(v2_v4, 5); cap.set(v2_v5, 8); cap.set(v3_v5, 5); cap.set(v4_t, 8); cap.set(v5_t, 8); cap.set(v2_s, 0); //Marci példája, maxflowvalue=23 /*  node_iterator s=flow_test.add_node(); node_iterator v1=flow_test.add_node(); node_iterator v2=flow_test.add_node(); node_iterator v3=flow_test.add_node(); node_iterator v4=flow_test.add_node(); node_iterator t=flow_test.add_node(); node_iterator w=flow_test.add_node(); node_property_vector node_name(flow_test); node_name.put(s, "s"); node_name.put(v1, "v1"); node_name.put(v2, "v2"); node_name.put(v3, "v3"); node_name.put(v4, "v4"); node_name.put(t, "t"); node_name.put(w, "w"); edge_iterator s_v1=flow_test.add_edge(s, v1); edge_iterator s_v2=flow_test.add_edge(s, v2); edge_iterator v1_v2=flow_test.add_edge(v1, v2); edge_iterator v2_v1=flow_test.add_edge(v2, v1); edge_iterator v1_v3=flow_test.add_edge(v1, v3); edge_iterator v3_v2=flow_test.add_edge(v3, v2); edge_iterator v2_v4=flow_test.add_edge(v2, v4); edge_iterator v4_v3=flow_test.add_edge(v4, v3); edge_iterator v3_t=flow_test.add_edge(v3, t); edge_iterator v4_t=flow_test.add_edge(v4, t); edge_iterator v3_v3=flow_test.add_edge(v3, v3); edge_iterator s_w=flow_test.add_edge(s, w); //  edge_iterator v2_s=flow_test.add_edge(v2, s); edge_property_vector cap(flow_test);  //serves as length in dijkstra cap.put(s_v1, 16); cap.put(s_v2, 13); cap.put(v1_v2, 10); cap.put(v2_v1, 4); cap.put(v1_v3, 12); cap.put(v3_v2, 9); cap.put(v2_v4, 14); cap.put(v4_v3, 7); cap.put(v3_t, 20); cap.put(v4_t, 4); cap.put(v3_v3, 4); cap.put(s_w, 4); //  cap.put(v2_s, 0); /*  NodeIt s=flow_test.addNode(); NodeIt v1=flow_test.addNode(); NodeIt v2=flow_test.addNode(); NodeIt v3=flow_test.addNode(); NodeIt v4=flow_test.addNode(); NodeIt t=flow_test.addNode(); NodeIt w=flow_test.addNode(); NodeMap Node_name(flow_test); Node_name.set(s, "s"); Node_name.set(v1, "v1"); Node_name.set(v2, "v2"); Node_name.set(v3, "v3"); Node_name.set(v4, "v4"); Node_name.set(t, "t"); Node_name.set(w, "w"); EdgeIt s_v1=flow_test.addEdge(s, v1); EdgeIt s_v2=flow_test.addEdge(s, v2); EdgeIt v1_v2=flow_test.addEdge(v1, v2); EdgeIt v2_v1=flow_test.addEdge(v2, v1); EdgeIt v1_v3=flow_test.addEdge(v1, v3); EdgeIt v3_v2=flow_test.addEdge(v3, v2); EdgeIt v2_v4=flow_test.addEdge(v2, v4); EdgeIt v4_v3=flow_test.addEdge(v4, v3); EdgeIt v3_t=flow_test.addEdge(v3, t); EdgeIt v4_t=flow_test.addEdge(v4, t); EdgeIt v3_v3=flow_test.addEdge(v3, v3); EdgeIt s_w=flow_test.addEdge(s, w); //  EdgeIt v2_s=flow_test.addEdge(v2, s); EdgeMap cap(flow_test);  //serves as length in dijkstra cap.set(s_v1, 16); cap.set(s_v2, 13); cap.set(v1_v2, 10); cap.set(v2_v1, 4); cap.set(v1_v3, 12); cap.set(v3_v2, 9); cap.set(v2_v4, 14); cap.set(v4_v3, 7); cap.set(v3_t, 20); cap.set(v4_t, 4); cap.set(v3_v3, 4); cap.set(s_w, 4); //  cap.set(v2_s, 0); */ //pelda 3, maxflowvalue=4 /*      node_iterator s=flow_test.add_node(); node_iterator v1=flow_test.add_node(); node_iterator v2=flow_test.add_node(); node_iterator t=flow_test.add_node(); node_iterator w=flow_test.add_node(); node_property_vector node_name(flow_test); node_name.put(s, "s"); node_name.put(v1, "v1"); node_name.put(v2, "v2"); node_name.put(t, "t"); node_name.put(w, "w"); edge_iterator s_v1=flow_test.add_edge(s, v1); edge_iterator v1_v2=flow_test.add_edge(v1, v2); edge_iterator v2_t=flow_test.add_edge(v2, t); edge_iterator v1_v1=flow_test.add_edge(v1, v1); edge_iterator s_w=flow_test.add_edge(s, w); edge_property_vector cap(flow_test); /*      NodeIt s=flow_test.addNode(); NodeIt v1=flow_test.addNode(); NodeIt v2=flow_test.addNode(); NodeIt t=flow_test.addNode(); NodeIt w=flow_test.addNode(); NodeMap Node_name(flow_test); Node_name.set(s, "s"); Node_name.set(v1, "v1"); Node_name.set(v2, "v2"); Node_name.set(t, "t"); Node_name.set(w, "w"); EdgeIt s_v1=flow_test.addEdge(s, v1); EdgeIt v1_v2=flow_test.addEdge(v1, v2); EdgeIt v2_t=flow_test.addEdge(v2, t); EdgeIt v1_v1=flow_test.addEdge(v1, v1); EdgeIt s_w=flow_test.addEdge(s, w); EdgeMap cap(flow_test); cap.put(s_v1, 16); cap.put(v1_v2, 10); cap.put(v2_t, 4); cap.put(v1_v1, 3); cap.put(s_w, 5); cap.set(s_v1, 16); cap.set(v1_v2, 10); cap.set(v2_t, 4); cap.set(v1_v1, 3); cap.set(s_w, 5); */ std::cout << "Testing reverse_bfs..." << std::endl; reverse_bfs bfs_test(flow_test, t); reverse_bfs bfs_test(flow_test, t); bfs_test.run(); for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) { for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) { std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) < preflow_push_test(flow_test, s, t, cap); preflow_push_hl preflow_push_test(flow_test, s, t, cap); preflow_push_test.run(); std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."< flow=preflow_push_test.allflow(); for (each_edge_iterator e=flow_test.first_edge(); e.valid(); ++e) { std::cout <<"Flow on edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " < flow=preflow_push_test.allflow(); for (EachEdgeIt e=flow_test.template first(); e.valid(); ++e) { std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " < mincut=preflow_push_test.mincut(); for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) { if (mincut.get(v)) std::cout < mincut=preflow_push_test.mincut(); for (EachNodeIt v=flow_test.template first(); v.valid(); ++v) { if (mincut.get(v)) std::cout < max_flow_test(flow_test, s, t, cap); preflow_push_max_flow max_flow_test(flow_test, s, t, cap); max_flow_test.run(); std::cout << "A minimum cut: " < mincut2=max_flow_test.mincut(); for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) { if (mincut2.get(v)) std::cout < mincut2=max_flow_test.mincut(); for (EachNodeIt v=flow_test.template first(); v.valid(); ++v) { if (mincut2.get(v)) std::cout < dijkstra_test(flow_test, root, cap); NodeIt root=v2; dijkstra dijkstra_test(flow_test, root, cap); dijkstra_test.run(); for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) { for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) { if (dijkstra_test.reach(w)) { std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w); if (dijkstra_test.pred(w).valid()) { std::cout <<", a shortest path from the root ends with edge " << dijkstra_test.pred(w) <
• ## src/work/jacint/preflow_push_hl.h

 r72 #include #include #include namespace marci { template template class preflow_push_hl { NodeIt s; NodeIt t; Graph::EdgeMap flow; Graph::EdgeMap capacity; typename Graph::EdgeMap flow; typename Graph::EdgeMap capacity; T value; Graph::NodeMap mincutvector; typename Graph::NodeMap mincutvector; preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, Graph::EdgeMap& _capacity) : typename Graph::EdgeMap& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { } void run() { Graph::NodeMap level(G);         //level of Node Graph::NodeMap excess(G);          //excess of Node typename Graph::NodeMap level(G);         //level of Node typename Graph::NodeMap excess(G);          //excess of Node int n=G.nodeNum();                        //number of Nodes /*Reverse_bfs from t, to find the starting level.*/ reverse_bfs bfs(G, t); reverse_bfs bfs(G, t); bfs.run(); for(EachNodeIt v=G.template first(); v.valid(); ++v) { */ EdgeMap allflow() { typename Graph::EdgeMap allflow() { return flow; } */ NodeMap mincut() { typename Graph::NodeMap mincut() { std::queue queue; } }; }//namespace marci
• ## src/work/jacint/reverse_bfs.hh

 r50 reverse_bfs by jacint Performs a bfs on the out edges. It does not count predecessors, Performs a bfs on the out Edges. It does not count predecessors, only the distances, but one can easily modify it to know the pred as well. Constructor: reverse_bfs(graph_type& G, node_iterator t) reverse_bfs(graph_type& G, NodeIt t) The following function should be used after run() was already run. int dist(node_iterator v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v. int dist(NodeIt v) : returns the distance from v to t. It is the number of Nodes if t is not reachable from v. */ #include #include #include template class reverse_bfs { typedef typename graph_traits::node_iterator node_iterator; //typedef typename graph_traits::edge_iterator edge_iterator; typedef typename graph_traits::each_node_iterator each_node_iterator; typedef typename graph_traits::in_edge_iterator in_edge_iterator; typedef typename graph_traits::NodeIt NodeIt; //typedef typename graph_traits::EdgeIt EdgeIt; typedef typename graph_traits::EachNodeIt EachNodeIt; typedef typename graph_traits::InEdgeIt InEdgeIt; graph_type& G; node_iterator t; //    node_property_vector pred; node_property_vector distance; NodeIt t; //    NodeMap pred; NodeMap distance; /* The distance of the nodes is n, except t for which it is 0. The distance of the Nodes is n, except t for which it is 0. */ reverse_bfs(graph_type& _G, node_iterator _t) : G(_G), t(_t), distance(G, number_of(G.first_node())) { reverse_bfs(graph_type& _G, NodeIt _t) : G(_G), t(_t), distance(G, number_of(G.first_Node())) { distance.put(t,0); } void run() { node_property_vector reached(G, false); NodeMap reached(G, false); reached.put(t, true); std::queue bfs_queue; std::queue bfs_queue; bfs_queue.push(t); while (!bfs_queue.empty()) { node_iterator v=bfs_queue.front(); NodeIt v=bfs_queue.front(); bfs_queue.pop(); for(in_edge_iterator e=G.first_in_edge(v); e.valid(); ++e) { node_iterator w=G.tail(e); for(InEdgeIt e=G.template first(v); e.valid(); ++e) { NodeIt w=G.tail(e); if (!reached.get(w)) { bfs_queue.push(w); int dist(node_iterator v) { int dist(NodeIt v) { return distance.get(v); }
Note: See TracChangeset for help on using the changeset viewer.