- Notifications
You must be signed in to change notification settings - Fork0
A very simple Graph library.
License
fosskers/simple-graph
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Wow, what a simple graph. Sometimes you just want to add some nodes and edges, and see what it all looks like, right? This library lets you do that. It has no dependencies.
Keep in mind that:
- Nodes are compared via
#'equalp. - All edges are directed.
- Edge weights are not supported.
- Other than a few conveniences, no fancy algorithms are provided.
Written using only standard Common Lisp, so should be portable to all implementations.
When importing, you should probably use a nickname:
(:local-nicknames (:g:simple-graph))
Although the examples below usein-package directly for brevity.
Thegraph itself is just a simple struct with a two Hash Tables:
- Nodes:
node -> T - Edges:
node -> list-of-node
To create one:
(in-package:simple-graph)(make-graph)
As you can see,graph-nodes andgraph-edges can be used to access the struct fields.
To mutably add entries to the graph (hence the!):
(in-package:simple-graph)(let ((g (make-graph))) (add-node! g:a) (add-node! g:b) (add-edge! g:a:b) g)
#S(GRAPH :NODES #<HASH-TABLE :TEST EQUAL :COUNT 2 {1008601393}> :EDGES #<HASH-TABLE :TEST EQUAL :COUNT 1 {1008601433}>)Note that:
add-node!will ignore multiple attempts to add the same node.- Multiple edges can be added between two of the same node.
- Edges between non-existent nodes can be added.
Is some given node a leaf node (i.e. has no outbound edges)?
(in-package:simple-graph)(let ((g (make-graph))) (add-node! g:a) (add-node! g:b) (add-edge! g:a:b) (leaf? g:b))
T
To fetch all the leaves:
(in-package:simple-graph)(let ((g (make-graph))) (add-node! g:a) (add-node! g:b) (add-node! g:c) (add-edge! g:a:b) (add-edge! g:a:c) (leaves g))
(:C :B)
To find all nodes with a directed edge to some given node:
(in-package:simple-graph)(let ((g (make-graph))) (add-node! g:a) (add-node! g:b) (add-node! g:c) (add-node! g:d) (add-edge! g:a:c) (add-edge! g:a:b) (add-edge! g:b:d) (add-edge! g:c:d) (nodes-to g:d))
(:C :B)
All paths that lead to a given node. The result sublists are in reverse order:
(in-package:simple-graph)(let ((g (make-graph))) (add-node! g:a) (add-node! g:b) (add-node! g:c) (add-node! g:d) (add-edge! g:a:c) (add-edge! g:a:b) (add-edge! g:b:d) (add-edge! g:c:d) (paths-to g:d))
((:D :C :A) (:D :B :A))
To yield a new subgraphgraph that starts from a given node (or nodes):
(in-package:simple-graph)(let ((g (make-graph))) (add-node! g:a) (add-node! g:b) (add-node! g:c) (add-node! g:d) (add-node! g:e) (add-edge! g:a:c) (add-edge! g:d:e) (subgraph g:a)))
#S(GRAPH :NODES #<HASH-TABLE :TEST EQUAL :COUNT 2 {1008A4C3A3}> :EDGES #<HASH-TABLE :TEST EQUAL :COUNT 1 {1008A4C443}>)If visualised (seeto-dot below), we would see onlya -> c.
Reverse the direction of all edges.
(in-package:simple-graph)(let ((g (make-graph))) (add-node! g:a) (add-node! g:b) (add-node! g:c) (add-edge! g:a:b) (add-edge! g:a:c) (flip-edges g))
(in-package:simple-graph)(let ((g (make-graph))) (add-node! g"A") (add-node! g"B") (add-node! g"C") (add-node! g"D") (add-node! g"E") (add-node! g"F") (add-edge! g"A""B") (add-edge! g"A""C") (add-edge! g"B""D") (add-edge! g"C""D") (add-edge! g"E""F") (to-dot (subgraph g"A")))
graph { \"A\"; \"C\"; \"D\"; \"B\"; \"A\" -- \"B\"; \"A\" -- \"C\"; \"C\" -- \"D\"; \"B\" -- \"D\";}Similarly, to write a graph’s DOT format directly to a file:
(in-package:simple-graph)(let ((g (make-graph))) (add-node! g"A") (add-node! g"B") (add-node! g"C") (add-node! g"D") (add-edge! g"A""B") (add-edge! g"A""C") (add-edge! g"B""D") (add-edge! g"C""D") (with-open-file (stream#p"deps.dot":direction:output:if-exists:supersede) (to-dot-with-stream gstream)))
Then you can either write it to apng withdot:
cat deps.dot | dot -Tpng -o deps.png
Or visualise it directly withxdot:
xdot deps.dot
About
A very simple Graph library.
Resources
License
Uh oh!
There was an error while loading.Please reload this page.