Generated: August 3, 2004, 13:56:58 A SchemeDoc Manual

Rooster Graph

Jonah Nathaniel Beckford © 2004

LAML Version 23.00 (December 12, 2003, full)

Table of Contents:
1. Copyrights. 7. Adjacency List: Hash Edge List 13. Algorithm
2. Usage Notes 8. Property Map 14. Algorithm: Depth First Search
3. Adjacency List 9. Property Map: Vertex Example 15. Algorithm: Topological Sort
4. Adjacency List: Vector Vertex List 10. Property Map: Edge Example 16. Algorithm: Partition: Fiduccia-Mattheyses
5. Adjacency List: Hash Vertex List 11. Visitor 17. Utility
6. Adjacency List: Singly-Linked Edge List 12. Visitor: Depth First Search

Alphabetic index:
##carp##make-GTYPE-el (##carp##make-GTYPE-el graph) Internal.
##carp##make-GTYPE-el (##carp##make-GTYPE-el graph) Internal.
##carp##make-GTYPE-vl (##carp##make-GTYPE-vl graph) Internal.
##carp##make-GTYPE-vl (##carp##make-GTYPE-vl graph) Internal.
##carp#GTYPE-add-directed-edge! (##carp#GTYPE-add-directed-edge! graph u-vertex_descriptor u-edge_list v-vertex_descriptor) Internal.
##carp#GTYPE-add-directed-edge! (##carp#GTYPE-add-directed-edge! graph u-vertex_descriptor u-edge_list v-vertex_descriptor) Internal.
##carp#GTYPE-degree (##carp#GTYPE-degree graph vertex_descriptor) Internal.
##carp#GTYPE-degree (##carp#GTYPE-degree graph vertex_descriptor) Internal.
##carp#GTYPE-edges (##carp#GTYPE-edges graph u-vertex_descriptor u-edge_list is-out-edge-list?) Internal.
##carp#GTYPE-edges (##carp#GTYPE-edges graph u-vertex_descriptor u-edge_list is-out-edge-list?) Internal.
##carp#GTYPE-edges* (##carp#GTYPE-edges* graph u-vertex_descriptor u-edge_list is-out-edge-list?) Internal.
##carp#GTYPE-edges* (##carp#GTYPE-edges* graph u-vertex_descriptor u-edge_list is-out-edge-list?) Internal.
##carp#GTYPE-in-edge-list (##carp#GTYPE-in-edge-list graph vertex_descriptor) Internal.
##carp#GTYPE-in-edge-list (##carp#GTYPE-in-edge-list graph vertex_descriptor) Internal.
##carp#GTYPE-out-edge-list (##carp#GTYPE-out-edge-list graph vertex_descriptor) Internal.
##carp#GTYPE-out-edge-list (##carp#GTYPE-out-edge-list graph vertex_descriptor) Internal.
##carp#GTYPE-remove-directed-edge! (##carp#GTYPE-remove-directed-edge! graph u-vertex_descriptor u-edge_list v-vertex_descriptor) Internal.
##carp#GTYPE-remove-directed-edge! (##carp#GTYPE-remove-directed-edge! graph u-vertex_descriptor u-edge_list v-vertex_descriptor) Internal.
##carp#GTYPE-transform-vertices! (##carp#GTYPE-transform-vertices! vertex_descriptor-to-vertex_descriptor-procedure graph u-vertex_descriptor ) Transforms each vertex in u's out- [and in- if bidirectional? is #t] edge list into another vertex_descriptor using the passed-in procedure.
##carp#GTYPE-transform-vertices! (##carp#GTYPE-transform-vertices! vertex_descriptor-to-vertex_descriptor-procedure graph u-vertex_descriptor ) Internal.
GTYPE-add-vertex! (GTYPE-add-vertex! graph key [ignored-arg ...]) Create and add a new vertex to graph, indexed by key.
GTYPE-add-vertex! (GTYPE-add-vertex! graph [ignored-arg ...]) Create and add a new vertex to graph.
GTYPE-clear! (GTYPE-clear! graph) Removes all vertices and edges from graph.
GTYPE-clear! (GTYPE-clear! graph) Removes all vertices and edges from graph.
GTYPE-edge (GTYPE-edge graph source-vertex_descriptor target-vertex_descriptor) Gets the edge(source,target).
GTYPE-edge (GTYPE-edge graph source-vertex_descriptor target-vertex_descriptor) Gets the edge(source,target).
GTYPE-edge-at (GTYPE-edge-at graph u-vertex_descriptor zero-based-n-integer) Get the n+1'th edge added the vertex u.
GTYPE-edge-color (GTYPE-edge-color graph edge_descriptor) Example.
GTYPE-edge-color-map GTYPE-edge-color-map Example.
GTYPE-edge-set? (GTYPE-edge-set?) Are the edges in a set (#t) or a list (#f)?
GTYPE-edge-set? (GTYPE-edge-set?) Are the edges in a set (#t) or a list (#f)?
GTYPE-edge-weight (GTYPE-edge-weight graph edge_descriptor) Example.
GTYPE-edge-weight-map GTYPE-edge-weight-map Example.
GTYPE-fill-graph! (GTYPE-fill-graph! graph edges set-vertex-name!) Fill graph from a list of edges, where each edge is a pair of the form '(vertex1 .
GTYPE-num-vertices (GTYPE-num-vertices graph) Gets the number of vertices in graph.
GTYPE-num-vertices (GTYPE-num-vertices graph) Gets the number of vertices in graph.
GTYPE-partition-fidmat (GTYPE-partition-fidmat graph partition-map gain descriptor-map working-graph working-descriptor-map cost balance weight criterion split-level) Fiduccia-Mattheyses Bipartitioning.
GTYPE-partition-fidmat-check GTYPE-partition-fidmat-check Set to #t to check that the pre-conditions are met in GTYPE-partition-fidmat.
GTYPE-partition-fidmat-debug GTYPE-partition-fidmat-debug Set to #t to print debug statements when running GTYPE-partition-fidmat.
GTYPE-remove-vertex! (GTYPE-remove-vertex! graph vertex_descriptor) Remove vertex from graph.
GTYPE-remove-vertex! (GTYPE-remove-vertex! graph vertex_descriptor) Remove vertex from graph.
GTYPE-source (GTYPE-source graph edge_descriptor) Gets the source of an edge(source,target).
GTYPE-source (GTYPE-source graph edge_descriptor) Gets the source of an edge(source,target).
GTYPE-target (GTYPE-target graph edge_descriptor) Gets the target of an edge(source,target).
GTYPE-target (GTYPE-target graph edge_descriptor) Gets the target of an edge(source,target).
GTYPE-vertex (GTYPE-vertex graph zero-based-n-integer) Get the n+1'th vertex added to graph.
GTYPE-vertex-color (GTYPE-vertex-color graph vertex_descriptor) Example.
GTYPE-vertex-color-map GTYPE-vertex-color-map Example.
GTYPE-vertex-eq? (GTYPE-vertex-eq? graph u v) Is vertex u the same vertex as vertex v?
GTYPE-vertex-eq? (GTYPE-vertex-eq? graph u v) Is vertex u the same vertex as vertex v?
GTYPE-vertex-index (GTYPE-vertex-index graph vertex_descriptor) Read-only property map created by vl-vector.
GTYPE-vertex-index (GTYPE-vertex-index graph vertex_descriptor) Read-only property map created by vl-hash.
GTYPE-vertex-name (GTYPE-vertex-name graph vertex_descriptor) Example.
GTYPE-vertex-name-map GTYPE-vertex-name-map Example.
GTYPE-vertex-set? (GTYPE-vertex-set?) Are the vertices in a set (#t) or a list (#f)?
GTYPE-vertex-set? (GTYPE-vertex-set?) Are the vertices in a set (#t) or a list (#f)?
GTYPE-vertices (GTYPE-vertices graph) Gets a list of all the vertices in the graph.
GTYPE-vertices (GTYPE-vertices graph) Gets a list of all the vertices in the graph.
GTYPE-vertices* (GTYPE-vertices* graph) Gets a stream of all the vertices in the graph.
GTYPE-vertices* (GTYPE-vertices* graph) Gets a stream of all the vertices in the graph.
NAME-add-edge! (NAME-add-edge! graph u-vertex_descriptor v-vertex_descriptor) Adds an edge(u,v) to graph
NAME-in-degree (NAME-in-degree graph vertex_descriptor) Gets number of in-edges for vertex.
NAME-in-edges (NAME-in-edges graph u-vertex_descriptor) Gets a list of in-edges for vertex u.
NAME-in-edges* (NAME-in-edges* graph u-vertex_descriptor) Gets a stream of in-edges for vertex u.
NAME-neighbours (NAME-neighbours graph u-vertex_descriptor) Gets a list of neighbours for vertex u.
NAME-neighbours* (NAME-neighbours* graph u-vertex_descriptor) Gets a stream of neighbours for vertex u.
NAME-out-degree (NAME-out-degree graph vertex_descriptor) Gets number of out-edges for vertex.
NAME-out-edges (NAME-out-edges graph u-vertex_descriptor) Gets a list of out-edges for vertex u.
NAME-out-edges* (NAME-out-edges* graph u-vertex_descriptor) Gets a stream of out-edges for vertex u.
NAME-remove-edge! (NAME-remove-edge! graph edge_descriptor) Removes an edge described by its descriptor
NAME-remove-edge2! (NAME-remove-edge2! graph source-vertex_descriptor target-vertex_descriptor) Removes the edge(source,target)
define-adjacency-list (define-adjacency-list name algorithms (VTYPE . args) vertex-properties (ETYPE . args) edge-properties directed? bidirectional?) Creates specialized adjacency-list graph methods, and imports them into the current lexical scope.
define-el-hash (define-el-hash name args streamed? bidirectional? edge-properties) Create and import specialized edge list.
define-el-slist (define-el-slist name args streamed? bidirectional? edge-properties) Create and import specialized edge list.
define-vl-hash (define-vl-hash name args streamed? bidirectional? vertex-properties get-vl) Create and import specialized vertex list.
define-vl-vector (define-vl-vector name args streamed? bidirectional? vertex-properties get-vl) Create and import specialized vertex list.
depth-first-search (GTYPE-depth-first-search graph dfs-visitor color-map starting-vertex) Depth first search.
depth-first-visit (GTYPE-depth-first-visit graph dfs-visitor color set-color! starting-vertex) Depth first visit
dfs-visitor (dfs-visitor init start discover examine tree-edge back-edge forward-or-cross-edge finish Create a depth-first search visitor.
let-rgraph (let-rgraph GTYPE (body) ...) Create a lexical scope with bindings to the graph methods.
make-NAME (make-NAME) Construct the specialized adjacency list graph.
null-dfs-visitor (null-dfs-visitor) Create a depth-first search visitor that does nothing.
prop-external-hash (prop-external-hash eq? [num]) Create an external property map on top of a hashtable.
prop-external-vector (prop-external-vector [num]) Create an external property map on top of a vector.
rgraph-doc-copyright-boost rgraph-doc-copyright-boost Boost Software License - Version 1.0 - August 17th, 2003.
rgraph-doc-copyright-rgraph rgraph-doc-copyright-rgraph Rooster Graph.
rgraph-doc-usage-debugging rgraph-doc-usage-debugging Debugging.
rgraph-doc-usage-imports rgraph-doc-usage-imports Imports.
set-GTYPE-edge-color! (set-GTYPE-edge-color! graph edge_descriptor edge-property) Example.
set-GTYPE-edge-weight! (set-GTYPE-edge-weight! graph edge_descriptor edge-property) Example.
set-GTYPE-vertex-color! (set-GTYPE-vertex-color! graph vertex_descriptor vertex-property) Example.
set-GTYPE-vertex-name! (set-GTYPE-vertex-name! graph vertex_descriptor vertex-property) Example.
set-dfs-visitor-back-edge! (set-dfs-visitor-back-edge! PROC) Call (PROC graph edge) on the back-edge event
set-dfs-visitor-discover! (set-dfs-visitor-discover! PROC) Call (PROC graph vertex) on the discover event
set-dfs-visitor-examine! (set-dfs-visitor-examine! PROC) Call (PROC graph vertex) on the examine event.
set-dfs-visitor-finish! (set-dfs-visitor-finish! PROC) Call (PROC graph vertex) on the finish event
set-dfs-visitor-forward-or-cross-edge! (set-dfs-visitor-forward-or-cross-edge! PROC) Call (PROC graph edge) on the forward-or-cross-edge event
set-dfs-visitor-init! (set-dfs-visitor-init! PROC) Call (PROC graph vertex) on the init event
set-dfs-visitor-start! (set-dfs-visitor-start! PROC) Call (PROC graph vertex) on the start event
set-dfs-visitor-tree-edge! (set-dfs-visitor-tree-edge! PROC) Call (PROC graph edge) on the tree-edge event
topological-sort (GTYPE-topological-sort graph) Topological sort.
topological-sort* (GTYPE-topological-sort* graph) Topological sort.

1 Copyrights.
rgraph-doc-copyright-rgraph
Form rgraph-doc-copyright-rgraph
Description Rooster Graph. 
 
 Copyright (c) 2004, Jonah Nathaniel Beckford
 All rights reserved.
 
 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions
 are met:
 
   Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
 
   Redistributions in binary form must reproduce the above
   copyright notice, this list of conditions and the following
   disclaimer in the documentation and/or other materials provided
   with the distribution.
 
   Neither the name of the author nor the names of its contributors
   may be used to endorse or promote products derived from this
   software without specific prior written permission.
 
 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 POSSIBILITY OF SUCH DAMAGE.
 
 jonah@usermail.com
rgraph-doc-copyright-boost
Form rgraph-doc-copyright-boost
Description Boost Software License - Version 1.0 - August 17th, 2003. 
 
 Permission is hereby granted, free of charge, to any person or
 organization obtaining a copy of the software and accompanying
 documentation covered by this license (the "Software") to use,
 reproduce, display, distribute, execute, and transmit the
 Software, and to prepare derivative works of the Software, and to
 permit third-parties to whom the Software is furnished to do so,
 all subject to the following:
 
 The copyright notices in the Software and this entire statement,
 including the above license grant, this restriction and the
 following disclaimer, must be included in all copies of the
 Software, in whole or in part, and all derivative works of the
 Software, unless such copies or derivative works are solely in the
 form of machine-executable object code generated by a source
 language processor.
 
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, TITLE AND
 NON-INFRINGEMENT. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
 ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE FOR ANY DAMAGES OR
 OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, ARISING
 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 OTHER DEALINGS IN THE SOFTWARE.
 
 Copyright © 2000-2001
 
 Jeremy Siek, Indiana University (jsiek@osl.iu.edu)
 Lie-Quan Lee, Indiana University (llee@cs.indiana.edu)
 Andrew Lumsdaine, Indiana University (lums@osl.iu.edu)
2 Usage Notes
rgraph-doc-usage-imports
Form rgraph-doc-usage-imports
Description Imports. 
 
 The following imports must be imported by the user *BEFORE*
 importing rgraph.
 
 NECESSARY
 =========
 
 ---------- All Scheme Implementations ----------
 
 Srfi-0 : cond-expand
 
 ---------- CHICKEN ----------
 
 Specified in the rgraph.setup
 
 Extras : hash-table
 
 OPTIONAL
 ========
 
 Srfi-40 : streams.  needed when you use the star-suffix versions of
 the methods; for example, when using the stream-valued
 (Graph-Name-out-edges* ...) instead of the list-valued
 (Graph-Name-out-edges ...)
rgraph-doc-usage-debugging
Form rgraph-doc-usage-debugging
Description Debugging. 
 Debugging includes, at minimum, some type-checking of
 function arguments.
 
 The feature (Srfi-0) 'rgraph-nodebug takes precedent over 'rgraph-debug.
 
 Chicken - If you are running in CSI, then 'rgraph-debug is implicitly
 turned on.  You may override by explicitly setting the feature
 'rgraph-nodebug.
3 Adjacency List
The adjacency_list class implements a generalized adjacency list graph structure. The template parameters provide many configuration options so that you can pick a version of the class that best meets your needs. An adjacency-list is basically a two-dimensional structure, where each element of the first dimension represents a vertex, and each of the vertices contains a one-dimensional structure that is its edge list. [description copied from boost]

See Boost's Adjacency List for more details.

define-adjacency-list
Form (define-adjacency-list name algorithms (VTYPE . args) vertex-properties (ETYPE . args) edge-properties directed? bidirectional?)
Description Creates specialized adjacency-list graph methods, and imports them into the current lexical scope. The methods that will be created (see the following methods in this section, and also see the documentation for your 'vertex-list and 'edge-list) will be prefixed with the argument 'name as opposed to "NAME".
Parameters name graph type name, which is used to prefix all the graph methods
algorithms list of algorithms
(VTYPE . args) vertex list constructor
vertex-properties list of internal vertex properties
(ETYPE . args) edge list constructor
edge-properties list of internal edge properties
directed? #t if directed graph, #f if undirected
bidirectional? #t if in-edge methods are to be created
Example 
 (define test-example
   (lambda ()
     (define-adjacency-list xyz
       (fill-graph! depth-first-search topological-sort)
       (vl-vector) (vertex-name vertex-color)
       (el-slist) (edge-weight)
       #t #f)
     
     (define g1 (make-xyz))
     (print g1)
 
     (define v1 (xyz-add-vertex! g1))
     (define v2 (xyz-add-vertex! g1))
     (define v3 (xyz-add-vertex! g1))
     (define e1 (xyz-add-edge! g1 v1 v2))
     (define e2 (xyz-add-edge! g1 v1 v3))
     (define e3 (xyz-add-edge! g1 v2 v3))
 
     (print (xyz-vertices g1))
     (stream-for-each print (xyz-vertices* g1))
 
     (print (xyz-edge g1 v1 v2)) ) )
make-NAME
Form (make-NAME)
Description Construct the specialized adjacency list graph.
Returns adjacency-list-graph
NAME-add-edge!
Form (NAME-add-edge! graph u-vertex_descriptor v-vertex_descriptor)
Description Adds an edge(u,v) to graph
Returns edge_descriptor
NAME-remove-edge!
Form (NAME-remove-edge! graph edge_descriptor)
Description Removes an edge described by its descriptor
NAME-remove-edge2!
Form (NAME-remove-edge2! graph source-vertex_descriptor target-vertex_descriptor)
Description Removes the edge(source,target)
Returns (if 'found-and-removed #t #f)
NAME-out-edges
Form (NAME-out-edges graph u-vertex_descriptor)
Description Gets a list of out-edges for vertex u.
Returns (list out-edge_descriptor ...)
NAME-out-edges*
Form (NAME-out-edges* graph u-vertex_descriptor)
Description Gets a stream of out-edges for vertex u.
Returns (stream out-edge_descriptor ...)
NAME-in-edges
Form (NAME-in-edges graph u-vertex_descriptor)
Description Gets a list of in-edges for vertex u. Defined only if bidirectional? is true. The ordinary semantics of source and target for directed? graphs are maintained: (NAME-target graph in-edge_descriptor) will always return u.
Returns (list in-edge_descriptor ...)
NAME-in-edges*
Form (NAME-in-edges* graph u-vertex_descriptor)
Description Gets a stream of in-edges for vertex u. Defined only if bidirectional? is true. The ordinary semantics of source and target for directed? graphs are maintained: (NAME-target graph in-edge_descriptor) will always return u.
Returns (stream in-edge_descriptor ...)
NAME-neighbours
Form (NAME-neighbours graph u-vertex_descriptor)
Description Gets a list of neighbours for vertex u. Defined only if bidirectional? is true or if directed? is false. The ordinary semantics of source and target for directed? graphs are maintained: (NAME-target graph neighbour-edge_descriptor) will always return u.
Returns (list (cons neighbour-vertex_descriptor neighbour-edge_descriptor) ...)
NAME-neighbours*
Form (NAME-neighbours* graph u-vertex_descriptor)
Description Gets a stream of neighbours for vertex u. Defined only if bidirectional? is true or if directed? is false. The ordinary semantics of source and target for directed? graphs are maintained: (NAME-target graph neighbour-edge_descriptor) will always return u.
Returns (stream (cons neighbour-vertex_descriptor neighbour-edge_descriptor) ...)
NAME-out-degree
Form (NAME-out-degree graph vertex_descriptor)
Description Gets number of out-edges for vertex.
Returns number-of-out-edges-integer
NAME-in-degree
Form (NAME-in-degree graph vertex_descriptor)
Description Gets number of in-edges for vertex. Defined only if bidirectional? is true.
Returns number-of-in-edges-integer
4 Adjacency List: Vector Vertex List
Scheme macro specialization to Adjacency List that stores the vertices in a logarithmetically growing (as you added vertices) vector.

See Boost's Choosing Graph Type for more details.

define-vl-vector
Form (define-vl-vector name args streamed? bidirectional? vertex-properties get-vl)
Description Create and import specialized vertex list. 
 VERTEX LIST
 
 [vertex_record-vector number-vertices-integer]
 
 VERTEX RECORD
 
 [out-edge_list {if bidirectional? in-edge_list} vertex-properties]
 
 VERTEX DESCRIPTOR
 
 source-index-integer
Parameters name graph type name, which is used to prefix all the graph methods
args arguments to constructor
streamed? #t if the stream methods are to be created
bidirectional? #t if in-edge methods are to be created
vertex-properties list of internal vertex properties
get-vl procedure -> vertex_list
See also Graph Methods graph-methods
GTYPE-vertex-set?
Form (GTYPE-vertex-set?)
Description Are the vertices in a set (#t) or a list (#f)?
Returns boolean
##carp##make-GTYPE-vl
Form (##carp##make-GTYPE-vl graph)
Description Internal.
Returns vertex_list
GTYPE-add-vertex!
Form (GTYPE-add-vertex! graph [ignored-arg ...])
Description Create and add a new vertex to graph. Amortized O(log n).
Parameters graph graph object
ignored-arg arguments that will be ignored
Returns vertex_descriptor
GTYPE-remove-vertex!
Form (GTYPE-remove-vertex! graph vertex_descriptor)
Description Remove vertex from graph. All vertex_descriptors will become invalid. O(n).
GTYPE-vertex
Form (GTYPE-vertex graph zero-based-n-integer)
Description Get the n+1'th vertex added to graph. O(1).
Returns (n+1)th-vertex-added-to-graph-vertex_descriptor
GTYPE-vertex-eq?
Form (GTYPE-vertex-eq? graph u v)
Description Is vertex u the same vertex as vertex v?
Returns (if 'vertices-equal #t #f)
GTYPE-num-vertices
Form (GTYPE-num-vertices graph)
Description Gets the number of vertices in graph. O(1).
Returns number-of-vertices-integer
GTYPE-vertices
Form (GTYPE-vertices graph)
Description Gets a list of all the vertices in the graph.
Returns (list vertex_descriptor ...)
GTYPE-vertices*
Form (GTYPE-vertices* graph)
Description Gets a stream of all the vertices in the graph.
Returns (stream vertex_descriptor ...)
GTYPE-clear!
Form (GTYPE-clear! graph)
Description Removes all vertices and edges from graph.
##carp#GTYPE-out-edge-list
Form (##carp#GTYPE-out-edge-list graph vertex_descriptor)
Description Internal.
Returns out-edge_list
##carp#GTYPE-in-edge-list
Form (##carp#GTYPE-in-edge-list graph vertex_descriptor)
Description Internal. Only defined if bidirectional?.
Returns in-edge_list
GTYPE-vertex-index
Form (GTYPE-vertex-index graph vertex_descriptor)
Description Read-only property map created by vl-vector.
Returns vertex-index-integer
5 Adjacency List: Hash Vertex List
Scheme macro specialization to Adjacency List that stores the vertices in a hash table.

See Boost's Choosing Graph Type for more details.

define-vl-hash
Form (define-vl-hash name args streamed? bidirectional? vertex-properties get-vl)
Description Create and import specialized vertex list. 
 VERTEX LIST
 
 [vertex_record-hashtable max-vertex_index]
 
 VERTEX RECORD
 
 [out-edge_list {if bidirectional? in-edge_list} vertex-properties]
 
 VERTEX DESCRIPTOR
 
 source-hashtable_key
Parameters name graph type name, which is used to prefix all the graph methods
args ([PRED [SIZE]]) - PRED is (lambda v1 v2) that equality compares two vertices, and SIZE is initial vertex storage size
streamed? #t if the stream methods are to be created
bidirectional? #t if in-edge methods are to be created
vertex-properties list of internal vertex properties
get-vl procedure -> vertex_list
See also Graph Methods graph-methods
GTYPE-vertex-set?
Form (GTYPE-vertex-set?)
Description Are the vertices in a set (#t) or a list (#f)?
Returns boolean
##carp##make-GTYPE-vl
Form (##carp##make-GTYPE-vl graph)
Description Internal.
Returns vertex_list
GTYPE-add-vertex!
Form (GTYPE-add-vertex! graph key [ignored-arg ...])
Description Create and add a new vertex to graph, indexed by key. If vertex already exists at key, then returns the preexisting vertex. In any case, the key is the vertex descriptor. Amortized O(1).
Parameters graph graph object
key to-be-added vertex_descriptor
ignored-arg argument that will be ignored
Returns vertex_descriptor
GTYPE-remove-vertex!
Form (GTYPE-remove-vertex! graph vertex_descriptor)
Description Remove vertex from graph. All vertex_descriptors will become invalid. O(n).
GTYPE-vertex-eq?
Form (GTYPE-vertex-eq? graph u v)
Description Is vertex u the same vertex as vertex v?
Returns (if 'vertices-equal #t #f)
GTYPE-num-vertices
Form (GTYPE-num-vertices graph)
Description Gets the number of vertices in graph. O(1).
Returns number-of-vertices-integer
GTYPE-vertices
Form (GTYPE-vertices graph)
Description Gets a list of all the vertices in the graph.
Returns (list vertex_descriptor ...)
GTYPE-vertices*
Form (GTYPE-vertices* graph)
Description Gets a stream of all the vertices in the graph.
Returns (stream vertex_descriptor ...)
GTYPE-clear!
Form (GTYPE-clear! graph)
Description Removes all vertices and edges from graph.
##carp#GTYPE-out-edge-list
Form (##carp#GTYPE-out-edge-list graph vertex_descriptor)
Description Internal.
Returns out-edge_list
##carp#GTYPE-in-edge-list
Form (##carp#GTYPE-in-edge-list graph vertex_descriptor)
Description Internal. Only defined if bidirectional?.
Returns in-edge_list
GTYPE-vertex-index
Form (GTYPE-vertex-index graph vertex_descriptor)
Description Read-only property map created by vl-hash.
Returns vertex-index-integer
6 Adjacency List: Singly-Linked Edge List
Scheme macro specialization to Adjacency List that stores the edges in a singly linked list.

See Boost's Choosing Graph Type for more details.

define-el-slist
Form (define-el-slist name args streamed? bidirectional? edge-properties)
Description Create and import specialized edge list. 
 EDGE LIST
 
 [(list target-edge_record ...) number-of-target-edges-integer]
 
 EDGE RECORD
 
 [target-vertex_descriptor edge-properties]
 
 EDGE DESCRIPTOR
 
 (cons source-vertex_descriptor target-edge_record)
Parameters name graph type name, which is used to prefix all the graph methods
args arguments to constructor
streamed? #t if the stream methods are to be created
bidirectional? #t if in-edge methods are to be created
edge-properties list of internal edge properties
See also Graph Methods graph-methods
GTYPE-edge-set?
Form (GTYPE-edge-set?)
Description Are the edges in a set (#t) or a list (#f)?
Returns boolean
##carp##make-GTYPE-el
Form (##carp##make-GTYPE-el graph)
Description Internal.
Returns edge_list
##carp#GTYPE-add-directed-edge!
Form (##carp#GTYPE-add-directed-edge! graph u-vertex_descriptor u-edge_list v-vertex_descriptor)
Description Internal. O(1).
Returns edge_descriptor
##carp#GTYPE-remove-directed-edge!
Form (##carp#GTYPE-remove-directed-edge! graph u-vertex_descriptor u-edge_list v-vertex_descriptor)
Description Internal. O(E/V).
Returns (if 'found-and-removed #t #f)
GTYPE-edge
Form (GTYPE-edge graph source-vertex_descriptor target-vertex_descriptor)
Description Gets the edge(source,target). O(E/V).
Returns (if 'found-edge edge_descriptor #f)
GTYPE-source
Form (GTYPE-source graph edge_descriptor)
Description Gets the source of an edge(source,target).
Returns source-vertex_descriptor
GTYPE-target
Form (GTYPE-target graph edge_descriptor)
Description Gets the target of an edge(source,target).
Returns target-vertex_descriptor
##carp#GTYPE-edges
Form (##carp#GTYPE-edges graph u-vertex_descriptor u-edge_list is-out-edge-list?)
Description Internal. O(E). Maintains source/target semantics in the resultant edge_descriptors for directed? graphs, so that u is the target if is-out-edge-list? is #f.
Returns (list edge_descriptor ...)
##carp#GTYPE-edges*
Form (##carp#GTYPE-edges* graph u-vertex_descriptor u-edge_list is-out-edge-list?)
Description Internal.
Returns (stream edge_descriptor ...)
GTYPE-edge-at
Form (GTYPE-edge-at graph u-vertex_descriptor zero-based-n-integer)
Description Get the n+1'th edge added the vertex u. O(E/V).
Returns (n+1)th-edge-added-to-u-edge_descriptor
##carp#GTYPE-degree
Form (##carp#GTYPE-degree graph vertex_descriptor)
Description Internal. O(1).
Returns number-of-edges-integer
##carp#GTYPE-transform-vertices!
Form (##carp#GTYPE-transform-vertices! vertex_descriptor-to-vertex_descriptor-procedure graph u-vertex_descriptor )
Description Transforms each vertex in u's out- [and in- if bidirectional? is #t] edge list into another vertex_descriptor using the passed-in procedure.
Returns unspecified
7 Adjacency List: Hash Edge List
Scheme macro specialization to Adjacency List that stores the edges in a hash table.

See Boost's Choosing Graph Type for more details.

define-el-hash
Form (define-el-hash name args streamed? bidirectional? edge-properties)
Description Create and import specialized edge list. 
 EDGE LIST
 
 [(hash-table target-edge_record ...)]
 
 EDGE RECORD
 
 [target-vertex_descriptor edge-properties]
 
 EDGE DESCRIPTOR
 
 (cons source-vertex_descriptor target-edge_record)
Parameters name graph type name, which is used to prefix all the graph methods
args arguments to constructor
streamed? #t if the stream methods are to be created
bidirectional? #t if in-edge methods are to be created
edge-properties list of internal edge properties
See also Graph Methods graph-methods
GTYPE-edge-set?
Form (GTYPE-edge-set?)
Description Are the edges in a set (#t) or a list (#f)?
Returns boolean
##carp##make-GTYPE-el
Form (##carp##make-GTYPE-el graph)
Description Internal.
Returns edge_list
##carp#GTYPE-add-directed-edge!
Form (##carp#GTYPE-add-directed-edge! graph u-vertex_descriptor u-edge_list v-vertex_descriptor)
Description Internal. Add directed edge(u,v) to graph. O(1). Does not overwrite edge(u,v) if already exist.
Returns edge_descriptor
##carp#GTYPE-remove-directed-edge!
Form (##carp#GTYPE-remove-directed-edge! graph u-vertex_descriptor u-edge_list v-vertex_descriptor)
Description Internal. O(1)
Returns (if 'found-and-removed #t #f)
GTYPE-edge
Form (GTYPE-edge graph source-vertex_descriptor target-vertex_descriptor)
Description Gets the edge(source,target). O(1).
Returns (if 'found-edge edge_descriptor #f)
GTYPE-source
Form (GTYPE-source graph edge_descriptor)
Description Gets the source of an edge(source,target).
Returns source-vertex_descriptor
GTYPE-target
Form (GTYPE-target graph edge_descriptor)
Description Gets the target of an edge(source,target).
Returns target-vertex_descriptor
##carp#GTYPE-edges
Form (##carp#GTYPE-edges graph u-vertex_descriptor u-edge_list is-out-edge-list?)
Description Internal. O(E). Maintains source/target semantics in the resultant edge_descriptors for directed? graphs, so that u is the target if is-out-edge-list? is #f.
Returns (list edge_descriptor ...)
##carp#GTYPE-edges*
Form (##carp#GTYPE-edges* graph u-vertex_descriptor u-edge_list is-out-edge-list?)
Description Internal.
Returns (stream edge_descriptor ...)
##carp#GTYPE-degree
Form (##carp#GTYPE-degree graph vertex_descriptor)
Description Internal. O(1).
Returns number-of-edges-integer
##carp#GTYPE-transform-vertices!
Form (##carp#GTYPE-transform-vertices! vertex_descriptor-to-vertex_descriptor-procedure graph u-vertex_descriptor )
Description Internal. Transforms each vertex in u's out- [and in- if bidirectional? is #t] edge list into another vertex_descriptor using the passed-in procedure.
Returns unspecified
8 Property Map

The internal property maps are defined when you define the graph.

See Adjacency List to see how internal properties are defined.
See Boost's Property Map for a description of property maps.
prop-external-hash
Form (prop-external-hash eq? [num])
Description Create an external property map on top of a hashtable.
Parameters eq? A procedure that will equality compare two property keys.
num Optional. The initial size of the hash-table.
Returns A property map.
prop-external-vector
Form (prop-external-vector [num])
Description Create an external property map on top of a vector. The property key must be an integer.
Parameters num Optional. The initial size of the vector
Returns A property map.
9 Property Map: Vertex Example
GTYPE-vertex-name
Form (GTYPE-vertex-name graph vertex_descriptor)
Description Example. Property getter.
Returns vertex-property
GTYPE-vertex-color
Form (GTYPE-vertex-color graph vertex_descriptor)
Description Example. Property getter.
Returns vertex-property
set-GTYPE-vertex-name!
Form (set-GTYPE-vertex-name! graph vertex_descriptor vertex-property)
Description Example. Property setter.
set-GTYPE-vertex-color!
Form (set-GTYPE-vertex-color! graph vertex_descriptor vertex-property)
Description Example. Property setter.
GTYPE-vertex-name-map
Form GTYPE-vertex-name-map
Description Example. Property map.
Returns vertex-property-map
GTYPE-vertex-color-map
Form GTYPE-vertex-color-map
Description Example. Property map.
Returns vertex-property-map
10 Property Map: Edge Example
GTYPE-edge-weight
Form (GTYPE-edge-weight graph edge_descriptor)
Description Example. Property getter.
Returns edge-property
GTYPE-edge-color
Form (GTYPE-edge-color graph edge_descriptor)
Description Example. Property getter.
Returns edge-property
set-GTYPE-edge-weight!
Form (set-GTYPE-edge-weight! graph edge_descriptor edge-property)
Description Example. Property setter.
set-GTYPE-edge-color!
Form (set-GTYPE-edge-color! graph edge_descriptor edge-property)
Description Example. Property setter.
GTYPE-edge-weight-map
Form GTYPE-edge-weight-map
Description Example. Property map.
Returns edge-property-map
GTYPE-edge-color-map
Form GTYPE-edge-color-map
Description Example. Property map.
Returns edge-property-map
11 Visitor
See Boost's Visitor Concepts for more details.
12 Visitor: Depth First Search
See Boost's DFSVisitor
dfs-visitor
Form (dfs-visitor init start discover examine tree-edge back-edge forward-or-cross-edge finish
Description Create a depth-first search visitor.
Parameters init This is invoked on every vertex of the graph before the start of the graph search.
start This is invoked on the source vertex once before the start of the search.
discover This is invoked when a vertex is encountered for the first time.
examine This is invoked on every out-edge of each vertex after it is discovered, and returns #f if the vertex should not be examined.
tree-edge This is invoked on each edge as it becomes a member of the edges that form the search tree.
back-edge This is invoked on the back edges in the graph. For an undirected graph there is some ambiguity between tree edges and back edges since the edge (u,v) and (v,u) are the same edge, but both the tree_edge() and back_edge() functions will be invoked. One way to resolve this ambiguity is to record the tree edges, and then disregard the back-edges that are already marked as tree edges. An easy way to record tree edges is to record predecessors at the tree_edge event point.
forward-or-cross-edge This is invoked on forward or cross edges in the graph. In an undirected graph this method is never called.
finish This is invoked on vertex u after finish_vertex has been called for all the vertices in the DFS-tree rooted at vertex u. If vertex u is a leaf in the DFS-tree, then the finish_vertex function is call on u after all the out-edges of u have been examined.
null-dfs-visitor
Form (null-dfs-visitor)
Description Create a depth-first search visitor that does nothing.
set-dfs-visitor-init!
Form (set-dfs-visitor-init! PROC)
Description Call (PROC graph vertex) on the init event
See also Depth First Search Visitor dfs-visitor
set-dfs-visitor-start!
Form (set-dfs-visitor-start! PROC)
Description Call (PROC graph vertex) on the start event
See also Depth First Search Visitor dfs-visitor
set-dfs-visitor-discover!
Form (set-dfs-visitor-discover! PROC)
Description Call (PROC graph vertex) on the discover event
See also Depth First Search Visitor dfs-visitor
set-dfs-visitor-examine!
Form (set-dfs-visitor-examine! PROC)
Description Call (PROC graph vertex) on the examine event. If PROC returns #f, then don't examine the vertex.
See also Depth First Search Visitor dfs-visitor
set-dfs-visitor-tree-edge!
Form (set-dfs-visitor-tree-edge! PROC)
Description Call (PROC graph edge) on the tree-edge event
See also Depth First Search Visitor dfs-visitor
set-dfs-visitor-back-edge!
Form (set-dfs-visitor-back-edge! PROC)
Description Call (PROC graph edge) on the back-edge event
See also Depth First Search Visitor dfs-visitor
set-dfs-visitor-forward-or-cross-edge!
Form (set-dfs-visitor-forward-or-cross-edge! PROC)
Description Call (PROC graph edge) on the forward-or-cross-edge event
See also Depth First Search Visitor dfs-visitor
set-dfs-visitor-finish!
Form (set-dfs-visitor-finish! PROC)
Description Call (PROC graph vertex) on the finish event
See also Depth First Search Visitor dfs-visitor
13 Algorithm
14 Algorithm: Depth First Search
See Boost's Depth First Search for more details.
depth-first-search
Form (GTYPE-depth-first-search graph dfs-visitor color-map starting-vertex)
Description Depth first search.
Parameters graph The graph object.
dfs-visitor A DFS visitor object
color Property map for the 'color' property.
starting-vertex Either #f, or the vertex the DFS search will begin with
depth-first-visit
Form (GTYPE-depth-first-visit graph dfs-visitor color set-color! starting-vertex)
Description Depth first visit
Parameters graph The graph object.
dfs-visitor A DFS visitor object
color Property map for the 'color' property.
starting-vertex The vertex that will be DFS visited.
15 Algorithm: Topological Sort
See Boost's Topological Sort for more details.
topological-sort
Form (GTYPE-topological-sort graph)
Description Topological sort. Gets a reverse-sorted list of vertexes.
Parameters graph The graph object.
Returns A list of topologically reverse-sorted vertexes.
topological-sort*
Form (GTYPE-topological-sort* graph)
Description Topological sort. Gets a reverse-sorted stream of vertexes.
Parameters graph The graph object.
Returns A stream of topologically reverse-sorted vertexes.
16 Algorithm: Partition: Fiduccia-Mattheyses
Bipartitioning of a graph or hypergraph, minimizing a cost function, subject to a balancing criterion. Is a NP-Complete problem, so this method is a heuristic.
GTYPE-partition-fidmat
Form (GTYPE-partition-fidmat graph partition-map gain descriptor-map working-graph working-descriptor-map cost balance weight criterion split-level)
Description Fiduccia-Mattheyses Bipartitioning. Should never fail to find a bipartition, although it might be a bad partition if the balance criterion is too rigid. You will want to (randomize N) before calling this method, so you can have repeatable partitions.
Precondition working-graph must be of type GTYPE, and have GTYPE-neighbours method. gain must be in the range [-2*DEGREE,2*DEGREE], where DEGREE is the maximum degree of a vertex in graph. When a vertex is moved to another partition, the decrease in cost of the graph must be equal to the gain of the vertex.
Parameters graph The graph you want to partition.
partition-map A vertex property map that is has as its values either #t or #f. These are the two partitions a cell might belong to. This is the main output of the algorithm.
gain A vertex property getter. Must calculate the gain of a vertex. See section 1.2 of Design and Implementation of the Fiduccia-Mattheyses Heuristic for VLSI Netlist Partitioning. Basically, the gain is positive if it reduces the solution cost if the cell switched partitions, and negative if it increases the solution cost. And the magnitude of the gain *must* correspond to the change in solution cost. You can make sure by calling (set! GTYPE-partition-fidmat-check #t) before using (partition-fm ...).
descriptor-map A vertex property map that has as its values the edge descriptors for working-graph.
working-graph An empty graph that has quick edge(u,v) access, and memory flexibility to handle the same number of vertices as graph. O(E) = O(V).
working-descriptor-map A vertex property map on working-graph that has as its values the vertex descriptors for graph. It should, but is not required to, be an internal property map, since the working-graph is clear!ed repeatedly.
cost Procedure of 0-arg that calculates the cost of the current partition for 'cells'. This solution cost is usually the edge cost, although it may be anything.
balance Procedure of 3 arguments (weight n#f n#t). How much more do you have in the larger partition compared to the smaller partition? The result can range as an integer from 0 to 100, with 0 being perfectly balanced and 100 being perfectly imbalanced. The argument weight is the desired weighting of the partition. For example, if weight==(cons 3 7), then the perfect balance is when 30% of the cost is for those within partition #f, while 70% are within partition #t. Normally you would want '(1 . 1) for an equal bipartition. You can, and should, pass in the number in partition #f and the number in partition #t by using n#f and n#t. If you want to be very fast, set them to non-negative integers; otherwise, leave them #f otherwise.
weight A pair in the form (X . Y). If X=3 and Y=7, then perfectly balanced would mean that 3/10 of the cost is in partition #f, and 7/10 of the cost is in partition #t.
criterion A non-negative integer that is the maximum that the balance may be. If you use the range [0..100] for balance, then the range for criterion would be [0..100], and you might use criterion=35 to allow significant imbalances.
split-level 0 = Exit after first iteration (quickest).
1 = Exit when cost does not decrease by at least one-half.
2 = Exit when cost does not change.
partition-map Property map for the 'partition' boolean property.
GTYPE-partition-fidmat-check
Form GTYPE-partition-fidmat-check
Description Set to #t to check that the pre-conditions are met in GTYPE-partition-fidmat. Whenever a vertex moves partitions, the decrease in cost must be equal to the gain. Also, the gain must always be in the range [-2*DEGREE,2*DEGREE], where DEGREE is the maximum degree of any vertex. This takes a lot of CPU time to check, so only do this when you are debugging and verifying that your cost and gain functions correspond.
GTYPE-partition-fidmat-debug
Form GTYPE-partition-fidmat-debug
Description Set to #t to print debug statements when running GTYPE-partition-fidmat.
17 Utility
let-rgraph
Form (let-rgraph GTYPE (body) ...)
Description Create a lexical scope with bindings to the graph methods. The scope will have the following bindings: 
 make-graph
 add-edge!
 remove-edge!
 remove-edge2!
 out-edges
 out-edges*
 out-edges+
 out-degree
 in-edges
 in-edges*
 in-edge+
 in-degree
 	
 add-vertex!
 remove-vertex!
 vertex
 vertex-eq?
 num-vertices
 vertices
 vertices*
 vertices+
 clear!
 	
 source
 target
 edge-at
The + version of the binding (like vertices+) will be the stream version if it exists, else it will be the list version. These are useful with the remaining bindings which process the results of the + bindings: 
 for-each+
 map+
Parameters GTYPE The type name of the graph.
GTYPE-fill-graph!
Form (GTYPE-fill-graph! graph edges set-vertex-name!)
Description Fill graph from a list of edges, where each edge is a pair of the form '(vertex1 . vertex2). vertex1, vertex2, etc. must be comparable using eq?. Gets mutated graph. Will fill internal property 'vertex-name if defined. Will set vertex_descriptor if a hash vertex list.
Parameters graph The graph object.
edges A list of edges, each a pair of the form '(vertex1 . vertex2)
set-vertex-name! Property to set the name of a vertex. May be #f.
Returns Mutated, filled graph

Generated: August 3, 2004, 13:57:02
Generated by LAML SchemeDoc .