Algebra.Graph.AdjacencyIntMap.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.AdjacencyIntMap instead.

Adjacency map implementation

newtype AdjacencyIntMap

The AdjacencyIntMap 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))

Note: the Num instance does not satisfy several "customary laws" of Num, which dictate that fromInteger 0 and fromInteger 1 should act as additive and multiplicative identities, and negate as additive inverse. Nevertheless, overloading fromInteger, + and * is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.

The Show instance is defined using basic graph construction primitives:

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

The total order on graphs is defined using size-lexicographic comparison:

• Compare the number of vertices. In case of a tie, continue.
• Compare the sets of vertices. In case of a tie, continue.
• Compare the number of edges. In case of a tie, continue.
• Compare the sets of edges.

Here are a few examples:

vertex 1 < vertex 2
vertex 3 < edge 1 2
vertex 1 < edge 1 1
edge 1 1 < edge 1 2
edge 1 2 < edge 1 1 + edge 2 2
edge 1 2 < edge 1 3

Note that the resulting order refines the isSubgraphOf relation and is compatible with overlay and connect operations:

isSubgraphOf x y ==> x <= y

empty <= x
x     <= x + y
x + y <= x * y

Constructors

AM

Fields

• adjacencyIntMap :: IntMap IntSet

  The adjacency map of a graph: each vertex is associated with a set of its direct successors. Complexity: O(1) time and memory.

  adjacencyIntMap empty      == IntMap.empty
  adjacencyIntMap (vertex x) == IntMap.singleton x IntSet.empty
  adjacencyIntMap (edge 1 1) == IntMap.singleton 1 (IntSet.singleton 1)
  adjacencyIntMap (edge 1 2) == IntMap.fromList [(1,IntSet.singleton 2), (2,IntSet.empty)]
  

Instances

Eq AdjacencyIntMap

Defined in Algebra.Graph.AdjacencyIntMap.Internal

Methods

(==) :: AdjacencyIntMap -> AdjacencyIntMap -> Bool

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

Num AdjacencyIntMap

Note: this does not satisfy the usual ring laws; see AdjacencyIntMap for more details.

Defined in Algebra.Graph.AdjacencyIntMap.Internal

Methods

(+) :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap

(-) :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap

(*) :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap

negate :: AdjacencyIntMap -> AdjacencyIntMap

abs :: AdjacencyIntMap -> AdjacencyIntMap

signum :: AdjacencyIntMap -> AdjacencyIntMap

fromInteger :: Integer -> AdjacencyIntMap

Ord AdjacencyIntMap

Defined in Algebra.Graph.AdjacencyIntMap.Internal

Methods

compare :: AdjacencyIntMap -> AdjacencyIntMap -> Ordering

(<) :: AdjacencyIntMap -> AdjacencyIntMap -> Bool

(<=) :: AdjacencyIntMap -> AdjacencyIntMap -> Bool

(>) :: AdjacencyIntMap -> AdjacencyIntMap -> Bool

(>=) :: AdjacencyIntMap -> AdjacencyIntMap -> Bool

max :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap

min :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap

Show AdjacencyIntMap

Defined in Algebra.Graph.AdjacencyIntMap.Internal

Methods

showsPrec :: Int -> AdjacencyIntMap -> ShowS

show :: AdjacencyIntMap -> String

showList :: [AdjacencyIntMap] -> ShowS

NFData AdjacencyIntMap

Defined in Algebra.Graph.AdjacencyIntMap.Internal

Methods

rnf :: AdjacencyIntMap -> ()

ToGraph AdjacencyIntMap

Defined in Algebra.Graph.ToGraph

Associated Types

type ToVertex AdjacencyIntMap :: Type

Methods

toGraph :: AdjacencyIntMap -> Graph (ToVertex AdjacencyIntMap)

foldg :: r -> (ToVertex AdjacencyIntMap -> r) -> (r -> r -> r) -> (r -> r -> r) -> AdjacencyIntMap -> r

isEmpty :: AdjacencyIntMap -> Bool

size :: AdjacencyIntMap -> Int

hasVertex :: ToVertex AdjacencyIntMap -> AdjacencyIntMap -> Bool

hasEdge :: ToVertex AdjacencyIntMap -> ToVertex AdjacencyIntMap -> AdjacencyIntMap -> Bool

vertexCount :: AdjacencyIntMap -> Int

edgeCount :: AdjacencyIntMap -> Int

vertexList :: AdjacencyIntMap -> [ToVertex AdjacencyIntMap]

edgeList :: AdjacencyIntMap -> [(ToVertex AdjacencyIntMap, ToVertex AdjacencyIntMap)]

vertexSet :: AdjacencyIntMap -> Set (ToVertex AdjacencyIntMap)

vertexIntSet :: AdjacencyIntMap -> IntSet

edgeSet :: AdjacencyIntMap -> Set (ToVertex AdjacencyIntMap, ToVertex AdjacencyIntMap)

preSet :: ToVertex AdjacencyIntMap -> AdjacencyIntMap -> Set (ToVertex AdjacencyIntMap)

preIntSet :: Int -> AdjacencyIntMap -> IntSet

postSet :: ToVertex AdjacencyIntMap -> AdjacencyIntMap -> Set (ToVertex AdjacencyIntMap)

postIntSet :: Int -> AdjacencyIntMap -> IntSet

adjacencyList :: AdjacencyIntMap -> [(ToVertex AdjacencyIntMap, [ToVertex AdjacencyIntMap])]

adjacencyMap :: AdjacencyIntMap -> Map (ToVertex AdjacencyIntMap) (Set (ToVertex AdjacencyIntMap))

adjacencyIntMap :: AdjacencyIntMap -> IntMap IntSet

adjacencyMapTranspose :: AdjacencyIntMap -> Map (ToVertex AdjacencyIntMap) (Set (ToVertex AdjacencyIntMap))

adjacencyIntMapTranspose :: AdjacencyIntMap -> IntMap IntSet

dfsForest :: AdjacencyIntMap -> Forest (ToVertex AdjacencyIntMap)

dfsForestFrom :: [ToVertex AdjacencyIntMap] -> AdjacencyIntMap -> Forest (ToVertex AdjacencyIntMap)

dfs :: [ToVertex AdjacencyIntMap] -> AdjacencyIntMap -> [ToVertex AdjacencyIntMap]

reachable :: ToVertex AdjacencyIntMap -> AdjacencyIntMap -> [ToVertex AdjacencyIntMap]

topSort :: AdjacencyIntMap -> Maybe [ToVertex AdjacencyIntMap]

isAcyclic :: AdjacencyIntMap -> Bool

toAdjacencyMap :: AdjacencyIntMap -> AdjacencyMap (ToVertex AdjacencyIntMap)

toAdjacencyMapTranspose :: AdjacencyIntMap -> AdjacencyMap (ToVertex AdjacencyIntMap)

toAdjacencyIntMap :: AdjacencyIntMap -> AdjacencyIntMap

toAdjacencyIntMapTranspose :: AdjacencyIntMap -> AdjacencyIntMap

isDfsForestOf :: Forest (ToVertex AdjacencyIntMap) -> AdjacencyIntMap -> Bool

isTopSortOf :: [ToVertex AdjacencyIntMap] -> AdjacencyIntMap -> Bool

Graph AdjacencyIntMap

Defined in Algebra.Graph.Class

Associated Types

type Vertex AdjacencyIntMap :: Type

Methods

empty :: AdjacencyIntMap

vertex :: Vertex AdjacencyIntMap -> AdjacencyIntMap

overlay :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap

connect :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap

type ToVertex AdjacencyIntMap

Defined in Algebra.Graph.ToGraph

type ToVertex AdjacencyIntMap = Int

type Vertex AdjacencyIntMap

Defined in Algebra.Graph.Class

type Vertex AdjacencyIntMap = Int

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