CrossClj

18.03.02 docs

SourceDocs



RECENT

    orbit

    Clojars

    Mar 1, 2018


    Readme

    Index of all namespaces


    « Project + dependencies

    Parallel orbit and search algorithms

    orbit.actionDocsSource
    Producing actions from binary functions.
    
    orbit.extensionDocsSource
    Strategies for creating new elements (extensions) based on a set and
    an action. General form: taking a collection and an action, returning
    a new set of elements and the unprocessed, in a vector.
    In graph terminology, we find the neighbouring nodes of nodes.
    orbit.full-orbitDocsSource
    Computing an orbit exhaustively.
    
    orbit.partial-orbitDocsSource
    Partial orbit stopping at first solution.
    
    orbit.tree-searchDocsSource
    Finding all solutions when the graph is guaranteed to be circuit free.
    
    The README below is fetched from the published project artifact. Some relative links may be broken.

    Clojars Project Build Status

    orbit

    The library came out from the observation that most problems in computational abstract algebra require a search algorithm. Instead of writing them again and again, it is natural to abstract the search part out. It is used by KIGEN.

    This library contains generic search algorithms. A set-valued operator and predicates for recognizing possible and actual solutions need to be given.

    The abstraction overhead is counterbalanced by parallel execution (using the reducers library).

    Orbit computation example

    For computing al subsets of a set, we define the following set-valued function.

    (defn subset-covers
      "All covering (missing a single element only) subsets of a collection.
      The collection is assumed to be a set."
      [coll]
      (map (fn [x]
             (remove (partial = x) coll))
           coll))
    

    Then we can call a full-orbit function by giving the seeds (a 4-element set in this case) to calculate all subsets.

    (orbit.core/full-orbit [(range 4)] subset-covers)
    #{(0 1 3) (2 3) (0 2 3) (0 1 2) () (3) (1 3) (0) (0 3) (1 2 3) (0 2) (2) (1 2) (1) (0 1 2 3) (0 1)}
    

    Attila Egri-Nagy