#
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) |
---|

Line | |
---|---|

1 | <html> <HEAD> |

2 | <LINK REL=StyleSheet HREF="../style.css" TYPE="text/css"> |

3 | <LINK REL=StyleSheet HREF="style-print.css" TYPE="text/css" MEDIA=print> |

4 | </HEAD> <body> |

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 |

11 | the Pathfinder algorithm is based on the triangle inequality, which states that the direct distance between two points must |

12 | be less than or equal to the distance between those two points going through an intermediate point. The triangle inequality can be easily |

13 | extended to all paths: the direct distance between two nodes must be less than or equal to the dist-length (sum of all weights) |

14 | of every path between these two nodes; therefore also less than or equal to the length of the geodesic path (i.e. the shortest path). |

15 | The 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)"> |

21 | The 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> |

30 | Simplifies 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 |

31 | parameter <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 |

32 | in the graph. |

33 | <dt>r</dt> |

34 | <dd> |

35 | This 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> |

36 | For 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>, |

37 | for <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> |

41 | This 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 - |

46 | a 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> |

57 | import orngNetwork |

58 | from orangeom import Pathfinder |

59 | from pylab import * |

60 | |

61 | ... |

62 | |

63 | # Read a demo network from a file |

64 | net = orngNetwork.Network.read('demo.net') |

65 | |

66 | # Compute a layout for plotting |

67 | netOp = orngNetwork.NetworkOptimization(net) |

68 | netOp.fruchtermanReingold(100, 1000) |

69 | |

70 | # Plot the original |

71 | myPlot(net, 'Original network') |

72 | |

73 | # Choose some parameters |

74 | r, q = 1, 6 |

75 | |

76 | # Create a pathfinder instance |

77 | pf = Pathfinder() |

78 | |

79 | # Simplify the network |

80 | pf.simplify(r, q, net) |

81 | |

82 | # Plot the simplified network |

83 | myPlot(net, 'Simplified network') |

84 | show() |

85 | </xmp> |

86 | <p>Executing the script above pops-up two pylab windows with the |

87 | following 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> |

96 | import orngNetwork |

97 | from orangeom import Pathfinder |

98 | |

99 | def 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 |

106 | net = orngNetwork.Network.read('demo.net') |

107 | |

108 | # Choose some parameters |

109 | r, q = 1, 6 |

110 | |

111 | # Create a pathfinder instance |

112 | pf = Pathfinder() |

113 | |

114 | # Pass the reference to the desired function |

115 | pf.setProgressCallback(myCb) |

116 | |

117 | # Simplify the network |

118 | pf.simplify(r, q, net) |

119 | </xmp> |

120 | <p>Executing the script above should print something like this:</p> |

121 | <xmp class=code> |

122 | The procedure is 14% complete. |

123 | The procedure is 28% complete. |

124 | The procedure is 42% complete. |

125 | The procedure is 57% complete. |

126 | The procedure is 71% complete. |

127 | The procedure is 85% complete. |

128 | The procedure is 100% complete. |

129 | </xmp> |

130 | </BODY></HTML> |

**Note:**See TracBrowser for help on using the repository browser.