Copyright | (c) Ivan Lazar Miljenovic 2009 |
---|---|
License | 2-Clause BSD |
Maintainer | Ivan.Miljenovic@gmail.com |
Safe Haskell | None |
Language | Haskell98 |
Defines algorithms that work on directed graphs.
- endNode :: Graph g => (g a b -> Node -> NGroup) -> g a b -> LNode a -> Bool
- endNode' :: Graph g => (g a b -> Node -> NGroup) -> g a b -> Node -> Bool
- endBy :: Graph g => (g a b -> Node -> NGroup) -> g a b -> LNGroup a
- endBy' :: Graph g => (g a b -> Node -> NGroup) -> g a b -> NGroup
- rootsOf :: Graph g => g a b -> LNGroup a
- rootsOf' :: Graph g => g a b -> NGroup
- isRoot :: Graph g => g a b -> LNode a -> Bool
- isRoot' :: Graph g => g a b -> Node -> Bool
- leavesOf :: Graph g => g a b -> LNGroup a
- leavesOf' :: Graph g => g a b -> NGroup
- isLeaf :: Graph g => g a b -> LNode a -> Bool
- isLeaf' :: Graph g => g a b -> Node -> Bool
- singletonsOf :: Graph g => g a b -> LNGroup a
- singletonsOf' :: Graph g => g a b -> NGroup
- isSingleton :: Graph g => g a b -> LNode a -> Bool
- isSingleton' :: Graph g => g a b -> Node -> Bool
- coreOf :: (DynGraph g, Eq a, Eq b) => g a b -> g a b
- levelGraph :: (Ord a, DynGraph g) => g a b -> g (GenCluster a) b
- levelGraphFrom :: (Ord a, DynGraph g) => NGroup -> g a b -> g (GenCluster a) b
- minLevel :: Int
- accessibleFrom :: Graph g => g a b -> [Node] -> [Node]
- accessibleFrom' :: Graph g => g a b -> Set Node -> Set Node
- accessibleOnlyFrom :: Graph g => g a b -> [Node] -> [Node]
- accessibleOnlyFrom' :: Graph g => g a b -> Set Node -> Set Node
- leafMinPaths :: Graph g => g a b -> [LNGroup a]
- leafMinPaths' :: Graph g => g a b -> [NGroup]
Ending nodes
Find starting/ending nodes.
We define an ending node as one where, given a function:
f :: (Graph g) => g a b -> Node -> [Node]
the only allowed result is that node itself (to allow for loops).
endNode :: Graph g => (g a b -> Node -> NGroup) -> g a b -> LNode a -> Bool Source #
Determine if this LNode
is an ending node.
endNode' :: Graph g => (g a b -> Node -> NGroup) -> g a b -> Node -> Bool Source #
Determine if this Node
is an ending node.
endBy :: Graph g => (g a b -> Node -> NGroup) -> g a b -> LNGroup a Source #
Find all LNode
s that meet the ending criteria.
endBy' :: Graph g => (g a b -> Node -> NGroup) -> g a b -> NGroup Source #
Find all Node
s that match the ending criteria.
Root nodes
Leaf nodes
Singleton nodes
singletonsOf :: Graph g => g a b -> LNGroup a Source #
Find all singletons of the graph.
singletonsOf' :: Graph g => g a b -> NGroup Source #
Find all singletons of the graph.
isSingleton :: Graph g => g a b -> LNode a -> Bool Source #
Returns True
if this LNode
is a singleton.
Subgraphs
coreOf :: (DynGraph g, Eq a, Eq b) => g a b -> g a b Source #
The core of the graph is the part of the graph containing all the cycles, etc. Depending on the context, it could be interpreted as the part of the graph where all the "work" is done.
Clustering
levelGraph :: (Ord a, DynGraph g) => g a b -> g (GenCluster a) b Source #
Cluster the nodes in the graph based upon how far away they are
from a root node. Root nodes are in the cluster labelled minLevel
,
nodes in level "n" (with n > minLevel
) are at least n edges away
from a root node.
levelGraphFrom :: (Ord a, DynGraph g) => NGroup -> g a b -> g (GenCluster a) b Source #
As with levelGraph
but provide a custom grouping of Node
s to
consider as the "roots".
The level of the nodes in the NGroup
provided to
levelGraphFrom
(or the root nodes for levelGraph
). A level
less than this indicates that the node is not accessible.
Node accessibility
Other
leafMinPaths :: Graph g => g a b -> [LNGroup a] Source #
The shortest paths to each of the leaves in the graph (excluding singletons). This can be used to obtain an indication of the overall height/depth of the graph.
leafMinPaths' :: Graph g => g a b -> [NGroup] Source #
The shortest paths to each of the leaves in the graph (excluding singletons). This can be used to obtain an indication of the overall height/depth of the graph.