model_server/gedge/src/bico.cxx
/*------------------------------------------------------------------------------------------*
 *   UNION_BICO_COMPONENTS vereinigt zwei zweifache Zusammenhangskomponenten, die ber den  *
 *   Artikulationspunkt ARTI verbunden sind. Da durch die Planarisierung neue Knoten ent-   *
 *   standen sein knnen werden ab newNO die Nummern der neuen Knoten vergeben.             *
 *   Zuerst werden die Knotenlisten zusammengehngt, dabei wird die Umbenennung rckgngig  *
 *   gemacht und es werden die beiden Adjazenzlisten fr den Artikulationspunkt gesucht.    *
 *   Die Adjazenzlisten des Artikulationspunktes werden zusammengehngt.                    *
 *   Um die Vereinigung 'biconnected' zu machen wird noch eine Dummy-Kante eingefgt, die   *
 *   einen Nachbarn des Artikulationspunktes aus der einen Komponente mit einem Nachbarn    *
 *   aus der anderen Komponente verbindet.                                                  *
 *   Um zu verhindern, daa die Umbenennung mehrfach stattfindet, wird nach der ersten Um-   *
 *   benennung die name_table gelscht.                                                     *
 *------------------------------------------------------------------------------------------*/
UNION_BICO_COMPONENTS vereinigt zwei zweifache Zusammenhangskomponenten, die ber den
Artikulationspunkt ARTI verbunden sind. Da durch die Planarisierung neue Knoten ent
standen sein knnen werden ab newNO die Nummern der neuen Knoten vergeben.
Zuerst werden die Knotenlisten zusammengehngt, dabei wird die Umbenennung rckgngig
gemacht und es werden die beiden Adjazenzlisten fr den Artikulationspunkt gesucht.
Die Adjazenzlisten des Artikulationspunktes werden zusammengehngt.
Um die Vereinigung 'biconnected' zu machen wird noch eine Dummy-Kante eingefgt, die
einen Nachbarn des Artikulationspunktes aus der einen Komponente mit einem Nachbarn
aus der anderen Komponente verbindet.
Um zu verhindern, daa die Umbenennung mehrfach stattfindet, wird nach der ersten Um
benennung die name_table gelscht.
UNION_BICO_COMPONENTS vereinigt zwei zweifache Zusammenhangskomponenten die ber den Artikulationspunkt ARTI verbunden sind . Da durch die Planarisierung neue Knoten ent standen sein knnen werden ab newNO die Nummern der neuen Knoten vergeben . Zuerst werden die Knotenlisten zusammengehngt dabei wird die Umbenennung rckgngig gemacht und es werden die beiden Adjazenzlisten fr den Artikulationspunkt gesucht . Die Adjazenzlisten des Artikulationspunktes werden zusammengehngt . Um die Vereinigung ' biconnected ' zu machen wird noch eine Dummy - Kante eingefgt die einen Nachbarn des Artikulationspunktes aus der einen Komponente mit einem Nachbarn aus der anderen Komponente verbindet . Um zu verhindern daa die Umbenennung mehrfach stattfindet wird nach der ersten Um benennung die name_table gelscht .
BICO_COMP*  UNION_BICO_COMPONENTS( BICO_COMP *BC1, BICO_COMP *BC2, int ARTI, int *newNO )
{
    struct AL              *Al, *arti1, *arti2, *prevAl, *prev_of_arti2, *node1, *node2;
    DYN_NODE        *DN, *prevDN, *newDN;
    BC_EDGE         *E;
    prevAl = nil;                                                          
    Al = BC1->DG->first_AL;
    while ( Al != nil ) {
        if ( BC1->name_table != nil ) {
            if ( Al->name <= BC1->DG->old_V ) 
                Al->name = BC1->name_table[ Al->name ];
            else {
                (*newNO)++;
                Al->name = (*newNO);
            }
        }
        if ( Al->name == ARTI ) arti1 = Al;
        prevAl = Al;
        Al = Al->next_AL;
    }
    prevAl->next_AL = BC2->DG->first_AL;                    
    Al = BC2->DG->first_AL;
    while ( Al != nil ) {                                                  
        if ( BC2->name_table != nil ) {    
            if ( Al->name <= BC2->DG->old_V )
                Al->name = BC2->name_table[ Al->name ];
            else {
                (*newNO)++;
                Al->name = (*newNO);
            }
        }
        if ( Al->name == ARTI ) {
            arti2 = Al;
            prev_of_arti2 = prevAl;
        }
        prevAl = Al;
        Al = Al->next_AL;
    }
    prevDN = nil;                    
    DN = arti1->first;
    while ( DN != nil ) {
        prevDN = DN;
        DN = DN->next;
    }
    prevDN->next = arti2->first;
    node1 = prevDN->name;                 
    node2 = arti2->first->name;
    prevDN = nil;                   
    DN = node1->first;
    while ( DN->name->name != ARTI ) {
        prevDN = DN;
        DN = DN->next;
    }
    newDN = (DYN_NODE*) psetmalloc( sizeof( DYN_NODE ) );
    newDN->name = node2;
    newDN->flag = false;
    newDN->next = DN;
    if ( prevDN == nil ) 
        node1->first = newDN;
    else 
        prevDN->next = newDN;
    DN = node2->first;             
    while ( DN->name->name != ARTI )
        DN = DN->next;
    newDN = (DYN_NODE*) psetmalloc( sizeof( DYN_NODE ) );
    newDN->name = node1;
    newDN->flag = false;
    newDN->next = DN->next;
    DN->next = newDN;
    E = (BC_EDGE*) psetmalloc( sizeof( BC_EDGE ) );                   
    E->source = node1->name;
    E->dest   = node2->name;
    E->next   = BC1->dummies;
    BC1->dummies  = E;  
    while ( E->next != nil ) E = E->next;        
    E->next = BC2->dummies;
    prev_of_arti2->next_AL = arti2->next_AL;         
    BC1->DG->old_V += BC2->DG->old_V - 1;
    BC1->DG->new_V += BC2->DG->new_V - 1;
    if ( BC1->name_table != nil ) {
        BC1->name_table = nil;
    }
    return( BC1 );
}
BICO_COMP * UNION_BICO_COMPONENTS ( BICO_COMP * BC1 , BICO_COMP * BC2 , int ARTI , int * newNO ) { struct AL * Al , * arti1 , * arti2 , * prevAl , * prev_of_arti2 , * node1 , * node2 ; DYN_NODE * DN , * prevDN , * newDN ; BC_EDGE * E ; prevAl = nil ; Al = BC1 -> DG -> first_AL ; while ( Al != nil ) { if ( BC1 -> name_table != nil ) { if ( Al -> name <= BC1 -> DG -> old_V ) Al -> name = BC1 -> name_table [ Al -> name ] ; else { ( * newNO ) ++ ; Al -> name = ( * newNO ) ; } } if ( Al -> name == ARTI ) arti1 = Al ; prevAl = Al ; Al = Al -> next_AL ; } prevAl -> next_AL = BC2 -> DG -> first_AL ; Al = BC2 -> DG -> first_AL ; while ( Al != nil ) { if ( BC2 -> name_table != nil ) { if ( Al -> name <= BC2 -> DG -> old_V ) Al -> name = BC2 -> name_table [ Al -> name ] ; else { ( * newNO ) ++ ; Al -> name = ( * newNO ) ; } } if ( Al -> name == ARTI ) { arti2 = Al ; prev_of_arti2 = prevAl ; } prevAl = Al ; Al = Al -> next_AL ; } prevDN = nil ; DN = arti1 -> first ; while ( DN != nil ) { prevDN = DN ; DN = DN -> next ; } prevDN -> next = arti2 -> first ; node1 = prevDN -> name ; node2 = arti2 -> first -> name ; prevDN = nil ; DN = node1 -> first ; while ( DN -> name -> name != ARTI ) { prevDN = DN ; DN = DN -> next ; } newDN = ( DYN_NODE * ) psetmalloc ( sizeof ( DYN_NODE ) ) ; newDN -> name = node2 ; newDN -> flag = false ; newDN -> next = DN ; if ( prevDN == nil ) node1 -> first = newDN ; else prevDN -> next = newDN ; DN = node2 -> first ; while ( DN -> name -> name != ARTI ) DN = DN -> next ; newDN = ( DYN_NODE * ) psetmalloc ( sizeof ( DYN_NODE ) ) ; newDN -> name = node1 ; newDN -> flag = false ; newDN -> next = DN -> next ; DN -> next = newDN ; E = ( BC_EDGE * ) psetmalloc ( sizeof ( BC_EDGE ) ) ; E -> source = node1 -> name ; E -> dest = node2 -> name ; E -> next = BC1 -> dummies ; BC1 -> dummies = E ; while ( E -> next != nil ) E = E -> next ; E -> next = BC2 -> dummies ; prev_of_arti2 -> next_AL = arti2 -> next_AL ; BC1 -> DG -> old_V += BC2 -> DG -> old_V - 1 ; BC1 -> DG -> new_V += BC2 -> DG -> new_V - 1 ; if ( BC1 -> name_table != nil ) { BC1 -> name_table = nil ; } return ( BC1 ) ; }
UNION_BICO_COMPONENTS vereinigt zwei zweifache Zusammenhangskomponenten, die ber den
   Artikulationspunkt ARTI verbunden sind.
UNION_BICO_COMPONENTS vereinigt zwei zweifache Zusammenhangskomponenten die ber den Artikulationspunkt ARTI verbunden sind .
//if (debug) printf( "Find ARTI in BC1\n" ); /* arti1 suchen */ //if( debug) printf( "Find ARTI in BC2\n" ); /* Knotenlisten zusammenhngen */ /* arti2 suchen */ /* Adjazenzlisten des Aritkulationspunktes vereinigen */ /* Dummy-Kante zwischen node1 und node2 einggen */ //if (debug) printf( "Add Dummy-Edge [ %d, %d ] \n", node1->name, node2->name );     /* node2 vor ARTI in Adjazenzliste von node1 eintragen */ /* node1 nach ARTI in Adjazenzliste von node2 eintragen */ /* Dummy-Kante eintragen */ /* Listen der Dummy-Kanten zusammenhngen */ /* Zweites Auftreten von ARTI lschen */ /* psetfree( BC1->name_table ); */