Algebra.Graph.AdjacencyMap.Internal

This module exposes the implementation of adjacency maps. The API is unstable and unsafe, and is exposed only for documentation. You should use the non-internal module Algebra.Graph.AdjacencyMap instead.

Adjacency map implementation

data AdjacencyMap a

The AdjacencyMap data type represents a graph by a map of vertices to their adjacency sets. We define a Num instance as a convenient notation for working with graphs:

0           == vertex 0
1 + 2       == overlay (vertex 1) (vertex 2)
1 * 2       == connect (vertex 1) (vertex 2)
1 + 2 * 3   == overlay (vertex 1) (connect (vertex 2) (vertex 3))
1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))

The Show instance is defined using basic graph construction primitives:

show (empty     :: AdjacencyMap Int) == "empty"
show (1         :: AdjacencyMap Int) == "vertex 1"
show (1 + 2     :: AdjacencyMap Int) == "vertices [1,2]"
show (1 * 2     :: AdjacencyMap Int) == "edge 1 2"
show (1 * 2 * 3 :: AdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]"
show (1 * 2 + 3 :: AdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"

The Eq instance satisfies all axioms of algebraic graphs:

• overlay is commutative and associative:

        x + y == y + x
  x + (y + z) == (x + y) + z

• connect is associative and has empty as the identity:

    x * empty == x
    empty * x == x
  x * (y * z) == (x * y) * z

• connect distributes over overlay:

  x * (y + z) == x * y + x * z
  (x + y) * z == x * z + y * z

• connect can be decomposed:

  x * y * z == x * y + x * z + y * z

The following useful theorems can be proved from the above set of axioms.

• overlay has empty as the identity and is idempotent:

    x + empty == x
    empty + x == x
        x + x == x

• Absorption and saturation of connect:

  x * y + x + y == x * y
      x * x * x == x * x

When specifying the time and memory complexity of graph algorithms, n and m will denote the number of vertices and edges in the graph, respectively.

Constructors

AM

Fields

• adjacencyMap :: !(Map a (Set a))

  The adjacency map of the graph: each vertex is associated with a set of its direct successors.

• graphKL :: GraphKL a

  Cached King-Launchbury representation. Note: this field is for internal use only.

Instances

Eq a => Eq (AdjacencyMap a)

Methods

(==) :: AdjacencyMap a -> AdjacencyMap a -> Bool

(/=) :: AdjacencyMap a -> AdjacencyMap a -> Bool

(Ord a, Num a) => Num (AdjacencyMap a)

Methods

(+) :: AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a

(-) :: AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a

(*) :: AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a

negate :: AdjacencyMap a -> AdjacencyMap a

abs :: AdjacencyMap a -> AdjacencyMap a

signum :: AdjacencyMap a -> AdjacencyMap a

fromInteger :: Integer -> AdjacencyMap a

(Ord a, Show a) => Show (AdjacencyMap a)

Methods

showsPrec :: Int -> AdjacencyMap a -> ShowS

show :: AdjacencyMap a -> String

showList :: [AdjacencyMap a] -> ShowS

ToGraph (AdjacencyMap a)

Associated Types

type ToVertex (AdjacencyMap a) :: *

Methods

toGraph :: (Graph g, (* ~ Vertex g) (ToVertex (AdjacencyMap a))) => AdjacencyMap a -> g

foldg :: r -> (ToVertex (AdjacencyMap a) -> r) -> (r -> r -> r) -> (r -> r -> r) -> AdjacencyMap a -> r

Ord a => Graph (AdjacencyMap a)

Associated Types

type Vertex (AdjacencyMap a) :: *

Methods

empty :: AdjacencyMap a

vertex :: Vertex (AdjacencyMap a) -> AdjacencyMap a

overlay :: AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a

connect :: AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a

type ToVertex (AdjacencyMap a)

type ToVertex (AdjacencyMap a) = a

type Vertex (AdjacencyMap a)

type Vertex (AdjacencyMap a) = a

mkAM :: Ord a => Map a (Set a) -> AdjacencyMap a

Construct an AdjacencyMap from a map of successor sets and (lazily) compute the corresponding King-Launchbury representation. Note: this function is for internal use only.

consistent :: Ord a => AdjacencyMap a -> Bool

Check if the internal graph representation is consistent, i.e. that all edges refer to existing vertices. It should be impossible to create an inconsistent adjacency map, and we use this function in testing. Note: this function is for internal use only.

consistent empty                  == True
consistent (vertex x)             == True
consistent (overlay x y)          == True
consistent (connect x y)          == True
consistent (edge x y)             == True
consistent (edges xs)             == True
consistent (graph xs ys)          == True
consistent (fromAdjacencyList xs) == True

Interoperability with King-Launchbury graphs

data GraphKL a

GraphKL encapsulates King-Launchbury graphs, which are implemented in the Data.Graph module of the containers library. Note: this data structure is for internal use only.

If mkGraphKL (adjacencyMap g) == h then the following holds:

map (fromVertexKL h) (vertices $ toGraphKL h)                               == vertexList g
map (\(x, y) -> (fromVertexKL h x, fromVertexKL h y)) (edges $ toGraphKL h) == edgeList g

Constructors

GraphKL

Fields

• toGraphKL :: Graph

  Array-based graph representation (King and Launchbury, 1995).

• fromVertexKL :: Vertex -> a

  A mapping of Data.Graph.Vertex to vertices of type a.

• toVertexKL :: a -> Maybe Vertex

  A mapping from vertices of type a to Data.Graph.Vertex. Returns Nothing if the argument is not in the graph.

mkGraphKL :: Ord a => Map a (Set a) -> GraphKL a

Build GraphKL from a map of successor sets. Note: this function is for internal use only.