algebraic-graphs-0.3: A library for algebraic graph construction and transformation

Copyright(c) Andrey Mokhov 2016-2018
LicenseMIT (see the file LICENSE)
Maintainerandrey.mokhov@gmail.com
Stabilityexperimental
Safe HaskellNone
LanguageHaskell2010

Algebra.Graph.NonEmpty.AdjacencyMap.Internal

Contents

Description

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

Synopsis

Adjacency map implementation

newtype AdjacencyMap a Source #

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

Note: the signum method of the type class Num cannot be implemented and will throw an error. Furthermore, 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 (1         :: AdjacencyMap Int) == "vertex 1"
show (1 + 2     :: AdjacencyMap Int) == "vertices1 [1,2]"
show (1 * 2     :: AdjacencyMap Int) == "edge 1 2"
show (1 * 2 * 3 :: AdjacencyMap Int) == "edges1 [(1,2),(1,3),(2,3)]"
show (1 * 2 + 3 :: AdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"

The Eq instance satisfies the following laws of algebraic graphs:

  • overlay is commutative, associative and idempotent:

          x + y == y + x
    x + (y + z) == (x + y) + z
          x + x == x
  • connect is associative:

    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
  • connect satisfies absorption and saturation:

    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
x     <= x + y
x + y <= x * y

Constructors

NAM 

Fields

Instances
Eq a => Eq (AdjacencyMap a) Source # 
Instance details

Defined in Algebra.Graph.NonEmpty.AdjacencyMap.Internal

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

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

Instance details

Defined in Algebra.Graph.NonEmpty.AdjacencyMap.Internal

Ord a => Ord (AdjacencyMap a) Source # 
Instance details

Defined in Algebra.Graph.NonEmpty.AdjacencyMap.Internal

(Ord a, Show a) => Show (AdjacencyMap a) Source # 
Instance details

Defined in Algebra.Graph.NonEmpty.AdjacencyMap.Internal

NFData a => NFData (AdjacencyMap a) Source # 
Instance details

Defined in Algebra.Graph.NonEmpty.AdjacencyMap.Internal

Methods

rnf :: AdjacencyMap a -> () #

Ord a => ToGraph (AdjacencyMap a) Source #

See Algebra.Graph.NonEmpty.AdjacencyMap.

Instance details

Defined in Algebra.Graph.ToGraph

Associated Types

type ToVertex (AdjacencyMap a) :: Type Source #

Methods

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

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

isEmpty :: AdjacencyMap a -> Bool Source #

size :: AdjacencyMap a -> Int Source #

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

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

vertexCount :: AdjacencyMap a -> Int Source #

edgeCount :: AdjacencyMap a -> Int Source #

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

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

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

vertexIntSet :: AdjacencyMap a -> IntSet Source #

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

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

preIntSet :: Int -> AdjacencyMap a -> IntSet Source #

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

postIntSet :: Int -> AdjacencyMap a -> IntSet Source #

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

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

adjacencyIntMap :: AdjacencyMap a -> IntMap IntSet Source #

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

adjacencyIntMapTranspose :: AdjacencyMap a -> IntMap IntSet Source #

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

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

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

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

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

isAcyclic :: AdjacencyMap a -> Bool Source #

toAdjacencyMap :: AdjacencyMap a -> AdjacencyMap0 (ToVertex (AdjacencyMap a)) Source #

toAdjacencyMapTranspose :: AdjacencyMap a -> AdjacencyMap0 (ToVertex (AdjacencyMap a)) Source #

toAdjacencyIntMap :: AdjacencyMap a -> AdjacencyIntMap Source #

toAdjacencyIntMapTranspose :: AdjacencyMap a -> AdjacencyIntMap Source #

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

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

type ToVertex (AdjacencyMap a) Source # 
Instance details

Defined in Algebra.Graph.ToGraph

type ToVertex (AdjacencyMap a) = a

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

Check if the internal graph representation is consistent, i.e. that all edges refer to existing vertices, and the graph is non-empty. 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 (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