home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph / _planar_.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  5.3 KB  |  280 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _planar_map.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/planar_map.h>
  18.  
  19.  
  20. declare(edge_array,edge)
  21. declare(edge_array,bool)
  22. declare(node_array,bool)
  23.  
  24. extern bool compute_correspondence(const graph&, edge_array(edge)&);
  25.  
  26. list(edge) planar_map::adj_edges(face f) const
  27. { list(edge) result(f->head);
  28.   edge e1 = succ_face_edge(f->head);
  29.   while (e1!=f->head)
  30.   { result.append(e1);
  31.     e1 = succ_face_edge(e1);
  32.    }
  33.   return result;
  34.  }
  35.  
  36. list(node) planar_map::adj_nodes(face f) const
  37. { list(node) result(source(f->head));
  38.   edge e1 = succ_face_edge(f->head);
  39.   while (e1!=f->head)
  40.   { result.append(source(e1));
  41.     e1 = succ_face_edge(e1);
  42.    }
  43.   return result;
  44.  }
  45.  
  46. list(face) planar_map::adj_faces(node v) const
  47. { list(face) result;
  48.   edge e;
  49.   forall_adj_edges(e,v) result.append(adj_face(e));
  50.   return result;
  51.  }
  52.  
  53. face  planar_map::new_face(ent i) 
  54. { 
  55.   //copy_face_entry(i);
  56.  
  57.   face f=new i_face(i,this);
  58.   f->loc=F_list.append(f);
  59.   return f;
  60.  }
  61.  
  62. /*
  63. node planar_map::split_edge(edge e)
  64. { edge r = get_rev(e);
  65.  
  66.   node v = source(e);
  67.   node w = target(e);
  68.  
  69.   node u = graph::new_node();
  70.  
  71. }
  72. */
  73.  
  74. edge planar_map::new_edge(edge e1, edge e2, ent face_i)
  75. { 
  76. /*
  77.     cout << "NEW_EDGE:\n";
  78.     print_edge(e1); cout << " F = " << int(adj_face(e1)->inf) << "\n";
  79.     print_edge(e2); cout << " F = " << int(adj_face(e2)->inf) << "\n";
  80.     newline;
  81. */
  82.  
  83.   if (adj_face(e1) != adj_face(e2)) 
  84.     error_handler(1,"planar_map::new_edge: new edge must split a face."); 
  85.  
  86.   face F = adj_face(e1);
  87.   face f = new_face(face_i);
  88.  
  89.   edge y = graph::new_edge(e1,source(e2),before);
  90.   F->head = y;
  91.   get_face(y) = F;
  92.   
  93.  
  94.   edge x = graph::new_edge(e2,source(e1),before);
  95.   f->head = x;
  96.  
  97.   get_rev(x) = y;
  98.   get_rev(y) = x;
  99.  
  100.   node v = source(x);
  101.   while (target(x) != v) 
  102.   { get_face(x) = f;
  103.     x = succ_face_edge(x);
  104.    }
  105.  
  106.   return y;
  107. }
  108.  
  109. void planar_map::del_edge(edge x, ent face_i)
  110. {
  111.   edge y  = reverse(x);
  112.   face F1 = adj_face(x);
  113.   face F2 = adj_face(y);
  114.  
  115.   edge e = succ_face_edge(y);
  116.  
  117.   F1->inf = face_i;
  118.  
  119.   if (F1!=F2)
  120.   { edge e = succ_face_edge(y);
  121.     F1->head = e;
  122.     while (e!=y)
  123.     { get_face(e) = F1;
  124.       e = succ_face_edge(e);
  125.      }
  126.  
  127.     del_face(F2);
  128.    }
  129.   else
  130.   { e = succ_face_edge(e);
  131.  
  132.     if (e!=y) // no isolated edge
  133.       F1->head = e;   
  134.     else 
  135.       del_face(F1);
  136.  
  137.    }
  138.  
  139.     graph::del_edge(x);
  140.     graph::del_edge(y);
  141.  
  142. }
  143.  
  144. /*
  145. void planar_map::init_entries()
  146. { node v;
  147.   forall_nodes(v,*this) init_node_entry(entry(v));
  148.   face f;
  149.   forall(f,F_list) init_face_entry(f->inf);
  150.  }
  151. */
  152.  
  153.  
  154. planar_map::~planar_map() 
  155. { face f;
  156.   forall(f,F_list) 
  157.   { clear_face_entry(f->inf);
  158.     delete f;
  159.    }
  160.  
  161.  }
  162.  
  163.  
  164. planar_map::planar_map(const graph& G) : graph(G)
  165.  
  166. // input planar embedded graph  represented by a directed graph G 
  167. // i.e., for each node v of G the adjacent edges are sorted 
  168. // counter-clockwise, 
  169. // computes planar map representation (faces!)
  170. // For each face F, one of its edge entries is copied into F
  171.  
  172. { 
  173.   edge e,e1;
  174.  
  175. /*
  176.   if (!PLANAR(*this)) error_handler(1,"planar_map: Graph is not planar."); 
  177. */
  178.  
  179.   edge_array(edge) Rev(*this);
  180.  
  181.   if (compute_correspondence(*this,Rev) == false)
  182.    { print();
  183.      error_handler(999,"planar_map: cannot find reversal edges");;
  184.     }
  185.  
  186.   forall_edges(e,*this) get_rev(e) = Rev[e];
  187.  
  188.  
  189.   Rev.clear();
  190.  
  191.   // compute faces
  192.  
  193.   edge_array(bool) F(*this,false);
  194.  
  195.   forall_edges(e,*this)
  196.    if (!F[e])
  197.     { F[e] = true;
  198.       face f = new_face(e->contents);  // copy entry of first edge into face
  199.       e->contents =  f;
  200.       f->head = e;
  201.       e1 = succ_face_edge(e);
  202.       while (e1 != e)
  203.       { G.clear_edge_entry(e1->contents);
  204.         e1->contents = f;
  205.         F[e1] = true;
  206.         e1 = succ_face_edge(e1);
  207.        }
  208.      } 
  209.  
  210.  
  211. } 
  212.  
  213. list(edge) planar_map::triangulate()
  214. {
  215.   node v,w;
  216.   edge e,e1,e2,e3;
  217.  
  218.   list(edge) L;
  219.  
  220.   node_array(bool) marked(*this,false);
  221.  
  222.   forall_nodes(v,*this)
  223.   {
  224.     edgelist El = adj_edges(v);
  225.  
  226.     forall(e,El) marked[target(e)] = true;
  227.  
  228.     forall(e,El)
  229.     { 
  230.       e1 = e;
  231.       e2 = succ_face_edge(e1);
  232.       e3 = succ_face_edge(e2);
  233.  
  234.       face F = get_face(e1);
  235.  
  236.       while (target(e3) != v)
  237.       { 
  238.  
  239.         // e1,e2 and e3 are the first three edges in a clockwise 
  240.         // traversal of a face incident to v and t(e3) is not equal
  241.         // to v.
  242.  
  243.         if ( !marked[target(e2)] )
  244.         { 
  245.           // we mark w and add the edge {v,w} inside F, i.e., after
  246.           // dart e1 at v and after dart e3 at w.
  247.  
  248.           marked[target(e2)] = true;
  249.   
  250.           e1 = new_edge(e1,e3,F->inf);
  251.           e2 = e3;
  252.           e3 = succ_face_edge(e2);
  253.  
  254.           L.append(e1);
  255.         }
  256.         else
  257.         { // we add the edge {source(e2),target(e3)} inside F, i.e.,
  258.           // after dart e2 at source(e2) and before dart 
  259.           // reversal_of[e3] at target(e3).
  260.  
  261.           e3 = succ_face_edge(e3); 
  262.  
  263.           e2 = new_edge(e2,e3,F->inf);
  264.  
  265.           L.append(e2);
  266.  
  267.         }
  268.       } //end of while
  269.  
  270.     } //end of stepping through incident faces
  271.  
  272.    forall_adj_nodes(w,v) marked[w] = false;
  273.  
  274.   } // end of stepping through nodes
  275.  
  276. return L;
  277.  
  278. } //end of triangulation
  279.  
  280.