Suuntaamaton verkko

Sisältö:

Määritelmä

Suuntaamaton verkko on melkein kuin suunnattu verkko. Se koostuu solmuista ja solmujen välisistä kaarista, mutta kaarilla ei ole suuntaa. Suunnatusta verkosta poiketen suuntaamattoman verkon kaari ei saa johtaa solmusta itseensä. Koska kaarella ei ole suuntaa, molempia kaareen liittyviä solmuja kutsutaan päätesolmuja ja ne myös ovat toistensa naapureita. Haluttu tieto on talletettu/talletetaan solmuihin. Solmut voidaan "värittää" eri väreillä ja niille voidaan antaa paino. Kaarille voidaan myös antaa nimi, väri ja paino.

Abstraktin tietotyypin "suuntaamaton verkko" nimi tietorakennekirjastossa on GRAPH.

Funktiot:

Uuden verkon luominen
GRAPH_CREATE (G)

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

void GRAPH_CREATE( GRAPH G );

Uuden solmun lisääminen:
GRAPH_INSERT_VERTEX(G, lbl, cst, col)

Vie verkkoon G Uuden solmun jonka nimiöksi tulee lbl, väriksi col ja painoksi cst, ja palauttaa luodun solmun.
Aikavaativuus: O(1) 

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

Uuden kaaren lisääminen:
GRAPH_INSERT_EDGE (G, V1, V2, lbl, cst, col)

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_EDGE GRAPH_INSERT_EDGE ( GRAPH G, GRAPH_VERTEX V1, GRAPH_VERTEX V2,
GRAPH_LABELTYPE lbl, GRAPH_COSTTYPE cst, GRAPH_COLORTYPE col );

Solmun poistaminen:
GRAPH_DELETE_VERTEX(G, V)

Poistaa verkosta G solmun V. Samalla poistetaan myös solmuun liittyvät kaaret V.
Aikavaativuus: O(|E+V|) 

void GRAPH_DELETE_VERTEX ( GRAPH G, GRAPH_VERTEX V );

Kaaren poistaminen:
GRAPH_DELETE_EDGE (G, E)

Poistaa verkosta G kaaren E, mutta ei kaareen liittyviä solmuja.
Aikavaativuus: O(|E|) 

void GRAPH_DELETE_EDGE ( GRAPH G, GRAPH_EDGE E );

Kaaren hakeminen:
GRAPH_RETRIEVE_EDGE(G, V1, V2)

Palauttaa verkon G solmujen V1 ja V2 välillä olevan kaaren jos sellainen on. Jos kaarta tai solmuja ei ole, palautetaan NULL.
Aikavaativuus: O(|E|) 

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

Verkon käyttämän tilan vapauttaminen:
GRAPH_FREE(G)

Tuhoaa kaikki solmut ja kaaret ja vapauttaa verkon varaaman tilan.
Aikavaativuus: O(|E+V|)

void GRAPH_FREE( GRAPH G );

Solmun sisältämän tiedon lukeminen:
GRAPH_VERTEX_COLOR (G, V)

Palauttaa verkon G solmun V värin.
Aikavaativuus: O(1). 

GRAPH_COLORTYPE GRAPH_VERTEX_COLOR ( GRAPH G, GRAPH_VERTEX V );

GRAPH_VERTEX_COST (G, V)

Palauttaa verkon G solmun V painon.
Aikavaativuus: O(1). 

GRAPH_COSTTYPE GRAPH_VERTEX_COST ( GRAPH G, GRAPH_VERTEX V )

GRAPH_VERTEX_LABEL (G, V)

Palauttaa verkon G solmun V nimiön.
Aikavaativuus: O(1). 

GRAPH_LABELTYPE GRAPH_VERTEX_LABEL ( GRAPH G, GRAPH_VERTEX V );

Kaaren sisältämän tiedon lukeminen:
GRAPH_EDGE_COLOR (G, E)

Palauttaa verkon G kaaren E värin.
Aikavaativuus: O(1). 

GRAPH_COLORTYPE GRAPH_EDGE_COLOR ( GRAPH G, GRAPH_EDGE E );

GRAPH_EDGE_COST (G, E)

Palauttaa verkon G kaaren E painon.
Aikavaativuus: O(1). 

GRAPH_COSTTYPE GRAPH_EDGE_COST ( GRAPH G, GRAPH_EDGE E )

GRAPH_EDGE_LABEL (G, E)

Palauttaa verkon G kaaren E nimiön.
Aikavaativuus: O(1).

Solmun sisältämän tiedon asettaminen:
GRAPH_ASSIGN_VERTEX_COLOR (G, V, col)

Asettaa verkon G solmun V väriksi col.
Aikavaativuus: O(1). 

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

GRAPH_ASSIGN_VERTEX_COST (G, V, cst)

Asettaa verkon G solmun V painoksi cst.
Aikavaativuus: O(1). 

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

GRAPH_ASSIGN_VERTEX_LABEL (G, V, lbl)

Asettaa verkon G solmun V nimiöksi lbl.
Aikavaativuus: O(1). 

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

Kaaren sisältämän tiedon asettaminen:
GRAPH_ASSIGN_EDGE_COLOR(G, E, col)

Asettaa verkon G kaaren E väriksi col.
Aikavaativuus: O(1).

GRAPH_ASSIGN_EDGE_COST(G, E, cst)

Asettaa verkon G kaaren E painoksi cst.
Aikavaativuus: O(1). 

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

GRAPH_ASSIGN_EDGE_LABEL(G, E, lbl)

Asettaa verkon G kaaren E nimiöksi lbl.
Aikavaativuus: O(1). 

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

Naapuruuden tutkiminen:
GRAPH_IS_ADJACENT (G, V1, V2)

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(1) 

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

Verkon solmujen läpikäynti:
GRAPH_VERTEX_ANY (G, i)

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

GRAPH_VERTEX GRAPH_VERTEX_ANY ( GRAPH G, GRAPH_VERTEX_ITERATOR  i );

GRAPH_VERTEX_ANOTHER (G, i)

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 GRAPH_VERTEX_ANOTHER ( GRAPH G, GRAPH_VERTEX_ITERATOR  i );

GRAPH_VERTEX_ITERATING (G, i)

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) 

int GRAPH_VERTEX_ITERATING ( GRAPH G, GRAPH_VERTEX_ITERATOR i );

Verkon kaarten läpikäynti:
GRAPH_EDGE_ANY (G, i)

Aloittaa verkon G läpikäynnin i ("iterator"), ja palauttaa verkosta jonkin kaaren. Jos verkossa ei ole kaaria, palauttaa NULL.
Aikavaativuus: O(|V|) 

GRAPH_EDGE GRAPH_EDGE_ANY ( GRAPH G, GRAPH_EDGE_ITERATOR  i );

GRAPH_EDGE_ANOTHER (G,i)

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(|V|)

GRAPH_EDGE_ITERATING (G, i)

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) 

int GRAPH_EDGE_ITERATING ( GRAPH G, GRAPH_EDGE_ITERATOR i );

Solmun naapurisolmujen läpikäynti:
GRAPH_VERTEX_ANY_ADJ (G, V, i)

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

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

GRAPH_VERTEX_ANOTHER_ADJ (G, V, i)

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 GRAPH_VERTEX_ANOTHER_ADJ (GRAPH G, GRAPH_VERTEX V, GRAPH_VERTEX_ITERATOR i);

GRAPH_VERTEX_ITERATING_ADJ (G, V, i)

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) 

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

Kaaren naapurikaarien läpikäynti:
GRAPH_EDGE_ANY_ADJ (G, E, i)

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 NULL.
Aikavaativuus: O(1) 

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

GRAPH_EDGE_ANOTHER_ADJ (G, E, i)

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 GRAPH_EDGE_ANOTHER_ADJ ( GRAPH G, GRAPH_EDGE E, GRAPH_EDGE_ITERATOR i );

GRAPH_EDGE_ITERATING_ADJ (G, E, i)

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) 

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