home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / prog / graph / subgraph.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  988 b   |  65 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  3.  
  4. declare2(GRAPH,int,int)
  5.  
  6. GRAPH(int,int) shortest_path_tree(GRAPH(int,int)& G, edge_array(int)& cost)
  7. {
  8.   // returns a shortest-paths tree  as a subgraph of G
  9.  
  10.   node_array(int) dist(G);
  11.   node_array(edge) pred(G);
  12.  
  13.   node s = G.first_node();
  14.  
  15.   DIJKSTRA(G,s,cost,dist,pred);
  16.  
  17.   edgelist el;
  18.  
  19.   node v;
  20.   forall_nodes(v,G) if (pred[v]!=0) el.append(pred[v]);
  21.  
  22.   return GRAPH(int,int)(G,G.all_nodes(),el);   // subgraph constructor
  23. }
  24.  
  25.  
  26.  
  27.  
  28. main()
  29.  
  30. { GRAPH(int,int) G;
  31.  
  32.   test_graph(G);
  33.  
  34.   edge_array(int) cost(G);
  35.  
  36.   int a = read_int("a = ");
  37.   int b = read_int("b = ");
  38.  
  39.   init_random();
  40.  
  41.   edge e;
  42.   forall_edges(e,G) cost[e] = G[e] = random(a,b);
  43.  
  44.  
  45.   GRAPH(int,int) S = shortest_path_tree(G,cost);
  46.  
  47.  
  48.   G.print("graph G");
  49.   newline; 
  50.  
  51.   S.print("subgraph S");
  52.   newline; 
  53.  
  54.  
  55.   edge_array(int) cost1(S);
  56.  
  57.   forall_edges(e,S) cost1[e] = S[e];  
  58.  
  59.   GRAPH(int,int) S1 = shortest_path_tree(S,cost1);
  60.  
  61.   S1.print("subgraph S1");
  62.   newline;
  63.  
  64. }
  65.