Changeset 243:a85fd87460e3 in lemon-0.x for src/work/marci_graph_demo.cc
- Timestamp:
- 03/25/04 10:42:59 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@342
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci_graph_demo.cc
r168 r243 3 3 #include <string> 4 4 5 #include <list_graph.h h>6 #include <bfs_iterator.h h>7 #include <edmonds_karp.h h>5 #include <list_graph.h> 6 #include <bfs_iterator.h> 7 #include <edmonds_karp.h> 8 8 9 9 using namespace hugo; … … 11 11 int main (int, char*[]) 12 12 { 13 typedef ListGraph::Node Node; 14 typedef ListGraph::Edge Edge; 13 15 typedef ListGraph::NodeIt NodeIt; 14 16 typedef ListGraph::EdgeIt EdgeIt; 15 typedef ListGraph::EachNodeIt EachNodeIt;16 typedef ListGraph::EachEdgeIt EachEdgeIt;17 17 typedef ListGraph::OutEdgeIt OutEdgeIt; 18 18 typedef ListGraph::InEdgeIt InEdgeIt; 19 19 typedef ListGraph::SymEdgeIt SymEdgeIt; 20 20 ListGraph G; 21 std::vector<Node It> vector_of_NodeIts;22 for(int i=0; i!=8; ++i) vector_of_Node Its.push_back(G.addNode());21 std::vector<Node> vector_of_Nodes; 22 for(int i=0; i!=8; ++i) vector_of_Nodes.push_back(G.addNode()); 23 23 for(int i=0; i!=8; ++i) 24 24 for(int j=0; j!=8; ++j) 25 if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Node Its[i], vector_of_NodeIts[j]);25 if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Nodes[i], vector_of_Nodes[j]); 26 26 27 27 std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl; 28 std::cout << "number of nodes: " << count(G.first< EachNodeIt>()) << std::endl;29 30 for( EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {28 std::cout << "number of nodes: " << count(G.first<NodeIt>()) << std::endl; 29 30 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) { 31 31 std::cout << "node " << G.id(i) << std::endl; 32 32 std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; 33 for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {33 for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 34 34 std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") "; 35 35 } … … 37 37 38 38 std::cout<< " "; 39 for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {39 for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 40 40 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 41 41 std::cout<<std::endl; 42 42 43 43 std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " "; 44 for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {44 for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) { 45 45 std::cout << j << " "; } 46 46 std::cout << std::endl; 47 47 48 48 std::cout<< " "; 49 for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {49 for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) { 50 50 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 51 51 std::cout<<std::endl; 52 52 53 53 std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " "; 54 for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {54 for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) { 55 55 std::cout << j << " "; } 56 56 std::cout<<std::endl; 57 57 58 58 std::cout<< " "; 59 for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {59 for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) { 60 60 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 61 61 std::cout<<std::endl; … … 63 63 64 64 std::cout << "all edges: "; 65 for(E achEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {65 for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) { 66 66 std::cout << i << " "; 67 67 } … … 70 70 std::cout << "node property array test" << std::endl; 71 71 ListGraph::NodeMap<int> my_property_vector(G); 72 EachNodeIt v;73 G. getFirst(v);72 NodeIt v; 73 G.first(v); 74 74 my_property_vector.set(v, 42); 75 my_property_vector.set( ++G.first<EachNodeIt>(), 314);76 my_property_vector.set( ++++G.first<EachNodeIt>(), 1956);77 my_property_vector.set(vector_of_Node Its[3], 1989);78 my_property_vector.set(vector_of_Node Its[4], 2003);79 my_property_vector.set(vector_of_Node Its[7], 1978);75 my_property_vector.set(G.next(G.first<NodeIt>()), 314); 76 my_property_vector.set(G.next(G.next(G.first<NodeIt>())), 1956); 77 my_property_vector.set(vector_of_Nodes[3], 1989); 78 my_property_vector.set(vector_of_Nodes[4], 2003); 79 my_property_vector.set(vector_of_Nodes[7], 1978); 80 80 std::cout << "some node property values..." << std::endl; 81 for( EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {81 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) { 82 82 std::cout << my_property_vector.get(i) << std::endl; 83 83 } … … 85 85 int _ii=1; 86 86 ListGraph::EdgeMap<int> my_edge_property(G); 87 for(E achEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {87 for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) { 88 88 my_edge_property.set(i, _i); 89 89 _i*=_ii; ++_ii; … … 91 91 92 92 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl; 93 for(E achEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) {93 for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) { 94 94 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " "; 95 95 } … … 97 97 /* 98 98 std::cout << "bfs from the first node" << std::endl; 99 bfs<ListGraph> bfs_test(G, G.first< EachNodeIt>());99 bfs<ListGraph> bfs_test(G, G.first<NodeIt>()); 100 100 bfs_test.run(); 101 101 std::cout << "reached: "; 102 for( EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {102 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) { 103 103 std::cout << bfs_test.reached.get(i) << " "; 104 104 } 105 105 std::cout<<std::endl; 106 106 std::cout << "dist: "; 107 for( EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {107 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) { 108 108 std::cout << bfs_test.dist.get(i) << " "; 109 109 } … … 114 114 ListGraph flowG; 115 115 116 Node Its=flowG.addNode();117 Node Itv1=flowG.addNode();118 Node Itv2=flowG.addNode();119 Node Itv3=flowG.addNode();120 Node Itv4=flowG.addNode();121 Node Itt=flowG.addNode();116 Node s=flowG.addNode(); 117 Node v1=flowG.addNode(); 118 Node v2=flowG.addNode(); 119 Node v3=flowG.addNode(); 120 Node v4=flowG.addNode(); 121 Node t=flowG.addNode(); 122 122 123 123 ListGraph::NodeMap<std::string> node_name(flowG); … … 129 129 node_name.set(t, "t"); 130 130 131 Edge Its_v1=flowG.addEdge(s, v1);132 Edge Its_v2=flowG.addEdge(s, v2);133 Edge Itv1_v2=flowG.addEdge(v1, v2);134 Edge Itv2_v1=flowG.addEdge(v2, v1);135 Edge Itv1_v3=flowG.addEdge(v1, v3);136 Edge Itv3_v2=flowG.addEdge(v3, v2);137 Edge Itv2_v4=flowG.addEdge(v2, v4);138 Edge Itv4_v3=flowG.addEdge(v4, v3);139 Edge Itv3_t=flowG.addEdge(v3, t);140 Edge Itv4_t=flowG.addEdge(v4, t);131 Edge s_v1=flowG.addEdge(s, v1); 132 Edge s_v2=flowG.addEdge(s, v2); 133 Edge v1_v2=flowG.addEdge(v1, v2); 134 Edge v2_v1=flowG.addEdge(v2, v1); 135 Edge v1_v3=flowG.addEdge(v1, v3); 136 Edge v3_v2=flowG.addEdge(v3, v2); 137 Edge v2_v4=flowG.addEdge(v2, v4); 138 Edge v4_v3=flowG.addEdge(v4, v3); 139 Edge v3_t=flowG.addEdge(v3, t); 140 Edge v4_t=flowG.addEdge(v4, t); 141 141 142 142 ListGraph::EdgeMap<int> cap(flowG); … … 155 155 std::cout << "on directed graph graph" << std::endl; //<< flowG; 156 156 std::cout << "names and capacity values" << std::endl; 157 for( EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {157 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 158 158 std::cout << node_name.get(i) << ": "; 159 159 std::cout << "out edges: "; 160 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)160 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 161 161 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; 162 162 std::cout << "in edges: "; 163 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)163 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 164 164 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; 165 165 std::cout << std::endl; … … 175 175 //flowG.setHead(v3_t, s); 176 176 /* 177 for( EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {177 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 178 178 std::cout << node_name.get(i) << ": "; 179 179 std::cout << "out edges: "; 180 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)180 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 181 181 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; 182 182 std::cout << "in edges: "; 183 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)183 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 184 184 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; 185 185 std::cout << std::endl; 186 186 } 187 187 188 for(E achEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) {188 for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 189 189 std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " "; 190 190 } 191 191 */ 192 192 /* 193 while (flowG. first<EachEdgeIt>().valid()) {194 flowG.deleteEdge(flowG.first<E achEdgeIt>());195 for( EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {193 while (flowG.valid(flowG.first<EdgeIt>())) { 194 flowG.deleteEdge(flowG.first<EdgeIt>()); 195 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 196 196 std::cout << node_name.get(i) << ": "; 197 197 std::cout << "out edges: "; 198 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)198 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 199 199 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; 200 200 std::cout << "in edges: "; 201 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)201 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 202 202 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; 203 203 std::cout << std::endl; … … 205 205 } 206 206 207 while (flowG. first<EachNodeIt>().valid()) {208 flowG.deleteNode(flowG.first< EachNodeIt>());209 for( EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {207 while (flowG.valid(flowG.first<NodeIt>())) { 208 flowG.deleteNode(flowG.first<NodeIt>()); 209 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 210 210 std::cout << node_name.get(i) << ": "; 211 211 std::cout << "out edges: "; 212 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)212 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 213 213 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; 214 214 std::cout << "in edges: "; 215 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)215 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 216 216 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; 217 217 std::cout << std::endl; … … 228 228 /* 229 229 max_flow_test.augmentOnBlockingFlow<ListGraph>(); 230 for(E achEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {230 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 231 231 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") "; 232 232 } 233 233 std::cout<<std::endl; 234 234 max_flow_test.augmentOnBlockingFlow<ListGraph>(); 235 for(E achEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {235 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 236 236 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") "; 237 237 } … … 241 241 //std::cout << "maximum flow: "<< std::endl; 242 242 while (max_flow_test.augmentOnShortestPath()) { 243 for(E achEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {243 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 244 244 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") "; 245 245 } … … 250 250 /* 251 251 { 252 std::list<Node It> S;252 std::list<Node> S; 253 253 S.push_back(s); S.push_back(v3); 254 std::list<Node It> T;254 std::list<Node> T; 255 255 T.push_back(t); 256 256 … … 260 260 261 261 std::cout << "maximum flow: "<< std::endl; 262 for(E achEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {262 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 263 263 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") "; 264 264 }
Note: See TracChangeset
for help on using the changeset viewer.