Common Lisp library for manipulating graphs and running graph algorithms
Home Page: http://common-lisp.net/project/cl-graph/
License: Other
Nix, Common Lisp, Emacs and literate programming.
My passion project is cl-nix-lite, a Common Lisp package scope for Nix, without Quicklisp.
I also maintain tomono, a multi-to-monorepository merge tool. It’s written entirely as a Literate Program.
My work is released under the AGPLv3. I am always willing to grant special commercial licenses, for a donation to me or the FSF.
Sometimes it returns the vector returned by #'iterate-children. Return from the recursive call is not dealt with correctly. (Iteration should continue when return is nil and stop when it is t.) Here is a fixed version:
(defmethod in-undirected-cycle-p
((graph basic-graph) (current basic-vertex)
&optional (marked (make-container 'simple-associative-container))
(previous nil))
(block do-it
(setf (item-at-1 marked current) t)
(iterate-children current
(lambda (child)
(cond
((eq child previous) nil)
((item-at-1 marked child) (return-from do-it t))
((in-undirected-cycle-p graph child marked current)
(return-from do-it t)))))
nil))I know you are not maintaining this project anymore, but would it be possible to remove the obsolete asdf-system-connections? It tries to load cl-graph-and-cl-variates when both are in an asdf :depends-on. The problem is, cl-graph and cl-variates have a symbol conflict. I would like to only import 1 function of cl-variates into my package, while using all of cl-graph, but this is not possible because of all this.
We are using cl-containers and cl-graph with lparallel, so we've added a "thread-safe-mixin" that automatically handles bordeaux-threads locking in production at a very high throughput. If there is enough interest, we can do a pull request here with the changes. Just let me know.
How do I configure the equality check of vertices in cl-graph? I would like to do an 'equalp check for vertex equality, so that two lists with equal contents are considered to be the same vertex.
There is a mistake in the implementation of has-children-p and has-parent-p, because they do the opposite of their specification.
Their implementations should be exchanged. Documentation should also be updated accordingly, because has-parent-p should look at target edges, and has-children-p look at source edges.
Example case:
(ql:quickload :cl-graph)
(use-package :cl-graph)
(setf g (make-graph 'graph-container :vertex-test #'equal :default-edge-type :directed))
(add-edge-between-vertexes g "foo" "bar")
(has-children-p (find-vertex g "foo"))
> NIL
(has-children-p (find-vertex g "bar"))
> T
(has-parent-p (find-vertex g "foo"))
> T
(has-parent-p (find-vertex g "bar"))
> NIL
``
I am trying to use cl-graph with https://github.com/own-pt/cl-conllu library. This library read conllu files (http://universaldependencies.org/format.html -- with a sentence tokenized). The library implements a class for a sentence that contains tokens (another class).
The first part works:
(let* ((sent (car (read-conllu #P"CF107.conllu")))
(tks (sentence-tokens sent))
(g (cl-graph:make-graph 'cl-graph:graph-container)))
(dolist (tk tks g)
(if (equal "0" (token-head tk))
(add-vertex g tk)
(add-edge-between-vertexes g tk (nth (token-head tk) tks) :edge-type :directed))))
But it seems the problem is with the edges when I try:
(cl-graph:graph->dot
*
nil
:vertex-labeler
(lambda (vertex stream)
(format stream "~(~A~)" (token-form (element vertex))))
:edge-formatter
(lambda (edge stream)
(format stream "~a" (element edge))))
I got
There is no applicable method for the generic function
#<STANDARD-GENERIC-FUNCTION CL-GRAPH:DOT-ATTRIBUTE-VALUE (1)>
when called with arguments
(:LABEL
#<GRAPH-CONTAINER-DIRECTED-EDGE <#<#<TOKEN {100301C313}>> #<#<TOKEN {100301B153}>> NIL>>).
[Condition of type SIMPLE-ERROR]
What did I miss?
Hi,
I preparing your project for Guix and I have unit tests failed:
starting phase `check'
Invoking sbcl: "/gnu/store/3pz3jlghd94sgw0iwi16hg5r5dhxzkdk-sbcl-2.2.10/bin/sbcl" "--non-interactive" "--eval" "(require :asdf)" "--eval" "(asdf:initialize-source-registry (list :source-registry (list :tree (uiop:ensure-pathname \"/gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6
-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-graph\" :truenamize t :ensure-directory t)) :inherit-configuration))" "--eval" "(asdf:test-system \"cl-graph\")" "--eval" "(asdf:test-system \"cl-graph+hu.dwim.graphviz\")" "--eval" "(asdf:test-system \"cl-graph-test
\")"
This is SBCL 2.2.10, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
WARNING:
The function SB-DEBUG:BACKTRACE has been deprecated as of SBCL version 1.2.15.
Use SB-DEBUG:PRINT-BACKTRACE instead.
In future SBCL versions SB-DEBUG:BACKTRACE will signal a full warning at
compile-time.
See also:
The SBCL Manual, Node "Deprecation Conditions"
handle config: (:IF-DRIBBLE-EXISTS :SUPERSEDE)
handle config: (:DRIBBLE "lift.dribble")
handle config: (:PRINT-LENGTH 10)
handle config: (:PRINT-LEVEL 5)
handle config: (:PRINT-TEST-CASE-NAMES T)
handle config: (CL-GRAPH-TEST)
Start: CL-GRAPH-TEST
Start: TEST-API
run: SOURCE-EDGES Pass
run: PARENTS-OF-CHILD-VERTEXES Pass
run: CHILDREN-OF-PARENT-VERTEXES Pass
run: PARENTS-AND-CHILDREN=ARE-CORRECT Pass
Start: GRAPH-CONTAINER-TEST
run: TEST-EMPTY! Pass
run: NO-VERTEX-TEST Pass
run: VERTEX-TEST Pass
Start: TEST-ROOTP
run: DIRECTED-EDGES Pass
run: TEST-SOURCE-VERTEX Pass
run: TEST-SINK-VERTEX Pass
run: TEST-MIDDLE-VERTEX Pass
Start: TEST-BASIC-GRAPH-PROPERTIES
run: TEST-1 Pass
run: TEST-2 Pass
run: TEST-3 Pass
Start: TEST-CHANGE-VERTEX-VALUE
run: TEST-UNDIRECTED Pass
Start: TEST-REPLACE-VERTEX
run: TEST-DIRECTED Pass
run: TEST-UNDIRECTED Pass
Start: TEST-TEST-VERTEX
run: TEST-1 Fail
run: TEST-2;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Error while running (CL-GRAPH-TEST) from /gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-graph/lift-standard.config: The slot CL-GRAPH:GRAPH-VERTEXES is unbound in the object .
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Unhandled UNBOUND-SLOT in thread #<SB-THREAD:THREAD "main thread" RUNNING {100B150123}>:
Backtrace for: #<SB-THREAD:THREAD "main thread" RUNNING {100B150123}>
0: (SB-DEBUG::DEBUGGER-DISABLED-HOOK #<UNBOUND-SLOT GRAPH-VERTEXES {1001C4EA13}> #<unused argument> :QUIT T)
1: (SB-DEBUG::RUN-HOOK *INVOKE-DEBUGGER-HOOK* #<UNBOUND-SLOT GRAPH-VERTEXES {1001C4EA13}>)
2: (INVOKE-DEBUGGER #<UNBOUND-SLOT GRAPH-VERTEXES {1001C4EA13}>)
3: (ERROR #<UNBOUND-SLOT GRAPH-VERTEXES {1001C4EA13}>)
4: (SB-KERNEL:WITH-SIMPLE-CONDITION-RESTARTS ERROR NIL UNBOUND-SLOT :NAME CL-GRAPH:GRAPH-VERTEXES :INSTANCE #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D06713}>>)
5: ((:METHOD SLOT-UNBOUND (T T T)) #<unused argument> #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D08723}>> CL-GRAPH:GRAPH-VERTEXES) [fast-method]
6: (SB-PCL::SLOT-UNBOUND-INTERNAL #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D0A613}>> 0)
7: ((:METHOD METABANG.UTILITIES:SIZE (CL-GRAPH:BASIC-GRAPH)) #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D0C313}>>) [fast-method]
8: ((FLET "THUNK" :IN PRINT-OBJECT))
9: ((FLET SB-IMPL::PRINT-DESCRIPTION :IN SB-IMPL::%PRINT-UNREADABLE-OBJECT))
10: (SB-IMPL::%PRINT-UNREADABLE-OBJECT #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D186A3}>> #<BROADCAST-STREAM {1000020C73}> 3 #<FUNCTION (FLET "THUNK" :IN PRINT-OBJECT) {7FFFF745B75B}>)
11: ((:METHOD PRINT-OBJECT (CL-GRAPH:BASIC-GRAPH T)) #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D1AA63}>> #<BROADCAST-STREAM {1000020C73}>) [fast-method]
12: ((LABELS SB-IMPL::HANDLE-IT :IN SB-KERNEL:OUTPUT-OBJECT) #<BROADCAST-STREAM {1000020C73}>)
13: ((LABELS SB-IMPL::CHECK-IT :IN SB-KERNEL:OUTPUT-OBJECT) #<SB-PRETTY:PRETTY-STREAM {1001C4E663}>)
14: (SB-INT:%WRITE #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D1F543}>> #<SB-PRETTY:PRETTY-STREAM {1001C4E663}>)
15: ((FLET "PPRINT-BLOCK" :IN SB-DEBUG::PRINT-FRAME-CALL) #<unused argument> #<SB-PRETTY:PRETTY-STREAM {1001C4E663}>)
16: ((FLET "WITH-PRETTY-STREAM0" :IN SB-PRETTY::CALL-LOGICAL-BLOCK-PRINTER) #<SB-PRETTY:PRETTY-STREAM {1001C4E663}>)
17: (SB-PRETTY::CALL-LOGICAL-BLOCK-PRINTER #<FUNCTION (FLET "PPRINT-BLOCK" :IN SB-DEBUG::PRINT-FRAME-CALL) {7FFFF745BB3B}> #<SB-IMPL::STRING-OUTPUT-STREAM {7FFFF745C263}> "(" NIL ")" NIL)
18: (SB-DEBUG::PRINT-FRAME-CALL #<SB-DI::COMPILED-FRAME SB-KERNEL:WITH-SIMPLE-CONDITION-RESTARTS> #<SB-IMPL::STRING-OUTPUT-STREAM {7FFFF745C263}> :PRINT-FRAME-SOURCE NIL :NUMBER 5 :METHOD-FRAME-STYLE :NORMAL :EMERGENCY-BEST-EFFORT NIL)
19: ((FLET "LAMBDA0" :IN "SYS:SRC;CODE;DEBUG.LISP") #<SB-DI::COMPILED-FRAME SB-KERNEL:WITH-SIMPLE-CONDITION-RESTARTS>)
20: (MAP-BACKTRACE #<FUNCTION (FLET "LAMBDA0" :IN "SYS:SRC;CODE;DEBUG.LISP") {7FFFF745BEAB}> :START 0 :FROM #<SB-DI::COMPILED-FRAME LIFT::GET-BACKTRACE-AS-STRING> :COUNT 4611686018427387903)
21: ((FLET "THUNK4" :IN PRINT-BACKTRACE))
22: ((LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX))
23: (SB-IMPL::CALL-WITH-SANE-IO-SYNTAX #<FUNCTION (LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX) {1001C47AFB}>)
24: (SB-IMPL::%WITH-STANDARD-IO-SYNTAX #<FUNCTION (FLET "THUNK" :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX) {7FFFF745C07B}>)
25: (SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX #<FUNCTION (FLET "THUNK4" :IN PRINT-BACKTRACE) {7FFFF745C11B}>)
26: (PRINT-BACKTRACE :STREAM #<SB-IMPL::STRING-OUTPUT-STREAM {7FFFF745C263}> :START 0 :FROM :DEBUGGER-FRAME :COUNT 4611686018427387903 :PRINT-THREAD T :PRINT-FRAME-SOURCE NIL :METHOD-FRAME-STYLE NIL :EMERGENCY-BEST-EFFORT NIL)
27: (LIFT::GET-BACKTRACE-AS-STRING #<unused argument>)
28: (LIFT::HANDLE-ERROR-WHILE-TESTING #<UNBOUND-SLOT GRAPH-VERTEXES {1001C47853}> LIFT::TESTSUITE-ERROR CL-GRAPH-TEST::TEST-TEST-VERTEX #<Results for /gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-graph/lift-standard.con
fig 18 Tests, 1 Failure, 1 Error>)
29: ((FLET "H1" :IN LIFT::DO-TESTING-IN-ENVIRONMENT) #<UNBOUND-SLOT GRAPH-VERTEXES {1001C47853}>)
30: (SB-KERNEL::%SIGNAL #<UNBOUND-SLOT GRAPH-VERTEXES {1001C47853}>)
31: (ERROR #<UNBOUND-SLOT GRAPH-VERTEXES {1001C47853}>)
32: (SB-KERNEL:WITH-SIMPLE-CONDITION-RESTARTS ERROR NIL UNBOUND-SLOT :NAME CL-GRAPH:GRAPH-VERTEXES :INSTANCE #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D396C3}>>)
33: ((:METHOD SLOT-UNBOUND (T T T)) #<unused argument> #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D3B543}>> CL-GRAPH:GRAPH-VERTEXES) [fast-method]
34: (SB-PCL::SLOT-UNBOUND-INTERNAL #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D3CF43}>> 0)
35: ((:METHOD METABANG.UTILITIES:SIZE (CL-GRAPH:BASIC-GRAPH)) #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D3EB33}>>) [fast-method]
36: ((FLET "THUNK" :IN PRINT-OBJECT))
37: ((FLET SB-IMPL::PRINT-DESCRIPTION :IN SB-IMPL::%PRINT-UNREADABLE-OBJECT))
38: (SB-IMPL::%PRINT-UNREADABLE-OBJECT #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D426B3}>> #<BROADCAST-STREAM {1000020C73}> 3 #<FUNCTION (FLET "THUNK" :IN PRINT-OBJECT) {7FFFF745C92B}>)
39: ((:METHOD PRINT-OBJECT (CL-GRAPH:BASIC-GRAPH T)) #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D44903}>> #<BROADCAST-STREAM {1000020C73}>) [fast-method]
40: ((LABELS SB-IMPL::HANDLE-IT :IN SB-KERNEL:OUTPUT-OBJECT) #<BROADCAST-STREAM {1000020C73}>)
41: ((LABELS SB-IMPL::CHECK-IT :IN SB-KERNEL:OUTPUT-OBJECT) #<SB-PRETTY:PRETTY-STREAM {1001C47053}>)
42: (SB-INT:%WRITE #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D48E73}>> #<SB-PRETTY:PRETTY-STREAM {1001C47053}>)
43: ((FLET "PPRINT-BLOCK" :IN SB-DEBUG::PRINT-FRAME-CALL) #<unused argument> #<SB-PRETTY:PRETTY-STREAM {1001C47053}>)
44: ((FLET "WITH-PRETTY-STREAM0" :IN SB-PRETTY::CALL-LOGICAL-BLOCK-PRINTER) #<SB-PRETTY:PRETTY-STREAM {1001C47053}>)
45: (SB-PRETTY::CALL-LOGICAL-BLOCK-PRINTER #<FUNCTION (FLET "PPRINT-BLOCK" :IN SB-DEBUG::PRINT-FRAME-CALL) {7FFFF745CD0B}> #<SB-IMPL::STRING-OUTPUT-STREAM {7FFFF745D433}> "(" NIL ")" NIL)
46: (SB-DEBUG::PRINT-FRAME-CALL #<SB-DI::COMPILED-FRAME (SB-PCL::FAST-METHOD INITIALIZE-INSTANCE :AFTER (CL-GRAPH:BASIC-GRAPH))> #<SB-IMPL::STRING-OUTPUT-STREAM {7FFFF745D433}> :PRINT-FRAME-SOURCE NIL :NUMBER 9 :METHOD-FRAME-STYLE :NORMAL :EMERGENCY-BEST-EFFORT NIL)
47: ((FLET "LAMBDA0" :IN "SYS:SRC;CODE;DEBUG.LISP") #<SB-DI::COMPILED-FRAME (SB-PCL::FAST-METHOD INITIALIZE-INSTANCE :AFTER (CL-GRAPH:BASIC-GRAPH))>)
48: (MAP-BACKTRACE #<FUNCTION (FLET "LAMBDA0" :IN "SYS:SRC;CODE;DEBUG.LISP") {7FFFF745D07B}> :START 0 :FROM #<SB-DI::COMPILED-FRAME LIFT::GET-BACKTRACE-AS-STRING> :COUNT 4611686018427387903)
49: ((FLET "THUNK4" :IN PRINT-BACKTRACE))
50: ((LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX))
51: (SB-IMPL::CALL-WITH-SANE-IO-SYNTAX #<FUNCTION (LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX) {1001C3924B}>)
52: (SB-IMPL::%WITH-STANDARD-IO-SYNTAX #<FUNCTION (FLET "THUNK" :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX) {7FFFF745D24B}>)
53: (SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX #<FUNCTION (FLET "THUNK4" :IN PRINT-BACKTRACE) {7FFFF745D2EB}>)
54: (PRINT-BACKTRACE :STREAM #<SB-IMPL::STRING-OUTPUT-STREAM {7FFFF745D433}> :START 0 :FROM :DEBUGGER-FRAME :COUNT 4611686018427387903 :PRINT-THREAD T :PRINT-FRAME-SOURCE NIL :METHOD-FRAME-STYLE NIL :EMERGENCY-BEST-EFFORT NIL)
55: (LIFT::GET-BACKTRACE-AS-STRING #<unused argument>)
56: (LIFT::HANDLE-ERROR-WHILE-TESTING #<SIMPLE-ERROR "Unknown :TEST for MAKE-HASH-TABLE: ~S" {1001C38EE3}> LIFT::TEST-ERROR CL-GRAPH-TEST::TEST-TEST-VERTEX #<Results for /gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-gra
ph/lift-standard.config 18 Tests, 1 Failure, 1 Error>)
57: ((FLET "H1" :IN LIFT::RUN-TEST-INTERNAL) #<SIMPLE-ERROR "Unknown :TEST for MAKE-HASH-TABLE: ~S" {1001C38EE3}>)
58: (SB-KERNEL::%SIGNAL #<SIMPLE-ERROR "Unknown :TEST for MAKE-HASH-TABLE: ~S" {1001C38EE3}>)
59: (ERROR "Unknown :TEST for MAKE-HASH-TABLE: ~S" =)
60: (MAKE-HASH-TABLE :TEST = :SIZE 7 :REHASH-SIZE 1.5 :REHASH-THRESHOLD 1 :HASH-FUNCTION NIL :WEAKNESS NIL :SYNCHRONIZED NIL)
61: ((:METHOD INITIALIZE-INSTANCE :AFTER (METABANG.CL-CONTAINERS::USES-CONTENTS-MIXIN)) #<METABANG.CL-CONTAINERS:SIMPLE-ASSOCIATIVE-CONTAINER {1001C38E93}> :INITIAL-SIZE 25 :TEST =) [fast-method]
62: ((SB-PCL::EMF INITIALIZE-INSTANCE) #<unused argument> #<unused argument> #<METABANG.CL-CONTAINERS:SIMPLE-ASSOCIATIVE-CONTAINER {1001C38E93}> :INITIAL-SIZE 25 :TEST =)
63: ((:METHOD MAKE-INSTANCE (CLASS)) #<STANDARD-CLASS METABANG.CL-CONTAINERS:SIMPLE-ASSOCIATIVE-CONTAINER> :INITIAL-SIZE 25 :TEST =) [fast-method]
64: ((:METHOD INITIALIZE-INSTANCE :AFTER (CL-GRAPH:BASIC-GRAPH)) #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D767F3}>> :INITIAL-SIZE 25) [fast-method]
65: ((SB-PCL::EMF INITIALIZE-INSTANCE) #<unused argument> #<unused argument> #<CL-GRAPH:GRAPH-CONTAINER #<error printing a CL-GRAPH:GRAPH-CONTAINER: #<UNBOUND-SLOT GRAPH-VERTEXES {1001D78C73}>> :VERTEX-TEST = :VERTEX-CLASS CL-GRAPH:GRAPH-CONTAINER-VERTEX :DIRECTED-EDGE-CLAS
S CL-GRAPH:GRAPH-CONTAINER-DIRECTED-EDGE :UNDIRECTED-EDGE-CLASS CL-GRAPH:GRAPH-CONTAINER-UNDIRECTED-EDGE :INITIAL-SIZE 25)
66: ((:METHOD MAKE-INSTANCE (CLASS)) #<STANDARD-CLASS CL-GRAPH:GRAPH-CONTAINER> :VERTEX-TEST = :VERTEX-CLASS CL-GRAPH:GRAPH-CONTAINER-VERTEX :DIRECTED-EDGE-CLASS CL-GRAPH:GRAPH-CONTAINER-DIRECTED-EDGE :UNDIRECTED-EDGE-CLASS CL-GRAPH:GRAPH-CONTAINER-UNDIRECTED-EDGE :INITIAL-
SIZE 25) [fast-method]
67: ((LAMBDA (LIFT::TESTSUITE) :IN #:DROP-THRU-TAG-2) #<unused argument>)
68: (LIFT::RUN-TEST-INTERNAL #<CL-GRAPH-TEST::TEST-TEST-VERTEX TEST-TEST-VERTEX {1001BDECF3}> CL-GRAPH-TEST::TEST-2 #<Results for /gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-graph/lift-standard.config 18 Tests, 1 Fail
ure, 1 Error>)
69: (LIFT::TESTSUITE-RUN #<CL-GRAPH-TEST::TEST-TEST-VERTEX TEST-TEST-VERTEX {1001BDECF3}> #<Results for /gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-graph/lift-standard.config 18 Tests, 1 Failure, 1 Error>)
70: ((:METHOD LIFT::DO-TESTING (LIFT:TEST-MIXIN T T)) #<unused argument> #<Results for /gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-graph/lift-standard.config 18 Tests, 1 Failure, 1 Error> #<FUNCTION (LAMBDA NIL :IN LI
FT::RUN-TESTS-INTERNAL) {1001B6EBFB}>) [fast-method]
71: (LIFT::DO-TESTING-IN-ENVIRONMENT CL-GRAPH-TEST::TEST-TEST-VERTEX #<Results for /gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-graph/lift-standard.config 18 Tests, 1 Failure, 1 Error> #<FUNCTION (LAMBDA NIL :IN LIFT::
RUN-TESTS-INTERNAL) {1001B6EBFB}>)
72: (LIFT::RUN-TESTS-INTERNAL CL-GRAPH-TEST #<Results for /gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-graph/lift-standard.config 18 Tests, 1 Failure, 1 Error>)
73: (LIFT:RUN-TESTS :RESULT #<Results for /gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-graph/lift-standard.config 18 Tests, 1 Failure, 1 Error>)
74: (LIFT::%RUN-TESTS-FROM-FILE #P"/gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-graph/lift-standard.config")
75: (LIFT::RUN-TESTS-FROM-FILE #P"/gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-graph/lift-standard.config")
76: (LIFT:RUN-TESTS)
77: ((SB-PCL::EMF ASDF/ACTION:PERFORM) #<unused argument> #<unused argument> #<ASDF/LISP-ACTION:TEST-OP > #<ASDF/SYSTEM:SYSTEM "cl-graph">)
78: ((LAMBDA NIL :IN ASDF/ACTION:CALL-WHILE-VISITING-ACTION))
79: ((:METHOD ASDF/ACTION:PERFORM :AROUND (ASDF/LISP-ACTION:TEST-OP ASDF/SYSTEM:SYSTEM)) #<ASDF/LISP-ACTION:TEST-OP > #<ASDF/SYSTEM:SYSTEM "cl-graph">) [fast-method]
80: ((:METHOD ASDF/ACTION:PERFORM-WITH-RESTARTS :AROUND (T T)) #<ASDF/LISP-ACTION:TEST-OP > #<ASDF/SYSTEM:SYSTEM "cl-graph">) [fast-method]
81: ((:METHOD ASDF/PLAN:PERFORM-PLAN (T)) #<ASDF/PLAN:SEQUENTIAL-PLAN {10059C5223}>) [fast-method]
82: ((FLET SB-C::WITH-IT :IN SB-C::%WITH-COMPILATION-UNIT))
83: ((:METHOD ASDF/PLAN:PERFORM-PLAN :AROUND (T)) #<ASDF/PLAN:SEQUENTIAL-PLAN {10059C5223}>) [fast-method]
84: ((:METHOD ASDF/OPERATE:OPERATE (ASDF/OPERATION:OPERATION ASDF/COMPONENT:COMPONENT)) #<ASDF/LISP-ACTION:TEST-OP > #<ASDF/SYSTEM:SYSTEM "cl-graph"> :PLAN-CLASS NIL :PLAN-OPTIONS NIL) [fast-method]
85: ((SB-PCL::EMF ASDF/OPERATE:OPERATE) #<unused argument> #<unused argument> #<ASDF/LISP-ACTION:TEST-OP > #<ASDF/SYSTEM:SYSTEM "cl-graph">)
86: ((LAMBDA NIL :IN ASDF/OPERATE:OPERATE))
87: ((:METHOD ASDF/OPERATE:OPERATE :AROUND (T T)) #<ASDF/LISP-ACTION:TEST-OP > #<ASDF/SYSTEM:SYSTEM "cl-graph">) [fast-method]
88: ((SB-PCL::EMF ASDF/OPERATE:OPERATE) #<unused argument> #<unused argument> ASDF/LISP-ACTION:TEST-OP "cl-graph")
89: ((LAMBDA NIL :IN ASDF/OPERATE:OPERATE))
90: ((:METHOD ASDF/OPERATE:OPERATE :AROUND (T T)) ASDF/LISP-ACTION:TEST-OP "cl-graph") [fast-method]
91: (ASDF/SESSION:CALL-WITH-ASDF-SESSION #<FUNCTION (LAMBDA NIL :IN ASDF/OPERATE:OPERATE) {100488E59B}> :OVERRIDE T :KEY NIL :OVERRIDE-CACHE T :OVERRIDE-FORCING NIL)
92: ((LAMBDA NIL :IN ASDF/OPERATE:OPERATE))
93: (ASDF/SESSION:CALL-WITH-ASDF-SESSION #<FUNCTION (LAMBDA NIL :IN ASDF/OPERATE:OPERATE) {100372649B}> :OVERRIDE NIL :KEY NIL :OVERRIDE-CACHE NIL :OVERRIDE-FORCING NIL)
94: ((:METHOD ASDF/OPERATE:OPERATE :AROUND (T T)) ASDF/LISP-ACTION:TEST-OP "cl-graph") [fast-method]
95: (ASDF/OPERATE:TEST-SYSTEM "cl-graph")
96: (SB-INT:SIMPLE-EVAL-IN-LEXENV (ASDF/OPERATE:TEST-SYSTEM "cl-graph") #<NULL-LEXENV>)
97: (EVAL (ASDF/OPERATE:TEST-SYSTEM "cl-graph"))
98: (SB-IMPL::PROCESS-EVAL/LOAD-OPTIONS ((:EVAL . "(require :asdf)") (:EVAL . #<(SIMPLE-ARRAY CHARACTER (259)) (asdf:initialize-source-registry (list :source-registry (list :tree (uiop:ensure-pathname "/gnu/store/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb78
67/share/common-lisp/sbcl/cl-graph" :... {100B26CE4F}>) (:EVAL . "(asdf:test-system \"cl-graph\")") (:EVAL . "(asdf:test-system \"cl-graph+hu.dwim.graphviz\")") (:EVAL . "(asdf:test-system \"cl-graph-test\")") (:QUIT)))
99: (SB-IMPL::TOPLEVEL-INIT)
100: ((FLET SB-UNIX::BODY :IN SB-IMPL::START-LISP))
101: ((FLET "WITHOUT-INTERRUPTS-BODY-3" :IN SB-IMPL::START-LISP))
102: (SB-IMPL::%START-LISP)
unhandled condition in --disable-debugger mode, quitting
;
; compilation unit aborted
; caught 1 fatal ERROR condition
error: in phase 'check': uncaught exception:
%exception #<&invoke-error program: "/gnu/store/3pz3jlghd94sgw0iwi16hg5r5dhxzkdk-sbcl-2.2.10/bin/sbcl" arguments: ("--non-interactive" "--eval" "(require :asdf)" "--eval" "(asdf:initialize-source-registry (list :source-registry (list :tree (uiop:ensure-pathname \"/gnu/store
/dqqh97x08prdlskhcw0p4b9ybx81i6v6-sbcl-cl-graph-0.10.2-1.3cb7867/share/common-lisp/sbcl/cl-graph\" :truenamize t :ensure-directory t)) :inherit-configuration))" "--eval" "(asdf:test-system \"cl-graph\")" "--eval" "(asdf:test-system \"cl-graph+hu.dwim.graphviz\")" "--eval" "
(asdf:test-system \"cl-graph-test\")") exit-status: 1 term-signal: #f stop-signal: #f>
phase `check' failed after 0.4 seconds
I'm trying to run the example in the documentation (https://common-lisp.net/project/cl-graph/user-guide.html#header3-18):
(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)) and I'm getting the following error:
There is no applicable method for the generic function
#<STANDARD-GENERIC-FUNCTION DOT-ATTRIBUTE-VALUE (1)>
when called with arguments
(:LABEL #<GRAPH-CONTAINER-DIRECTED-EDGE <#<A> #<B> NIL>>).
Has anything changed?
My old code that used cl-graph and dot export is failing with the same error and I just discovered that the example in the documentation doesn't work either.
Any idea as to why this fails?
Thanks!
I had a problem with topological-sort hanging, which I traced to the implementation of assign-level. In the worst case this can take exponential time (in the number of vertexes) on a directed acyclic graph.
I have a linear time implementation of topological sort I will be uploading to a branch when I have time. I doesn't use assign-level. Depth can be computed from the topological sort in linear time. Can assign-level be removed from the api?
The depth function doesn't seem to be working; it always reports 0 for depth.
Example:
(setq g (let ((g (make-container 'graph-container)))
(loop for v in '(a b c d e) do
(add-vertex g v))
(loop for (v1 . v2) in '((a . b) (a . c) (b . d) (c . e)) do
(add-edge-between-vertexes g v1 v2))
g))
(depth g)
0From the API description, this should return 2, should it not?
I'm running CCL on MacOSX using cl-graph with quicklisp.
(many thanks for the library, btw!)
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.