source: project/wiki/eggref/5/digraph @ 37636

Last change on this file since 37636 was 36981, checked in by Ivan Raikov, 22 months ago

updated digraph api info

File size: 6.5 KB
Line 
1[[tags:egg]]
2
3== digraph
4
5Directed graph in adjacency list format.
6
7[[toc:]]
8
9== Documentation
10
11
12The {{digraph}} library is an implementation of a directed graph, where
13the edges are stored as adjacency lists indexed by node number.
14
15The present version implements a [[yasos|yasos object]]
16that provides a number of methods for graph operations.
17
18=== Directed graph procedures
19
20
21The digraph object is created by procedure {{make-digraph}}:
22
23<procedure>make-digraph:: NAME INFO [NODE-LIST [SUCC-LIST [PRED-LIST]]] -> SELECTOR</procedure>
24
25where:
26
27* {{NAME}} is the graph name (string or symbol)
28* {{INFO}} is an optional metadata object of an arbitrary type or {{#f}}
29* {{NODE-LIST}} is an optional list of nodes to be inserted in the graph; each element of the list must be of the form {{(N INFO)}} where {{N}} is a unique node number (integer), and {{INFO}} is an optional metadata object describing the node.
30* {{SUCC-LIST}} and {{PRED-LIST}} can be used to define the graph edges upon graph creation. If supplied, these arguments must be lists in which every element is of the form {{(I J INFO)}}, where {{I}} and {{J}} are node numbers, and {{INFO}} is an optional metadata object.
31
32
33The returned [[yasos]] object supports the following operations:
34
35; {{name}} : returns the graph name (string or symbol)
36; {{info}} : returns the graph metadata (arbitrary type)
37; {{new-id!}} : returns a procedure with no arguments, which returns the lowest available node number
38; {{add-node!}} : procedure {{LAMBDA N INFO}} which inserts in the graph node with number {{N}} and metadata {{INFO}}; if the node already exists in the graph, it will be overwritten with the new metadata
39; {{add-edge!}} : procedure {{LAMBDA EDGE}} which inserts in the graph the specifed edge; the edge is given by a list of the form {{(I J INFO)}}, where {{I}} and {{J}} are source and destination nodes, respectively, and {{INFO}} is edge metadata of arbitrary type
40; {{remove-node!}} : procedure {{LAMBDA N}} which removes node {{N}} and all its edges from the graph
41; {{nodes}} : returns a list with the nodes of the graph and their metadata
42; {{edges}} : returns a list with the edges of the graph and their metadata
43; {{roots}} : returns a list with all nodes in the graph that do not have an predecessor
44; {{terminals}} : which returns a list with all nodes in the graph that do not have a successor
45; {{order}} : returns the number of nodes in the graph
46; {{size}} : returns the number of edges in the graph
47; {{capacity}} : returns the size of the underlying dynamic vector
48; {{succ}} : procedure {{LAMBDA N}} which returns a list with the successor nodes of node {{N}}
49; {{pred}} : procedure {{LAMBDA N}} which returns a list with the predecessor nodes of node {{N}}
50; {{succ-list}} : returns a list containing the successor nodes for each node.
51; {{pred-list}} : returns a list containing the predecessor nodes for each node.
52; {{out-edges}} : procedure {{LAMBDA N}} which returns a list with the outgoing edges of node {{N}}
53; {{in-edges}} : procedure {{LAMBDA N}} which returns a list with the incoming edges of node {{N}}
54; {{has-edge}} : procedure {{LAMBDA I J}} which returns true if edge {{I -> J}} exists in the graph and false otherwise
55; {{has-node}} : procedure {{LAMBDA N}} which returns true if node {{N}} exists in the graph and false otherwise
56; {{node-info}} : procedure {{LAMBDA N}} which returns the metadata for node {{N}}
57; {{node-info-set!}} : procedure {{LAMBDA N V}} which sets the metadata for node {{N}}
58; {{foreach-node}} : procedure {{LAMBDA F}} which iterates over the nodes in the graph by invoking function {{F}} on the node number and metadata of each node
59; {{foreach-edge}} : procedure {{LAMBDA F}} which iterates over the edges in the graph by invoking function {{F}} on each edge
60
61
62== Examples
63
64 ;; example adapted from graph example in the Boost library documentation
65 (import srfi-1 digraph matchable)
66   
67 (define g (make-digraph 'depgraph "dependency graph"))
68   
69 (define used-by
70    (list
71      (cons 'dax_h 'foo_cpp) (cons 'dax_h 'bar_cpp) (cons 'dax_h 'yow_h)
72      (cons 'yow_h 'bar_cpp) (cons 'yow_h 'zag_cpp) (cons 'boz_h 'bar_cpp)
73      (cons 'boz_h 'zig_cpp) (cons 'boz_h 'zag_cpp) (cons 'zow_h 'foo_cpp)
74      (cons 'foo_cpp 'foo_o) (cons 'foo_o 'libfoobar_a)
75      (cons 'bar_cpp 'bar_o) (cons 'bar_o 'libfoobar_a)
76      (cons 'libfoobar_a 'libzigzag_a) (cons 'zig_cpp 'zig_o)
77      (cons 'zig_o 'libzigzag_a) (cons 'zag_cpp 'zag_o)
78      (cons 'zag_o 'libzigzag_a) (cons 'libzigzag_a 'killerapp)))
79 
80 
81 (define node-list (delete-duplicates
82                   (concatenate (list (map car used-by) (map cdr used-by)))))
83 
84 (define node-ids (list-tabulate (length node-list) values))
85 
86 (for-each (lambda (i n) (add-node! g i n)) node-ids node-list)
87 (define node-map (zip node-list node-ids))
88 
89 (for-each (lambda (e)
90            (match e ((ni . nj) (let ((i (car (alist-ref ni node-map)))
91                                      (j (car (alist-ref nj node-map))))
92                                  (add-edge! g (list i j (format "~A->~A" ni nj)))))
93                   (else (error "invalid edge " e))))
94          used-by)
95 (print (nodes g))
96 (print (edges g))
97 
98 (remove-node! g 0)
99 (print (nodes g))
100 (print (edges g))
101
102== About this egg
103
104
105=== Author
106
107[[/users/ivan-raikov|Ivan Raikov]]
108
109=== Version history
110
111; 2.0 : Ported to CHICKEN 5 and yasos
112; 1.16 : Added terminals message to digraph object
113; 1.15 : Ensure unit test script return proper exit code
114; 1.13 : Added test as a test dependency
115; 1.12 : Converted documentation to wiki format
116; 1.11 : Ported to Chicken 4
117; 1.10 : Now using matchable extension
118; 1.9 : Added procedures pred-list and succ-list
119; 1.8 : Added procedure node-info-set!
120; 1.7 : Build script updated for better cross-platform compatibility
121; 1.6 : Test infrastructure changed to use testbase
122; 1.5 : Bug fixes in set-out-edges! and set-in-edges! [thanks to Andreas Scholta]
123; 1.4 : License upgrade to GPL v3
124; 1.3 : Updated the roots procedure to match the documentation
125; 1.2 : Minor changes to the setup script
126; 1.1 : Added support for chicken-setup -test
127; 1.0 : Initial release
128
129
130=== License
131
132 Copyright 2007-2018 Ivan Raikov.
133 
134 This program is free software: you can redistribute it and/or modify
135 it under the terms of the GNU General Public License as published by
136 the Free Software Foundation, either version 3 of the License, or (at
137 your option) any later version.
138 
139 This program is distributed in the hope that it will be useful, but
140 WITHOUT ANY WARRANTY; without even the implied warranty of
141 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
142 General Public License for more details.
143 
144 A full copy of the GPL license can be found at
145 <http://www.gnu.org/licenses/>.
146
Note: See TracBrowser for help on using the repository browser.