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.