source: project/wiki/eggref/5/graph-separators @ 37088

Last change on this file since 37088 was 37088, checked in by Ivan Raikov, 23 months ago

c5 doc for graph-separators

File size: 3.3 KB
Line 
1[[tags:egg]]
2
3== graph-separators
4
5Determine the separation vertices of a graph.
6
7[[toc:]]
8
9== Documentation
10
11
12A graph is said to have a separation vertex {{v}} (sometimes called an
13articulation point) if there exist vertices {{a}} and {{b}}, where {{a
14!= b}} and {{b != v}}, and all paths connecting {{a}} and {{b}} pass
15through {{v}}. A graph which has a separation vertex is called
16separable, and one which has none is called non-separable.
17
18=== Procedures
19
20
21<procedure>graph-separation-vertices:: G -> SEPARATORS * COMPONENTS</procedure>
22
23Computes the separation vertices of the given graph. Returns a list of
24separation vertices and a list of graph components that contain a
25separation vertex.
26
27
28
29== Examples
30
31
32 (import scheme (chicken base)srfi-1 digraph graph-separators)
33 
34 (define g (make-digraph 'depgraph "dependency graph"))
35 
36 (define used-by
37    (list
38      (cons 'dax_h 'foo_cpp) (cons 'def_h 'foo_cpp) (cons 'xyz_h 'foo_cpp)
39      (cons 'foo_cpp 'libfoobar_a ) (cons 'foo_cpp 'libzigzag_a)
40      (cons 'libfoobar_a 'app) (cons 'libzigzag_a 'app)
41    ))
42 
43 (define node-list (delete-duplicates
44                   (concatenate (list (map car used-by) (map cdr used-by)))))
45 
46 (define node-ids (list-tabulate (length node-list) values))
47 
48 (for-each (lambda (i n) (add-node! g i (list #f n))) node-ids node-list)
49 (define node-map (zip node-list node-ids))
50 
51 (for-each (lambda (e)
52            (match e ((ni . nj) (let ((i (car (alist-ref ni node-map)))
53                                      (j (car (alist-ref nj node-map))))
54                                  (add-edge! g (list i j (format "~A->~A" ni nj)))))
55                   (else (error "invalid edge " e))))
56          used-by)
57 
58 (graph-separation-vertices g)
59 
60 
61
62== About this egg
63
64
65=== Author
66
67Richard Kelsey; ported to Chicken by [[/users/ivan-raikov|Ivan Raikov]]
68
69=== Version history
70
71; 2.0 : Ported to Chicken 5
72; 1.4 : Documentation converted to wiki format
73; 1.3 : Ported to Chicken 4
74; 1.0 : Initial release
75
76
77=== License
78
79 Copyright by Richard Kelsey.
80 
81 Redistribution and use in source and binary forms, with or without
82 modification, are permitted provided that the following conditions
83 are met:
84 
85 - Redistributions of source code must retain the above copyright
86 notice, this list of conditions and the following disclaimer.
87 
88 - Redistributions in binary form must reproduce the above
89 copyright notice, this list of conditions and the following
90 disclaimer in the documentation and/or other materials provided
91 with the distribution.
92 
93 - Neither name of the copyright holders nor the names of its
94 contributors may be used to endorse or promote products derived
95 from this software without specific prior written permission.
96 
97 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND THE
98 CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
99 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
100 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
101 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR THE
102 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
103 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
104 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
105 USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
106 AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
107 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
108 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
109 POSSIBILITY OF SUCH DAMAGE.
Note: See TracBrowser for help on using the repository browser.