Category

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

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

_mw_matc.c：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _mw_matc.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. int compare(const KANTENLISTE&, const KANTENLISTE&) { return 0; }
  30. LEDA_TYPE_PARAMETER(KANTENLISTE)
  31. #endif
  33. #define GENAUIGKEIT 1e-10
  35. enum MARKENTYP {
  36.   S = -1, UNMARKIERT, T
  37. };
  39. class blossom {
  40.  public:
  42.   list <list_item >ub_zeiger_liste;
  43.   list <edge >kantenliste;
  46.   node basis;
  47.   DUALER_TYP z;
  50.   list <node >knotenliste;
  53.   MARKENTYP typ;
  54.   edge kante;
  57.   edge d3_kante;
  60.   list <edge >adj_s_blossoms;
  64.    blossom() {
  65.     ub_zeiger_liste.clear();
  66.     kantenliste.clear();
  67.     knotenliste.clear();
  68.     adj_s_blossoms.clear();
  69.     basis = nil;
  70.     z = 0;
  71.     typ = UNMARKIERT;
  72.     kante = nil;
  73.     d3_kante = nil;
  74.   }
  76.    blossom(const list <list_item >&zliste, const list <edge >&eliste,
  77.      const list <node >&nliste, const node b) {
  78.     ub_zeiger_liste = zliste;
  79.     kantenliste = eliste;
  80.     knotenliste = nliste;
  81.     adj_s_blossoms.clear();
  82.     basis = b;
  84.     z = 0;
  85.     typ = S;
  86.     kante = nil;
  87.     d3_kante = nil;
  88.   }
  90.   bool operator == (const blossom & bl) {
  91.     return 0;
  92.   }
  93. };
  95. #if !defined(TEMPLATE_FUNCTIONS)
  96. int compare(const blossom&, const blossom&) { return 0; }
  97. LEDA_TYPE_PARAMETER(blossom)
  98. #endif
  101. int markiere
  102.  (const ugraph &G,
  103.    const edge_array <GEWICHT_TYP > &gewicht,
  104.    const node_array <DUALER_TYP > &u,
  105.    const edge_array <bool >&gematcht,
  106.    const node_array <list_item >&blossom_zu_knoten,
  107.    const node_array <edge >&gematchte_kante,
  108.    list <blossom > &blossomliste,
  109.    list <node >&ungescannt,
  110.    node_array <KANTENLISTE > &brauchbare_kanten,
  111.    list <edge >&pfad,
  112.    node_array <edge >&d2_kante);
  114. void rek_erweitere
  115.  (const ugraph &G,
  116.    edge_array <bool >&gematcht,
  117.    list <blossom > &unterblossomliste,
  118.    blossom & bl,
  119.    node j);
  121. void erweitere
  122.  (const ugraph &G,
  123.    const edge_array <GEWICHT_TYP > &gewicht,
  124.    const node_array <list_item >&blossom_zu_knoten,
  125.    const node_array <DUALER_TYP > &u,
  126.    const list <edge >&pfad,
  127.    edge_array <bool >&gematcht,
  128.    list <blossom > &blossomliste,
  129.    list <blossom > &unterblossomliste,
  130.    list <node >&ungescannt,
  131.    node_array <edge >&gematchte_kante,
  132.    node_array <KANTENLISTE > &brauchbare_kanten,
  133.    node_array <edge >&d2_kante);
  135. int aendere_duale_variablen
  136.  (const ugraph &G,
  137.    const edge_array <GEWICHT_TYP > &gewicht,
  138.    const edge_array <bool >&gematcht,
  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. void aktualisiere_knotenliste
  185.  (list <blossom > &unterblossomliste,
  186.    blossom & bl);
  189. void matchingtest
  190.  (const ugraph &G,
  191.    const edge_array <bool >&gematcht);
  193. 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. 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. void bed3test
  211.  (const ugraph &G,
  212.    const node_array <DUALER_TYP > &u,
  213.    const node_array <edge >&gematchte_kante);
  215. 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. 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_WEIGHTED_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, gematcht, 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.   if (ungescannt.empty())
  528.     return 0;
  531. }
  535. void neues_s_blossom
  536.  (const ugraph &G,
  537.    const edge_array <GEWICHT_TYP > &gewicht,
  538.    const node_array <DUALER_TYP > &u,
  539.    list <blossom > &blossomliste,
  540.    const node_array <list_item >&blossom_zu_knoten,
  541.    const edge_array <bool >&gematcht,
  542.    blossom & bl,
  543.    list <node >&ungescannt,
  544.    node_array <KANTENLISTE > &brauchbare_kanten,
  545.    node_array <edge >&d2_kante) {
  546.   if (!bl.knotenliste.empty()) {
  547.     list_item knotenlit = bl.knotenliste.first();
  549.     while (knotenlit != nil) {
  550.       node i = bl.knotenliste.inf(knotenlit);
  553.       edge e;
  554.       bool knoten_brauchbar = false;
  556.       brauchbare_kanten[i].clear();
  557.       d2_kante[i] = nil;
  559.       forall_adj_edges (e, i) {
  560. if (gematcht[e] == false) {
  561.   list_item litsource = blossom_zu_knoten[G.source(e)];
  562.   list_item littarget = blossom_zu_knoten[G.target(e)];
  564.   if (litsource != littarget) {
  565.     DUALER_TYP pi = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  567.     if ((pi == 0) ||
  568.       (pi < 0 && (-pi) < GENAUIGKEIT) ||
  569.       (pi > 0 && pi < GENAUIGKEIT)) {
  570.       brauchbare_kanten[i].append(e);
  571.       knoten_brauchbar = true;
  572.     }
  574.     else {
  576.       list_item bllit;
  577.       node j;
  579.       if (G.source(e) == i) {
  580. bllit = littarget;
  581. j = G.target(e);
  582.       }
  584.       else {
  585. bllit = litsource;
  586. j = G.source(e);
  587.       }
  590.       if ((blossomliste[bllit].typ == UNMARKIERT) ||
  591. (blossomliste[bllit].typ == T)) {
  592. if (d2_kante[j] != nil) {
  593.   edge min_e = d2_kante[j];
  594.   DUALER_TYP pi_j;
  595.   pi_j = u[G.source(min_e)] + u[G.target(min_e)] - gewicht[min_e];
  597.   if (pi < pi_j)
  598.     d2_kante[j] = e;
  599. }
  601. else
  602.   d2_kante[j] = e;
  603.       }
  606.       else if (blossomliste[bllit].typ == S) {
  607. if ((pi != 0) ||
  608.   (pi < 0 && (-pi) < GENAUIGKEIT) ||
  609.   (pi > 0 && pi < GENAUIGKEIT)) {
  610.   blossomliste[litsource].adj_s_blossoms.append(e);
  611.   blossomliste[littarget].adj_s_blossoms.append(e);
  612. }
  614. if (bl.d3_kante != nil) {
  615.   edge min_e = bl.d3_kante;
  616.   DUALER_TYP pi_j;
  617.   pi_j = u[G.source(min_e)] + u[G.target(min_e)] - gewicht[min_e];
  619.   if (pi < pi_j)
  620.     bl.d3_kante = e;
  621. }
  623. else
  624.   bl.d3_kante = e;
  626. if (blossomliste[bllit].d3_kante != nil) {
  627.   edge min_e = blossomliste[bllit].d3_kante;
  628.   DUALER_TYP pi_j;
  629.   pi_j = u[G.source(min_e)] + u[G.target(min_e)] - gewicht[min_e];
  631.   if (pi < pi_j)
  632.     blossomliste[bllit].d3_kante = e;
  633. }
  635. else
  636.   blossomliste[bllit].d3_kante = e;
  637.       }
  638.     }
  639.   }
  640. }
  641.       }
  643.       if (knoten_brauchbar == true)
  644. ungescannt.push(i);
  648.       knotenlit = bl.knotenliste.succ(knotenlit);
  649.     }
  650.   }
  652.   else {
  653.     node i = bl.basis;
  655.     edge e;
  656.     bool knoten_brauchbar = false;
  658.     brauchbare_kanten[i].clear();
  659.     d2_kante[i] = nil;
  661.     forall_adj_edges (e, i) {
  662.       if (gematcht[e] == false) {
  663. list_item litsource = blossom_zu_knoten[G.source(e)];
  664. list_item littarget = blossom_zu_knoten[G.target(e)];
  666. if (litsource != littarget) {
  667.   DUALER_TYP pi = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  669.   if ((pi == 0) ||
  670.     (pi < 0 && (-pi) < GENAUIGKEIT) ||
  671.     (pi > 0 && pi < GENAUIGKEIT)) {
  672.     brauchbare_kanten[i].append(e);
  673.     knoten_brauchbar = true;
  674.   }
  676.   else {
  678.     list_item bllit;
  679.     node j;
  681.     if (G.source(e) == i) {
  682.       bllit = littarget;
  683.       j = G.target(e);
  684.     }
  686.     else {
  687.       bllit = litsource;
  688.       j = G.source(e);
  689.     }
  692.     if ((blossomliste[bllit].typ == UNMARKIERT) ||
  693.       (blossomliste[bllit].typ == T)) {
  694.       if (d2_kante[j] != nil) {
  695. edge min_e = d2_kante[j];
  696. DUALER_TYP pi_j;
  697. pi_j = u[G.source(min_e)] + u[G.target(min_e)] - gewicht[min_e];
  699. if (pi < pi_j)
  700.   d2_kante[j] = e;
  701.       }
  703.       else
  704. d2_kante[j] = e;
  705.     }
  708.     else if (blossomliste[bllit].typ == S) {
  709.       if ((pi != 0) ||
  710. (pi < 0 && (-pi) < GENAUIGKEIT) ||
  711. (pi > 0 && pi < GENAUIGKEIT)) {
  712. blossomliste[litsource].adj_s_blossoms.append(e);
  713. blossomliste[littarget].adj_s_blossoms.append(e);
  714.       }
  716.       if (bl.d3_kante != nil) {
  717. edge min_e = bl.d3_kante;
  718. DUALER_TYP pi_j;
  719. pi_j = u[G.source(min_e)] + u[G.target(min_e)] - gewicht[min_e];
  721. if (pi < pi_j)
  722.   bl.d3_kante = e;
  723.       }
  725.       else
  726. bl.d3_kante = e;
  728.       if (blossomliste[bllit].d3_kante != nil) {
  729. edge min_e = blossomliste[bllit].d3_kante;
  730. DUALER_TYP pi_j;
  731. pi_j = u[G.source(min_e)] + u[G.target(min_e)] - gewicht[min_e];
  733. if (pi < pi_j)
  734.   blossomliste[bllit].d3_kante = e;
  735.       }
  737.       else
  738. blossomliste[bllit].d3_kante = e;
  739.     }
  740.   }
  741. }
  742.       }
  743.     }
  745.     if (knoten_brauchbar == true)
  746.       ungescannt.push(i);
  749.   }
  750. }
  755. void erweitere
  756.  (const ugraph &G,
  757.    const edge_array <GEWICHT_TYP > &gewicht,
  758.    const node_array <list_item >&blossom_zu_knoten,
  759.    const node_array <DUALER_TYP > &u,
  760.    const list <edge >&pfad,
  761.    edge_array <bool >&gematcht,
  762.    list <blossom > &blossomliste,
  763.    list <blossom > &unterblossomliste,
  764.    list <node >&ungescannt,
  765.    node_array <edge >&gematchte_kante,
  766.    node_array <KANTENLISTE > &brauchbare_kanten,
  767.    node_array <edge >&d2_kante) {
  769.   if (!pfad.empty()) {
  770.     list_item lit = pfad.first();
  772.     while (lit != nil) {
  773.       edge e = pfad.inf(lit);
  775.       if (gematcht[e] == true) {
  776. gematcht[e] = false;
  777.       }
  779.       else {
  780. gematcht[e] = true;
  781. node s = G.source(e);
  782. node t = G.target(e);
  784. if (s != blossomliste[blossom_zu_knoten[s]].basis) {
  785.   rek_erweitere
  786.     (G, gematcht, unterblossomliste, blossomliste[blossom_zu_knoten[s]], s);
  788.   aktualisiere_knotenliste
  789.     (unterblossomliste, blossomliste[blossom_zu_knoten[s]]);
  790. }
  792. if (t != blossomliste[blossom_zu_knoten[t]].basis) {
  793.   rek_erweitere
  794.     (G, gematcht, unterblossomliste, blossomliste[blossom_zu_knoten[t]], t);
  796.   aktualisiere_knotenliste
  797.     (unterblossomliste, blossomliste[blossom_zu_knoten[t]]);
  798. }
  801.       }
  803.       lit = pfad.succ(lit);
  804.     }
  805.   }
  809.   gematchte_kante.init(G, nil);
  811.   edge e;
  813.   forall_edges (e, G) {
  814.     if (gematcht[e] == true) {
  815.       gematchte_kante[G.source(e)] = e;
  816.       gematchte_kante[G.target(e)] = e;
  817.     }
  818.   }
  822.   list <edge >l;
  823.   brauchbare_kanten.init(G, l);
  824.   ungescannt.clear();
  826.   d2_kante.init(G, nil);
  828.   if (!blossomliste.empty()) {
  829.     list_item bllit = blossomliste.first();
  831.     while (bllit != nil) {
  832.       blossomliste[bllit].typ = UNMARKIERT;
  833.       blossomliste[bllit].d3_kante = nil;
  834.       blossomliste[bllit].kante = nil;
  835.       blossomliste[bllit].adj_s_blossoms.clear();
  837.       bllit = blossomliste.succ(bllit);
  838.     }
  839.   }
  842.   if (!blossomliste.empty()) {
  843.     list_item bllit = blossomliste.first();
  845.     while (bllit != nil) {
  846.       if (gematchte_kante[blossomliste[bllit].basis] == nil) {
  847. blossomliste[bllit].typ = S;
  849. neues_s_blossom
  850.   (G, gewicht, u, blossomliste, blossom_zu_knoten, gematcht,
  851.   blossomliste[bllit], ungescannt, brauchbare_kanten, d2_kante);
  852.       }
  854.       bllit = blossomliste.succ(bllit);
  855.     }
  856.   }
  857. }
  861. void rek_erweitere
  862.  (const ugraph &G,
  863.    edge_array <bool >&gematcht,
  864.    list <blossom > &unterblossomliste,
  865.    blossom & bl,
  866.    node j) {
  868.   list_item knotenlit = bl.knotenliste.first();
  869.   node i = bl.knotenliste.inf(knotenlit);
  872.   list_item ubzlit = bl.ub_zeiger_liste.first();
  873.   list_item ubllit = bl.ub_zeiger_liste[ubzlit];
  874.   list_item kantenlit = bl.kantenliste.first();
  877.   while (i != j) {
  878.     node b = unterblossomliste[ubllit].basis;
  881.     if (i == b) {
  882.       ubzlit = bl.ub_zeiger_liste.succ(ubzlit);
  883.       ubllit = bl.ub_zeiger_liste[ubzlit];
  884.       kantenlit = bl.kantenliste.succ(kantenlit);
  885.     }
  889.     knotenlit = bl.knotenliste.succ(knotenlit);
  890.     i = bl.knotenliste.inf(knotenlit);
  891.   }
  895.   list <edge >pfad;
  896.   list <list_item >ub_liste;
  897.   list <node >exitknotenliste;
  901.   list_item hklit = kantenlit;
  902.   list_item hzlit = ubzlit;
  904.   if (gematcht[bl.kantenliste.inf(kantenlit)] == true) {
  905.     while (kantenlit != nil) {
  906.       pfad.append(bl.kantenliste.inf(kantenlit));
  907.       kantenlit = bl.kantenliste.pred(kantenlit);
  909.       ub_liste.append(bl.ub_zeiger_liste[ubzlit]);
  910.       ubzlit = bl.ub_zeiger_liste.pred(ubzlit);
  911.     }
  913.     ubzlit = bl.ub_zeiger_liste.last();
  914.     ub_liste.append(bl.ub_zeiger_liste[ubzlit]);
  915.   }
  918.   else {
  919.     kantenlit = bl.kantenliste.succ(kantenlit);
  921.     while (kantenlit != nil) {
  922.       pfad.append(bl.kantenliste.inf(kantenlit));
  924.       kantenlit = bl.kantenliste.succ(kantenlit);
  926.       ub_liste.append(bl.ub_zeiger_liste[ubzlit]);
  927.       ubzlit = bl.ub_zeiger_liste.succ(ubzlit);
  928.     }
  930.     ub_liste.append(bl.ub_zeiger_liste[ubzlit]);
  931.   }
  935.   kantenlit = pfad.first();
  937.   while (kantenlit != nil) {
  938.     edge e = pfad.inf(kantenlit);
  940.     if (gematcht[e] == true) {
  941.       gematcht[e] = false;
  942.     }
  944.     else {
  945.       gematcht[e] = true;
  946.       exitknotenliste.append(G.source(e));
  947.       exitknotenliste.append(G.target(e));
  948.     }
  950.     kantenlit = pfad.succ(kantenlit);
  951.   }
  955.   list <list_item >ubzliste[2];
  957.   ubzlit = hzlit;
  958.   kantenlit = hklit;
  960.   ubzlit = bl.ub_zeiger_liste.succ(ubzlit);
  962.   bl.ub_zeiger_liste.split(ubzlit, ubzliste[0], ubzliste[1]);
  963.   bl.ub_zeiger_liste.conc(ubzliste[1]);
  964.   bl.ub_zeiger_liste.conc(ubzliste[0]);
  967.   list <edge >kaliste[2];
  969.   kantenlit = bl.kantenliste.succ(kantenlit);
  971.   bl.kantenliste.split(kantenlit, kaliste[0], kaliste[1]);
  972.   bl.kantenliste.conc(kaliste[1]);
  973.   bl.kantenliste.conc(kaliste[0]);
  977.   bl.basis = j;
  981.   list_item lit = ub_liste.pop();
  982.   node b = unterblossomliste[lit].basis;
  984.   if (j != b) {
  985.     rek_erweitere
  986.       (G, gematcht, unterblossomliste, unterblossomliste[lit], j);
  988.     aktualisiere_knotenliste
  989.       (unterblossomliste, unterblossomliste[lit]);
  990.   }
  993.   while (!exitknotenliste.empty()) {
  994.     node k = exitknotenliste.pop();
  995.     node l = exitknotenliste.pop();
  997.     list_item lit = ub_liste.pop();
  998.     list_item lit2 = ub_liste.pop();
  1001.     if ((!unterblossomliste[lit].knotenliste.empty()) &&
  1002.       (!unterblossomliste[lit2].knotenliste.empty())) {
  1003.       list_item knotenlit = unterblossomliste[lit].knotenliste.first();
  1005.       while (knotenlit != nil) {
  1006. node hilfsknoten = unterblossomliste[lit].knotenliste[knotenlit];
  1009. if (hilfsknoten == k) {
  1010.   if (k != unterblossomliste[lit].basis) {
  1011.     rek_erweitere
  1012.       (G, gematcht, unterblossomliste, unterblossomliste[lit], k);
  1014.     aktualisiere_knotenliste
  1015.       (unterblossomliste, unterblossomliste[lit]);
  1016.   }
  1018.   if (l != unterblossomliste[lit2].basis) {
  1019.     rek_erweitere
  1020.       (G, gematcht, unterblossomliste, unterblossomliste[lit2], l);
  1022.     aktualisiere_knotenliste
  1023.       (unterblossomliste, unterblossomliste[lit2]);
  1024.   }
  1026.   break;
  1027. }
  1031. else if (hilfsknoten == l) {
  1032.   if (l != unterblossomliste[lit].basis) {
  1033.     rek_erweitere
  1034.       (G, gematcht, unterblossomliste, unterblossomliste[lit], l);
  1036.     aktualisiere_knotenliste
  1037.       (unterblossomliste, unterblossomliste[lit]);
  1038.   }
  1040.   if (k != unterblossomliste[lit2].basis) {
  1041.     rek_erweitere
  1042.       (G, gematcht, unterblossomliste, unterblossomliste[lit2], k);
  1044.     aktualisiere_knotenliste
  1045.       (unterblossomliste, unterblossomliste[lit2]);
  1046.   }
  1048.   break;
  1049. }
  1053. knotenlit = unterblossomliste[lit].knotenliste.succ(knotenlit);
  1054.       }
  1055.     }
  1058.     else if ((unterblossomliste[lit].knotenliste.empty()) &&
  1059.       (!unterblossomliste[lit2].knotenliste.empty())) {
  1060.       if (k == unterblossomliste[lit].basis) {
  1061. if (l != unterblossomliste[lit2].basis) {
  1062.   rek_erweitere
  1063.     (G, gematcht, unterblossomliste, unterblossomliste[lit2], l);
  1065.   aktualisiere_knotenliste
  1066.     (unterblossomliste, unterblossomliste[lit2]);
  1067. }
  1068.       }
  1070.       else {
  1071. if (k != unterblossomliste[lit2].basis) {
  1072.   rek_erweitere
  1073.     (G, gematcht, unterblossomliste, unterblossomliste[lit2], k);
  1075.   aktualisiere_knotenliste
  1076.     (unterblossomliste, unterblossomliste[lit2]);
  1077. }
  1078.       }
  1079.     }
  1082.     else if ((!unterblossomliste[lit].knotenliste.empty()) &&
  1083.       (unterblossomliste[lit2].knotenliste.empty())) {
  1084.       if (k == unterblossomliste[lit2].basis) {
  1085. if (l != unterblossomliste[lit].basis) {
  1086.   rek_erweitere
  1087.     (G, gematcht, unterblossomliste, unterblossomliste[lit], l);
  1089.   aktualisiere_knotenliste
  1090.     (unterblossomliste, unterblossomliste[lit]);
  1091. }
  1092.       }
  1094.       else {
  1095. if (k != unterblossomliste[lit].basis) {
  1096.   rek_erweitere
  1097.     (G, gematcht, unterblossomliste, unterblossomliste[lit], k);
  1099.   aktualisiere_knotenliste
  1100.     (unterblossomliste, unterblossomliste[lit]);
  1101. }
  1102.       }
  1103.     }
  1104.   }
  1107. }
  1111. void aktualisiere_knotenliste
  1112.  (list <blossom > &unterblossomliste, blossom & bl) {
  1113.   bl.knotenliste.clear();
  1115.   if (!bl.ub_zeiger_liste.empty()) {
  1116.     list_item ubzlit = bl.ub_zeiger_liste.first();
  1118.     while (ubzlit != nil) {
  1119.       list_item ubllit = bl.ub_zeiger_liste[ubzlit];
  1121.       if (!unterblossomliste[ubllit].knotenliste.empty()) {
  1122. list_item knotenlit = unterblossomliste[ubllit].knotenliste.first();
  1124. while (knotenlit != nil) {
  1125.   node i = unterblossomliste[ubllit].knotenliste.inf(knotenlit);
  1126.   bl.knotenliste.append(i);
  1128.   knotenlit = unterblossomliste[ubllit].knotenliste.succ(knotenlit);
  1129. }
  1130.       }
  1132.       else {
  1133. bl.knotenliste.append(unterblossomliste[ubllit].basis);
  1134.       }
  1136.       ubzlit = bl.ub_zeiger_liste.succ(ubzlit);
  1137.     }
  1138.   }
  1139. }
  1144. void bilde_blossom
  1145.  (const ugraph &G,
  1146.    const edge_array <GEWICHT_TYP > &gewicht,
  1147.    const node_array <DUALER_TYP > &u,
  1148.    const edge_array <bool >&gematcht,
  1149.    const list <edge >&pfad,
  1150.    list <blossom > &blossomliste,
  1151.    list <blossom > &unterblossomliste,
  1152.    list <node >&ungescannt,
  1153.    node_array <list_item >&blossom_zu_knoten,
  1154.    node_array <KANTENLISTE > &brauchbare_kanten,
  1155.    node_array <edge >&d2_kante) {
  1157.   node neue_basis;
  1158.   list_item neues_blossom;
  1159.   list <list_item >zliste;
  1160.   list <node >nliste;
  1161.   edge hilfskante;
  1165.   edge e1 = pfad.inf(pfad.first());
  1166.   edge e2 = pfad.inf(pfad.last());
  1168.   node i1 = G.source(e1);
  1169.   node i2 = G.target(e1);
  1170.   node i3 = G.source(e2);
  1171.   node i4 = G.target(e2);
  1173.   if ((blossom_zu_knoten[i1] == blossom_zu_knoten[i3]) ||
  1174.     (blossom_zu_knoten[i1] == blossom_zu_knoten[i4])) {
  1175.     neue_basis = blossomliste[blossom_zu_knoten[i1]].basis;
  1176.   }
  1178.   else
  1179.     neue_basis = blossomliste[blossom_zu_knoten[i2]].basis;
  1183.   list_item litpfad = pfad.first();
  1185.   while (pfad.succ(litpfad) != nil) {
  1187.     list_item bllit;
  1188.     edge e1 = pfad.inf(litpfad);
  1189.     edge e2 = pfad.inf(pfad.succ(litpfad));
  1191.     node i1 = G.source(e1);
  1192.     node i2 = G.target(e1);
  1193.     node i3 = G.source(e2);
  1194.     node i4 = G.target(e2);
  1196.     if ((blossom_zu_knoten[i1] == blossom_zu_knoten[i3]) ||
  1197.       (blossom_zu_knoten[i1] == blossom_zu_knoten[i4])) {
  1198.       bllit = blossom_zu_knoten[i1];
  1199.     }
  1201.     else
  1202.       bllit = blossom_zu_knoten[i2];
  1206.     if (!blossomliste[bllit].knotenliste.empty()) {
  1207.       list_item knotenlit = blossomliste[bllit].knotenliste.first();
  1209.       while (knotenlit != nil) {
  1210. node i = blossomliste[bllit].knotenliste[knotenlit];
  1211. nliste.append(i);
  1213. knotenlit = blossomliste[bllit].knotenliste.succ(knotenlit);
  1214.       }
  1215.     }
  1217.     else {
  1218.       node i = blossomliste[bllit].basis;
  1220.       nliste.append(i);
  1221.     }
  1224.     if (blossomliste[bllit].typ == T) {
  1225.       neues_s_blossom(G, gewicht, u, blossomliste, blossom_zu_knoten, gematcht,
  1226. blossomliste[bllit], ungescannt, brauchbare_kanten, d2_kante);
  1227.     }
  1230.     blossom bl = blossomliste.del_item(bllit);
  1231.     bllit = unterblossomliste.append(bl);
  1232.     unterblossomliste[bllit].typ = UNMARKIERT;
  1233.     unterblossomliste[bllit].kante = nil;
  1235.     zliste.append(bllit);
  1239.     litpfad = pfad.succ(litpfad);
  1240.   }
  1243.   list_item bllit = blossom_zu_knoten[neue_basis];
  1244.   blossom bl = blossomliste.del_item(bllit);
  1245.   hilfskante = bl.kante;
  1246.   bllit = unterblossomliste.append(bl);
  1247.   unterblossomliste[bllit].typ = UNMARKIERT;
  1248.   unterblossomliste[bllit].kante = nil;
  1250.   zliste.append(bllit);
  1252.   if (!bl.knotenliste.empty()) {
  1253.     list_item lit = bl.knotenliste.first();
  1255.     while (lit != nil) {
  1256.       nliste.append(bl.knotenliste.inf(lit));
  1257.       lit = bl.knotenliste.succ(lit);
  1258.     }
  1259.   }
  1261.   else
  1262.     nliste.append(bl.basis);
  1268.   bl = blossom(zliste, pfad, nliste, neue_basis);
  1269.   bl.typ = S;
  1270.   bl.kante = hilfskante;
  1271.   neues_blossom = blossomliste.append(bl);
  1275.   list_item litn = nliste.first();
  1277.   while (litn != nil) {
  1278.     node i = nliste[litn];
  1279.     blossom_zu_knoten[i] = neues_blossom;
  1281.     litn = nliste.succ(litn);
  1282.   }
  1286.   if (!blossomliste[neues_blossom].ub_zeiger_liste.empty()) {
  1287.     list_item ubzlit = blossomliste[neues_blossom].ub_zeiger_liste.first();
  1289.     while (ubzlit != nil) {
  1290.       list_item ubllit = blossomliste[neues_blossom].ub_zeiger_liste[ubzlit];
  1292.       if (unterblossomliste[ubllit].d3_kante != nil) {
  1293. edge e = unterblossomliste[ubllit].d3_kante;
  1294. node i = G.source(e);
  1295. node j = G.target(e);
  1296. DUALER_TYP pi = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  1298. if ((blossom_zu_knoten[i] == blossom_zu_knoten[j]) ||
  1299.   (pi == 0) || (pi < 0 && (-pi) < GENAUIGKEIT) || (pi > 0 && pi < GENAUIGKEIT)) {
  1300.   unterblossomliste[ubllit].d3_kante = nil;
  1303.   list <list_item >loesche_kante;
  1305.   if (!unterblossomliste[ubllit].adj_s_blossoms.empty()) {
  1306.     list_item kantenlit = unterblossomliste[ubllit].adj_s_blossoms.first();
  1308.     while (kantenlit != nil) {
  1309.       edge e = unterblossomliste[ubllit].adj_s_blossoms[kantenlit];
  1311.       DUALER_TYP pi = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  1313.       if ((blossom_zu_knoten[G.source(e)] != blossom_zu_knoten[G.target(e)]) &&
  1314. (pi > GENAUIGKEIT || pi < -GENAUIGKEIT)) {
  1315. if (unterblossomliste[ubllit].d3_kante == nil)
  1316.   unterblossomliste[ubllit].d3_kante = e;
  1318. else {
  1319.   edge e_min = unterblossomliste[ubllit].d3_kante;
  1321.   DUALER_TYP pi_min = u[G.source(e_min)] + u[G.target(e_min)] - gewicht[e_min];
  1323.   if (pi < pi_min)
  1324.     unterblossomliste[ubllit].d3_kante = e;
  1325. }
  1326.       }
  1328.       else
  1329. loesche_kante.append(kantenlit);
  1331.       kantenlit = unterblossomliste[ubllit].adj_s_blossoms.succ(kantenlit);
  1332.     }
  1333.   }
  1336.   while (!loesche_kante.empty()) {
  1337.     list_item lit = loesche_kante.pop();
  1338.     blossomliste[ubllit].adj_s_blossoms.del_item(lit);
  1339.   }
  1342. }
  1343.       }
  1345.       ubzlit = blossomliste[neues_blossom].ub_zeiger_liste.succ(ubzlit);
  1346.     }
  1347.   }
  1350.   if (!blossomliste[neues_blossom].ub_zeiger_liste.empty()) {
  1351.     list_item ubzlit = blossomliste[neues_blossom].ub_zeiger_liste.first();
  1353.     while (ubzlit != nil) {
  1354.       list_item ubllit = blossomliste[neues_blossom].ub_zeiger_liste[ubzlit];
  1356.       if (unterblossomliste[ubllit].d3_kante != nil) {
  1358. edge e = unterblossomliste[ubllit].d3_kante;
  1360. DUALER_TYP pi_e = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  1362. if (blossomliste[neues_blossom].d3_kante == nil)
  1363.   blossomliste[neues_blossom].d3_kante = e;
  1365. else {
  1366.   edge e_min = blossomliste[neues_blossom].d3_kante;
  1367.   DUALER_TYP pi_min;
  1368.   pi_min = u[G.source(e_min)] + u[G.target(e_min)] - gewicht[e_min];
  1370.   if (pi_e < pi_min)
  1371.     blossomliste[neues_blossom].d3_kante = e;
  1372. }
  1374. blossomliste[neues_blossom].adj_s_blossoms.append(e);
  1376. unterblossomliste[ubllit].d3_kante = nil;
  1377.       }
  1379.       unterblossomliste[ubllit].adj_s_blossoms.clear();
  1381.       ubzlit = blossomliste[neues_blossom].ub_zeiger_liste.succ(ubzlit);
  1382.     }
  1383.   }
  1386. }
  1390. int aendere_duale_variablen
  1391.  (const ugraph &G, const edge_array <GEWICHT_TYP > &gewicht,
  1392.    const edge_array <bool >&gematcht,
  1393.    const node_array <list_item >&blossom_zu_knoten,
  1394.    const node_array <edge >&gematchte_kante,
  1395.    list <blossom > &blossomliste,
  1396.    node_array <DUALER_TYP > &u,
  1397.    list <node >&ungescannt,
  1398.    node_array <KANTENLISTE > &brauchbare_kanten,
  1399.    const node_array <edge >&d2_kante) {
  1401.   DUALER_TYP delta, d_1, d_2, d_3, d_4;
  1402.   int erg_aendere;
  1405.   node_array <bool >schon_eingefuegt;
  1406.   schon_eingefuegt.init(G, false);
  1410.   d_1 = 0;
  1411.   d_2 = 0;
  1413.   node i;
  1414.   forall_nodes (i, G) {
  1415.     if (gematchte_kante[i] == nil) {
  1416.       d_1 = u[i];
  1417.     }
  1419.     list_item bllit = blossom_zu_knoten[i];
  1421.     if ((blossomliste[bllit].typ == UNMARKIERT) && (d2_kante[i] != nil)) {
  1422.       edge e = d2_kante[i];
  1424.       DUALER_TYP pi = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  1426.       if ((d_2 == 0) || (pi < d_2)) {
  1427. d_2 = pi;
  1428.       }
  1429.     }
  1430.   }
  1432.   if (d_2 == 0)
  1433.     d_2 = d_1;
  1436.   d_3 = d_1;
  1437.   d_4 = 2 * d_1;
  1439.   if (!blossomliste.empty()) {
  1440.     list_item bllit = blossomliste.first();
  1442.     while (bllit != nil) {
  1443.       if ((blossomliste[bllit].typ == S) && (blossomliste[bllit].d3_kante != nil)) {
  1444. edge e = blossomliste[bllit].d3_kante;
  1446. DUALER_TYP pi = (u[G.source(e)] + u[G.target(e)] - gewicht[e]) / 2;
  1447. if (pi < d_3)
  1448.   d_3 = pi;
  1449.       }
  1451.       else if ((!blossomliste[bllit].knotenliste.empty()) &&
  1452. (blossomliste[bllit].typ == T)) {
  1453. if (blossomliste[bllit].z < d_4) {
  1454.   d_4 = blossomliste[bllit].z;
  1455. }
  1456.       }
  1458.       bllit = blossomliste.succ(bllit);
  1459.     }
  1460.   }
  1462.   d_4 = d_4 / 2;
  1465.   if ((d_1 <= d_2) && (d_1 <= d_3) && (d_1 <= d_4)) {
  1466.     delta = d_1;
  1467.     erg_aendere = 1;
  1468.   }
  1470.   else if ((d_2 <= d_3) && (d_2 <= d_4)) {
  1471.     delta = d_2;
  1472.     erg_aendere = 0;
  1473.   }
  1475.   else if (d_3 <= d_4) {
  1476.     delta = d_3;
  1477.     erg_aendere = 0;
  1478.   }
  1480.   else {
  1481.     delta = d_4;
  1482.     erg_aendere = -1;
  1483.   }
  1487.   forall_nodes (i, G) {
  1488.     if (blossomliste[blossom_zu_knoten[i]].typ == S) {
  1489.       u[i] = u[i] - delta;
  1490.     }
  1492.     if (blossomliste[blossom_zu_knoten[i]].typ == T) {
  1493.       u[i] = u[i] + delta;
  1494.     }
  1495.   }
  1498.   if (!blossomliste.empty()) {
  1499.     list_item bllit = blossomliste.first();
  1501.     while (bllit != nil) {
  1502.       if (!blossomliste[bllit].knotenliste.empty()) {
  1503. if (blossomliste[bllit].typ == S) {
  1504.   blossomliste[bllit].z = blossomliste[bllit].z + 2 * delta;
  1505. }
  1507. else if (blossomliste[bllit].typ == T) {
  1508.   blossomliste[bllit].z = blossomliste[bllit].z - 2 * delta;
  1509. }
  1510.       }
  1512.       bllit = blossomliste.succ(bllit);
  1513.     }
  1514.   }
  1518.   if (delta == d_1)
  1519.     return erg_aendere;
  1520.   forall_nodes (i, G) {
  1521.     if ((blossomliste[blossom_zu_knoten[i]].typ == UNMARKIERT) &&
  1522.       (d2_kante[i] != nil)) {
  1523.       edge e = d2_kante[i];
  1524.       node j;
  1526.       if (i == G.target(e))
  1527. j = G.source(e);
  1528.       else
  1529. j = G.target(e);
  1531.       DUALER_TYP pi = u[i] + u[j] - gewicht[e];
  1533.       if ((pi == 0) ||
  1534. ((pi < 0) && ((-pi) < GENAUIGKEIT)) ||
  1535. ((pi > 0) && (pi < GENAUIGKEIT))) {
  1536. brauchbare_kanten[j].append(e);
  1538. if (schon_eingefuegt[j] == false) {
  1539.   ungescannt.push(j);
  1540.   schon_eingefuegt[j] = true;
  1541. }
  1542.       }
  1543.     }
  1544.   }
  1547.   if (!blossomliste.empty()) {
  1548.     edge_array <bool >kante_schon_betrachtet(G, false);
  1549.     list_item bllit = blossomliste.first();
  1551.     while (bllit != nil) {
  1552.       if ((blossomliste[bllit].typ == S) && (blossomliste[bllit].d3_kante != nil)) {
  1553. edge e = blossomliste[bllit].d3_kante;
  1555. DUALER_TYP pi = u[G.source(e)] + u[G.target(e)] - gewicht[e];
  1557. if ((pi == 0) ||
  1558.   ((pi < 0) && ((-pi) < GENAUIGKEIT)) ||
  1559.   ((pi > 0) && (pi < GENAUIGKEIT))) {
  1560.   if (schon_eingefuegt[G.source(e)] == false) {
  1561.     ungescannt.push(G.source(e));
  1562.     schon_eingefuegt[G.source(e)] = true;
  1563.   }
  1565.   if (schon_eingefuegt[G.target(e)] == false) {
  1566.     ungescannt.push(G.target(e));
  1567.     schon_eingefuegt[G.target(e)] = true;
  1568.   }
  1570.   if (kante_schon_betrachtet[e] == false) {
  1571.     brauchbare_kanten[G.source(e)].append(e);
  1572.     brauchbare_kanten[G.target(e)].append(e);
  1573.     kante_schon_betrachtet[e] = true;
  1574.   }
  1575. }
  1576.       }
  1578.       bllit = blossomliste.succ(bllit);
  1579.     }
  1580.   }
  1582.   return erg_aendere;
  1583. }
  1584. ;
  1586. void expandiere_blossoms(
  1587.    const ugraph &G,
  1588.    const edge_array <GEWICHT_TYP > &gewicht,
  1589.    const node_array <DUALER_TYP > &u,
  1590.    const edge_array <bool >&gematcht,
  1591.    list <blossom > &blossomliste,
  1592.    list <blossom > &unterblossomliste,
  1593.    list <node >&ungescannt,
  1594.    node_array <list_item >&blossom_zu_knoten,
  1595.    node_array <KANTENLISTE > &brauchbare_kanten,
  1596.    node_array <edge >&d2_kante)
  1597. {
  1599.   list <list_item >entferne_liste, verschiebe_liste;
  1603.   list_item bllit = blossomliste.first();
  1605.   while (bllit != nil) {
  1606.     if ((!blossomliste[bllit].knotenliste.empty()) &&
  1607.       (blossomliste[bllit].typ == T) && (blossomliste[bllit].z == 0)) {
  1611.       edge e = blossomliste[bllit].kante;
  1612.       node i;
  1614.       if (blossom_zu_knoten[G.source(e)] == bllit)
  1615. i = G.source(e);
  1616.       else if (blossom_zu_knoten[G.target(e)] == bllit)
  1617. i = G.target(e);
  1621.       list_item knotenlit = blossomliste[bllit].knotenliste.first();
  1622.       node j = blossomliste[bllit].knotenliste.inf(knotenlit);
  1623.       list_item ubzlit = blossomliste[bllit].ub_zeiger_liste.first();
  1624.       list_item ubllit = blossomliste[bllit].ub_zeiger_liste.inf(ubzlit);
  1625.       list_item kantenlit = blossomliste[bllit].kantenliste.first();
  1628.       while (i != j) {
  1629. if (j == unterblossomliste[ubllit].basis) {
  1630.   ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1631.   ubllit = blossomliste[bllit].ub_zeiger_liste.inf(ubzlit);
  1633.   kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1634. }
  1636. knotenlit = blossomliste[bllit].knotenliste.succ(knotenlit);
  1637. j = blossomliste[bllit].knotenliste.inf(knotenlit);
  1638.       }
  1642.       unterblossomliste[ubllit].typ = T;
  1643.       unterblossomliste[ubllit].kante = e;
  1646.       e = blossomliste[bllit].kantenliste.inf(kantenlit);
  1648.       if (gematcht[e] == true) {
  1650. list_item ubzlit_kopie = ubzlit;
  1651. list_item kantenlit_kopie = kantenlit;
  1653. ubzlit = blossomliste[bllit].ub_zeiger_liste.pred(ubzlit);
  1655. while (ubzlit != nil) {
  1656.   e = blossomliste[bllit].kantenliste.inf(kantenlit);
  1657.   ubllit = blossomliste[bllit].ub_zeiger_liste.inf(ubzlit);
  1659.   if (gematcht[e] == true) {
  1660.     unterblossomliste[ubllit].typ = S;
  1661.     unterblossomliste[ubllit].kante = e;
  1662.   }
  1664.   else {
  1665.     unterblossomliste[ubllit].typ = T;
  1666.     unterblossomliste[ubllit].kante = e;
  1667.   }
  1669.   kantenlit = blossomliste[bllit].kantenliste.pred(kantenlit);
  1670.   ubzlit = blossomliste[bllit].ub_zeiger_liste.pred(ubzlit);
  1671. }
  1674. ubzlit = blossomliste[bllit].ub_zeiger_liste.last();
  1675. ubllit = blossomliste[bllit].ub_zeiger_liste[ubzlit];
  1676. e = blossomliste[bllit].kantenliste.inf(kantenlit);
  1678. unterblossomliste[ubllit].typ = T;
  1679. unterblossomliste[ubllit].kante = e;
  1683. ubzlit = ubzlit_kopie;
  1684. kantenlit = kantenlit_kopie;
  1686. ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1687. kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1688. kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1690. while (kantenlit != nil) {
  1692.   e = blossomliste[bllit].kantenliste[kantenlit];
  1694.   list_item ubllit = blossomliste[bllit].ub_zeiger_liste[ubzlit];
  1696.   list_item ubzlit_succ = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1697.   list_item ubllit_succ = blossomliste[bllit].ub_zeiger_liste[ubzlit_succ];
  1699.   if (!unterblossomliste[ubllit].knotenliste.empty()) {
  1700.     list_item knotenlit = unterblossomliste[ubllit].knotenliste.first();
  1702.     while ((knotenlit != nil) && (unterblossomliste[ubllit].typ == UNMARKIERT)) {
  1703.       node i = unterblossomliste[ubllit].knotenliste[knotenlit];
  1705.       if (!brauchbare_kanten[i].empty()) {
  1706. edge e_brauchbar = brauchbare_kanten[i].pop();
  1708. unterblossomliste[ubllit].typ = T;
  1709. unterblossomliste[ubllit].kante = e_brauchbar;
  1710. unterblossomliste[ubllit_succ].typ = S;
  1711. unterblossomliste[ubllit_succ].kante = e;
  1712.       }
  1714.       knotenlit = unterblossomliste[ubllit].knotenliste.succ(knotenlit);
  1715.     }
  1716.   }
  1718.   else {
  1719.     node i = unterblossomliste[ubllit].basis;
  1721.     if (!brauchbare_kanten[i].empty()) {
  1722.       edge e_brauchbar = brauchbare_kanten[i].pop();
  1724.       unterblossomliste[ubllit].typ = T;
  1725.       unterblossomliste[ubllit].kante = e_brauchbar;
  1726.       unterblossomliste[ubllit_succ].typ = S;
  1727.       unterblossomliste[ubllit_succ].kante = e;
  1728.     }
  1729.   }
  1732.   if (!unterblossomliste[ubllit_succ].knotenliste.empty()) {
  1733.     list_item knotenlit = unterblossomliste[ubllit_succ].knotenliste.first();
  1735.     while ((knotenlit != nil) &&
  1736.       (unterblossomliste[ubllit_succ].typ == UNMARKIERT)) {
  1737.       node i = unterblossomliste[ubllit_succ].knotenliste[knotenlit];
  1739.       if (!brauchbare_kanten[i].empty()) {
  1740. edge e_brauchbar = brauchbare_kanten[i].pop();
  1742. unterblossomliste[ubllit_succ].typ = T;
  1743. unterblossomliste[ubllit_succ].kante = e_brauchbar;
  1744. unterblossomliste[ubllit].typ = S;
  1745. unterblossomliste[ubllit].kante = e;
  1746.       }
  1748.       knotenlit = unterblossomliste[ubllit_succ].knotenliste.succ(knotenlit);
  1749.     }
  1750.   }
  1752.   else {
  1753.     node i = unterblossomliste[ubllit_succ].basis;
  1755.     if (!brauchbare_kanten[i].empty()) {
  1756.       edge e_brauchbar = brauchbare_kanten[i].pop();
  1758.       unterblossomliste[ubllit_succ].typ = T;
  1759.       unterblossomliste[ubllit_succ].kante = e_brauchbar;
  1760.       unterblossomliste[ubllit].typ = S;
  1761.       unterblossomliste[ubllit].kante = e;
  1762.     }
  1763.   }
  1767.   ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1768.   ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1769.   kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1770.   kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1771. }
  1774.       }
  1777.       else if (gematcht[e] != true) {
  1779. list_item ubzlit_kopie = ubzlit;
  1780. list_item kantenlit_kopie = kantenlit;
  1782. kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1783. ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1785. while (kantenlit != nil) {
  1786.   e = blossomliste[bllit].kantenliste.inf(kantenlit);
  1787.   ubllit = blossomliste[bllit].ub_zeiger_liste.inf(ubzlit);
  1789.   if (gematcht[e] == true) {
  1790.     unterblossomliste[ubllit].typ = S;
  1791.     unterblossomliste[ubllit].kante = e;
  1792.   }
  1794.   else {
  1795.     unterblossomliste[ubllit].typ = T;
  1796.     unterblossomliste[ubllit].kante = e;
  1797.   }
  1799.   kantenlit = blossomliste[bllit].kantenliste.succ(kantenlit);
  1800.   ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1801. }
  1805. ubzlit = ubzlit_kopie;
  1806. kantenlit = kantenlit_kopie;
  1808. ubzlit = blossomliste[bllit].ub_zeiger_liste.pred(ubzlit);
  1809. kantenlit = blossomliste[bllit].kantenliste.pred(kantenlit);
  1811. while (kantenlit != nil) {
  1813.   e = blossomliste[bllit].kantenliste[kantenlit];
  1815.   list_item ubllit = blossomliste[bllit].ub_zeiger_liste[ubzlit];
  1817.   list_item ubzlit_pred = blossomliste[bllit].ub_zeiger_liste.pred(ubzlit);
  1818.   list_item ubllit_pred = blossomliste[bllit].ub_zeiger_liste[ubzlit_pred];
  1820.   if (!unterblossomliste[ubllit].knotenliste.empty()) {
  1821.     list_item knotenlit = unterblossomliste[ubllit].knotenliste.first();
  1823.     while ((knotenlit != nil) && (unterblossomliste[ubllit].typ == UNMARKIERT)) {
  1824.       node i = unterblossomliste[ubllit].knotenliste[knotenlit];
  1826.       if (!brauchbare_kanten[i].empty()) {
  1827. edge e_brauchbar = brauchbare_kanten[i].pop();
  1829. unterblossomliste[ubllit].typ = T;
  1830. unterblossomliste[ubllit].kante = e_brauchbar;
  1831. unterblossomliste[ubllit_pred].typ = S;
  1832. unterblossomliste[ubllit_pred].kante = e;
  1833.       }
  1835.       knotenlit = unterblossomliste[ubllit].knotenliste.succ(knotenlit);
  1836.     }
  1837.   }
  1839.   else {
  1840.     node i = unterblossomliste[ubllit].basis;
  1842.     if (!brauchbare_kanten[i].empty()) {
  1843.       edge e_brauchbar = brauchbare_kanten[i].pop();
  1845.       unterblossomliste[ubllit].typ = T;
  1846.       unterblossomliste[ubllit].kante = e_brauchbar;
  1847.       unterblossomliste[ubllit_pred].typ = S;
  1848.       unterblossomliste[ubllit_pred].kante = e;
  1849.     }
  1850.   }
  1853.   if (!unterblossomliste[ubllit_pred].knotenliste.empty()) {
  1854.     list_item knotenlit = unterblossomliste[ubllit_pred].knotenliste.first();
  1856.     while ((knotenlit != nil) &&
  1857.       (unterblossomliste[ubllit_pred].typ == UNMARKIERT)) {
  1858.       node i = unterblossomliste[ubllit_pred].knotenliste[knotenlit];
  1860.       if (!brauchbare_kanten[i].empty()) {
  1861. edge e_brauchbar = brauchbare_kanten[i].pop();
  1863. unterblossomliste[ubllit_pred].typ = T;
  1864. unterblossomliste[ubllit_pred].kante = e_brauchbar;
  1865. unterblossomliste[ubllit].typ = S;
  1866. unterblossomliste[ubllit].kante = e;
  1867.       }
  1869.       knotenlit = unterblossomliste[ubllit_pred].knotenliste.succ(knotenlit);
  1870.     }
  1871.   }
  1873.   else {
  1874.     node i = unterblossomliste[ubllit_pred].basis;
  1876.     if (!brauchbare_kanten[i].empty()) {
  1877.       edge e_brauchbar = brauchbare_kanten[i].pop();
  1879.       unterblossomliste[ubllit_pred].typ = T;
  1880.       unterblossomliste[ubllit_pred].kante = e_brauchbar;
  1881.       unterblossomliste[ubllit].typ = S;
  1882.       unterblossomliste[ubllit].kante = e;
  1883.     }
  1884.   }
  1888.   ubzlit = blossomliste[bllit].ub_zeiger_liste.pred(ubzlit);
  1889.   ubzlit = blossomliste[bllit].ub_zeiger_liste.pred(ubzlit);
  1890.   kantenlit = blossomliste[bllit].kantenliste.pred(kantenlit);
  1891.   kantenlit = blossomliste[bllit].kantenliste.pred(kantenlit);
  1892. }
  1895.       }
  1901.       ubzlit = blossomliste[bllit].ub_zeiger_liste.first();
  1903.       while (ubzlit != nil) {
  1904. ubllit = blossomliste[bllit].ub_zeiger_liste.inf(ubzlit);
  1905. verschiebe_liste.append(ubllit);
  1907. ubzlit = blossomliste[bllit].ub_zeiger_liste.succ(ubzlit);
  1908.       }
  1912.       entferne_liste.append(bllit);
  1917.     }
  1919.     bllit = blossomliste.succ(bllit);
  1920.   }
  1924.   while (!entferne_liste.empty()) {
  1925.     blossomliste.del_item(entferne_liste.pop());
  1926.   }
  1930.   if (!verschiebe_liste.empty()) {
  1931.     list_item vlit = verschiebe_liste.first();
  1932.     list_item ubllit;
  1934.     while (vlit != nil) {
  1935.       ubllit = verschiebe_liste.inf(vlit);
  1936.       list_item hilfslit = blossomliste.append(unterblossomliste[ubllit]);
  1937.       unterblossomliste.del_item(verschiebe_liste.inf(vlit));
  1940.       if (!blossomliste[hilfslit].knotenliste.empty()) {
  1941. list_item knotenlit = blossomliste[hilfslit].knotenliste.first();
  1943. while (knotenlit != nil) {
  1944.   node i = blossomliste[hilfslit].knotenliste[knotenlit];
  1945.   blossom_zu_knoten[i] = hilfslit;
  1947.   knotenlit = blossomliste[hilfslit].knotenliste.succ(knotenlit);
  1948. }
  1949.       }
  1951.       else {
  1952. node i = blossomliste[hilfslit].basis;
  1953. blossom_zu_knoten[i] = hilfslit;
  1954.       }
  1956.       vlit = verschiebe_liste.succ(vlit);
  1957.     }
  1958.   }
  1961.   if (!verschiebe_liste.empty()) {
  1962.     list_item vlit = verschiebe_liste.first();
  1963.     list_item hilfslit = blossomliste.last();
  1965.     while (vlit != nil) {
  1966.       if (blossomliste[hilfslit].typ == S) {
  1967. neues_s_blossom
  1968.   (G, gewicht, u, blossomliste, blossom_zu_knoten, gematcht,
  1969.   blossomliste[hilfslit], ungescannt, brauchbare_kanten, d2_kante);
  1970.       }
  1972.       hilfslit = blossomliste.pred(hilfslit);
  1973.       vlit = verschiebe_liste.succ(vlit);
  1974.     }
  1975.   }
  1978. }
  1983. void matchingtest(const ugraph &G, const edge_array <bool >&gematcht)
  1984. {
  1985.   node_array <bool >knoten_betrachtet(G, false);
  1986.   edge e;
  1988.   forall_edges (e, G) {
  1989.     node i = G.source(e);
  1990.     node j = G.target(e);
  1992.     if (gematcht[e] == true) {
  1993.       if (knoten_betrachtet[i] == false)
  1994. knoten_betrachtet[i] = true;
  1996.       else {
  1997. cout << "Knoten ";
  1998. G.print_node(i);
  1999. cout << " ist Endknoten mehrerer gematchter Kanten!!!n";
  2000.       }
  2002.       if (knoten_betrachtet[j] == false)
  2003. knoten_betrachtet[j] = true;
  2005.       else {
  2006. cout << "Knoten ";
  2007. G.print_node(j);
  2008. cout << " ist Endknoten mehrerer gematchter Kanten!!!n";
  2009.       }
  2010.     }
  2011.   }
  2013.   cout << "Test auf Matching abgeschlossen!n";
  2014.   return;
  2015. }
  2019. void bed1test(const ugraph &G, const edge_array <GEWICHT_TYP > &gewicht, const
  2020.    node_array <DUALER_TYP > &u, const list <blossom > &blossomliste, const
  2021.    list <blossom > &unterblossomliste, const node_array <list_item >&blossom_zu_knoten)
  2022. {
  2024.   node i;
  2026.   forall_nodes (i, G) {
  2027.     if (u[i] < 0) {
  2028.       cout << "Die duale Variable von Knoten ";
  2029.       G.print_node(i);
  2030.       cout << " ist negativn";
  2031.     }
  2032.   }
  2036.   edge e;
  2038.   forall_edges (e, G) {
  2039.     node i = G.source(e);
  2040.     node j = G.target(e);
  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. 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. 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. 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. 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. }