hraban / cl-graph Goto Github PK

Common Lisp library for manipulating graphs and running graph algorithms

Home Page: http://common-lisp.net/project/cl-graph/

License: Other

Common Lisp 95.37% CSS 1.12% Mermaid 3.51%

cl-graph's Issues

asdf-system-connections

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.

Interest in thread-safe cl-graph?

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.

Configure vertex equality check

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.

In graph.lisp in-undirected-cycle-p is not correct

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))

Graphviz dot export broken?

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!

Failing test : The slot CL-GRAPH:GRAPH-VERTEXES is unbound in the object

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

Incorrect methods has-parent-p, has-children-p

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
``

(depth g) doesn't report correctly

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)
0

From 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!)

assign-level may take exponential time

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?

trying to understand why graph->dot is failing

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?

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 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.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

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.