-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathdependencies.html
More file actions
170 lines (162 loc) · 7.81 KB
/
dependencies.html
File metadata and controls
170 lines (162 loc) · 7.81 KB
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
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Sorting dependencies — bits v0.8 documentation</title>
<link rel="stylesheet" href="_static/sphinxdoc.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: '',
VERSION: '0.8',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: true
};
</script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/underscore.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<link rel="top" title="bits v0.8 documentation" href="index.html" />
<link rel="next" title="A naive, CPU hungry solution" href="dependencies/brute.py.html" />
<link rel="prev" title="The yield keyword simplifies Twisted code" href="concurrent/smartpython.html" />
</head>
<body>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="dependencies/brute.py.html" title="A naive, CPU hungry solution"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="concurrent/smartpython.html" title="The yield keyword simplifies Twisted code"
accesskey="P">previous</a> |</li>
<li><a href="index.html">bits v0.8 documentation</a> »</li>
</ul>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<h4>Previous topic</h4>
<p class="topless"><a href="concurrent/smartpython.html"
title="previous chapter">The <em>yield</em> keyword simplifies Twisted code</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="dependencies/brute.py.html"
title="next chapter">A naive, CPU hungry solution</a></p>
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="_sources/dependencies.txt"
rel="nofollow">Show Source</a></li>
</ul>
<div id="searchbox" style="display: none">
<h3>Quick search</h3>
<form class="search" action="search.html" method="get">
<input type="text" name="q" size="18" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
<p class="searchtip" style="font-size: 90%">
Enter search terms or a module, class or function name.
</p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body">
<div class="section" id="sorting-dependencies">
<h1>Sorting dependencies<a class="headerlink" href="#sorting-dependencies" title="Permalink to this headline">¶</a></h1>
<p>This article is on different ways to solve a set of dependencies. That
is, given a set of dependencies between nodes (think of projects or
software packages): a needs b, a needs c, c needs b, we want an
<strong>sorted list of nodes where each nodes occurs *after* its
dependencies</strong>. In this simple example, the sorted list is <em>b, c
a</em>. <em>b</em> is first, because <em>b</em> has no dependencies, <em>c</em> is next because
it only requires <em>b</em> which is already in the list, and <em>a</em> is last
since it needs all the rest.</p>
<div class="toctree-wrapper compound">
</div>
<p>Several algorithms will be presented to build this list:</p>
<ul>
<li><p class="first">A naive method which is simple to read and understand: a function
test if list satisfies the dependencies, and this function is
applied to all possible permutation of the node list. But is
computationaly too hard to be useful: it takes much too long to
solve even simple sets of dependencies:</p>
<p><a class="reference internal" href="dependencies/brute.py.html"><em>A naive, CPU hungry solution</em></a></p>
</li>
<li><p class="first">Finding the sorted list is actually a known problem and the
solutions are called topological sort. A topological sort
implementation returns quickly only one of the possible solution. In
Python, there is one implementation in the package <em>topsort</em>,
derived from a mail in the Python mailing list written by Tim Peters
and also, another version in the <em>python-graph</em> package.</p>
<p><a class="reference internal" href="dependencies/off_the_shelf.html"><em>Topsort in available packages</em></a></p>
<p>All languages have their advantages: for a recursive algorithm
dealing and the manipulation of lists, Erlang is particularly
adapted. Actually, the topsort algorithm is part of Erlang standard
library, as examplified in the previous article.</p>
</li>
<li><p class="first">Yet another way to solve this problem is to consider <em>the graph of
the candidates</em>, that is given the first part of the sorted list of
nodes, consider as the children of the last node of the list: all
the nodes which are not yet in the list and whose dependencies are
in the list. Then, it is just a matter of traversing the graph in
depth first or breadth first to find the list of all possible
solutions.</p>
<p><a class="reference internal" href="dependencies/bfs_dfs.html"><em>Graph traversal</em></a></p>
<p>In depth search first, it is possible to build a generator
(<a class="reference internal" href="dependencies/bfs_dfs.html#recursive-gen"><em>a recursive generator</em></a>) of the solutions: the
solution are not computed in a long batch, accumulated and returned
as a long list, the solutions are available as soon as they are
found. The processing of the solution alternates with the search for
the next solution. For instance, a solution can be handed to a
client which draws the solution, while the server continues the
exhaustion of the solutions.</p>
<p>It is actually possible to do a <a class="reference internal" href="dependencies/bfs_dfs.html#recursive-query"><em>breadth first search traversal
in pure SQL</em></a> using the recent standard <tt class="docutils literal"><span class="pre">with</span>
<span class="pre">recurse</span></tt> queries available in PostgreSQL 8.4. Performance-wise, the
SQL query is one hundred time faster that the traversal in pure
CPython. The SQL query (which find all solutions) is actually on par
with the topological sort (which finds only one).</p>
</li>
</ul>
</div>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="dependencies/brute.py.html" title="A naive, CPU hungry solution"
>next</a> |</li>
<li class="right" >
<a href="concurrent/smartpython.html" title="The yield keyword simplifies Twisted code"
>previous</a> |</li>
<li><a href="index.html">bits v0.8 documentation</a> »</li>
</ul>
</div>
<div class="footer">
© Copyright 2009, Jean Daniel Browne.
Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.0.4.
</div>
</body>
</html>