[cl-graph-devel] Re: cl-graph

[Gary King]

Hi Ron,

> I have been trying to use your library, but not with a lot of  
> success (I
> managed to create empty graphs, partly because this is the first  
> useful
> thing I will do with Common Lisp, partly because the documentation
> contains dead links.
>
> http://common-lisp.net/project/cl-graph/documentation/metabang.cl- 
> containers-package/class-graph--container.html
>

Can you tell me where this link originated. The class graph-container  
shouldn't be referenced from the containers package so this is a  
Tinaa bug that I'd like to fix.

> Some remarks about your library: you use vertexes, shouldn't this  
> be vertices?

Well,... both are actually allowed (though vertices is preferred).  
For some reason, I started with vertexes way back when and then  
decided I didn't want to mess with changing it.

> I have already seen the code in the examples directory. Could you give
> me some high-level view on how to use your library (and CL) somewhat
> more effective?

Structurally, a graph-container 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, and so  
forth. In practice, this means that when you add a thing to a graph,  
it 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.

I know that CL-Graph needs more how to and tutorial documentation and  
I'm sorry that I won't have time to do it for a while yet. Please let  
me know any specific questions and I'll do the best I can.

thanks.
-- 
Gary Warren King
metabang.com
http://www.metabang.com/
(413) 210 7511
gwking on #lisp (occasionally)