18.03.02 docs





    Mar 1, 2018


    Index of all namespaces

    « Project + dependencies

    Parallel orbit and search algorithms

    Producing actions from binary functions.
    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.
    Computing an orbit exhaustively.
    Partial orbit stopping at first solution.
    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


    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."
      (map (fn [x]
             (remove (partial = x) 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