[Haskell] Niet bestaande paden *

[licensed]

Ik was voor de grap even wat met Haskell aan het spelen voor het vak Algoritmen & Datastructuren. Bij het hoofdstuk over grafen dacht ik even een stukje te schrijven dat kijkt of er een pad bestaat tussen twee vertices. Hiervoor heb ik het volgende bedacht:

Haskell:

type Graaf = (Vertices, Edges)
type Vertices = [Vertex]
type Vertex = Int
type Edges = [Edge]
type Edge = (Vertex, Vertex)

graaf1 :: Graaf
graaf1 = ([1,2,3,4,5],[(1,2),(2,4),(2,3),(3,1),(3,5),(5,4)])

graaf2 :: Graaf
graaf2 = ([1,2,3,4,5,6],[(1,2),(1,4),(2,3),(4,5),(5,6),(5,2),(6,5)])

isConnected :: Graaf -> Vertices -> Vertices -> Vertex -> Bool
-- g = de graaf
-- l = een lijst van reeds bezochte vertices
-- (a:k) = een lijst van te bekijken vertices
-- v = de vertex waar we naartoe willen
isConnected g l [] v = False
isConnected (vs, es) l (a:k) v
  | a == v = True
  | (visited l a) = False
  | otherwise = (isConnected (vs,es) (a:l) (adjecentVertices es a) v) || 
    (isConnected (vs,es) (a:l) k v)

adjecentVertices :: Edges -> Vertex -> Vertices
adjecentVertices [] v = []
adjecentVertices ((o,d):k) v
  | o == v = (d:(adjecentVertices k v))
  | otherwise = (adjecentVertices k v)

visited :: Vertices -> Vertex -> Bool
visited [] v = False
visited (a:k) v
  | a == v = True
  | otherwise = (visited k v)

Dit lijkt goed te werken, maar in graaf1 geeft

code:

isConnected graaf1 [] [1] 5

het antwoord False. Dit moet echter True zijn.

Ook in graaf2 gaat er iets niet goed. Volgens het programmaatje is er geen pad tussen 6 en 3, dit is er wel.

Kan iemand ontdekken welke denkfout ik maak?

[licensed]

*offtopic : bedankt voor het aanvullen van de titel, dat was ik vergeten

curry684 is heel knuffelbaar

[ Voor 32% gewijzigd door curry684 op 30-06-2003 15:11 ]

[joepP]

Zoals je adjecentVertices hebt geimplementeerd ga je uit van een gerichte graaf, en dan is er inderdaad geen verbinding tussen 1 en 5. Wat je wilt is een extra regeltje:

Haskell:

adjecentVertices :: Edges -> Vertex -> Vertices
adjecentVertices [] v = []
adjecentVertices ((o,d):k) v
  | o == v = (d:(adjecentVertices k v))
  | d == v = (o:(adjecentVertices k v))
  | otherwise = (adjecentVertices k v)

[licensed]

(1,2), (2,3), (3,5) lijkt mij een pad van 1 naar 5, toch?

Goed dat je nog even noemt dat het om een gerichte graaf gaat!

[joepP]

Oeps, poging 2 dan maar

Je maakt een fout in je isConnected functie... Als je een knoop reeds eerder bezocht heeft wil je niet stoppen, maar doorgaan zonder deze knoop in de lijst. Dan is dat vage gedoe met de || ook niet langer nodig:

Haskell:

isConnected :: Graaf -> Vertices -> Vertices -> Vertex -> Bool
-- g = de graaf
-- l = een lijst van reeds bezochte vertices
-- (a:k) = een lijst van te bekijken vertices
-- v = de vertex waar we naartoe willen
isConnected g l [] v = False
isConnected (vs, es) l (a:k) v
  | a == v = True
  | (visited l a) = isConnected (vs,es) (a:l) k v
  | otherwise = isConnected (vs,es) (a:l) ((adjecentVertices es a)++k) v

[licensed]

joepP dit geeft een oneindige loop tussen de vertices 1, 2 en 3.
Je moet eerder bezochte vertices zus niet nog eens bekijken...

[Soultaker]

licensed schreef op 30 June 2003 @ 17:03:
joepP dit geeft een oneindige loop tussen de vertices 1, 2 en 3.
Je moet eerder bezochte vertices zus niet nog eens bekijken...

Ik kwam onafhankelijk van joepP op hetzelfde idee, dus volgens mij heeft 'ie gewoon gelijk (of we hebben het allebei mis). Heb je het al geprobeerd?

Een oneindige lus wordt voorkomen omdat je in elke recursiestap ofwel een vertex toevoegd aan de lijst van bezochte vertices, ofwel de lijst van nog te bezoeken vertices korter maakt.

Overigens is het niet nodig de huidige vertex toe te voegen aan de lijst met bezochtte vertices als al vastgesteld was dat de huidige vertex al bezocht was. De code zou dus zoiets worden:

Haskell:

isConnected g l [] v = False
isConnected (vs, es) l (a:k) v
  | a == v = True
  | (visited l a) = isConnected (vs,es) l k v
  | otherwise = isConnected (vs,es) (a:l) ((adjacentVertices es a)++k) v

[ Voor 61% gewijzigd door Soultaker op 30-06-2003 17:38 ]

[licensed]

Ja, het idee kan ik volgen, maar het werkt niet (ik heb het geprobeerd in Hugs).

Mijn code geeft voor 1 naar 5 het verkeerde antwoord, jullie suggestie geeft helemaal geen antwoord (tenzij je stack overflow een antwoord vindt )

[Soultaker]

licensed schreef op 30 juni 2003 @ 17:45:
Ja, het idee kan ik volgen, maar het werkt niet (ik heb het geprobeerd in Hugs).

Mijn code geeft voor 1 naar 5 het verkeerde antwoord, jullie suggestie geeft helemaal geen antwoord (tenzij je stack overflow een antwoord vindt )

Wat staat er dan zoal op de stack? Waar treedt de oneindige recursie op? Of is je stack gewoon te klein? (Dan moet 'ie wel HEEL klein zijn, trouwens)

Volgens mij klopt het idee gewoon wel, dus moet het aan de implementatie liggen. Als je een vertex beschouwt met een aantal buren en één van die buren heb je al bezocht, dan moet je nog steeds de overige (misschien nog niet bezochte) buren nagaan om te zien of daar geen pad ligt.

De code is wat rommelig, dus misschien zit er een foutje in de implementatie dat ik over het hoofd zie. Ik zou ook wel een andere (nettere) implementatie kunnen geven, maar ja, dat is natuurlijk niet direct de bedoeling. Als het probleem vanavond nog niet opgelost is, zal ik er eens in meer detail naar kijken.

[licensed]

Soultaker schreef op 30 June 2003 @ 18:08:
Wat staat er dan zoal op de stack? Waar treedt de oneindige recursie op? Of is je stack gewoon te klein? (Dan moet 'ie wel HEEL klein zijn, trouwens)

Hugs komt niet tot een antwoord. Hij loopt een hele tijd en dan breek ik hem af omdat hij het goede antwoord binnen een seconde zou moeten geven.

Soultaker schreef op 30 June 2003 @ 18:08:
De code is wat rommelig, dus misschien zit er een foutje in de implementatie dat ik over het hoofd zie. Ik zou ook wel een andere (nettere) implementatie kunnen geven, maar ja, dat is natuurlijk niet direct de bedoeling. Als het probleem vanavond nog niet opgelost is, zal ik er eens in meer detail naar kijken.

Rommelig

Haskell:

  | (visited l a) = isConnected (vs,es) l k v

Waarom zou je een reeds bezochte vertex nog eens willen gaan bekijken? Op deze manier kom je dus in een loop, ondanks dat je die a in (a:k) niet meer bekijkt.

[joepP]

licensed schreef op 30 June 2003 @ 17:45:
Ja, het idee kan ik volgen, maar het werkt niet (ik heb het geprobeerd in Hugs).

Mijn code geeft voor 1 naar 5 het verkeerde antwoord, jullie suggestie geeft helemaal geen antwoord (tenzij je stack overflow een antwoord vindt )

Ik denk dat je beter moet copy/pasten, want het werkt hier perfect. Getest en al

[licensed]

Na, das raar... Hij doet het inderdaad wel. Vast ergens een foutje gemaakt

Heel erg bedankt!

[Soultaker]

Tja, probleem opgelost. Een beetje zorgvuldiger werken mag wel, natuurlijk, want dit is wel een beetje zonde van de tijd van mij en joepP!