Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
subgraph.c
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 1k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

subgraph.c：Code Content
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  5. GRAPH<int,int> shortest_path_tree(GRAPH<int,int>& G, edge_array<int>& cost)
  6. {
  7.   // returns a shortest-paths tree  as a subgraph of G
  9.   node_array<int> dist(G);
  10.   node_array<edge> pred(G);
  12.   node s = G.first_node();
  14.   DIJKSTRA(G,s,cost,dist,pred);
  16.   list<edge> el;
  18.   node v;
  19.   forall_nodes(v,G) if (pred[v]!=0) el.append(pred[v]);
  21.   return GRAPH<int,int>(G,G.all_nodes(),el);   // subgraph constructor
  22. }
  26. main()
  28. { GRAPH<int,int> G;
  30.   test_graph(G);
  32.   edge_array<int> cost(G);
  34.   int a = read_int("a = ");
  35.   int b = read_int("b = ");
  37.   random_source ran(a,b);
  40.   edge e;
  41.   forall_edges(e,G) cost[e] = G[e] = ran();
  44.   GRAPH<int,int> S = shortest_path_tree(G,cost);
  47.   G.print("graph G");
  48.   newline; 
  50.   S.print("subgraph S");
  51.   newline; 
  54.   edge_array<int> cost1(S);
  56.   forall_edges(e,S) cost1[e] = S[e];  
  58.   GRAPH<int,int> S1 = shortest_path_tree(S,cost1);
  60.   S1.print("subgraph S1");
  61.   newline;
  63. return 0;
  64. }