Suunnattu verkko on abstrakti tietotyyppi, joka koostuu solmujen joukosta ja suunnattujen kaarien joukosta. Ideana on, että solmut voidaan yhdistää toisiinsa suunnatuilla kaarilla siten, että yhdestä solmusta lähtee kaari, jota seuraamalla päästään toiseen solmuun. Samaa kaarta pitkin ei voida tulla takaisin, se on vain yksisuuntainen väylä. Kaari voi toki johtaa myös suoraan takaisin solmuun itseensä. Solmua, johon päästään kaarta pitkin, sanotaan alkuperäisen solmun naapuriksi.
Jotta suunnattu verkko olisi kiinnostava, on siihen voitava laittaa tietoa. Tätä varten on sekä solmut että kaaret tehty sellaisiksi, että niille voidaan asettaa arvoja, symboleja, värejä jne. Kun verkosta poistetaan jokin solmu, poistuu samalla myös kaikki siitä lähtevät sekä kaikki siihen johtavat kaaret. Verkkoa käsitellään yleisen verkon avulla tietämättä verkon solmujen tarkkaa tyyppiä.
Suunnattu verkko = DG (digraph, direct graph)
solmu = V (vertex, node)
kaari = E (edge)
värittäminen = COLOR
naapuri = ADJACENT
paino = COST
Luo uuden verkon DG, ja asettaa sen tyhjäksi verkoksi.
Aikavaativuus: O(1)
void DIGRAPH_CREATE (DIGRAPH DG);
Vie verkkoon DG uuden solmun jonka nimiöksi tulee lbl, väriksi col
ja painoksi cst, ja palauttaa luodun solmun.
Aikavaativuus: O(1)
DIGRAPH_VERTEX DIGRAPH_INSERT_VERTEX (DIGRAPH DG, DIGRAPH_LABELTYPE lbl,DIGRAPH_COSTTYPE cst, DIGRAPH_COLORTYPE col);
Vie verkkoon DG uuden kaaren solmujen from ja to välille, ja
palauttaa luodun kaaren. Nimiöksi tulee lbl, painoksi cst ja väriksi col.
Aikavaativuus: O(1)
DIGRAPH_EDGE DIGRAPH_INSERT_EDGE (DIGRAPH DG, DIGRAPH_VERTEX from, DIGRAPH_VERTEX to,DIGRAPH_LABELTYPE lbl, DIGRAPH_COSTTYPE cst,DIGRAPH_COLORTYPE col);
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|)
void DIGRAPH_DELETE_VERTEX (DIGRAPH DG, DIGRAPH_VERTEX V)
Poistaa verkosta DG kaaren E.
Aikavaativuus: O(|E|)
void DIGRAPH_DELETE_EDGE (DIGRAPH DG, DIGRAPH_EDGE E);
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 NULL.
Aikavaativuus: O(|E|)
DIGRAPH_EDGE DIGRAPH_RETRIEVE_EDGE (DIGRAPH DG, DIGRAPH_VERTEX V1, DIGRAPH_VERTEX V2);
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)
int DIGRAPH_IS_ADJACENT(DIGRAPH DG, DIGRAPH_VERTEX V1, DIGRAPH_VERTEX V2)
Tuhoaa kaikki solmut ja kaaret ja vapauttaa verkon varaaman tilan.
Aikavaativuus: O(|E+V|)
void DIGRAPH_FREE (DIGRAPH DG)
Alustaa verkon DG läpikäyntimuuttujan i (iterator), ja palauttaa
verkosta jonkin solmun. Jos verkossa ei ole solmuja, palauttaa NULL.
Aikavaativuus: O(1)
DIGRAPH_VERTEX DIGRAPH_VERTEX_ANY (DIGRAPH DG, DIGRAPH_VERTEX_ITERATOR i)
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 DIGRAPH_VERTEX_ANOTHER (DIGRAPH DG, DIGRAPH_VERTEX_ITERATOR i)
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)
int DIGRAPH_VERTEX_ITERATING (DIGRAPH DG, DIGRAPH_VERTEX_ITERATOR i)
Alustaa verkon DG läpikäyntimuuttujan i (iterator), ja palauttaa
verkosta jonkin kaaren. Jos verkossa ei ole kaaria, palauttaa NULL.
Aikavaativuus: O(|V|)
DIGRAPH_EDGE DIGRAPH_EDGE_ANY (DIGRAPH DG, DIGRAPH_EDGE_ITERATOR i)
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 DIGRAPH_EDGE_ANOTHER (DIGRAPH DG, DIGRAPH_EDGE_ITERATOR i)
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)
int DIGRAPH_EDGE_ITERATING (DIGRAPH DG, DIGRAPH_EDGE_ITERATOR i)
Alustaa verkon DG läpikäyntimuuttujan i (iterator), ja palauttaa jonkin
solmun V naapurisolmuista. Jos sellaisia ei ole, palauttaa NULL.
Aikavaativuus: O(1)
DIGRAPH_VERTEX DIGRAPH_VERTEX_ANY_ADJ (DIGRAPH DG, DIGRAPH_VERTEX V, DIGRAPH_VERTEX_ITERATOR i)
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 DIGRAPH_VERTEX_ANOTHER_ADJ (DIGRAPH DG, DIGRAPH_VERTEX V, DIGRAPH_VERTEX_ITERATOR i)
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)
int DIGRAPH_VERTEX_ITERATING_ADJ (DIGRAPH DG, DIGRAPH_VERTEX V, DIGRAPH_VERTEX_ITERATOR i)
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 NULL.
Aikavaativuus: O(1)
DIGRAPH_EDGE DIGRAPH_EDGE_ANY_ADJ (DIGRAPH DG, DIGRAPH_EDGE E, DIGRAPH_EDGE_ITERATOR i)
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 DIGRAPH_EDGE_ANOTHER_ADJ (DIGRAPH DG, DIGRAPH_EDGE E, DIGRAPH_EDGE_ITERATOR i)
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)
int DIGRAPH_EDGE_ITERATING_ADJ (DIGRAPH DG, DIGRAPH_EDGE E, DIGRAPH_EDGE_ITERATOR i)
Palauttaa verkon DG solmun V värin.
Aikavaativuus: O(1).
DIGRAPH_COLORTYPE DIGRAPH_VERTEX_COLOR (DIGRAPH DG, DIGRAPH_VERTEX V)
Palauttaa verkon DG solmun V painon.
Aikavaativuus: O(1).
DIGRAPH_COSTTYPE DIGRAPH_VERTEX_COST (DIGRAPH DG, DIGRAPH_VERTEX V)
Palauttaa verkon DG solmun V nimiön.
Aikavaativuus: O(1).
DIGRAPH_LABELTYPE DIGRAPH_VERTEX_LABEL (DIGRAPH DG, DIGRAPH_VERTEX V)
Palauttaa verkon DG kaaren E värin.
Aikavaativuus: O(1).
DIGRAPH_COLORTYPE DIGRAPH_EDGE_COLOR (DIGRAPH DG, DIGRAPH_EDGE E)
Palauttaa verkon DG kaaren E painon.
Aikavaativuus: O(1).
DIGRAPH_COSTTYPE DIGRAPH_EDGE_COST (DIGRAPH DG, DIGRAPH_EDGE E)
Palauttaa verkon DG kaaren E nimiön.
Aikavaativuus: O(1).
DIGRAPH_LABELTYPE DIGRAPH_EDGE_LABEL (DIGRAPH DG, DIGRAPH_EDGE E)
Asettaa verkon DG solmun V väriksi color.
Aikavaativuus: O(1).
void DIGRAPH_ASSIGN_VERTEX_COLOR(DIGRAPH DG, DIGRAPH_VERTEX V, DIGRAPH_COLORTYPE color)
Asettaa verkon DG solmun V painoksi cost.
Aikavaativuus: O(1).
void DIGRAPH_ASSIGN_VERTEX_COST (DIGRAPH DG, DIGRAPH_VERTEX V, DIGRAPH_COSTTYPE cost)
Asettaa verkon DG solmun V nimiöksi lbl.
Aikavaativuus: O(1).
void DIGRAPH_ASSIGN_VERTEX_LABEL (DIGRAPH DG, DIGRAPH_VERTEX V, DIGRAPH_LABELTYPE label)
Asettaa verkon DG kaaren E väriksi col.
Aikavaativuus: O(1).
void DIGRAPH_ASSIGN_EDGE_COLOR (DIGRAPH DG, DIGRAPH_EDGE E, DIGRAPH_COLORTYPE col)
Asettaa verkon DG kaaren E painoksi cst.
Aikavaativuus: O(1).
void DIGRAPH_ASSIGN_EDGE_COST (DIGRAPH DG, DIGRAPH_EDGE E, DIGRAPH_COSTTYPE cst)
Asettaa verkon DG kaaren E nimiöksi lbl.
Aikavaativuus: O(1).
void DIGRAPH_ASSIGN_EDGE_LABEL (DIGRAPH DG, DIGRAPH_EDGE E, DIGRAPH_LABELTYPE lbl)