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ä:
  1. Perusoperaatiot digraafien käsittelylle
  2. Tallennusformaatti ja -operaatiot
  3. Editori digraafitiedostojen muokkaukselle
  4. 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:

Algoritmit

Suoritetaan valikosta. 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.


Pääsivu Takaisin