Category

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

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

Is_Bidirected.w：Code Content
  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}