Главная » Haskell » Модуль Graph

0

В модуле Graph определены функции для алгоритмов работы с графами, которые описаны в работе [11]. Использование модуля:

import  Data.Graph

Во внешнем интерфейсе этого модуля имеется несколько программных сущностей. Это алгебраический тип данных и пара функций для манипуляции им. Тип: SCC

Описание: представляет сильно связанные компоненты графа (SCC — от английского выражения strongly connected components). Каждый  граф является одним или несколькими значениями типа SCC.

Определение:

data  SCC  vertex

= AcyclicSCC  vertex

| CyclicSCC   [vertex]

Первый конструктор AcyclicSCC представляет собой отдельные вершины графа, которые не связаны ни в какой цикл. Соответственно, второй конструктор CyclicSCC представляет компонент графа, в котором выделено наибольшее количество связанных друг с другом вершин (непосредственно или косвенно). Функция: stronglyConnComp

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

Определение:

stronglyConnComp :: Ord key  => [(node, key,  [key])] ->  [SCC node] stronglyConnComp edges0 = map  get_node  (stronglyConnCompR edges0)

where

get_node  (AcyclicSCC  (n, _, _)) = AcyclicSCC  n

get_node  (CyclicSCC  triples)     = CyclicSCC [n | (n, _, _)  < triples]

Функция: stronglyConnCompR

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

Определение:

stronglyConnCompR :: Ord key  => [(node, key,  [key])] ->  [SCC (node,  key,  [key])] stronglyConnCompR []     = []

stronglyConnCompR edges0 = map  decode forest

where (graph, vertex_fn, _)  =  graphFromEdges  edges0 forest                              =  scc  graph

decode (Node v  []) | mentions_itself v  = CyclicSCC  [vertex_fn v]

| otherwise               = AcyclicSCC  (vertex_fn v) decode other = CyclicSCC (dec  other [])

where dec (Node v  ts) vs  = vertex_fn v  :  foldr dec vs  ts mentions_itself v  = v  ‘elem‘  (graph  ! v)

Функция: flattenSCC

Описание: возвращает список вершин из заданного сильно связанного компонента.

Определение:

flattenSCC :: SCC  vertex ->  [vertex]  flattenSCC  (AcyclicSCC  v) = [v] flattenSCC (CyclicSCC  vs)  =  vs

Функция: flattenSCCs

Описание: возвращает список вершин из заданных сильно связанных компонентов.

Определение:

flattenSCCs :: [SCC a] ->  [a]  flattenSCCs =  concatMap  flattenSCC

Собственно, для представления графов создано несколько синонимов типов, которые позволяют описывать графы с метками в вершинах в виде ограниченных целых чисел. Данные типы суть Graph, Table, Bounds, Edge и Vertex.

Тип: Vertex

Описание: абстрактное представление вершины графа.

Определение:

type  Vertex  = Int

Тип: Edge

Описание: Абстрактное представление ребра графа. Ребро считается направленным от первой вершины в паре ко второй.

Определение:

type  Edge = (Vertex, Vertex)

Тип: Bounds

Описание: граничные значения в типе Table.

Определение:

type  Bounds = (Vertex, Vertex)

Тип: Table

Описание: индексированная таблица вершин графа для  представления  одного элемента в матрице смежности.

Определение:

type  Table  a =  Array  Vertex  a

Тип: Graph

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

Определение:

type  Graph =  Table  [Vertex]

Уже  для работы с этими типами предназначены  следующие  утилитарные функции.

Функция: graphFromEdges

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

Определение:

graphFromEdges  :: Ord key  => [(node,  key,  [key])]  ->

(Graph,   Vertex  ->  (node,   key,  [key]), key  ->  Maybe Vertex) graphFromEdges  edges0 = (graph, \v ->  vertex_map  ! v,  key_vertex)

where

max_v                   = length edges0 1

bounds0                = (0, max_v) ::  (Vertex, Vertex) sorted_edges        =  sortBy lt edges0

edges1                  = zipWith (,) [0..] sorted_edges

graph                     = array bounds0 [(,) v  (mapMaybe  key_vertex ks)| (,)  v  (_, _, ks)  < edges1]

key_map               = array bounds0 [(,) v  k  | (,) v  (_, k, _ )  < edges1] vertex_map           = array bounds0 edges1

(_, k1,  _)  ‘lt‘ (_, k2,  _)  = k1  ‘compare‘ k2 key_vertex k       =  findVertex 0 max_v

where

findVertex a b | a > b = Nothing

findVertex a b = case compare k  (key_map ! mid)  of

where

LT ->  findVertex a  (mid  1) EQ  ->  Just  mid

GT  ->  findVertex (mid  + 1)  b

mid = (a  + b)  ‘div‘ 2

Функция: graphFromEdges’

Описание: вариант функции graphFromEdges, который не возвращает функцию поиска вершины по ключу.

Определение:

graphFromEdges’ :: Ord key  => [(node, key,  [key])] ->  (Graph,   Vertex  ->  (node,   key,  [key])) graphFromEdges’ x  = (a, b)

where

(a, b, _)  =  graphFromEdges  x

Функция: buildG

Описание: строит граф по списку рёбер.

Определение:

buildG  :: Bounds ->  [Edge]  ->  Graph

buildG  bounds0 edges0 = accumArray (flip (:)) [] bounds0 edges0

Функция: transposeG

Описание: возвращает граф, в котором все рёбра имеют противоположную направленность, чем в исходном графе.

Определение:

transposeG  :: Graph ->  Graph

transposeG  g = buildG  (bounds  g)  (reverseE g)

Функция: vertices

Описание: возвращает список вершин графа.

Определение:

vertices :: Graph ->  [Vertex] vertices =  indices

Функция: edges

Описание: возвращает список рёбер графа.

Определение:

edges ::  Graph ->  [Edge]

edges g = [(v, w) | v  < vertices g, w  < g ! v  ]

Функция: outdegree

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

Определение:

outdegree  :: Graph  ->  Table  Int outdegree  = mapT  numEdges

where

numEdges  _ ws = length ws

Функция: indegree

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

Определение:

indegree   :: Graph ->  Table  Int indegree   =  outdegree  .  transposeG

Функция: dfs

Описание: лес части графа, в которую можно попасть из заданного набора вершин. Поиск осуществляется по принципу «сначала в глубину» по всем вершинам списка, начиная с начала.

Определение:

dfs  :: Graph ->  [Vertex]  ->  Forest Vertex

dfs  g vs  = prune  (bounds  g)  (map  (generate g)  vs)

Функция: dff

Описание: недетерминированный лес части графа, в которую  можно попасть из заданного набора вершин. Поиск осуществляется по принципу «сначала в глубину» по всем вершинам списка в произвольном порядке.

Определение:

dff :: Graph ->  Forest Vertex  dff  g  = dfs  g  (vertices g)

Функция: topSort

Описание: возвращает топологически отсортированный граф.

Определение:

topSort :: Graph ->  [Vertex] topSort =  reverse . postOrd

Функция: components

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

Определение:

components :: Graph ->  Forest  Vertex  components =  dff . undirected

Функция: scc

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

scc  :: Graph ->  Forest  Vertex

scc  g = dfs  g (reverse  (postOrd  (transposeG  g)))

Функция: bcc

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

Определение:

bcc  :: Graph ->  Forest  [Vertex]

bcc  g = (concat . map  bicomps . map  (do_label g  dnum))  forest where

forest = dff g

dnum    = preArr (bounds  g)  forest

Функция: reachable

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

Определение:

reachable :: Graph ->  Vertex  ->  [Vertex] reachable g v  =  preorderF (dfs  g [v])

Функция: path

Описание: возвращает значение True, если до второй вершины существует путь из первой.

Определение:

path  :: Graph ->  Vertex  ->  Vertex  ->  Bool path  g v  w  = w  ‘elem‘  (reachable g v)

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

Источник: Душкин Р. В., Справочник по языку Haskell. М.: ДМК Пресс, 2008. 544 с., ил.

По теме:

  • Комментарии