Suunnatun verkon funktioiden esittelyt

Suunnattu verkko DG (digraph) 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ä. Suuntaamaton verkko eroaa suunnatusta verkosta vain siinä, ettei verkon kaarilla ole suuntaa.

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, poistuu samalla 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);

Varaa muistia uudelle tunnussolmulle ja asettaa verkon 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 uuden solmun jonka nimiöksi tulee lbl, väriksi col ja painoksi cst. solmu tulee aina listan ensimmäiseksi.

Aikavaativuus : O(1)

 

DIGRAPH_INSERT_EDGE(DG,from,tu,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,tu:DIGRAPH_VERTEX;lbl:DIGRAPH_LABELTYPE;cst:DIGRAPH_COSTTYPE;col:DIGRAPH_COLORTYPE):DIGRAPH_EDGE;

Vie verkkoon uuden kaaren solmujen from ja to välille. Nimiöksi tulee lbl, väriksi col ja painoksi cst. Kaari tulee solmun kaarilistan ensimmäiseksi.

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 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.

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 boolean-tietoa siitä löytyykö solmusta V1 kaari V2:een.

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 E. Poistetaan myös ne kaaret jotka johtavat tähän tai lähtevät tästä.

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

 

DIGRAPH_FREE (DG)

void DIGRAPH_FREE (DIGRAPH* DG)

procedure DIGRAPH_FREE (DG:DIGRAPH);

Tuhoaa kaikki solmut ja kaaret ja hävittää verkon tunnussolmun.

Aikavaativuus : O(|E+V|)

 

DIGRAPH_VERTEX_ANY (DG,i)

DIGRAPH_VERTEX DIGRAPH_VERTEX_ANY (DIGRAPH DG, DIGRAPH_VERTEX_ITERATOR* i)

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

Alustaa läpikäyntimuuttujan i, ja palauttaa verkon ensimmäisen 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;i:DIGRAPH_VERTEX_ITERATOR):DIGRAPH_VERTEX;

Päivittää läpikäyntimuuttujaa i ja palauttaa verkon seuraavan solmun (tai NIL).

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;

Jos i osoittaa johonkin solmuun, läpikäynti on vielä kesken. Palautetaan silloin 1, muuten 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;i: DIGRAPH_EDGE_ITERATOR):DIGRAPH_EDGE;

Palauttaa ensimmäisen löydetyn kaaren koko verkosta (tai NIL jos kaaria ei ole).

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;i:DIGRAPH_EDGE_ITERATOR):DIGRAPH_EDGE;

Palauttaa järjestyksessä seuraavan löydetyn kaaren (tai NIL jos niitä ei enää ole).

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;

Jos i osoittaa johonkin solmuun, läpikäynti on vielä kesken. Palautetaan silloin true, muuten false.

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;i:DIGRAPH_VERTEX_ITERATOR):DIGRAPH_VERTEX;

Alustaa läpikäyntimuuttujan i, ja palauttaa V:n ensimmäisen naapurin jos sellainen on. i osoittaa aina kaareen, mutta palautetaan solmu.

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;i:DIGRAPH_VERTEX_ITERATOR):DIGRAPH_VERTEX;

Päivittää läpikäyntimuuttujaa i ja palauttaa solmun seuraavan naapurin (tai NIL). i osoittaa kaareen, mutta palautetaan solmu.

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;

Jos i osoittaa johonkin solmuun, läpikäynti on vielä kesken. Palautetaan silloin 1, muuten 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; i:DIGRAPH_EDGE_ITERATOR):DIGRAPH_EDGE;

Palauttaa kaaren E ensimmäisen naapurin, eli samasta solmusta lähtevän kaaren.

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;i:DIGRAPH_EDGE_ITERATOR):DIGRAPH_EDGE;

Palauttaa järjestyksessä seuraavan kaaren naapurin mikäli niitä on.

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;

Jos i osoittaa johonkin, läpikäynti on vielä kesken. Palautetaan silloin 1, muuten 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 solmun 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 solmun 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 solmun nimen.

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 kaaren 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 kaaren 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 kaaren nimen.

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);

Määrittelee solmun värin.

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);

Määrittelee solmun painon.

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);

Määrittelee solmun nimen.

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);

Määrittelee kaaren värin.

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);

Määrittelee kaaren painon.

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);

Määrittelee kaaren nimen.

Aikavaativuus on O(1).