Suunnatun verkon funktioiden esittelyt

Suunnattu verkko DG (digraph, directed graph ) muodostuu solmujen (vertex, node) joukosta V ja suunnattujen kaarten (edge) joukosta E. Solmulla voi olla mielivaltainen määrä naapureita ja vastaavasti solmu voi olla mielivaltaisen monen solmun naapuri. Solmu voi olla itsensä naapuri, ja naapuruus voi olla jopa moninkertaista, toisin sanoen lähtösolmusta päätesolmuun voi johtaa useita kaaria. Solmujen ja kaarten joukot ovat aina äärellisiä, joten verkkokin on äärellinen. Sekä verkon solmu että verkon kaari voidaan varustaa nimiöllä. Verkon käsittelyssä tarvitaan myös solmujen ja kaarten painoja ja/tai värejä.

Kaksisuuntainen verkko on verkko jonka alkioilla voi olla yhteys monen  suhteessa moneen. Vietäessä solmuja tai kaaria verkkoon määritellään samalla niihin ominaisuuksia, kuten paino,väri jne. Kun verkosta poistetaan solmu, poistuvat samalla myös kaikki solmuun tulevat ja solmusta lähtevät kaaret. Verkkoa käsitellään yleisen verkon avulla tietämättä verkon solmujen tarkkaa tyyppiä

Tässä osassa on esitelty kaksisuuntaisen verkon funktiot. Funktioista / proseduureista esitellään aina ensiksi C-kieliset, sitten Pascal-kieliset versiot. Kaikkien funktioiden käytössä oletetaan että verkko on määritelty. Mikäli parametrina annettava jono DG on määrittelemätön, on aliohjelmien toiminta määrittelemätöntä, lukuunottamatta tietenkin DIGRAPH_CREATE:a joka määrittelee jonon.

 

Funktioiden esittelyt

 

DIGRAPH_CREATE (DG)

void DIGRAPH_CREATE (DIGRAPH DG);

procedure DIGRAPH_CREATE (DG:DIGRAPH);

Luo uuden verkon DG, ja asettaa sen tyhjäksi verkoksi.

Aikavaativuus : O(1)

 

DIGRAPH_INSERT_VERTEX (DG,lbl,cst,col)

DIGRAPH_VERTEX DIGRAPH_INSERT_VERTEX (DIGRAPH DG, DIGRAPH_LABELTYPE lbl,DIGRAPH_COSTTYPE cst, DIGRAPH_COLORTYPE col);

function DIGRAPH_INSERT_VERTEX (DG:DIGRAPH;lbl:DIGRAPH_LABELTYPE;cst:DIGRAPH_COSTTYPE;col:DIGRAPH_COLORTYPE):DIGRAPH_VERTEX;

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

Aikavaativuus : O(1)

 

DIGRAPH_INSERT_EDGE(DG,from,to,lbl,cst,col)

DIGRAPH_EDGE DIGRAPH_INSERT_EDGE (DIGRAPH DG, DIGRAPH_VERTEX from, DIGRAPH_VERTEX to,DIGRAPH_LABELTYPE lbl, DIGRAPH_COSTTYPE cst,DIGRAPH_COLORTYPE col);

function DIGRAPH_INSERT_EDGE (DG:DIGRAPH;from,to:DIGRAPH_VERTEX;lbl:DIGRAPH_LABELTYPE;cst:DIGRAPH_COSTTYPE;col:DIGRAPH_COLORTYPE):DIGRAPH_EDGE;

Vie verkkoon DG uuden kaaren solmujen from ja to välille, ja palauttaa luodun kaaren. Nimiöksi tulee lbl, väriksi col ja painoksi cst.

Aikavaativuus : O(1)

 

DIGRAPH_DELETE_EDGE (DG,E)

void DIGRAPH_DELETE_EDGE (DIGRAPH DG, DIGRAPH_EDGE E);

procedure DIGRAPH_DELETE_EDGE (DG:DIGRAPH;E:DIGRAPH_EDGE);

Poistaa verkosta DG kaaren E.

Aikavaativuus : O(|E|)

 

DIGRAPH_RETRIEVE_EDGE (DG,V1,V2,)

DIGRAPH_EDGE DIGRAPH_RETRIEVE_EDGE (DIGRAPH DG, DIGRAPH_VERTEX V1, DIGRAPH_VERTEX V2);

function DIGRAPH_RETRIEVE_EDGE (DG:DIGRAPH;V1:DIGRAPH_VERTEX;V2:DIGRAPH_VERTEX):DIGRAPH_EDGE;

Palauttaa verkon DG solmujen V1 ja V2 välillä olevan kaaren jos sellainen on. Kaaren pitää lähteä solmusta V1 ja päättyä V2:een. Jos kaarta tai solmuja ei ole, palautetaan NIL/NULL.

Aikavaativuus : O(|E|)

 

DIGRAPH_IS_ADJACENT (DG,V1,V2)

int DIGRAPH_IS_ADJACENT(DIGRAPH DG, DIGRAPH_VERTEX V1, DIGRAPH_VERTEX V2)

function DIGRAPH_IS_ADJACENT(DG:DIGRAPH;V1,V2:DIGRAPH_VERTEX):boolean;

Palauttaa tiedon siitä löytyykö verkon DG solmusta V1 kaari solmuun V2. Mikäli solmusta V1 johtaa kaari solmuun V2, palautetaan TRUE (!=0), muutoin FALSE (0).

Aikavaativuus : O(1)

 

DIGRAPH_DELETE_VERTEX (DG,V)

void DIGRAPH_DELETE_VERTEX (DIGRAPH DG, DIGRAPH_VERTEX V)

procedure DIGRAPH_DELETE_VERTEX(DG:DIGRAPH;V:DIGRAPH_VERTEX);

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

Aikavaativuus : O(|E|+|V|)

 

DIGRAPH_FREE (DG)

void DIGRAPH_FREE (DIGRAPH DG)

procedure DIGRAPH_FREE (DG:DIGRAPH);

Tuhoaa kaikki solmut ja kaaret ja vapauttaa verkon varaaman tilan.

Aikavaativuus : O(|E+V|)

 

DIGRAPH_HEAD (DG, E)

DIGRAPH_VERTEX DIGRAPH_HEAD (DIGRAPH DG, DIGRAPH_EDGE E)

function DIGRAPH_HEAD (DG:DIGRAPH ; E : DIGRAPH_EDGE) : DIGRAPH_VERTEX;

Palauttaa kaaren E maalisolmun.

Aikavaativuus : O(1)

 

DIGRAPH_TAIL (DG, E)

DIGRAPH_VERTEX DIGRAPH_TAIL (DIGRAPH DG, DIGRAPH_EDGE E)

function DIGRAPH_TAIL (DG:DIGRAPH ; E : DIGRAPH_EDGE) : DIGRAPH_VERTEX;

Palauttaa kaaren E lähtösolmun.

Aikavaativuus : O(1)

 

DIGRAPH_VERTEX_ANY (DG,i)

DIGRAPH_VERTEX DIGRAPH_VERTEX_ANY (DIGRAPH DG, DIGRAPH_VERTEX_ITERATOR i )

function DIGRAPH_VERTEX_ANY (DG:DIGRAPH; var i:DIGRAPH_VERTEX_ITERATOR): DIGRAPH_VERTEX);

Alustaa verkon DG läpikäyntimuuttujan i (iterator), ja palauttaa verkosta jonkin solmun. Jos verkossa ei ole solmuja, palauttaa NIL.

Aikavaativuus : O(1)

 

DIGRAPH_VERTEX_ANOTHER (DG,i)

DIGRAPH_VERTEX DIGRAPH_VERTEX_ANOTHER (DIGRAPH DG, DIGRAPH_VERTEX_ITERATOR  i )

function DIGRAPH_VERTEX_ANOTHER (DG:DIGRAPH;var i : DIGRAPH_VERTEX_ITERATOR) : DIGRAPH_VERTEX;

Palauttaa verkon DG 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)

 

DIGRAPH_VERTEX_ITERATING(DG,i)

int DIGRAPH_VERTEX_ITERATING (DIGRAPH DG, DIGRAPH_VERTEX_ITERATOR i)

function DIGRAPH_VERTEX_ITERATING(DG:DIGRAPH;i:DIGRAPH_VERTEX_ITERATOR):boolean;

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

Aikavaativuus : O(1)

 

DIGRAPH_EDGE_ANY (DG,i)

DIGRAPH_EDGE DIGRAPH_EDGE_ANY (DIGRAPH DG, DIGRAPH_EDGE_ITERATOR  i )

function DIGRAPH_EDGE_ANY (DG:DIGRAPH;var i: DIGRAPH_EDGE_ITERATOR):DIGRAPH_EDGE;

Alustaa verkon DG läpikäyntimuuttujan i (iterator), ja palauttaa verkosta jonkin kaaren. Jos verkossa ei ole kaaria, palauttaa NIL.

Aikavaativuus : O(|V|)

 

DIGRAPH_EDGE_ANOTHER (DG,i)

DIGRAPH_EDGE DIGRAPH_EDGE_ANOTHER (DIGRAPH DG, DIGRAPH_EDGE_ITERATOR  i )

function DIGRAPH_EDGE_ANOTHER (DG:DIGRAPH;var i : DIGRAPH_EDGE_ITERATOR) : DIGRAPH_EDGE;

Palauttaa verkon DG 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(|V|)

 

DIGRAPH_EDGE_ITERATING (DG,i)

int DIGRAPH_EDGE_ITERATING (DIGRAPH DG, DIGRAPH_EDGE_ITERATOR i)

function DIGRAPH_EDGE_ITERATING (DG:DIGRAPH;i: DIGRAPH_EDGE_ITERATOR):boolean;

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

Aikavaativuus : O(1)

 

DIGRAPH_VERTEX_ANY_ADJ(DG,V,i)

DIGRAPH_VERTEX DIGRAPH_VERTEX_ANY_ADJ (DIGRAPH DG, DIGRAPH_VERTEX V,DIGRAPH_VERTEX_ITERATOR  i );

function DIGRAPH_VERTEX_ANY_ADJ(DG:DIGRAPH;V:DIGRAPH_VERTEX;var i : DIGRAPH_VERTEX_ITERATOR) : DIGRAPH_VERTEX;

Alustaa verkon DG läpikäyntimuuttujan i (iterator), ja palauttaa jonkin solmun V naapurisolmuista. Jos sellaisia ei ole, palauttaa NIL.

Aikavaativuus : O(1)

 

DIGRAPH_VERTEX_ANOTHER_ADJ(DG,V,i)

DIGRAPH_VERTEX DIGRAPH_VERTEX_ANOTHER_ADJ (DIGRAPH DG, DIGRAPH_VERTEX V,DIGRAPH_VERTEX_ITERATOR  i )

function DIGRAPH_VERTEX_ANOTHER_ADJ(DG:DIGRAPH;V:DIGRAPH_VERTEX; var i : DIGRAPH_VERTEX_ITERATOR) : DIGRAPH_VERTEX;

Palauttaa verkon DG 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)

 

DIGRAPH_VERTEX_ITERATING_ADJ(DG,V,i)

int DIGRAPH_VERTEX_ITERATING_ADJ (DIGRAPH DG, DIGRAPH_VERTEX V,DIGRAPH_VERTEX_ITERATOR i)

function DIGRAPH_VERTEX_ITERATING_ADJ (DG:DIGRAPH; V:DIGRAPH_VERTEX;i:DIGRAPH_VERTEX_ITERATOR):boolean;

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

Aikavaativuus : O(1)

 

DIGRAPH_EDGE_ANY_ADJ(DG,E,i)

DIGRAPH_EDGE DIGRAPH_EDGE_ANY_ADJ (DIGRAPH DG, DIGRAPH_EDGE E,DIGRAPH_EDGE_ITERATOR   i )

function DIGRAPH_EDGE_ANY_ADJ(DG:DIGRAPH;E:DIGRAPH_EDGE; var i:DIGRAPH_EDGE_ITERATOR) :DIGRAPH_EDGE;

Alustaa verkon DG läpikäyntimuuttujan 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)

 

DIGRAPH_EDGE_ANOTHER_ADJ (DG,E,i)

DIGRAPH_EDGE DIGRAPH_EDGE_ANOTHER_ADJ (DIGRAPH DG, DIGRAPH_EDGE E,DIGRAPH_EDGE_ITERATOR   i )

function DIGRAPH_EDGE_ANOTHER_ADJ (DG:DIGRAPH;E:DIGRAPH_EDGE;var i : DIGRAPH_EDGE_ITERATOR) : DIGRAPH_EDGE;

Palauttaa verkon DG 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)

 

DIGRAPH_EDGE_ITERATING_ADJ (DG,E,i)

int DIGRAPH_EDGE_ITERATING_ADJ (DIGRAPH DG, DIGRAPH_EDGE E,DIGRAPH_EDGE_ITERATOR   i )

function DIGRAPH_EDGE_ITERATING_ADJ (DG:DIGRAPH;E:DIGRAPH_EDGE;i:DIGRAPH_EDGE_ITERATOR):integer;

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

Aikavaativuus : O(1)

 

DIGRAPH_VERTEX_COLOR (DG,V)

DIGRAPH_COLORTYPE DIGRAPH_VERTEX_COLOR (DIGRAPH DG, DIGRAPH_VERTEX V)

function DIGRAPH_VERTEX_COLOR (DG:DIGRAPH;V:DIGRAPH_VERTEX):DIGRAPH_COLORTYPE;

Palauttaa verkon DG solmun V värin.

Aikavaativuus on O(1).

 

DIGRAPH_VERTEX_COST (DG,V)

DIGRAPH_COSTTYPE DIGRAPH_VERTEX_COST (DIGRAPH DG, DIGRAPH_VERTEX V)

function DIGRAPH_VERTEX_COST (DG:DIGRAPH;V:DIGRAPH_VERTEX):DIGRAPH_COSTTYPE;

Palauttaa verkon DG solmun V painon.

Aikavaativuus on O(1).

 

DIGRAPH_VERTEX_LABEL (DG,V)

DIGRAPH_LABELTYPE DIGRAPH_VERTEX_LABEL (DIGRAPH DG, DIGRAPH_VERTEX V)

function DIGRAPH_VERTEX_LABEL (DG:DIGRAPH;V:DIGRAPH_VERTEX):DIGRAPH_LABELTYPE;

Palauttaa verkon DG solmun V nimiön.

Aikavaativuus on O(1).

 

DIGRAPH_EDGE_COLOR (DG,E)

DIGRAPH_COLORTYPE DIGRAPH_EDGE_COLOR (DIGRAPH DG, DIGRAPH_EDGE E)

function DIGRAPH_EDGE_COLOR (DG:DIGRAPH;E:DIGRAPH_EDGE):DIGRAPH_COLORTYPE;

Palauttaa verkon DG kaaren E värin.

Aikavaativuus on O(1).

 

DIGRAPH_EDGE_COST (DG,E)

DIGRAPH_COSTTYPE DIGRAPH_EDGE_COST (DIGRAPH DG, DIGRAPH_EDGE E)

function DIGRAPH_EDGE_COST (DG:DIGRAPH;E:DIGRAPH_EDGE):DIGRAPH_COSTTYPE;

Palauttaa verkon DG kaaren E painon.

Aikavaativuus on O(1).

 

DIGRAPH_EDGE_LABEL (DG,E)

DIGRAPH_LABELTYPE DIGRAPH_EDGE_LABEL (DIGRAPH DG, DIGRAPH_EDGE E)

function DIGRAPH_EDGE_LABEL (DG:DIGRAPH;E:DIGRAPH_EDGE):DIGRAPH_LABELTYPE;

Palauttaa verkon DG kaaren E nimiön.

Aikavaativuus on O(1).

 

DIGRAPH_ASSIGN_VERTEX_COLOR(DG,V,color)

void DIGRAPH_ASSIGN_VERTEX_COLOR(DIGRAPH DG, DIGRAPH_VERTEX V,DIGRAPH_COLORTYPE color)

procedure DIGRAPH_ASSIGN_VERTEX_COLOR(var DG:DIGRAPH;var V:DIGRAPH_VERTEX;color:DIGRAPH_COLORTYPE);

Asettaa verkon DG solmun V väriksi color.

Aikavaativuus on O(1).

 

DIGRAPH_ASSIGN_VERTEX_COST (DG,V,cost)

void DIGRAPH_ASSIGN_VERTEX_COST (DIGRAPH DG, DIGRAPH_VERTEX V,DIGRAPH_COSTTYPE cost)

procedure DIGRAPH_ASSIGN_VERTEX_COST (DG:DIGRAPH;V:DIGRAPH_VERTEX;cost:DIGRAPH_COSTTYPE);

Asettaa verkon DG solmun V painoksi cost.

Aikavaativuus on O(1).

 

DIGRAPH_ASSIGN_VERTEX_LABEL (DG,V,lbl)

void DIGRAPH_ASSIGN_VERTEX_LABEL (DIGRAPH DG, DIGRAPH_VERTEX V,DIGRAPH_LABELTYPE label)

procedure DIGRAPH_ASSIGN_VERTEX_LABEL(DG:DIGRAPH;V:DIGRAPH_VERTEX;lbl:DIGRAPH_LABELTYPE);

Asettaa verkon DG solmun V nimiöksi lbl.

Aikavaativuus on O(1).

 

DIGRAPH_ASSIGN_EDGE_COLOR (DG,E,col)

void DIGRAPH_ASSIGN_EDGE_COLOR (DIGRAPH DG, DIGRAPH_EDGE E, DIGRAPH_COLORTYPE col)

procedure DIGRAPH_ASSIGN_EDGE_COLOR (DG:DIGRAPH;E:DIGRAPH_EDGE;col:DIGRAPH_COLORTYPE);

Asettaa verkon DG kaaren E väriksi col.

Aikavaativuus on O(1).

 

DIGRAPH_ASSIGN_EDGE_COST (DG,E,cst)

void DIGRAPH_ASSIGN_EDGE_COST (DIGRAPH DG, DIGRAPH_EDGE E, DIGRAPH_COSTTYPE cst)

procedure DIGRAPH_ASSIGN_EDGE_COST (DG:DIGRAPH;E:DIGRAPH_EDGE;cst:DIGRAPH_COSTTYPE);

Asettaa verkon DG kaaren E painoksi cst.

Aikavaativuus on O(1).

 

DIGRAPH_ASSIGN_EDGE_LABEL (DG,E,lbl)

void DIGRAPH_ASSIGN_EDGE_LABEL (DIGRAPH DG, DIGRAPH_EDGE E, DIGRAPH_LABELTYPE lbl)

procedure DIGRAPH_ASSIGN_EDGE_LABEL (DG:DIGRAPH;E:DIGRAPH_EDGE;lbl:DIGRAPH_LABELTYPE);

Asettaa verkon DG kaaren E nimiöksi lbl.

Aikavaativuus on O(1).