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.
|
Ja tässä on sitten se Javapohjainen editori:
|
Lyhyt käyttöohje
Ohjelman käynnistyessä muodostetaan satunnaisesti 8 esimerkkisolmua.
Napit:
[Uusi] : Luo uusia solmuja
[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.
![](/~magi/bottline.gif)