1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
|
<html>
<head>
<title>clojure contrib - graph API reference</title>
<link href="file/view/favicon.png" rel="icon" />
<link href="file/view/favicon.png" rel="shortcut icon" />
<link media="all" type="text/css" href="static/clojure.css" rel="stylesheet" />
<link media="all" type="text/css" href="static/wiki.css" rel="stylesheet" />
<link media="all" type="text/css" href="static/internal.css" rel="stylesheet" />
<!-- TODO: are we using these (from clojure.org)? If so, add the files -->
<script src="file/view/code_highlighter.js" type="text/javascript"></script>
<script src="file/view/clojure.js" type="text/javascript"></script>
<style>.menuWrapper{height: 36px;}</style>
<!--[if lte IE 6]>
<link rel="stylesheet" href="http://www.wikispaces.com/_/2009051601/s/internal_ie.css" type="text/css" />
<![endif]-->
</head>
<!--
This document was auto-generated from the clojure.contrib source by contrib-autodoc.
To report errors or ask questions about the overall documentation structure, formatting,
etc., contact Tom Faulhaber (google mail name: tomfaulhaber).
For errors in the documentation of a particular namespace, contact the author of that
namespace.
-->
<body>
<div id="AllContentContainer">
<div id="Header">
<a id="Logo" href="index.html"><img alt="Clojure" height="100" width="100" src="file/view/clojure-icon.gif" /></a>
<h1><a title="Clojure" href="index.html">Clojure</a></h1>
</div>
<div id="leftcolumn"><div><div style="text-align: center;"></div>
<div class="menu">
<div class="WikiCustomNav WikiElement wiki">
<a class="wiki_link" href="index.html">Overview</a><br />
<a class="wiki_link" href="api-index.html">API Index</a><br />
<a class="wiki_link" href="#">Namespaces:</a>
<ul id="left-sidebar-list">
<li><a href="accumulators-api.html" class="wiki_link">accumulators</a></li><li><a href="agent-utils-api.html" class="wiki_link">agent-utils</a></li><li><a href="classpath-api.html" class="wiki_link">classpath</a></li><li><a href="combinatorics-api.html" class="wiki_link">combinatorics</a></li><li><a href="command-line-api.html" class="wiki_link">command-line</a></li><li><a href="complex-numbers-api.html" class="wiki_link">complex-numbers</a></li><li><a href="cond-api.html" class="wiki_link">cond</a></li><li><a href="condition-api.html" class="wiki_link">condition</a></li><li><a href="core-api.html" class="wiki_link">core</a></li><li><a href="dataflow-api.html" class="wiki_link">dataflow</a></li><li><a href="datalog-api.html" class="wiki_link">datalog</a></li><li><a href="def-api.html" class="wiki_link">def</a></li><li><a href="duck-streams-api.html" class="wiki_link">duck-streams</a></li><li><a href="error-kit-api.html" class="wiki_link">error-kit</a></li><li><a href="except-api.html" class="wiki_link">except</a></li><li><a href="fcase-api.html" class="wiki_link">fcase</a></li><li><a href="find-namespaces-api.html" class="wiki_link">find-namespaces</a></li><li><a href="fnmap-api.html" class="wiki_link">fnmap</a></li><li><a href="gen-html-docs-api.html" class="wiki_link">gen-html-docs</a></li><li><a href="generic.arithmetic-api.html" class="wiki_link">generic.arithmetic</a></li><li><a href="generic.collection-api.html" class="wiki_link">generic.collection</a></li><li><a href="generic.comparison-api.html" class="wiki_link">generic.comparison</a></li><li><a href="generic.functor-api.html" class="wiki_link">generic.functor</a></li><li><a href="generic.math-functions-api.html" class="wiki_link">generic.math-functions</a></li><li><a href="graph-api.html" class="wiki_link">graph</a></li><li><a href="greatest-least-api.html" class="wiki_link">greatest-least</a></li><li><a href="http.agent-api.html" class="wiki_link">http.agent</a></li><li><a href="http.connection-api.html" class="wiki_link">http.connection</a></li><li><a href="import-static-api.html" class="wiki_link">import-static</a></li><li><a href="jar-api.html" class="wiki_link">jar</a></li><li><a href="java-utils-api.html" class="wiki_link">java-utils</a></li><li><a href="javadoc.browse-api.html" class="wiki_link">javadoc.browse</a></li><li><a href="jmx-api.html" class="wiki_link">jmx</a></li><li><a href="json.read-api.html" class="wiki_link">json.read</a></li><li><a href="json.write-api.html" class="wiki_link">json.write</a></li><li><a href="lazy-seqs-api.html" class="wiki_link">lazy-seqs</a></li><li><a href="lazy-xml-api.html" class="wiki_link">lazy-xml</a></li><li><a href="logging-api.html" class="wiki_link">logging</a></li><li><a href="macro-utils-api.html" class="wiki_link">macro-utils</a></li><li><a href="macros-api.html" class="wiki_link">macros</a></li><li><a href="map-utils-api.html" class="wiki_link">map-utils</a></li><li><a href="math-api.html" class="wiki_link">math</a></li><li><a href="miglayout-api.html" class="wiki_link">miglayout</a></li><li><a href="mmap-api.html" class="wiki_link">mmap</a></li><li><a href="monadic-io-streams-api.html" class="wiki_link">monadic-io-streams</a></li><li><a href="monads-api.html" class="wiki_link">monads</a></li><li><a href="ns-utils-api.html" class="wiki_link">ns-utils</a></li><li><a href="pprint-api.html" class="wiki_link">pprint</a></li><li><a href="probabilities.finite-distributions-api.html" class="wiki_link">probabilities.finite-distributions</a></li><li><a href="probabilities.monte-carlo-api.html" class="wiki_link">probabilities.monte-carlo</a></li><li><a href="probabilities.random-numbers-api.html" class="wiki_link">probabilities.random-numbers</a></li><li><a href="profile-api.html" class="wiki_link">profile</a></li><li><a href="prxml-api.html" class="wiki_link">prxml</a></li><li><a href="repl-ln-api.html" class="wiki_link">repl-ln</a></li><li><a href="repl-utils-api.html" class="wiki_link">repl-utils</a></li><li><a href="seq-utils-api.html" class="wiki_link">seq-utils</a></li><li><a href="server-socket-api.html" class="wiki_link">server-socket</a></li><li><a href="set-api.html" class="wiki_link">set</a></li><li><a href="shell-out-api.html" class="wiki_link">shell-out</a></li><li><a href="singleton-api.html" class="wiki_link">singleton</a></li><li><a href="sql-api.html" class="wiki_link">sql</a></li><li><a href="str-utils-api.html" class="wiki_link">str-utils</a></li><li><a href="str-utils2-api.html" class="wiki_link">str-utils2</a></li><li><a href="stream-utils-api.html" class="wiki_link">stream-utils</a></li><li><a href="swing-utils-api.html" class="wiki_link">swing-utils</a></li><li><a href="trace-api.html" class="wiki_link">trace</a></li><li><a href="types-api.html" class="wiki_link">types</a></li><li><a href="with-ns-api.html" class="wiki_link">with-ns</a></li><li><a href="zip-filter-api.html" class="wiki_link">zip-filter</a></li>
</ul>
</div>
</div>
</div></div>
<div id="rightcolumn">
<div id="Content">
<div class="contentBox"><div class="innerContentBox">
<div style="" id="WikiAdMargin">
<div id="content_view" class="wiki wikiPage">
<!-- Temporary disclaimer -->
<div style="background-color: #FF0000; font-weight: bold;">
NOTE: These autogen pages are still under development.
Not all links work. Not all formatting is done.
Contact Tom Faulhaber (tomfaulhaber on github, gmail, etc.)
with any questions.
</div>
<div id="right-sidebar"><div><div id="toc">
<h1 class="nopad">Table of Contents</h1>
<div style="margin-left: 1em;" class="toc-section">
<a href="#toc0">Overview</a>
<div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/add-loops">add-loops</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/component-graph">component-graph</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/dependency-list">dependency-list</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/fixed-point">fixed-point</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/get-neighbors">get-neighbors</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/lazy-walk">lazy-walk</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/post-ordered-nodes">post-ordered-nodes</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/recursive-component?">recursive-component?</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/remove-loops">remove-loops</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/reverse-graph">reverse-graph</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/scc">scc</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/self-recursive-sets">self-recursive-sets</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/stratification-list">stratification-list</a>
</div><div style="margin-left: 1em;" class="toc-entry">
<a href="#graph/transitive-closure">transitive-closure</a>
</div>
<br />
</div>
</div>
</div></div>
<div id="content-tag"><div><h1 id="overview">API for <span id="namespace-name">graph</span></h1>
by <span id="author">Jeffrey Straszheim</span><br />
<br />Usage:
<pre>
(ns your-namespace
(:require <span id="long-name">clojure.contrib.graph</span>))
</pre><pre>
</pre><h2>Overview</h2>
<pre id="namespace-docstr">Basic graph theory algorithms</pre>
<br />
<h2>Public Variables and Functions</h2>
<div id="var-entry">
<hr />
<h2 id="graph/add-loops">add-loops</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (add-loops g)
</pre>
<pre id="var-docstr">For each node n, add the edge n->n if not already present.</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L49" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/component-graph">component-graph</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (component-graph g)
(component-graph g sccs)
</pre>
<pre id="var-docstr">Given a graph, perhaps with cycles, return a reduced graph that is acyclic.
Each node in the new graph will be a set of nodes from the old.
These sets are the strongly connected components. Each edge will
be the union of the corresponding edges of the prior graph.</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L133" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/dependency-list">dependency-list</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (dependency-list g)
</pre>
<pre id="var-docstr">Similar to a topological sort, this returns a vector of sets. The
set of nodes at index 0 are independent. The set at index 1 depend
on index 0; those at 2 depend on 0 and 1, and so on. Those withing
a set have no mutual dependencies. Assume the input graph (which
much be acyclic) has an edge a->b when a depends on b.</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L190" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/fixed-point">fixed-point</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (fixed-point data fun max equal)
</pre>
<pre id="var-docstr">Repeatedly apply fun to data until (equal old-data new-data)
returns true. If max iterations occur, it will throw an
exception. Set max to nil for unlimited iterations.</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L167" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/get-neighbors">get-neighbors</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (get-neighbors g n)
</pre>
<pre id="var-docstr">Get the neighbors of a node.</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L29" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/lazy-walk">lazy-walk</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (lazy-walk g n)
(lazy-walk g ns v)
</pre>
<pre id="var-docstr">Return a lazy sequence of the nodes of a graph starting a node n. Optionally,
provide a set of visited notes (v) and a collection of nodes to
visit (ns).</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L68" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/post-ordered-nodes">post-ordered-nodes</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (post-ordered-nodes g)
</pre>
<pre id="var-docstr">Return a sequence of indexes of a post-ordered walk of the graph.</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L110" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/recursive-component?">recursive-component?</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (recursive-component? g ns)
</pre>
<pre id="var-docstr">Is the component (recieved from scc) self recursive?</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L151" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/remove-loops">remove-loops</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (remove-loops g)
</pre>
<pre id="var-docstr">For each node n, remove any edges n->n.</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L57" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/reverse-graph">reverse-graph</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (reverse-graph g)
</pre>
<pre id="var-docstr">Given a directed graph, return another directed graph with the
order of the edges reversed.</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L37" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/scc">scc</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (scc g)
</pre>
<pre id="var-docstr">Returns, as a sequence of sets, the strongly connected components
of g.</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L117" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/self-recursive-sets">self-recursive-sets</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (self-recursive-sets g)
</pre>
<pre id="var-docstr">Returns, as a sequence of sets, the components of a graph that are
self-recursive.</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L158" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/stratification-list">stratification-list</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (stratification-list g1 g2)
</pre>
<pre id="var-docstr">Similar to dependency-list (see doc), except two graphs are
provided. The first is as dependency-list. The second (which may
have cycles) provides a partial-dependency relation. If node a
depends on node b (meaning an edge a->b exists) in the second
graph, node a must be equal or later in the sequence.</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L207" id="var-source">Source</a>
</div><div id="var-entry">
<hr />
<h2 id="graph/transitive-closure">transitive-closure</h2>
<span id="var-type">function</span><br />
<pre id="var-usage">Usage: (transitive-closure g)
</pre>
<pre id="var-docstr">Returns the transitive closure of a graph. The neighbors are lazily computed.
Note: some version of this algorithm return all edges a->a
regardless of whether such loops exist in the original graph. This
version does not. Loops will be included only if produced by
cycles in the graph. If you have code that depends on such
behavior, call (-> g transitive-closure add-loops)</pre>
<a href="http://github.com/richhickey/clojure-contrib/blob/db7ac3aa9a5de29ac9c0107a21a790f90104ad3f/src/clojure/contrib/graph.clj#L81" id="var-source">Source</a>
</div>
</div></div>
</div>
</div>
</div>
</div>
</div>
<div id="foot">
<div style="text-align: center;">
Copyright 2008-2009 Rich Hickey and the various contributors
</div>
</div>
</div>
<!-- /rightcolumn -->
<div id="DesignedBy">Logo & site design by <a title="Visit Tom Hickey's website." href="http://www.tomhickey.com">Tom Hickey</a>.</div>
</div>
<!-- /AllContentContainer -->
</body>
</html>
|
