dev/package.lisp

   1 ;;;-*- Mode: Lisp; Package: COMMON-LISP-USER -*-
   2
   3 #| simple-header
   4
   5 Author: Gary King, et. al.
   6
   7 DISCUSSION
   8
   9 |#
  10 (in-package common-lisp-user)
  11
  12 (defpackage "CL-GRAPH"
  13   (:use "COMMON-LISP" "METATILITIES" "CL-CONTAINERS"
  14         "METABANG.BIND" "METABANG.MATH")
  15   (:nicknames "METABANG.GRAPH")
  16   (:documentation "CL-Graph is a Common Lisp library for manipulating graphs and running graph algorithms.")
  17
  18   (:export
  19    #:with-changing-vertex
  20
  21    #:make-graph
  22    #:basic-graph
  23
  24    #:add-edge-between-vertexes     ; graph { value | vertex } { value | vertex }
  25    #:delete-edge-between-vertexes  ; graph { value | vertex } { value | vertex }
  26    #:add-vertex                    ; graph { value | vertex }
  27    #:find-vertex                   ; graph { value | vertex }
  28    #:find-edge                     ; graph edge
  29    #:find-edge-between-vertexes    ; graph { vertex | value } { vertex | value }
  30    #:find-vertex-if
  31    #:find-vertexes-if
  32    #:search-for-vertex
  33
  34    #:iterate-container             ; graph fn
  35    #:iterate-vertexes
  36    #:vertexes
  37    #:source-edges
  38    #:target-edges
  39    #:child-vertexes
  40    #:parent-vertexes
  41    #:neighbor-vertexes
  42    #:other-vertex
  43
  44    #:edge-count                    ; graph
  45    #:vertex-count                  ; graph
  46    #:source-edge-count             ; vertex
  47    #:target-edge-count             ; vertex
  48
  49    #:rootp                         ; vertex
  50    #:graph-roots                   ; graph
  51
  52    #:topological-sort              ; graph
  53    #:depth                         ; graph | vertex
  54    #:depth-level
  55
  56    #:get-transitive-closure        ;; CTM
  57    #:make-filtered-graph           ;; CTM
  58
  59    #:adjacentp
  60    #:in-cycle-p                    ; graph vertex
  61    #:force-undirected
  62
  63    #:renumber-vertexes
  64    #:renumber-edges
  65
  66    #:generate-directed-free-tree
  67
  68    #:contains-undirected-edge-p
  69    #:contains-directed-edge-p
  70
  71    #:undirected-edge-p
  72    #:directed-edge-p
  73    #:tagged-edge-p
  74    #:untagged-edge-p
  75    #:tag-all-edges
  76    #:untag-all-edges
  77    #:graph->dot
  78    #:vertex->dot
  79    #:edge->dot
  80    #:graph->dot-properties
  81    #:subgraph-containing
  82    #:graph->dot-external
  83    #:dot-graph
  84    #:dot-vertex
  85    #:dot-edge
  86
  87    #:connected-graph-p
  88    #:find-connected-components
  89    #:connected-component-count
  90
  91    #:target-vertex
  92    #:source-vertex
  93
  94    #:add-edge                      ; graph edge
  95    #:delete-edge                   ; graph edge
  96
  97    #:add-vertex                    ; graph { value | vertex }
  98    #:delete-vertex                 ; graph { value | vertex }
  99    #:find-vertex                   ; graph { value | vertex }
 100    #:find-edge                     ; graph edge
 101    #:find-edge-between-vertexes    ; graph { vertex | value } { vertex | value }
 102    #:find-edge-between-vertexes-if ; graph { vertex | value } { vertex | value } fn
 103    #:find-edge-if                  ; graph
 104    #:find-edges-if                 ; graph
 105
 106    #:edges                         ; graph | vertex
 107    #:iterate-edges                 ; graph fn
 108    #:iterate-source-edges          ; vertex fn
 109    #:iterate-target-edges          ; vertex fn
 110    #:iterate-children              ; vertex (nodes) fn
 111    #:iterate-parents               ; vertex (nodes) fn
 112    #:iterate-neighbors             ; vertex (all neighbors) fn
 113    #:has-children-p
 114    #:has-parent-p
 115    #:number-of-neighbors
 116
 117    #:edge-count                    ; graph
 118    #:vertex-count                  ; graph
 119
 120    #:topological-sort              ; graph
 121    #:depth                         ; graph | vertex
 122    #:depth-level
 123
 124    #:get-transitive-closure        ;; CTM
 125    #:make-filtered-graph           ;; CTM
 126
 127    #:adjacentp
 128    #:in-cycle-p                    ; graph vertex
 129    #:in-undirected-cycle-p         ; graph vertex
 130    #:any-undirected-cycle-p        ; graph
 131    #:force-undirected
 132    #:vertices-share-edge-p
 133
 134    #:map-paths
 135    #:map-shortest-paths
 136
 137    ;;; depth first search
 138    #:dfs-edge-type
 139    #:dfs-back-edge-p
 140    #:dfs-tree-edge-p
 141    #:edge-lessp-by-direction
 142    #:out-edge-for-vertex-p
 143    #:dfs
 144
 145    ;;; minimum-spanning-tree
 146    #+Ignore #:add-edges-to-graph
 147
 148    #:make-graph-from-vertexes
 149    #:edge-lessp-by-weight
 150    #:minimum-spanning-tree
 151
 152    ;;; mapping
 153    #+Ignore #:map-over-all-combinations-of-k-vertexes
 154    #+Ignore #:map-over-all-combinations-of-k-edges
 155
 156    #:project-bipartite-graph
 157
 158    #:make-vertex-edges-container
 159
 160    #:vertex-degree-counts
 161    #:vertex-degree
 162    #:average-vertex-degree
 163    #:vertex-clustering-coefficient
 164    #:average-vertex-clustering-coefficient
 165
 166    #:graph-mixing-matrix
 167    #:graph-edge-mixture-matrix
 168    #:assortativity-coefficient
 169    #:vertex-degree-summary))