Как пройти по графу в haskell?

Question

Предположим, у меня есть следующий график:

(graph, nodeFromVertex, vertexFromKey) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c']), ("c", 'c', []), ("d", 'd', ['b'])]

Это изображение:

Мне нужен способ выяснить вершины, у которых нет исходящих ребер.

В этом случае это всего лишь c

Я предполагаю, что способ найти это вручную рекурсивно, покаВы находите вершину, которая не имеет связей.Но я не уверен, как здесь повторить ...

Документы на графике Хаскелла на самом деле не говорят ...

Answer 1

Вы можете использовать outdegree, чтобы получить массив всех вершин с количеством исходящих ребер:

Prelude Data.Graph Data.Array> outdegree graph
array (0,3) [(0,1),(1,1),(2,0),(3,1)]

Значением каждого элемента в массиве является количество исходящих ребер.Если вы хотите отфильтровать массив, вы можете превратить его в список ассоциаций:

Prelude Data.Graph Data.Array> assocs $ outdegree graph
[(0,1),(1,1),(2,0),(3,1)]

, а затем отфильтровать его.Так как вас интересуют вершины, у которых нет исходящих ребер, вы можете отфильтровать те, где значение (второй элемент) в списке ассоциаций равно 0:

Prelude Data.Graph Data.Array> filter ((0 ==) . snd) $ assocs $ outdegree graph
[(2,0)]

Если вы хотите списокузлов, вы можете отобразить этот отфильтрованный список ассоциаций, используя nodeFromVertex:

Prelude Data.Graph Data.Array> l = filter ((0 ==) . snd) $ assocs $ outdegree graph
Prelude Data.Graph Data.Array> fmap (nodeFromVertex . fst) l
[("c",'c',"")]

Answer 2

Graph - это Array Vertex [Vertex].Вы можете индексировать его с помощью Vertex (0 на основе Int индекса) и получить список вершин-преемников.Вы можете получить список вершин без преемников, как этот (предположим, Data.Array импортировано):

vs = [v | (v, []) <- Data.Array.assocs graph]

Это понимание списка выбирает индексы элементов с пустым списком преемников.

Вершины могут быть сопоставлены с узлами с помощью функции nodeFromVertex.