| Copyright | (c) Andrey Mokhov 2016-2022 |
|---|---|
| License | MIT (see the file LICENSE) |
| Maintainer | andrey.mokhov@gmail.com |
| Stability | experimental |
| Safe Haskell | None |
| Language | Haskell2010 |
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
:
foldMapf =foldgmemptyf (<>) (<>)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
-
class
ToGraph
t
where
- type ToVertex t
- toGraph :: t -> Graph ( ToVertex t)
- foldg :: r -> ( ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
- isEmpty :: t -> Bool
- hasVertex :: Eq ( ToVertex t) => ToVertex t -> t -> Bool
- hasEdge :: Eq ( ToVertex t) => ToVertex t -> ToVertex t -> t -> Bool
- vertexCount :: Ord ( ToVertex t) => t -> Int
- edgeCount :: Ord ( ToVertex t) => t -> Int
- vertexList :: Ord ( ToVertex t) => t -> [ ToVertex t]
- edgeList :: Ord ( ToVertex t) => t -> [( ToVertex t, ToVertex t)]
- vertexSet :: Ord ( ToVertex t) => t -> Set ( ToVertex t)
- vertexIntSet :: ToVertex t ~ Int => t -> IntSet
- edgeSet :: Ord ( ToVertex t) => t -> Set ( ToVertex t, ToVertex t)
- preSet :: Ord ( ToVertex t) => ToVertex t -> t -> Set ( ToVertex t)
- preIntSet :: ToVertex t ~ Int => Int -> t -> IntSet
- postSet :: Ord ( ToVertex t) => ToVertex t -> t -> Set ( ToVertex t)
- postIntSet :: ToVertex t ~ Int => Int -> t -> IntSet
- adjacencyList :: Ord ( ToVertex t) => t -> [( ToVertex t, [ ToVertex t])]
- dfsForest :: Ord ( ToVertex t) => t -> Forest ( ToVertex t)
- dfsForestFrom :: Ord ( ToVertex t) => [ ToVertex t] -> t -> Forest ( ToVertex t)
- dfs :: Ord ( ToVertex t) => [ ToVertex t] -> t -> [ ToVertex t]
- reachable :: Ord ( ToVertex t) => ToVertex t -> t -> [ ToVertex t]
- topSort :: Ord ( ToVertex t) => t -> Either ( Cycle ( ToVertex t)) [ ToVertex t]
- isAcyclic :: Ord ( ToVertex t) => t -> Bool
- toAdjacencyMap :: Ord ( ToVertex t) => t -> AdjacencyMap ( ToVertex t)
- toAdjacencyMapTranspose :: Ord ( ToVertex t) => t -> AdjacencyMap ( ToVertex t)
- toAdjacencyIntMap :: ToVertex t ~ Int => t -> AdjacencyIntMap
- toAdjacencyIntMapTranspose :: ToVertex t ~ Int => t -> AdjacencyIntMap
- isDfsForestOf :: Ord ( ToVertex t) => Forest ( ToVertex t) -> t -> Bool
- isTopSortOf :: Ord ( ToVertex t) => [ ToVertex t] -> t -> Bool
- adjacencyMap :: ToGraph t => Ord ( ToVertex t) => t -> Map ( ToVertex t) ( Set ( ToVertex t))
- adjacencyIntMap :: ( ToGraph t, ToVertex t ~ Int ) => t -> IntMap IntSet
- adjacencyMapTranspose :: ( ToGraph t, Ord ( ToVertex t)) => t -> Map ( ToVertex t) ( Set ( ToVertex t))
- adjacencyIntMapTranspose :: ( ToGraph t, ToVertex t ~ Int ) => t -> IntMap IntSet
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.
Methods
toGraph :: t -> Graph ( ToVertex t) Source #
Convert a value to the corresponding algebraic graph, see Algebra.Graph .
toGraph ==foldgEmptyVertexOverlayConnect
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
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 #
vertexCount :: Ord ( ToVertex t) => t -> Int Source #
edgeCount :: Ord ( ToVertex t) => t -> Int Source #
vertexList :: Ord ( ToVertex t) => t -> [ ToVertex t] Source #
edgeList :: Ord ( ToVertex t) => t -> [( ToVertex t, ToVertex t)] Source #
vertexSet :: Ord ( ToVertex t) => t -> Set ( ToVertex t) Source #
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 ==foldgIntSet.emptyIntSet.singletonIntSet.unionIntSet.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.preSetx .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.preIntSetx .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.postSetx .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.postIntSetx .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 ==foldgemptyvertexoverlayconnect
toAdjacencyMapTranspose :: Ord ( ToVertex t) => t -> AdjacencyMap ( ToVertex t) Source #
Convert a value to the corresponding
AdjacencyMap
and transpose the
result.
toAdjacencyMapTranspose ==foldgemptyvertexoverlay(flipconnect)
toAdjacencyIntMap :: ToVertex t ~ Int => t -> AdjacencyIntMap Source #
Convert a value to the corresponding
AdjacencyIntMap
.
toAdjacencyIntMap ==foldgemptyvertexoverlayconnect
toAdjacencyIntMapTranspose :: ToVertex t ~ Int => t -> AdjacencyIntMap Source #
Convert a value to the corresponding
AdjacencyIntMap
and transpose
the result.
toAdjacencyIntMapTranspose ==foldgemptyvertexoverlay(flipconnect)
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
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