开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
schedule.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：3k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

schedule.c：源码内容
  1. //---------------------------------------------------------------
  2. //
  3. //
  4. //  A List Scheduling Algorithm
  5. //
  6. //   S. Naeher (August 1993)
  7. //---------------------------------------------------------------
  9. #include <LEDA/graph_alg.h>
  10. #include <LEDA/node_pq.h>
  12. static int compute_depth(graph& G, node_array<int>& depth);
  14. static void make_acyclic(graph& G)
  15. { node_array<int> dfsnum(G);
  16.   node_array<int> compnum(G);
  17.   DFS_NUM(G,dfsnum,compnum);
  19.   list<edge> back;
  20.   edge e;
  22.   forall_edges(e,G)
  23.   { node v = source(e);
  24.     node w = target(e);
  25.     if (v == w || (dfsnum[v] > dfsnum[w] && compnum[v] < compnum[w]))
  26.       back.append(e);
  27.    }
  29.   forall(e,back) G.del_edge(e);
  30. }
  31.     
  33. void list_schedule(graph& G, int k)
  34. {
  35.   node u;
  36.   node v;
  38.   node_array<int> path(G);     // path[v] = length of longest path starting in v
  40.   node_array<int> degree(G);   // degree[v] = current indegree of v
  42.   list<node> zero_deg;         // set of nodes v with degree[v] = 0
  44.   node_pq<int> Vd(G);
  46.   forall_nodes(v,G) 
  47.   { degree[v] = G.indeg(v);
  48.     if ( G.indeg(v) == 0) zero_deg.append(v);
  49.    }
  51.   int max_depth = compute_depth(G,path);
  53.   forall(v,zero_deg) Vd.insert(v,max_depth-path[v]);
  54.   zero_deg.clear();
  56.   for(int level=0; !Vd.empty(); level++) 
  57.   { 
  58.     //cout << level << ": ";
  60.     for(int i=0; i < k && !Vd.empty(); i++) 
  61.     { v = Vd.del_min();
  62.       //G.print_node(v); 
  63.       //cout <<  " ";
  64.       forall_adj_nodes(u,v)
  65.       if (--degree[u] == 0) zero_deg.append(u);
  66.      }
  67.     //newline;
  69.     forall(v,zero_deg) Vd.insert(v,max_depth-path[v]);
  70.     zero_deg.clear();
  71.   }
  72. }
  75.  
  76. static int compute_depth(graph& G, node_array<int>& depth)
  77. {
  78.   // reverse all edges and compute longest paths in topological order
  79.   // starting in nodes with indegree 0
  80.   // PRECONDITION: G is acyclic
  81.  
  82.   G.rev();  
  83.  
  84.   node_array<int>  degree(G);
  85.   list<node>       zero_deg;
  86.   node v;
  87.   edge e;
  89.   int count = 0;
  90.   int max_depth = 0;
  91.  
  92.   forall_nodes(v,G)
  93.   { depth[v] = 0;
  94.     degree[v] = G.indeg(v);
  95.     if (G.indeg(v) == 0) zero_deg.append(v);
  96.    }
  97.  
  98.   while(! zero_deg.empty())
  99.   { count++;
  100.     v = zero_deg.pop();
  101.     forall_adj_edges(e,v)
  102.     { int  d = depth[v]+1;
  103.       node w = G.target(e);
  104.       if (depth[w] < d) 
  105.       { depth[w] = d;
  106.         if (max_depth < d) max_depth = d;
  107.        }
  108.       if (--degree[w] == 0) zero_deg.append(w);
  109.      }
  110.    }
  112.   if (count < G.number_of_nodes()) 
  113.   { cerr << "Error: cyclic graphn";
  114.     exit(1);
  115.    }
  117.   G.rev();  // restore original graph
  119.   return max_depth;
  121. }
  125. main()
  126. {
  128.   graph G;
  129.   
  130.   test_graph(G);
  131.   int k = read_int("k = ");
  133.   make_acyclic(G);
  135.   cout << "|E| = " << G.number_of_edges() << endl;
  136.   newline;
  139.   float T = used_time();
  140.   list_schedule(G,k);
  141.   cout << string(" %f sec",used_time(T));
  142.   newline;
  144. }