Algebra.Graph.IntAdjacencyMap.Internal

This module exposes the implementation of adjacency maps. The API is unstable and unsafe. Where possible use non-internal module Algebra.Graph.IntAdjacencyMap instead.

Adjacency map implementation

newtype IntAdjacencyMap

The IntAdjacencyMap 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     :: IntAdjacencyMap Int) == "empty"
show (1         :: IntAdjacencyMap Int) == "vertex 1"
show (1 + 2     :: IntAdjacencyMap Int) == "vertices [1,2]"
show (1 * 2     :: IntAdjacencyMap Int) == "edge 1 2"
show (1 * 2 * 3 :: IntAdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]"
show (1 * 2 + 3 :: IntAdjacencyMap Int) == "graph [1,2,3] [(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

IntAdjacencyMap

Fields

• adjacencyMap :: IntMap IntSet

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

Instances

Eq IntAdjacencyMap

Methods

(==) :: IntAdjacencyMap -> IntAdjacencyMap -> Bool

(/=) :: IntAdjacencyMap -> IntAdjacencyMap -> Bool

Num IntAdjacencyMap

Methods

(+) :: IntAdjacencyMap -> IntAdjacencyMap -> IntAdjacencyMap

(-) :: IntAdjacencyMap -> IntAdjacencyMap -> IntAdjacencyMap

(*) :: IntAdjacencyMap -> IntAdjacencyMap -> IntAdjacencyMap

negate :: IntAdjacencyMap -> IntAdjacencyMap

abs :: IntAdjacencyMap -> IntAdjacencyMap

signum :: IntAdjacencyMap -> IntAdjacencyMap

fromInteger :: Integer -> IntAdjacencyMap

Show IntAdjacencyMap

Methods

showsPrec :: Int -> IntAdjacencyMap -> ShowS

show :: IntAdjacencyMap -> String

showList :: [IntAdjacencyMap] -> ShowS

Graph IntAdjacencyMap

Associated Types

type Vertex IntAdjacencyMap :: *

Methods

empty :: IntAdjacencyMap

vertex :: Vertex IntAdjacencyMap -> IntAdjacencyMap

overlay :: IntAdjacencyMap -> IntAdjacencyMap -> IntAdjacencyMap

connect :: IntAdjacencyMap -> IntAdjacencyMap -> IntAdjacencyMap

type Vertex IntAdjacencyMap

type Vertex IntAdjacencyMap = Int

consistent :: IntAdjacencyMap -> 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