# source:orange/Orange/doc/reference/pathfinder.htm@9671:a7b056375472

Revision 9671:a7b056375472, 5.1 KB checked in by anze <anze.staric@…>, 2 years ago (diff)

Moved orange to Orange (part 2)

Line
5
6<index name="graphs">
7<h1>Simplifying networks</h1>
8
9<p>Orange provides an implementation of a procedure called the Pathfinder for simplifying (large) networks.</p>
10<p>Assuming that a weight of an edge represents a distance (interpreted as a dissimilarity measure), the pruning idea of
11the Pathfinder algorithm is based on the triangle inequality, which states that the direct distance between two points must
12be less than or equal to the distance between those two points going through an intermediate point. The triangle inequality can be easily
13extended to all paths: the direct distance between two nodes must be less than or equal to the dist-length (sum of all weights)
14of every path between these two nodes; therefore also less than or equal to the length of the geodesic path (i.e. the shortest path).
15The algorithm eliminates the links which violate the extended triangle inequality and thus simplifying the network and clarifying it for the subsequent analysis.</p>
16
17<p>For further information regarding the implemented procedure (with some experiments) consult the following document <a href="pathfinder.pdf">[Vavpetic 2010]</a>.</p>
18
19<h2>Pathfinder</h2>
20<p><INDEX name="classes/Pathfinder (in orangeom)">
21The Pathfinder class offers a way to simplify a given network with the specified parameters.
22</p>
23
24<p class=section>Methods</p>
25<dl class=attributes>
26<dt>Pathfinder()</dt>
27<dd>Constructs a Pathfinder object.</dd>
28<dt>simplify(r, q, graph)</dt>
29<dd>
30Simplifies the given graph by removing the edges which violate the extended triangle inequality. See the parameter meanings bellow. The speed of the procedure depends heavily on the
31parameter <code>q</code> and the graph's properties (it works best with sparse graphs). The most commonly used values are <code>r = sys.maxint</code> and <code>q = n-1</code>, where <code>n</code> equals the number of nodes
32in the graph.
33<dt>r</dt>
34<dd>
35This parameter affects the way in which the cost of a path is calculated - it is actually the parameter to the Minkowski formula (consult the paper mentioned above for further information).</br>
36For example, if we have two edges with weights a and b, then for <code>r = 1</code> the calculated cost <code>c</code> would be <code>c = a + b</code>,
37for <code>r = 2</code>, <code>c = sqrt(a**2 + b**2)</code> and for <code>r = sys.maxint</code> (which is used to represent infinity) it converges to <code>c = max(a, b)</code>.
38</dd>
39<dt>q</dt>
40<dd>
41This parameter represents the maximum length (i.e. the number of edges) of all alternative paths checked between two nodes when calculating the lowest cost between them.
42</dd>
43</dd>
44<dt>setProgressCallback(fun)</dt>
45<dd>Sets a progress callback function, which is called for every node when it's complete. The function is expected to accept one argument -
46a double value between 0 and 1 is passed to it.</dd>
47</dl>
48
49<h2>Examples</h2>
50
51<h3>Simplifying a small network</h3>
52
53<p>This example shows how to simplify a weighted network using the Pathfinder procedure. As the procedure interprets the weights of a given network as dissimilarities, it only makes sense to apply the procedure to undirected graphs.</p>
54
55<p class="header">Part of <a href="pathfinder.py">pathfinder.py</a> (uses <a href="demo.net">demo.net</a>)</p>
56<xmp class=code>
57import orngNetwork
58from orangeom import Pathfinder
59from pylab import *
60
61...
62
63# Read a demo network from a file
65
66# Compute a layout for plotting
67netOp = orngNetwork.NetworkOptimization(net)
68netOp.fruchtermanReingold(100, 1000)
69
70# Plot the original
71myPlot(net, 'Original network')
72
73# Choose some parameters
74r, q = 1, 6
75
76# Create a pathfinder instance
77pf = Pathfinder()
78
79# Simplify the network
80pf.simplify(r, q, net)
81
82# Plot the simplified network
83myPlot(net, 'Simplified network')
84show()
85</xmp>
86<p>Executing the script above pops-up two pylab windows with the
87following two networks:</p>
88<img src="orig_graph.png">
89<img src="simplified_graph.png">
90
91<h3>Progress callback functionality</h3>
92
93<p>This example shows how to use a progress callback function.</p>
94<p class="header">Part of <a href="pf_progress.py">pf_progress.py</a> (uses <a href="demo.net">demo.net</a>)</p>
95<xmp class=code>
96import orngNetwork
97from orangeom import Pathfinder
98
99def myCb(complete):
100    """
101    The callback function.
102    """
103    print 'The procedure is %d%% complete.' % int(complete * 100)
104
105# Read a demo network from a file
107
108# Choose some parameters
109r, q = 1, 6
110
111# Create a pathfinder instance
112pf = Pathfinder()
113
114# Pass the reference to the desired function
115pf.setProgressCallback(myCb)
116
117# Simplify the network
118pf.simplify(r, q, net)
119</xmp>
120<p>Executing the script above should print something like this:</p>
121<xmp class=code>
122The procedure is 14% complete.
123The procedure is 28% complete.
124The procedure is 42% complete.
125The procedure is 57% complete.
126The procedure is 71% complete.
127The procedure is 85% complete.
128The procedure is 100% complete.
129</xmp>
130</BODY></HTML>
Note: See TracBrowser for help on using the repository browser.