algotools.algos.graph — org.clojars.vishk/algotools 0.2.0

A set of widely-applicable (and fun!) graph theory algorithms and utilities. This includes algorithms for both unweighted and weighted graphs (where edge-costs are provided) as well as directed and undirected graphs, such as Breadth-First and Depth-First Searches, Shortest-path (Dijkstra), Minimum Spanning Trees, Pathfinding (A*) etc. In contrast with other languages, graphs that are usable by the functions in this namespace can be in flexible and 'natural' formats. Most functions in this namespace work with 'Adjacency-list' graphs that are simply mapping of vertices to sequences of neighbors i.e. a graph like this: {:c (:b), :f (:g), :d (:e), :a (:b), :b (), :g (), :e ()} or a weighted adjaceny-graph such as {:c '([:b 1] [:e 2]), :d '([:e 1]), :a '([:b 2] [:d 1]), :b '([:d 5]), :e '([:b 3]])} At the same time, one could start from as natural a format for unweighted graphs as just a sequences of edges (optionally accompanied by a set of vertices if some vertices are not connected). These edge-lists could be converted to the adjacency graph format or vice-versa using functions provided below. Also see 'Example Usages' indicated in several function documentation below.

-make_adjlist_graph clj

(-make_adjlist_graph graph directed)

-neighbors clj

(-neighbors v g Un parents)

-scc_directed_graph clj

(-scc_directed_graph graph nbrfunc)

bfs clj

(bfs g start & {neighbors-fn :neighbors-fn :or {neighbors-fn neighbors}})

Traverses an adjacency-graph (g) in Breadth-First-Search manner. Supports both directed and undirected graphs. Returns a set of vertices that could not be reached (if any) and a map of the parent of each vtx (the vertex one hop before it). This map can be used with the 'path-to' function elsewhere in this namespace to find the shortest path to any specific vertex from the start-vertex. You can optionally pass in a function to determine valid neighbors of each vertex during the search; otherwise 'neighbors' is used as the default neighbor-fn.

Example Usage: (bfs {:g '(:f :e), :c '(:b :e), :f '(:g :e :d), :d '(:e :f :b :a), :a '(:b :d), :b '(:d :c :a :e), :e '(:b :f :g :d :c) } :c) => {:unvisited #{}, :parents {:c nil, :b :c, :e :c, :d :b, :a :b, :f :e, :g :e}}

cc-undirected-graph clj

(cc-undirected-graph g
                     &
                     {neighbors-fn :neighbors-fn :or {neighbors-fn neighbors}})

Returns sets of connected components for an UNDIRECTED graph. For directed graphs, use scc-directed-graph.

debug clj

dfs clj

(dfs g start & {neighbors-fn :neighbors-fn :or {neighbors-fn neighbors}})

Given an adjacency graph (g) and a start-vertex(node) traverses the graph in Depth-First-Search manner and returns a map comprising the following triad :

• Unvisited-vertices (vertices that were unreachable)
• Traversed Vertices in decreasing order of Finish-times (the last vertex was the first terminal point in the Depth-first search, the penultimate the second terminal point and so on).
• Map of each vertex to its Parent (vertex one hop before it). This map can be used to retrieve the depth-first-traversed-path to any vertex by using the 'path-to' function available in this namespace. You can optionally pass in a function to determine valid neighbors of each vertex during the search; otherwise 'neighbors' is used as the default neighbor-fn. Example Usage: (dfs {:c '(:b :e), :f '(:g), :d '(:e :f), :a '(:b :d), :b '(:d), :e '(:b :f :g) :g '()} :c :neighbor-fn neighbors) => {:unvisited #{:a}, :reverse-finish-order (:c :b :d :e :f :g), :parents {:g :f, :f :e, :e :d, :d :b, :b :c, :c nil}}

get-edge-graph clj

(get-edge-graph adjacencies directed)

Given a graph in adjacency-list format (map of vertices to neighbor-vertices), returns the set of all edges in the graph. The edge-set returned from this function plus optionally the set of vertices (in case any vertices have zero incident edges) is a succinct description of the graph that can be used with some graph functions in this package. Example Usage: (get-edge-graph {:g '(:f :e), :c '(:b :e), :f '(:g :e :d)} false)
=> #{[:c :b] [:f :g] [:f :d] [:g :e] [:f :e] [:c :e]}

get-wtd-edge-graph clj

(get-wtd-edge-graph adjacencies directed)

Given a weighted-graph in adjacency-list format (map of vertices to neighbor-vertices with weights for connections), returns a graph in form of a map of all edges and their respective weights. The edge-set returned from this function plus optionally the set of vertices (in case any vertices have zero incident edges) is a succinct description of the graph that can be used with some graph functions in this package.

make-adjlist-graph clj

(make-adjlist-graph edges
                    directed?
                    &
                    {vertices :vertices
                     :or {vertices (set (flatten (seq edges)))}})

Given a graph described by a sequence of edges, a directed? flag (true/false) and optionally a Set of vertices (in case some vertices have no incident edges), returns graph in adjacency list format (map of vertices to connected-neighbors). Example Usage: (make-adjlist-graph [[:c :b] [:f :g] [:d :e] [:a :b]] true ) => {:c (:b), :f (:g), :d (:e), :a (:b), :b (), :g (), :e ()}

make-wtd-adjlist-graph clj

(make-wtd-adjlist-graph wtd-edges
                        directed?
                        &
                        {vertices :vertices
                         :or {vertices (set (flatten (keys wtd-edges)))}})

Given a graph described by a map of edges and weights, a directed? flag (true/false) and optionally a Set of vertices (in case some vertices have no incident edges), returns graph in adjacency list format (map of vertices to connected-neighbors). Example Usage: (make-wtd-adjlist-graph {[:a :b] 4, [:c :e] 3, [:a :c] 1, [:a :d] 5} true) => {:a ([:c 1] [:b 4] [:d 5]), :c ([:e 3]), :b (), :d (), :e ()}

MST-kruskal clj

(MST-kruskal g directed?)

Minimum Spanning Tree by Kruskal's algorithm, given an adjacency graph with edge-costs.

MST-prim clj

(MST-prim g start & {V :vertices :or {V (set (flatten (keys g)))}})

Efficient implementation of Prim's algorithm to retrieve the Minimum Spanning Tree for a adjacency-graph with edge-costs. The MST-edges, Total-cost of MST-edges and the parent-pointers are returned. The last can be used with the path-to function to retrace the path to a vertex from the start.

neighbors clj

(neighbors v g Un parents)

(neighbors v g Un parents exclude)

Given an adjacency-graph (map of adjacent vertices to each vertex), returns the list of neighbor-vertices of v so long as they are in the set of vertices (Un) provided as the third argument. If an additional argument :exclude is provided, then the behavior of Un is reversed i.e. neighbors are returned if they are not in Un (excluded from Un).

path-to clj

(path-to v parent-map)

Get path to any vtx from start vertex used to generate the parent-map (typically returned by bfs/dfs). The parent-map must not end in a loop i.e. a vertex pointing to itself.

pathfind-astar clj

(pathfind-astar G
                start
                goal
                &
                {h :est-func
                 M :max
                 :or {h (fn [a b]
                            (Math/sqrt
                              (reduce +
                                      (map (fn* [p1__677# p2__678#]
                                                (let [d (- p1__677# p2__678#)]
                                                     (* d d)))
                                           a
                                           b))))
                      M Double/MAX_VALUE}})

Returns a path to be traversed in a grid of points (for example a maze) using the A* algorithm. Takes G (a vector of vectors representing the grid of points), a start and a goal (2-D vectors). An estimation-func (h) of 2 args(2-D vectors) may be optionally passed in using the key :est-func (default is euclidean dist to goal). Any points that are never to be in path may be checked using a high-value indicated via optional arg :max, else Double/MAX_VALUE will be used as default. Example Usage: (pathfind-astar [[1 1 1] [99 99 1] [1 1 1]] [0 0] [2 0] :max 100 ) => ([0 0] [0 1] [0 2] [1 2] [2 2] [2 1] [2 0])

reverse-graph clj

(reverse-graph g)

Reverse a directed adjacency graph. Example Usage: (reverse-graph {:c '(:b :e), :f '(:g), :d '(:e :f), :a '(:b :d)}) => {:f [:d], :g [:f], :e (:c :d), :d [:a], :b (:a :c)}

reverse-wtd-graph clj

(reverse-wtd-graph g)

Reverse a directed adjacency graph. Example Usage: (reverse-wtd-graph {:c '([:b 1] [:e 2]), :a '([:b 3] [:d 4]), :d '([:e 6] [:f 5]), :f '([:g 7])}) => {:f '([:d 5]), :g '([:f 7]), :e '([:c 2] [:d 6]), :d '([:a 4]), :b '([:a 3] [:c 1])}

scc-directed-graph clj

(scc-directed-graph g
                    &
                    {neighbors-fn :neighbors-fn :or {neighbors-fn neighbors}})

Returns a Set containing sequences of strongly connected components for a directed adjacency graph.

shortest-path-dijk clj

(shortest-path-dijk g
                    start
                    &
                    {goal :goal V :vertices :or {goal nil V (set (keys g))}})

Efficient Dijkstra Implementation for a adjacency-graph with edge-costs. A goal vtx can be optionally indicated in which case a path to that vtx will be returned. Otherwise costs to each vtx and parent-ptrs are returned. The latter can be used with the path-to function to retrieve the shortest path to a vertex from the start.

to-unweighted-graph clj

(to-unweighted-graph wtd-g)

Given a weighted graph, drop edge-weights to make an unweighted one.

topological-sort clj

(topological-sort g)

Given a DIRECTED ACYCLIC adjacency-graph, finds the ordering in which each vertex should be processed. It is assumed that the direction of each edge [u,v] indicates that u must be processed before v (for example u and v may be modeling scheduling dependencies). Do not use with UNDIRECTED graphs.

wtd-neighbors clj

(wtd-neighbors v g Un)

(wtd-neighbors v g Un exclude)

Given a weighted adjacency-graph (map of vertices to neighbor-vertices with weights for connections), returns the list of neighbor-vertices of v with edge-weights, so long as they are in the set of vertices (Un) provided as the third argument. If an additional argument :exclude is provided, then the behavior of Un is reversed i.e. neighbors are returned if they are not in Un (excluded from Un).