This library started off as a project for a social network analysis class. It is somewhat simple, but reasonably useful, so I thought I would make it available for others.
The source is available on github: https://github.com/kraison/graph-utils
Author: Kevin Raison, raison@chatsubo.net
License: MIT-License
Dependencies: cl-ppcre, dso-lex, cl-yacc, trivial-shell, parse-number, alexandria, bordeaux-threads
Implements the following functionality:
- Create directed and undirected graphs with a single edge type
- Compare graphs using graph= method
- Bulk-add function for adding lots of nodes and growing the adjacency matrix in one operation, thus speeding up the node addition process quite a bit
- Neighbors, outbound-edges and inbound-edges methods for listing a node's neighbors in directed and undirected graphs
- Edge deletion and creation methods
- Functions for mapping over all nodes and edges
- Denisty calculation
- Node degree & degree distribution calculation
- An implementation of Dijkstra's algorithm
- Distance map calculation
- Methods to find all components in a graph
- Graph visualization using the Graphviz library
- Random graph generation using the two methods specified in our labs
- Clustering algorithms based on edge betweenness and edge span
- Page rank and page rank distribution calculation
- Hubs and authorities calculation
- Graph center calculator
- GML and Pajek .net graph file format parsers
TODO: Get rid of the adjacency matrix and add typed edges.
Mathematics