Module Data.Graph

Module

Data.Graph

Copyright

(c) The University of Glasgow 2002

License

BSD-style (see the file libraries/base/LICENSE)

A version of the graph algorithms described in:

Lazy Depth-First Search and Linear Graph Algorithms in Haskell, by David King and John Launchbury.

Ported to Frege from the Haskell library source.

Imports

• import Data.List as List
• import frege.Prelude as Prelude
• import Prelude.PreludeArrays as PreludeArrays
• import Prelude.PreludeBase as PreludeBase
• import Prelude.PreludeDecimal as PreludeDecimal
• import Prelude.PreludeIO as PreludeIO
• import Prelude.PreludeList as PreludeList
• import Prelude.PreludeMonad as PreludeMonad
• import Prelude.PreludeText as PreludeText
• import Java.util.Regex as Regexp
• import Data.TreeMap as TM
• import Data.Tree as Tree

Table of Content

• Definitions

  data Edge

  data SCC vertex

  flattenSCCs ∷ [SCC a] → [a]

  flattenSCC ∷ SCC vertex → [vertex]

  edgeFromTuple ∷ (𝖆, 𝖇) → (𝖆, 𝖆, 𝖇)

  stronglyConnectedComponents ∷ Ord key ⇒ [(key, [key])] → [[key]]

  stronglyConnComp ∷ Ord key ⇒ [(node, key, [key])] → [SCC node]

  stronglyConnCompR ∷ Ord key ⇒ [(node, key, [key])] → [SCC (node, key, [key])]

  size ∷ (Int, Int) → Int

  bounds ∷ JArray a → (Int, Int)

  vertices ∷ JArray [Int] → [Int]

  edges ∷ JArray [Int] → [Edge]

  mapT ∷ (ArrayElement a, ArrayElement b) ⇒ (Int → a → b) → JArray a → JArray b

  mapTI ∷ ArrayElement a ⇒ (Int → a → Int) → JArray a → JArray Int

  buildG ∷ (Int, Int) → [Edge] → JArray [Int]

  transposeG ∷ JArray [Int] → JArray [Int]

  reverseE ∷ JArray [Int] → [Edge]

  outdegree ∷ JArray [Int] → JArray Int

  indegree ∷ JArray [Int] → JArray Int

  graphFromEdges' ∷ Ord key ⇒ [(node, key, [key])] → (JArray [Int], Int→(node, key, [key]))

  graphFromEdges ∷ Ord key ⇒ [(node, key, [key])] → (JArray [Int], Int→(node, key, [key]), key→Maybe Int)

  dff ∷ JArray [Int] → Forest Int

  dfs ∷ JArray [Int] → [Int] → Forest Int

  generate ∷ JArray [Int] → Int → Tree Int

  prune ∷ (Int, Int) → Forest Int → Forest Int

  chop ∷ Forest Int → ArrayOf s Bool → ST s (Forest Int)

  preorder ∷ Tree a → [a]

  preorderF ∷ Forest a → [a]

  tabulate ∷ (Int, Int) → [Int] → JArray Int

  preArr ∷ (Int, Int) → Forest Int → JArray Int

  postorder ∷ Tree a → [a]

  postorderF ∷ Forest a → [a]

  postOrd ∷ JArray [Int] → [Int]

  topSort ∷ JArray [Int] → [Int]

  components ∷ JArray [Int] → Forest Int

  undirected ∷ JArray [Int] → JArray [Int]

  scc ∷ JArray [Int] → Forest Int

  reachable ∷ JArray [Int] → Int → [Int]

  path ∷ JArray [Int] → Int → Int → Bool

  bcc ∷ JArray [Int] → Forest [Int]

  do_label ∷ JArray [Int] → JArray Int → Tree Int → Tree (Int, Int, Int)

  bicomps ∷ Tree (Int, Int, Int) → Forest [Int]

  collect ∷ Tree (Int, Int, Int) → (Int, Tree [Int])

• Re-Exported Items

  elemAt ∷ ArrayElement a ⇒ JArray a → Int → a 

• Functions and Values by Type

Definitions

data SCC vertex

Strongly connected component.

Constructors

AcyclicSCC vertex

A single vertex that is not in any cycle.

CyclicSCC [vertex]

A maximal set of mutually reachable vertices.

flattenSCCs ∷ [SCC a] → [a]

The vertices of a list of strongly connected components.

flattenSCC ∷ SCC vertex → [vertex]

The vertices of a strongly connected component.

edgeFromTuple ∷ (𝖆, 𝖇) → (𝖆, 𝖆, 𝖇)

Make a (key, [key]) list into one that is accepted by stronglyConnComp

stronglyConnectedComponents ∷ Ord key ⇒ [(key, [key])] → [[key]]

Convenience function to compute topologically sorted strongly connected components of an adjacency list of the form:

  [(key, [key])]

The result will be a list of lists of keys, where a singleton indicates no mutual dependency with other keys and a list consisting of several keys means that those are mutually dependent on each other.

In addition, earlier elements will not depend on later ones.

If the result contains only singletons, then the input was an acyclic graph.

stronglyConnComp ∷ Ord key ⇒ [(node, key, [key])] → [SCC node]

The strongly connected components of a directed graph, topologically sorted.

The graph is a list of nodes uniquely identified by keys, with a list of keys of nodes this node has edges to. The latter one may contain keys that don't correspond to nodes of the graph; such edges are ignored.

stronglyConnCompR ∷ Ord key ⇒ [(node, key, [key])] → [SCC (node, key, [key])]

The strongly connected components of a directed graph, topologically sorted. The function is the same as stronglyConnComp, except that all the information about each node retained.

This interface is used when you expect to apply SCC to (some of) the result of SCC, so you don't want to lose the dependency information.

data Edge

An edge from the first vertex to the second.

Constructors

Edge {from ∷ Int, to ∷ Int}

Member Functions

from ∷ Edge → Int

access field from

to ∷ Edge → Int

access field to

size ∷ (Int, Int) → Int

bounds ∷ JArray a → (Int, Int)

vertices ∷ JArray [Int] → [Int]

All vertices of a graph.

edges ∷ JArray [Int] → [Edge]

All edges of a graph.

mapT ∷ (ArrayElement a, ArrayElement b) ⇒ (Int → a → b) → JArray a → JArray b

mapTI ∷ ArrayElement a ⇒ (Int → a → Int) → JArray a → JArray Int

buildG ∷ (Int, Int) → [Edge] → JArray [Int]

Build a graph from a list of edges.

transposeG ∷ JArray [Int] → JArray [Int]

The graph obtained by reversing all edges.

reverseE ∷ JArray [Int] → [Edge]

outdegree ∷ JArray [Int] → JArray Int

A table of the count of edges from each node.

indegree ∷ JArray [Int] → JArray Int

A table of the count of edges into each node.

graphFromEdges' ∷ Ord key ⇒ [(node, key, [key])] → (JArray [Int], Int→(node, key, [key]))

Identical to graphFromEdges, except that the return value does not include the function which maps keys to vertices. This version of graphFromEdges is for backwards compatibility.

graphFromEdges ∷ Ord key ⇒ [(node, key, [key])] → (JArray [Int], Int→(node, key, [key]), key→Maybe Int)

Build a graph from a list of nodes uniquely identified by keys, with a list of keys of nodes this node should have edges to. The out-list may contain keys that don't correspond to nodes of the graph; they are ignored.

dff ∷ JArray [Int] → Forest Int

A spanning forest of the graph, obtained from a depth-first search of the graph starting from each vertex in an unspecified order.

dfs ∷ JArray [Int] → [Int] → Forest Int

A spanning forest of the part of the graph reachable from the listed vertices, obtained from a depth-first search of the graph starting at each of the listed vertices in order.

generate ∷ JArray [Int] → Int → Tree Int

prune ∷ (Int, Int) → Forest Int → Forest Int

chop ∷ Forest Int → ArrayOf s Bool → ST s (Forest Int)

preorder ∷ Tree a → [a]

preorderF ∷ Forest a → [a]

tabulate ∷ (Int, Int) → [Int] → JArray Int

preArr ∷ (Int, Int) → Forest Int → JArray Int

postorder ∷ Tree a → [a]

postorderF ∷ Forest a → [a]

postOrd ∷ JArray [Int] → [Int]

topSort ∷ JArray [Int] → [Int]

A topological sort of the graph.

The order is partially specified by the condition that a vertex i precedes j whenever j is reachable from i but not vice versa.

components ∷ JArray [Int] → Forest Int

The connected components of a graph.

Two vertices are connected if there is a path between them, traversing edges in either direction.

undirected ∷ JArray [Int] → JArray [Int]

scc ∷ JArray [Int] → Forest Int

The strongly connected components of a graph.

reachable ∷ JArray [Int] → Int → [Int]

A list of vertices reachable from a given vertex.

path ∷ JArray [Int] → Int → Int → Bool

Is the second vertex reachable from the first?

bcc ∷ JArray [Int] → Forest [Int]

The biconnected components of a graph.

An undirected graph is biconnected if the deletion of any vertex leaves it connected.

do_label ∷ JArray [Int] → JArray Int → Tree Int → Tree (Int, Int, Int)

bicomps ∷ Tree (Int, Int, Int) → Forest [Int]

collect ∷ Tree (Int, Int, Int) → (Int, Tree [Int])

Functions and Values by Type

(Int, Int) → Forest Int → JArray Int

preArr

(Int, Int) → Forest Int → Forest Int

prune

(Int, Int) → [Edge] → JArray [Int]

buildG

(Int, Int) → [Int] → JArray Int

tabulate

(Int, Int) → Int

size

Tree (Int, Int, Int) → (Int, Tree [Int])

collect

Tree (Int, Int, Int) → Forest [Int]

bicomps

JArray [Int] → JArray Int → Tree Int → Tree (Int, Int, Int)

do_label

JArray [Int] → [Int] → Forest Int

dfs

JArray [Int] → Int → Int → Bool

path

JArray [Int] → Int → Tree Int

generate

JArray [Int] → Int → [Int]

reachable

JArray [Int] → JArray [Int]

transposeG, undirected

JArray [Int] → JArray Int

indegree, outdegree

JArray [Int] → Forest [Int]

bcc

JArray [Int] → Forest Int

components, dff, scc

JArray [Int] → [Edge]

edges, reverseE

JArray [Int] → [Int]

postOrd, topSort, vertices

Edge → (Int→Int) → Edge

Edge.chg$from, Edge.chg$to

Edge → Int → Edge

Edge.upd$to, Edge.upd$from

Edge → Int

Edge.to, Edge.from

Int → Int → Edge

Edge.Edge

SCC vertex → [vertex]

flattenSCC

Tree a → [a]

postorder, preorder

JArray a → (Int, Int)

bounds

[SCC a] → [a]

flattenSCCs

Forest Int → ArrayOf s Bool → ST s (Forest Int)

chop

Forest a → [a]

postorderF, preorderF

[vertex] → SCC vertex

SCC.CyclicSCC

vertex → SCC vertex

SCC.AcyclicSCC

𝖆 → Bool

Edge.has$from, Edge.has$to

ArrayElement a ⇒ (Int → a → Int) → JArray a → JArray Int

mapTI

Ord key ⇒ [(key, [key])] → [[key]]

stronglyConnectedComponents

(𝖆, 𝖇) → (𝖆, 𝖆, 𝖇)

edgeFromTuple

(ArrayElement a, ArrayElement b) ⇒ (Int → a → b) → JArray a → JArray b

mapT

Ord key ⇒ [(node, key, [key])] → (JArray [Int], Int→(node, key, [key]), key→Maybe Int)

graphFromEdges

Ord key ⇒ [(node, key, [key])] → (JArray [Int], Int→(node, key, [key]))

graphFromEdges'

Ord key ⇒ [(node, key, [key])] → [SCC (node, key, [key])]

stronglyConnCompR

Ord key ⇒ [(node, key, [key])] → [SCC node]

stronglyConnComp