Data.Graph

Авторские права	(c) Университет Глазго 2002
Лицензия	BSD-стиль (см. файл libraries/base/LICENSE)
Поддержка	libraries@haskell.org
Стабильность	экспериментальная
Переносимость	переносимая
Безопасный Haskell	Надёжный
Язык	Haskell98

Внешний интерфейс

stronglyConnComp Источник

Сильно связанные компоненты ориентированного графа, отсортированные топологически.

stronglyConnCompR Источник

Сильно связанные компоненты ориентированного графа, отсортированные топологически. Функция идентична stronglyConnComp, за исключением того, что вся информация о каждом узле сохраняется. Этот интерфейс используется, когда ожидается применение SCC к (некоторым из) результата SCC, поэтому вы не хотите терять информацию о зависимостях.

data SCC vertex Источник

Компонента сильной связности.

flattenSCC :: SCC vertex -> [vertex] Источник

Узлы компоненты сильной связности.

flattenSCCs :: [SCC a] -> [a] Источник

Узлы списка компонент сильной связности.

Графы

type Graph = Table [Vertex] Источник

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

type Table a = Array Vertex a Источник

Таблица, индексированная непрерывным множеством вершин.

type Bounds = (Vertex, Vertex) Источник

Границы Table.

type Edge = (Vertex, Vertex) Источник

Ребро от первой вершины ко второй.

type Vertex = Int Источник

Абстрактное представление вершин.

Создание графов

graphFromEdges :: Ord key => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex) Источник

Построение графа из списка узлов, однозначно идентифицированных ключами, со списком ключей узлов, с которыми у этого узла должны быть рёбра. Список выходящих рёбер может содержать ключи, не соответствующие узлам графа; они игнорируются.

graphFromEdges' :: Ord key => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key])) Источник

Идентично graphFromEdges, за исключением того, что значение возврата не включает функцию, которая отображает ключи на вершины. Эта версия graphFromEdges предназначена для обратной совместимости.

buildG :: Bounds -> [Edge] -> Graph Источник

Построение графа из списка рёбер.

transposeG :: Graph -> Graph Источник

Граф, полученный путём инвертирования всех рёбер.

Свойства графов

vertices :: Graph -> [Vertex] Источник

Все вершины графа.

edges :: Graph -> [Edge] Источник

Все рёбра графа.

outdegree :: Graph -> Table Int Источник

Таблица количества рёбер, выходящих из каждого узла.

indegree :: Graph -> Table Int Источник

Таблица количества рёбер, входящих в каждый узел.

Алгоритмы

dfs :: Graph -> [Vertex] -> Forest Vertex Источник

Остовное дерево части графа, достижимой из перечисленных вершин, полученное путём поиска в глубину графа, начиная с каждой из указанных вершин в порядке.

dff :: Graph -> Forest Vertex Источник

Остовное дерево графа, полученное путём поиска в глубину графа, начиная с каждой вершины в произвольном порядке.

topSort :: Graph -> [Vertex] Источник

Топологическая сортировка графа. Порядок частично задаётся условием, что вершина i предшествует j, когда вершина j достижима из i, но не наоборот.

components :: Graph -> Forest Vertex Source

Связные компоненты графа. Две вершины соединены, если между ними существует путь, проходящий по рёбрам в любом направлении.

scc :: Graph -> Forest Vertex Source

Сильно связанные компоненты графа.

bcc :: Graph -> Forest [Vertex] Source

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

reachable :: Graph -> Vertex -> [Vertex] Source

Список вершин, достижимых из данной вершины.

path :: Graph -> Vertex -> Vertex -> Bool Source

Достижима ли вторая вершина из первой?

module Data.Tree