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

newtype 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. Complexity: O(1) time and memory.

  adjacencyMap empty      == Map.empty
  adjacencyMap (vertex x) == Map.singleton x Set.empty
  adjacencyMap (edge 1 1) == Map.singleton 1 (Set.singleton 1)
  adjacencyMap (edge 1 2) == Map.fromList [(1,Set.singleton 2), (2,Set.empty)]
  

Instances

Eq a => Eq (AdjacencyMap a)

Defined in Algebra.Graph.AdjacencyMap.Internal

Methods

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

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

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

Defined in Algebra.Graph.AdjacencyMap.Internal

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)

Defined in Algebra.Graph.AdjacencyMap.Internal

Methods

showsPrec :: Int -> AdjacencyMap a -> ShowS

show :: AdjacencyMap a -> String

showList :: [AdjacencyMap a] -> ShowS

NFData a => NFData (AdjacencyMap a)

Defined in Algebra.Graph.AdjacencyMap.Internal

Methods

rnf :: AdjacencyMap a -> ()

Ord a => ToGraph (AdjacencyMap a)

Defined in Algebra.Graph.ToGraph

Associated Types

type ToVertex (AdjacencyMap a) :: *

Methods

toGraph :: AdjacencyMap a -> Graph (ToVertex (AdjacencyMap a))

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

isEmpty :: AdjacencyMap a -> Bool

size :: AdjacencyMap a -> Int

hasVertex :: ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool

hasEdge :: ToVertex (AdjacencyMap a) -> ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool

vertexCount :: AdjacencyMap a -> Int

edgeCount :: AdjacencyMap a -> Int

vertexList :: AdjacencyMap a -> [ToVertex (AdjacencyMap a)]

edgeList :: AdjacencyMap a -> [(ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))]

vertexSet :: AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))

vertexIntSet :: AdjacencyMap a -> IntSet

edgeSet :: AdjacencyMap a -> Set (ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))

preSet :: ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))

preIntSet :: Int -> AdjacencyMap a -> IntSet

postSet :: ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))

postIntSet :: Int -> AdjacencyMap a -> IntSet

adjacencyList :: AdjacencyMap a -> [(ToVertex (AdjacencyMap a), [ToVertex (AdjacencyMap a)])]

adjacencyMap :: AdjacencyMap a -> Map (ToVertex (AdjacencyMap a)) (Set (ToVertex (AdjacencyMap a)))

adjacencyIntMap :: AdjacencyMap a -> IntMap IntSet

adjacencyMapTranspose :: AdjacencyMap a -> Map (ToVertex (AdjacencyMap a)) (Set (ToVertex (AdjacencyMap a)))

adjacencyIntMapTranspose :: AdjacencyMap a -> IntMap IntSet

dfsForest :: AdjacencyMap a -> Forest (ToVertex (AdjacencyMap a))

dfsForestFrom :: [ToVertex (AdjacencyMap a)] -> AdjacencyMap a -> Forest (ToVertex (AdjacencyMap a))

dfs :: [ToVertex (AdjacencyMap a)] -> AdjacencyMap a -> [ToVertex (AdjacencyMap a)]

reachable :: ToVertex (AdjacencyMap a) -> AdjacencyMap a -> [ToVertex (AdjacencyMap a)]

topSort :: AdjacencyMap a -> Maybe [ToVertex (AdjacencyMap a)]

isAcyclic :: AdjacencyMap a -> Bool

toAdjacencyMap :: AdjacencyMap a -> AdjacencyMap (ToVertex (AdjacencyMap a))

toAdjacencyMapTranspose :: AdjacencyMap a -> AdjacencyMap (ToVertex (AdjacencyMap a))

toAdjacencyIntMap :: AdjacencyMap a -> AdjacencyIntMap

toAdjacencyIntMapTranspose :: AdjacencyMap a -> AdjacencyIntMap

isDfsForestOf :: Forest (ToVertex (AdjacencyMap a)) -> AdjacencyMap a -> Bool

isTopSortOf :: [ToVertex (AdjacencyMap a)] -> AdjacencyMap a -> Bool

Ord a => Graph (AdjacencyMap a)

Defined in Algebra.Graph.Class

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)

Defined in Algebra.Graph.ToGraph

type ToVertex (AdjacencyMap a) = a

type Vertex (AdjacencyMap a)

Defined in Algebra.Graph.Class

type Vertex (AdjacencyMap a) = a

empty :: AdjacencyMap a

Construct the empty graph. Complexity: O(1) time and memory.

isEmpty     empty == True
hasVertex x empty == False
vertexCount empty == 0
edgeCount   empty == 0

vertex :: a -> AdjacencyMap a

Construct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.

isEmpty     (vertex x) == False
hasVertex x (vertex x) == True
vertexCount (vertex x) == 1
edgeCount   (vertex x) == 0

overlay :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a

Overlay two graphs. This is a commutative, associative and idempotent operation with the identity empty. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

isEmpty     (overlay x y) == isEmpty   x   && isEmpty   y
hasVertex z (overlay x y) == hasVertex z x || hasVertex z y
vertexCount (overlay x y) >= vertexCount x
vertexCount (overlay x y) <= vertexCount x + vertexCount y
edgeCount   (overlay x y) >= edgeCount x
edgeCount   (overlay x y) <= edgeCount x   + edgeCount y
vertexCount (overlay 1 2) == 2
edgeCount   (overlay 1 2) == 0

connect :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a

Connect two graphs. This is an associative operation with the identity empty, which distributes over overlay and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).

isEmpty     (connect x y) == isEmpty   x   && isEmpty   y
hasVertex z (connect x y) == hasVertex z x || hasVertex z y
vertexCount (connect x y) >= vertexCount x
vertexCount (connect x y) <= vertexCount x + vertexCount y
edgeCount   (connect x y) >= edgeCount x
edgeCount   (connect x y) >= edgeCount y
edgeCount   (connect x y) >= vertexCount x * vertexCount y
edgeCount   (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
vertexCount (connect 1 2) == 2
edgeCount   (connect 1 2) == 1

fromAdjacencySets :: Ord a => [(a, Set a)] -> AdjacencyMap a

Construct a graph from a list of adjacency sets. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

fromAdjacencySets []                                        == empty
fromAdjacencySets [(x, Set.empty)]                          == vertex x
fromAdjacencySets [(x, Set.singleton y)]                    == edge x y
fromAdjacencySets . map (fmap Set.fromList) . adjacencyList == id
overlay (fromAdjacencySets xs) (fromAdjacencySets ys)       == fromAdjacencySets (xs ++ ys)

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 (stars xs)    == True