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

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

数值算法/人工智能

开发平台：

MultiPlatform

Is_Bidirected.w：源码内容
  1. documentstyle[11pt,comments]{cweb}
  3. textwidth=6.5in
  4. textheight=9in
  5. oddsidemargin=0in
  6. topmargin=0in
  8. begin{document}
  10. markright{fbox{protecttiny version of today}}
  11. pagestyle{myheadings}
  13. @* Testing Bidirectedness.
  15. noindent Let $G$ be a simple graph. We test whether $G$ is bidirected
  16. and (if required) also establish the correspondence between edges and
  17. their reversals. We first bucket--sort the edges according to their
  18. target node, then according to their source node. The result is 
  19. maintained in a list. Afterwards we sort the edges again, but first 
  20. according to their source node and then according to their target node.
  21. The result is maintained in a second list. Since |bucket sort| is 
  22. stable,
  23. in a bidirected graph the position of an edge in the first list
  24. corresponds to the position of the reversal edge in the second
  25. list. The following procedure 
  26. checks this relation. 
  27. As soon as the tested edges do not correspond, false is returned. 
  29. @c
  30. bool is_bidirected(const graph& G)     
  31. {
  32.  // computes for every edge e = (v,w) in G its reversal reversal[e] = (w,v)
  33.  // in G ( nil if not present). Returns true if every edge has a
  34.  // reversal and false otherwise.
  36.   int n = G.max_i_node();
  37.   int count = 0;
  39.   edge e,r;
  41.   list<edge> El = G.all_edges();
  42.   El.bucket_sort(0,n,&edge_ord2);
  43.   El.bucket_sort(0,n,&edge_ord1);
  44.   
  45.   list<edge> El1 = G.all_edges();
  46.   El1.bucket_sort(0,n,&edge_ord1);
  47.   El1.bucket_sort(0,n,&edge_ord2);
  50.   // merge El and El1 to find corresponding edges
  52.   while (! El.empty() && ! El1.empty())
  53.   { e = El.head();
  54.     r = El1.head();
  56.     if ((target(r) == source(e))&&(source(r) == target(e))) 
  57.          { El1.pop();
  58.            El.pop();
  59.           }
  60.     else
  61.          return false;
  62.   }
  63.   return true;
  65. }
  67. @ The following procedure 
  68. also establishes the correspondence between edges and their reversals.
  69. For every edge |e = (v, w)| in $G$ it computes its reversal
  70. |reversal[e] = (w,v)| if existing in $G$ (|nil| otherwise). If every
  71. edge has a reversal it returns |true| and |false| otherwise.
  74. @c
  76. bool is_bidirected(const graph& G, edge_array<edge>& reversal)     
  77. {
  78.  // computes for every edge e = (v,w) in G its reversal reversal[e] = (w,v)
  79.  // in G ( nil if not present). Returns true if every edge has a
  80.  // reversal and false otherwise.
  82.   int n = G.max_i_node();
  83.   int count = 0;
  85.   edge e,r;
  87.   forall_edges(e,G) reversal[e] = 0;
  89.   list<edge> El = G.all_edges();
  90.   El.bucket_sort(0,n,&edge_ord2);
  91.   El.bucket_sort(0,n,&edge_ord1);
  92.   
  93.   list<edge> El1 = G.all_edges();
  94.   El1.bucket_sort(0,n,&edge_ord1);
  95.   El1.bucket_sort(0,n,&edge_ord2);
  98.   // merge El and El1 to find corresponding edges
  100.   while (! El.empty() && ! El1.empty())
  101.   { e = El.head();
  102.     r = El1.head();
  105.     if (target(r) == source(e))
  106.       if (source(r) == target(e))
  107.          { reversal[e] = r;
  108.            El1.pop();
  109.            El.pop();
  110.            count++;
  111.           }
  112.       else
  113.          if (index(source(r)) < index(target(e)))
  114.              El1.pop();
  115.          else
  116.              El.pop();
  118.     else
  119.       if (index(target(r)) < index(source(e)))
  120.           El1.pop();
  121.       else
  122.           El.pop();
  124.     }
  125.   return (count == G.number_of_edges());
  127. }
  128.  
  129. @
  130. end{document}