# HG changeset patch # User Steve Losh # Date 1615771967 14400 # Node ID 55507a7c499d6433d3098d9555eadc7b85942967 # Parent d61bb4fbe61d31f8d942d4908fcab997ec6d0a12 cl-digraph: Update site. diff -r d61bb4fbe61d -r 55507a7c499d cl-digraph/changelog/index.html --- a/cl-digraph/changelog/index.html Sun Feb 21 12:18:04 2021 -0500 +++ b/cl-digraph/changelog/index.html Sun Mar 14 21:32:47 2021 -0400 @@ -15,6 +15,8 @@

Changelog

Here's the list of changes in each released version.

+

v1.4.0

+

Added an explicit condition hierarchy.

+

v1.3.2

+

Fixed a bug where certain kinds of +cycles were not correctly detected during topological sorting.

v1.3.1

Fixed a bug for recent SBCL versions when creating a digraph without a custom hash function.

diff -r d61bb4fbe61d -r 55507a7c499d cl-digraph/reference/index.html --- a/cl-digraph/reference/index.html Sun Feb 21 12:18:04 2021 -0500 +++ b/cl-digraph/reference/index.html Sun Mar 14 21:32:47 2021 -0400 @@ -30,6 +30,7 @@
  • DEGREE-IN (function)
  • DEGREE-OUT (function)
  • DIGRAPH (class)
    • +
  • DIGRAPH-ERROR (class)
  • EDGES (function)
  • EMPTYP (function)
  • INSERT-EDGE (function)
    • @@ -45,6 +46,9 @@
  • MAPC-DEPTH-FIRST (function)
  • MAPC-EDGES (function)
  • MAPC-VERTICES (function)
    • +
  • MISSING-PREDECESSOR (class)
    • +
  • MISSING-SUCCESSOR (class)
    • +
  • MISSING-VERTEX (class)
  • NEIGHBORS (function)
  • PREDECESSORS (function)
  • REACHABLEP (function)
    • @@ -54,6 +58,8 @@
  • ROOTS (function)
  • SUCCESSORS (function)
  • TOPOLOGICAL-SORT (function)
    • +
  • TOPOLOGICAL-SORT-CYCLE (class)
    • +
  • VERTEX-INVOLVED (generic function)
  • VERTICES (function)
    • @@ -117,6 +123,8 @@

    Return the number of successors of vertex.

    DIGRAPH (class)

    A directed graph. Use make-digraph to create one.

    +

    DIGRAPH-ERROR (class)

    +

    Base condition for digraph-related errors.

    EDGES (function)

    (EDGES DIGRAPH)
    @@ -136,9 +144,12 @@

    Insert an edge from predecessor to successor if not already present.

    -

    The predecessor and successor vertices must exist in the graph already.

    Returns t if the edge was already in the graph, or nil if it was inserted.

    +

    The predecessor and successor vertices must already exist in the graph. + If predecessor is not in the graph a missing-predecessor error will be + signaled. Otherwise, if successor is not in the graph, a missing-successor + error will be signaled.

    INSERT-VERTEX (function)

    (INSERT-VERTEX DIGRAPH VERTEX)
    @@ -250,6 +261,14 @@

    Call function on each vertex in digraph.

    The order in which the vertices are processed is unspecified.

    Returns nil.

    +

    MISSING-PREDECESSOR (class)

    +

    An error signaled when trying to insert an edge whose predecessor is not in the graph.

    +

    vertex-involved can be used to retrieve the offending predecessor.

    +

    MISSING-SUCCESSOR (class)

    +

    An error signaled when trying to insert an edge whose successor is not in the graph.

    +

    vertex-involved can be used to retrieve the offending successor.

    +

    MISSING-VERTEX (class)

    +

    Base condition for errors signaled when inserting an edge with a vertex missing.

    NEIGHBORS (function)

    (NEIGHBORS DIGRAPH VERTEX)
    @@ -318,7 +337,18 @@ depends on B" and that B must come before A in the resulting list. Aside from this restriction, the order of the resulting list is arbitrary.

    The order in which the vertices are processed is unspecified.

    -

    An error will be signaled if the graph contains a cycle.

    +

    A topological-sort-cycle error will be signaled if the graph contains + a cycle.

    +

    TOPOLOGICAL-SORT-CYCLE (class)

    +

    An error signaled when topologically sorting a graph that contains a cycle.

    +

    vertex-involved can be used to retrieve one of the vertices involved in a + cycle. Which vertex in the cycle is chosen is arbitrary.

    +

    VERTEX-INVOLVED (generic function)

    +
    (VERTEX-INVOLVED CONDITION)
+
    + + +

    Retrieve the vertex involved in the condition.

    VERTICES (function)

    (VERTICES DIGRAPH)
    diff -r d61bb4fbe61d -r 55507a7c499d cl-digraph/static/conditions.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cl-digraph/static/conditions.svg Sun Mar 14 21:32:47 2021 -0400 @@ -0,0 +1,67 @@ + + + + + + +%3 + + + +5 + +TOPOLOGICAL-SORT-CYCLE + + + +1 + +DIGRAPH-ERROR + + + +5->1 + + + + + +4 + +MISSING-SUCCESSOR + + + +2 + +MISSING-VERTEX + + + +4->2 + + + + + +3 + +MISSING-PREDECESSOR + + + +3->2 + + + + + +2->1 + + + + + diff -r d61bb4fbe61d -r 55507a7c499d cl-digraph/static/errors.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cl-digraph/static/errors.svg Sun Mar 14 21:32:47 2021 -0400 @@ -0,0 +1,67 @@ + + + + + + +%3 + + + +5 + +TOPOLOGICAL-SORT-CYCLE + + + +1 + +DIGRAPH-ERROR + + + +5->1 + + + + + +4 + +MISSING-SUCCESSOR + + + +2 + +MISSING-VERTEX + + + +4->2 + + + + + +3 + +MISSING-PREDECESSOR + + + +3->2 + + + + + +2->1 + + + + + diff -r d61bb4fbe61d -r 55507a7c499d cl-digraph/usage/index.html --- a/cl-digraph/usage/index.html Sun Feb 21 12:18:04 2021 -0500 +++ b/cl-digraph/usage/index.html Sun Mar 14 21:32:47 2021 -0400 @@ -34,6 +34,7 @@
  • Topological Sorting
    • +
  • Conditions
  • Drawing

    • Package

    @@ -43,8 +44,7 @@

    Creating Digraphs

    Digraphs can be created with make-digraph:

    (digraph:make-digraph)
-; =>
-#<DIGRAPH:DIGRAPH () {1002CFD343}>
+; => #<DIGRAPH:DIGRAPH () {1002CFD343}>
    @@ -185,10 +185,18 @@ ; => ((a . b)) (digraph:insert-edge *d* 'cats 'dogs) -; => Error! +; => +; Cannot add edge with predecessor CATS because it is not in the graph +; [Condition of type DIGRAPH::MISSING-PREDECESSOR] +; +; Restarts: +; R 0. CONTINUE - Retry assertion with new value for DIGRAPH::PREDECESSOR. +; R 1. ABORT - Exit debugger, returning to top level. +

    See the Conditions section for more information about the error +hierarchy.

    Edges can be removed with remove-edge. Removing an edge that's not in the graph is silently ignored:

    (defparameter *d*
@@ -335,12 +343,64 @@
 
 (digraph:topological-sort *d*)
 ; => one of
-(C B A D)
-(B C A D)
+; (C B A D)
+; (B C A D)
+
    + + +

    A digraph:topological-sort-cycle will be signaled if the digraph +contains a cycle:

    +
    (defparameter *d*
+  (digraph:make-digraph :initial-vertices '(a b c d)))
+
+(digraph:insert-edge *d* 'a 'b) ; a depends on b
+(digraph:insert-edge *d* 'b 'c) ; b depends on c
+(digraph:insert-edge *d* 'c 'a) ; c depends on a
+
+(digraph:topological-sort *d*)
+; =>
+; Cycle detected during topological sort involving vertex A
+;     [Condition of type DIGRAPH:TOPOLOGICAL-SORT-CYCLE]
+;
+; Restarts:
+;   R 0. ABORT - Exit debugger, returning to top level.
    -

    An error will be signaled if the digraph contains a cycle.

    +

    See the Conditions section for more information about the error +hierarchy.

    +

    Conditions

    +

    The following condition types are defined by cl-digraph:

    +

    condition type hierarchy

    +

    Dotted outlines denote abstract types that are never actually instantiated, but +can be useful for handling whole classes of errors.

    + +

    For missing-vertex errors of both kinds you can use the vertex-involved +reader to retrieve the offending vertex from the condition object.

    +

    For topological-sort-cycle errors you can use the vertex-involved reader to +retrieve one of the vertices involved in a cycle from the condition object. +Which vertex of the cycle is returned is arbitrary:

    +
    (defparameter *d*
+  (digraph:make-digraph :initial-vertices '(a b c d)))
+
+(digraph:insert-edge *d* 'a 'b) ; a depends on b
+(digraph:insert-edge *d* 'b 'c) ; b depends on c
+(digraph:insert-edge *d* 'c 'a) ; c depends on a
+
+(handler-case (digraph:topological-sort *d*)
+  (digraph:topological-sort-cycle-error (c)
+    (list :cyclic (digraph:vertex-involved c))))
+; =>
+; (:CYCLIC A)
+
    + +

    Drawing

    If you have Graphviz installed, you can draw digraph objects to images with the cl-dot library by loading the optional cl-digraph.dot system: