Datentyp Graph in EWS

Graphen in EWS werden meist als Nachbarschaftsliste kodiert.

Nachbarschaftsliste

Bei dieser Kodierung eines Graphen Zu einer gegebenen Knotennummer werden alle Knoten aufgeführt, die mit diesem verbunden sind. Betrachte folgendes Beispiel: 
0------5         1
|      |          
|      |          
|      |          
2------3---------4
Als erstes bemerkt man, daß die Knoten beginnend mit 0 durch numeriert werden. Wir erhalten folgende Nachbarschaftsliste 
              2   5    
              -        
              0   3    
              5   2   4
              3        
              0   3
Schreibt man dies in einen Vektor, so weiß man natürlich nicht, wie lang er ist und wo die Information für einen Knoten endet. Deshalb werden zuerst die Anfangspositionen der einzelnen Knoten im Vektor notiert und als letzter Eintrag des Vorspanns die erste ungültige Position im Vektor, also im obigen Beispiel: 
           7 9 9 11 14 15 17 2 5 0 3 5 2 4 3 0 3
Man sieht auch, daß die Information nicht sortiert sein braucht. Dies ist die Datenstruktur für die Nachbarschaftsliste, sie wird in drei verschiedenen Basistypen verwendet, als UCHAR vektor, als USHORT vektor, als ULONG vektor. UCHAR,USHORT,ULONG sind in <EWS/intern.h> definiert.

Kantennumerierung

Aus dieser Struktur erhält man auch eine Numerierung der Kanten, nämlich nach ihren Auftauchen in der Nachbarschaftsliste. Im obigen Beispiel ist 
    die 0-te Kante, die zwischen 0 und 2
    die 1-te Kante, die zwischen 0 und 5
    die 2-te Kante, die zwischen 2 und 3
    die 3-te Kante, die zwischen 3 und 5
    die 4-te Kante, die zwischen 3 und 4
Diese Numerierung braucht man bei Informationen für die Kanten.

gerichtete Graphen

Handelt es sich um gerichtete Graphen so gibt es eine ähnliche Datenstruktur, wieder ein Beispiel 

            1 <--------> 5                4
            |                              
            |                              
            |                              
            V                              
            0  -----------> 2 <-----------3
in der Nachbarschaftsliste wird nun eingetragen, zu welchen Knoten man vom Knoten i aus kommt 

           2  
           0 5
           -  
           2  
           -  
           1
Zuletzt kommen als Vorspann wieder die Plätze, sodaß man 


           7 8 10 10 11 11 12          2 0 5 2 1
erhält und man erhält auch wieder eine Kantennumerierung 

     0 : von 0 nach 2
     1 : von 1 nach 0
     2 : von 1 nach 5
     3 : von 3 nach 2
     4 : von 5 nach 1
Obige Datenstruktur gibt es als UCHAR USHORT und ULONG Vektor.


Send comments or suggestions to:
ews@btm2x2.mat.uni-bayreuth.de

AK080396
Home