Графическое представление в Haskell

Question

Я решил представить граф в Haskell списком узлов (например, n=[1,2,3,4]) и списком пар, представляющих ребра (пример m=[(1,2), (2,3)]). Теперь я должен посмотреть, сильно ли связан граф.

Моя главная проблема заключается в том, как найти, существует ли путь между 2 узлами на графике. Я написал что-то вроде этого:

-- 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  

Это работает, когда у меня есть узлы степени 1, но для узлов с большей степенью это не всегда работает. Можете ли вы дать мне подсказку об этом?

Answer 1

Вот несколько вопросов, которые вы себе задаете:

1. Должно ли adjacent 3 2 [(1,2),(2,3)] быть True?
2. Сколько преемников 1 есть на графике [(1,2),(2,3),(1,4),(3,4)]
3. Почему way должен иметь или x==y, и adjacent x y ... кейс?
4. На шаге рекурсии way тест == False действительно говорит вам что-то, что позволяет вам выполнить рекурсию на меньшем графике m?

Как правило, вы не написали сигнатуры типов для функций верхнего уровня. Обычно это очень поучительно, и ваш проект будет более понятным:

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

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

Подумайте, имеют ли эти типы смысл, и если они разлагают вашу проблему так, как вы ожидаете, просто подумайте о графиках в целом.

Является ли ваша цель действительно функцией way или она определяет, подключен ли график? Возможно, вы слишком много предполагаете, каким образом вы можете определить, связан ли график.

Наконец, небольшая часть о синтаксисе Haskell: Как и большинство других языков, приложение функций связывается очень плотно, более жестко, чем операторы == и &&. В отличие от большинства других языков, приложение-функция не использует скобки. Следовательно, adjacent можно перекодировать как:

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

Что, в свою очередь, может быть упрощено до:

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

Answer 2

У вас есть две ошибки понимания:

1. m, ваш список ребер статичен на протяжении всего поиска. Не ешьте это, как вы повторяете в way.
2. Каждая вершина может иметь более одного ребра, выходящего из нее. Вы хотите знать, имеет ли any из соседей x значение way для y. Чтобы найти соседей, вы сначала должны filter список ребер, чтобы найти только ребра, оставляющие x.

Вам также необходимо составить список узлов, которые вы уже посетили в своем поиске, чтобы найти соединение. Если вы окажетесь на узле, который уже видели, этот конкретный путь не удался.

Некоторые подсказки, чтобы сделать ваш код намного короче: для adjacent, попробуйте elem. Для succ попробуйте Data.Maybe.fromMaybe и lookup.