source: project/wiki/eggref/4/graphs @ 32629

Last change on this file since 32629 was 32629, checked in by Jeremy Steward, 5 years ago

Adds bitbucket mirror to graphs egg docs

File size: 20.9 KB
Line 
1== graphs
2
3Provides graphs, digraphs, multigraphs, and multidigraphs for CHICKEN 4.9+
4
5[[toc:]]
6
7== Overview
8
9The purpose of this egg is to provide a generic interface for graphs, digraphs, multigraphs and multidigraphs to CHICKEN Scheme. Compared to other combinatorial graphing eggs in the coop, this egg aims to be generic and cover a broad range of use cases. Moreover, unlike many graphing libraries, an interface for multigraphs and multidigraphs are provided.
10
11== Installation
12
13 $ chicken-install graphs
14
15or
16
17 $ chicken-install graphs -test
18
19if you want to run the tests for the egg in addition.
20
21== Usage
22
23 (use graphs)
24 (use graphs-derived)
25
26The latter module extends the primitives found in the graphs module to perform other graph-related functionality (e.g. searching for isomorphisms between graphs).
27
28== Description
29
30The graphs module is implemented primarily as a set of [[http://wiki.call-cc.org/eggref/4/coops|COOPS]] classes and methods that set up rules for managing vertices and edges within a (multi)(di)graph. The interface provides both destructive (!) and non-destructive operations for different graph primitives; however, all procedures start with {{graph-}}, regardless of the type of graph they are. Thanks to COOPS, everything dispatches properly and the rules for (multi)(di)graphs are maintained. This way, whether you're using a multigraph or a graph, you can still (for example) call {{(graph-vertex-add G 'a)}} and the vertex {{a}} will still be added to (multi)graph G.
31
32'''NOTE:''' for methods below, unless otherwise specified by distinguishing between (multi)(di)graph classes, all methods _should_ work without modification for every type of graph provided by this egg.
33
34=== graphs
35
36==== Classes
37
38<class><multidigraph></class>
39<class><multigraph></class>
40<class><digraph></class>
41<class><graph></class>
42
43The four primary classes that are provided by the module. These are exported here such that if you want to create your own methods using COOPS, and want to dispatch based on the type of graph, it is possible to do so.
44
45'''NOTE:''' {{<multigraph>}} is a subclass of {{<multidigraph>}}, and {{<graph>}} is a subclass of {{<digraph>}}. These all inherit from an {{<abstract-graph>}} class, but multigraph types and graph types are otherwise not related in any specific hierarchical way. The reason for this is that this model makes it easier to dispatch based on the possibility of multiple edges vs. dispatching on whether or not the edges are directed.
46
47==== Constructors
48
49<procedure>(make-multidigraph [#!rest attr])</procedure>
50<procedure>(make-multigraph [#!rest attr])</procedure>
51<procedure>(make-digraph [#!rest attr])</procedure>
52<procedure>(make-graph [#!rest attr])</procedure>
53
54Default procedures for creating and initializing (multi)(di)graph objects.
55
56; attr : A series of keyword / value pairs for graph attributes. For example, you may name your graph "Graph 1", which would be called as seen below. Note that keyword types are necessary (symbol ending with ':'), so you can't add attributes with keys of type symbol, string, etc.
57
58 (define G (make-graph name: "Graph 1"))
59
60==== General methods
61
62<method>(graph-copy (G <graph>))</method>
63
64Creates a shallow copy of (multi)(di)graph G, depending on the type of G. Deep copies are not provided, but they are typically unnecessary unless you are writing directly to a slot value or using {{set!}} haphazardly in your code. Using the methods provided by the graphs egg for primitive operations such as adding or removing vertices and edges should nullify this issue.
65
66This may not seem like a terribly useful method to have; however, using this in conjunction with destructive operations can help hide side effects on graphs. Because non-destructive operations have to construct a copy of the graph for small changes, they can have larger performance implications down the line (adding 1 vertex to a graph with 100000 vertices means you have to first copy the original graph and then add 1 vertex to that copy destructively). If anybody has any ideas for constructing an efficient functional hash-table or graph type, please let me know, as currently this implementation utilizes srfi-69, which provides traditional (and very imperative) hash-tables.
67
68<method>(graph->list (G <graph>))        [[DEPRECATED]]</method>
69
70'''NOTE:''' As of Release 0.4 this function is deprecated. It will likely be removed in the coming releases.
71
72Converts a graph-type object into an adjacency-list type format. Currently provides something along the lines of:
73
74 '((a {(b . <hash-table>) (c . <hash-table>)})
75   (b {(a . <hash-table>)})
76   (c {(a . <hash-table>)}))
77
78Where each hash-table is the properties of the edge. This was initially done to provide as sane means of displaying the adjacency table, but should not be relied upon in most cases.
79
80<method>(graph-attribute (G <graph>) keyword)</method>
81
82Allows one to retrieve the value of the attribute corresponding to keyword in the graph G.
83
84; G : the graph to search
85; keyword : the keyword corresponding to the value you wish to retrieve (e.g. ''name:'')
86
87<method>(graph-attribute-set (G <graph>) keyword value)</method>
88<method>(graph-attribute-set! (G <graph>) keyword value)</method>
89
90Sets an attribute for graph G.
91
92; G : the graph to set the attribute
93; keyword : some keyword which satisfies {{keyword?}}
94; value : any value for which keyword should correspond
95
96<method>(graph-vertex-exists? (G <graph>) vertex)</method>
97
98Predicate for checking if a vertex exists within graph G.
99
100; G : the graph to check
101; vertex : the identifier for the vertex (can be anything)
102
103<method>(graph-adjacent? (G <multidigraph>) u v [id])</method>
104<method>(graph-adjacent? (G <multigraph>) u v [id])</method>
105<method>(graph-adjacent? (G <digraph>) u v)</method>
106<method>(graph-adjacent? (G <graph>) u v)</method>
107
108Predicate to check if an edge exists between vertices u and v (in other words, is v adjacent to u?). For multigraph types, an optional {{id}} argument can also be passed, to differentiate between multiple edges.
109
110; G : the graph to check
111; u : the head vertex
112; v : the tail vertex
113; id : an optional argument for multigraph-types which allows one to specify which edge you may be looking for (where {{id}} is a unique identifier). Passing id when calling this method with a graph type will result in an error.
114
115<method>(graph-neighbours (G <multidigraph>) vertex)</method>
116<method>(graph-neighbours (G <multigraph>) vertex)</method>
117<method>(graph-neighbours (G <digraph>) vertex)</method>
118<method>(graph-neighbours (G <graph>) vertex)</method>
119
120Returns the set or multiset of adjacent vertices to the provided vertex. If called with a multigraph type, the multiset contains pair-lists with the adjacent vertex identifier as well as the unique id field for each edge. E.g. if vertex a has two edges to b, labeled with {{id}} 1 and 2 respectively, the multiset returned will be {(b 1) (b 2)}. If this was instead a regular graph, then the returned set would be {b}.
121
122; G : the graph to search neighbours within
123; vertex : the vertex whose neighbours you wish to receive
124
125'''NOTE:''' raises an error if the vertex does not exist.
126
127<procedure>(graph? G)</procedure>
128
129Predicate for testing whether or not a value is a graph type. This does ''NOT'' test that an object is of type <class <graph>>, but whether something is a graph at all. Therefore, this returns #t iff the type of G is <multidigraph>, <multigraph>, <digraph>, <graph>, or some descendent thereof, else returns #f.
130
131; G : the object to test
132
133<procedure>(digraph? G)</procedure>
134
135Predicate for testing whether or not a value is a directed graph. Returns #t iff the type of G is <multidigraph> or <digraph>. Otherwise returns #f.
136
137; G : the object to test
138
139<procedure>(multigraph? G)</procedure>
140
141Predicate for testing if a graph is a multigraph (a graph that can allow multiple edges). Returns #t iff G is of type <multidigraph>, <multigraph>, or some descendent thereof. Otherwise returns #f.
142
143; G : the object to test
144
145==== Vertex methods
146
147<method>(graph-vertex (G <graph>) vertex)</method>
148
149Returns a hash table of the attributes for a vertex in G.
150
151; G : the graph to search
152; vertex : the vertex of which you wish to get the attributes of
153
154<method>(graph-vertices (G <graph>))</method>
155
156Returns a set V containing all the vertices in graph G.
157
158; G : the graph whose vertices you want.
159
160<method>(graph-vertex-add (G <graph>) vertex [#!rest attr])</method>
161<method>(graph-vertex-add! (G <graph>) vertex [#!rest attr])</method>
162
163Adds a vertex with attributes {{attr}} to a graph G. Raises an error if the vertex already exists within the graph.
164
165; G : the graph you wish to add a vertex to
166; vertex : the vertex (identifier) you wish to add
167; attr : a series of keyword / value pairs that define vertex attributes
168
169<method>(graph-vertex-remove (G <graph>) vertex)</method>
170<method>(graph-vertex-remove! (G <graph>) vertex)</method>
171
172Removes a vertex and all associated edges / vertex attributes from the graph G. Raises an error if the vertex does not exist within the graph.
173
174; G : the graph you wish to remove the vertex from
175; vertex : the vertex you wish to remove
176
177<method>(graph-vertex-update (G <graph>) vertex [#!rest attr])</method>
178<method>(graph-vertex-update! (G <graph>) vertex [#!rest attr])</method>
179
180Updates the vertex attributes for a vertex in graph G. Raises an error if the vertex does not exist within the graph.
181
182; G : the graph to update
183; vertex : the vertex whose attributes you wish to modify
184; attr : a series of keyword / value pairs which describe attributes to add to the vertex
185
186E.g.:
187
188 (graph-vertex-update G 'a colour: "red" size: 4)
189
190==== Edge methods
191
192<method>(graph-edge (G <multidigraph>) u v id)</method>
193<method>(graph-edge (G <multigraph>) u v id)</method>
194<method>(graph-edge (G <digraph>) u v)</method>
195<method>(graph-edge (G <graph>) u v)</method>
196
197Returns an alist of the attributes for edge u->v in G. If u->v does not exist in G, an error is raised.
198
199; G : the graph
200; u : the head vertex
201; v : the tail vertex
202; id : (multigraph-types only) distinguishes which edge amongst multiple edges
203
204<method>(graph-edge-add (G <multidigraph>) u v id [#!rest attr])</method>
205<method>(graph-edge-add (G <multigraph>) u v id [#!rest attr])</method>
206<method>(graph-edge-add (G <digraph>) u v [#!rest attr])</method>
207<method>(graph-edge-add (G <graph>) u v [#!rest attr])</method>
208<method>(graph-edge-add! (G <multidigraph>) u v id [#!rest attr])</method>
209<method>(graph-edge-add! (G <multigraph>) u v id [#!rest attr])</method>
210<method>(graph-edge-add! (G <digraph>) u v [#!rest attr])</method>
211<method>(graph-edge-add! (G <graph>) u v [#!rest attr])</method>
212
213Adds an edge u->v to the graph G. Optional attributes can be added as keyword / value pairs in {{attr}}. Note that for multigraph-types, an identifier ({{id}}) is needed to distinguish edges (can be anything that compares with {{equal?}}). For undirected graph types this adds u->v and v->u to the graph since the distinction is meaningless.
214
215Raises an error if the edge already exists or already exists with the ID {{id}}. If either of the vertices {{u}} or {{v}} do not exist when this method is called, they are first added to the graph, and the edge added afterwards.
216
217; G : the graph to add the edge to
218; u : the head vertex
219; v : the tail vertex
220; id : an identifier (compares with {{equal?}}) for the edge (in cases where multiple edges can exist). '''NOTE:''' Do not set {{id}} to be #f, as this can cause problems with removing edges later, and makes no logical sense.
221; attr : a list of keyword / value pairs
222
223<method>(graph-edge-remove (G <multidigraph>) u v [id])</method>
224<method>(graph-edge-remove (G <multigraph>) u v [id])</method>
225<method>(graph-edge-remove (G <digraph>) u v)</method>
226<method>(graph-edge-remove (G <graph>) u v)</method>
227<method>(graph-edge-remove! (G <multidigraph>) u v [id])</method>
228<method>(graph-edge-remove! (G <multigraph>) u v [id])</method>
229<method>(graph-edge-remove! (G <digraph>) u v)</method>
230<method>(graph-edge-remove! (G <graph>) u v)</method>
231
232Removes an edge u->v from the graph G. For multigraph types, if {{id}} is specified, it removes the edge u->v with ID {{id}}, otherwise removes all edges u->v. For undirected graphs, the edge u->v and v->u are both removed, as there is no distinction between the two.
233
234Raises an error if the edge u->v does not exist in graph G.
235
236; G : the graph to remove the edge from
237; u : the head vertex
238; v : the tail vertex
239; id : (multigraph-types only) Specifies which edge with this identifier to remove, or removes all edges u->v if this is #f or not passed in.
240
241<method>(graph-edge-update (G <multidigraph>) u v id [#!rest attr])</method>
242<method>(graph-edge-update (G <multigraph>) u v id [#!rest attr])</method>
243<method>(graph-edge-update (G <digraph>) u v [#!rest attr])</method>
244<method>(graph-edge-update (G <graph>) u v [#!rest attr])</method>
245<method>(graph-edge-update! (G <multidigraph>) u v id [#!rest attr])</method>
246<method>(graph-edge-update! (G <multigraph>) u v id [#!rest attr])</method>
247<method>(graph-edge-update! (G <digraph>) u v [#!rest attr])</method>
248<method>(graph-edge-update! (G <graph>) u v [#!rest attr])</method>
249
250Updates the attributes for an edge u->v in graph G, with ID {{id}} if the graph is a multigraph. Raises an error if the edge u->v does not exist.
251
252; G : the graph to update
253; u : the head vertex of the edge to update
254; v : the tail vertex of the edge to update
255; id : (multigraph-types only) the ID of the edge whose attributes you wish to update
256; attr : a set of keyword / value pairs describing attributes to add to the edge
257
258==== Other methods
259
260<method>(graph-simple? (G <graph>))</method>
261
262Predicate for testing whether or not a graph G is simple. A graph is considered simple if it does not contain multiple edges and has no loops (i.e. edges that go from u->u). Given this definition, even if a graph has a type of <multidigraph> or <multigraph>, so long as no vertices actually _contain_ multiple edges, {{graph-simple?}} can still evaluate to #t. If multiple edges or loops are present, then {{graph-simple?}} will evaluate to #f.
263
264<method>(graph-indegree (G <digraph>) vertex)</method>
265
266Computes the indegree of a vertex in a directed graph G. When called with an undirected graph, returns the same as {{graph-degree}}.
267
268<method>(graph-outdegree (G <digraph>) vertex)</method>
269
270Computes the outdegree of a vertex in a directed graph G. When called with an undirected graph, returns the same as {{graph-degree}}.
271
272<method>(graph-degree (G <graph>) vertex)</method>
273
274Computes the degree (number of edges coming in and out of) a vertex in a graph G.
275
276<method>(graph-order (G <graph>))</method>
277
278Returns the order of the graph. The order of a graph is defined as the number of unique vertices within a graph.
279
280=== graphs-derived
281
282==== Isomorphism
283
284The set of procedures below implement the VF2 algorithm for graph/subgraph isomorphism checking. To be clear with how these work, a short explanation of the implementation is provided. Specifically, there is some confusion as to what is meant by "subgraph isomorphism." In some circles, it is treated as "there is no subgraph in G1 that is isomorphic to some other graph G2." Here, subgraph isomorphism is taken to mean subgraph isomorphism as treated by the authors of the original VF2 algorithm, that is, "'''a graph G1 is subgraph isomorphic to another graph G2 if there exists some subgraph in G1 which has a direct isomorphism to graph G2.'''" In effect, this means that the order you input your graphs matters when testing for subgraph isomorphism.
285
286The second major thing to bear in mind is the {{semantic-feasibility?}} argument that shows up in each of the procedures below. The original authors of the VF2 paper divided their evaluation of an isomorphism into two feasibility categories: semantic and syntactic. Syntactic feasibility defines a set of rules that evaluates whether the structure of a partial mapping between two graphs provides a feasible isomorphism. However, the authors did not specify a unique or specific way to determine semantic feasibility. The reason for this is because semantic feasibility deals with evaluating whether two vertices ''n'' and ''m'' can be added to the partial mapping ''s'' based on their attributes. In the original paper the attributes of their edges (weights, length, etc.) were evaluated as semantically feasible if they existed within some tolerance (to maintain a sense of scale). Consequently, this worked well for the application the authors had in mind, but means nothing for every isomorphism problem in general. Therefore, no particular semantic-feasibility? procedure is assumed, and the default is just a dummy procedure that always returns true (this means we effectively ignore semantic information about the vertices).
287
288To construct a custom procedure to evaluate semantic feasibility, it should ideally be written as below:
289
290<procedure>(semantic-feasibility? G1 G2 s n m) => bool</procedure>
291
292Evaluates semantic feasibility of adding vertices ''n'' from G1 and ''m'' from G2 to the partial mapping ''s''. This can be done by evaluating the vertex attributes between ''n'' and ''m'', or by evaluating the edge attributes of ''n'' and its neighbours in G1 to that of ''m'' and its neighbours in G2.
293
294; G1 : the first graph
295; G2 : the second graph
296; s : the partial mapping between G1 and G2. Represented as a set of pairs (N . M) of feasible matches between G1 and G2
297; n : a candidate vertex from G1
298; m : a candidate vertex from G2
299
300<procedure>(graph-isomorphisms G1 G2 #!optional semantic-feasibility?)</procedure>
301<procedure>(subgraph-isomorphisms G1 G2 #!optional semantic-feasibility?)</procedure>
302
303Returns a lazy-seq of all match sets between G1 and G2. Each isomorphism in the lazy-seq is represented as a set of pairs which lists the match between G1 and G2. If subgraph-isomorphisms is used instead, the algorithm attempts to find a subgraph in G1 that is isomorphic to G2.
304
305; G1 : the first graph
306; G2 : the second graph
307; semantic-feasibility? : a procedure which evaluates semantic feasibility for a candidate pair. See discussion above.
308
309<procedure>(graph-isomorphisms-list G1 G2 #!optional semantic-feasibility?)</procedure>
310<procedure>(subgraph-isomorphisms-list G1 G2 #!optional semantic-feasibility?)</procedure>
311
312Same as above, however returns a list instead of a lazy-seq. I suggest avoiding these, as there may be many isomorphisms between two large graphs. As a result, the runtime of this is not necessarily known.
313
314<procedure>(graph-isomorphic? G1 G2 #!optional semantic-feasibility?)</procedure>
315<procedure>(subgraph-isomorphic? G1 G2 #!optional semantic-feasibility?)</procedure>
316
317Predicate which tests if a graph G1 is isomorphic or subgraph-isomorphic to G2.
318
319; G1 : the first graph
320; G2 : the second graph
321; semantic-feasibility? : a procedure which evaluates semantic feasibility for a candidate pair. See discussion above.
322
323== Repository
324
325[[https://github.com/ThatGeoGuy/chicken-graphs/|Github]], [[https://bitbucket.org/ThatGeoGuy/chicken-graphs|BitBucket]]
326
327== Examples
328
329To come later. In the meantime, send an email to chicken-users or myself (you can find the email on Github) if you stumble into trouble.
330
331== Version History
332
333; 0.4.2 : Bug fix for graph-edge-add regression when used with multidigraphs. Test cases added for make procedures and predicates
334; 0.4.1 : Bug fix for graph-edge -> return a hash-table instead of an alist. Documentation fixes.
335; 0.4 : Simplified implementation details for API and performance improvements for isomorphism functionality. graph-vertex returns a hash-table, not an alist.
336; 0.3 : Adds graphs-derived module for isomorphism (VF2) functionality.
337; 0.2 : Initial release to the coop under BSD3 license
338
339== License
340
341 Copyright (c) 2015, Jeremy Steward
342 All rights reserved.
343 
344 Redistribution and use in source and binary forms, with or without
345 modification, are permitted provided that the following conditions are met:
346 
347 1. Redistributions of source code must retain the above copyright notice,
348 this list of conditions and the following disclaimer.
349 
350 2. Redistributions in binary form must reproduce the above copyright notice,
351 this list of conditions and the following disclaimer in the documentation
352 and/or other materials provided with the distribution.
353 
354 3. Neither the name of the copyright holder nor the names of its
355 contributors may be used to endorse or promote products derived from this
356 software without specific prior written permission.
357 
358 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
359 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
360 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
361 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
362 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
363 CONSEQUENTIAL DAMAGES  INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
364 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
365 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
366 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
367 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
368 POSSIBILITY OF SUCH DAMAGE.
Note: See TracBrowser for help on using the repository browser.