cl-graph

API Reference

cl-graph

Graph manipulation utilities for Common Lisp

CL-GRAPH

CL-Graph is a Common Lisp library for manipulating graphs and running graph algorithms.
  • Generic-Function MAKE-GRAPH (graph-type &key &allow-other-keys)
    Create a new graph of type `graph-type'. Graph type can be a symbol naming a sub-class of basic-graph or a list. If it is a list of symbols naming different classes. If graph-type 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 make-instance.
  • Generic-Function ADD-EDGE (graph edge &rest args &key force-new?)
    Add-edge adds an existing edge to a graph. As add-edge-between-vertexes is generally more natural to use, this method is rarely called.
  • Generic-Function ADD-EDGE-BETWEEN-VERTEXES (graph value-or-vertex-1 value-or-vertex-2 &rest args &key if-duplicate-do edge-type &allow-other-keys)
    Adds an edge between two vertexes and returns it. If force-new? 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 :error-if-not-found? is true). The class of the edge can be specified using :edge-class or :edge-type. If :edge-type is used, it can be either :directed or :undirected; the actual class of the edge will be determined by using the edge-types of the graph. If neither :edge-type nor :edge-class is specified, then a directed edge will be created. If-duplicate-do 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.
  • Generic-Function DELETE-EDGE (graph edge)
    Delete the `edge' from the `graph' and returns it.
  • Generic-Function DELETE-ALL-EDGES (graph)
    Delete all edges from `graph'. Returns the graph..
  • Generic-Function DELETE-EDGE-BETWEEN-VERTEXES (graph value-or-vertex-1 value-or-vertex-2 &rest args)
    Finds an edge in the graph between the two specified vertexes. If values (i.e., non-vertexes) are passed in, then the graph will be searched for matching vertexes.
  • Generic-Function ADD-VERTEX (graph value-or-vertex &key if-duplicate-do &allow-other-keys)
    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. If-duplicate-do can be one of :ignore, :force, :replace, :replace-value, :error, or a function. The default is :ignore.
  • Generic-Function DELETE-VERTEX (graph value-or-vertex)
    Remove a vertex from a graph. The 'vertex-or-value' argument can be a vertex of the graph or a 'value' that will find a vertex via a call to find-vertex. A graph-vertex-not-found-error will be raised if the vertex is not found or is not part of the graph.
  • Generic-Function FIND-VERTEX (graph value &optional error-if-not-found?)
    Search 'graph' for a vertex with element 'value'. The search is fast but inflexible because it uses an associative-container. If you need more flexibity, see search-for-vertex.
  • Generic-Function SEARCH-FOR-VERTEX (graph value &key key test error-if-not-found?)
    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 find-vertex instead.
  • Generic-Function FIND-EDGE (graph edge &optional error-if-not-found?)
    Search `graph` for an edge whose vertexes match `edge`. This means that `vertex-1` of the edge in the graph must match `vertex-1` of `edge` and so forth. Wil signal an error of type `graph-edge-not-found-error` unless `error-if-not-found?` is nil. [?? Unused. Remove?]
  • Generic-Function FIND-EDGE-BETWEEN-VERTEXES (graph value-or-vertex-1 value-or-vertex-2 &key error-if-not-found?)
    Searches `graph` for an edge that connects vertex-1 and vertex-2. [?? Ignores error-if-not-found? Does directedness matter? need test]
  • Generic-Function SOURCE-VERTEX (edge)
    Returns the source-vertex of a directed edge. Compare with `vertex-1`.
  • Generic-Function TARGET-VERTEX (edge)
    Returns the target-vertex of a directed edge. Compare with `vertex-2`.
  • Generic-Function ITERATE-EDGES (graph-or-vertex fn)
    Calls `fn` on each edge of graph or vertex.
  • Generic-Function ITERATE-SOURCE-EDGES (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 `iterate-edges`.
  • Generic-Function ITERATE-TARGET-EDGES (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 `iterate-edges`.
  • Generic-Function HAS-CHILDREN-P (vertex)
    In a directed graph, returns true if vertex has any edges that point from vertex to some other vertex (cf. iterate-source-edges). In an undirected graph, `has-children-p` is testing only whether or not the vertex has any edges.
  • Generic-Function HAS-PARENT-P (vertex)
    In a directed graph, returns true if vertex has any edges that point from some other vertex to this vertex (cf. iterate-target-edges). In an undirected graph, `has-parent-p` is testing only whether or not the vertex has any edges.
  • Generic-Function ITERATE-PARENTS (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.
  • Generic-Function ITERATE-NEIGHBORS (vertex fn)
    Calls fn on every vertex adjecent to vertex See also iterate-children and iterate-parents.
  • Generic-Function RENUMBER-VERTEXES (graph)
    Assign a number to each vertex in a graph in some unspecified order. [?? internal]
  • Generic-Function RENUMBER-EDGES (graph)
    Assign a number to each edge in a graph in some unspecified order. [?? internal]
  • Generic-Function GENERATE-DIRECTED-FREE-TREE (graph root)
    Returns a version of graph which is a directed free tree rooted at root.
  • Generic-Function IN-UNDIRECTED-CYCLE-P (graph start-vertex &optional marked previous)
    Return true if-and-only-if an undirected cycle in graph is reachable from start-vertex.
  • Generic-Function UNDIRECTED-EDGE-P (edge)
    Returns true if-and-only-if edge is undirected
  • Generic-Function DIRECTED-EDGE-P (edge)
    Returns true if-and-only-if edge is directed
  • Generic-Function TAGGED-EDGE-P (edge)
    Returns true if-and-only-if edge's tag slot is t
  • Generic-Function UNTAGGED-EDGE-P (edge)
    Returns true if-and-only-if edge's tage slot is nil
  • Generic-Function ADJACENTP (graph vertex-1 vertex-2)
    Return true if vertex-1 and vertex-2 are connected by an edge. [?? compare with vertices-share-edge-p and remove one or maybe call one directed-adjacentp]
  • Generic-Function MAKE-FILTERED-GRAPH (old-graph test-fn &key graph-completion-method depth new-graph)
    Takes a GRAPH and a TEST-FN (a single argument function returning NIL or non-NIL), and filters the graph nodes according to the test-fn (those that return non-NIL 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 filled-out, depending on the following keywords passed to the optional GRAPH-COMPLETION-METHOD argument: * NIL (default) New graph has only nodes that correspond to those in the original graph that pass the test. NO LINKS are reproduced. * :COMPLETE-LINKS New graph has only nodes that pass, but reproduces corresponding links between passing nodes in the original graph. * :COMPLETE-CLOSURE-NODES-ONLY New graph also includes nodes corresponding to the transitive closure(s) that include the passign nodes in the original graph. NO LINKS are reproduced. * :COMPLETE-CLOSURE-WITH-LINKS 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.
  • Generic-Function PROJECT-BIPARTITE-GRAPH (new-graph existing-graph vertex-class vertex-classifier)
    Creates the unimodal bipartite projects of existing-graph with vertexes for each vertex of existing graph whose `vertex-classifier` is eq to `vertex-class` and where an edge existing between two vertexes of the graph if and only if they are connected to a shared vertex in the existing-graph.
  • Generic-Function ASSORTATIVITY-COEFFICIENT (mixing-matrix)
    An assortative graph is one where vertexes of the same type are more likely to have edges between them. The (discrete) assortativity-coefficient 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 'newman200-mixing' in moab or the URL 'http://arxiv.org/abs/cond-mat/0209450'.
  • Generic-Function GRAPH->DOT (graph output &key graph-formatter vertex-key vertex-labeler vertex-formatter edge-labeler edge-formatter)
    Generates a description of `graph` in DOT file format. The formatting can be altered using `graph->dot-properties,` `vertex->dot,` and `edge->dot` as well as `edge-formatter,` `vertex-formatter,` `vertex-labeler,` and `edge-labeler`. These can be specified directly in the call to `graph->dot` or by creating subclasses of basic-graph, basic-vertex and basic-edge. 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 \*standard-output\*. Here is an example; (let ((g (make-container 'graph-container :default-edge-type :directed))) (loop for (a b) in '((a b) (b c) (b d) (d e) (e f) (d f)) do (add-edge-between-vertexes 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'.
  • Generic-Function GRAPH->DOT-PROPERTIES (g stream)
    Unless a different graph-formatter is specified, this method is called by graph->dot to output graph-properties onto a stream. The function can assume that the openning and closing brackets will be taken care of by the graph->dot.
  • Generic-Function VERTEX->DOT (vertex stream)
    Unless a different vertex-formatter 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.
  • Generic-Function 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.
  • Generic-Function MAKE-VERTEX-FOR-GRAPH (graph &key &allow-other-keys)
    Creates a new vertex for graph `graph`. The keyword arguments include: * vertex-class : 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.
  • Generic-Function TAG-ALL-EDGES (thing)
    Sets the `tag` of all the edges of `thing` to true. [?? why does this exist?]
  • Generic-Function UNTAG-ALL-EDGES (thing)
    Sets the `tag` of all the edges of `thing` to nil. [?? why does this exist?]
  • Generic-Function REPLACE-VERTEX (graph old new)
    Replace vertex `old` in graph `graph` with vertex `new`. The edge structure of the graph is maintained.
  • Generic-Function SOURCE-EDGES (vertex &optional filter)
    Returns a list of the source edges of `vertex`. I.e., the edges that begin at `vertex`.
  • Generic-Function TARGET-EDGES (vertex &optional filter)
    Returns a list of the target edges of `vertex`. I.e., the edges that end at `vertex`.
  • Generic-Function CHILD-VERTEXES (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].
  • Generic-Function PARENT-VERTEXES (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].
  • Generic-Function NEIGHBOR-VERTEXES (vertex &optional filter)
    Returns a list of the vertexes to which `vertex` is connected by an edge disregarding edge direction. In a directed graph, neighbor-vertexes is the union of parent-vertexes and child-vertexes. [?? Could be a defun].
  • Generic-Function NUMBER-OF-NEIGHBORS (vertex)
    Returns the number of neighbors of `vertex` (cf. `neighbor-vertexes`). [?? could be a defun]
  • Generic-Function IN-CYCLE-P (graph start-vertex)
    Returns true if `start-vertex` is in some cycle in `graph`. This uses child-vertexes to generate the vertexes adjacent to a vertex.
  • Generic-Function ITERATE-VERTEXES (thing fn)
    Calls `fn` on each of the vertexes of `thing`.
  • Generic-Function EDGES (thing)
    Returns a list of the edges of `thing`.
  • Generic-Function VERTEX-COUNT (graph)
    Returns the number of vertexes in `graph`. [?? could be a defun]
  • Generic-Function VERTEXES (thing)
    Returns a list of the vertexes of `thing`.
  • Generic-Function SOURCE-EDGE-COUNT (vertex)
    Returns the number of source edges of vertex (cf. source-edges). [?? could be a defun]
  • Generic-Function TARGET-EDGE-COUNT (vertex)
    Returns the number of target edges of vertex (cf. target-edges). [?? could be a defun]
  • Generic-Function GRAPH-ROOTS (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 out-going). (cf. rootp) [?? could be a defun]
  • Generic-Function ROOTP (vertex)
    Returns true if `vertex` is a root vertex (i.e., it has no incoming (source) edges).
  • Generic-Function FIND-VERTEX-IF (thing predicate &key key)
    Returns the first vertex in `thing` for which the `predicate` function returns non-nil. If the `key` is supplied, then it is applied to the vertex before the predicate is.
  • Generic-Function FIND-EDGE-IF (graph fn &key key)
    Returns the first edge in `thing` for which the `predicate` function returns non-nil. If the `key` is supplied, then it is applied to the edge before the predicate is.
  • Generic-Function FIND-EDGES-IF (thing predicate)
    Returns a list of edges in `thing` for which the `predicate` returns non-nil. [?? why no key function?]
  • Generic-Function FIND-VERTEXES-IF (thing predicate)
    Returns a list of vertexes in `thing` for which the `predicate` returns non-nil. [?? why no key function?]
  • Generic-Function FORCE-UNDIRECTED (graph)
    Ensures that the graph is undirected (possibly by calling change-class on the edges).
  • Generic-Function ANY-UNDIRECTED-CYCLE-P (graph)
    Returns true if there are any undirected cycles in `graph`.
  • Generic-Function EDGE-COUNT (vertex)
    Returns the number of edges attached to `vertex`. Compare with the more flexible `vertex-degree`.
  • Generic-Function TOPOLOGICAL-SORT (graph)
    Returns a list of vertexes sorted by the depth from the roots of the graph. See also assign-level and graph-roots.
  • Generic-Function 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.
  • Generic-Function MAKE-VERTEX-EDGES-CONTAINER (vertex container-class &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 :vertex-edges-container-class can be used to alter the default container class.
  • Generic-Function OTHER-VERTEX (edge value-or-vertex)
    Assuming that the value-or-vertex corresponds to one of the vertexes for `edge`, this method returns the other vertex of `edge`. If the value-or-vertex is not part of edge, then an error is signaled. [?? Should create a new condition for this]
  • Generic-Function FIND-EDGE-BETWEEN-VERTEXES-IF (graph value-or-vertex-1 value-or-vertex-2 fn &key error-if-not-found?)
    Finds and returns an edge between value-or-vertex-1 and value-or-vertex-2 which returns true (as a generalized boolean) when evaluated by `fn`. Unless error-if-not-found? is nil, then a error will be signaled. [?? IS error really signaled? need a test.]
  • Generic-Function VERTICES-SHARE-EDGE-P (vertex-1 vertex-2)
    Return true if vertex-1 and vertex-2 are connected by an edge. [?? Compare adjacentp]
  • Generic-Function GRAPH-EDGE-MIXTURE-MATRIX (graph vertex-classifier &key edge-weight)
    Return the `mixing-matrix` of graph based on the classifier and the edge-weight 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. [?? Edge-weight is not used; also compare with graph-mixture-matrix.]
  • Generic-Function GRAPH-MIXING-MATRIX (graph vertex-classifier &key edge-weight)
    Return the `mixing-matrix` of graph based on the classifier and the edge-weight 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. [?? Edge-weight is not used; also compare with graph-edge-mixture-matrix.]
  • Generic-Function CONNECTED-COMPONENTS (graph)
    Returns a union-find-container representing the connected-components of `graph`.
  • Generic-Function CONNECTED-COMPONENT-COUNT (graph)
    Returns the number of connected-components of graph.
  • Generic-Function FIND-CONNECTED-COMPONENTS (graph)
    Returns a list of sub-graphs of `graph` where each sub-graph is a different connected component of graph. Compare with connected-components and connected-component-count.
  • Generic-Function MAKE-GRAPH-FROM-VERTEXES (vertex-list)
    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.
  • Generic-Function EDGE-LESSP-BY-WEIGHT (edge-1 edge-2)
    Returns true if the weight of edge-1 is strictly less than the weight of edge-2.
  • Generic-Function MINIMUM-SPANNING-TREE (graph &key edge-sorter)
    Returns a minimum spanning tree of graph if one exists and nil otherwise.
  • Generic-Function CONNECTED-GRAPH-P (graph &key edge-sorter)
    Returns true if graph is a connected graph and nil otherwise.
  • Generic-Function EDGE-LESSP-BY-DIRECTION (edge-1 edge-2)
    Returns true if and only if edge-1 is undirected and edge-2 is directed.
  • Generic-Function OUT-EDGE-FOR-VERTEX-P (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.
  • Generic-Function DFS (graph root fn &key out-edge-sorter)
  • Generic-Function DFS-TREE-EDGE-P (edge)
  • Generic-Function DFS-BACK-EDGE-P (edge)
  • Generic-Function DFS-EDGE-TYPE (edge)
  • Generic-Function SUBGRAPH-CONTAINING (graph vertex &key depth new-graph)
    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 sub-graph reachable from vertex will be returned. [?? Edge weights are always assumed to be one.]
  • Generic-Function (setf DOT-ATTRIBUTE-VALUE) (value attribute thing)
  • Generic-Function DOT-ATTRIBUTE-VALUE (attribute thing)
  • Generic-Function GRAPH->DOT-EXTERNAL (graph file-name &key type)
  • Macro WITH-CHANGING-VERTEX ((vertex) &body body)
    This is used to maintain consistency when changing the value of vertex elements while iterating over the vertexes...
  • Condition GRAPH-ERROR  (ERROR)
    This is the root condition for errors that occur while running code in CL-Graph.
  • Condition EDGE-ERROR  (GRAPH-ERROR)
    This is the root condition for graph errors that have to do with edges.
  • Condition GRAPH-VERTEX-NOT-FOUND-ERROR  (GRAPH-ERROR)
    This condition is signaled when a vertex can not be found in a graph.
  • Condition GRAPH-VERTEX-NOT-FOUND-IN-EDGE-ERROR  (EDGE-ERROR)
    This condition is signaled when a vertex can not be found in an edge.
  • Condition GRAPH-EDGE-NOT-FOUND-ERROR  (GRAPH-ERROR)
    This condition is signaled when an edge cannot be found in a graph.
  • Class BASIC-VERTEX  (CONTAINER-NODE-MIXIN)
    This is the root class for all vertexes in CL-Graph.
    DEPTH-LEVEL   Accessor: DEPTH-LEVEL
    `Depth-level` is used by some algorithms for bookkeeping. [?? Should be in a mixin]
    VERTEX-ID   Reader: VERTEX-ID
    `Vertex-id` 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]
    PREVIOUS-NODE   Accessor: PREVIOUS-NODE
    `Previous-node` is used by some algorithms for bookkeeping. [?? Should be in a mixin]
    NEXT-NODE   Accessor: NEXT-NODE
    `Next-node` is used by some algorithms for bookkeeping. [?? Should be in a mixin]
    DISCOVERY-TIME   Accessor: DISCOVERY-TIME
    `Discovery-time` is used by some algorithms for bookkeeping. [?? Should be in a mixin]
    FINISH-TIME   Accessor: FINISH-TIME
    `Finish-time` is used by some algorithms for bookkeeping. [?? Should be in a mixin]
  • Class BASIC-EDGE
    This is the root class for all edges in CL-Graph.
    EDGE-ID   Accessor: EDGE-ID
    The `edge-id` is used internally by CL-Graph 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 DIRECTED-EDGE-MIXIN
    This mixin class is used to indicate that an edge is directed.
    No slots.
  • Class UNDIRECTED-EDGE-MIXIN
    This mixin class is used to indicate that an edge is undirected.
    No slots.
  • Class WEIGHTED-EDGE-MIXIN
    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 BASIC-GRAPH
    This is the root class for all graphs in CL-Graph.
    GRAPH-VERTEXES   Reader: GRAPH-VERTEXES
    GRAPH-EDGES   Reader: GRAPH-EDGES
    LARGEST-VERTEX-ID   Reader: LARGEST-VERTEX-ID
    LARGEST-EDGE-ID   Reader: LARGEST-EDGE-ID
    VERTEX-CLASS   Reader: VERTEX-CLASS
    The class of the vertexes in the graph. This must extend the base-class for vertexes of the graph type. E.g., all vertexes of a graph-container must extend graph-container-vertex.
    DIRECTED-EDGE-CLASS   Reader: DIRECTED-EDGE-CLASS
    The class used to create directed edges in the graph. This must extend the base-class for edges of the graph type and directed-edge-mixin. E.g., the directed-edge-class of a graph-container must extend graph-container-edge and directed-edge-mixin.
    UNDIRECTED-EDGE-CLASS   Reader: UNDIRECTED-EDGE-CLASS
    The class used to create undirected edges in the graph. This must extend the base-class for edges of the graph type and undirected-edge-mixin. E.g., all undirected edges of a graph-container must extend graph-container-edge and undirected-edge-mixin.
    CONTAINS-DIRECTED-EDGE-P   Accessor: CONTAINS-DIRECTED-EDGE-P
    Returns true if graph contains at least one directed edge. [?? Not sure if this is really kept up-to-date.]
    CONTAINS-UNDIRECTED-EDGE-P   Accessor: CONTAINS-UNDIRECTED-EDGE-P
    Returns true if graph contains at least one undirected edge. [?? Not sure if this is really kept up-to-date.]
    VERTEX-TEST   Reader: VERTEX-TEST
    VERTEX-KEY   Reader: VERTEX-KEY
    EDGE-TEST   Reader: EDGE-TEST
    EDGE-KEY   Reader: EDGE-KEY
    DEFAULT-EDGE-TYPE   Reader: DEFAULT-EDGE-TYPE
    The default edge type for the graph. This should be one of :undirected or :directed.
    DEFAULT-EDGE-CLASS   Reader: DEFAULT-EDGE-CLASS
    The default edge class for the graph.
  • Method ADD-VERTEX ((graph basic-graph) (value basic-vertex) &key if-duplicate-do)
  • Method MAKE-VERTEX-FOR-GRAPH ((graph basic-graph) &rest args &key (vertex-class (vertex-class graph)) &allow-other-keys)
  • Method MAKE-GRAPH ((graph-type symbol) &rest args &key &allow-other-keys)
  • Method UNDIRECTED-EDGE-P ((edge basic-edge))
  • Method DIRECTED-EDGE-P ((edge basic-edge))
  • Method TAGGED-EDGE-P ((edge basic-edge))
  • Method UNTAGGED-EDGE-P ((edge basic-edge))
  • Method TAG-ALL-EDGES ((graph basic-graph))
  • Method TAG-ALL-EDGES ((vertex basic-vertex))
  • Method UNTAG-ALL-EDGES ((graph basic-graph))
  • Method UNTAG-ALL-EDGES ((vertex basic-vertex))
  • Method ADD-VERTEX ((graph basic-graph) (value t) &rest args &key (if-duplicate-do :ignore) &allow-other-keys)
  • Method REPLACE-VERTEX ((graph basic-graph) (old basic-vertex) (new basic-vertex))
  • Method ADD-EDGE-BETWEEN-VERTEXES ((graph basic-graph) (value-1 t) (value-2 t) &rest args &key (if-duplicate-do :ignore) &allow-other-keys)
  • Method ADD-EDGE-BETWEEN-VERTEXES ((graph basic-graph) (v-1 basic-vertex) (v-2 basic-vertex) &rest args &key (value nil) (if-duplicate-do :ignore) (edge-type (default-edge-type graph)) (edge-class (default-edge-class graph)) &allow-other-keys)
  • Method FIND-EDGE-BETWEEN-VERTEXES ((graph basic-graph) (value-1 t) (value-2 t) &key (error-if-not-found? t))
  • Method DELETE-EDGE-BETWEEN-VERTEXES ((graph basic-graph) (value-or-vertex-1 t) (value-or-vertex-2 t) &rest args)
  • Method DELETE-VERTEX ((graph basic-graph) value-or-vertex)
  • Method DELETE-VERTEX ((graph basic-graph) (vertex basic-vertex))
  • Method DELETE-VERTEX ((graph basic-graph) (vertex basic-vertex))
  • Method SOURCE-EDGES ((vertex basic-vertex) &optional filter)
  • Method TARGET-EDGES ((vertex basic-vertex) &optional filter)
  • Method CHILD-VERTEXES (vertex &optional filter)
  • Method PARENT-VERTEXES (vertex &optional filter)
  • Method NEIGHBOR-VERTEXES (vertex &optional filter)
  • Method ADJACENTP ((graph basic-graph) vertex-1 vertex-2)
  • Method ADJACENTP ((graph basic-graph) (vertex-1 basic-vertex) (vertex-2 basic-vertex))
  • Method NUMBER-OF-NEIGHBORS (vertex)
  • Method IN-CYCLE-P ((graph basic-graph) (vertex t))
  • Method RENUMBER-VERTEXES ((graph basic-graph))
  • Method RENUMBER-EDGES ((graph basic-graph))
  • Method ADD-VERTEX ((graph basic-graph) (vertex basic-vertex) &key &allow-other-keys)
  • Method ADD-EDGE ((graph basic-graph) (edge basic-edge) &key force-new?)
  • Method FIND-VERTEX ((graph basic-graph) (value t) &optional (error-if-not-found? t))
  • Method FIND-VERTEX ((graph basic-graph) (vertex basic-vertex) &optional (error-if-not-found? t))
  • Method FIND-VERTEX ((edge basic-edge) (value t) &optional (error-if-not-found? t))
  • Method SEARCH-FOR-VERTEX ((graph basic-graph) (vertex basic-vertex) &key (key (vertex-key graph)) (test 'equal) (error-if-not-found? t))
  • Method SEARCH-FOR-VERTEX ((graph basic-graph) (vertex t) &key (key (vertex-key graph)) (test 'equal) (error-if-not-found? t))
  • Method ITERATE-VERTEXES ((graph basic-graph) fn)
  • Method ITERATE-VERTEXES ((edge basic-edge) fn)
  • Method EDGES ((graph basic-graph))
  • Method EDGES ((vertex basic-vertex))
  • Method VERTEX-COUNT ((graph basic-graph))
  • Method VERTEXES ((graph basic-graph))
  • Method SOURCE-EDGE-COUNT ((vertex basic-vertex))
  • Method TARGET-EDGE-COUNT ((vertex basic-vertex))
  • Method GRAPH-ROOTS ((graph basic-graph))
  • Method ROOTP ((vertex basic-vertex))
  • Method FIND-VERTEX-IF ((graph basic-graph) fn &key key)
  • Method FIND-VERTEX-IF ((edge basic-edge) fn &key key)
  • Method FIND-EDGE-IF ((graph basic-graph) fn &key key)
  • Method FIND-EDGES-IF ((graph basic-graph) fn)
  • Method FIND-VERTEXES-IF ((graph basic-graph) fn)
  • Method GENERATE-DIRECTED-FREE-TREE ((graph basic-graph) root)
  • Method FORCE-UNDIRECTED ((graph basic-graph))
  • Method IN-CYCLE-P ((graph basic-graph) (start-vertex basic-vertex))
  • Method IN-UNDIRECTED-CYCLE-P ((graph basic-graph) (current basic-vertex) &optional (marked (make-container 'simple-associative-container)) (previous nil))
  • Method ANY-UNDIRECTED-CYCLE-P ((graph basic-graph))
  • Function GET-TRANSITIVE-CLOSURE (vertex-list &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 EDGE-COUNT ((graph basic-graph))
  • Method EDGE-COUNT ((vertex basic-vertex))
  • Method TOPOLOGICAL-SORT ((graph basic-graph))
  • Method DEPTH ((graph basic-graph))
  • Function MAP-PATHS (graph start-vertex length fn &key (filter (constantly t)))
    Apply fn to each path that starts at start-vertex and is of exactly length length
  • Function MAP-SHORTEST-PATHS (graph start-vertex depth fn &key (filter (constantly t)))
    Apply fn to each shortest path starting at `start-vertex` of depth `depth`. The `filter` predicate is used to remove vertexes from consideration.
  • Method PROJECT-BIPARTITE-GRAPH ((new-graph symbol) graph vertex-class vertex-classifier)
  • Class GRAPH-CONTAINER  (ITERATABLE-CONTAINER-MIXIN, NON-ASSOCIATIVE-CONTAINER-MIXIN, INITIAL-CONTENTS-MIXIN, BASIC-GRAPH, CONTAINER-USES-NODES-MIXIN)
    A graph container is essentially an adjacency list graph representation [?? The Bad name comes from it being implemented with containers... ugh]
    VERTEX-PAIR->EDGE   Reader: VERTEX-PAIR->EDGE
  • Class GRAPH-CONTAINER-EDGE  (BASIC-EDGE)
    This is the root class for edges in graph-containers. It adds vertex-1 and vertex-2 slots.
    VERTEX-1   Reader: VERTEX-1
    `Vertex-1` is one of the two vertexes that an edge connects. In a directed-edge, `vertex-1` is also the `source-vertex`.
    VERTEX-2   Reader: VERTEX-2
    `Vertex-2` is one of the two vertexes that an edge connects. In a directed edge, `vertex-2` is also the `target-vertex`.
  • Class WEIGHTED-EDGE  (WEIGHTED-EDGE-MIXIN, GRAPH-CONTAINER-EDGE)
    A weighted edge is both a weighted-edge-mixin and a graph-container-edge.
    No slots.
  • Class WEIGHTED-DIRECTED-EDGE  (WEIGHTED-EDGE-MIXIN, GRAPH-CONTAINER-DIRECTED-EDGE)
    A weighted edge is a weighted-edge-mixin, a directed-edge-mixin, and a graph-container-edge.
    No slots.
  • Class WEIGHTED-UNDIRECTED-EDGE  (WEIGHTED-EDGE-MIXIN, GRAPH-CONTAINER-UNDIRECTED-EDGE)
    A weighted undirected edge is a weighted-edge-mixin, an undirected-edge-mixin, and a graph-container-edge.
    No slots.
  • Class GRAPH-CONTAINER-VERTEX  (BASIC-VERTEX)
    A graph container vertex keeps track of its edges in the the vertex-edges slot. The storage for this defaults to a vector-container but can be changed using the vertex-edges-container-class initarg.
    VERTEX-EDGES   Reader: VERTEX-EDGES
  • Method MAKE-VERTEX-EDGES-CONTAINER ((vertex graph-container-vertex) container-class &rest args)
  • Class GRAPH-CONTAINER-UNDIRECTED-EDGE  (UNDIRECTED-EDGE-MIXIN, GRAPH-CONTAINER-EDGE)
    A graph-container-undirected-edge is both an undirected-edge-mixin and a graph-container-edge.
    No slots.
  • Class GRAPH-CONTAINER-DIRECTED-EDGE  (DIRECTED-EDGE-MIXIN, GRAPH-CONTAINER-EDGE)
    A graph-container-directed-edge is both a directed-edge-mixin and a graph-container-edge.
    No slots.
  • Method SOURCE-VERTEX ((edge graph-container-edge))
  • Method TARGET-VERTEX ((edge graph-container-edge))
  • Method OTHER-VERTEX ((edge graph-container-edge) (v graph-container-vertex))
  • Method OTHER-VERTEX ((edge graph-container-edge) (value t))
  • Method REPLACE-VERTEX ((graph graph-container) (old basic-vertex) (new basic-vertex))
  • Method REPLACE-VERTEX ((graph graph-container) (old basic-vertex) (new basic-vertex))
  • Method FIND-EDGE-BETWEEN-VERTEXES ((graph graph-container) (vertex-1 graph-container-vertex) (vertex-2 graph-container-vertex) &key error-if-not-found?)
  • Method FIND-EDGE-BETWEEN-VERTEXES-IF ((graph graph-container) (vertex-1 graph-container-vertex) (vertex-2 graph-container-vertex) fn &key error-if-not-found?)
  • Method FIND-EDGE-BETWEEN-VERTEXES-IF ((graph graph-container) (value-1 t) (value-2 t) fn &key error-if-not-found?)
  • Method FIND-EDGE ((graph graph-container) (edge graph-container-edge) &optional error-if-not-found?)
  • Method ITERATE-EDGES ((graph graph-container) fn)
  • Method ITERATE-EDGES ((vertex graph-container-vertex) fn)
  • Method ITERATE-SOURCE-EDGES ((vertex graph-container-vertex) fn)
  • Method ITERATE-TARGET-EDGES ((vertex graph-container-vertex) fn)
  • Method ITERATE-PARENTS ((vertex graph-container-vertex) fn)
  • Method ITERATE-NEIGHBORS ((vertex graph-container-vertex) fn)
  • Method VERTEXES ((edge graph-container-edge))
  • Method HAS-CHILDREN-P ((vertex graph-container-vertex))
  • Method HAS-PARENT-P ((vertex graph-container-vertex))
  • Method VERTICES-SHARE-EDGE-P ((vertex-1 graph-container-vertex) (vertex-2 graph-container-vertex))
  • Method EDGE-COUNT ((graph graph-container))
  • Class GRAPH-MATRIX  (BASIC-GRAPH)
    Stub for matrix based graph. Not implemented.
    ADJENCENCY-MATRIX   Reader: ADJENCENCY-MATRIX
  • Class GRAPH-MATRIX-EDGE  (BASIC-EDGE)
    Stub for matrix based graph. Not implemented.
    No slots.
  • Class GRAPH-MATRIX-VERTEX  (BASIC-VERTEX)
    Stub for matrix based graph. Not implemented.
    No slots.
  • Method CONNECTED-COMPONENTS ((graph basic-graph))
  • Method CONNECTED-COMPONENT-COUNT ((graph basic-graph))
  • Method FIND-CONNECTED-COMPONENTS ((graph basic-graph))
  • Method EDGE-LESSP-BY-WEIGHT ((e1 basic-edge) (e2 basic-edge))
  • Method MINIMUM-SPANNING-TREE ((graph basic-graph) &key (edge-sorter #'edge-lessp-by-weight))
  • Method CONNECTED-GRAPH-P ((graph basic-graph) &key (edge-sorter 'edge-lessp-by-weight))
  • Method EDGE-LESSP-BY-DIRECTION ((e1 basic-edge) (e2 basic-edge))
  • Method OUT-EDGE-FOR-VERTEX-P ((edge basic-edge) (vertex basic-vertex))
  • Method DFS ((graph basic-graph) (root t) fn &key (out-edge-sorter #'edge-lessp-by-direction))
  • Method DFS ((graph basic-graph) (root basic-vertex) fn &key (out-edge-sorter #'edge-lessp-by-direction))
  • Generic-Function ROOTED-DFS (graph root fn &key out-edge-sorter)
    A variant of DFS that does not visit nodes that are unreachable from the ROOT.
  • Method ROOTED-DFS ((graph basic-graph) (root basic-vertex) fn &key (out-edge-sorter #'edge-lessp-by-direction))
  • Method ROOTED-DFS ((graph basic-graph) (root basic-vertex) fn &key (out-edge-sorter #'edge-lessp-by-direction))
  • Method ROOTED-DFS ((graph basic-graph) (root basic-vertex) fn &key (out-edge-sorter #'edge-lessp-by-direction))
  • Method ROOTED-DFS ((graph basic-graph) (root t) fn &key (out-edge-sorter #'edge-lessp-by-direction))
  • Method ROOTED-DFS ((graph basic-graph) (root t) fn &key (out-edge-sorter #'edge-lessp-by-direction))
  • Method ROOTED-DFS ((graph basic-graph) (root t) fn &key (out-edge-sorter #'edge-lessp-by-direction))
  • Method DFS-TREE-EDGE-P ((edge graph-container-edge))
  • Method DFS-BACK-EDGE-P ((edge graph-container-edge))
  • Method DFS-EDGE-TYPE ((edge graph-container-edge))
  • Method GRAPH->DOT ((g basic-graph) (stream stream) &key (graph-formatter 'graph->dot-properties) (vertex-key 'vertex-id) (vertex-labeler nil) (vertex-formatter 'vertex->dot) (edge-labeler 'princ) (edge-formatter 'edge->dot) &allow-other-keys)
  • Method GRAPH->DOT ((g basic-graph) (stream (eql nil)) &rest args &key &allow-other-keys)
  • Method GRAPH->DOT ((g basic-graph) (stream (eql t)) &rest args &key &allow-other-keys)
  • Method GRAPH->DOT ((g basic-graph) (stream string) &rest args &key &allow-other-keys)
  • Method GRAPH->DOT ((g basic-graph) (stream pathname) &rest args &key &allow-other-keys)
  • Method GRAPH->DOT-PROPERTIES ((g t) (stream t))
  • Method VERTEX->DOT ((v basic-vertex) (stream stream))
  • Method EDGE->DOT ((v basic-edge) (stream stream))
  • Variable *DOT-GRAPH-ATTRIBUTES*
    '((:size cl-graph::coordinate) (:bb cl-graph::bounding-box)
      (:page cl-graph::text) (:dpi float) (:ratio (:fill :compress :auto))
      (:margin float) (:nodesep float) (:ranksep float) (:ordering (:out))
      (:overlap cl-graph::text) (:rankdir ("lr" "rl" "bt"))
      (:pagedir cl-graph::text) (:rank (:same :min :max)) (:rotate integer)
      (:center integer) (:nslimit float) (:mclimit float) (:layers cl-graph::text)
      (:color cl-graph::text) (:bgcolor cl-graph::text) (:fontname cl-graph::text))
  • Class DOT-ATTRIBUTES-MIXIN
    DOT-ATTRIBUTES   Accessor: DOT-ATTRIBUTES
  • Class DOT-GRAPH-MIXIN  (DOT-ATTRIBUTES-MIXIN)
    No slots.
  • Class DOT-VERTEX-MIXIN  (DOT-ATTRIBUTES-MIXIN)
    No slots.
  • Class DOT-EDGE-MIXIN  (DOT-ATTRIBUTES-MIXIN)
    No slots.
  • Class DOT-GRAPH  (DOT-GRAPH-MIXIN, GRAPH-CONTAINER)
    No slots.
  • Class DOT-VERTEX  (DOT-VERTEX-MIXIN, GRAPH-CONTAINER-VERTEX)
    No slots.
  • Class DOT-EDGE  (DOT-EDGE-MIXIN, GRAPH-CONTAINER-EDGE)
    No slots.
  • Class DOT-DIRECTED-EDGE  (DOT-EDGE, DIRECTED-EDGE-MIXIN)
    No slots.
  • Method (setf DOT-ATTRIBUTE-VALUE) (value (attr symbol) (thing dot-attributes-mixin))
  • Method (setf DOT-ATTRIBUTE-VALUE) (value (attr symbol) (thing dot-attributes-mixin))
  • Method DOT-ATTRIBUTE-VALUE ((attr symbol) (thing dot-attributes-mixin))
  • Method WIDTH-IN-PIXELS ((thing dot-vertex-mixin))
    Return the attribute in pixels assuming 72 dpi
  • Method (setf WIDTH-IN-PIXELS) (value (thing dot-vertex-mixin))
    Set the attribute in pixels assuming 72 dpi
  • Method HEIGHT-IN-PIXELS ((thing dot-vertex-mixin))
    Return the attribute in pixels assuming 72 dpi
  • Method (setf HEIGHT-IN-PIXELS) (value (thing dot-vertex-mixin))
    Set the attribute in pixels assuming 72 dpi
  • Method GRAPH->DOT-PROPERTIES ((graph dot-graph-mixin) (stream t))
  • Method VERTEX->DOT ((vertex dot-vertex-mixin) (stream t))
  • Method EDGE->DOT ((edge dot-edge-mixin) (stream t))
  • Function PRINT-DOT-KEY-VALUE (key value dot-attributes stream)
  • Method GRAPH->DOT-EXTERNAL ((g basic-graph) file-name &rest args &key (type :ps) &allow-other-keys)
    Generate an external represenation of a graph to a file, by running the program in *dot-path*.

Also exports

  • METABANG.UTILITIES:TAG
  • METABANG.UTILITIES:ELEMENT
  • METABANG.CL-CONTAINERS:WEIGHT
  • METABANG.CL-CONTAINERS:ITERATE-CHILDREN
  • METABANG.CL-CONTAINERS:ITERATE-CONTAINER

cl-graph+hu.dwim.graphviz

No packages.