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

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

数值算法/人工智能

开发平台：

MultiPlatform

_min_cut.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _min_cut.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. /* This file has been automatically generated from "min_cut.w"
  15.    by CTANGLE (Version 3.1 [km2c]) */
  17. #include <LEDA/graph_alg.h>
  18. #include <LEDA/ugraph.h>
  19. #include <LEDA/stream.h>
  20. #include <LEDA/node_pq.h>
  22. list <node >MIN_CUT(const graph &G0, edge_array <int >&weight)
  23. {
  24.   typedef list <node >nodelist;
  25.   UGRAPH < nodelist *, int >G;
  26.   node v, x;
  27.   edge e;
  28.   node_array <node >partner(G0);
  29.   forall_nodes (x, G0) {
  30.     partner[x] = G.new_node(new nodelist);
  31.     G[partner[x]]->append(x);
  32.   }
  34.   forall_edges (e, G0)
  35.     if (source(e) != target(e))
  36.       G.new_edge(partner[source(e)], partner[target(e)], weight[e]);
  40.   node a = G.first_node();
  41.   int n = G.number_of_nodes();
  42.   list <node >best_cut;
  43.   int best_value = MAXINT;
  44.   int cut_weight;
  48. /* |n| is now the number of nodes of the current graph and |a|
  49.      is a fixed vertex */
  50.   while (n >= 2) {
  52.     node t = a;
  53.     node s;
  54.     node_array <bool >in_PQ(G);
  56.     node_pq <int >PQ(G);
  58.     forall_nodes (v, G)
  59.       if (v != a) {
  60. PQ.insert(v, 0); /* $w(v,A) = 0$ if there is no edge
  61.  * connecting |v| to |A| */
  62. in_PQ[v] = true;
  63.       }
  64.       else {
  65. in_PQ[v] = false;
  66.       }
  67.     {
  68.       forall_adj_edges (e, a)
  69. PQ.decrease_inf(G.opposite(a, e), PQ.inf(G.opposite(a, e)) - G[e]);
  70.     }
  71.     while (!PQ.empty()) {
  72.       s = t;
  73.       cut_weight = -PQ.inf(PQ.find_min());
  74.       t = PQ.del_min();
  75.       in_PQ[t] = false;
  76.       forall_adj_edges (e, t) {
  77. if (in_PQ[v = G.opposite(t, e)])
  78.   PQ.decrease_inf(v, PQ.inf(v) - G[e]);
  80.       }
  81.     }
  83.     ;
  85.     if (cut_weight < best_value) {
  86.       best_cut = *(G[t]);
  87.       best_value = cut_weight;
  88.     }
  90.     G[s]->conc(*(G[t]));
  92.     node_array <edge >s_edge(G, nil);
  93.     {
  94.       forall_adj_edges (e, s)
  95. s_edge[G.opposite(s, e)] = e;
  96.     }
  97.     {
  98.       forall_adj_edges (e, t) {
  99. if (s_edge[v = G.opposite(t, e)] == nil)
  100.   G.new_edge(s, v, G[e]);
  101. else
  102.   G[s_edge[v]] += G[e];
  103.       }
  104.     }
  106.     delete G[t];
  107.     G.del_node(t);
  110.     ;
  111.     n--;
  114.   }
  116.   return best_cut;
  119. }