Keskustelu: Yleinen keskustelu: Graafin luominen klikkailemalla

Graafilla tarkoitan tätä:
http://en.wikipedia.org/wiki/Graph_(data_structure)

Teen peliä, jossa pitäisi saada klikkailtua tieverkosto kartan päälle, jota sitten hyödynnetään reitinhaussa.

Käytän tuota wikipedia-artikkelin kuvaa esimerkkinä ongelman havainnollistamisessa: jos käyttäjä klikkailee kohdat 1-6, miten voin ohjelmallisesti päätellä, ettei esim. solmujen 2-4 ja 3-5 välillä ei kulje tietä?

Koska nyt tarkoitat suoraa yhteyttä eri solmujen välillä, niin katsot tietysti vaikka solmusta 2, että onko sillä linkkiä solmuun 4 ja sama myös solmuparin (3, 5) kanssa. Jos linkki / yhteys on, niin silloinhan - duh - tie on olemassa ja muutoin ei.

Voisin kaivaa jostain kovalevyn kätköistä PL/I:llä kirjoitetun esimerkin, mikä laskee lyhimmän reitin solmujen välillä verkossa. Olisiko tuosta apua?

Eihän graafia voi luoda pelkästään solmujen perusteella, vaan lisäksi tarvitaan siihen kaaret. Et voi mitenkään ”päätellä, ettei esim. solmujen 2–4 ja 3–5 välillä ei kulje tietä”, koska ihan yhtä hyvin siinä myös voisi kulkea tie, vai mitä? Piirrät vain kuvaan uuden viivan, ja edellinen päätelmäsi on heti pielessä.

Sinun pitää tietenkin ohjelmoida peliisi kaksi työkalua: yksi, jolla asetetaan lisää solmuja, ja toinen, jolla yhdistetään solmuja eli piirretään kaaria. Helpoimmassa toteutuksessa jokainen solmu sisältää yksinkertaisesti tiedon, mihin solmuihin siitä menee tie.

C++-kielellä koko tieto voi näyttää esimerkiksi tältä:

struct Solmu {
	std::unordered_set<std::weak_ptr<Solmu>> naapurit;
};
std::vector<std::shared_ptr<Solmu>> solmut;

Sitähän minäkin, että väkisinhän tämä vaatii enemmän työtä kuin pelkkien solmujen klikkailemisen... Näillä tiedoilla on hyvä jatkaa, kiitoksia.