Suuntaamattoman verkon funktioiden esittelyt

Suuntaamaton verkko G=(V, E) koostuu solmuista ja kaarista kuten suunnattu verkkokin, mutta suuntaamattoman verkon kaaria ei varusteta suunnalla. Tämä merkitsee, että kaari (u, v) on järjestämätön pari ja se voidaan yhtä hyvin esittää muodossa (v, u). Koska kaarella ei ole suuntaa, voidaan molempia kaareen liittyviä solmuja kutsua kaaren päätesolmuiksi. Kaaren päätesolmut ovat toistensa naapureita, toisin sanoen naapuruussuhde on symmetrinen. Suunatusta verkosta poiketen, suuntaamattoman verkon kaaren ei sallita johtavan solmusta itseensä ja kahden eri solmun välillä saa olla vain yksi kaari. Abstraktin tietotyypin "suuntamaton verkko" operaatiot ovat muutamaa poikkeusta lukuunottamatta samat kuin suunnatun verkon operaatiot.

Verkkojen funktioista / proseduureista esitellään aina ensiksi C-kieliset, sitten Pascal-kieliset versiot. Kaikkien funktioiden käytössä oletetaan että verkko G on määritelty. Mikäli parametrina annettava verkko G on määrittelemätön, on aliohjelmien toiminta määrittelemätöntä, lukuunottamatta tietenkin GRAPH_CREATE:a joka määrittelee verkon.

Verkon luontiin tarvittavat operaatiot:

Verkon solmujen ja kaarten värittämiseen tarvittavat operaatiot:

Verkon läpikäynteihin tarvittavat operaatiot:

Funktioiden esittelyt : Verkon luontiin tarvittavat operaatiot

GRAPH_CREATE (G)

void GRAPH_CREATE ( GRAPH G );

procedure GRAPH_CREATE ( G : GRAPH );

Luo uuden verkon G, ja asettaa sen tyhjäksi verkoksi. Jos verkko G ei ole tyhjä verkko, kaikki verkossa olleet solmut menetetään.

Aikavaativuus : O(1).

 

GRAPH_FREE(G)

void GRAPH_FREE ( GRAPH G );

procedure GRAPH_FREE ( G : GRAPH );

Tuhoaa kaikki solmut ja kaaret ja vapauttaa verkon varaaman tilan.

Aikavaativuus : O(|E+V|)  

 

GRAPH_INSERT_VERTEX(G, lbl, cst, col)

GRAPH_VERTEX GRAPH_INSERT_VERTEX ( GRAPH G, GRAPH_LABELTYPE lbl, GRAPH_COSTTYPE cst, GRAPH_COLORTYPE col );

function GRAPH_INSERT_VERTEX ( G : GRAPH; lbl : GRAPH_LABELTYPE; cst : GRAPH_COSTTYPE; col : GRAPH_COLORTYPE ) : GRAPH_VERTEX;

Vie verkkoon G uuden solmun jonka nimiöksi tulee lbl, väriksi col ja painoksi cst, ja palauttaa luodun solmun.

Aikavaativuus : O(1)

 

GRAPH_DELETE_VERTEX(G, V)

void GRAPH_DELETE_VERTEX ( GRAPH G, GRAPH_VERTEX V );

procedure GRAPH_DELETE_VERTEX ( G : GRAPH; V : GRAPH_VERTEX );

Poistaa verkosta G solmun V. Samalla poistetaan myös ne kaaret jotka johtavat solmuun tai lähtevät solmusta V.

Aikavaativuus : O(naapurien määrä)

 

GRAPH_INSERT_EDGE (G, V1, V2, lbl, cst, col)

GRAPH_EDGE GRAPH_INSERT_EDGE ( GRAPH G, GRAPH_VERTEX V1, GRAPH_VERTEX V2, GRAPH_LABELTYPE lbl, GRAPH_COSTTYPE cst, GRAPH_COLORTYPE col );

function GRAPH_INSERT_EDGE ( G : GRAPH; V1, V2 : GRAPH_VERTEX; lbl : GRAPH_LABELTYPE; cst : GRAPH_COSTTYPE; col : GRAPH_COLORTYPE ) : GRAPH_EDGE;

Vie verkkoon G uuden kaaren solmujen V1 ja V2 välille, ja palauttaa luodun kaaren. Nimiöksi tulee lbl, väriksi col ja painoksi cst.

Aikavaativuus : O(1)

 

GRAPH_DELETE_EDGE (G, E)

void GRAPH_DELETE_EDGE ( GRAPH G, GRAPH_EDGE E );

procedure GRAPH_DELETE_EDGE ( G : GRAPH; E : GRAPH_EDGE );

Poistaa verkosta G kaaren E.

Aikavaativuus : O(1)

 

GRAPH_RETRIEVE_EDGE(G, V1, V2)

GRAPH_EDGE GRAPH_RETRIEVE_EDGE ( GRAPH G, GRAPH_VERTEX V1, GRAPH_VERTEX V2 );

function GRAPH_RETRIEVE_EDGE ( G : GRAPH; V1, V2 : GRAPH_VERTEX ) : GRAPH_EDGE;

Palauttaa verkon DG solmujen V1 ja V2 välillä olevan kaaren jos sellainen on. Jos kaarta tai solmuja ei ole, palautetaan NIL/NULL.

Aikavaativuus : O(naapurien määrä)

 

GRAPH_HEAD (G, E)

GRAPH_VERTEX GRAPH_HEAD (GRAPH G, GRAPH_EDGE E)

function GRAPH_HEAD (G:GRAPH ; E : GRAPH_EDGE) : GRAPH_VERTEX;

Palauttaa kaaren E jommankumman pään solmun.

Aikavaativuus : O(1)

 

GRAPH_TAIL (G, E)

GRAPH_VERTEX GRAPH_TAIL (GRAPH G, GRAPH_EDGE E)

function GRAPH_TAIL (G:GRAPH ; E : GRAPH_EDGE) : GRAPH_VERTEX;

Palauttaa kaaren E toisen pään solmun (vrt yllä GRAPH_HEAD).

Aikavaativuus : O(1)

Funktioiden esittelyt : Verkon solmujen ja kaarten värittämiseen tarvittavat operaatiot

 

GRAPH_VERTEX_COLOR (G, V)

GRAPH_COLORTYPE GRAPH_VERTEX_COLOR ( GRAPH G, GRAPH_VERTEX V );

function GRAPH_VERTEX_COLOR ( G : GRAPH; V : GRAPH_VERTEX ) : GRAPH_COLORTYPE;

Palauttaa verkon G solmun V värin.

Aikavaativuus : O(1).

 

GRAPH_VERTEX_COST (G, V)

GRAPH_COSTTYPE GRAPH_VERTEX_COST ( GRAPH G, GRAPH_VERTEX V )

function GRAPH_VERTEX_COST (G:GRAPH;V:GRAPH_VERTEX ):GRAPH_COSTTYPE;

Palauttaa verkon G solmun V painon.

Aikavaativuus : O(1).

 

GRAPH_VERTEX_LABEL (G, V)

GRAPH_LABELTYPE GRAPH_VERTEX_LABEL ( GRAPH G, GRAPH_VERTEX V );

function GRAPH_VERTEX_LABEL ( G : GRAPH; V : GRAPH_VERTEX ) : GRAPH_LABELTYPE;

Palauttaa verkon G solmun V nimiön.

Aikavaativuus : O(1).

 

GRAPH_ASSIGN_VERTEX_COLOR (G, V, col)

void GRAPH_ASSIGN_VERTEX_COLOR ( GRAPH G, GRAPH_VERTEX V, GRAPH_COLORTYPE col );

procedure GRAPH_ASSIGN_VERTEX_COLOR ( G : GRAPH; V : GRAPH_VERTEX; col : GRAPH_COLORTYPE );

Asettaa verkon G solmun V väriksi col.

Aikavaativuus : O(1).

 

GRAPH_ASSIGN_VERTEX_COST (G, V, cst)

void GRAPH_ASSIGN_VERTEX_COST ( GRAPH G, GRAPH_VERTEX V, GRAPH_COSTTYPE cst );

procedure GRAPH_ASSIGN_VERTEX_COST ( G : GRAPH; V : GRAPH_VERTEX; cst : GRAPH_COSTTYPE );

Asettaa verkon G solmun V painoksi cst.

Aikavaativuus : O(1).

 

GRAPH_ASSIGN_VERTEX_LABEL (G, V, lbl)

void GRAPH_ASSIGN_VERTEX_LABEL ( GRAPH G, GRAPH_VERTEX V, GRAPH_LABELTYPE lbl );

procedure GRAPH_ASSIGN_VERTEX_LABEL ( G : GRAPH; V : GRAPH_VERTEX; lbl : GRAPH_LABELTYPE );

Asettaa verkon G solmun V nimiöksi lbl.

Aikavaativuus : O(1).

 

GRAPH_EDGE_COLOR (G, E)

GRAPH_COLORTYPE GRAPH_EDGE_COLOR ( GRAPH G, GRAPH_EDGE E );

function GRAPH_EDGE_COLOR ( G : GRAPH; E : GRAPH_EDGE ) : GRAPH_COLORTYPE;

Palauttaa verkon G kaaren E värin.

Aikavaativuus : O(1).

 

GRAPH_EDGE_COST (G, E)

GRAPH_COSTTYPE GRAPH_EDGE_COST ( GRAPH G, GRAPH_EDGE E )

function GRAPH_EDGE_COST ( G : GRAPH; V : GRAPH_EDGE ) : GRAPH_COSTTYPE;

Palauttaa verkon G kaaren E painon.

Aikavaativuus : O(1).

 

GRAPH_EDGE_LABEL (G, E)

GRAPH_LABELTYPE GRAPH_EDGE_LABEL ( GRAPH G, GRAPH_EDGE V );

function GRAPH_EDGE_LABEL ( G : GRAPH; V : GRAPH_EDGE ) : GRAPH_LABELTYPE;

Palauttaa verkon G kaaren E nimiön.

Aikavaativuus : O(1).

 

GRAPH_ASSIGN_EDGE_COLOR(G, E, col)

void GRAPH_ASSIGN_EDGE_COLOR ( GRAPH G, GRAPH_EDGE V, GRAPH_COLORTYPE col );

procedure GRAPH_ASSIGN_EDGE_COLOR ( G : GRAPH; V : GRAPH_EDGE; col : GRAPH_COLORTYPE );

Asettaa verkon G kaaren E väriksi col.

Aikavaativuus : O(1).

 

GRAPH_ASSIGN_EDGE_COST(G, E, cst)

void GRAPH_ASSIGN_EDGE_COST ( GRAPH G, GRAPH_EDGE V, GRAPH_COSTTYPE cst );

procedure GRAPH_ASSIGN_EDGE_COST ( G : GRAPH; V : GRAPH_EDGE; cst : GRAPH_COSTTYPE );

Asettaa verkon G kaaren E painoksi cst.

Aikavaativuus : O(1).

 

GRAPH_ASSIGN_EDGE_LABEL(G, E, lbl)

void GRAPH_ASSIGN_EDGE_LABEL ( GRAPH G, GRAPH_EDGE V, GRAPH_LABELTYPE lbl );

procedure GRAPH_ASSIGN_EDGE_LABEL ( G : GRAPH; V : GRAPH_EDGE; lbl : GRAPH_LABELTYPE );

Asettaa verkon G kaaren E nimiöksi lbl.

Aikavaativuus : O(1).

Funktioiden esittelyt : Verkon läpikäynteihin tarvittavat operaatiot

 

GRAPH_IS_ADJACENT (G, V1, V2)

int GRAPH_IS_ADJACENT ( GRAPH G, GRAPH_VERTEX V1, GRAPH_VERTEX V2 );

function GRAPH_IS_ADJACENT ( G : GRAPH; V1 ,V2 : GRAPH_VERTEX ) : boolean;

Palauttaa tiedon siitä löytyykö verkon G solmujen V1 ja V2 väliltä kaari. Mikäli solmusta välillä on kaari, palautetaan TRUE (!=0), muutoin FALSE (0).

Aikavaativuus : O(naapurien määrä)

 

GRAPH_VERTEX_ANY (G, i)

GRAPH_VERTEX GRAPH_VERTEX_ANY ( GRAPH G, GRAPH_VERTEX_ITERATOR  i );

function GRAPH_VERTEX_ANY ( G : GRAPH; var i : GRAPH_VERTEX_ITERATOR ) : GRAPH_VERTEX;

Aloittaa verkon G läpikäynnin i ("iterator"), ja palauttaa verkosta jonkin solmun. Jos verkossa ei ole solmuja, palauttaa NIL.

Aikavaativuus : O(1)

 

GRAPH_VERTEX_ANOTHER (G, i)

GRAPH_VERTEX GRAPH_VERTEX_ANOTHER ( GRAPH G, GRAPH_VERTEX_ITERATOR  i );

function GRAPH_VERTEX_ANOTHER ( G : GRAPH; var i : GRAPH_VERTEX_ITERATOR ) : GRAPH_VERTEX;

Palauttaa verkon G läpikäynnin i mukaan verkosta jonkin vielä käsittelemättömän solmun (määrittelemätön mikäli kaikki solmut on jo käsitelty).

Aikavaativuus : O(1)

 

GRAPH_VERTEX_ITERATING (G, i)

int GRAPH_VERTEX_ITERATING ( GRAPH G, GRAPH_VERTEX_ITERATOR i );

function GRAPH_VERTEX_ITERATING ( G : GRAPH; i : GRAPH_VERTEX_ITERATOR) : boolean;

Palauttaa tiedon siitä, onko verkon G läpikäynti i vielä kesken. Jos läpikäynti on vielä kesken, palautetaan TRUE(!=0), muuten FALSE(0).

Aikavaativuus : O(1)

 

GRAPH_EDGE_ANY (G, i)

GRAPH_EDGE GRAPH_EDGE_ANY ( GRAPH G, GRAPH_EDGE_ITERATOR  i );

function GRAPH_EDGE_ANY ( G : GRAPH; var i : GRAPH_EDGE_ITERATOR ) : GRAPH_EDGE;

Aloittaa verkon G läpikäynnin i ("iterator"), ja palauttaa verkosta jonkin kaaren. Jos verkossa ei ole kaaria, palauttaa NIL.

Aikavaativuus : O(1)

 

GRAPH_EDGE_ANOTHER (G,  i)

GRAPH_EDGE GRAPH_EDGE_ANOTHER ( GRAPH G, GRAPH_EDGE_ITERATOR  i );

function GRAPH_EDGE_ANOTHER ( G : GRAPH; var i : GRAPH_EDGE_ITERATOR ) : GRAPH_EDGE;

Palauttaa verkon G läpikäynnin i mukaan verkosta jonkin vielä käsittelemättömän kaaren (määrittelemätön mikäli kaikki kaaret on jo käsitelty).

Aikavaativuus : O(1)

 

GRAPH_EDGE_ITERATING (G, i)

int GRAPH_EDGE_ITERATING ( GRAPH G, GRAPH_EDGE_ITERATOR i );

function GRAPH_EDGE_ITERATING ( G : GRAPH; i : GRAPH_EDGE_ITERATOR ) : boolean;

Palauttaa tiedon siitä, onko verkon G läpikäynti i vielä kesken. Jos läpikäynti on vielä kesken, palautetaan TRUE(!=0), muuten FALSE(0).

Aikavaativuus : O(1)

 

GRAPH_VERTEX_ANY_ADJ (G, V, i)

GRAPH_VERTEX GRAPH_VERTEX_ANY_ADJ ( GRAPH G, GRAPH_VERTEX V , GRAPH_VERTEX_ITERATOR i );

function GRAPH_VERTEX_ANY_ADJ ( G : GRAPH; V : GRAPH_VERTEX; var i : GRAPH_VERTEX_ITERATOR ) : GRAPH_VERTEX;

Aloittaa verkon G läpikäynnin i ("iterator"), ja palauttaa jonkin solmun V naapurisolmuista. Jos sellaisia ei ole, palauttaa NIL.

Aikavaativuus : O(1)

 

GRAPH_VERTEX_ANOTHER_ADJ (G, V, i)

GRAPH_VERTEX GRAPH_VERTEX_ANOTHER_ADJ (GRAPH G, GRAPH_VERTEX V, GRAPH_VERTEX_ITERATOR i );

function GRAPH_VERTEX_ANOTHER_ADJ ( G : GRAPH; V : GRAPH_VERTEX; var i : GRAPH_VERTEX_ITERATOR ) : GRAPH_VERTEX;

Palauttaa verkon G läpikäynnin i mukaan verkosta jonkin solmun V vielä käsittelemättömän naapurisolmun (määrittelemätön mikäli kaikki naapurit on jo käsitelty).

Aikavaativuus : O(1)

 

GRAPH_VERTEX_ITERATING_ADJ (G, V, i)

int GRAPH_VERTEX_ITERATING_ADJ ( GRAPH G, GRAPH_VERTEX V, GRAPH_VERTEX_ITERATOR  i );

function GRAPH_VERTEX_ITERATING_ADJ ( G : GRAPH; V : GRAPH_VERTEX; i : GRAPH_VERTEX_ITERATOR ) : boolean;

Palauttaa tiedon siitä, onko verkon G solmun V viereisten solmujen läpikäynti i vielä kesken. Jos läpikäynti on vielä kesken, palautetaan TRUE(!=0), muuten FALSE(0).

Aikavaativuus : O(1)

 

GRAPH_EDGE_ANY_ADJ (G, E, i)

GRAPH_EDGE GRAPH_EDGE_ANY_ADJ ( GRAPH G, GRAPH_EDGE E, GRAPH_EDGE_ITERATOR  i );

function GRAPH_EDGE_ANY_ADJ ( G : GRAPH; E : GRAPH_EDGE; var i : GRAPH_EDGE_ITERATOR ) : GRAPH_EDGE;

Aloittaa verkon G läpikäynnin i ("iterator"), ja palauttaa jonkin kaaren E naapurikaarista, eli kaarista jotka lähtevät samasta solmusta. Jos sellaisia ei ole, palauttaa NIL.

Aikavaativuus : O(1)

 

GRAPH_EDGE_ANOTHER_ADJ (G, E, i)

GRAPH_EDGE GRAPH_EDGE_ANOTHER_ADJ ( GRAPH G, GRAPH_EDGE E, GRAPH_EDGE_ITERATOR i );

function GRAPH_EDGE_ANOTHER_ADJ (G : GRAPH; E : GRAPH_EDGE; var i : GRAPH_EDGE_ITERATOR) : GRAPH_EDGE;

Palauttaa verkon G läpikäynnin i mukaan verkosta jonkin kaaren E vielä käsittelemättömän naapurikaaren (määrittelemätön mikäli kaikki naapurikaaret on jo käsitelty).

Aikavaativuus : O(1)

 

GRAPH_EDGE_ITERATING_ADJ (G, E, i)

int GRAPH_EDGE_ITERATING_ADJ (GRAPH G, GRAPH_EDGE E, GRAPH_EDGE_ITERATOR i );

function GRAPH_EDGE_ITERATING_ADJ ( G : GRAPH; E : GRAPH_EDGE; i : GRAPH_EDGE_ITERATOR ) : boolean;

Palauttaa tiedon siitä, onko verkon G kaaren E viereisten kaarten läpikäynti i vielä kesken. Jos läpikäynti on vielä kesken, palautetaan TRUE(!=0), muuten FALSE(0).

Aikavaativuus : O(1)