|
Data.Graph.Analysis.Algorithms.Common | Maintainer | Ivan.Miljenovic@gmail.com |
|
|
|
|
|
Description |
Defines algorithms that work on both undirected and
directed graphs.
|
|
Synopsis |
|
|
|
|
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.
|
|
|
Find all connected components of a graph.
|
|
|
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).
|
|
|
Finds all cliques (i.e. maximal complete subgraphs) in the given graph.
|
|
|
Finds all cliques in the graph, without including labels.
|
|
|
Find all regular subgraphs of the given graph.
|
|
|
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.
|
|
|
Find all cycles in the given graph.
|
|
|
Find all cycles in the given graph, returning just the nodes.
|
|
|
Find all cycles in the given graph, excluding those that are also cliques.
|
|
|
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.
|
|
|
Find all chains in the given graph.
|
|
|
Find all chains in the given graph.
|
|
Produced by Haddock version 2.3.0 |