1 (in-package #:cl-graph)
4 (defgeneric make-vertex-container (graph initial-size)
5 (:documentation "Make-vertex-container is called during graph
6 creation and can be used to create specialized containers to hold
10 (defgeneric make-edge-container (graph initial-size)
11 (:documentation "Make-edge-container is called during graph creation
12 and can be used to create specialized containers to hold graph
17 (defgeneric make-graph (graph-type &key &allow-other-keys)
18 (:documentation "Create a new graph of type `graph-type'. Graph type
19 can be a symbol naming a sub-class of basic-graph or a list. If it is
20 a list of symbols naming different classes. If graph-type is a list,
21 then a class which has all of the listed classes as superclasses will
22 be found (or created). In either case, the new graph will be created
23 as if with a call to make-instance."))
26 (defgeneric make-edge-for-graph (graph vertex-1 vertex-2
27 &key edge-type edge-class
29 (:documentation "It should not usually necessary to call this in
30 user code. Creates a new edge between vertex-1 and vertex-2 for the
31 graph. If the edge-type and edge-class are not specified, they will
32 be determined from the defaults of the graph."))
35 (defgeneric add-edge (graph edge &rest args &key force-new?)
36 (:documentation "Add-edge adds an existing edge to a graph. As
37 add-edge-between-vertexes is generally more natural to use, this
38 method is rarely called."))
41 (defgeneric add-edge-between-vertexes (graph value-or-vertex-1 value-or-vertex-2
42 &rest args &key if-duplicate-do
43 edge-type &allow-other-keys)
44 (:documentation "Adds an edge between two vertexes and returns it.
45 If force-new? is true, the edge is added even if one already exists.
46 If the vertexes are not found in the graph, they will be added
47 \(unless :error-if-not-found? is true\). The class of the edge can be
48 specified using :edge-class or :edge-type. If :edge-type is used, it
49 can be either :directed or :undirected; the actual class of the edge
50 will be determined by using the edge-types of the graph. If
51 neither :edge-type nor :edge-class is specified, then a directed edge
54 If-duplicate-do is used when the 'same' edge is added more than
55 once. It can be either a function on one variable or :ignore
56 or :force. If it is :ignore, then the previously added edge is
57 returned; if it is :force, then another edge is added between the two
58 vertexes; if it is a function, then this function will be called with
62 (defgeneric delete-edge (graph edge)
63 (:documentation "Delete the `edge' from the `graph' and returns it."))
65 (defgeneric delete-all-edges (graph)
66 (:documentation "Delete all edges from `graph'. Returns the graph.."))
69 (defgeneric delete-edge-between-vertexes (graph value-or-vertex-1
70 value-or-vertex-2 &rest args)
71 (:documentation "Finds an edge in the graph between the two
72 specified vertexes. If values (i.e., non-vertexes) are passed in,
73 then the graph will be searched for matching vertexes."))
76 (defgeneric add-vertex (graph value-or-vertex &key if-duplicate-do &allow-other-keys)
77 (:documentation "Adds a vertex to a graph. If called with a vertex,
78 then this vertex is added. If called with a value, then a new vertex
79 is created to hold the value. If-duplicate-do can be one
80 of :ignore, :force, :replace, :replace-value, :error, or a function. The
81 default is :ignore."))
84 (defgeneric delete-vertex (graph value-or-vertex)
85 (:documentation "Remove a vertex from a graph. The 'vertex-or-value'
86 argument can be a vertex of the graph or a 'value' that will find a
87 vertex via a call to find-vertex. A graph-vertex-not-found-error will
88 be raised if the vertex is not found or is not part of the graph."))
91 (defgeneric find-vertex (graph value &optional error-if-not-found?)
92 (:documentation "Search 'graph' for a vertex with element
93 'value'. The search is fast but inflexible because it uses an
94 associative-container. If you need more flexibity, see
98 (defgeneric search-for-vertex (graph value &key key test error-if-not-found?)
99 (:documentation "Search 'graph' for a vertex with element
100 'value'. The 'key' function is applied to each element before that
101 element is compared with the value. The comparison is done using the
102 function 'test'. If you don't need to use key or test, then consider
103 using find-vertex instead."))
106 (defgeneric find-edge (graph edge &optional error-if-not-found?)
107 (:documentation "Search `graph` for an edge whose vertexes match
108 `edge`. This means that `vertex-1` of the edge in the graph must
109 match `vertex-1` of `edge` and so forth. Wil signal an error of type
110 `graph-edge-not-found-error` unless `error-if-not-found?` is
111 nil. [?? Unused. Remove?]"))
114 (defgeneric find-edge-between-vertexes (graph value-or-vertex-1 value-or-vertex-2
115 &key error-if-not-found?)
116 (:documentation "Searches `graph` for an edge that connects vertex-1
117 and vertex-2. [?? Ignores error-if-not-found? Does directedness
118 matter? need test]"))
121 (defgeneric source-vertex (edge)
122 (:documentation "Returns the source-vertex of a directed
123 edge. Compare with `vertex-1`."))
126 (defgeneric target-vertex (edge)
127 (:documentation "Returns the target-vertex of a directed
128 edge. Compare with `vertex-2`."))
131 (defgeneric iterate-edges (graph-or-vertex fn)
132 (:documentation "Calls `fn` on each edge of graph or vertex."))
135 (defgeneric iterate-source-edges (vertex fn)
136 (:documentation "In a directed graph, calls `fn` on each edge of a
137 vertex that begins at vertex. In an undirected graph, this is
138 equivalent to `iterate-edges`."))
141 (defgeneric iterate-target-edges (vertex fn)
142 (:documentation "In a directed graph, calls `fn` on each edge of a
143 vertex that ends at vertex. In an undirected graph, this is
144 equivalent to `iterate-edges`."))
146 (defgeneric has-children-p (vertex)
147 (:documentation "In a directed graph, returns true if vertex has any
148 edges that point from vertex to some other
149 vertex (cf. iterate-target-edges). In an undirected graph,
150 `has-children-p` is testing only whether or not the vertex has any
154 (defgeneric has-parent-p (vertex)
155 (:documentation "In a directed graph, returns true if vertex has any
156 edges that point from some other vertex to this
157 vertex (cf. iterate-source-edges). In an undirected graph,
158 `has-parent-p` is testing only whether or not the vertex has any
162 (defgeneric iterate-parents (vertex fn)
163 (:documentation "Calls fn on every vertex that is either connected
164 to vertex by an undirected edge or is at the source end of a
168 (defgeneric iterate-neighbors (vertex fn)
169 (:documentation "Calls fn on every vertex adjecent to vertex See
170 also iterate-children and iterate-parents."))
173 (defgeneric renumber-vertexes (graph)
174 (:documentation "Assign a number to each vertex in a graph in some
175 unspecified order. [?? internal]"))
178 (defgeneric renumber-edges (graph)
179 (:documentation "Assign a number to each edge in a graph in some
180 unspecified order. [?? internal]"))
183 (defgeneric generate-directed-free-tree (graph root)
184 (:documentation "Returns a version of graph which is a directed free
185 tree rooted at root."))
188 (defgeneric in-undirected-cycle-p (graph start-vertex &optional marked previous)
189 (:documentation "Return true if-and-only-if an undirected cycle in
190 graph is reachable from start-vertex."))
193 (defgeneric undirected-edge-p (edge)
194 (:documentation "Returns true if-and-only-if edge is undirected"))
197 (defgeneric directed-edge-p (edge)
198 (:documentation "Returns true if-and-only-if edge is directed"))
201 (defgeneric tagged-edge-p (edge)
202 (:documentation "Returns true if-and-only-if edge's tag slot is t"))
205 (defgeneric untagged-edge-p (edge)
206 (:documentation "Returns true if-and-only-if edge's tage slot is nil"))
209 (defgeneric adjacentp (graph vertex-1 vertex-2)
210 (:documentation "Return true if vertex-1 and vertex-2 are connected
211 by an edge. [?? compare with vertices-share-edge-p and remove one or
212 maybe call one directed-adjacentp]"))
215 (defgeneric make-filtered-graph (old-graph test-fn &key
216 graph-completion-method depth
218 (:documentation "Takes a GRAPH and a TEST-FN (a single argument
219 function returning NIL or non-NIL), and filters the graph nodes
220 according to the test-fn (those that return non-NIL are accepted),
221 returning a new graph with only nodes corresponding to those in the
222 original graph that satisfy the test (the nodes in the new graph are
223 new, but their values and name point to the same contents of the
224 original graph). There are four options for how the new graph is
225 filled-out, depending on the following keywords passed to the optional
226 GRAPH-COMPLETION-METHOD argument:
230 New graph has only nodes that correspond to those in the original
231 graph that pass the test. NO LINKS are reproduced.
235 New graph has only nodes that pass, but reproduces corresponding
236 links between passing nodes in the original graph.
238 * :COMPLETE-CLOSURE-NODES-ONLY
240 New graph also includes nodes corresponding to the transitive
241 closure(s) that include the passign nodes in the original
242 graph. NO LINKS are reproduced.
244 * :COMPLETE-CLOSURE-WITH-LINKS
246 Same as above, except corresponding links are reproduced.
248 For both transitive closure options, an additional optional argument,
249 DEPTH, specifies how many links away from a source vertex to travel in
250 gathering vertexes of the closure. E.g., a depth of 1 returns the
251 source vertex and the parents and children of that vertex (all
252 vertexes one link away from the source). The default value is NIL,
253 indicating that all vertexes are to be included, no matter their
254 depth. This value is ignored in non closure options."))
257 (defgeneric project-bipartite-graph
258 (new-graph existing-graph vertex-class vertex-classifier)
259 (:documentation "Creates the unimodal bipartite projects of
260 existing-graph with vertexes for each vertex of existing graph whose
261 `vertex-classifier` is eq to `vertex-class` and where an edge existing
262 between two vertexes of the graph if and only if they are connected to
263 a shared vertex in the existing-graph."))
266 (defgeneric assortativity-coefficient (mixing-matrix)
267 (:documentation "An assortative graph is one where vertexes of the
268 same type are more likely to have edges between them. The \(discrete\)
269 assortativity-coefficient measures how assortative a graph is based on
270 its mixing matrix. The definition we use is from Mixing Patterns in
271 Networks by Mark Newman. See the citation 'newman200-mixing' in moab
272 or the URL 'http://arxiv.org/abs/cond-mat/0209450'."))
275 (defgeneric graph->dot (graph output
284 "Generates a description of `graph` in DOT file format. The
285 formatting can be altered using `graph->dot-properties,`
286 `vertex->dot,` and `edge->dot` as well as `edge-formatter,`
287 `vertex-formatter,` `vertex-labeler,` and `edge-labeler`. These can
288 be specified directly in the call to `graph->dot` or by creating
289 subclasses of basic-graph, basic-vertex and basic-edge.
291 The output can be a stream or pathname or one of the values `nil` or
292 `t`. If output is `nil`, then graph->dot returns a string containing
293 the DOT description. If it is `t`, then the DOT description is written
294 to \\*standard-output\\*.
298 (let ((g (make-container 'graph-container :default-edge-type :directed)))
299 (loop for (a b) in '((a b) (b c) (b d) (d e) (e f) (d f)) do
300 (add-edge-between-vertexes g a b))
318 For more information about DOT file format, search the web for 'DOTTY' and
322 (defgeneric graph->dot-properties (g stream)
323 (:documentation "Unless a different graph-formatter is specified,
324 this method is called by graph->dot to output graph-properties onto
325 a stream. The function can assume that the openning and closing
326 brackets will be taken care of by the graph->dot."))
329 (defgeneric vertex->dot (vertex stream)
330 (:documentation "Unless a different vertex-formatter is specified
331 with a keyword argument, this is used by graph->dot to output vertex
332 formatting for `vertex` onto the `stream`. The function can assume
333 that openning and closing square brackets and label have already
334 been taken care of."))
337 (defgeneric edge->dot (edge stream)
338 (:documentation "Used by graph->dot to output edge formatting for
339 `edge` onto the `stream`. The function can assume that openning and
340 closing square brackets and label have already been taken care
344 (defgeneric generate-gnm (generator graph n m &key)
345 (:documentation "Generate a 'classic' random graph G(n, m) with n
346 vertexes and m edges."))
349 (defgeneric generate-gnp (generator graph n p &key)
350 (:documentation "Generate the Erd\"os-R\'enyi random graph G\(n,
351 p\). I.e., a graph with n vertexes where each possible edge appears
352 with probability p. This implementation is from Efficient Generation
353 of Large Random Networks \(see batagelj-generation-2005 in doab\)."))
356 (defgeneric generate-undirected-graph-via-assortativity-matrix
357 (generator graph-class size edge-count kind-matrix assortativity-matrix
359 (:documentation "This generates a random graph with 'size' vertexes.
360 The vertexes can be in multiple different classes and the number of
361 vertexes in each class is specified in the 'kind-matrix'. If the
362 matrix has all fixnums, then it specifies the counts and these should
363 add up to the size. If the kind-matrix contains non-fixnums then the
364 values are treated as ratios.
366 The assortativity-matrix specifies the number of edges between
367 vertexes of different kinds.
369 The vertex-labeler is a function of two parameters: the vertex kind
370 and the index. It should return whatever the 'value' of the vertex
374 (defgeneric generate-undirected-graph-via-vertex-probabilities
375 (generator graph-class size kind-matrix probability-matrix vertex-labeler)
376 (:documentation "Generate an Erd\"os-R/'enyi like random graph
377 having multiple vertex kinds. See the function Gnp for the simple one
380 Generator and graph-class specify the random number generator used and
381 the class of the graph produced; Size the number of vertexes. Kind
382 matrix is a vector of ratios specifying the distribution of vertex
383 kinds {0 ... \(1- k\)}. The probability-matrix is a k x k matrix
384 specifying the probability that two vertexes of the row-kind and the
385 column-kind will have an edge between them. vertex-labeler is a
386 function of two arguments \(the kind and the vertex number\) called to
387 create values for vertexes. It will be called only once for each
390 The clever sequential sampling technique in this implementation is
391 from Efficient Generation of Large Random Networks \(see
392 batagelj-generation-2005 in moab\)."))
395 (defgeneric generate-scale-free-graph
396 (generator graph size kind-matrix add-edge-count
397 other-vertex-kind-samplers vertex-labeler &key)
398 (:documentation "Generates a 'scale-free' graph using preferential
399 attachment -- too damn slow.
401 Size is the number of vertexes; kind-matrix is as in
402 generate-undirected-graph-via-assortativity-matrix, etc.;
403 add-edge-count is the number of edges to add for each vertex;
404 other-vertex-kind-samplers are confusing...; and vertex-labeler is
405 used to create vertex elements \(as in other generators\)."))
408 (defgeneric generate-assortative-graph-with-degree-distributions
410 edge-count assortativity-matrix
418 (defgeneric generate-simple-preferential-attachment-graph (generator graph size minimum-degree)
419 (:documentation "Generate a simple scale-free graph using the
420 preferential attachment mechanism of Barabasi and Albert. The
421 implementation is from Efficient Generation of Large Random Networks
422 \(see batagelj-generation-2005 in moab\). Self-edges are possible."))
425 (defgeneric generate-preferential-attachment-graph
426 (generator graph size kind-matrix minimum-degree
429 (:documentation "Generate a Barabasi-Albert type scale free graph
430 with multiple vertex kinds.
432 The idea behind this implementation is from Efficient Generation of
433 Large Random Networks \(see batagelj-generation-2005 in moab\)."))
438 (defgeneric make-vertex-for-graph (graph &key &allow-other-keys)
439 (:documentation "Creates a new vertex for graph `graph`. The keyword
442 * vertex-class : specify the class of the vertex
443 * element : specify the `element` of the vertex
445 and any other initialization arguments that make sense for the vertex
449 (defgeneric tag-all-edges (thing)
450 (:documentation "Sets the `tag` of all the edges of `thing` to
451 true. [?? why does this exist?\]"))
454 (defgeneric untag-all-edges (thing)
455 (:documentation "Sets the `tag` of all the edges of `thing` to nil.
456 [?? why does this exist?\]"))
459 (defgeneric untag-edges (edges)
460 (:documentation "Sets the `tag` of all the edges of `thing` to
461 true. [?? why does this exist?\]"))
464 (defgeneric tag-edges (edges)
465 (:documentation "Sets the `tag` of all the edges of `thing` to
466 true. [?? why does this exist?\]"))
469 (defgeneric replace-vertex (graph old new)
470 (:documentation "Replace vertex `old` in graph `graph` with vertex
471 `new`. The edge structure of the graph is maintained."))
474 (defgeneric add-edge-to-vertex (edge vertex)
475 (:documentation "Attaches the edge `edge` to the vertex `vertex`."))
478 (defgeneric source-edges (vertex &optional filter)
479 (:documentation "Returns a list of the source edges of
480 `vertex`. I.e., the edges that begin at `vertex`."))
483 (defgeneric target-edges (vertex &optional filter)
484 (:documentation "Returns a list of the target edges of `vertex`.
485 I.e., the edges that end at `vertex`."))
488 (defgeneric child-vertexes (vertex &optional filter)
489 (:documentation "Returns a list of the vertexes to which `vertex` is
490 connected by an edge and for which `vertex` is the source vertex. If
491 the connecting edge is undirected, then the vertex is always counted
492 as a source. [?? Could be a defun]."))
495 (defgeneric parent-vertexes (vertex &optional filter)
496 (:documentation "Returns a list of the vertexes to which `vertex` is
497 connected by an edge and for which `vertex` is the target vertex. If
498 the connecting edge is undirected, then the vertex is always counted
499 as a target. [?? Could be a defun]."))
502 (defgeneric neighbor-vertexes (vertex &optional filter)
503 (:documentation "Returns a list of the vertexes to which `vertex` is
504 connected by an edge disregarding edge direction. In a directed
505 graph, neighbor-vertexes is the union of parent-vertexes and
506 child-vertexes. [?? Could be a defun]."))
509 (defgeneric number-of-neighbors (vertex)
510 (:documentation "Returns the number of neighbors of
511 `vertex` (cf. `neighbor-vertexes`). [?? could be a defun]"))
514 (defgeneric in-cycle-p (graph start-vertex)
515 (:documentation "Returns true if `start-vertex` is in some cycle in
516 `graph`. This uses child-vertexes to generate the vertexes adjacent
520 (defgeneric iterate-vertexes (thing fn)
521 (:documentation "Calls `fn` on each of the vertexes of `thing`."))
524 (defgeneric edges (thing)
525 (:documentation "Returns a list of the edges of `thing`."))
528 (defgeneric vertex-count (graph)
529 (:documentation "Returns the number of vertexes in `graph`. [??
533 (defgeneric vertexes (thing)
534 (:documentation "Returns a list of the vertexes of `thing`."))
537 (defgeneric source-edge-count (vertex)
538 (:documentation "Returns the number of source edges of
539 vertex (cf. source-edges). [?? could be a defun]"))
542 (defgeneric target-edge-count (vertex)
543 (:documentation "Returns the number of target edges of
544 vertex (cf. target-edges). [?? could be a defun]"))
547 (defgeneric graph-roots (graph)
548 (:documentation "Returns a list of the roots of graph. A root is
549 defined as a vertex with no source edges \(i.e., all of the edges
550 are out-going\). (cf. rootp) [?? could be a defun]"))
553 (defgeneric rootp (vertex)
554 (:documentation "Returns true if `vertex` is a root vertex \(i.e.,
555 it has no incoming \(source\) edges\)."))
558 (defgeneric find-vertex-if (thing predicate &key key)
559 (:documentation "Returns the first vertex in `thing` for which the
560 `predicate` function returns non-nil. If the `key` is supplied, then
561 it is applied to the vertex before the predicate is."))
564 (defgeneric find-edge-if (graph fn &key key)
565 (:documentation "Returns the first edge in `thing` for which the
566 `predicate` function returns non-nil. If the `key` is supplied, then
567 it is applied to the edge before the predicate is."))
570 (defgeneric find-edges-if (thing predicate)
571 (:documentation "Returns a list of edges in `thing` for which the
572 `predicate` returns non-nil. [?? why no key function?]"))
575 (defgeneric find-vertexes-if (thing predicate)
576 (:documentation "Returns a list of vertexes in `thing` for which the `predicate` returns non-nil. [?? why no key function?]"))
579 (defgeneric force-undirected (graph)
580 (:documentation "Ensures that the graph is undirected (possibly by
581 calling change-class on the edges)."))
584 (defgeneric traverse-elements (thing style fn)
585 (:documentation "WIP"))
587 (defgeneric traverse-elements-helper (thing style marker fn)
588 (:documentation "WIP"))
590 (defgeneric any-undirected-cycle-p (graph)
591 (:documentation "Returns true if there are any undirected cycles in `graph`."))
593 (defgeneric edge-count (vertex)
594 (:documentation "Returns the number of edges attached to
595 `vertex`. Compare with the more flexible `vertex-degree`."))
597 (defgeneric topological-sort (graph)
598 (:documentation "Returns a list of vertexes sorted by the depth from
599 the roots of the graph. See also assign-level and graph-roots."))
601 (defgeneric assign-level (vertex level)
602 (:documentation "Sets the depth of `vertex` to level and then
603 recursively sets the depth of all of the children of `vertex` to
606 (defgeneric depth (graph)
607 (:documentation "Returns the maximum depth of the vertexes in graph
608 assuming that the roots are of depth 0 and that each edge distance
609 from the roots increments the depth by one."))
611 (defgeneric make-vertex-edges-container (vertex container-class &rest args)
612 (:documentation "Called during the initialization of a vertex to
613 create the create the container used to store the edges incident to
614 the vertex. The initarg :vertex-edges-container-class can be used to
615 alter the default container class."))
617 (defgeneric other-vertex (edge value-or-vertex)
618 (:documentation "Assuming that the value-or-vertex corresponds to
619 one of the vertexes for `edge`, this method returns the other vertex
620 of `edge`. If the value-or-vertex is not part of edge, then an error
621 is signaled. [?? Should create a new condition for this]"))
623 (defgeneric find-edge-between-vertexes-if
624 (graph value-or-vertex-1 value-or-vertex-2 fn &key error-if-not-found?)
625 (:documentation "Finds and returns an edge between value-or-vertex-1
626 and value-or-vertex-2 if one exists. Unless error-if-not-found? is
627 nil, then a error will be signaled. [?? Error not signal, need
630 (defgeneric vertices-share-edge-p (vertex-1 vertex-2)
631 (:documentation "Return true if vertex-1 and vertex-2 are connected
632 by an edge. [?? Compare adjacentp]"))
634 (defgeneric graph-edge-mixture-matrix (graph vertex-classifier &key edge-weight)
635 (:documentation "Return the `mixing-matrix` of graph based on the
636 classifier and the edge-weight function. The mixing matrix is a
637 matrix whose runs and columns represent each class of vertex in the
638 graph. The entries of the matrix show the total number of edges
639 between vertexes of the two kinds. [?? Edge-weight is not used; also
640 compare with graph-mixture-matrix.]"))
642 (defgeneric graph-mixing-matrix (graph vertex-classifier &key edge-weight)
643 (:documentation "Return the `mixing-matrix` of graph based on the
644 classifier and the edge-weight function. The mixing matrix is a
645 matrix whose runs and columns represent each class of vertex in the
646 graph. The entries of the matrix show the total number of edges
647 between vertexes of the two kinds. [?? Edge-weight is not used; also
648 compare with graph-edge-mixture-matrix.]"))
650 (defgeneric connected-components (graph)
651 (:documentation "Returns a union-find-container representing the
652 connected-components of `graph`."))
654 (defgeneric connected-component-count (graph)
655 (:documentation "Returns the number of connected-components of
658 (defgeneric find-connected-components (graph)
659 (:documentation "Returns a list of sub-graphs of `graph` where each
660 sub-graph is a different connected component of graph. Compare with
661 connected-components and connected-component-count."))
663 (defgeneric initialize-vertex-data (graph)
666 (defgeneric breadth-first-visitor (graph source fn)
669 (defgeneric breadth-first-search-graph (graph source)
672 (defgeneric mst-find-set (vertex)
675 (defgeneric mst-make-set (vertex)
678 (defgeneric mst-tree-union (v1 v2)
681 (defgeneric mst-link (v1 v2)
684 (defgeneric add-edges-to-graph (graph edges &key if-duplicate-do)
687 (defgeneric make-graph-from-vertexes (vertex-list)
688 (:documentation "Create a new graph given a list of vertexes \(which
689 are assumed to be from the same graph\). The new graph contains all
690 of the vertexes in the list and all of the edges between any
691 vertexes on the list."))
693 (defgeneric edge-lessp-by-weight (edge-1 edge-2)
694 (:documentation "Returns true if the weight of edge-1 is strictly less than the weight of edge-2."))
696 (defgeneric minimum-spanning-tree (graph &key edge-sorter)
697 (:documentation "Returns a minimum spanning tree of graph if one exists and nil otherwise."))
699 (defgeneric connected-graph-p (graph &key edge-sorter)
700 (:documentation "Returns true if graph is a connected graph and nil otherwise."))
702 (defgeneric edge-lessp-by-direction (edge-1 edge-2)
703 (:documentation "Returns true if and only if edge-1 is undirected and edge-2 is directed."))
705 (defgeneric out-edge-for-vertex-p (edge vertex)
706 (:documentation "Returns true if the edge is connected to vertex and
707 is either an undirected edge or a directed edge for which vertex is
708 the source vertex of the edge."))
710 (defgeneric dfs (graph root fn &key out-edge-sorter)
713 (defgeneric dfs-visit (graph u fn sorter)
716 (defgeneric dfs-tree-edge-p (edge)
719 (defgeneric dfs-back-edge-p (edge)
722 (defgeneric dfs-forward-edge-p (edge)
725 (defgeneric dfs-cross-edge-p (edge)
728 (defgeneric dfs-edge-type (edge)
731 (defgeneric map-over-all-combinations-of-k-vertexes (graph k fn)
734 (defgeneric map-over-all-combinations-of-k-edges (vertex k fn)
737 (defgeneric complete-links (new-graph old-graph)
738 (:documentation "Add edges between vertexes in the new-graph for
739 which the matching vertexes in the old-graph have edges. The vertex
740 matching is done using `find-vertex`."))
742 (defgeneric subgraph-containing (graph vertex &key depth new-graph)
743 (:documentation "Returns a new graph that is a subset of `graph`
744 that contains `vertex` and all of the other vertexes that can be
745 reached from vertex by paths of less than or equal of length `depth`.
746 If depth is not specified, then the entire sub-graph reachable from
747 vertex will be returned. [?? Edge weights are always assumed to be
751 (defgeneric weight (edge)
752 (:documentation "Returns the weight of an edge. This defaults to 1.0
753 and can only be altered if the edge is a sub-class of
754 `weighted-edge-mixin`."))
756 (defgeneric (setf dot-attribute-value) (value attribute thing)
759 (defgeneric dot-attribute-value (attribute thing)
762 (defgeneric graph->dot-external (graph file-name &key type)
765 (defgeneric ensure-valid-dot-attribute (key object)
768 (defgeneric write-name-for-dot (attribute stream)