Graphalyze-0.15.0.0: Graph-Theoretic Analysis library.

Copyright (c) Ivan Lazar Miljenovic 2009 2-Clause BSD Ivan.Miljenovic@gmail.com None Haskell98

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 LNodes that meet the ending criteria.

endBy' :: Graph g => (g a b -> Node -> NGroup) -> g a b -> NGroup Source #

Find all Nodes 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 Nodes 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 Nodes that can be reached from the provided Nodes.

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

Find all Nodes that can be reached from the provided nodes using Sets rather than lists.

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

Find those Nodes that are reachable only from the provided Nodes.

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

Find those Nodes that are reachable only from the provided Nodes, using Sets 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.