LUEMINUT.txt

Verkoista ja containereista, lyhyesti. 

Alkuun pääsee seuraavilla includeilla:

#include "lcelib/Containers.H"
#include "lcelib/Nets.H"
#include "lcelib/Randgens.H"

Hyvin yksinkertainen verkkoimplementaatio, jolla kelpaa aloittaa,
tuntee nimen SymmNet. Se on templaattiluokka, joka syö parametreinaan
särmiin varastoidun datatyypin sekä tarkan implementaation määrittäviä
templaattiluokkia. Seuraavat lienevät tässä vaiheessa käyttökelpoisia:

SymmNet<bool> net(size); // painottamaton
SymmNet<float> net(size); // painotettu
SymmNet<NDEdgeData> net(size); // jos jotakuta vielä kiinnostaa

Verkon koko pitää siis määrittää luotaessa. Muukin on toki
mahdollista: kertokaa sitten, kun tarvitsette tällaisia
ominaisuuksia. 

Jos solmuja halutaan arpoa satunnaisesti painottaen degreellä tai
strengthillä, kannattaa seuraavia käyttää:

SymmNet<*, ExplSumTreeTable>
SymmNet<*, ExplSumTreeTable, WeightSumTable> 

Ensimmäinen käyttää painona degreetä, jälkimmäinen strengthiä. Tämä on
vain arvaus siitä, mitä käyttäjä tahtoo: jos solmun paino varastoidaan
eksplisiittisesti (jälkimmäinen) kirjasto olettaa, että sitä halutaan
käyttää painona. Kaikki on kuitenkin kustomoitavissa: painot tuotetaan
viime kädessä käyttäjän määrittelemän policy-luokan perusteella. *
korvataan siis halutulla särmäluokalla.

Verkon solmuihin pääsee käsiksi []-operaattorilla, joka syö ihan
tavallisia etumerkittömiä kokonaislukuja. Siis tyyliin:

net[i]

Varsinainen iteraattori on
olemassa, mutta sille ei kiinteän kokoisilla verkoilla liene
tarvetta. Geneeriset algoritmit (dijkstraattorit tms.) käyttävät toki
iteraattoreita, koska haluavat olla riippumattomia verkon
implementaatiosta.

const-referenssin solmuihin saa käyttämällä ()-operaattoria. Tämä voi
olla ajoittain kätevää; kaiken pitäisi kuitenkin yleisesti toimia
tavanomaisillakin referensseillä. const-referenssi on periaattessa
suora referenssi solmun naapurustoa kuvaavaan tietorakenteeseen.

Särmän i->j saa ulos seuraavalla notaatiolla:

net[i][j]

Tälle voi sitten tehdä mitä lystää: =, +=, metodikutsut "->"-
operaattorin kautta tms. on implementoitu. Verkko pidetään
automaagisesti symmetrisenä ja aputietorakenteet valideina. Nollaksi
(tai yleisemmin, default-konstruoituun arvoon) menevät särmät
poistetaan verkosta automaagisesti. Kun sellaisia kysytään, saavat ne
arvon 0 (tai yleisemmin default). 

Const-referenssin särmään saa ulos joko tyyliin:

net(i)[j] 

tai

net(i,j) 

Sekin palauttaa default-arvon, jos särmää ei löydy verkosta. 

Särmäiteraattori toimii seuraavasti:

for (NetType::edge_iterator j=net[i].begin(); !j.finished(); ++j) {
   edge_destination=*j;
   edge_weight=j.value();
   j.value()+=1; // jne;
}

"value()" antaa siis ulos referenssin särmän painoon. *-operaattori
palauttaa ainoastaan const-referenssejä: särmän siirto täytyy siis
tehdä "manuaalisesti" kopioimalla särmä ja asettamalla vanha
0:ksi. Tämä lähinnä turvallisuus- ja
yhteensopivuussyistä. Iteraattoritkin pitävät verkon invarianteista
huolen automaagisesti. 

NetType korvataan yllä vaikkapa ilmauksella
SymmNet<bool> tms. Kannattanee sanoa koodin alussa esimerkiksi, jotta:

typedef SymmNet<bool> NetType;

niin ei tarvitse toistaa itseään, ja implementaatiota voi vaihtaa
helposti.

Solmu valitaan painotetun satunnaisesti komennolla

node=net.weighedRandSlot(randgen); 

Tästä tulee ulos siis numero: itse solmuun saa referenssin []- tai
()-operaattoreilla kuten edellä.

Sivuvaikutusten kanssa kannattaa olla tarkkana. Kun verkkoon lisätään
särmä, vaikuttaa se heti toisen päänsä solmuun, painorakenteisiin
jne. 

Containerit.

Eniten tarvitut container-luokat ovat seuraavat. Esitys on jälleen
yksinkertainen: luokista esitetään ainoastaan vakioversiot:

Set<KeyType>

operaatiot:

bool contains(key);
bool put(key) // true, jos oli ennestääm
bool remove(key) // true, jos oli ja voitiin poistaa
size_t size() // montako elementtiä 
SetType::iterator begin(), jolle * palauttaa avaimen, ++ ja finished()
                           kuten edellä, lisäksi remove() joka poistaa
			   elementin, johon osoitetaan

Map<KeyType, ValueType>

operaatiot:

contains, remove ja size kuten edellä

ValueType & operator[](KeyType key) 
eli siis map[key]=value jne. Standardikirjaston esimerkin mukaisesti
palauttaa default-konstruoidun arvon, jos avain ei ollut
läsnä. 

Iteraattorista saa vastaavan referenssin kutsulla i.value(), kuten
verkkojenkin tapuksessa. 

AutoMap<KeyType, ValueType>

Kuten Map, mutta nollaan menevät arvot poistetaan automaagisesti. 

Ranmarin saa käyttöön julistuksella:

RandNumGen<> rands(int seed (optional)); 

Select-operaatiot syövät suoraan generaattoreita: näin käyttäjän ei
tarvitse kiinnostua siitä, montako satunnaislukua tarvitaan ja missä
muodossa.

Luvun väliltä [0, x[ saa ulos kutsulla

ResultType rands.next(ResultType x); 

Palautusarvo on siis samaa tyyppiä kuin syöte. Tämä on yleensä aika
näppärää. (1.0 on muuten flotari, 1 int). 

Työn iloa!

Esimerkkejä (testaamattomia):

Solmun i klusterointikerroin:

size_t sum;
// naapurit:
for (NetType::const_edge_iterator j=net(i).begin();
     !j.finished();
     ++j) {
   // niiden naapurit. Huomaa, ettei särmää *j->i tarvitse suodattaa pois. 
   for (NetType::const_edge_iterator k=net(*j).begin();
     !k.finished();
     ++k) {
     if (net(*k)[i] != 0) sum++;    
}
result=((float) sum)/net(i).size() / ( net(i).size()-1 ); 

Huomaa: Kannattaa välttää toistuvia jakolaskuja, koska
niistä saattaa syntyä pyöristysvirhettä. Lasketaan mieluummin 
summan osamäärä kuin osamäärien summa. 


Jos kyseessä on painottamaton verkko, käy if-lauseen sijasta yksinkertaisesti 

sum+=net(*k,i); 		
                       
koska bool konvertoituu automaagisesti arvoihin 1 ja
0. Harjoitustyöksi jätettäköön, miksi tulosta ei jaeta/kerrota
kahdella. 

Solmun i naapureiden average-degree:

size_t sum
for (NetType::const_edge_iterator j=net(i).begin();
     !j.finished();
     ++j) {
   sum+=net(*j).size();
}
result=((float) sum)/net(i).size();