clgraph
Graph manipulation utilities for Common Lisp
CLGRAPH
CLGraph is a Common Lisp library for manipulating graphs and running graph algorithms.

GenericFunction
MAKEGRAPH
(graphtype &key &allowotherkeys)Create a new graph of type `graphtype'. Graph type can be a symbol naming a subclass of basicgraph or a list. If it is a list of symbols naming different classes. If graphtype is a list, then a class which has all of the listed classes as superclasses will be found (or created). In either case, the new graph will be created as if with a call to makeinstance. 
GenericFunction
ADDEDGE
(graph edge &rest args &key forcenew?)Addedge adds an existing edge to a graph. As addedgebetweenvertexes is generally more natural to use, this method is rarely called. 
GenericFunction
ADDEDGEBETWEENVERTEXES
(graph valueorvertex1 valueorvertex2 &rest args &key ifduplicatedo edgetype &allowotherkeys)Adds an edge between two vertexes and returns it. If forcenew? is true, the edge is added even if one already exists. If the vertexes are not found in the graph, they will be added (unless :errorifnotfound? is true). The class of the edge can be specified using :edgeclass or :edgetype. If :edgetype is used, it can be either :directed or :undirected; the actual class of the edge will be determined by using the edgetypes of the graph. If neither :edgetype nor :edgeclass is specified, then a directed edge will be created. Ifduplicatedo is used when the 'same' edge is added more than once. It can be either a function on one variable or :ignore or :force. If it is :ignore, then the previously added edge is returned; if it is :force, then another edge is added between the two vertexes; if it is a function, then this function will be called with the previous edge. 
GenericFunction
DELETEEDGE
(graph edge)Delete the `edge' from the `graph' and returns it. 
GenericFunction
DELETEALLEDGES
(graph)Delete all edges from `graph'. Returns the graph.. 
GenericFunction
DELETEEDGEBETWEENVERTEXES
(graph valueorvertex1 valueorvertex2 &rest args)Finds an edge in the graph between the two specified vertexes. If values (i.e., nonvertexes) are passed in, then the graph will be searched for matching vertexes. 
GenericFunction
ADDVERTEX
(graph valueorvertex &key ifduplicatedo &allowotherkeys)Adds a vertex to a graph. If called with a vertex, then this vertex is added. If called with a value, then a new vertex is created to hold the value. Ifduplicatedo can be one of :ignore, :force, :replace, :replacevalue, :error, or a function. The default is :ignore. 
GenericFunction
DELETEVERTEX
(graph valueorvertex)Remove a vertex from a graph. The 'vertexorvalue' argument can be a vertex of the graph or a 'value' that will find a vertex via a call to findvertex. A graphvertexnotfounderror will be raised if the vertex is not found or is not part of the graph. 
GenericFunction
FINDVERTEX
(graph value &optional errorifnotfound?)Search 'graph' for a vertex with element 'value'. The search is fast but inflexible because it uses an associativecontainer. If you need more flexibity, see searchforvertex. 
GenericFunction
SEARCHFORVERTEX
(graph value &key key test errorifnotfound?)Search 'graph' for a vertex with element 'value'. The 'key' function is applied to each element before that element is compared with the value. The comparison is done using the function 'test'. If you don't need to use key or test, then consider using findvertex instead. 
GenericFunction
FINDEDGE
(graph edge &optional errorifnotfound?)Search `graph` for an edge whose vertexes match `edge`. This means that `vertex1` of the edge in the graph must match `vertex1` of `edge` and so forth. Wil signal an error of type `graphedgenotfounderror` unless `errorifnotfound?` is nil. [?? Unused. Remove?] 
GenericFunction
FINDEDGEBETWEENVERTEXES
(graph valueorvertex1 valueorvertex2 &key errorifnotfound?)Searches `graph` for an edge that connects vertex1 and vertex2. [?? Ignores errorifnotfound? Does directedness matter? need test] 
GenericFunction
SOURCEVERTEX
(edge)Returns the sourcevertex of a directed edge. Compare with `vertex1`. 
GenericFunction
TARGETVERTEX
(edge)Returns the targetvertex of a directed edge. Compare with `vertex2`. 
GenericFunction
ITERATEEDGES
(graphorvertex fn)Calls `fn` on each edge of graph or vertex. 
GenericFunction
ITERATESOURCEEDGES
(vertex fn)In a directed graph, calls `fn` on each edge of a vertex that begins at vertex. In an undirected graph, this is equivalent to `iterateedges`. 
GenericFunction
ITERATETARGETEDGES
(vertex fn)In a directed graph, calls `fn` on each edge of a vertex that ends at vertex. In an undirected graph, this is equivalent to `iterateedges`. 
GenericFunction
HASCHILDRENP
(vertex)In a directed graph, returns true if vertex has any edges that point from vertex to some other vertex (cf. iteratesourceedges). In an undirected graph, `haschildrenp` is testing only whether or not the vertex has any edges. 
GenericFunction
HASPARENTP
(vertex)In a directed graph, returns true if vertex has any edges that point from some other vertex to this vertex (cf. iteratetargetedges). In an undirected graph, `hasparentp` is testing only whether or not the vertex has any edges. 
GenericFunction
ITERATEPARENTS
(vertex fn)Calls fn on every vertex that is either connected to vertex by an undirected edge or is at the source end of a directed edge. 
GenericFunction
ITERATENEIGHBORS
(vertex fn)Calls fn on every vertex adjecent to vertex See also iteratechildren and iterateparents. 
GenericFunction
RENUMBERVERTEXES
(graph)Assign a number to each vertex in a graph in some unspecified order. [?? internal] 
GenericFunction
RENUMBEREDGES
(graph)Assign a number to each edge in a graph in some unspecified order. [?? internal] 
GenericFunction
GENERATEDIRECTEDFREETREE
(graph root)Returns a version of graph which is a directed free tree rooted at root. 
GenericFunction
INUNDIRECTEDCYCLEP
(graph startvertex &optional marked previous)Return true ifandonlyif an undirected cycle in graph is reachable from startvertex. 
GenericFunction
UNDIRECTEDEDGEP
(edge)Returns true ifandonlyif edge is undirected 
GenericFunction
DIRECTEDEDGEP
(edge)Returns true ifandonlyif edge is directed 
GenericFunction
TAGGEDEDGEP
(edge)Returns true ifandonlyif edge's tag slot is t 
GenericFunction
UNTAGGEDEDGEP
(edge)Returns true ifandonlyif edge's tage slot is nil 
GenericFunction
ADJACENTP
(graph vertex1 vertex2)Return true if vertex1 and vertex2 are connected by an edge. [?? compare with verticesshareedgep and remove one or maybe call one directedadjacentp] 
GenericFunction
MAKEFILTEREDGRAPH
(oldgraph testfn &key graphcompletionmethod depth newgraph)Takes a GRAPH and a TESTFN (a single argument function returning NIL or nonNIL), and filters the graph nodes according to the testfn (those that return nonNIL are accepted), returning a new graph with only nodes corresponding to those in the original graph that satisfy the test (the nodes in the new graph are new, but their values and name point to the same contents of the original graph). There are four options for how the new graph is filledout, depending on the following keywords passed to the optional GRAPHCOMPLETIONMETHOD argument: * NIL (default) New graph has only nodes that correspond to those in the original graph that pass the test. NO LINKS are reproduced. * :COMPLETELINKS New graph has only nodes that pass, but reproduces corresponding links between passing nodes in the original graph. * :COMPLETECLOSURENODESONLY New graph also includes nodes corresponding to the transitive closure(s) that include the passign nodes in the original graph. NO LINKS are reproduced. * :COMPLETECLOSUREWITHLINKS Same as above, except corresponding links are reproduced. For both transitive closure options, an additional optional argument, DEPTH, specifies how many links away from a source vertex to travel in gathering vertexes of the closure. E.g., a depth of 1 returns the source vertex and the parents and children of that vertex (all vertexes one link away from the source). The default value is NIL, indicating that all vertexes are to be included, no matter their depth. This value is ignored in non closure options. 
GenericFunction
PROJECTBIPARTITEGRAPH
(newgraph existinggraph vertexclass vertexclassifier)Creates the unimodal bipartite projects of existinggraph with vertexes for each vertex of existing graph whose `vertexclassifier` is eq to `vertexclass` and where an edge existing between two vertexes of the graph if and only if they are connected to a shared vertex in the existinggraph. 
GenericFunction
ASSORTATIVITYCOEFFICIENT
(mixingmatrix)An assortative graph is one where vertexes of the same type are more likely to have edges between them. The (discrete) assortativitycoefficient measures how assortative a graph is based on its mixing matrix. The definition we use is from Mixing Patterns in Networks by Mark Newman. See the citation 'newman200mixing' in moab or the URL 'http://arxiv.org/abs/condmat/0209450'. 
GenericFunction
GRAPH>DOT
(graph output &key graphformatter vertexkey vertexlabeler vertexformatter edgelabeler edgeformatter)Generates a description of `graph` in DOT file format. The formatting can be altered using `graph>dotproperties,` `vertex>dot,` and `edge>dot` as well as `edgeformatter,` `vertexformatter,` `vertexlabeler,` and `edgelabeler`. These can be specified directly in the call to `graph>dot` or by creating subclasses of basicgraph, basicvertex and basicedge. The output can be a stream or pathname or one of the values `nil` or `t`. If output is `nil`, then graph>dot returns a string containing the DOT description. If it is `t`, then the DOT description is written to \*standardoutput\*. Here is an example; (let ((g (makecontainer 'graphcontainer :defaultedgetype :directed))) (loop for (a b) in '((a b) (b c) (b d) (d e) (e f) (d f)) do (addedgebetweenvertexes g a b)) (graph>dot g nil)) "digraph G { E [] C [] B [] A [] D [] F [] E>F [] B>C [] B>D [] A>B [] D>E [] D>F [] }" For more information about DOT file format, search the web for 'DOTTY' and 'GRAPHVIZ'. 
GenericFunction
GRAPH>DOTPROPERTIES
(g stream)Unless a different graphformatter is specified, this method is called by graph>dot to output graphproperties onto a stream. The function can assume that the openning and closing brackets will be taken care of by the graph>dot. 
GenericFunction
VERTEX>DOT
(vertex stream)Unless a different vertexformatter is specified with a keyword argument, this is used by graph>dot to output vertex formatting for `vertex` onto the `stream`. The function can assume that openning and closing square brackets and label have already been taken care of. 
GenericFunction
EDGE>DOT
(edge stream)Used by graph>dot to output edge formatting for `edge` onto the `stream`. The function can assume that openning and closing square brackets and label have already been taken care of. 
GenericFunction
MAKEVERTEXFORGRAPH
(graph &key &allowotherkeys)Creates a new vertex for graph `graph`. The keyword arguments include: * vertexclass : specify the class of the vertex * element : specify the `element` of the vertex and any other initialization arguments that make sense for the vertex class. 
GenericFunction
TAGALLEDGES
(thing)Sets the `tag` of all the edges of `thing` to true. [?? why does this exist?] 
GenericFunction
UNTAGALLEDGES
(thing)Sets the `tag` of all the edges of `thing` to nil. [?? why does this exist?] 
GenericFunction
REPLACEVERTEX
(graph old new)Replace vertex `old` in graph `graph` with vertex `new`. The edge structure of the graph is maintained. 
GenericFunction
SOURCEEDGES
(vertex &optional filter)Returns a list of the source edges of `vertex`. I.e., the edges that begin at `vertex`. 
GenericFunction
TARGETEDGES
(vertex &optional filter)Returns a list of the target edges of `vertex`. I.e., the edges that end at `vertex`. 
GenericFunction
CHILDVERTEXES
(vertex &optional filter)Returns a list of the vertexes to which `vertex` is connected by an edge and for which `vertex` is the source vertex. If the connecting edge is undirected, then the vertex is always counted as a source. [?? Could be a defun]. 
GenericFunction
PARENTVERTEXES
(vertex &optional filter)Returns a list of the vertexes to which `vertex` is connected by an edge and for which `vertex` is the target vertex. If the connecting edge is undirected, then the vertex is always counted as a target. [?? Could be a defun]. 
GenericFunction
NEIGHBORVERTEXES
(vertex &optional filter)Returns a list of the vertexes to which `vertex` is connected by an edge disregarding edge direction. In a directed graph, neighborvertexes is the union of parentvertexes and childvertexes. [?? Could be a defun]. 
GenericFunction
NUMBEROFNEIGHBORS
(vertex)Returns the number of neighbors of `vertex` (cf. `neighborvertexes`). [?? could be a defun] 
GenericFunction
INCYCLEP
(graph startvertex)Returns true if `startvertex` is in some cycle in `graph`. This uses childvertexes to generate the vertexes adjacent to a vertex. 
GenericFunction
ITERATEVERTEXES
(thing fn)Calls `fn` on each of the vertexes of `thing`. 
GenericFunction
EDGES
(thing)Returns a list of the edges of `thing`. 
GenericFunction
VERTEXCOUNT
(graph)Returns the number of vertexes in `graph`. [?? could be a defun] 
GenericFunction
VERTEXES
(thing)Returns a list of the vertexes of `thing`. 
GenericFunction
SOURCEEDGECOUNT
(vertex)Returns the number of source edges of vertex (cf. sourceedges). [?? could be a defun] 
GenericFunction
TARGETEDGECOUNT
(vertex)Returns the number of target edges of vertex (cf. targetedges). [?? could be a defun] 
GenericFunction
GRAPHROOTS
(graph)Returns a list of the roots of graph. A root is defined as a vertex with no source edges (i.e., all of the edges are outgoing). (cf. rootp) [?? could be a defun] 
GenericFunction
ROOTP
(vertex)Returns true if `vertex` is a root vertex (i.e., it has no incoming (source) edges). 
GenericFunction
FINDVERTEXIF
(thing predicate &key key)Returns the first vertex in `thing` for which the `predicate` function returns nonnil. If the `key` is supplied, then it is applied to the vertex before the predicate is. 
GenericFunction
FINDEDGEIF
(graph fn &key key)Returns the first edge in `thing` for which the `predicate` function returns nonnil. If the `key` is supplied, then it is applied to the edge before the predicate is. 
GenericFunction
FINDEDGESIF
(thing predicate)Returns a list of edges in `thing` for which the `predicate` returns nonnil. [?? why no key function?] 
GenericFunction
FINDVERTEXESIF
(thing predicate)Returns a list of vertexes in `thing` for which the `predicate` returns nonnil. [?? why no key function?] 
GenericFunction
FORCEUNDIRECTED
(graph)Ensures that the graph is undirected (possibly by calling changeclass on the edges). 
GenericFunction
ANYUNDIRECTEDCYCLEP
(graph)Returns true if there are any undirected cycles in `graph`. 
GenericFunction
EDGECOUNT
(vertex)Returns the number of edges attached to `vertex`. Compare with the more flexible `vertexdegree`. 
GenericFunction
TOPOLOGICALSORT
(graph)Returns a list of vertexes sorted by the depth from the roots of the graph. See also assignlevel and graphroots. 
GenericFunction
DEPTH
(graph)Returns the maximum depth of the vertexes in graph assuming that the roots are of depth 0 and that each edge distance from the roots increments the depth by one. 
GenericFunction
MAKEVERTEXEDGESCONTAINER
(vertex containerclass &rest args)Called during the initialization of a vertex to create the create the container used to store the edges incident to the vertex. The initarg :vertexedgescontainerclass can be used to alter the default container class. 
GenericFunction
OTHERVERTEX
(edge valueorvertex)Assuming that the valueorvertex corresponds to one of the vertexes for `edge`, this method returns the other vertex of `edge`. If the valueorvertex is not part of edge, then an error is signaled. [?? Should create a new condition for this] 
GenericFunction
FINDEDGEBETWEENVERTEXESIF
(graph valueorvertex1 valueorvertex2 fn &key errorifnotfound?)Finds and returns an edge between valueorvertex1 and valueorvertex2 which returns true (as a generalized boolean) when evaluated by `fn`. Unless errorifnotfound? is nil, then a error will be signaled. [?? IS error really signaled? need a test.] 
GenericFunction
VERTICESSHAREEDGEP
(vertex1 vertex2)Return true if vertex1 and vertex2 are connected by an edge. [?? Compare adjacentp] 
GenericFunction
GRAPHEDGEMIXTUREMATRIX
(graph vertexclassifier &key edgeweight)Return the `mixingmatrix` of graph based on the classifier and the edgeweight function. The mixing matrix is a matrix whose runs and columns represent each class of vertex in the graph. The entries of the matrix show the total number of edges between vertexes of the two kinds. [?? Edgeweight is not used; also compare with graphmixturematrix.] 
GenericFunction
GRAPHMIXINGMATRIX
(graph vertexclassifier &key edgeweight)Return the `mixingmatrix` of graph based on the classifier and the edgeweight function. The mixing matrix is a matrix whose runs and columns represent each class of vertex in the graph. The entries of the matrix show the total number of edges between vertexes of the two kinds. [?? Edgeweight is not used; also compare with graphedgemixturematrix.] 
GenericFunction
CONNECTEDCOMPONENTS
(graph)Returns a unionfindcontainer representing the connectedcomponents of `graph`. 
GenericFunction
CONNECTEDCOMPONENTCOUNT
(graph)Returns the number of connectedcomponents of graph. 
GenericFunction
FINDCONNECTEDCOMPONENTS
(graph)Returns a list of subgraphs of `graph` where each subgraph is a different connected component of graph. Compare with connectedcomponents and connectedcomponentcount. 
GenericFunction
MAKEGRAPHFROMVERTEXES
(vertexlist)Create a new graph given a list of vertexes (which are assumed to be from the same graph). The new graph contains all of the vertexes in the list and all of the edges between any vertexes on the list. 
GenericFunction
EDGELESSPBYWEIGHT
(edge1 edge2)Returns true if the weight of edge1 is strictly less than the weight of edge2. 
GenericFunction
MINIMUMSPANNINGTREE
(graph &key edgesorter)Returns a minimum spanning tree of graph if one exists and nil otherwise. 
GenericFunction
CONNECTEDGRAPHP
(graph &key edgesorter)Returns true if graph is a connected graph and nil otherwise. 
GenericFunction
EDGELESSPBYDIRECTION
(edge1 edge2)Returns true if and only if edge1 is undirected and edge2 is directed. 
GenericFunction
OUTEDGEFORVERTEXP
(edge vertex)Returns true if the edge is connected to vertex and is either an undirected edge or a directed edge for which vertex is the source vertex of the edge. 
GenericFunction
DFS
(graph root fn &key outedgesorter) 
GenericFunction
DFSTREEEDGEP
(edge) 
GenericFunction
DFSBACKEDGEP
(edge) 
GenericFunction
DFSEDGETYPE
(edge) 
GenericFunction
SUBGRAPHCONTAINING
(graph vertex &key depth newgraph)Returns a new graph that is a subset of `graph` that contains `vertex` and all of the other vertexes that can be reached from vertex by paths of less than or equal of length `depth`. If depth is not specified, then the entire subgraph reachable from vertex will be returned. [?? Edge weights are always assumed to be one.] 
GenericFunction
(setf DOTATTRIBUTEVALUE)
(value attribute thing) 
GenericFunction
DOTATTRIBUTEVALUE
(attribute thing) 
GenericFunction
GRAPH>DOTEXTERNAL
(graph filename &key type) 
Macro
WITHCHANGINGVERTEX
((vertex) &body body)This is used to maintain consistency when changing the value of vertex elements while iterating over the vertexes... 
Condition
GRAPHERROR
(ERROR
)This is the root condition for errors that occur while running code in CLGraph. 
Condition
EDGEERROR
(GRAPHERROR
)This is the root condition for graph errors that have to do with edges. 
Condition
GRAPHVERTEXNOTFOUNDERROR
(GRAPHERROR
)This condition is signaled when a vertex can not be found in a graph. 
Condition
GRAPHVERTEXNOTFOUNDINEDGEERROR
(EDGEERROR
)This condition is signaled when a vertex can not be found in an edge. 
Condition
GRAPHEDGENOTFOUNDERROR
(GRAPHERROR
)This condition is signaled when an edge cannot be found in a graph. 
Class
BASICVERTEX
(CONTAINERNODEMIXIN
)This is the root class for all vertexes in CLGraph.
DEPTHLEVEL
Accessor:DEPTHLEVEL
 `Depthlevel` is used by some algorithms for bookkeeping. [?? Should be in a mixin]

VERTEXID
Reader:VERTEXID
 `Vertexid` is used internally to keep track of vertexes.

ELEMENT
Accessor:ELEMENT
,VALUE
 The `element` is the value that this vertex represents.

TAG
Accessor:TAG
 The `tag` slot is used by some algorithms to keep track of which vertexes have been visited.

GRAPH
Accessor:GRAPH
 The graph in which this vertex is contained.

COLOR
Accessor:COLOR
 The `color` slot is used by some algorithms for bookkeeping.

RANK
Accessor:RANK
 The `rank` is used by some algorithms for bookkeeping. [?? Should be in a mixin]

PREVIOUSNODE
Accessor:PREVIOUSNODE
 `Previousnode` is used by some algorithms for bookkeeping. [?? Should be in a mixin]

NEXTNODE
Accessor:NEXTNODE
 `Nextnode` is used by some algorithms for bookkeeping. [?? Should be in a mixin]

DISCOVERYTIME
Accessor:DISCOVERYTIME
 `Discoverytime` is used by some algorithms for bookkeeping. [?? Should be in a mixin]

FINISHTIME
Accessor:FINISHTIME
 `Finishtime` is used by some algorithms for bookkeeping. [?? Should be in a mixin]


Class
BASICEDGE
This is the root class for all edges in CLGraph.
EDGEID
Accessor:EDGEID
 The `edgeid` is used internally by CLGraph for bookkeeping.

ELEMENT
Accessor:ELEMENT
,VALUE

TAG
Accessor:TAG
 The `tag` is used by some algorithms for bookkeeping. [?? Should probably be in a mixin]

GRAPH
Reader:GRAPH
 The `graph` of which this edge is a part.

COLOR
Accessor:COLOR
 The `color` is used by some algorithms for bookkeeping. [?? Should probably be in a mixin]


Class
DIRECTEDEDGEMIXIN
This mixin class is used to indicate that an edge is directed.No slots. 
Class
UNDIRECTEDEDGEMIXIN
This mixin class is used to indicate that an edge is undirected.No slots. 
Class
WEIGHTEDEDGEMIXIN
This mixin class adds a `weight` slot to an edge.
WEIGHT
Accessor:WEIGHT
 The value of the weight of this edge. Defaults to 1.0d0


Class
BASICGRAPH
This is the root class for all graphs in CLGraph.
GRAPHVERTEXES
Reader:GRAPHVERTEXES

GRAPHEDGES
Reader:GRAPHEDGES

LARGESTVERTEXID
Reader:LARGESTVERTEXID

LARGESTEDGEID
Reader:LARGESTEDGEID

VERTEXCLASS
Reader:VERTEXCLASS
 The class of the vertexes in the graph. This must extend the baseclass for vertexes of the graph type. E.g., all vertexes of a graphcontainer must extend graphcontainervertex.

DIRECTEDEDGECLASS
Reader:DIRECTEDEDGECLASS
 The class used to create directed edges in the graph. This must extend the baseclass for edges of the graph type and directededgemixin. E.g., the directededgeclass of a graphcontainer must extend graphcontaineredge and directededgemixin.

UNDIRECTEDEDGECLASS
Reader:UNDIRECTEDEDGECLASS
 The class used to create undirected edges in the graph. This must extend the baseclass for edges of the graph type and undirectededgemixin. E.g., all undirected edges of a graphcontainer must extend graphcontaineredge and undirectededgemixin.

CONTAINSDIRECTEDEDGEP
Accessor:CONTAINSDIRECTEDEDGEP
 Returns true if graph contains at least one directed edge. [?? Not sure if this is really kept uptodate.]

CONTAINSUNDIRECTEDEDGEP
Accessor:CONTAINSUNDIRECTEDEDGEP
 Returns true if graph contains at least one undirected edge. [?? Not sure if this is really kept uptodate.]

VERTEXTEST
Reader:VERTEXTEST

VERTEXKEY
Reader:VERTEXKEY

EDGETEST
Reader:EDGETEST

EDGEKEY
Reader:EDGEKEY

DEFAULTEDGETYPE
Reader:DEFAULTEDGETYPE
 The default edge type for the graph. This should be one of :undirected or :directed.

DEFAULTEDGECLASS
Reader:DEFAULTEDGECLASS
 The default edge class for the graph.


Method
ADDVERTEX
((graph basicgraph) (value basicvertex) &key ifduplicatedo) 
Method
MAKEVERTEXFORGRAPH
((graph basicgraph) &rest args &key (vertexclass (vertexclass graph)) &allowotherkeys) 
Method
MAKEGRAPH
((graphtype symbol) &rest args &key &allowotherkeys) 
Method
UNDIRECTEDEDGEP
((edge basicedge)) 
Method
DIRECTEDEDGEP
((edge basicedge)) 
Method
TAGGEDEDGEP
((edge basicedge)) 
Method
UNTAGGEDEDGEP
((edge basicedge)) 
Method
TAGALLEDGES
((graph basicgraph)) 
Method
TAGALLEDGES
((vertex basicvertex)) 
Method
UNTAGALLEDGES
((graph basicgraph)) 
Method
UNTAGALLEDGES
((vertex basicvertex)) 
Method
ADDVERTEX
((graph basicgraph) (value t) &rest args &key (ifduplicatedo :ignore) &allowotherkeys) 
Method
REPLACEVERTEX
((graph basicgraph) (old basicvertex) (new basicvertex)) 
Method
ADDEDGEBETWEENVERTEXES
((graph basicgraph) (value1 t) (value2 t) &rest args &key (ifduplicatedo :ignore) &allowotherkeys) 
Method
ADDEDGEBETWEENVERTEXES
((graph basicgraph) (v1 basicvertex) (v2 basicvertex) &rest args &key (value nil) (ifduplicatedo :ignore) (edgetype (defaultedgetype graph)) (edgeclass (defaultedgeclass graph)) &allowotherkeys) 
Method
FINDEDGEBETWEENVERTEXES
((graph basicgraph) (value1 t) (value2 t) &key (errorifnotfound? t)) 
Method
DELETEEDGEBETWEENVERTEXES
((graph basicgraph) (valueorvertex1 t) (valueorvertex2 t) &rest args) 
Method
DELETEVERTEX
((graph basicgraph) valueorvertex) 
Method
DELETEVERTEX
((graph basicgraph) (vertex basicvertex)) 
Method
DELETEVERTEX
((graph basicgraph) (vertex basicvertex)) 
Method
SOURCEEDGES
((vertex basicvertex) &optional filter) 
Method
TARGETEDGES
((vertex basicvertex) &optional filter) 
Method
CHILDVERTEXES
(vertex &optional filter) 
Method
PARENTVERTEXES
(vertex &optional filter) 
Method
NEIGHBORVERTEXES
(vertex &optional filter) 
Method
ADJACENTP
((graph basicgraph) vertex1 vertex2) 
Method
ADJACENTP
((graph basicgraph) (vertex1 basicvertex) (vertex2 basicvertex)) 
Method
NUMBEROFNEIGHBORS
(vertex) 
Method
INCYCLEP
((graph basicgraph) (vertex t)) 
Method
RENUMBERVERTEXES
((graph basicgraph)) 
Method
RENUMBEREDGES
((graph basicgraph)) 
Method
ADDVERTEX
((graph basicgraph) (vertex basicvertex) &key &allowotherkeys) 
Method
ADDEDGE
((graph basicgraph) (edge basicedge) &key forcenew?) 
Method
FINDVERTEX
((graph basicgraph) (value t) &optional (errorifnotfound? t)) 
Method
FINDVERTEX
((graph basicgraph) (vertex basicvertex) &optional (errorifnotfound? t)) 
Method
FINDVERTEX
((edge basicedge) (value t) &optional (errorifnotfound? t)) 
Method
SEARCHFORVERTEX
((graph basicgraph) (vertex basicvertex) &key (key (vertexkey graph)) (test 'equal) (errorifnotfound? t)) 
Method
SEARCHFORVERTEX
((graph basicgraph) (vertex t) &key (key (vertexkey graph)) (test 'equal) (errorifnotfound? t)) 
Method
ITERATEVERTEXES
((graph basicgraph) fn) 
Method
ITERATEVERTEXES
((edge basicedge) fn) 
Method
EDGES
((graph basicgraph)) 
Method
EDGES
((vertex basicvertex)) 
Method
VERTEXCOUNT
((graph basicgraph)) 
Method
VERTEXES
((graph basicgraph)) 
Method
SOURCEEDGECOUNT
((vertex basicvertex)) 
Method
TARGETEDGECOUNT
((vertex basicvertex)) 
Method
GRAPHROOTS
((graph basicgraph)) 
Method
ROOTP
((vertex basicvertex)) 
Method
FINDVERTEXIF
((graph basicgraph) fn &key key) 
Method
FINDVERTEXIF
((edge basicedge) fn &key key) 
Method
FINDEDGEIF
((graph basicgraph) fn &key key) 
Method
FINDEDGESIF
((graph basicgraph) fn) 
Method
FINDVERTEXESIF
((graph basicgraph) fn) 
Method
GENERATEDIRECTEDFREETREE
((graph basicgraph) root) 
Method
FORCEUNDIRECTED
((graph basicgraph)) 
Method
INCYCLEP
((graph basicgraph) (startvertex basicvertex)) 
Method
INUNDIRECTEDCYCLEP
((graph basicgraph) (current basicvertex) &optional (marked (makecontainer 'simpleassociativecontainer)) (previous nil)) 
Method
ANYUNDIRECTEDCYCLEP
((graph basicgraph)) 
Function
GETTRANSITIVECLOSURE
(vertexlist &optional (depth nil))Given a list of vertices, returns a combined list of all of the nodes in the transitive closure(s) of each of the vertices in the list (without duplicates). Optional DEPTH limits the depth (in _both_ the child and parent directions) to which the closure is gathered; default nil gathers the entire closure(s). 
Method
EDGECOUNT
((graph basicgraph)) 
Method
EDGECOUNT
((vertex basicvertex)) 
Method
TOPOLOGICALSORT
((graph basicgraph)) 
Method
DEPTH
((graph basicgraph)) 
Function
MAPPATHS
(graph startvertex length fn &key (filter (constantly t)))Apply fn to each path that starts at startvertex and is of exactly length length 
Function
MAPSHORTESTPATHS
(graph startvertex depth fn &key (filter (constantly t)))Apply fn to each shortest path starting at `startvertex` of depth `depth`. The `filter` predicate is used to remove vertexes from consideration. 
Method
PROJECTBIPARTITEGRAPH
((newgraph symbol) graph vertexclass vertexclassifier) 
Class
GRAPHCONTAINER
(ITERATABLECONTAINERMIXIN
,NONASSOCIATIVECONTAINERMIXIN
,INITIALCONTENTSMIXIN
,BASICGRAPH
,CONTAINERUSESNODESMIXIN
)A graph container is essentially an adjacency list graph representation [?? The Bad name comes from it being implemented with containers... ugh]
VERTEXPAIR>EDGE
Reader:VERTEXPAIR>EDGE


Class
GRAPHCONTAINEREDGE
(BASICEDGE
)This is the root class for edges in graphcontainers. It adds vertex1 and vertex2 slots.
VERTEX1
Reader:VERTEX1
 `Vertex1` is one of the two vertexes that an edge connects. In a directededge, `vertex1` is also the `sourcevertex`.

VERTEX2
Reader:VERTEX2
 `Vertex2` is one of the two vertexes that an edge connects. In a directed edge, `vertex2` is also the `targetvertex`.


Class
WEIGHTEDEDGE
(WEIGHTEDEDGEMIXIN
,GRAPHCONTAINEREDGE
)A weighted edge is both a weightededgemixin and a graphcontaineredge.No slots. 
Class
WEIGHTEDDIRECTEDEDGE
(WEIGHTEDEDGEMIXIN
,GRAPHCONTAINERDIRECTEDEDGE
)A weighted edge is a weightededgemixin, a directededgemixin, and a graphcontaineredge.No slots. 
Class
WEIGHTEDUNDIRECTEDEDGE
(WEIGHTEDEDGEMIXIN
,GRAPHCONTAINERUNDIRECTEDEDGE
)A weighted undirected edge is a weightededgemixin, an undirectededgemixin, and a graphcontaineredge.No slots. 
Class
GRAPHCONTAINERVERTEX
(BASICVERTEX
)A graph container vertex keeps track of its edges in the the vertexedges slot. The storage for this defaults to a vectorcontainer but can be changed using the vertexedgescontainerclass initarg.
VERTEXEDGES
Reader:VERTEXEDGES


Method
MAKEVERTEXEDGESCONTAINER
((vertex graphcontainervertex) containerclass &rest args) 
Class
GRAPHCONTAINERUNDIRECTEDEDGE
(UNDIRECTEDEDGEMIXIN
,GRAPHCONTAINEREDGE
)A graphcontainerundirectededge is both an undirectededgemixin and a graphcontaineredge.No slots. 
Class
GRAPHCONTAINERDIRECTEDEDGE
(DIRECTEDEDGEMIXIN
,GRAPHCONTAINEREDGE
)A graphcontainerdirectededge is both a directededgemixin and a graphcontaineredge.No slots. 
Method
SOURCEVERTEX
((edge graphcontaineredge)) 
Method
TARGETVERTEX
((edge graphcontaineredge)) 
Method
OTHERVERTEX
((edge graphcontaineredge) (v graphcontainervertex)) 
Method
OTHERVERTEX
((edge graphcontaineredge) (value t)) 
Method
REPLACEVERTEX
((graph graphcontainer) (old basicvertex) (new basicvertex)) 
Method
REPLACEVERTEX
((graph graphcontainer) (old basicvertex) (new basicvertex)) 
Method
FINDEDGEBETWEENVERTEXES
((graph graphcontainer) (vertex1 graphcontainervertex) (vertex2 graphcontainervertex) &key errorifnotfound?) 
Method
FINDEDGEBETWEENVERTEXESIF
((graph graphcontainer) (vertex1 graphcontainervertex) (vertex2 graphcontainervertex) fn &key errorifnotfound?) 
Method
FINDEDGEBETWEENVERTEXESIF
((graph graphcontainer) (value1 t) (value2 t) fn &key errorifnotfound?) 
Method
FINDEDGE
((graph graphcontainer) (edge graphcontaineredge) &optional errorifnotfound?) 
Method
ITERATEEDGES
((graph graphcontainer) fn) 
Method
ITERATEEDGES
((vertex graphcontainervertex) fn) 
Method
ITERATESOURCEEDGES
((vertex graphcontainervertex) fn) 
Method
ITERATETARGETEDGES
((vertex graphcontainervertex) fn) 
Method
ITERATEPARENTS
((vertex graphcontainervertex) fn) 
Method
ITERATENEIGHBORS
((vertex graphcontainervertex) fn) 
Method
VERTEXES
((edge graphcontaineredge)) 
Method
HASCHILDRENP
((vertex graphcontainervertex)) 
Method
HASPARENTP
((vertex graphcontainervertex)) 
Method
VERTICESSHAREEDGEP
((vertex1 graphcontainervertex) (vertex2 graphcontainervertex)) 
Method
EDGECOUNT
((graph graphcontainer)) 
Class
GRAPHMATRIX
(BASICGRAPH
)Stub for matrix based graph. Not implemented.
ADJENCENCYMATRIX
Reader:ADJENCENCYMATRIX


Class
GRAPHMATRIXEDGE
(BASICEDGE
)Stub for matrix based graph. Not implemented.No slots. 
Class
GRAPHMATRIXVERTEX
(BASICVERTEX
)Stub for matrix based graph. Not implemented.No slots. 
Method
CONNECTEDCOMPONENTS
((graph basicgraph)) 
Method
CONNECTEDCOMPONENTCOUNT
((graph basicgraph)) 
Method
FINDCONNECTEDCOMPONENTS
((graph basicgraph)) 
Method
EDGELESSPBYWEIGHT
((e1 basicedge) (e2 basicedge)) 
Method
MINIMUMSPANNINGTREE
((graph basicgraph) &key (edgesorter #'edgelesspbyweight)) 
Method
CONNECTEDGRAPHP
((graph basicgraph) &key (edgesorter 'edgelesspbyweight)) 
Method
EDGELESSPBYDIRECTION
((e1 basicedge) (e2 basicedge)) 
Method
OUTEDGEFORVERTEXP
((edge basicedge) (vertex basicvertex)) 
Method
DFS
((graph basicgraph) (root t) fn &key (outedgesorter #'edgelesspbydirection)) 
Method
DFS
((graph basicgraph) (root basicvertex) fn &key (outedgesorter #'edgelesspbydirection)) 
GenericFunction
ROOTEDDFS
(graph root fn &key outedgesorter)A variant of DFS that does not visit nodes that are unreachable from the ROOT. 
Method
ROOTEDDFS
((graph basicgraph) (root basicvertex) fn &key (outedgesorter #'edgelesspbydirection)) 
Method
ROOTEDDFS
((graph basicgraph) (root basicvertex) fn &key (outedgesorter #'edgelesspbydirection)) 
Method
ROOTEDDFS
((graph basicgraph) (root basicvertex) fn &key (outedgesorter #'edgelesspbydirection)) 
Method
ROOTEDDFS
((graph basicgraph) (root t) fn &key (outedgesorter #'edgelesspbydirection)) 
Method
ROOTEDDFS
((graph basicgraph) (root t) fn &key (outedgesorter #'edgelesspbydirection)) 
Method
ROOTEDDFS
((graph basicgraph) (root t) fn &key (outedgesorter #'edgelesspbydirection)) 
Method
DFSTREEEDGEP
((edge graphcontaineredge)) 
Method
DFSBACKEDGEP
((edge graphcontaineredge)) 
Method
DFSEDGETYPE
((edge graphcontaineredge)) 
Method
GRAPH>DOT
((g basicgraph) (stream stream) &key (graphformatter 'graph>dotproperties) (vertexkey 'vertexid) (vertexlabeler nil) (vertexformatter 'vertex>dot) (edgelabeler 'princ) (edgeformatter 'edge>dot) &allowotherkeys) 
Method
GRAPH>DOT
((g basicgraph) (stream (eql nil)) &rest args &key &allowotherkeys) 
Method
GRAPH>DOT
((g basicgraph) (stream (eql t)) &rest args &key &allowotherkeys) 
Method
GRAPH>DOT
((g basicgraph) (stream string) &rest args &key &allowotherkeys) 
Method
GRAPH>DOT
((g basicgraph) (stream pathname) &rest args &key &allowotherkeys) 
Method
GRAPH>DOTPROPERTIES
((g t) (stream t)) 
Method
VERTEX>DOT
((v basicvertex) (stream stream)) 
Method
EDGE>DOT
((v basicedge) (stream stream)) 
Variable
*DOTGRAPHATTRIBUTES*
'((:size clgraph::coordinate) (:bb clgraph::boundingbox) (:page clgraph::text) (:dpi float) (:ratio (:fill :compress :auto)) (:margin float) (:nodesep float) (:ranksep float) (:ordering (:out)) (:overlap clgraph::text) (:rankdir ("lr" "rl" "bt")) (:pagedir clgraph::text) (:rank (:same :min :max)) (:rotate integer) (:center integer) (:nslimit float) (:mclimit float) (:layers clgraph::text) (:color clgraph::text) (:bgcolor clgraph::text) (:fontname clgraph::text))

Class
DOTATTRIBUTESMIXIN

DOTATTRIBUTES
Accessor:DOTATTRIBUTES


Class
DOTGRAPHMIXIN
(DOTATTRIBUTESMIXIN
)No slots. 
Class
DOTVERTEXMIXIN
(DOTATTRIBUTESMIXIN
)No slots. 
Class
DOTEDGEMIXIN
(DOTATTRIBUTESMIXIN
)No slots. 
Class
DOTGRAPH
(DOTGRAPHMIXIN
,GRAPHCONTAINER
)No slots. 
Class
DOTVERTEX
(DOTVERTEXMIXIN
,GRAPHCONTAINERVERTEX
)No slots. 
Class
DOTEDGE
(DOTEDGEMIXIN
,GRAPHCONTAINEREDGE
)No slots. 
Class
DOTDIRECTEDEDGE
(DOTEDGE
,DIRECTEDEDGEMIXIN
)No slots. 
Method
(setf DOTATTRIBUTEVALUE)
(value (attr symbol) (thing dotattributesmixin)) 
Method
(setf DOTATTRIBUTEVALUE)
(value (attr symbol) (thing dotattributesmixin)) 
Method
DOTATTRIBUTEVALUE
((attr symbol) (thing dotattributesmixin)) 
Method
WIDTHINPIXELS
((thing dotvertexmixin))Return the attribute in pixels assuming 72 dpi 
Method
(setf WIDTHINPIXELS)
(value (thing dotvertexmixin))Set the attribute in pixels assuming 72 dpi 
Method
HEIGHTINPIXELS
((thing dotvertexmixin))Return the attribute in pixels assuming 72 dpi 
Method
(setf HEIGHTINPIXELS)
(value (thing dotvertexmixin))Set the attribute in pixels assuming 72 dpi 
Method
GRAPH>DOTPROPERTIES
((graph dotgraphmixin) (stream t)) 
Method
VERTEX>DOT
((vertex dotvertexmixin) (stream t)) 
Method
EDGE>DOT
((edge dotedgemixin) (stream t)) 
Function
PRINTDOTKEYVALUE
(key value dotattributes stream) 
Method
GRAPH>DOTEXTERNAL
((g basicgraph) filename &rest args &key (type :ps) &allowotherkeys)Generate an external represenation of a graph to a file, by running the program in *dotpath*.
Also exports
METABANG.UTILITIES:TAG
METABANG.UTILITIES:ELEMENT
METABANG.CLCONTAINERS:WEIGHT
METABANG.CLCONTAINERS:ITERATECHILDREN
METABANG.CLCONTAINERS:ITERATECONTAINER