Improved efficiency of edge-count for graphs in general (from (length (graph-edges...

[cl-graph.git] / dev / graph.lisp

diff --git a/dev/graph.lisp b/dev/graph.lisp
index 32a9bd6..b2c1cf3 100644 (file)
--- a/dev/graph.lisp
+++ b/dev/graph.lisp
@@ -87,11 +87,6 @@ something is putting something on the vertexes plist's
 
 ;;; ---------------------------------------------------------------------------
 
-#+COPYING
-(defcopy-methods basic-vertex :copy-all t)
-
-;;; ---------------------------------------------------------------------------
-
 (defmethod initialize-instance :after ((object basic-vertex) &key graph vertex-id)
   (when (and graph (not vertex-id))
     (setf (slot-value object 'vertex-id)
@@ -116,7 +111,6 @@ something is putting something on the vertexes plist's
    (color nil ia "The `color` is used by some algorithms for bookkeeping. [?? Should probably be in a mixin]"))
   (:export-p t)
   (:export-slots edge-id element tag color)
-  #+COPYING :copy-slots
   (:make-load-form-p t)
   (:documentation "This is the root class for all edges in CL-Graph."))
 
@@ -136,15 +130,14 @@ something is putting something on the vertexes plist's
 
 ;;; ---------------------------------------------------------------------------
 
-(defclass* directed-edge-mixin (#+COPYING copyable-mixin) ()
+(defclass* directed-edge-mixin () ()
   (:export-p t)
   (:documentation "This mixin class is used to indicate that an edge is directed."))
 
 ;;; ---------------------------------------------------------------------------
 
-(defclass* weighted-edge-mixin (#+COPYING copyable-mixin)
+(defclass* weighted-edge-mixin ()
   ((weight 1d0 ia "The value of the weight of this edge. Defaults to 1.0d0"))
-  #+COPYING :copy-slots
   :export-slots
   (:export-p t)
   (:documentation "This mixin class adds a `weight` slot to an edge."))
@@ -155,17 +148,17 @@ something is putting something on the vertexes plist's
 
 ;;; ---------------------------------------------------------------------------
 
-(defclass* basic-graph (#+COPYING copyable-mixin)
+(defclass* basic-graph ()
   ((graph-vertexes :unbound ir)
    (graph-edges :unbound ir)
    (largest-vertex-id 0 r)
    (largest-edge-id 0 r)
    (vertex-class 'basic-vertex ir
-                 "The class of the vertexes in the graph.")
+                 "The class of the vertexes in the graph. This must extend the base-class for vertexes of the graph type. E.g., all vertexes of a graph-container must extend graph-container-vertex.")
    (directed-edge-class 'basic-directed-edge ir
-                        "The class used to create directed edges in the graph.")
+                        "The class used to create directed edges in the graph. This must extend the base-class for edges of the graph type and directed-edge-mixin. E.g., the directed-edge-class of a graph-container must extend graph-container-edge and directed-edge-mixin.")
    (undirected-edge-class 'basic-edge ir
-                          "The class used to create undirected edges in the graph.")
+                          "The class used to create undirected edges in the graph. This must extend the base-class for edges of the graph type. E.g., all edges of a graph-container must extend graph-container-edge")
    (contains-directed-edge-p nil ar 
                              "Returns true if graph contains at least one directed edge. [?? Not sure if this is really keep up-to-date.]")
    (contains-undirected-edge-p nil ar
@@ -198,7 +191,7 @@ something is putting something on the vertexes plist's
 
 (defmethod print-object ((graph basic-graph) stream)
   (print-unreadable-object (graph stream :type t :identity t)
-    (format stream "~A" (size graph))))
+    (format stream "[~A,~A]" (size graph) (edge-count graph))))
 
 
 ;;; ---------------------------------------------------------------------------
@@ -672,7 +665,7 @@ something is putting something on the vertexes plist's
          (error "~A not found in ~A" vertex graph))))
 
 ;;; ---------------------------------------------------------------------------
-
+;; TODO !!! dispatch is the same as the second method above
 (defmethod search-for-vertex ((graph basic-graph) (vertex t)
                               &key (key (vertex-key graph)) (test 'equal)
                               (error-if-not-found? t))
@@ -1072,7 +1065,7 @@ nil gathers the entire closure(s)."
 ;;; ---------------------------------------------------------------------------
 
 (defmethod edge-count ((graph basic-graph))
-  (length (edges graph)))
+  (count-using #'iterate-edges nil graph))
 
 ;;; ---------------------------------------------------------------------------