T-79.161 Kombinatoriset algoritmit / Kotitehtävä 3

Kolmannen kotitehtävän tehtävänanto osoittautui laajemmaksi kuin tarkoitettiin. Tehtävän helpottamiseksi tarjoamme seuraavassa kaksi C-kielistä aliohjelmaa, joilla multigraafeja voidaan käsitellä. Aliohjelmien bugittomuutta emme valitettavasti voi taata.

Tiedostossa kotit3.c on kaksi aliohjelmaa multigraafien käsittelyyn:

void canon(int vertices, char *s, char *canon);
void parent(int vertices, char *s, char *parent);

canon laskee multigraafin kanonisen muodon. Syötemultigraafi määritellään antamalla parametrissä vertices sen solmujen määrä ja parametrissä s merkkijono, joka määrittää itse multigraafin. Solmut ajatellaan numeroiduiksi 0...vertices-1 ja merkkijono

s=b_2,1 b_3,1 b_3,2 b_4,1 b_4,2 b_4,3 b_5,1 ... b_vertices-1,vertices-2

parent saa syötteensä samassa muodossa kuin canon. Se poistaa saamastaan syötteestä yhden sellaisen solmun, että yhtenäisten komponenttien määrä ei lisäänny; erityisesti jos syötemultigraafi on yhtenäinen, tulos on myös yhtenäinen. Aliohjelma kirjoittaa tuloksen merkkijonoon parent, jota varten käyttäjän tulee varata muistia. Huomattakoon, että parent ei millään lailla ota kantaa syötemultigraafin mahdolliseen kanonisuuteen.

Nämä aliohjelmat puolestaan käyttävät Brendan McKay:n nauty-aliohjelmakirjastoa. kotit3.c:n alussa rivi

#include "nauty22/nauty.h"

#define MAXN 60

kotit3.c sisältää myös minimaalisen pääohjelman, joka kutsuu kerran kumpaakin aliohjelmaa. Pikaisella kokeilulla vaikuttaisi siltä, että käännökseen ainakin Linux-alustalla riittäisi seuraavanlainen rivi:

cc -o kotit3 kotit3.c nauty22/nauty.c nauty22/nautil.c nauty22/naugraph.c

Pahoittelemme tämän ilmoituksen myöhäistä ajankohtaa. Tilanteen johdosta siirrämme viimeisen palautuspäivän torstaiksi 24.4.2003, ja pyrimme palauttamaan mahdolliset bumerangit perjantaina 25.4.2003. Koska tentti on kuitenkin jo 5.5. ja kotitehtävien tulee olla hyväksyttynä ennen tenttiä, suosittelemme lämpimästi kotitehtävän palauttamista niin pian kuin pääsiäisloma-aikatauluunne sopii. Pyrimme tarkastamaan palautetut kotitehtävät mahdollisimman pian palautuksen jälkeen.