API for clojure.algo.graph - Basic graph theory algorithms 0.1.0 (in development)

by Jeffrey Straszheim

Full namespace name: clojure.algo.graph

Overview

Basic graph theory algorithms

Public Variables and Functions



add-loops

function
Usage: (add-loops g)
For each node n, add the edge n->n if not already present.

    
    
    Source
  


component-graph

function
Usage: (component-graph g)
       (component-graph g sccs)
Given a graph, perhaps with cycles, return a reduced graph that is acyclic.
Each node in the new graph will be a set of nodes from the old.
These sets are the strongly connected components.  Each edge will
be the union of the corresponding edges of the prior graph.

    
    
    Source
  


dependency-list

function
Usage: (dependency-list g)
Similar to a topological sort, this returns a vector of sets. The
set of nodes at index 0 are independent.  The set at index 1 depend
on index 0; those at 2 depend on 0 and 1, and so on.  Those withing
a set have no mutual dependencies.  Assume the input graph (which
much be acyclic) has an edge a->b when a depends on b.

    
    
    Source
  


fixed-point

function
Usage: (fixed-point data fun max equal)
Repeatedly apply fun to data until (equal old-data new-data)
returns true.  If max iterations occur, it will throw an
exception.  Set max to nil for unlimited iterations.

    
    
    Source
  


get-neighbors

function
Usage: (get-neighbors g n)
Get the neighbors of a node.

    
    
    Source
  


lazy-walk

function
Usage: (lazy-walk g n)
       (lazy-walk g ns v)
Return a lazy sequence of the nodes of a graph starting a node n.  Optionally,
provide a set of visited notes (v) and a collection of nodes to
visit (ns).

    
    
    Source
  


post-ordered-nodes

function
Usage: (post-ordered-nodes g)
Return a sequence of indexes of a post-ordered walk of the graph.

    
    
    Source
  


recursive-component?

function
Usage: (recursive-component? g ns)
Is the component (recieved from scc) self recursive?

    
    
    Source
  


remove-loops

function
Usage: (remove-loops g)
For each node n, remove any edges n->n.

    
    
    Source
  


reverse-graph

function
Usage: (reverse-graph g)
Given a directed graph, return another directed graph with the
order of the edges reversed.

    
    
    Source
  


scc

function
Usage: (scc g)
Returns, as a sequence of sets, the strongly connected components
of g.

    
    
    Source
  


self-recursive-sets

function
Usage: (self-recursive-sets g)
Returns, as a sequence of sets, the components of a graph that are
self-recursive.

    
    
    Source
  


stratification-list

function
Usage: (stratification-list g1 g2)
Similar to dependency-list (see doc), except two graphs are
provided.  The first is as dependency-list.  The second (which may
have cycles) provides a partial-dependency relation.  If node a
depends on node b (meaning an edge a->b exists) in the second
graph, node a must be equal or later in the sequence.

    
    
    Source
  


transitive-closure

function
Usage: (transitive-closure g)
Returns the transitive closure of a graph.  The neighbors are lazily computed.

Note: some version of this algorithm return all edges a->a
regardless of whether such loops exist in the original graph.  This
version does not.  Loops will be included only if produced by
cycles in the graph.  If you have code that depends on such
behavior, call (-> g transitive-closure add-loops)

    
    
    Source
  
Logo & site design by Tom Hickey.
Clojure auto-documentation system by Tom Faulhaber.