graph analysis tools in Common Lisp
Common Lisp
Switch branches/tags
Nothing to show
Latest commit 6483429 Apr 21, 2017 @kraison remove reference to log4cl
Permalink
Failed to load latest commit information.
data misc Mar 10, 2013
LICENSE fix license typo Jun 21, 2011
README Update README Mar 17, 2013
TODO first pas at typed edges Mar 10, 2013
bipartite.lisp sparse matrices Mar 10, 2013
cut.lisp first pass at vertex capacities + max flow for vertex capacities May 27, 2012
edge.lisp misc improvements Jun 30, 2016
edit-distance.lisp begin edit-distance Oct 7, 2015
fib-heap.lisp misc improvements Jun 30, 2016
functor.lisp make it work with ACL; hash tables perhaps no longer thread safe. nee… Mar 7, 2014
graph-class.lisp Add Floyd-Warshall algorithm for all pairs shortest paths Aug 22, 2016
graph-generation.lisp updates to graph generation Jul 30, 2014
graph-methods.lisp remove reference to log4cl Apr 21, 2017
graph-package.lisp Add Floyd-Warshall algorithm for all pairs shortest paths Aug 22, 2016
graph-test.lisp max matching changes May 28, 2012
graph-utils.asd misc improvements Jun 30, 2016
graph-visualization.lisp add visualization for typed graphs Oct 13, 2015
index.lisp misc improvements Jun 30, 2016
maximum-flow.lisp Add Floyd-Warshall algorithm for all pairs shortest paths Aug 22, 2016
node.lisp max flow algorithms. still need optimization, but working May 12, 2012
parsers.lisp first pas at typed edges Mar 10, 2013
prolog-functors.lisp misc improvements Jun 30, 2016
prologc.lisp misc improvements Jun 30, 2016
queue.lisp misc improvements Jun 30, 2016
r-test.lisp make it work with ACL; hash tables perhaps no longer thread safe. nee… Mar 7, 2014
sparse-arrays.lisp make it work with ACL; hash tables perhaps no longer thread safe. nee… Mar 7, 2014
tests.lisp first pas at typed edges Mar 10, 2013
triples.lisp misc improvements Jun 30, 2016
typed-edge-graph-class.lisp Add Floyd-Warshall algorithm for all pairs shortest paths Aug 22, 2016
typed-edge-graph-methods.lisp misc improvements Jun 30, 2016
utilities.lisp misc improvements Jun 30, 2016

README

graph-utils:  a graph analysis library for Common Lisp
by: Kevin Raison
dependencies: cl-ppcre, dso-lex, cl-yacc, trivial-shell, parse-number, bordeaux-threads

Implements the following functionality:

    1.  Create directed and undirected graphs with typed or untyped edges
    2.  Compare graphs using graph= method
    3.  Sparse 2D array representation of adjacency matrix
    4.  Neighbors, outbound-edges and inbound-edges methods for listing a node's neighbors in directed and undirected graphs
    5.  Edge deletion and creation methods
    6.  Functions for mapping over all nodes and edges
    7.  Denisty calculation
    8.  Node degree & degree distribution calculation
    9.  An implementation of Dijkstra's algorithm
    10. Distance map calculation
    11. Methods to find all components in a graph
    12. Graph visualization using the Graphviz library
    13. Random graph generation using the erdos-renyi and barabasi-albert algorithms
    14. Clustering algorithms based on edge betweenness and edge span
    15. Page rank and page rank distribution calculation
    16. Hubs and authorities calculation
    17. Graph center calculator
    18. Maximum flow calculation for directed graphs using The Push-Relabel method, Karzanov's algorithm, Dinic's algorithm, and the Edmond/Karp method
    19. Maximum matching for bipartite graphs using the max-flow method
    20. GML and Pajek .net graph file format parsers
    21. A prolog implementation for searching graphs based on PAIP