graph-utils

graph-utils copied to clipboard

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, cl-skip-list

Implements the following functionality:

1.  Create directed and undirected graphs with typed or untyped edges
2.  Compare graphs using graph-equal 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