CrossClj

0.1.1 docs

SourceDocs



RECENT
    VARS
    ->DirectedGraph
    add-loops
    component-graph
    dependency-list
    fixed-point
    fold-into-sets
    get-neighbors
    lazy-walk
    map->DirectedGraph
    post-ordered-nodes
    post-ordered-visit
    recursive-component?
    remove-loops
    reverse-graph
    scc
    self-recursive-sets
    stratification-list
    transitive-closure

    « Index of all namespaces of this project

    Basic graph theory algorithms
    

    — Jeffrey Straszheim

    (->DirectedGraph nodes neighbors)
    Positional factory function for class datalog.graph.DirectedGraph.
    
    (add-loops g)
    For each node n, add the edge n->n if not already present.
    
    (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.
    (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.
    (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.
    Private
    (fold-into-sets priorities)
    (get-neighbors g n)
    Get the neighbors of a node.
    
    (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).
    (map->DirectedGraph m__7585__auto__)
    Factory function for class datalog.graph.DirectedGraph, taking a map of keywords to field values.
    
    (post-ordered-nodes g)
    Return a sequence of indexes of a post-ordered walk of the graph.
    
    Private
    (post-ordered-visit g n [visited acc :as state])
    Starting at node n, perform a post-ordered walk.
    
    (recursive-component? g ns)
    Is the component (recieved from scc) self recursive?
    
    (remove-loops g)
    For each node n, remove any edges n->n.
    
    (reverse-graph g)
    Given a directed graph, return another directed graph with the
    order of the edges reversed.
    (scc g)
    Returns, as a sequence of sets, the strongly connected components
    of g.
    (self-recursive-sets g)
    Returns, as a sequence of sets, the components of a graph that are
    self-recursive.
    (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.
    (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)