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

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

数值算法/人工智能

开发平台：

MultiPlatform

_mw_matching.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _mw_matching.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 "max_weight_matching.w"
  15.    by CTANGLE (Version 3.1 [km2c]) */
  17. #include <LEDA/basic.h>
  18. #include <LEDA/list.h>
  19. #include <LEDA/ugraph.h>
  23. typedef num_type GEWICHT_TYP;
  24. typedef num_type DUALER_TYP;
  26. typedef list <edge> KANTENLISTE;
  28. #if !defined(__TEMPLATE_FUNCTIONS__)
  29. LEDA_TYPE_PARAMETER(KANTENLISTE)
  30. #endif
  32. #define GENAUIGKEIT 1e-10
  34. enum MARKENTYP {
  35.   S = -1, UNMARKIERT, T
  36. };
  38. class blossom {
  39.  public:
  41.   list <list_item >ub_zeiger_liste;
  42.   list <edge >kantenliste;
  45.   node basis;
  46.   DUALER_TYP z;
  49.   list <node >knotenliste;
  52.   MARKENTYP typ;
  53.   edge kante;
  56.   edge d3_kante;
  59.   list <edge >adj_s_blossoms;
  63.    blossom() {
  64.     ub_zeiger_liste.clear();
  65.     kantenliste.clear();
  66.     knotenliste.clear();
  67.     adj_s_blossoms.clear();
  68.     basis = nil;
  69.     z = 0;
  70.     typ = UNMARKIERT;
  71.     kante = nil;
  72.     d3_kante = nil;
  73.   }
  75.    blossom(const list <list_item >&zliste, const list <edge >&eliste,
  76.      const list <node >&nliste, const node b) {
  77.     ub_zeiger_liste = zliste;
  78.     kantenliste = eliste;
  79.     knotenliste = nliste;
  80.     adj_s_blossoms.clear();
  81.     basis = b;
  83.     z = 0;
  84.     typ = S;
  85.     kante = nil;
  86.     d3_kante = nil;
  87.   }
  89. };
  91. #if !defined(__TEMPLATE_FUNCTIONS__)
  92. void Print(const blossom&, ostream&) {}
  93. void Read(blossom&, istream&) {}
  94. int compare(const blossom&, const blossom&) 
  95. { error_handler(1,"no compare for blossoms"); 
  96.   return 0; 
  97. }
  98. LEDA_TYPE_PARAMETER(blossom)
  99. #endif
  102. int markiere
  103.  (const ugraph &G,
  104.    const edge_array <GEWICHT_TYP > &gewicht,
  105.    const node_array <DUALER_TYP > &u,
  106.    const edge_array <bool >&gematcht,
  107.    const node_array <list_item >&blossom_zu_knoten,
  108.    const node_array <edge >&gematchte_kante,
  109.    list <blossom > &blossomliste,
  110.    list <node >&ungescannt,
  111.    node_array <KANTENLISTE > &brauchbare_kanten,
  112.    list <edge >&pfad,
  113.    node_array <edge >&d2_kante);
  115. static void rek_erweitere
  116.  (const ugraph &G,
  117.    edge_array <bool >&gematcht,
  118.    list <blossom > &unterblossomliste,
  119.    blossom & bl,
  120.    node j);
  122. void erweitere
  123.  (const ugraph &G,
  124.    const edge_array <GEWICHT_TYP > &gewicht,
  125.    const node_array <list_item >&blossom_zu_knoten,
  126.    const node_array <DUALER_TYP > &u,
  127.    const list <edge >&pfad,
  128.    edge_array <bool >&gematcht,
  129.    list <blossom > &blossomliste,
  130.    list <blossom > &unterblossomliste,
  131.    list <node >&ungescannt,
  132.    node_array <edge >&gematchte_kante,
  133.    node_array <KANTENLISTE > &brauchbare_kanten,
  134.    node_array <edge >&d2_kante);
  136. int aendere_duale_variablen
  137.  (const ugraph &G,
  138.    const edge_array <GEWICHT_TYP > &gewicht,
  139.    const node_array <list_item >&blossom_zu_knoten,
  140.    const node_array <edge >&gematchte_kante,
  141.    list <blossom > &blossomliste,
  142.    node_array <DUALER_TYP > &u,
  143.    list <node >&ungescannt,
  144.    node_array <KANTENLISTE > &brauchbare_kanten,
  145.    const node_array <edge >&d2_kante);
  147. void bilde_blossom
  148.  (const ugraph &G,
  149.    const edge_array <GEWICHT_TYP > &gewicht,
  150.    const node_array <DUALER_TYP > &u,
  151.    const edge_array <bool >&gematcht,
  152.    const list <edge >&pfad,
  153.    list <blossom > &blossomliste,
  154.    list <blossom > &unterblossomliste,
  155.    list <node >&ungescannt,
  156.    node_array <list_item >&blossom_zu_knoten,
  157.    node_array <KANTENLISTE > &brauchbare_kanten,
  158.    node_array <edge >&d2_kante);
  160. void expandiere_blossoms
  161.  (const ugraph &G,
  162.    const edge_array <GEWICHT_TYP > &gewicht,
  163.    const node_array <DUALER_TYP > &u,
  164.    const edge_array <bool >&gematcht,
  165.    list <blossom > &blossomliste,
  166.    list <blossom > &unterblossomliste,
  167.    list <node >&ungescannt,
  168.    node_array <list_item >&blossom_zu_knoten,
  169.    node_array <KANTENLISTE > &brauchbare_kanten,
  170.    node_array <edge >&d2_kante);
  172. void neues_s_blossom
  173.  (const ugraph &G,
  174.    const edge_array <GEWICHT_TYP > &gewicht,
  175.    const node_array <DUALER_TYP > &u,
  176.    list <blossom > &blossomliste,
  177.    const node_array <list_item >&blossom_zu_knoten,
  178.    const edge_array <bool >&gematcht,
  179.    blossom & bl,
  180.    list <node >&ungescannt,
  181.    node_array <KANTENLISTE > &brauchbare_kanten,
  182.    node_array <edge >&d2_kante);
  184. static void aktualisiere_knotenliste
  185.  (list <blossom > &unterblossomliste,
  186.    blossom & bl);
  189. static void matchingtest
  190.  (const ugraph &G,
  191.    const edge_array <bool >&gematcht);
  193. static void bed1test
  194.  (const ugraph &G,
  195.    const edge_array <GEWICHT_TYP > &gewicht,
  196.    const node_array <DUALER_TYP > &u,
  197.    const list <blossom > &blossomliste,
  198.    const list <blossom > &unterblossomliste,
  199.    const node_array <list_item >&blossom_zu_knoten);
  201. static void bed2test
  202.  (const ugraph &G,
  203.    const edge_array <GEWICHT_TYP > &gewicht,
  204.    const list <blossom > &blossomliste,
  205.    const list <blossom > &unterblossomliste,
  206.    const node_array <list_item >&blossom_zu_knoten,
  207.    const edge_array <bool >&gematcht,
  208.    const node_array <DUALER_TYP > &u);
  210. static void bed3test
  211.  (const ugraph &G,
  212.    const node_array <DUALER_TYP > &u,
  213.    const node_array <edge >&gematchte_kante);
  215. static void bed4test
  216.  (const ugraph &G,
  217.    const list <blossom > &blossomliste,
  218.    const list <blossom > &unterblossomliste,
  219.    const node_array <edge >&gematchte_kante,
  220.    const node_array <list_item >&blossom_zu_knoten);
  222. static DUALER_TYP bestimme_z
  223.  (const ugraph &G,
  224.    const list <blossom > &blossomliste,
  225.    const list <blossom > &unterblossomliste,
  226.    const blossom & bl,
  227.    const edge &e);
  231. list <edge >MAX_WEIGHT_MATCHING (const ugraph &G, 
  232.                                  const edge_array <GEWICHT_TYP > &gewicht) 
  233. {
  235.   edge_array <bool >gematcht;
  236.   gematcht.init(G, false);
  239.   list <blossom > blossomliste;
  240.   list <blossom > unterblossomliste;
  242.   node i;
  244.   forall_nodes (i, G) {
  245.     list <list_item >l1;
  246.     list <edge >l2;
  247.     list <node >l3;
  249.     blossomliste.append(blossom(l1, l2, l3, i));
  250.   }
  253.   node_array <list_item >blossom_zu_knoten(G);
  255.   if (!blossomliste.empty()) {
  256.     list_item lit = blossomliste.first();
  258.     while (lit != nil) {
  259.       node i = blossomliste[lit].basis;
  260.       blossom_zu_knoten[i] = lit;
  262.       lit = blossomliste.succ(lit);
  263.     }
  264.   }
  267.   node_array <DUALER_TYP > u(G);
  268.   GEWICHT_TYP w_max = 0;
  269.   edge e;
  271.   forall_edges (e, G) {
  272.     if (gewicht[e] > w_max)
  273.       w_max = gewicht[e];
  274.   }
  276.   u.init(G, num_type(w_max / 2.0));
  279.   node_array <edge >gematchte_kante(G, nil);
  282.   list <edge >l;
  283.   node_array <KANTENLISTE > brauchbare_kanten(G, l);
  286.   list <node >ungescannt;
  289.   node_array <bool >schon_eingefuegt(G, false);
  290.   forall_edges (e, G) {
  291.     if ((gewicht[e] == w_max) ||
  292.       ((gewicht[e] < w_max) && (w_max - gewicht[e] < GENAUIGKEIT)) ||
  293.       ((gewicht[e] > w_max) && (gewicht[e] - w_max < GENAUIGKEIT))) {
  294.       if (schon_eingefuegt[G.source(e)] == false) {
  295. ungescannt.append(G.source(e));
  296. schon_eingefuegt[G.source(e)] = true;
  297.       }
  299.       if (schon_eingefuegt[G.target(e)] == false) {
  300. ungescannt.append(G.target(e));
  301. schon_eingefuegt[G.target(e)] = true;
  302.       }
  304.       brauchbare_kanten[G.source(e)].append(e);
  305.       brauchbare_kanten[G.target(e)].append(e);
  306.     }
  307.   }
  310.   list <edge >pfad;
  313.   node_array <edge >d2_kante(G, nil);
  317.   bool maximal = false;
  319.   while (!maximal) {
  320.     pfad.clear();
  323.     int erg_markiere = markiere
  324.     (G, gewicht, u, gematcht, blossom_zu_knoten, gematchte_kante,
  325.       blossomliste, ungescannt, brauchbare_kanten, pfad, d2_kante);
  328.     if (erg_markiere > 0) {
  331.       erweitere
  332. (G, gewicht, blossom_zu_knoten, u, pfad, gematcht, blossomliste,
  333. unterblossomliste, ungescannt, gematchte_kante, brauchbare_kanten, d2_kante);
  336.     }
  338.     else if (erg_markiere < 0) {
  341.       bilde_blossom
  342. (G, gewicht, u, gematcht, pfad, blossomliste, unterblossomliste, ungescannt,
  343. blossom_zu_knoten, brauchbare_kanten, d2_kante);
  346.     }
  348.     else if (erg_markiere == 0) {
  351.       int erg_aendere = aendere_duale_variablen
  352.       (G, gewicht, blossom_zu_knoten, gematchte_kante,
  353. blossomliste, u, ungescannt, brauchbare_kanten, d2_kante);
  356.       if (erg_aendere > 0)
  357. maximal = true;
  359.       else if (erg_aendere < 0) {
  362. expandiere_blossoms
  363.   (G, gewicht, u, gematcht, blossomliste, unterblossomliste, ungescannt,
  364.   blossom_zu_knoten, brauchbare_kanten, d2_kante);
  367.       }
  368.     }
  369.   }
  372.   matchingtest(G, gematcht);
  373.   bed1test(G, gewicht, u, blossomliste, unterblossomliste, blossom_zu_knoten);
  374.   bed2test(G, gewicht, blossomliste, unterblossomliste, blossom_zu_knoten, gematcht, u);
  375.   bed3test(G, u, gematchte_kante);
  376.   bed4test(G, blossomliste, unterblossomliste, gematchte_kante, blossom_zu_knoten);
  379.   list <edge >matching;
  381.   forall_edges (e, G)
  382.     if (gematcht[e] == true) {
  383.       matching.append(e);
  384.     }
  386.   return matching;
  387. }
  391. int markiere
  392.  (const ugraph &G,
  393.    const edge_array <GEWICHT_TYP > &gewicht,
  394.    const node_array <DUALER_TYP > &u,
  395.    const edge_array <bool >&gematcht,
  396.    const node_array <list_item >&blossom_zu_knoten,
  397.    const node_array <edge >&gematchte_kante,
  398.    list <blossom > &blossomliste,
  399.    list <node >&ungescannt,
  400.    node_array <KANTENLISTE > &brauchbare_kanten,
  401.    list <edge >&pfad,
  402.    node_array <edge >&d2_kante) {
  404.   if (!ungescannt.empty()) {
  405.     list_item lit_ungescannt = ungescannt.first();
  407.     while (lit_ungescannt != nil) {
  408.       node i = ungescannt.pop();
  411.       while (!brauchbare_kanten[i].empty()) {
  412. edge e = brauchbare_kanten[i].pop();
  413. node j = G.opposite(i, e);
  415. if (blossomliste[blossom_zu_knoten[j]].typ == UNMARKIERT) {
  417.   blossomliste[blossom_zu_knoten[j]].typ = T;
  418.   blossomliste[blossom_zu_knoten[j]].kante = e;
  421.   node b = blossomliste[blossom_zu_knoten[j]].basis;
  422.   edge e_gematcht = gematchte_kante[b];
  424.   list_item bllit = blossom_zu_knoten[G.opposite(b, e_gematcht)];
  425.   blossomliste[bllit].typ = S;
  426.   blossomliste[bllit].kante = e_gematcht;
  428.   neues_s_blossom
  429.     (G, gewicht, u, blossomliste, blossom_zu_knoten, gematcht, blossomliste[bllit],
  430.     ungescannt, brauchbare_kanten, d2_kante);
  433. }
  435. else if ((blossomliste[blossom_zu_knoten[j]].typ == S) &&
  436.   (blossom_zu_knoten[i] != blossom_zu_knoten[j])) {
  438.   ungescannt.push(i);
  440.   node start[2];
  441.   start[0] = i;
  442.   start[1] = j;
  444.   list <edge >alt_pfad[2];
  446.   for (int index = 0; index < 2; index++) {
  448.     edge kante = blossomliste[blossom_zu_knoten[start[index]]].kante;
  450.     while (kante != nil) {
  451.       node s = G.source(kante);
  452.       node t = G.target(kante);
  454.       alt_pfad[index].push(kante);
  456.       if (blossom_zu_knoten[s] == blossom_zu_knoten[start[index]]) {
  457. start[index] = t;
  458.       }
  460.       else {
  461. start[index] = s;
  462.       }
  464.       kante = blossomliste[blossom_zu_knoten[start[index]]].kante;
  465.     }
  467.     start[index] = blossomliste[blossom_zu_knoten[start[index]]].basis;
  470.   }
  473.   if (start[0] == start[1]) {
  475.     while (alt_pfad[0].head() == alt_pfad[1].head()) {
  476.       alt_pfad[0].pop();
  477.       alt_pfad[1].pop();
  478.     }
  482.     pfad = alt_pfad[0];
  483.     pfad.append(e);
  485.     if (!alt_pfad[1].empty()) {
  486.       list_item lit = alt_pfad[1].last();
  488.       while (lit != nil) {
  489. pfad.append(alt_pfad[1].inf(lit));
  490. lit = alt_pfad[1].pred(lit);
  491.       }
  492.     }
  494.     return -1;
  495.   }
  497.   else {
  499.     pfad = alt_pfad[0];
  500.     pfad.append(e);
  502.     if (!alt_pfad[1].empty()) {
  503.       list_item lit = alt_pfad[1].last();
  505.       while (lit != nil) {
  506. pfad.append(alt_pfad[1].inf(lit));
  507. lit = alt_pfad[1].pred(lit);
  508.       }
  509.     }
  511.     return 1;
  512.   }
  515. }
  517. else if (blossomliste[blossom_zu_knoten[j]].typ == T) {
  518.   brauchbare_kanten[j].append(e);
  519. }
  520.       }
  523.       lit_ungescannt = ungescannt.first();
  524.     }
  525.   }
  527.  return 0;
  530. }
  534. void neues_s_blossom
  535.  (const ugraph &G,
  536.    const edge_array <GEWICHT_TYP > &gewicht,
  537.    const node_array <DUALER_TYP > &u,
  538.    list <blossom > &blossomliste,
  539.    const node_array <list_item >&blossom_zu_knoten,
  540.    const edge_array <bool >&gematcht,
  541.    blossom & bl,
  542.    list <node >&ungescannt,
  543.    node_array <KANTENLISTE > &brauchbare_kanten,
  544.    node_array <edge >&d2_kante) {
  545.   if (!bl.knotenliste.empty()) {
  546.     list_item knotenlit = bl.knotenliste.first();
  548.     while (knotenlit != nil) {
  549.       node i = bl.knotenliste.inf(knotenlit);
  552.       edge e;
  553.       bool knoten_brauchbar = false;
  555.       brauchbare_kanten[i].clear();
  556.       d2_kante[i] = nil;
  558.       forall_adj_edges (e, i) {
  559. if (gematcht[e] == false) {
  560.   list_item litsource = blossom_zu_knoten[G.source(e)];
  561.   list_item littarget = blossom_zu_knoten[G.target(e)];
  563.   if (litsource != littarget) {
  564.     DUALER_TYP pi = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  566.     if ((pi == 0) ||
  567.       (pi < 0 && (-pi) < GENAUIGKEIT) ||
  568.       (pi > 0 && pi < GENAUIGKEIT)) {
  569.       brauchbare_kanten[i].append(e);
  570.       knoten_brauchbar = true;
  571.     }
  573.     else {
  575.       list_item bllit;
  576.       node j;
  578.       if (G.source(e) == i) {
  579. bllit = littarget;
  580. j = G.target(e);
  581.       }
  583.       else {
  584. bllit = litsource;
  585. j = G.source(e);
  586.       }
  589.       if ((blossomliste[bllit].typ == UNMARKIERT) ||
  590. (blossomliste[bllit].typ == T)) {
  591. if (d2_kante[j] != nil) {
  592.   edge min_e = d2_kante[j];
  593.   DUALER_TYP pi_j;
  594.   pi_j = u[G.source(min_e)] + u[G.target(min_e)] - gewicht[min_e];
  596.   if (pi < pi_j)
  597.     d2_kante[j] = e;
  598. }
  600. else
  601.   d2_kante[j] = e;
  602.       }
  605.       else if (blossomliste[bllit].typ == S) {
  606. if ((pi != 0) ||
  607.   (pi < 0 && (-pi) < GENAUIGKEIT) ||
  608.   (pi > 0 && pi < GENAUIGKEIT)) {
  609.   blossomliste[litsource].adj_s_blossoms.append(e);
  610.   blossomliste[littarget].adj_s_blossoms.append(e);
  611. }
  613. if (bl.d3_kante != nil) {
  614.   edge min_e = bl.d3_kante;
  615.   DUALER_TYP pi_j;
  616.   pi_j = u[G.source(min_e)] + u[G.target(min_e)] - gewicht[min_e];
  618.   if (pi < pi_j)
  619.     bl.d3_kante = e;
  620. }
  622. else
  623.   bl.d3_kante = e;
  625. if (blossomliste[bllit].d3_kante != nil) {
  626.   edge min_e = blossomliste[bllit].d3_kante;
  627.   DUALER_TYP pi_j;
  628.   pi_j = u[G.source(min_e)] + u[G.target(min_e)] - gewicht[min_e];
  630.   if (pi < pi_j)
  631.     blossomliste[bllit].d3_kante = e;
  632. }
  634. else
  635.   blossomliste[bllit].d3_kante = e;
  636.       }
  637.     }
  638.   }
  639. }
  640.       }
  642.       if (knoten_brauchbar == true)
  643. ungescannt.push(i);
  647.       knotenlit = bl.knotenliste.succ(knotenlit);
  648.     }
  649.   }
  651.   else {
  652.     node i = bl.basis;
  654.     edge e;
  655.     bool knoten_brauchbar = false;
  657.     brauchbare_kanten[i].clear();
  658.     d2_kante[i] = nil;
  660.     forall_adj_edges (e, i) {
  661.       if (gematcht[e] == false) {
  662. list_item litsource = blossom_zu_knoten[G.source(e)];
  663. list_item littarget = blossom_zu_knoten[G.target(e)];
  665. if (litsource != littarget) {
  666.   DUALER_TYP pi = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  668.   if ((pi == 0) ||
  669.     (pi < 0 && (-pi) < GENAUIGKEIT) ||
  670.     (pi > 0 && pi < GENAUIGKEIT)) {
  671.     brauchbare_kanten[i].append(e);
  672.     knoten_brauchbar = true;
  673.   }
  675.   else {
  677.     list_item bllit;
  678.     node j;
  680.     if (G.source(e) == i) {
  681.       bllit = littarget;
  682.       j = G.target(e);
  683.     }
  685.     else {
  686.       bllit = litsource;
  687.       j = G.source(e);
  688.     }
  691.     if ((blossomliste[bllit].typ == UNMARKIERT) ||
  692.       (blossomliste[bllit].typ == T)) {
  693.       if (d2_kante[j] != nil) {
  694. edge min_e = d2_kante[j];
  695. DUALER_TYP pi_j;
  696. pi_j = u[G.source(min_e)] + u[G.target(min_e)] - gewicht[min_e];
  698. if (pi < pi_j)
  699.   d2_kante[j] = e;
  700.       }
  702.       else
  703. d2_kante[j] = e;
  704.     }
  707.     else if (blossomliste[bllit].typ == S) {
  708.       if ((pi != 0) ||
  709. (pi < 0 && (-pi) < GENAUIGKEIT) ||
  710. (pi > 0 && pi < GENAUIGKEIT)) {
  711. blossomliste[litsource].adj_s_blossoms.append(e);
  712. blossomliste[littarget].adj_s_blossoms.append(e);
  713.       }
  715.       if (bl.d3_kante != nil) {
  716. edge min_e = bl.d3_kante;
  717. DUALER_TYP pi_j;
  718. pi_j = u[G.source(min_e)] + u[G.target(min_e)] - gewicht[min_e];
  720. if (pi < pi_j)
  721.   bl.d3_kante = e;
  722.       }
  724.       else
  725. bl.d3_kante = e;
  727.       if (blossomliste[bllit].d3_kante != nil) {
  728. edge min_e = blossomliste[bllit].d3_kante;
  729. DUALER_TYP pi_j;
  730. pi_j = u[G.source(min_e)] + u[G.target(min_e)] - gewicht[min_e];
  732. if (pi < pi_j)
  733.   blossomliste[bllit].d3_kante = e;
  734.       }
  736.       else
  737. blossomliste[bllit].d3_kante = e;
  738.     }
  739.   }
  740. }
  741.       }
  742.     }
  744.     if (knoten_brauchbar == true)
  745.       ungescannt.push(i);
  748.   }
  749. }
  754. void erweitere
  755.  (const ugraph &G,
  756.    const edge_array <GEWICHT_TYP > &gewicht,
  757.    const node_array <list_item >&blossom_zu_knoten,
  758.    const node_array <DUALER_TYP > &u,
  759.    const list <edge >&pfad,
  760.    edge_array <bool >&gematcht,
  761.    list <blossom > &blossomliste,
  762.    list <blossom > &unterblossomliste,
  763.    list <node >&ungescannt,
  764.    node_array <edge >&gematchte_kante,
  765.    node_array <KANTENLISTE > &brauchbare_kanten,
  766.    node_array <edge >&d2_kante) {
  768.   if (!pfad.empty()) {
  769.     list_item lit = pfad.first();
  771.     while (lit != nil) {
  772.       edge e = pfad.inf(lit);
  774.       if (gematcht[e] == true) {
  775. gematcht[e] = false;
  776.       }
  778.       else {
  779. gematcht[e] = true;
  780. node s = G.source(e);
  781. node t = G.target(e);
  783. if (s != blossomliste[blossom_zu_knoten[s]].basis) {
  784.   rek_erweitere
  785.     (G, gematcht, unterblossomliste, blossomliste[blossom_zu_knoten[s]], s);
  787.   aktualisiere_knotenliste
  788.     (unterblossomliste, blossomliste[blossom_zu_knoten[s]]);
  789. }
  791. if (t != blossomliste[blossom_zu_knoten[t]].basis) {
  792.   rek_erweitere
  793.     (G, gematcht, unterblossomliste, blossomliste[blossom_zu_knoten[t]], t);
  795.   aktualisiere_knotenliste
  796.     (unterblossomliste, blossomliste[blossom_zu_knoten[t]]);
  797. }
  800.       }
  802.       lit = pfad.succ(lit);
  803.     }
  804.   }
  808.   gematchte_kante.init(G, nil);
  810.   edge e;
  812.   forall_edges (e, G) {
  813.     if (gematcht[e] == true) {
  814.       gematchte_kante[G.source(e)] = e;
  815.       gematchte_kante[G.target(e)] = e;
  816.     }
  817.   }
  821.   list <edge >l;
  822.   brauchbare_kanten.init(G, l);
  823.   ungescannt.clear();
  825.   d2_kante.init(G, nil);
  827.   if (!blossomliste.empty()) {
  828.     list_item bllit = blossomliste.first();
  830.     while (bllit != nil) {
  831.       blossomliste[bllit].typ = UNMARKIERT;
  832.       blossomliste[bllit].d3_kante = nil;
  833.       blossomliste[bllit].kante = nil;
  834.       blossomliste[bllit].adj_s_blossoms.clear();
  836.       bllit = blossomliste.succ(bllit);
  837.     }
  838.   }
  841.   if (!blossomliste.empty()) {
  842.     list_item bllit = blossomliste.first();
  844.     while (bllit != nil) {
  845.       if (gematchte_kante[blossomliste[bllit].basis] == nil) {
  846. blossomliste[bllit].typ = S;
  848. neues_s_blossom
  849.   (G, gewicht, u, blossomliste, blossom_zu_knoten, gematcht,
  850.   blossomliste[bllit], ungescannt, brauchbare_kanten, d2_kante);
  851.       }
  853.       bllit = blossomliste.succ(bllit);
  854.     }
  855.   }
  856. }
  860. static void rek_erweitere
  861.  (const ugraph &G,
  862.    edge_array <bool >&gematcht,
  863.    list <blossom > &unterblossomliste,
  864.    blossom & bl,
  865.    node j) {
  867.   list_item knotenlit = bl.knotenliste.first();
  868.   node i = bl.knotenliste.inf(knotenlit);
  871.   list_item ubzlit = bl.ub_zeiger_liste.first();
  872.   list_item ubllit = bl.ub_zeiger_liste[ubzlit];
  873.   list_item kantenlit = bl.kantenliste.first();
  876.   while (i != j) {
  877.     node b = unterblossomliste[ubllit].basis;
  880.     if (i == b) {
  881.       ubzlit = bl.ub_zeiger_liste.succ(ubzlit);
  882.       ubllit = bl.ub_zeiger_liste[ubzlit];
  883.       kantenlit = bl.kantenliste.succ(kantenlit);
  884.     }
  888.     knotenlit = bl.knotenliste.succ(knotenlit);
  889.     i = bl.knotenliste.inf(knotenlit);
  890.   }
  894.   list <edge >pfad;
  895.   list <list_item >ub_liste;
  896.   list <node >exitknotenliste;
  900.   list_item hklit = kantenlit;
  901.   list_item hzlit = ubzlit;
  903.   if (gematcht[bl.kantenliste.inf(kantenlit)] == true) {
  904.     while (kantenlit != nil) {
  905.       pfad.append(bl.kantenliste.inf(kantenlit));
  906.       kantenlit = bl.kantenliste.pred(kantenlit);
  908.       ub_liste.append(bl.ub_zeiger_liste[ubzlit]);
  909.       ubzlit = bl.ub_zeiger_liste.pred(ubzlit);
  910.     }
  912.     ubzlit = bl.ub_zeiger_liste.last();
  913.     ub_liste.append(bl.ub_zeiger_liste[ubzlit]);
  914.   }
  917.   else {
  918.     kantenlit = bl.kantenliste.succ(kantenlit);
  920.     while (kantenlit != nil) {
  921.       pfad.append(bl.kantenliste.inf(kantenlit));
  923.       kantenlit = bl.kantenliste.succ(kantenlit);
  925.       ub_liste.append(bl.ub_zeiger_liste[ubzlit]);
  926.       ubzlit = bl.ub_zeiger_liste.succ(ubzlit);
  927.     }
  929.     ub_liste.append(bl.ub_zeiger_liste[ubzlit]);
  930.   }
  934.   kantenlit = pfad.first();
  936.   while (kantenlit != nil) {
  937.     edge e = pfad.inf(kantenlit);
  939.     if (gematcht[e] == true) {
  940.       gematcht[e] = false;
  941.     }
  943.     else {
  944.       gematcht[e] = true;
  945.       exitknotenliste.append(G.source(e));
  946.       exitknotenliste.append(G.target(e));
  947.     }
  949.     kantenlit = pfad.succ(kantenlit);
  950.   }
  954.   list <list_item >ubzliste[2];
  956.   ubzlit = hzlit;
  957.   kantenlit = hklit;
  959.   ubzlit = bl.ub_zeiger_liste.succ(ubzlit);
  961.   bl.ub_zeiger_liste.split(ubzlit, ubzliste[0], ubzliste[1]);
  962.   bl.ub_zeiger_liste.conc(ubzliste[1]);
  963.   bl.ub_zeiger_liste.conc(ubzliste[0]);
  966.   list <edge >kaliste[2];
  968.   kantenlit = bl.kantenliste.succ(kantenlit);
  970.   bl.kantenliste.split(kantenlit, kaliste[0], kaliste[1]);
  971.   bl.kantenliste.conc(kaliste[1]);
  972.   bl.kantenliste.conc(kaliste[0]);
  976.   bl.basis = j;
  980.   list_item lit = ub_liste.pop();
  981.   node b = unterblossomliste[lit].basis;
  983.   if (j != b) {
  984.     rek_erweitere
  985.       (G, gematcht, unterblossomliste, unterblossomliste[lit], j);
  987.     aktualisiere_knotenliste
  988.       (unterblossomliste, unterblossomliste[lit]);
  989.   }
  992.   while (!exitknotenliste.empty()) {
  993.     node k = exitknotenliste.pop();
  994.     node l = exitknotenliste.pop();
  996.     list_item lit = ub_liste.pop();
  997.     list_item lit2 = ub_liste.pop();
  1000.     if ((!unterblossomliste[lit].knotenliste.empty()) &&
  1001.       (!unterblossomliste[lit2].knotenliste.empty())) {
  1002.       list_item knotenlit = unterblossomliste[lit].knotenliste.first();
  1004.       while (knotenlit != nil) {
  1005. node hilfsknoten = unterblossomliste[lit].knotenliste[knotenlit];
  1008. if (hilfsknoten == k) {
  1009.   if (k != unterblossomliste[lit].basis) {
  1010.     rek_erweitere
  1011.       (G, gematcht, unterblossomliste, unterblossomliste[lit], k);
  1013.     aktualisiere_knotenliste
  1014.       (unterblossomliste, unterblossomliste[lit]);
  1015.   }
  1017.   if (l != unterblossomliste[lit2].basis) {
  1018.     rek_erweitere
  1019.       (G, gematcht, unterblossomliste, unterblossomliste[lit2], l);
  1021.     aktualisiere_knotenliste
  1022.       (unterblossomliste, unterblossomliste[lit2]);
  1023.   }
  1025.   break;
  1026. }
  1030. else if (hilfsknoten == l) {
  1031.   if (l != unterblossomliste[lit].basis) {
  1032.     rek_erweitere
  1033.       (G, gematcht, unterblossomliste, unterblossomliste[lit], l);
  1035.     aktualisiere_knotenliste
  1036.       (unterblossomliste, unterblossomliste[lit]);
  1037.   }
  1039.   if (k != unterblossomliste[lit2].basis) {
  1040.     rek_erweitere
  1041.       (G, gematcht, unterblossomliste, unterblossomliste[lit2], k);
  1043.     aktualisiere_knotenliste
  1044.       (unterblossomliste, unterblossomliste[lit2]);
  1045.   }
  1047.   break;
  1048. }
  1052. knotenlit = unterblossomliste[lit].knotenliste.succ(knotenlit);
  1053.       }
  1054.     }
  1057.     else if ((unterblossomliste[lit].knotenliste.empty()) &&
  1058.       (!unterblossomliste[lit2].knotenliste.empty())) {
  1059.       if (k == unterblossomliste[lit].basis) {
  1060. if (l != unterblossomliste[lit2].basis) {
  1061.   rek_erweitere
  1062.     (G, gematcht, unterblossomliste, unterblossomliste[lit2], l);
  1064.   aktualisiere_knotenliste
  1065.     (unterblossomliste, unterblossomliste[lit2]);
  1066. }
  1067.       }
  1069.       else {
  1070. if (k != unterblossomliste[lit2].basis) {
  1071.   rek_erweitere
  1072.     (G, gematcht, unterblossomliste, unterblossomliste[lit2], k);
  1074.   aktualisiere_knotenliste
  1075.     (unterblossomliste, unterblossomliste[lit2]);
  1076. }
  1077.       }
  1078.     }
  1081.     else if ((!unterblossomliste[lit].knotenliste.empty()) &&
  1082.       (unterblossomliste[lit2].knotenliste.empty())) {
  1083.       if (k == unterblossomliste[lit2].basis) {
  1084. if (l != unterblossomliste[lit].basis) {
  1085.   rek_erweitere
  1086.     (G, gematcht, unterblossomliste, unterblossomliste[lit], l);
  1088.   aktualisiere_knotenliste
  1089.     (unterblossomliste, unterblossomliste[lit]);
  1090. }
  1091.       }
  1093.       else {
  1094. if (k != unterblossomliste[lit].basis) {
  1095.   rek_erweitere
  1096.     (G, gematcht, unterblossomliste, unterblossomliste[lit], k);
  1098.   aktualisiere_knotenliste
  1099.     (unterblossomliste, unterblossomliste[lit]);
  1100. }
  1101.       }
  1102.     }
  1103.   }
  1106. }
  1110. static void aktualisiere_knotenliste
  1111.  (list <blossom > &unterblossomliste, blossom & bl) {
  1112.   bl.knotenliste.clear();
  1114.   if (!bl.ub_zeiger_liste.empty()) {
  1115.     list_item ubzlit = bl.ub_zeiger_liste.first();
  1117.     while (ubzlit != nil) {
  1118.       list_item ubllit = bl.ub_zeiger_liste[ubzlit];
  1120.       if (!unterblossomliste[ubllit].knotenliste.empty()) {
  1121. list_item knotenlit = unterblossomliste[ubllit].knotenliste.first();
  1123. while (knotenlit != nil) {
  1124.   node i = unterblossomliste[ubllit].knotenliste.inf(knotenlit);
  1125.   bl.knotenliste.append(i);
  1127.   knotenlit = unterblossomliste[ubllit].knotenliste.succ(knotenlit);
  1128. }
  1129.       }
  1131.       else {
  1132. bl.knotenliste.append(unterblossomliste[ubllit].basis);
  1133.       }
  1135.       ubzlit = bl.ub_zeiger_liste.succ(ubzlit);
  1136.     }
  1137.   }
  1138. }
  1143. void bilde_blossom
  1144.  (const ugraph &G,
  1145.    const edge_array <GEWICHT_TYP > &gewicht,
  1146.    const node_array <DUALER_TYP > &u,
  1147.    const edge_array <bool >&gematcht,
  1148.    const list <edge >&pfad,
  1149.    list <blossom > &blossomliste,
  1150.    list <blossom > &unterblossomliste,
  1151.    list <node >&ungescannt,
  1152.    node_array <list_item >&blossom_zu_knoten,
  1153.    node_array <KANTENLISTE > &brauchbare_kanten,
  1154.    node_array <edge >&d2_kante) {
  1156.   node neue_basis;
  1157.   list_item neues_blossom;
  1158.   list <list_item >zliste;
  1159.   list <node >nliste;
  1160.   edge hilfskante;
  1164.   edge e1 = pfad.inf(pfad.first());
  1165.   edge e2 = pfad.inf(pfad.last());
  1167.   node i1 = G.source(e1);
  1168.   node i2 = G.target(e1);
  1169.   node i3 = G.source(e2);
  1170.   node i4 = G.target(e2);
  1172.   if ((blossom_zu_knoten[i1] == blossom_zu_knoten[i3]) ||
  1173.     (blossom_zu_knoten[i1] == blossom_zu_knoten[i4])) {
  1174.     neue_basis = blossomliste[blossom_zu_knoten[i1]].basis;
  1175.   }
  1177.   else
  1178.     neue_basis = blossomliste[blossom_zu_knoten[i2]].basis;
  1182.   list_item litpfad = pfad.first();
  1184.   while (pfad.succ(litpfad) != nil) {
  1186.     list_item bllit;
  1187.     edge e1 = pfad.inf(litpfad);
  1188.     edge e2 = pfad.inf(pfad.succ(litpfad));
  1190.     node i1 = G.source(e1);
  1191.     node i2 = G.target(e1);
  1192.     node i3 = G.source(e2);
  1193.     node i4 = G.target(e2);
  1195.     if ((blossom_zu_knoten[i1] == blossom_zu_knoten[i3]) ||
  1196.       (blossom_zu_knoten[i1] == blossom_zu_knoten[i4])) {
  1197.       bllit = blossom_zu_knoten[i1];
  1198.     }
  1200.     else
  1201.       bllit = blossom_zu_knoten[i2];
  1205.     if (!blossomliste[bllit].knotenliste.empty()) {
  1206.       list_item knotenlit = blossomliste[bllit].knotenliste.first();
  1208.       while (knotenlit != nil) {
  1209. node i = blossomliste[bllit].knotenliste[knotenlit];
  1210. nliste.append(i);
  1212. knotenlit = blossomliste[bllit].knotenliste.succ(knotenlit);
  1213.       }
  1214.     }
  1216.     else {
  1217.       node i = blossomliste[bllit].basis;
  1219.       nliste.append(i);
  1220.     }
  1223.     if (blossomliste[bllit].typ == T) {
  1224.       neues_s_blossom(G, gewicht, u, blossomliste, blossom_zu_knoten, gematcht,
  1225. blossomliste[bllit], ungescannt, brauchbare_kanten, d2_kante);
  1226.     }
  1229.     blossom bl = blossomliste.del_item(bllit);
  1230.     bllit = unterblossomliste.append(bl);
  1231.     unterblossomliste[bllit].typ = UNMARKIERT;
  1232.     unterblossomliste[bllit].kante = nil;
  1234.     zliste.append(bllit);
  1238.     litpfad = pfad.succ(litpfad);
  1239.   }
  1242.   list_item bllit = blossom_zu_knoten[neue_basis];
  1243.   blossom bl = blossomliste.del_item(bllit);
  1244.   hilfskante = bl.kante;
  1245.   bllit = unterblossomliste.append(bl);
  1246.   unterblossomliste[bllit].typ = UNMARKIERT;
  1247.   unterblossomliste[bllit].kante = nil;
  1249.   zliste.append(bllit);
  1251.   if (!bl.knotenliste.empty()) {
  1252.     list_item lit = bl.knotenliste.first();
  1254.     while (lit != nil) {
  1255.       nliste.append(bl.knotenliste.inf(lit));
  1256.       lit = bl.knotenliste.succ(lit);
  1257.     }
  1258.   }
  1260.   else
  1261.     nliste.append(bl.basis);
  1267.   bl = blossom(zliste, pfad, nliste, neue_basis);
  1268.   bl.typ = S;
  1269.   bl.kante = hilfskante;
  1270.   neues_blossom = blossomliste.append(bl);
  1274.   list_item litn = nliste.first();
  1276.   while (litn != nil) {
  1277.     node i = nliste[litn];
  1278.     blossom_zu_knoten[i] = neues_blossom;
  1280.     litn = nliste.succ(litn);
  1281.   }
  1285.   if (!blossomliste[neues_blossom].ub_zeiger_liste.empty()) {
  1286.     list_item ubzlit = blossomliste[neues_blossom].ub_zeiger_liste.first();
  1288.     while (ubzlit != nil) {
  1289.       list_item ubllit = blossomliste[neues_blossom].ub_zeiger_liste[ubzlit];
  1291.       if (unterblossomliste[ubllit].d3_kante != nil) {
  1292. edge e = unterblossomliste[ubllit].d3_kante;
  1293. node i = G.source(e);
  1294. node j = G.target(e);
  1295. DUALER_TYP pi = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  1297. if ((blossom_zu_knoten[i] == blossom_zu_knoten[j]) ||
  1298.   (pi == 0) || (pi < 0 && (-pi) < GENAUIGKEIT) || (pi > 0 && pi < GENAUIGKEIT)) {
  1299.   unterblossomliste[ubllit].d3_kante = nil;
  1302.   list <list_item >loesche_kante;
  1304.   if (!unterblossomliste[ubllit].adj_s_blossoms.empty()) {
  1305.     list_item kantenlit = unterblossomliste[ubllit].adj_s_blossoms.first();
  1307.     while (kantenlit != nil) {
  1308.       edge e = unterblossomliste[ubllit].adj_s_blossoms[kantenlit];
  1310.       DUALER_TYP pi = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  1312.       if ((blossom_zu_knoten[G.source(e)] != blossom_zu_knoten[G.target(e)]) &&
  1313. (pi > GENAUIGKEIT || pi < -GENAUIGKEIT)) {
  1314. if (unterblossomliste[ubllit].d3_kante == nil)
  1315.   unterblossomliste[ubllit].d3_kante = e;
  1317. else {
  1318.   edge e_min = unterblossomliste[ubllit].d3_kante;
  1320.   DUALER_TYP pi_min = u[G.source(e_min)] + u[G.target(e_min)] - gewicht[e_min];
  1322.   if (pi < pi_min)
  1323.     unterblossomliste[ubllit].d3_kante = e;
  1324. }
  1325.       }
  1327.       else
  1328. loesche_kante.append(kantenlit);
  1330.       kantenlit = unterblossomliste[ubllit].adj_s_blossoms.succ(kantenlit);
  1331.     }
  1332.   }
  1335.   while (!loesche_kante.empty()) {
  1336.     list_item lit = loesche_kante.pop();
  1337.     blossomliste[ubllit].adj_s_blossoms.del_item(lit);
  1338.   }
  1341. }
  1342.       }
  1344.       ubzlit = blossomliste[neues_blossom].ub_zeiger_liste.succ(ubzlit);
  1345.     }
  1346.   }
  1349.   if (!blossomliste[neues_blossom].ub_zeiger_liste.empty()) {
  1350.     list_item ubzlit = blossomliste[neues_blossom].ub_zeiger_liste.first();
  1352.     while (ubzlit != nil) {
  1353.       list_item ubllit = blossomliste[neues_blossom].ub_zeiger_liste[ubzlit];
  1355.       if (unterblossomliste[ubllit].d3_kante != nil) {
  1357. edge e = unterblossomliste[ubllit].d3_kante;
  1359. DUALER_TYP pi_e = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  1361. if (blossomliste[neues_blossom].d3_kante == nil)
  1362.   blossomliste[neues_blossom].d3_kante = e;
  1364. else {
  1365.   edge e_min = blossomliste[neues_blossom].d3_kante;
  1366.   DUALER_TYP pi_min;
  1367.   pi_min = u[G.source(e_min)] + u[G.target(e_min)] - gewicht[e_min];
  1369.   if (pi_e < pi_min)
  1370.     blossomliste[neues_blossom].d3_kante = e;
  1371. }
  1373. blossomliste[neues_blossom].adj_s_blossoms.append(e);
  1375. unterblossomliste[ubllit].d3_kante = nil;
  1376.       }
  1378.       unterblossomliste[ubllit].adj_s_blossoms.clear();
  1380.       ubzlit = blossomliste[neues_blossom].ub_zeiger_liste.succ(ubzlit);
  1381.     }
  1382.   }
  1385. }
  1389. int aendere_duale_variablen
  1390.  (const ugraph &G, const edge_array <GEWICHT_TYP > &gewicht,
  1391.    const node_array <list_item >&blossom_zu_knoten,
  1392.    const node_array <edge >&gematchte_kante,
  1393.    list <blossom > &blossomliste,
  1394.    node_array <DUALER_TYP > &u,
  1395.    list <node >&ungescannt,
  1396.    node_array <KANTENLISTE > &brauchbare_kanten,
  1397.    const node_array <edge >&d2_kante) {
  1399.   DUALER_TYP delta, d_1, d_2, d_3, d_4;
  1400.   int erg_aendere;
  1403.   node_array <bool >schon_eingefuegt;
  1404.   schon_eingefuegt.init(G, false);
  1408.   d_1 = 0;
  1409.   d_2 = 0;
  1411.   node i;
  1412.   forall_nodes (i, G) {
  1413.     if (gematchte_kante[i] == nil) {
  1414.       d_1 = u[i];
  1415.     }
  1417.     list_item bllit = blossom_zu_knoten[i];
  1419.     if ((blossomliste[bllit].typ == UNMARKIERT) && (d2_kante[i] != nil)) {
  1420.       edge e = d2_kante[i];
  1422.       DUALER_TYP pi = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  1424.       if ((d_2 == 0) || (pi < d_2)) {
  1425. d_2 = pi;
  1426.       }
  1427.     }
  1428.   }
  1430.   if (d_2 == 0)
  1431.     d_2 = d_1;
  1434.   d_3 = d_1;
  1435.   d_4 = 2 * d_1;
  1437.   if (!blossomliste.empty()) {
  1438.     list_item bllit = blossomliste.first();
  1440.     while (bllit != nil) {
  1441.       if ((blossomliste[bllit].typ == S) && (blossomliste[bllit].d3_kante != nil)) {
  1442. edge e = blossomliste[bllit].d3_kante;
  1444. DUALER_TYP pi = (u[G.source(e)] + u[G.target(e)] - gewicht[e]) / 2;
  1445. if (pi < d_3)
  1446.   d_3 = pi;
  1447.       }
  1449.       else if ((!blossomliste[bllit].knotenliste.empty()) &&
  1450. (blossomliste[bllit].typ == T)) {
  1451. if (blossomliste[bllit].z < d_4) {
  1452.   d_4 = blossomliste[bllit].z;
  1453. }
  1454.       }
  1456.       bllit = blossomliste.succ(bllit);
  1457.     }
  1458.   }
  1460.   d_4 = d_4 / 2;
  1463.   if ((d_1 <= d_2) && (d_1 <= d_3) && (d_1 <= d_4)) {
  1464.     delta = d_1;
  1465.     erg_aendere = 1;
  1466.   }
  1468.   else if ((d_2 <= d_3) && (d_2 <= d_4)) {
  1469.     delta = d_2;
  1470.     erg_aendere = 0;
  1471.   }
  1473.   else if (d_3 <= d_4) {
  1474.     delta = d_3;
  1475.     erg_aendere = 0;
  1476.   }
  1478.   else {
  1479.     delta = d_4;
  1480.     erg_aendere = -1;
  1481.   }
  1485.   forall_nodes (i, G) {
  1486.     if (blossomliste[blossom_zu_knoten[i]].typ == S) {
  1487.       u[i] = u[i] - delta;
  1488.     }
  1490.     if (blossomliste[blossom_zu_knoten[i]].typ == T) {
  1491.       u[i] = u[i] + delta;
  1492.     }
  1493.   }
  1496.   if (!blossomliste.empty()) {
  1497.     list_item bllit = blossomliste.first();
  1499.     while (bllit != nil) {
  1500.       if (!blossomliste[bllit].knotenliste.empty()) {
  1501. if (blossomliste[bllit].typ == S) {
  1502.   blossomliste[bllit].z = blossomliste[bllit].z + 2 * delta;
  1503. }
  1505. else if (blossomliste[bllit].typ == T) {
  1506.   blossomliste[bllit].z = blossomliste[bllit].z - 2 * delta;
  1507. }
  1508.       }
  1510.       bllit = blossomliste.succ(bllit);
  1511.     }
  1512.   }
  1516.   if (delta == d_1)
  1517.     return erg_aendere;
  1518.   forall_nodes (i, G) {
  1519.     if ((blossomliste[blossom_zu_knoten[i]].typ == UNMARKIERT) &&
  1520.       (d2_kante[i] != nil)) {
  1521.       edge e = d2_kante[i];
  1522.       node j;
  1524.       if (i == G.target(e))
  1525. j = G.source(e);
  1526.       else
  1527. j = G.target(e);
  1529.       DUALER_TYP pi = u[i] + u[j] - gewicht[e];
  1531.       if ((pi == 0) ||
  1532. ((pi < 0) && ((-pi) < GENAUIGKEIT)) ||
  1533. ((pi > 0) && (pi < GENAUIGKEIT))) {
  1534. brauchbare_kanten[j].append(e);
  1536. if (schon_eingefuegt[j] == false) {
  1537.   ungescannt.push(j);
  1538.   schon_eingefuegt[j] = true;
  1539. }
  1540.       }
  1541.     }
  1542.   }
  1545.   if (!blossomliste.empty()) {
  1546.     edge_array <bool >kante_schon_betrachtet(G, false);
  1547.     list_item bllit = blossomliste.first();
  1549.     while (bllit != nil) {
  1550.       if ((blossomliste[bllit].typ == S) && (blossomliste[bllit].d3_kante != nil)) {
  1551. edge e = blossomliste[bllit].d3_kante;
  1553. DUALER_TYP pi = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  1555. if ((pi == 0) ||
  1556.   ((pi < 0) && ((-pi) < GENAUIGKEIT)) ||
  1557.   ((pi > 0) && (pi < GENAUIGKEIT))) {
  1558.   if (schon_eingefuegt[G.source(e)] == false) {
  1559.     ungescannt.push(G.source(e));
  1560.     schon_eingefuegt[G.source(e)] = true;
  1561.   }
  1563.   if (schon_eingefuegt[G.target(e)] == false) {
  1564.     ungescannt.push(G.target(e));
  1565.     schon_eingefuegt[G.target(e)] = true;
  1566.   }
  1568.   if (kante_schon_betrachtet[e] == false) {
  1569.     brauchbare_kanten[G.source(e)].append(e);
  1570.     brauchbare_kanten[G.target(e)].append(e);
  1571.     kante_schon_betrachtet[e] = true;
  1572.   }
  1573. }
  1574.       }
  1576.       bllit = blossomliste.succ(bllit);
  1577.     }
  1578.   }
  1580.   return erg_aendere;
  1581. }
  1583. void expandiere_blossoms(
  1584.    const ugraph &G,
  1585.    const edge_array <GEWICHT_TYP > &gewicht,
  1586.    const node_array <DUALER_TYP > &u,
  1587.    const edge_array <bool >&gematcht,
  1588.    list <blossom > &blossomliste,
  1589.    list <blossom > &unterblossomliste,
  1590.    list <node >&ungescannt,
  1591.    node_array <list_item >&blossom_zu_knoten,
  1592.    node_array <KANTENLISTE > &brauchbare_kanten,
  1593.    node_array <edge >&d2_kante)
  1594. {
  1596.   list <list_item >entferne_liste, verschiebe_liste;
  1600.   list_item bllit = blossomliste.first();
  1602.   while (bllit != nil) {
  1603.     if ((!blossomliste[bllit].knotenliste.empty()) &&
  1604.       (blossomliste[bllit].typ == T) && (blossomliste[bllit].z == 0)) {
  1608.       edge e = blossomliste[bllit].kante;
  1609.       node i;
  1611.       if (blossom_zu_knoten[G.source(e)] == bllit)
  1612. i = G.source(e);
  1613.       else if (blossom_zu_knoten[G.target(e)] == bllit)
  1614. i = G.target(e);
  1618.       list_item knotenlit = blossomliste[bllit].knotenliste.first();
  1619.       node j = blossomliste[bllit].knotenliste.inf(knotenlit);
  1620.       list_item ubzlit = blossomliste[bllit].ub_zeiger_liste.first();
  1621.       list_item ubllit = blossomliste[bllit].ub_zeiger_liste.inf(ubzlit);
  1622.       list_item kantenlit = blossomliste[bllit].kantenliste.first();
  1625.       while (i != j) {
  1626. if (j == unterblossomliste[ubllit].basis) {
  1627.   ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1628.   ubllit = blossomliste[bllit].ub_zeiger_liste.inf(ubzlit);
  1630.   kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1631. }
  1633. knotenlit = blossomliste[bllit].knotenliste.succ(knotenlit);
  1634. j = blossomliste[bllit].knotenliste.inf(knotenlit);
  1635.       }
  1639.       unterblossomliste[ubllit].typ = T;
  1640.       unterblossomliste[ubllit].kante = e;
  1643.       e = blossomliste[bllit].kantenliste.inf(kantenlit);
  1645.       if (gematcht[e] == true) {
  1647. list_item ubzlit_kopie = ubzlit;
  1648. list_item kantenlit_kopie = kantenlit;
  1650. ubzlit = blossomliste[bllit].ub_zeiger_liste.pred(ubzlit);
  1652. while (ubzlit != nil) {
  1653.   e = blossomliste[bllit].kantenliste.inf(kantenlit);
  1654.   ubllit = blossomliste[bllit].ub_zeiger_liste.inf(ubzlit);
  1656.   if (gematcht[e] == true) {
  1657.     unterblossomliste[ubllit].typ = S;
  1658.     unterblossomliste[ubllit].kante = e;
  1659.   }
  1661.   else {
  1662.     unterblossomliste[ubllit].typ = T;
  1663.     unterblossomliste[ubllit].kante = e;
  1664.   }
  1666.   kantenlit = blossomliste[bllit].kantenliste.pred(kantenlit);
  1667.   ubzlit = blossomliste[bllit].ub_zeiger_liste.pred(ubzlit);
  1668. }
  1671. ubzlit = blossomliste[bllit].ub_zeiger_liste.last();
  1672. ubllit = blossomliste[bllit].ub_zeiger_liste[ubzlit];
  1673. e = blossomliste[bllit].kantenliste.inf(kantenlit);
  1675. unterblossomliste[ubllit].typ = T;
  1676. unterblossomliste[ubllit].kante = e;
  1680. ubzlit = ubzlit_kopie;
  1681. kantenlit = kantenlit_kopie;
  1683. ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1684. kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1685. kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1687. while (kantenlit != nil) {
  1689.   e = blossomliste[bllit].kantenliste[kantenlit];
  1691.   list_item ubllit = blossomliste[bllit].ub_zeiger_liste[ubzlit];
  1693.   list_item ubzlit_succ = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1694.   list_item ubllit_succ = blossomliste[bllit].ub_zeiger_liste[ubzlit_succ];
  1696.   if (!unterblossomliste[ubllit].knotenliste.empty()) {
  1697.     list_item knotenlit = unterblossomliste[ubllit].knotenliste.first();
  1699.     while ((knotenlit != nil) && (unterblossomliste[ubllit].typ == UNMARKIERT)) {
  1700.       node i = unterblossomliste[ubllit].knotenliste[knotenlit];
  1702.       if (!brauchbare_kanten[i].empty()) {
  1703. edge e_brauchbar = brauchbare_kanten[i].pop();
  1705. unterblossomliste[ubllit].typ = T;
  1706. unterblossomliste[ubllit].kante = e_brauchbar;
  1707. unterblossomliste[ubllit_succ].typ = S;
  1708. unterblossomliste[ubllit_succ].kante = e;
  1709.       }
  1711.       knotenlit = unterblossomliste[ubllit].knotenliste.succ(knotenlit);
  1712.     }
  1713.   }
  1715.   else {
  1716.     node i = unterblossomliste[ubllit].basis;
  1718.     if (!brauchbare_kanten[i].empty()) {
  1719.       edge e_brauchbar = brauchbare_kanten[i].pop();
  1721.       unterblossomliste[ubllit].typ = T;
  1722.       unterblossomliste[ubllit].kante = e_brauchbar;
  1723.       unterblossomliste[ubllit_succ].typ = S;
  1724.       unterblossomliste[ubllit_succ].kante = e;
  1725.     }
  1726.   }
  1729.   if (!unterblossomliste[ubllit_succ].knotenliste.empty()) {
  1730.     list_item knotenlit = unterblossomliste[ubllit_succ].knotenliste.first();
  1732.     while ((knotenlit != nil) &&
  1733.       (unterblossomliste[ubllit_succ].typ == UNMARKIERT)) {
  1734.       node i = unterblossomliste[ubllit_succ].knotenliste[knotenlit];
  1736.       if (!brauchbare_kanten[i].empty()) {
  1737. edge e_brauchbar = brauchbare_kanten[i].pop();
  1739. unterblossomliste[ubllit_succ].typ = T;
  1740. unterblossomliste[ubllit_succ].kante = e_brauchbar;
  1741. unterblossomliste[ubllit].typ = S;
  1742. unterblossomliste[ubllit].kante = e;
  1743.       }
  1745.       knotenlit = unterblossomliste[ubllit_succ].knotenliste.succ(knotenlit);
  1746.     }
  1747.   }
  1749.   else {
  1750.     node i = unterblossomliste[ubllit_succ].basis;
  1752.     if (!brauchbare_kanten[i].empty()) {
  1753.       edge e_brauchbar = brauchbare_kanten[i].pop();
  1755.       unterblossomliste[ubllit_succ].typ = T;
  1756.       unterblossomliste[ubllit_succ].kante = e_brauchbar;
  1757.       unterblossomliste[ubllit].typ = S;
  1758.       unterblossomliste[ubllit].kante = e;
  1759.     }
  1760.   }
  1764.   ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1765.   ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1766.   kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1767.   kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1768. }
  1771.       }
  1774.       else if (gematcht[e] != true) {
  1776. list_item ubzlit_kopie = ubzlit;
  1777. list_item kantenlit_kopie = kantenlit;
  1779. kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1780. ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1782. while (kantenlit != nil) {
  1783.   e = blossomliste[bllit].kantenliste.inf(kantenlit);
  1784.   ubllit = blossomliste[bllit].ub_zeiger_liste.inf(ubzlit);
  1786.   if (gematcht[e] == true) {
  1787.     unterblossomliste[ubllit].typ = S;
  1788.     unterblossomliste[ubllit].kante = e;
  1789.   }
  1791.   else {
  1792.     unterblossomliste[ubllit].typ = T;
  1793.     unterblossomliste[ubllit].kante = e;
  1794.   }
  1796.   kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1797.   ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1798. }
  1802. ubzlit = ubzlit_kopie;
  1803. kantenlit = kantenlit_kopie;
  1805. ubzlit = blossomliste[bllit].ub_zeiger_liste.pred(ubzlit);
  1806. kantenlit = blossomliste[bllit].kantenliste.pred(kantenlit);
  1808. while (kantenlit != nil) {
  1810.   e = blossomliste[bllit].kantenliste[kantenlit];
  1812.   list_item ubllit = blossomliste[bllit].ub_zeiger_liste[ubzlit];
  1814.   list_item ubzlit_pred = blossomliste[bllit].ub_zeiger_liste.pred(ubzlit);
  1815.   list_item ubllit_pred = blossomliste[bllit].ub_zeiger_liste[ubzlit_pred];
  1817.   if (!unterblossomliste[ubllit].knotenliste.empty()) {
  1818.     list_item knotenlit = unterblossomliste[ubllit].knotenliste.first();
  1820.     while ((knotenlit != nil) && (unterblossomliste[ubllit].typ == UNMARKIERT)) {
  1821.       node i = unterblossomliste[ubllit].knotenliste[knotenlit];
  1823.       if (!brauchbare_kanten[i].empty()) {
  1824. edge e_brauchbar = brauchbare_kanten[i].pop();
  1826. unterblossomliste[ubllit].typ = T;
  1827. unterblossomliste[ubllit].kante = e_brauchbar;
  1828. unterblossomliste[ubllit_pred].typ = S;
  1829. unterblossomliste[ubllit_pred].kante = e;
  1830.       }
  1832.       knotenlit = unterblossomliste[ubllit].knotenliste.succ(knotenlit);
  1833.     }
  1834.   }
  1836.   else {
  1837.     node i = unterblossomliste[ubllit].basis;
  1839.     if (!brauchbare_kanten[i].empty()) {
  1840.       edge e_brauchbar = brauchbare_kanten[i].pop();
  1842.       unterblossomliste[ubllit].typ = T;
  1843.       unterblossomliste[ubllit].kante = e_brauchbar;
  1844.       unterblossomliste[ubllit_pred].typ = S;
  1845.       unterblossomliste[ubllit_pred].kante = e;
  1846.     }
  1847.   }
  1850.   if (!unterblossomliste[ubllit_pred].knotenliste.empty()) {
  1851.     list_item knotenlit = unterblossomliste[ubllit_pred].knotenliste.first();
  1853.     while ((knotenlit != nil) &&
  1854.       (unterblossomliste[ubllit_pred].typ == UNMARKIERT)) {
  1855.       node i = unterblossomliste[ubllit_pred].knotenliste[knotenlit];
  1857.       if (!brauchbare_kanten[i].empty()) {
  1858. edge e_brauchbar = brauchbare_kanten[i].pop();
  1860. unterblossomliste[ubllit_pred].typ = T;
  1861. unterblossomliste[ubllit_pred].kante = e_brauchbar;
  1862. unterblossomliste[ubllit].typ = S;
  1863. unterblossomliste[ubllit].kante = e;
  1864.       }
  1866.       knotenlit = unterblossomliste[ubllit_pred].knotenliste.succ(knotenlit);
  1867.     }
  1868.   }
  1870.   else {
  1871.     node i = unterblossomliste[ubllit_pred].basis;
  1873.     if (!brauchbare_kanten[i].empty()) {
  1874.       edge e_brauchbar = brauchbare_kanten[i].pop();
  1876.       unterblossomliste[ubllit_pred].typ = T;
  1877.       unterblossomliste[ubllit_pred].kante = e_brauchbar;
  1878.       unterblossomliste[ubllit].typ = S;
  1879.       unterblossomliste[ubllit].kante = e;
  1880.     }
  1881.   }
  1885.   ubzlit = blossomliste[bllit].ub_zeiger_liste.pred(ubzlit);
  1886.   ubzlit = blossomliste[bllit].ub_zeiger_liste.pred(ubzlit);
  1887.   kantenlit = blossomliste[bllit].kantenliste.pred(kantenlit);
  1888.   kantenlit = blossomliste[bllit].kantenliste.pred(kantenlit);
  1889. }
  1892.       }
  1898.       ubzlit = blossomliste[bllit].ub_zeiger_liste.first();
  1900.       while (ubzlit != nil) {
  1901. ubllit = blossomliste[bllit].ub_zeiger_liste.inf(ubzlit);
  1902. verschiebe_liste.append(ubllit);
  1904. ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1905.       }
  1909.       entferne_liste.append(bllit);
  1914.     }
  1916.     bllit = blossomliste.succ(bllit);
  1917.   }
  1921.   while (!entferne_liste.empty()) {
  1922.     blossomliste.del_item(entferne_liste.pop());
  1923.   }
  1927.   if (!verschiebe_liste.empty()) {
  1928.     list_item vlit = verschiebe_liste.first();
  1929.     list_item ubllit;
  1931.     while (vlit != nil) {
  1932.       ubllit = verschiebe_liste.inf(vlit);
  1933.       list_item hilfslit = blossomliste.append(unterblossomliste[ubllit]);
  1934.       unterblossomliste.del_item(verschiebe_liste.inf(vlit));
  1937.       if (!blossomliste[hilfslit].knotenliste.empty()) {
  1938. list_item knotenlit = blossomliste[hilfslit].knotenliste.first();
  1940. while (knotenlit != nil) {
  1941.   node i = blossomliste[hilfslit].knotenliste[knotenlit];
  1942.   blossom_zu_knoten[i] = hilfslit;
  1944.   knotenlit = blossomliste[hilfslit].knotenliste.succ(knotenlit);
  1945. }
  1946.       }
  1948.       else {
  1949. node i = blossomliste[hilfslit].basis;
  1950. blossom_zu_knoten[i] = hilfslit;
  1951.       }
  1953.       vlit = verschiebe_liste.succ(vlit);
  1954.     }
  1955.   }
  1958.   if (!verschiebe_liste.empty()) {
  1959.     list_item vlit = verschiebe_liste.first();
  1960.     list_item hilfslit = blossomliste.last();
  1962.     while (vlit != nil) {
  1963.       if (blossomliste[hilfslit].typ == S) {
  1964. neues_s_blossom
  1965.   (G, gewicht, u, blossomliste, blossom_zu_knoten, gematcht,
  1966.   blossomliste[hilfslit], ungescannt, brauchbare_kanten, d2_kante);
  1967.       }
  1969.       hilfslit = blossomliste.pred(hilfslit);
  1970.       vlit = verschiebe_liste.succ(vlit);
  1971.     }
  1972.   }
  1975. }
  1980. static void matchingtest(const ugraph &G, const edge_array <bool >&gematcht)
  1981. {
  1982.   node_array <bool >knoten_betrachtet(G, false);
  1983.   edge e;
  1985.   forall_edges (e, G) {
  1986.     node i = G.source(e);
  1987.     node j = G.target(e);
  1989.     if (gematcht[e] == true) {
  1990.       if (knoten_betrachtet[i] == false)
  1991. knoten_betrachtet[i] = true;
  1993.       else {
  1994. cout << "Knoten ";
  1995. G.print_node(i);
  1996. cout << " ist Endknoten mehrerer gematchter Kanten!!!n";
  1997.       }
  1999.       if (knoten_betrachtet[j] == false)
  2000. knoten_betrachtet[j] = true;
  2002.       else {
  2003. cout << "Knoten ";
  2004. G.print_node(j);
  2005. cout << " ist Endknoten mehrerer gematchter Kanten!!!n";
  2006.       }
  2007.     }
  2008.   }
  2010.   cout << "Test auf Matching abgeschlossen!n";
  2011.   return;
  2012. }
  2016. static void bed1test(const ugraph &G, const edge_array <GEWICHT_TYP > &gewicht, const
  2017.    node_array <DUALER_TYP > &u, const list <blossom > &blossomliste, const
  2018.    list <blossom > &unterblossomliste, const node_array <list_item >&blossom_zu_knoten)
  2019. {
  2021.   node i;
  2023.   forall_nodes (i, G) {
  2024.     if (u[i] < 0) {
  2025.       cout << "Die duale Variable von Knoten ";
  2026.       G.print_node(i);
  2027.       cout << " ist negativn";
  2028.     }
  2029.   }
  2033.   edge e;
  2035.   forall_edges (e, G) {
  2036.     node i = G.source(e);
  2037.     node j = G.target(e);
  2039.     if (i==j) continue;
  2041.     list_item litsource = blossom_zu_knoten[i];
  2042.     list_item littarget = blossom_zu_knoten[j];
  2043.     DUALER_TYP z;
  2045.     if (litsource != littarget)
  2046.       z = 0;
  2048.     else
  2049.       z = bestimme_z(G, blossomliste, unterblossomliste, blossomliste[litsource], e);
  2051.     DUALER_TYP pi = u[i] + u[j] - gewicht[e] + z;
  2053.     if (pi < 0) {
  2054.       cout << "pi<0 fuer Kante ";
  2055.       G.print_edge(e);
  2056.       cout << endl;
  2057.     }
  2058.   }
  2063.   if (!blossomliste.empty()) {
  2064.     list_item lit = blossomliste.first();
  2066.     while (lit != nil) {
  2067.       if (blossomliste[lit].z < 0) {
  2068. cout << "Es gibt ein z<0n";
  2069.       }
  2071.       lit = blossomliste.succ(lit);
  2072.     }
  2073.   }
  2077.   if (!unterblossomliste.empty()) {
  2078.     list_item lit = unterblossomliste.first();
  2080.     while (lit != nil) {
  2081.       if (unterblossomliste[lit].z < 0) {
  2082. cout << "Es gibt ein z<0n";
  2083.       }
  2085.       lit = unterblossomliste.succ(lit);
  2086.     }
  2087.   }
  2093.   cout << "Test von Bedingung (1) abgeschlossen!n";
  2094.   return;
  2095. }
  2099. static void bed2test(const ugraph &G, const edge_array <GEWICHT_TYP > &gewicht, const
  2100.    list <blossom > &blossomliste, const list <blossom > &unterblossomliste, const
  2101.    node_array <list_item >&blossom_zu_knoten, const edge_array <bool >&gematcht,
  2102.    const node_array <DUALER_TYP > &u)
  2103. {
  2104.   edge e;
  2106.   forall_edges (e, G) {
  2107.     if (gematcht[e] == true) {
  2108.       node i = G.source(e);
  2109.       node j = G.target(e);
  2110.       list_item litsource = blossom_zu_knoten[i];
  2111.       list_item littarget = blossom_zu_knoten[j];
  2112.       DUALER_TYP z;
  2114.       if (litsource != littarget)
  2115. z = 0;
  2117.       else
  2118. z = bestimme_z(G, blossomliste, unterblossomliste, blossomliste[litsource], e);
  2120.       DUALER_TYP pi = u[i] + u[j] - gewicht[e] + z;
  2122.       if (pi > 0) {
  2123. cout << "Kante ";
  2124. G.print_edge(e);
  2125. cout << " ist gematcht, aber pi ist positivn";
  2126.       }
  2127.     }
  2128.   }
  2130.   cout << "Test von Bedingung (2) abgeschlossen!n";
  2131.   return;
  2132. }
  2136. static void bed3test(const ugraph &G, const node_array <DUALER_TYP > &u, const
  2137.    node_array <edge >&gematchte_kante)
  2138. {
  2139.   node i;
  2141.   forall_nodes (i, G) {
  2142.     if (u[i] > 0) {
  2143.       if (gematchte_kante[i] == nil) {
  2144. cout << "Die duale Variable des freien Knotens ";
  2145. G.print_node(i);
  2146. cout << " ist positivn";
  2147.       }
  2148.     }
  2149.   }
  2151.   cout << "Test von Bedingung (3) abgeschlossen!n";
  2152.   return;
  2153. }
  2157. static void bed4test(const ugraph &G, const list <blossom > &blossomliste, const
  2158.    list <blossom > &unterblossomliste, const node_array <edge >&gematchte_kante,
  2159.    const node_array <list_item >&blossom_zu_knoten)
  2160. {
  2162.   if (!blossomliste.empty()) {
  2163.     list_item lit = blossomliste.first();
  2165.     while (lit != nil) {
  2166.       node_array <bool >schon_besucht(G, false);
  2167.       int anzknoten = 0;
  2168.       int anzgematchtekanten = 0;
  2170.       if ((blossomliste[lit].z > 0) &&
  2171. (!blossomliste[lit].knotenliste.empty())) {
  2173. list_item knotenlit = blossomliste[lit].knotenliste.first();
  2175. while (knotenlit != nil) {
  2176.   anzknoten++;
  2177.   node v = blossomliste[lit].knotenliste[knotenlit];
  2179.   if ((!schon_besucht[v]) && (gematchte_kante[v] != nil)) {
  2180.     schon_besucht[v] = true;
  2182.     edge e = gematchte_kante[v];
  2183.     node w = G.opposite(v, e);
  2185.     if (blossom_zu_knoten[w] == lit) {
  2186.       anzgematchtekanten++;
  2187.       schon_besucht[w] = true;
  2188.     }
  2189.   }
  2191.   knotenlit = blossomliste[lit].knotenliste.succ(knotenlit);
  2192. }
  2194. if (anzknoten != (2 * anzgematchtekanten + 1)) {
  2195.   cout << "Bedingung (4) ist verletzt!!!n";
  2196. }
  2199.       }
  2201.       lit = blossomliste.succ(lit);
  2202.     }
  2203.   }
  2207.   if (!unterblossomliste.empty()) {
  2208.     list_item lit = unterblossomliste.first();
  2210.     while (lit != nil) {
  2211.       node_array <bool >schon_besucht(G, false);
  2212.       int anzknoten = 0;
  2213.       int anzgematchtekanten = 0;
  2215.       if ((unterblossomliste[lit].z > 0) &&
  2216. (!unterblossomliste[lit].knotenliste.empty())) {
  2218. list_item knotenlit = unterblossomliste[lit].knotenliste.first();
  2220. while (knotenlit != nil) {
  2221.   anzknoten++;
  2222.   node v = unterblossomliste[lit].knotenliste[knotenlit];
  2224.   if ((!schon_besucht[v]) && (gematchte_kante[v] != nil)) {
  2225.     schon_besucht[v] = true;
  2227.     edge e = gematchte_kante[v];
  2228.     node w = G.opposite(v, e);
  2230.     list_item knotenlit2 = unterblossomliste[lit].knotenliste.first();
  2232.     while (knotenlit2 != nil) {
  2233.       if (unterblossomliste[lit].knotenliste[knotenlit2] == w) {
  2234. break;
  2235.       }
  2237.       knotenlit2 = unterblossomliste[lit].knotenliste.succ(knotenlit2);
  2238.     }
  2240.     if (knotenlit2 != nil) {
  2241.       anzgematchtekanten++;
  2242.       schon_besucht[w] = true;
  2243.     }
  2244.   }
  2246.   knotenlit = unterblossomliste[lit].knotenliste.succ(knotenlit);
  2247. }
  2249. if (anzknoten != (2 * anzgematchtekanten + 1)) {
  2250.   cout << "Bedingung (4) ist verletzt!!!n";
  2251. }
  2254.       }
  2256.       lit = unterblossomliste.succ(lit);
  2257.     }
  2258.   }
  2262.   cout << "Test von Bedingung (4) abgeschlossen!n";
  2263.   return;
  2264. }
  2268. static DUALER_TYP bestimme_z(const ugraph &G, const list <blossom > &blossomliste,
  2269.    const list <blossom > &unterblossomliste, const blossom & bl, const edge &e)
  2270. {
  2272.   DUALER_TYP z = bl.z;
  2274.   if (!bl.ub_zeiger_liste.empty()) {
  2275.     list_item ubzlit = bl.ub_zeiger_liste.first();
  2277.     while (ubzlit != nil) {
  2278.       int anzahl = 0;
  2279.       list_item ubllit = bl.ub_zeiger_liste[ubzlit];
  2281.       if (!unterblossomliste[ubllit].knotenliste.empty()) {
  2282. list_item knotenlit = unterblossomliste[ubllit].knotenliste.first();
  2284. while (knotenlit != nil) {
  2285.   node k = unterblossomliste[ubllit].knotenliste[knotenlit];
  2287.   if ((k == G.source(e)) || (k == G.target(e)))
  2288.     anzahl++;
  2289.   if (anzahl == 2)
  2290.     break;
  2292.   knotenlit = unterblossomliste[ubllit].knotenliste.succ(knotenlit);
  2293. }
  2294.       }
  2296.       if (anzahl == 2) {
  2297. z += bestimme_z(G, blossomliste, unterblossomliste,
  2298.   unterblossomliste[ubllit], e);
  2299. break;
  2300.       }
  2302.       else if (anzahl == 1)
  2303. break;
  2305.       ubzlit = bl.ub_zeiger_liste.succ(ubzlit);
  2306.     }
  2307.   }
  2309.   return z;
  2310. }