home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / prog / graph / maxflow.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  932 b   |  55 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  3.  
  4.  
  5. declare2(GRAPH,int,int);
  6.  
  7. main()
  8. {
  9.  
  10. GRAPH(int,int) G;
  11.  
  12. test_graph(G);
  13.  
  14. edge_array(int)  cap(G,0);
  15. edge_array(int)  flow(G,0);
  16.  
  17. edge_array(real)  cap1(G,0);
  18. edge_array(real)  flow1(G,0);
  19.  
  20. int a = read_int("a = ");
  21. int b = read_int("b = ");
  22.  
  23. edge e;
  24.  
  25. init_random();
  26.   forall_edges(e,G) cap1[e] = G[e] = cap[e] = random(a,b);
  27.  
  28. node s = G.first_node();
  29. node t = G.last_node();
  30.  
  31. float T = used_time();
  32.  
  33. cout << "MAX_FLOW (int)    ";
  34. cout.flush();
  35. int val = MAX_FLOW(G,s,t,cap,flow) ;
  36. cout << form("flow = %d     time: %6.2f sec  \n",val,used_time(T));
  37. newline;
  38.  
  39. cout << "MAX_FLOW (reals)  ";
  40. cout.flush();
  41. real val1 = MAX_FLOW(G,s,t,cap1,flow1);
  42. cout << form("flow = %f     time: %6.2f sec  \n",~val1,used_time(T));
  43. newline;
  44.  
  45. if (Yes("show flow values? "))
  46. forall_edges(e,G) 
  47.   { G.print_edge(e);
  48.     cout << form(" flow = %6d  flow1 = %4.2f\n",flow[e],~flow1[e]);
  49.   }
  50. newline;
  51.  
  52. }
  53.  
  54.  
  55.