Représentation graphique dans Haskell

Question

J'ai choisi de représenter un graphe dans Haskell par une liste de noeuds (par exemple n=[1,2,3,4]) et une liste de paires représentant les arêtes (exemple m=[(1,2), (2,3)]). Maintenant, je dois voir si le graphique est fortement connecté.

Mon problème principal est de savoir s'il y a un chemin entre 2 nœuds dans le graphique. J'ai écrit quelque chose comme ça:

-- sees if 2 nodes are adjacent 

adjacent x y [] = False 

adjacent x y (mu:m) = 
     if(x== (fst mu) && y==(snd mu)) then True 
     else adjacent x y m 

-- the successor of a node, ex for the edge (1,2) the succ of 1 is 2 
suc x [] = 0 
suc x (l:list) = 
     if(x==(fst l)) then snd l 
     else suc x list 

-- my main function 
way 0 y list = False 

way x y (mu:m) 
    | x==y = True 
    | (adjacent x y (mu:m)) == True = True 
    | otherwise = 
     if ((way (suc x (mu:m)) y (mu:m))==False) then way (suc x m) y m 
     else True 

Il fonctionne quand j'ai noeuds de degré 1, mais pour les noeuds avec un degré plus élevé, il ne fonctionne pas toujours. Pouvez-vous me donner une idée à ce sujet?

Answer 1

Vous avez deux erreurs de compréhension:

1. m, votre liste d'arêtes est statique tout au long de la recherche ensemble. Ne le mangez pas comme vous le répétez dans way.
2. Chaque sommet peut avoir plus d'un arête le quittant. Vous voulez savoir si any des voisins de x a way à y. Pour trouver les voisins, vous devez d'abord filter la liste des arêtes pour trouver uniquement les arêtes qui quittent x.

Vous devez également créer une liste de nœuds que vous avez déjà visités lors de votre quête pour trouver une connexion. Si vous vous retrouvez sur un noeud que vous avez déjà vu, ce chemin particulier a échoué.

Quelques conseils pour rendre votre code beaucoup plus court: pour adjacent, essayez elem. Pour succ, essayez Data.Maybe.fromMaybe et lookup.

Answer 2

Voici quelques questions à vous poser:

1. Si adjacent 3 2 [(1,2),(2,3)] être True?
2. Combien de successeurs à 1 sont là dans le graphique [(1,2),(2,3),(1,4),(3,4)]
3. Pourquoi, ou n'a pas, way besoin d'avoir à la fois un x==y cas et un cas adjacent x y ...?
4. Lors de l'étape de récurrence de way, le test == False vous indique-t-il vraiment quelque chose qui vous permet de vous recurder sur le graphique plus petit de m?

En général, vous n'avez pas écrit de signatures de type pour vos fonctions de niveau supérieur. Il est généralement très instructif de le faire, et communiquera votre conception plus clairement:

type Vertex = Int 
type Edge = (Vertex, Vertex) 
type Graph = [Edge] 

adjacent :: Vertex -> Vertex -> Graph -> Bool 
suc :: Vertex -> Graph -> Vertex 
way :: Vertex -> Vertex -> Graph -> Bool 

Pensez si ces types de sens, et si elles se décomposent votre problème que vous attendez, juste à penser à des graphiques en général.

Votre objectif est vraiment la fonction way, ou est-ce pour déterminer si le graphique est connecté? Vous pourriez supposer trop sur la façon dont vous pouvez déterminer si le graphique est connecté. Enfin, une petite partie sur la syntaxe Haskell: Comme la plupart des autres langages, l'application de la fonction se lie très étroitement, plus serré que les opérateurs == et &&.Contrairement à la plupart des autres langages, l'application de fonction n'utilise pas de parenthèse. Par conséquent, adjacent peut être recodé comme:

adjacent x y [] = False 
adjacent x y (mu:m) = 
    if x == fst mu && y == snd mu then True 
    else adjacent x y m 

ce qui pourrait être simplifié à:

adjacent x y [] = False 
adjacent x y (mu:m) = (x == fst mu && y == snd mu) || adjacent x y m