http://www.utu.fi/~magi/opinnot/trak/

Tietorakenteet ja algoritmit harjoitustyö: Digraafit

Marko Grönroos

Haettu syksyllä 1989. Alkuperäinen tarkastaja Kimmo Kari. Palautettu korjattavaksi 1990. Siirretty toiselle kääntäjälle (Borland C++ » GCC) ja käyttöjärjestelmään (MSDOS » Linux) 1996. Samalla ohjelman dokumentointi ja käyttöympäristö muutettu HTML-pohjaiseksi. Digraph '97:ssä (versio 2.1) C++-grafiikkaluokat poistettu ja käyttöliittymä kokonaan Javalle.

Palautettu tarkistettavaksi: 8.9.1997

Kuvaus

Tehtävänä oli tehdä:

Perusoperaatiot digraafien käsittelylle
Tallennusformaatti ja -operaatiot
Editori digraafitiedostojen muokkaukselle
Algoritmit:
- Lyhimmän polun etsintä. Tämä on ratkaistu käyttämällä Floydin algoritmia pienellä lisäyksellä.
- Kauppamatkustajan ongelma. Tämä on ratkaistu käyttämällä yksinkertaista rekursiivista generointifunktiota jonka avulla lyhin reitti etsitään. Jokaisesta kaupungista on oletettu kulkevan suora reitti jokaiseen toiseen kaupunkiin.

	Graafiluokat (.h, .cc)
	Kauppamatkustajan ongelma
	Lyhimmän polun etsintä
	Pääohjelma, Makefile
	Common-luokat
	Editori (Java)
	Lähdekoodi
	Java Language Specification
	Kommentteja

Ja tässä on sitten se Javapohjainen editori:

Lyhyt käyttöohje

Ohjelman käynnistyessä muodostetaan satunnaisesti 8 esimerkkisolmua.

Napit:

[Uusi]

[Poista] : Poista solmuja klikkaamalla niitä

[Siirrä] : Siirrä solmuja painamalla niitä hiirellä ja vetämällä nappi painettuna

[Kytke] : Muodosta kytkentä solmusta toiseen painamalla hiirinappi alas solmun kohdalla ja vetämällä kytkentä toiseen solmuun

[Pura] : Pura olemassaoleva kytkentä samalla lailla kuin se tehtiinkin

[Merk. lähtö] : Merkitse lähtösolmu lyhimmän polun etsintää varten

[Merk. kohde] : Merkitse kohdesolmu lyhimmän polun etsintää varten

Algoritmit

Suoritetaan valikosta.

Kauppamatkustajan ongelma. Vaatii 1-10 solmua, joiden välille muodostaa lyhimmän reitin. Jos solmuja on enemmän, loput jätetään huomiotta. 10:llä solmulla voi kestää joitain minuutteja.
Lyhimmän polun etsintä. Vaatii lähtö- ja kohdesolmun merkinnän, sekä ainakin yhden polun josta saa kuljettua.

Algoritmit eivät anna virheilmoitusta epäonnistumisesta.

Tekstimuotoinen muokkaus

Tekstimuotoisen muokkauksen graafille saa valikosta. Varsinaisia tallennusoperaatioita tiedostoon ei ole, koska Java ei turvallisuussyistä tue sellaisia. Graafien "lukeminen" ja "tallentaminen" tapahtuu siten copy&paste-menetelmällä käyttämällä tekstieditointia.