Plaster

(defpackage #:org.euouae.package-generator.graph.interface (:use #:cl) (:export #:add-edge #:add-vertex #:breadth-first-search #:components #:cycle #:depth-first-search #:edgep #:edges #:graph #:neighbors #:path #:remove-edge #:remove-vertex #:vertexp #:vertices)) (in-package #:org.euouae.package-generator.graph.interface) (defclass graph () ()) (defgeneric vertices (graph) (:documentation "Sequence of vertices of GRAPH.")) (defgeneric edges (graph) (:documentation "Sequence of edges of GRAPH.")) (defgeneric neighbors (graph vertex) (:documentation "Sequence of neighbors of VERTEX in GRAPH.")) (defgeneric add-vertex (graph vertex) (:documentation "Add VERTEX to GRAPH.")) (defgeneric delete-vertex (graph vertex) (:documentation "Delete VERTEX from GRAPH.")) (defgeneric vertexp (graph vertex) (:documentation "True if VERTEX is a vertex of GRAPH.")) (defgeneric add-edge (graph u v) (:documentation "Add an edge with vertices U, V in GRAPH. Neither U nor V need to be vertices of GRAPH beforehand.")) (defgeneric delete-edge (graph u v) (:documentation "Delete the edge with vertices U, V from GRAPH.")) (defgeneric edgep (graph u v) (:documentation "True if there is an edge with vertices U, V in GRAPH.")) (defgeneric depth-first-search (graph function vertex) (:documentation "Depth-first search applying FUNCTION on GRAPH vertices starting from VERTEX. FUNCTION takes two arguments, SOURCE and TARGET. When applied on the first vertex, which is VERTEX, SOURCE is `nil'. Then, for every successful invocation, SOURCE is the previous vertex in the search and TARGET is the current vertex. For this reason, there should not be a `nil' vertex in GRAPH.")) (defgeneric breadth-first-search (graph function vertex) (:documentation "Breadth-first search applying FUNCTION on GRAPH vertices starting from VERTEX.")) (defgeneric path (graph u v) (:documentation "A shortest sequence of vertices forming edges from U to V in GRAPH")) (defgeneric components (graph) (:documentation "A sequence of sequences of vertices of GRAPH representing its connected components.")) (defgeneric cycle (graph) (:documentation "A sequence of vertices forming edges of GRAPH making a cycle.")) (defgeneric span (graph vertices) (:documentation "The subgraph spanned by VERTICES in GRAPH."))