Data.Graph.Analysis.Algorithms.Common
 Maintainer Ivan.Miljenovic@gmail.com
 Contents Graph decomposition Clique Detection Cycle Detection Chain detection
Description
Defines algorithms that work on both undirected and directed graphs.
Synopsis
 componentsOf :: DynGraph g => g a b -> [g a b] pathTree :: DynGraph g => Decomp g a b -> [NGroup] cliquesIn :: DynGraph g => g a b -> [[LNode a]] cliquesIn' :: DynGraph g => g a b -> [NGroup] findRegular :: Graph g => g a b -> [[Node]] isRegular :: Graph g => g a b -> NGroup -> Bool cyclesIn :: DynGraph g => g a b -> [LNGroup a] cyclesIn' :: DynGraph g => g a b -> [NGroup] uniqueCycles :: DynGraph g => g a b -> [LNGroup a] uniqueCycles' :: DynGraph g => g a b -> [NGroup] chainsIn :: (DynGraph g, Eq b) => g a b -> [LNGroup a] chainsIn' :: (DynGraph g, Eq b) => g a b -> [NGroup]
Graph decomposition

Finding connected components.

Whilst the FGL library does indeed have a function components that returns the connected components of a graph, it returns each component as a list of Nodes. This implementation instead returns each component as a graph, which is much more useful.

Connected components are found by choosing a random node, then recursively extracting all neighbours of that node until no more nodes can be removed.

Note that for directed graphs, these are known as the weakly connected components.

 componentsOf :: DynGraph g => g a b -> [g a b] Source
Find all connected components of a graph.
 pathTree :: DynGraph g => Decomp g a b -> [NGroup] Source
Find all possible paths from this given node, avoiding loops, cycles, etc.
Clique Detection
Clique detection routines. Find cliques by taking out a node, and seeing which other nodes are all common neighbours (by both pre and suc).
 cliquesIn :: DynGraph g => g a b -> [[LNode a]] Source
Finds all cliques (i.e. maximal complete subgraphs) in the given graph.
 cliquesIn' :: DynGraph g => g a b -> [NGroup] Source
Finds all cliques in the graph, without including labels.
 findRegular :: Graph g => g a b -> [[Node]] Source
Find all regular subgraphs of the given graph.
 isRegular :: Graph g => g a b -> NGroup -> Bool Source
Determines if the list of nodes represents a regular subgraph.
Cycle Detection
Cycle detection. Find cycles by finding all paths from a given node, and seeing if it reaches itself again.
 cyclesIn :: DynGraph g => g a b -> [LNGroup a] Source
Find all cycles in the given graph.
 cyclesIn' :: DynGraph g => g a b -> [NGroup] Source
Find all cycles in the given graph, returning just the nodes.
 uniqueCycles :: DynGraph g => g a b -> [LNGroup a] Source
Find all cycles in the given graph, excluding those that are also cliques.
 uniqueCycles' :: DynGraph g => g a b -> [NGroup] Source
Find all cycles in the given graph, excluding those that are also cliques.
Chain detection
A chain is a path in a graph where for each interior node, there is exactly one predecessor and one successor node, i.e. that part of the graph forms a "straight line". Furthermore, the initial node should have only one successor, and the final node should have only one predecessor. Chains are found by recursively finding the next successor in the chain, until either a leaf node is reached or no more nodes match the criteria.
 chainsIn :: (DynGraph g, Eq b) => g a b -> [LNGroup a] Source
Find all chains in the given graph.
 chainsIn' :: (DynGraph g, Eq b) => g a b -> [NGroup] Source
Find all chains in the given graph.
Produced by Haddock version 2.1.0