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

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

数值算法/人工智能

开发平台：

MultiPlatform

_planar.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _planar.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #include <LEDA/stack.h>
  14. #include <LEDA/graph.h>
  15. #include <LEDA/graph_alg.h>
  17. static void dfs_in_make_biconnected_graph(graph & G, node v, 
  18.   list<edge>& new_edges, int &dfs_count,
  19.   node_array < bool > &reached,
  20.   node_array < int >&dfsnum, node_array < int >&lowpt,
  21.   node_array < node > &parent);
  23. const int left = 1;
  24. const int right = 2;
  26. static void dfs_in_reorder(list < edge > &Del, node v, int &dfs_count,
  27.   node_array < bool > &reached,
  28.   node_array < int >&dfsnum,
  29.   node_array < int >&lowpt1, node_array < int >&lowpt2,
  30.   node_array < node > &parent);
  32. class block
  33. {
  34.   private:
  35.   list < int >Latt, Ratt; /* list of attachments */
  36.    list < edge > Lseg, Rseg; /* list of segments represented by their *
  37.  * defining edges */
  39.    public:
  41.    block(edge e, list < int >&A) {
  42.     Lseg.append(e);
  43.     Latt.conc(A);
  44. /* the other two lists are empty */
  45.   } ~block() {
  46.   }
  48.   void flip() {
  49.     list < int >ha;
  50.      list < edge > he;
  51. /* we first interchange |Latt| and |Ratt| and then |Lseg| and |Rseg| */
  52.      ha.conc(Ratt);
  53.      Ratt.conc(Latt);
  54.      Latt.conc(ha);
  55.      he.conc(Rseg);
  56.      Rseg.conc(Lseg);
  57.      Lseg.conc(he);
  58.   } int head_of_Latt() {
  59.     return Latt.head();
  60.   }
  61.   bool empty_Latt() {
  62.     return Latt.empty();
  63.   }
  64.   int head_of_Ratt() {
  65.     return Ratt.head();
  66.   }
  67.   bool empty_Ratt() {
  68.     return Ratt.empty();
  69.   }
  70.   bool left_interlace(stack < block * >&S) {
  71. /* check for interlacing with the left side of the topmost block of
  72.  * |S| */
  73.     if (Latt.empty())
  74.       error_handler(1, "Latt is never empty");
  76.     if (!S.empty() && !((S.top())->empty_Latt()) &&
  77.       Latt.tail() < (S.top())->head_of_Latt())
  78.       return true;
  79.     else
  80.       return false;
  81.   }
  82.   bool right_interlace(stack < block * >&S) {
  83. /* check for interlacing with the right side of the topmost block of
  84.  * |S| */
  85.     if (Latt.empty())
  86.       error_handler(1, "Latt is never empty");
  88.     if (!S.empty() && !((S.top())->empty_Ratt()) &&
  89.       Latt.tail() < (S.top())->head_of_Ratt())
  90.       return true;
  91.     else
  92.       return false;
  93.   }
  94.   void combine(block * Bprime) {
  95. /* add block Bprime to the rear of |this| block */
  96.     Latt.conc(Bprime->Latt);
  97.     Ratt.conc(Bprime->Ratt);
  98.     Lseg.conc(Bprime->Lseg);
  99.     Rseg.conc(Bprime->Rseg);
  100.     delete(Bprime);
  101.   } bool clean(int dfsnum_w, edge_array < int >&alpha) {
  102. /* remove all attachments to |w|; there may be several */
  103.     while (!Latt.empty() && Latt.head() == dfsnum_w)
  104.       Latt.pop();
  105.     while (!Ratt.empty() && Ratt.head() == dfsnum_w)
  106.       Ratt.pop();
  108.     if (!Latt.empty() || !Ratt.empty())
  109.       return false;
  111. /*|Latt| and |Ratt| are empty; we record the placement of the subsegments
  112.  * in |alpha|. */
  114.     edge e;
  115.      forall(e, Lseg) alpha[e] = left;
  117.      forall(e, Rseg) alpha[e] = right;
  119.      return true;
  120.   }
  121.   void add_to_Att(list < int >&Att, int dfsnum_w0, edge_array < int >&alpha) {
  122. /* add the block to the rear of |Att|. Flip if necessary */
  123.     if (!Ratt.empty() && head_of_Ratt() > dfsnum_w0)
  124.       flip();
  126.     Att.conc(Latt);
  127.     Att.conc(Ratt);
  128. /* This needs some explanation. Note that |Ratt| is either empty
  129.  * or ${w0}$. Also if |Ratt| is non-empty then all subsequent sets are contained
  130.  * in ${w0}$. So we indeed compute an ordered set of attachments. */
  132.     edge e;
  133.      forall(e, Lseg) alpha[e] = left;
  135.      forall(e, Rseg) alpha[e] = right;
  136.   }
  137. };
  140. list<edge> make_biconnected_graph(graph & G)
  141. {
  142.   node v;
  143.   node_array < bool > reached(G, false);
  144.   list<edge> new_edges;
  145.   node u = G.first_node();
  147.   forall_nodes(v, G) {
  148.     if (!reached[v]) { /* explore the connected component with root
  149.  * * |v| */
  150.       DFS(G, v, reached);
  151.       if (u != v) { /* link |v|'s component to the first *
  152.  * component */
  153. new_edges.append(G.new_edge(u,v));
  154. new_edges.append(G.new_edge(v,u));
  155.       } /* end if */
  156.     } /* end not reached */
  157.   } /* end forall */
  159. /* |G| is now connected. We next make it biconnected. */
  161.   forall_nodes(v, G) reached[v] = false;
  162.   node_array < int >dfsnum(G);
  163.   node_array < node > parent(G, nil);
  164.   int dfs_count = 0;
  165.   node_array < int >lowpt(G);
  167.   dfs_in_make_biconnected_graph(G, G.first_node(), new_edges,dfs_count, reached, dfsnum, lowpt, parent);
  169.   return new_edges;
  170. } /* end |make_biconnected_graph| */
  172. static void dfs_in_make_biconnected_graph(graph & G, node v, 
  173.   list<edge>& new_edges, int &dfs_count,
  174.   node_array < bool > &reached,
  175.   node_array < int >&dfsnum, node_array < int >&lowpt,
  176.   node_array < node > &parent)
  177. {
  179.   node w;
  180.   edge e;
  182.   dfsnum[v] = dfs_count++;
  183.   lowpt[v] = dfsnum[v];
  184.   reached[v] = true;
  186.   if (!G.first_adj_edge(v))
  187.     return; /* no children */
  189.   node u = target(G.first_adj_edge(v)); /* first child */
  191.   forall_adj_edges(e, v) {
  192.     w = target(e);
  193.     if (!reached[w]) { /* e is a tree edge */
  194.       parent[w] = v;
  195.       dfs_in_make_biconnected_graph(G, w, new_edges, dfs_count, reached, dfsnum, lowpt, parent);
  196.       if (lowpt[w] == dfsnum[v]) { /* |v| is an articulation point. We * 
  197.  * now add an edge. If |w| is the *
  198.  * first child and |v| has a parent * 
  199.  * then we connect |w| and *
  200.  * |parent[v]|, if |w| is a first *
  201.  * child and |v| has no parent then * 
  202.  * we do nothing. If |w| is not the * 
  203.  * first child then we connect |w| to 
  204.  * 
  205.  * * the first child. The net effect
  206.  * of  * all of this is to link all * 
  207.  * children of an articulation point
  208.  * * to the first child and the first
  209.  * * child to the parent (if it
  210.  * exists)  */
  211. if (w == u && parent[v]) {
  212.   new_edges.append(G.new_edge(w, parent[v]));
  213.   new_edges.append(G.new_edge(parent[v], w));
  214. }
  215. if (w != u) {
  216.   new_edges.append(G.new_edge(u,w));
  217.   new_edges.append(G.new_edge(w,u));
  218. }
  219.       } /* end if lowpt = dfsnum */
  220.       lowpt[v] = Min(lowpt[v], lowpt[w]);
  221.     } /* end tree edge */
  222.     else
  223.       lowpt[v] = Min(lowpt[v], dfsnum[w]); /* non tree edge */
  224.   } /* end forall */
  225. } /* end dfs */
  227. static void reorder(graph & G, node_array < int >&dfsnum,
  228.   node_array < node > &parent)
  229. {
  230.   node v;
  231.   node_array < bool > reached(G, false);
  232.   int dfs_count = 0;
  233.   list < edge > Del;
  234.   node_array < int >lowpt1(G), lowpt2(G);
  236.   dfs_in_reorder(Del, G.first_node(), dfs_count, reached, dfsnum, lowpt1, lowpt2, parent);
  238. /* remove forward and reversals of tree edges */
  240.   edge e;
  241.   forall(e, Del) G.del_edge(e);
  243. /* we now reorder adjacency lists as described in cite[page 101]{Me:book} */
  245.   node w;
  246.   edge_array<int> cost(G);
  247.   forall_edges(e, G) {
  248.     v = source(e);
  249.     w = target(e);
  250.     cost[e] = ((dfsnum[w] < dfsnum[v]) ?
  251.       2 * dfsnum[w] :
  252.       ((lowpt2[w] >= dfsnum[v]) ?
  253. 2 * lowpt1[w] : 2 * lowpt1[w] + 1));
  254.   }
  256.   G.sort_edges(cost);
  258. }
  260. static void dfs_in_reorder(list < edge > &Del, node v, int &dfs_count,
  261.   node_array < bool > &reached,
  262.   node_array < int >&dfsnum,
  263.   node_array < int >&lowpt1, node_array < int >&lowpt2,
  264.   node_array < node > &parent)
  265. {
  266.   node w;
  267.   edge e;
  269.   dfsnum[v] = dfs_count++;
  270.   lowpt1[v] = lowpt2[v] = dfsnum[v];
  271.   reached[v] = true;
  272.   forall_adj_edges(e, v) {
  273.     w = target(e);
  274.     if (!reached[w]) { /* e is a tree edge */
  275.       parent[w] = v;
  276.       dfs_in_reorder(Del, w, dfs_count, reached, dfsnum, lowpt1, lowpt2,
  277. parent);
  278.       lowpt1[v] = Min(lowpt1[v], lowpt1[w]);
  279.     } /* end tree edge */
  280.     else {
  281.       lowpt1[v] = Min(lowpt1[v], dfsnum[w]); /* no effect for forward *
  282.  * edges */
  283.       if ((dfsnum[w] >= dfsnum[v]) || w == parent[v])
  284. /* forward edge or reversal of tree edge */
  285. Del.append(e);
  286.     } /* end non-tree edge */
  288.   } /* end forall */
  290. /* we know |lowpt1[v]| at this point and now make a second pass over all
  291.  * adjacent edges of |v| to compute |lowpt2| */
  293.   {
  294.     forall_adj_edges(e, v) {
  295.       w = target(e);
  296.       if (parent[w] == v) { /* tree edge */
  297. if (lowpt1[w] != lowpt1[v])
  298.   lowpt2[v] = Min(lowpt2[v], lowpt1[w]);
  299. lowpt2[v] = Min(lowpt2[v], lowpt2[w]);
  300.       } /* end tree edge */
  301.       else
  302.       /* all other edges */ if (lowpt1[v] != dfsnum[w])
  303. lowpt2[v] = Min(lowpt2[v], dfsnum[w]);
  304.     } /* end forall */
  305.   }
  306. } /* end dfs */
  308. static bool strongly_planar(edge e0, graph & G, list < int >&Att,
  309.   edge_array < int >&alpha,
  310.   node_array < int >&dfsnum,
  311.   node_array < node > &parent)
  312. {
  314.   node x = source(e0);
  316.   node y = target(e0);
  318.   edge e = G.first_adj_edge(y);
  320.   node wk = y;
  322.   while (dfsnum[target(e)] > dfsnum[wk]) { /* e is a tree edge */
  323.     wk = target(e);
  324.     e = G.first_adj_edge(wk);
  325.   }
  327.   node w0 = target(e);
  329.   node w = wk;
  331.   stack < block * >S;
  333.   while (w != x) {
  334.     int count = 0;
  335.     forall_adj_edges(e, w) {
  336.       count++;
  337.       if (count != 1) { /* no action for first edge */
  338. list < int >A;
  340. if (dfsnum[w] < dfsnum[target(e)]) { /* tree edge */
  341.   if (!strongly_planar(e, G, A, alpha, dfsnum, parent)) {
  342.     while (!S.empty())
  343.       delete(S.pop());
  344.     return false;
  345.   }
  347. }
  348. else
  349.   A.append(dfsnum[target(e)]); /* a back edge */
  351. block *B = new block(e, A);
  353. while (true) {
  354.   if (B->left_interlace(S))
  355.     (S.top())->flip();
  357.   if (B->left_interlace(S)) {
  358.     delete(B);
  359.     while (!S.empty())
  360.       delete(S.pop());
  361.     return false;
  362.   };
  364.   if (B->right_interlace(S))
  365.     B->combine(S.pop());
  366.   else
  367.     break;
  368. } /* end while */
  370. S.push(B);
  372.       } /* end if */
  373.     } /* end forall */
  375.     while (!S.empty() && (S.top())->clean(dfsnum[parent[w]], alpha))
  376.       delete(S.pop());
  378.     w = parent[w];
  379.   } /* end while */
  381.   Att.clear();
  382.   while (!S.empty()) {
  383.     block *B = S.pop();
  385.     if (!(B->empty_Latt()) && !(B->empty_Ratt()) &&
  386.       (B->head_of_Latt() > dfsnum[w0]) && (B->head_of_Ratt() > dfsnum[w0])) {
  387.       delete(B);
  388.       while (!S.empty())
  389. delete(S.pop());
  390.       return false;
  391.     }
  393.     B->add_to_Att(Att, dfsnum[w0], alpha);
  395.     delete(B);
  396.   } /* end while */
  398. /* Let's not forget (as the book does) that $w0$ is an attachment of $S(e0)$
  399.  * except if $w0 = x$. */
  401.   if (w0 != x)
  402.     Att.append(dfsnum[w0]);
  404.   return true;
  405. }
  407. static void embedding(edge e0, int t, GRAPH < node, edge > &G,
  408.   edge_array < int >&alpha,
  409.   node_array < int >&dfsnum,
  410.   list < edge > &T, list < edge > &A, int &cur_nr,
  411.   edge_array < int >&sort_num, node_array < edge > &tree_edge_into,
  412.   node_array < node > &parent, edge_array < edge > &reversal)
  413. {
  415.   node x = source(e0);
  417.   node y = target(e0);
  419.   tree_edge_into[y] = e0;
  421.   edge e = G.first_adj_edge(y);
  423.   node wk = y;
  425.   while (dfsnum[target(e)] > dfsnum[wk]) { /* e is a tree edge */
  426.     wk = target(e);
  427.     tree_edge_into[wk] = e;
  428.     e = G.first_adj_edge(wk);
  429.   }
  431.   node w0 = target(e);
  432.   edge back_edge_into_w0 = e;
  434.   node w = wk;
  436.   list < edge > Al, Ar;
  437.   list < edge > Tprime, Aprime;
  439.   T.clear();
  440.   T.append(G[e]); /* |e = (wk,w0)| at this point, line (2) */
  442.   while (w != x) {
  443.     int count = 0;
  444.     forall_adj_edges(e, w) {
  445.       count++;
  446.       if (count != 1) { /* no action for first edge */
  448. if (dfsnum[w] < dfsnum[target(e)]) { /* tree edge */
  449.   int tprime = ((t == alpha[e]) ? left : right);
  450.   embedding(e, tprime, G, alpha, dfsnum, Tprime, Aprime, cur_nr, sort_num, tree_edge_into, parent, reversal);
  452. }
  453. else { /* back edge */
  454.   Tprime.append(G[e]); /* $e$ */
  455.   Aprime.append(reversal[G[e]]); /* reversal of $e$ */
  456. }
  458. if (t == alpha[e]) {
  459.   Tprime.conc(T);
  460.   T.conc(Tprime); /* $T = Tprime conc T$ */
  462.   Al.conc(Aprime); /* $Al = Al conc Aprime$ */
  464. }
  465. else {
  466.   T.conc(Tprime); /* $ T = T conc Tprime $ */
  468.   Aprime.conc(Ar);
  469.   Ar.conc(Aprime); /* $ Ar = Aprime conc Ar$ */
  471. }
  473.       } /* end if */
  474.     } /* end forall */
  476.     T.append(reversal[G[tree_edge_into[w]]]); /* $(w_{j-1},w_j)$ */
  478.     forall(e, T) sort_num[e] = cur_nr++;
  480. /* |w|'s adjacency list is now computed; we clear |T| and prepare for the
  481.  * next iteration by moving all darts incident to |parent[w]| from |Al| and
  482.  * |Ar| to |T|. These darts are at the rear end of |Al| and at the front end
  483.  * of |Ar| */
  485.     T.clear();
  487.     while (!Al.empty() && source(Al.tail()) == G[parent[w]])
  488. /* |parent[w]| is in |G|, |Al.tail| in |H| */
  489.     {
  490.       T.push(Al.Pop()); /* Pop removes from the rear */
  491.     }
  493.     T.append(G[tree_edge_into[w]]); /* push would be equivalent */
  495.     while (!Ar.empty() && source(Ar.head()) == G[parent[w]]) { /* */
  496.       T.append(Ar.pop()); /* pop removes from the front */
  497.     }
  499.     w = parent[w];
  500.   } /* end while */
  502.   A.clear();
  504.   A.conc(Ar);
  505.   A.append(reversal[G[back_edge_into_w0]]);
  506.   A.conc(Al);
  508. }
  510. bool PLANAR(graph & Gin, bool embed)
  511. /* |Gin| is a directed graph. |planar| decides whether |Gin| is planar.
  512.  * If it is and |embed == true| then it also computes a
  513.  * combinatorial embedding of |Gin| by suitably reordering
  514.  * its adjacency lists.
  515.  * |Gin| must be bidirected in that case. */
  517. {
  518.   int n = Gin.number_of_nodes();
  520.   if (n <= 3)
  521.     return true;
  523.   if (Gin.number_of_edges() > 6 * n - 12)
  524.     return false;
  526. /* An undirected planar graph has at most $3n-6$ edges; a directed graph may
  527.  * have twice as many */
  529.   GRAPH < node, edge > G;
  531.   edge_array < edge > companion_in_G(Gin);
  533.   node_array < node > link(Gin);
  535.   bool Gin_is_bidirected = true;
  537.   {
  538.     node v;
  539.     forall_nodes(v, Gin) link[v] = G.new_node(v); /* bidirectional *
  540.  * links */
  541.     edge e;
  542.     forall_edges(e, Gin) companion_in_G[e] =
  543.       G.new_edge(link[source(e)], link[target(e)], e);
  545.   }
  547.   {
  548.     node_array < int >nr(G);
  549.     edge_array < int >cost(G);
  550.     int cur_nr = 0;
  551.     int n = G.number_of_nodes();
  552.     node v;
  553.     edge e;
  555.     forall_nodes(v, G) nr[v] = cur_nr++;
  557.     forall_edges(e, G) cost[e] = ((nr[source(e)] < nr[target(e)]) ?
  558.       n * nr[source(e)] + nr[target(e)] :
  559.       n * nr[target(e)] + nr[source(e)]);
  561.     G.sort_edges(cost);
  563.     list < edge > L = G.all_edges();
  565.     while (!L.empty()) {
  566.       e = L.pop();
  567. /* check whether the first edge on |L| is equal to the reversal of |e|. If so,
  568.  * delete it from |L|, if not, add the reversal to |G| */
  569.       if (!L.empty() && (source(e) == target(L.head())) && (source(L.head()) == target(e)))
  570. L.pop();
  571.       else {
  572. G.new_edge(target(e), source(e));
  573. Gin_is_bidirected = false;
  574.       }
  575.     }
  577.   }
  579.   make_biconnected_graph(G);
  581.   GRAPH < node, edge > H;
  582.   edge_array < edge > companion_in_H(Gin);
  584.   {
  585.     node v;
  586.     forall_nodes(v, G) G.assign(v, H.new_node(v));
  588.     edge e;
  589.     forall_edges(e, G) G.assign(e, H.new_edge(G[source(e)], G[target(e)], e));
  591.     edge ein;
  592.     forall_edges(ein, Gin) companion_in_H[ein] = G[companion_in_G[ein]];
  593.   }
  595.   edge_array < edge > reversal(H);
  597.   if (!compute_correspondence(H, reversal)) 
  598.      error_handler(1,"graph not bidirected");
  600.   node_array < int >dfsnum(G);
  601.   node_array < node > parent(G, nil);
  603.   reorder(G, dfsnum, parent);
  605.   edge_array < int >alpha(G, 0);
  607.   {
  608.     list < int >Att;
  610.     alpha[G.first_adj_edge(G.first_node())] = left;
  612.     if (!strongly_planar(G.first_adj_edge(G.first_node()), G, Att, alpha, dfsnum, parent))
  613.       return false;
  614.   }
  616.   if (embed) {
  617.     if (Gin_is_bidirected) {
  618.       list < edge > T, A; /* lists of edges of |H| */
  620.       int cur_nr = 0;
  621.       edge_array < int >sort_num(H);
  622.       node_array < edge > tree_edge_into(G);
  624.       embedding(G.first_adj_edge(G.first_node()), left, G, alpha, dfsnum, T, A,
  625. cur_nr, sort_num, tree_edge_into, parent, reversal);
  627. /* |T| contains all edges incident to the first node except the cycle edge into it.
  628.  * That edge comprises |A| */
  630.       T.conc(A);
  631.       edge e;
  633.       forall(e, T) sort_num[e] = cur_nr++;
  635.       edge_array < int >sort_Gin(Gin);
  637.       {
  638. edge ein;
  639. forall_edges(ein, Gin) sort_Gin[ein] = sort_num[companion_in_H[ein]];
  640.       }
  642.       Gin.sort_edges(sort_Gin);
  643.     }
  645.     else
  646.       error_handler(2, "sorry: can only embed bidirected graphs");
  647.   }
  648.   return true;
  649. }
  653. bool PLANAR(graph & G, list < edge > &P, bool embed)
  654. {
  655.   if (PLANAR(G, embed)) return true;
  657. /* We work on a copy |H| of |G| since the procedure alters |G|; we link every
  658.  * vertex and edge of |H| with its original. For the vertices we also have the
  659.  * reverse links. */
  661.   GRAPH < node, edge > H;
  662.   node_array < node > link(G);
  663.   node v;
  664.   forall_nodes(v, G) link[v] = H.new_node(v);
  665. /* This requires some explanation. |H.new_node(v)| adds a new node to
  666.  * |H|, returns the new node, and makes |v| the information associated
  667.  * with the new node. So the statement creates a copy of |v| and
  668.  * bidirectionally links it with |v| */
  670.   int N = G.number_of_nodes();
  672.   edge e;
  674.   forall_edges(e,G)
  675.   if (G.source(e) != G.target(e))
  676.   { H.new_edge(link[G.source(e)], link[G.target(e)], e);
  677.     if (--N < 1 && !PLANAR(H)) break;
  678.    }
  680. /* |link[source(e)]| and |link[target(e)]| are the copies of |source(e)|
  681.  * and |target(e)| in |H|. The operation |H.new_edge| creates a new edge
  682.  * with these endpoints, returns it, and makes |e| the information of that
  683.  * edge. So the effect of the loop is to make the edge set of |H| a copy
  684.  * of the edge set of |G| and to let every edge of |H| know its original.
  685.  * We can now determine a minimal non-planar subgraph of |H| */
  687.   list<edge> L = H.all_edges();
  689.   edge eh;
  691.   forall(eh, L) {
  692.     e = H[eh]; /* the edge in |G| corresponding to |eh| */
  693.     node x = G.source(eh);
  694.     node y = G.target(eh);
  695.     H.del_edge(eh);
  696.     if (PLANAR(H))
  697.       H.new_edge(x, y, e); /* put a new version of |eh| back in and *
  698.  * establish the correspondence */
  700.   }
  702. /* |H| is now a homeomorph of either $K_5$ or $K_{3,3}$. We still need
  703.  * to translate back to |G|. */
  705.   P.clear();
  707.   forall_edges(eh, H) P.append(H[eh]);
  709.   return false;
  711. }