Safe Haskell | None |
---|---|
Language | Haskell2010 |
Directed graphs (can of course simulate undirected graphs).
Represented as adjacency maps in direction from source to target.
Each source node maps to a adjacency map of outgoing edges, which is a map from target nodes to edges.
This allows to get outgoing edges in O(log n) time where
n
is the number of nodes in the graph.
However, the set of incoming edges can only be obtained in
O(n log n)
or O(e)
where e
is the total number of edges.
- newtype Graph s t e = Graph {}
- data Edge s t e = Edge {}
- transposeEdge :: Edge s t e -> Edge t s e
- edges :: Graph s t e -> [Edge s t e]
- edgesFrom :: Ord s => Graph s t e -> [s] -> [Edge s t e]
- edgesTo :: Ord t => Graph s t e -> [t] -> [Edge s t e]
- diagonal :: Ord n => Graph n n e -> [Edge n n e]
- lookup :: (Ord s, Ord t) => s -> t -> Graph s t e -> Maybe e
- neighbours :: Ord s => s -> Graph s t e -> [(t, e)]
- neighboursMap :: Ord s => s -> Graph s t e -> Map t e
- sourceNodes :: Graph s t e -> Set s
- targetNodes :: Ord t => Graph s t e -> Set t
- data Nodes n = Nodes {}
- computeNodes :: Ord n => Graph n n e -> Nodes n
- nodes :: Ord n => Graph n n e -> Set n
- fromNodes :: Ord n => [n] -> Graph n n e
- fromList :: (Ord s, Ord t) => [Edge s t e] -> Graph s t e
- fromListWith :: (Ord s, Ord t) => (e -> e -> e) -> [Edge s t e] -> Graph s t e
- toList :: Graph s t e -> [Edge s t e]
- discrete :: Null e => Graph s t e -> Bool
- clean :: Null e => Graph s t e -> Graph s t e
- empty :: Graph s t e
- singleton :: s -> t -> e -> Graph s t e
- insert :: (Ord s, Ord t) => s -> t -> e -> Graph s t e -> Graph s t e
- insertWith :: (Ord s, Ord t) => (e -> e -> e) -> s -> t -> e -> Graph s t e -> Graph s t e
- insertEdge :: (Ord s, Ord t) => Edge s t e -> Graph s t e -> Graph s t e
- insertEdgeWith :: (Ord s, Ord t) => (e -> e -> e) -> Edge s t e -> Graph s t e -> Graph s t e
- union :: (Ord s, Ord t) => Graph s t e -> Graph s t e -> Graph s t e
- unionWith :: (Ord s, Ord t) => (e -> e -> e) -> Graph s t e -> Graph s t e -> Graph s t e
- unions :: (Ord s, Ord t) => [Graph s t e] -> Graph s t e
- unionsWith :: (Ord s, Ord t) => (e -> e -> e) -> [Graph s t e] -> Graph s t e
- removeNode :: Ord n => n -> Graph n n e -> Graph n n e
- removeEdge :: (Ord s, Ord t) => s -> t -> Graph s t e -> Graph s t e
- filterEdges :: (e -> Bool) -> Graph s t e -> Graph s t e
- unzip :: Graph s t (e, e') -> (Graph s t e, Graph s t e')
- mapWithEdge :: (Edge s t e -> e') -> Graph s t e -> Graph s t e'
- sccs' :: Ord n => Graph n n e -> [SCC n]
- sccs :: Ord n => Graph n n e -> [[n]]
- data DAG n = DAG {
- dagGraph :: Graph
- dagComponentMap :: IntMap (SCC n)
- dagNodeMap :: Map n Int
- dagInvariant :: Ord n => DAG n -> Bool
- oppositeDAG :: DAG n -> DAG n
- reachable :: Ord n => DAG n -> SCC n -> [n]
- sccDAG' :: forall n e. Ord n => Graph n n e -> [SCC n] -> DAG n
- sccDAG :: Ord n => Graph n n e -> DAG n
- acyclic :: Ord n => Graph n n e -> Bool
- reachableFrom :: Ord n => Graph n n e -> n -> Map n (Int, [Edge n n e])
- walkSatisfying :: Ord n => (e -> Bool) -> (e -> Bool) -> Graph n n e -> n -> n -> Maybe [Edge n n e]
- composeWith :: (Ord t, Ord u) => (c -> d -> e) -> (e -> e -> e) -> Graph s t c -> Graph t u d -> Graph s u e
- complete :: (Eq e, Null e, SemiRing e, Ord n) => Graph n n e -> Graph n n e
- gaussJordanFloydWarshallMcNaughtonYamadaReference :: forall n e. (Ord n, Eq e, StarSemiRing e) => Graph n n e -> Graph n n e
- gaussJordanFloydWarshallMcNaughtonYamada :: forall n e. (Ord n, Eq e, StarSemiRing e) => Graph n n e -> (Graph n n e, [SCC n])
Documentation
Graph s t e
is a directed graph with
source nodes in s
target nodes in t
and edges in e
.
Admits at most one edge between any two nodes.
Several edges can be modeled by using a collection type for e
.
Represented as "adjacency list", or rather, adjacency map.
This allows to get all outgoing edges for a node
in O(log n)
time where n
is the number of nodes of the graph.
Incoming edges can only be computed in O(n + e)
time where
e
is the number of edges.
(Ord r, Ord f) => SetToInfty f (ConGraph r f) Source # | |
Functor (Graph s t) Source # | |
(Eq e, Eq t, Eq s) => Eq (Graph s t e) Source # | |
(Show e, Show t, Show s) => Show (Graph s t e) Source # | |
(Ord r, Ord f, Negative a) => Negative (Graphs r f a) Source # | |
(Ord r, Ord f, Negative a) => Negative (Graph r f a) Source # | A graph is |
(PrettyTCM n, PrettyTCM (WithNode n e)) => PrettyTCM (Graph n n e) Source # | |
Eq f => SetToInfty f (Edge' r f a) Source # | |
Functor (Edge s t) Source # | |
(Eq e, Eq t, Eq s) => Eq (Edge s t e) Source # | |
(Ord e, Ord t, Ord s) => Ord (Edge s t e) Source # | |
(Show e, Show t, Show s) => Show (Edge s t e) Source # | |
(Ord r, Ord f, Dioid a) => Dioid (Edge' r f a) Source # | |
(Ord r, Ord f, MeetSemiLattice a) => MeetSemiLattice (Edge' r f a) Source # | |
(Ord r, Ord f, Top a) => Top (Edge' r f a) Source # | |
Negative a => Negative (Edge' r f a) Source # | An edge is negative if its label is. |
transposeEdge :: Edge s t e -> Edge t s e Source #
Reverse an edge.
edgesFrom :: Ord s => Graph s t e -> [s] -> [Edge s t e] Source #
All edges originating in the given nodes. (I.e., all outgoing edges for the given nodes.)
Roughly linear in the length of the result list O(result)
.
edgesTo :: Ord t => Graph s t e -> [t] -> [Edge s t e] Source #
All edges ending in the given nodes. (I.e., all incoming edges for the given nodes.)
Expensive: O(n * |ts| * log n)
.
neighbours :: Ord s => s -> Graph s t e -> [(t, e)] Source #
Get a list of outgoing edges with target.
neighboursMap :: Ord s => s -> Graph s t e -> Map t e Source #
Get a list of outgoing edges with target.
sourceNodes :: Graph s t e -> Set s Source #
Returns all the nodes with outgoing edges. O(n)
.
targetNodes :: Ord t => Graph s t e -> Set t Source #
Returns all the nodes with incoming edges. Expensive! O(e)
.
For homogeneous graphs, (s = t)
we can compute a set
of all nodes.
Structure Nodes
is for computing all nodes but also
remembering which were incoming and which outgoing.
This is mostly for efficiency reasons, to avoid recomputation
when all three sets are needed.
fromNodes :: Ord n => [n] -> Graph n n e Source #
Constructs a completely disconnected graph containing the given
nodes. O(n)
.
fromList :: (Ord s, Ord t) => [Edge s t e] -> Graph s t e Source #
Constructs a graph from a list of edges. O(e log n)
Later edges overwrite earlier edges.
fromListWith :: (Ord s, Ord t) => (e -> e -> e) -> [Edge s t e] -> Graph s t e Source #
Constructs a graph from a list of edges. O(e log n)
Later edges are combined with earlier edges using the supplied function.
discrete :: Null e => Graph s t e -> Bool Source #
Check whether the graph is discrete (no edges).
This could be seen as an empty graph.
Worst-case (is discrete): O(e)
.
singleton :: s -> t -> e -> Graph s t e Source #
A graph with two nodes and a single connecting edge.
insert :: (Ord s, Ord t) => s -> t -> e -> Graph s t e -> Graph s t e Source #
Insert an edge into the graph.
insertWith :: (Ord s, Ord t) => (e -> e -> e) -> s -> t -> e -> Graph s t e -> Graph s t e Source #
Insert an edge, possibly combining old
edge weight with new
weight by
given function f
into f new old
.
insertEdgeWith :: (Ord s, Ord t) => (e -> e -> e) -> Edge s t e -> Graph s t e -> Graph s t e Source #
removeNode :: Ord n => n -> Graph n n e -> Graph n n e Source #
Removes the given node, be it source or target, and all corresponding edges, from the graph.
Expensive! O(n log n)
.
removeEdge :: (Ord s, Ord t) => s -> t -> Graph s t e -> Graph s t e Source #
removeEdge s t g
removes the edge going from s
to t
, if any.
O((log n)^2)
.
filterEdges :: (e -> Bool) -> Graph s t e -> Graph s t e Source #
Keep only the edges that satisfy the predicate. O(e).
unzip :: Graph s t (e, e') -> (Graph s t e, Graph s t e') Source #
Unzipping a graph (naive implementation using fmap).
mapWithEdge :: (Edge s t e -> e') -> Graph s t e -> Graph s t e' Source #
Maps over a graph under availability of positional information,
like mapWithKey
.
sccs' :: Ord n => Graph n n e -> [SCC n] Source #
The graph's strongly connected components, in reverse topological order.
sccs :: Ord n => Graph n n e -> [[n]] Source #
The graph's strongly connected components, in reverse topological order.
SCC DAGs.
The maps map SCC indices to and from SCCs/nodes.
DAG | |
|
oppositeDAG :: DAG n -> DAG n Source #
The opposite DAG.
Constructs a DAG containing the graph's strongly connected components.
sccDAG :: Ord n => Graph n n e -> DAG n Source #
Constructs a DAG containing the graph's strongly connected components.
reachableFrom :: Ord n => Graph n n e -> n -> Map n (Int, [Edge n n e]) Source #
reachableFrom g n
is a map containing all nodes reachable from
n
in g
. For each node a simple path to the node is given, along
with its length (the number of edges). The paths are as short as
possible (in terms of the number of edges).
Precondition: n
must be a node in g
. The number of nodes in the
graph must not be larger than
.maxBound
:: Int
Amortised time complexity (assuming that comparisons take constant time): O(e log n), if the lists are not inspected. Inspection of a prefix of a list is linear in the length of the prefix.
walkSatisfying :: Ord n => (e -> Bool) -> (e -> Bool) -> Graph n n e -> n -> n -> Maybe [Edge n n e] Source #
walkSatisfying every some g from to
determines if there is a
walk from from
to to
in g
, in which every edge satisfies the
predicate every
, and some edge satisfies the predicate some
. If
there are several such walks, then a shortest one (in terms of the
number of edges) is returned.
Precondition: from
and to
must be nodes in g
. The number of
nodes in the graph must not be larger than
.maxBound
:: Int
Amortised time complexity (assuming that comparisons and the predicates take constant time to compute): O(e log n).
composeWith :: (Ord t, Ord u) => (c -> d -> e) -> (e -> e -> e) -> Graph s t c -> Graph t u d -> Graph s u e Source #
composeWith times plus g g'
finds all edges
s --c_i--> t_i --d_i--> u
and constructs the
result graph from edge(s,u) = sum_i (c_i times d_i)
.
Complexity: for each edge s --> t
in g
we lookup up
all edges starting in with t
in g'
.
complete :: (Eq e, Null e, SemiRing e, Ord n) => Graph n n e -> Graph n n e Source #
Transitive closure ported from Agda.Termination.CallGraph.
Relatively efficient, see Issue 1560.
gaussJordanFloydWarshallMcNaughtonYamadaReference :: forall n e. (Ord n, Eq e, StarSemiRing e) => Graph n n e -> Graph n n e Source #
Computes the transitive closure of the graph.
Uses the Gauss-Jordan-Floyd-Warshall-McNaughton-Yamada algorithm (as described by Russell O'Connor in "A Very General Method of Computing Shortest Paths" http://r6.ca/blog/20110808T035622Z.html), implemented using matrices.
The resulting graph does not contain any zero edges.
This algorithm should be seen as a reference implementation. In
practice gaussJordanFloydWarshallMcNaughtonYamada
is likely to be
more efficient.
gaussJordanFloydWarshallMcNaughtonYamada :: forall n e. (Ord n, Eq e, StarSemiRing e) => Graph n n e -> (Graph n n e, [SCC n]) Source #
Computes the transitive closure of the graph.
Uses the Gauss-Jordan-Floyd-Warshall-McNaughton-Yamada algorithm
(as described by Russell O'Connor in "A Very General Method of
Computing Shortest Paths"
http://r6.ca/blog/20110808T035622Z.html), implemented using
Graph
, and with some shortcuts:
- Zero edge differences are not added to the graph, thus avoiding some zero edges.
- Strongly connected components are used to avoid computing some zero edges.
The graph's strongly connected components (in reverse topological order) are returned along with the transitive closure.