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

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

Algebra.Graph.ToGraph

Contents

Description

Alga is a library for algebraic construction and manipulation of graphs in Haskell. See this paper for the motivation behind the library, the underlying theory, and implementation details.

This module defines the type class ToGraph for capturing data types that can be converted to algebraic graphs. To make an instance of this class you need to define just a single method (toGraph or foldg), which gives you access to many other useful methods for free (although note that the default implementations may be suboptimal performance-wise).

This type class is similar to the standard type class Foldable defined for lists. Furthermore, one can define Foldable methods foldMap and toList using ToGraph.foldg:

foldMap f = foldg mempty f    (<>) (<>)
toList    = foldg []     pure (++) (++)

However, the resulting Foldable instance is problematic. For example, folding equivalent algebraic graphs 1 and 1 + 1 leads to different results:

toList (1    ) == [1]
toList (1 + 1) == [1, 1]

To avoid such cases, we do not provide Foldable instances for algebraic graph datatypes. Furthermore, we require that the four arguments passed to foldg satisfy the laws of the algebra of graphs. The above definitions of foldMap and toList violate this requirement, for example [1] ++ [1] /= [1], and are therefore disallowed.

Synopsis

Type class

class ToGraph t where Source #

The ToGraph type class captures data types that can be converted to algebraic graphs. Instances of this type class should satisfy the laws specified by the default method definitions.

Minimal complete definition

toGraph | foldg

Associated Types

type ToVertex t Source #

The type of vertices of the resulting graph.

Methods

toGraph :: t -> Graph (ToVertex t) Source #

Convert a value to the corresponding algebraic graph, see Algebra.Graph.

toGraph == foldg Empty Vertex Overlay Connect

foldg :: r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r Source #

The method foldg is used for generalised graph folding. It collapses a given value by applying the provided graph construction primitives. The order of arguments is: empty, vertex, overlay and connect, and it is assumed that the arguments satisfy the axioms of the graph algebra.

foldg == Algebra.Graph.foldg . toGraph

isEmpty :: t -> Bool Source #

Check if a graph is empty.

isEmpty == foldg True (const False) (&&) (&&)

hasVertex :: Eq (ToVertex t) => ToVertex t -> t -> Bool Source #

Check if a graph contains a given vertex.

hasVertex x == foldg False (==x) (||) (||)

hasEdge :: Eq (ToVertex t) => ToVertex t -> ToVertex t -> t -> Bool Source #

Check if a graph contains a given edge.

hasEdge x y == Algebra.Graph.hasEdge x y . toGraph

vertexCount :: Ord (ToVertex t) => t -> Int Source #

The number of vertices in a graph.

vertexCount == Set.size . vertexSet

edgeCount :: Ord (ToVertex t) => t -> Int Source #

The number of edges in a graph.

edgeCount == Set.size . edgeSet

vertexList :: Ord (ToVertex t) => t -> [ToVertex t] Source #

The sorted list of vertices of a given graph.

vertexList == Set.toAscList . vertexSet

edgeList :: Ord (ToVertex t) => t -> [(ToVertex t, ToVertex t)] Source #

The sorted list of edges of a graph.

edgeList == Set.toAscList . edgeSet

vertexSet :: Ord (ToVertex t) => t -> Set (ToVertex t) Source #

The set of vertices of a graph.

vertexSet == foldg Set.empty Set.singleton Set.union Set.union

vertexIntSet :: ToVertex t ~ Int => t -> IntSet Source #

The set of vertices of a graph. Like vertexSet but specialised for graphs with vertices of type Int.

vertexIntSet == foldg IntSet.empty IntSet.singleton IntSet.union IntSet.union

edgeSet :: Ord (ToVertex t) => t -> Set (ToVertex t, ToVertex t) Source #

The set of edges of a graph.

edgeSet == Algebra.Graph.AdjacencyMap.edgeSet . toAdjacencyMap

preSet :: Ord (ToVertex t) => ToVertex t -> t -> Set (ToVertex t) Source #

The preset of a vertex is the set of its direct predecessors.

preSet x == Algebra.Graph.AdjacencyMap.preSet x . toAdjacencyMap

preIntSet :: ToVertex t ~ Int => Int -> t -> IntSet Source #

The preset (here preIntSet) of a vertex is the set of its direct predecessors. Like preSet but specialised for graphs with vertices of type Int.

preIntSet x == Algebra.Graph.AdjacencyIntMap.preIntSet x . toAdjacencyIntMap

postSet :: Ord (ToVertex t) => ToVertex t -> t -> Set (ToVertex t) Source #

The postset of a vertex is the set of its direct successors.

postSet x == Algebra.Graph.AdjacencyMap.postSet x . toAdjacencyMap

postIntSet :: ToVertex t ~ Int => Int -> t -> IntSet Source #

The postset (here postIntSet) of a vertex is the set of its direct successors. Like postSet but specialised for graphs with vertices of type Int.

postIntSet x == Algebra.Graph.AdjacencyIntMap.postIntSet x . toAdjacencyIntMap

adjacencyList :: Ord (ToVertex t) => t -> [(ToVertex t, [ToVertex t])] Source #

The sorted adjacency list of a graph.

adjacencyList == Algebra.Graph.AdjacencyMap.adjacencyList . toAdjacencyMap

dfsForest :: Ord (ToVertex t) => t -> Forest (ToVertex t) Source #

Compute the depth-first search forest of a graph that corresponds to searching from each of the graph vertices in the Ord a order.

dfsForest == Algebra.Graph.AdjacencyMap.dfsForest . toAdjacencyMap

dfsForestFrom :: Ord (ToVertex t) => [ToVertex t] -> t -> Forest (ToVertex t) Source #

Compute the depth-first search forest of a graph, searching from each of the given vertices in order. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable.

dfsForestFrom vs == Algebra.Graph.AdjacencyMap.dfsForestFrom vs . toAdjacencyMap

dfs :: Ord (ToVertex t) => [ToVertex t] -> t -> [ToVertex t] Source #

Compute the list of vertices visited by the depth-first search in a graph, when searching from each of the given vertices in order.

dfs vs == Algebra.Graph.AdjacencyMap.dfs vs . toAdjacencyMap

reachable :: Ord (ToVertex t) => ToVertex t -> t -> [ToVertex t] Source #

Compute the list of vertices that are reachable from a given source vertex in a graph. The vertices in the resulting list appear in the depth-first order.

reachable x == Algebra.Graph.AdjacencyMap.reachable x . toAdjacencyMap

topSort :: Ord (ToVertex t) => t -> Either (Cycle (ToVertex t)) [ToVertex t] Source #

Compute the topological sort of a graph or a AM.Cycle if the graph is cyclic.

topSort == Algebra.Graph.AdjacencyMap.topSort . toAdjacencyMap

isAcyclic :: Ord (ToVertex t) => t -> Bool Source #

Check if a given graph is acyclic.

isAcyclic == Algebra.Graph.AdjacencyMap.isAcyclic . toAdjacencyMap

toAdjacencyMap :: Ord (ToVertex t) => t -> AdjacencyMap (ToVertex t) Source #

Convert a value to the corresponding AdjacencyMap.

toAdjacencyMap == foldg empty vertex overlay connect

toAdjacencyMapTranspose :: Ord (ToVertex t) => t -> AdjacencyMap (ToVertex t) Source #

Convert a value to the corresponding AdjacencyMap and transpose the result.

toAdjacencyMapTranspose == foldg empty vertex overlay (flip connect)

toAdjacencyIntMap :: ToVertex t ~ Int => t -> AdjacencyIntMap Source #

Convert a value to the corresponding AdjacencyIntMap.

toAdjacencyIntMap == foldg empty vertex overlay connect

toAdjacencyIntMapTranspose :: ToVertex t ~ Int => t -> AdjacencyIntMap Source #

Convert a value to the corresponding AdjacencyIntMap and transpose the result.

toAdjacencyIntMapTranspose == foldg empty vertex overlay (flip connect)

isDfsForestOf :: Ord (ToVertex t) => Forest (ToVertex t) -> t -> Bool Source #

Check if a given forest is a valid depth-first search forest of a graph.

isDfsForestOf f == Algebra.Graph.AdjacencyMap.isDfsForestOf f . toAdjacencyMap

isTopSortOf :: Ord (ToVertex t) => [ToVertex t] -> t -> Bool Source #

Check if a given list of vertices is a valid topological sort of a graph.

isTopSortOf vs == Algebra.Graph.AdjacencyMap.isTopSortOf vs . toAdjacencyMap
Instances
ToGraph AdjacencyIntMap Source # 
Instance details

Defined in Algebra.Graph.ToGraph

Associated Types

type ToVertex AdjacencyIntMap :: Type Source #

Methods

toGraph :: AdjacencyIntMap -> Graph (ToVertex AdjacencyIntMap) Source #

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

isEmpty :: AdjacencyIntMap -> Bool Source #

hasVertex :: ToVertex AdjacencyIntMap -> AdjacencyIntMap -> Bool Source #

hasEdge :: ToVertex AdjacencyIntMap -> ToVertex AdjacencyIntMap -> AdjacencyIntMap -> Bool Source #

vertexCount :: AdjacencyIntMap -> Int Source #

edgeCount :: AdjacencyIntMap -> Int Source #

vertexList :: AdjacencyIntMap -> [ToVertex AdjacencyIntMap] Source #

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

vertexSet :: AdjacencyIntMap -> Set (ToVertex AdjacencyIntMap) Source #

vertexIntSet :: AdjacencyIntMap -> IntSet Source #

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

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

preIntSet :: Int -> AdjacencyIntMap -> IntSet Source #

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

postIntSet :: Int -> AdjacencyIntMap -> IntSet Source #

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

dfsForest :: AdjacencyIntMap -> Forest (ToVertex AdjacencyIntMap) Source #

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

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

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

topSort :: AdjacencyIntMap -> Either (Cycle (ToVertex AdjacencyIntMap)) [ToVertex AdjacencyIntMap] Source #

isAcyclic :: AdjacencyIntMap -> Bool Source #

toAdjacencyMap :: AdjacencyIntMap -> AdjacencyMap (ToVertex AdjacencyIntMap) Source #

toAdjacencyMapTranspose :: AdjacencyIntMap -> AdjacencyMap (ToVertex AdjacencyIntMap) Source #

toAdjacencyIntMap :: AdjacencyIntMap -> AdjacencyIntMap Source #

toAdjacencyIntMapTranspose :: AdjacencyIntMap -> AdjacencyIntMap Source #

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

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

Ord a => ToGraph (AdjacencyMap a) Source #

See Algebra.Graph.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 #

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 #

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 -> Either (Cycle (ToVertex (AdjacencyMap a))) [ToVertex (AdjacencyMap a)] Source #

isAcyclic :: AdjacencyMap a -> Bool Source #

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

toAdjacencyMapTranspose :: AdjacencyMap a -> AdjacencyMap (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 #

Ord a => ToGraph (Graph a) Source # 
Instance details

Defined in Algebra.Graph.ToGraph

Associated Types

type ToVertex (Graph a) :: Type Source #

Methods

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

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

isEmpty :: Graph a -> Bool Source #

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

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

vertexCount :: Graph a -> Int Source #

edgeCount :: Graph a -> Int Source #

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

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

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

vertexIntSet :: Graph a -> IntSet Source #

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

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

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

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

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

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

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

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

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

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

topSort :: Graph a -> Either (Cycle (ToVertex (Graph a))) [ToVertex (Graph a)] Source #

isAcyclic :: Graph a -> Bool Source #

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

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

toAdjacencyIntMap :: Graph a -> AdjacencyIntMap Source #

toAdjacencyIntMapTranspose :: Graph a -> AdjacencyIntMap Source #

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

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

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 #

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 #

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 -> Either (Cycle (ToVertex (AdjacencyMap a))) [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 #

Ord a => ToGraph (Relation a) Source #

See Algebra.Graph.Relation.

Instance details

Defined in Algebra.Graph.ToGraph

Associated Types

type ToVertex (Relation a) :: Type Source #

Methods

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

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

isEmpty :: Relation a -> Bool Source #

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

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

vertexCount :: Relation a -> Int Source #

edgeCount :: Relation a -> Int Source #

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

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

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

vertexIntSet :: Relation a -> IntSet Source #

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

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

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

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

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

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

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

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

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

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

topSort :: Relation a -> Either (Cycle (ToVertex (Relation a))) [ToVertex (Relation a)] Source #

isAcyclic :: Relation a -> Bool Source #

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

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

toAdjacencyIntMap :: Relation a -> AdjacencyIntMap Source #

toAdjacencyIntMapTranspose :: Relation a -> AdjacencyIntMap Source #

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

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

Ord a => ToGraph (Relation a) Source #

See Algebra.Graph.Symmetric.Relation. Warning: this instance is likely to be modified or removed in future.

Instance details

Defined in Algebra.Graph.ToGraph

Associated Types

type ToVertex (Relation a) :: Type Source #

Methods

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

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

isEmpty :: Relation a -> Bool Source #

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

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

vertexCount :: Relation a -> Int Source #

edgeCount :: Relation a -> Int Source #

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

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

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

vertexIntSet :: Relation a -> IntSet Source #

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

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

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

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

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

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

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

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

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

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

topSort :: Relation a -> Either (Cycle (ToVertex (Relation a))) [ToVertex (Relation a)] Source #

isAcyclic :: Relation a -> Bool Source #

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

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

toAdjacencyIntMap :: Relation a -> AdjacencyIntMap Source #

toAdjacencyIntMapTranspose :: Relation a -> AdjacencyIntMap Source #

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

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

ToGraph (Graph a) Source # 
Instance details

Defined in Algebra.Graph.NonEmpty

Associated Types

type ToVertex (Graph a) :: Type Source #

Methods

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

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

isEmpty :: Graph a -> Bool Source #

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

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

vertexCount :: Graph a -> Int Source #

edgeCount :: Graph a -> Int Source #

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

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

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

vertexIntSet :: Graph a -> IntSet Source #

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

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

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

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

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

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

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

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

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

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

topSort :: Graph a -> Either (Cycle (ToVertex (Graph a))) [ToVertex (Graph a)] Source #

isAcyclic :: Graph a -> Bool Source #

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

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

toAdjacencyIntMap :: Graph a -> AdjacencyIntMap Source #

toAdjacencyIntMapTranspose :: Graph a -> AdjacencyIntMap Source #

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

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

(Eq e, Monoid e, Ord a) => ToGraph (AdjacencyMap e a) Source #

See Algebra.Graph.Labelled.AdjacencyMap.

Instance details

Defined in Algebra.Graph.ToGraph

Associated Types

type ToVertex (AdjacencyMap e a) :: Type Source #

Methods

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

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

isEmpty :: AdjacencyMap e a -> Bool Source #

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

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

vertexCount :: AdjacencyMap e a -> Int Source #

edgeCount :: AdjacencyMap e a -> Int Source #

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

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

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

vertexIntSet :: AdjacencyMap e a -> IntSet Source #

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

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

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

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

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

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

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

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

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

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

topSort :: AdjacencyMap e a -> Either (Cycle (ToVertex (AdjacencyMap e a))) [ToVertex (AdjacencyMap e a)] Source #

isAcyclic :: AdjacencyMap e a -> Bool Source #

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

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

toAdjacencyIntMap :: AdjacencyMap e a -> AdjacencyIntMap Source #

toAdjacencyIntMapTranspose :: AdjacencyMap e a -> AdjacencyIntMap Source #

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

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

(Eq e, Monoid e, Ord a) => ToGraph (Graph e a) Source #

See Algebra.Graph.Labelled.

Instance details

Defined in Algebra.Graph.ToGraph

Associated Types

type ToVertex (Graph e a) :: Type Source #

Methods

toGraph :: Graph e a -> Graph0 (ToVertex (Graph e a)) Source #

foldg :: r -> (ToVertex (Graph e a) -> r) -> (r -> r -> r) -> (r -> r -> r) -> Graph e a -> r Source #

isEmpty :: Graph e a -> Bool Source #

hasVertex :: ToVertex (Graph e a) -> Graph e a -> Bool Source #

hasEdge :: ToVertex (Graph e a) -> ToVertex (Graph e a) -> Graph e a -> Bool Source #

vertexCount :: Graph e a -> Int Source #

edgeCount :: Graph e a -> Int Source #

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

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

vertexSet :: Graph e a -> Set (ToVertex (Graph e a)) Source #

vertexIntSet :: Graph e a -> IntSet Source #

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

preSet :: ToVertex (Graph e a) -> Graph e a -> Set (ToVertex (Graph e a)) Source #

preIntSet :: Int -> Graph e a -> IntSet Source #

postSet :: ToVertex (Graph e a) -> Graph e a -> Set (ToVertex (Graph e a)) Source #

postIntSet :: Int -> Graph e a -> IntSet Source #

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

dfsForest :: Graph e a -> Forest (ToVertex (Graph e a)) Source #

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

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

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

topSort :: Graph e a -> Either (Cycle (ToVertex (Graph e a))) [ToVertex (Graph e a)] Source #

isAcyclic :: Graph e a -> Bool Source #

toAdjacencyMap :: Graph e a -> AdjacencyMap (ToVertex (Graph e a)) Source #

toAdjacencyMapTranspose :: Graph e a -> AdjacencyMap (ToVertex (Graph e a)) Source #

toAdjacencyIntMap :: Graph e a -> AdjacencyIntMap Source #

toAdjacencyIntMapTranspose :: Graph e a -> AdjacencyIntMap Source #

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

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

Derived functions

adjacencyMap :: ToGraph t => Ord (ToVertex t) => t -> Map (ToVertex t) (Set (ToVertex t)) Source #

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

adjacencyMap == Algebra.Graph.AdjacencyMap.adjacencyMap . toAdjacencyMap

adjacencyIntMap :: (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSet Source #

The adjacency map of a graph: each vertex is associated with a set of its direct successors. Like adjacencyMap but specialised for graphs with vertices of type Int.

adjacencyIntMap == Algebra.Graph.AdjacencyIntMap.adjacencyIntMap . toAdjacencyIntMap

adjacencyMapTranspose :: (ToGraph t, Ord (ToVertex t)) => t -> Map (ToVertex t) (Set (ToVertex t)) Source #

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

adjacencyMapTranspose == Algebra.Graph.AdjacencyMap.adjacencyMap . toAdjacencyMapTranspose

adjacencyIntMapTranspose :: (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSet Source #

The transposed adjacency map of a graph: each vertex is associated with a set of its direct predecessors. Like adjacencyMapTranspose but specialised for graphs with vertices of type Int.

adjacencyIntMapTranspose == Algebra.Graph.AdjacencyIntMap.adjacencyIntMap . toAdjacencyIntMapTranspose