Safe Haskell | None |
---|---|
Language | Haskell98 |
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 :: (Ord s, Ord t) => Graph s t e -> [Edge s t e]
- edgesFrom :: (Ord s, Ord t) => Graph s t e -> [s] -> [Edge s t e]
- edgesTo :: (Ord s, 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, Ord t) => s -> Graph s t e -> [(t, e)]
- neighboursMap :: (Ord s, Ord t) => s -> Graph s t e -> Map t e
- sourceNodes :: (Ord s, Ord t) => Graph s t e -> Set s
- targetNodes :: (Ord s, 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 :: (Ord s, Ord t) => Graph s t e -> [Edge s t e]
- discrete :: Null e => Graph s t e -> Bool
- clean :: (Ord s, Ord t, Null e) => Graph s t e -> Graph s t e
- empty :: Graph s t e
- singleton :: (Ord s, Ord t) => 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 :: (Ord s, Ord t) => (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 :: (Ord s, Ord t) => (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
- composeWith :: (Ord s, 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
- findPath :: (SemiRing e, Ord n) => (e -> Bool) -> n -> n -> Graph n n e -> Maybe e
- allPaths :: (SemiRing e, Ord n, Ord c) => (e -> c) -> n -> n -> Graph n n e -> [e]
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 s, Eq t, Eq e) => Eq (Graph s t e) Source | |
(Show s, Show t, Show e) => Show (Graph s t e) Source | |
(Ord n, SemiRing e, Arbitrary n, Arbitrary e) => Arbitrary (Graph n n 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 s, Eq t, Eq e) => Eq (Edge s t e) Source | |
(Ord s, Ord t, Ord e) => Ord (Edge s t e) Source | |
(Show s, Show t, Show e) => Show (Edge s t e) Source | |
(CoArbitrary s, CoArbitrary t, CoArbitrary e) => CoArbitrary (Edge s t e) Source | |
(Arbitrary s, Arbitrary t, Arbitrary e) => Arbitrary (Edge s t e) Source | |
(Show r, Show f, Show a, Ord r, Ord f, Dioid a) => Dioid (Edge' r f a) Source | |
(Show r, Show f, Show a, 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.
edges :: (Ord s, Ord t) => Graph s t e -> [Edge s t e] Source
Turn a graph into a list of edges. O(n + e)
edgesFrom :: (Ord s, Ord t) => 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 s, 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, Ord t) => s -> Graph s t e -> [(t, e)] Source
Get a list of outgoing edges with target.
neighboursMap :: (Ord s, Ord t) => s -> Graph s t e -> Map t e Source
Get a list of outgoing edges with target.
sourceNodes :: (Ord s, Ord t) => Graph s t e -> Set s Source
Returns all the nodes with outgoing edges. O(n)
.
targetNodes :: (Ord s, 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.
computeNodes :: Ord n => Graph n n e -> Nodes n Source
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.
toList :: (Ord s, Ord t) => Graph s t e -> [Edge s t e] Source
Convert a graph into a list of edges. O(e)
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 :: (Ord s, Ord t) => 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 :: (Ord s, Ord t) => (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 :: (Ord s, Ord t) => (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.
composeWith :: (Ord s, 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 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.