Graphalyze-0.14.1.1: Graph-Theoretic Analysis library.

Data.Graph.Analysis.Algorithms.Directed

Description

Defines algorithms that work on directed graphs.

Synopsis

# 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

rootsOf :: Graph g => g a b -> LNGroup a Source

Find all roots of the graph.

rootsOf' :: Graph g => g a b -> NGroup Source

Find all roots of the graph.

isRoot :: Graph g => g a b -> LNode a -> Bool Source

Returns `True` if this `LNode` is a root.

isRoot' :: Graph g => g a b -> Node -> Bool Source

Returns `True` if this `Node` is a root.

## Leaf nodes

leavesOf :: Graph g => g a b -> LNGroup a Source

Find all leaves of the graph.

leavesOf' :: Graph g => g a b -> NGroup Source

Find all leaves of the graph.

isLeaf :: Graph g => g a b -> LNode a -> Bool Source

Returns `True` if this `LNode` is a leaf.

isLeaf' :: Graph g => g a b -> Node -> Bool Source

Returns `True` if this `Node` is a leaf.

## 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.

isSingleton' :: Graph g => g a b -> Node -> Bool Source

Returns `True` if this `Node` 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

accessibleFrom :: Graph g => g a b -> [Node] -> [Node] Source

Find all `Node`s that can be reached from the provided `Node`s.

accessibleFrom' :: Graph g => g a b -> Set Node -> Set Node Source

Find all `Node`s that can be reached from the provided nodes using `Set`s rather than lists.

accessibleOnlyFrom :: Graph g => g a b -> [Node] -> [Node] Source

Find those `Node`s that are reachable only from the provided `Node`s.

accessibleOnlyFrom' :: Graph g => g a b -> Set Node -> Set Node Source

Find those `Node`s that are reachable only from the provided `Node`s, using `Set`s rather than lists.

# 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.