opening it up with Common Lisp

Favorite weblogs

Lisp Related

Bill Clementson

Finding Lisp

Lemonodor

Lispmeister.com

Planet Lisp

Politics

Orcinus

Talking Points Memo

This Modern World

Working for Change

Other home

Polliblog

Recent Readings

Book review: Darwinia
Reviewed: Friday, August 11, 2006

Summer reading: Spin
Reviewed: Saturday, August 5, 2006

Runner
Reviewed: Tuesday, July 18, 2006

the Omnivoire's Delimma
Reviewed: Wednesday, July 12, 2006

the Golem's Eye
Reviewed: Wednesday, May 31, 2006





tinderbox
 width=

brief note on CL-Graph
Friday, May 26, 2006

Someone rightly mentioned to me that CL-Graph doesn't have much in the way of a high level overview. Tinaa documentation isn't bad for seeing the trees but it doesn't make the forest any easier to navigate. Here, then is a very brief snapshot of CL-Graph from on high:

Structurally, a graph is a container-uses-nodes-mixin. This means that the things you put in the container are wrapped up in some other structure (a node). Examples of containers that use nodes are graph-container, binary-search-tree, heap-container. Examples of containers without nodes are list-container, array-container, basic-queue and so forth. In practice, this means that when you add a thing to a graph, the thing gets wrapped up in a vertex structure. When you do a find-vertex, you get back the vertex structure (not the element you added). For example:

? (add-vertex *graph* 23)
#<23>
:new        ; tells you that this was a new vertex
? (find-vertex *graph* 23)
#<23>     ; the vertex
? (describe *)
#<23>
Class: #<STANDARD-CLASS GRAPH-CONTAINER-VERTEX>
Wrapper: #<CCL::CLASS-WRAPPER GRAPH-CONTAINER-VERTEX #x8686356>
Instance slots
ELEMENT: 23
DEPTH-LEVEL: 0
VERTEX-ID: 0
TAG: NIL
GRAPH: #<GRAPH-CONTAINER [1,0] #x8E0EBD6>
COLOR: NIL
RANK: NIL
PREVIOUS-NODE: NIL
NEXT-NODE: NIL
DISCOVERY-TIME: -1
FINISH-TIME: -1
VERTEX-EDGES: #<VECTOR-CONTAINER 0 #x8E0B3EE>
; No value
? (element (find-vertex *graph* 23)) => 23
23

The main functions for creating and querying graphs are add-vertex / find-vertex / delete-vertex and add-edge-between-vertexes / find-edge-between-vertexes and delete-edge-between-vertexes. Once you have a graph or a vertex, you can map a function over its elements / edges using iterate-elements or iterate-edges. If you want to actually map over the vertexes, you can use iterate-nodes. There are also lots of iteration / collection functions for dealing with the children and parents of vertexes in directed graphs.

Quite a lot of CL-Graph is bound up with different ways of querying, collecting and iterating over the graph structures. It also has some simple graph algorithms (mostly of the summary sort like clustering coefficient, vertex degree, etc.) and it has decent export to DOT and integration with GraphViz. It's main claim to fame is that it does a good deal of bookkeeping to keep track of vertexes and edges so that you can concentrate on using the graph to do your stuff.


|

Home | About | Quotes | Recent | Archives

Copyright -- Gary Warren King, 2004 - 2006