source: orange/Orange/network/network.py @ 9671:a7b056375472

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

Moved orange to Orange (part 2)

Line 
1"""
2.. index:: network
3
4*********
5BaseGraph
6*********
7
8BaseGraph is primarily used to work with additional data attached to the
9NetworkX graph. Two types of data can be added to the graph:
10
11* items (:obj:`Orange.data.Table`) - a table containing data about graph nodes. Each row in the table should correspond to a node with ID set to the row index.
12* links (:obj:`Orange.data.Table`) - a table containing data about graph edges. Each row in the table corresponds to an edge. Two columns titled "u" and "v" must be given in the table, each containing indices of nodes on the given edge.
13   
14Some other methods, common to all graph types are also added to BaseGraph class.
15   
16.. autoclass:: Orange.network.BaseGraph
17   :members:
18
19***********
20Graph types
21***********
22
23The reference in this section is complemented with the original NetworkX
24library reference. For a complete documentation please refer to the
25`NetworkX docs <http://networkx.lanl.gov/reference/>`_. All methods from the
26NetworkX package can be used for graph analysis and manipulation with exception
27to read and write graph methods. For reading and writing graphs please refer to
28the Orange.network.readwrite docs.
29
30Graph
31=====
32
33.. autoclass:: Orange.network.Graph
34   :members:
35
36DiGraph
37=======
38   
39.. autoclass:: Orange.network.DiGraph
40   :members:
41
42MultiGraph
43==========
44   
45.. autoclass:: Orange.network.MultiGraph
46   :members:
47   
48MultiDiGraph
49============
50   
51.. autoclass:: Orange.network.MultiDiGraph
52   :members:
53   
54"""
55
56import copy
57import math
58import numpy
59import networkx as nx
60import Orange
61import orangeom
62import readwrite
63from networkx import algorithms
64from networkx.classes import function
65
66class MdsTypeClass():
67    def __init__(self):
68        self.componentMDS = 0
69        self.exactSimulation = 1
70        self.MDS = 2
71
72MdsType = MdsTypeClass()
73
74def _get_doc(doc):
75    tmp = doc.replace('nx.', 'Orange.network.')
76    return tmp
77
78class BaseGraph():
79    """A collection of methods inherited by all graph types (:obj:`Graph`,
80    :obj:`DiGraph`, :obj:`MultiGraph` and :obj:`MultiDiGraph`).
81   
82    """
83
84    def __init__(self):
85        self._items = None
86        self._links = None
87
88    def items(self):
89        """Return the :obj:`Orange.data.Table` items with data about network
90        nodes.
91       
92        """
93
94        if self._items is not None and \
95                        len(self._items) != self.number_of_nodes():
96            print "Warning: items length does not match the number of nodes."
97
98        return self._items
99
100    def set_items(self, items=None):
101        """Set the :obj:`Orange.data.Table` items to the given data. Notice
102        that the number of instances must match the number of nodes.
103       
104        """
105
106        if items is not None:
107            if not isinstance(items, Orange.data.Table):
108                raise TypeError('items must be of type \'Orange.data.Table\'')
109            if len(items) != self.number_of_nodes():
110                print "Warning: items length must match the number of nodes."
111
112        self._items = items
113
114    def links(self):
115        """Return the :obj:`Orange.data.Table` links with data about network
116        edges.
117       
118        """
119
120        if self._links is not None \
121                    and len(self._links) != self.number_of_edges():
122            print "Warning: links length does not match the number of edges."
123
124        return self._links
125
126    def set_links(self, links=None):
127        """Set the :obj:`Orange.data.Table` links to the given data. Notice
128        that the number of instances must match the number of edges.
129       
130        """
131
132        if links is not None:
133            if not isinstance(links, Orange.data.Table):
134                raise TypeError('links must be of type \'Orange.data.Table\'')
135            if len(links) != self.number_of_edges():
136                print "Warning: links length must match the number of edges."
137
138        self._links = links
139
140    def to_orange_network(self):
141        """Convert the current network to >>Orange<< NetworkX standard. To use
142        :obj:`Orange.network` in Orange widgets, set node IDs to be range
143        [0, no_of_nodes - 1].
144       
145        """
146
147        G = self.__class__()
148        node_list = sorted(self.nodes())
149        node_to_index = dict(zip(node_list, range(self.number_of_nodes())))
150        index_to_node = dict(zip(range(self.number_of_nodes()), node_list))
151
152        G.add_nodes_from(zip(range(self.number_of_nodes()), [copy.deepcopy(self.node[nid]) for nid in node_list]))
153        G.add_edges_from(((node_to_index[u], node_to_index[v], copy.deepcopy(self.edge[u][v])) for u, v in self.edges()))
154
155        for id in G.node.keys():
156            G.node[id]['old_id'] = index_to_node[id]
157
158        if self.items():
159            G.set_items(self.items())
160
161        if self.links():
162            G.set_links(self.links())
163
164        return G
165
166    ### TODO: OVERRIDE METHODS THAT CHANGE GRAPH STRUCTURE, add warning prints
167
168    def items_vars(self):
169        """Return a list of features in the :obj:`Orange.data.Table` items."""
170
171        vars = []
172        if (self._items is not None):
173            if isinstance(self._items, Orange.data.Table):
174                vars = list(self._items.domain.variables)
175
176                metas = self._items.domain.getmetas(0)
177                vars.extend(var for i, var in metas.iteritems())
178        return vars
179
180    def links_vars(self):
181        """Return a list of features in the :obj:`Orange.data.Table` links."""
182
183        vars = []
184        if (self._links is not None):
185            if isinstance(self._links, Orange.data.Table):
186                vars = list(self._links.domain.variables)
187
188                metas = self._links.domain.getmetas(0)
189                vars.extend(var for i, var in metas.iteritems())
190        return [x for x in vars if str(x.name) != 'u' and str(x.name) != 'v']
191
192class Graph(BaseGraph, nx.Graph):
193    """Bases: `NetworkX.Graph <http://networkx.lanl.gov/reference/classes.graph.html>`_,
194    :obj:`Orange.network.BaseGraph`
195   
196    """
197
198    def __init__(self, data=None, name='', **attr):
199        nx.Graph.__init__(self, data, name=name, **attr)
200        BaseGraph.__init__(self)
201
202    def subgraph(self, nbunch):
203        G = nx.Graph.subgraph(self, nbunch)
204        items = self.items().get_items(G.nodes())
205        G = G.to_orange_network()
206        G.set_items(items)
207        return G
208        # TODO: _links
209
210    __doc__ += _get_doc(nx.Graph.__doc__)
211    __init__.__doc__ = _get_doc(nx.Graph.__init__.__doc__)
212
213class DiGraph(BaseGraph, nx.DiGraph):
214    """Bases: `NetworkX.DiGraph <http://networkx.lanl.gov/reference/classes.digraph.html>`_,
215    :obj:`Orange.network.BaseGraph`
216   
217    """
218
219
220    def __init__(self, data=None, name='', **attr):
221        nx.DiGraph.__init__(self, data, name=name, **attr)
222        BaseGraph.__init__(self)
223
224    __doc__ += _get_doc(nx.DiGraph.__doc__)
225    __init__.__doc__ = _get_doc(nx.DiGraph.__init__.__doc__)
226
227class MultiGraph(BaseGraph, nx.MultiGraph):
228    """Bases: `NetworkX.MultiGraph <http://networkx.lanl.gov/reference/classes.multigraph.html>`_,
229    :obj:`Orange.network.BaseGraph`
230   
231    """
232
233
234    def __init__(self, data=None, name='', **attr):
235        nx.MultiGraph.__init__(self, data, name=name, **attr)
236        BaseGraph.__init__(self)
237
238    __doc__ += _get_doc(nx.MultiGraph.__doc__)
239    __init__.__doc__ = _get_doc(nx.MultiGraph.__init__.__doc__)
240
241class MultiDiGraph(BaseGraph, nx.MultiDiGraph):
242    """Bases: `NetworkX.MultiDiGraph <http://networkx.lanl.gov/reference/classes.multidigraph.html>`_,
243    :obj:`Orange.network.BaseGraph`
244   
245    """
246
247
248    def __init__(self, data=None, name='', **attr):
249        nx.MultiDiGraph.__init__(self, data, name=name, **attr)
250        BaseGraph.__init__(self)
251
252    __doc__ += _get_doc(nx.MultiDiGraph.__doc__)
253    __init__.__doc__ = _get_doc(nx.MultiDiGraph.__init__.__doc__)
254
255class GraphLayout(orangeom.GraphLayout):
256    """A class for graph layout optimization. Before using any of the layout
257    optimization technique, the class have to be initialized with the :obj:`set_graph`
258    method. Also, do not forget to call :obj:`set_graph` again if the graph
259    structure changes.
260   
261    .. attribute:: coors
262   
263        Coordinates of all vertices. They are initialized to random positions.
264        You can modify them manually or use one of the optimization algorithms.
265        Usage: coors[0][i], coors[1][i]; 0 for x-axis, 1 for y-axis
266       
267   
268    .. automethod:: Orange.network.GraphLayout.set_graph
269   
270    **Network optimization**
271   
272    .. automethod:: Orange.network.GraphLayout.random
273   
274    .. automethod:: Orange.network.GraphLayout.fr
275   
276    .. automethod:: Orange.network.GraphLayout.fr_radial
277   
278    .. automethod:: Orange.network.GraphLayout.circular_original
279   
280    .. automethod:: Orange.network.GraphLayout.circular_random
281   
282    .. automethod:: Orange.network.GraphLayout.circular_crossing_reduction
283   
284    **FragViz**
285   
286    .. automethod:: Orange.network.GraphLayout.mds_components
287   
288    .. automethod:: Orange.network.GraphLayout.rotate_components
289   
290    **Helper methods**
291   
292    .. automethod:: Orange.network.GraphLayout.get_vertices_in_rect
293   
294    .. automethod:: Orange.network.GraphLayout.closest_vertex
295   
296    .. automethod:: Orange.network.GraphLayout.vertex_distances
297   
298    .. automethod:: Orange.network.GraphLayout.rotate_vertices
299   
300    **Examples**
301   
302    *Network constructor and random layout*
303   
304    In our first example we create a Network object with a simple full graph (K5).
305    Vertices are initially placed randomly. Graph is visualized using pylabs
306    matplotlib.
307       
308    :download:`network-constructor-nx.py <code/network-constructor-nx.py>`
309   
310    .. literalinclude:: code/network-constructor-nx.py
311   
312    Executing the above saves a pylab window with the following graph drawing:
313   
314    .. image:: files/network-K5-random.png
315   
316    *Network layout optimization*
317   
318    This example demonstrates how to optimize network layout using one of the
319    included algorithms.
320   
321    part of :download:`network-optimization-nx.py <code/network-optimization-nx.py>`
322   
323    .. literalinclude:: code/network-optimization-nx.py
324        :lines: 14-19
325       
326    The result of the above script is a spring force layout optimization:
327   
328    .. image:: files/network-K5-fr.png
329   
330    """
331
332    def __init__(self):
333        self.graph = None
334        self.items_matrix = None
335
336    def set_graph(self, graph=None, positions=None):
337        """Init graph structure.
338       
339        :param graph: Orange network
340        :type graph: Orange.netowork.Graph
341       
342        :param positions: Initial node positions
343        :type positions: A list of positions (x, y)
344       
345        """
346        self.graph = graph
347
348        if positions is not None and len(positions) == graph.number_of_nodes():
349            orangeom.GraphLayout.set_graph(self, graph, positions)
350        else:
351            orangeom.GraphLayout.set_graph(self, graph)
352
353    def random(self):
354        """Random graph layout."""
355
356        orangeom.GraphLayout.random(self)
357
358    def fr(self, steps, temperature, coolFactor=0, weighted=False):
359        """Fruchterman-Reingold spring layout optimization. Set number of
360        iterations with argument steps, start temperature with temperature
361        (for example: 1000).
362       
363        """
364
365        return orangeom.GraphLayout.fr(self, steps, temperature, coolFactor, weighted)
366
367    def fr_radial(self, center, steps, temperature):
368        """Radial Fruchterman-Reingold spring layout optimization. Set center
369        node with attribute center, number of iterations with argument steps
370        and start temperature with temperature (for example: 1000).
371       
372        """
373
374        return orangeom.GraphLayout.fr_radial(self, center, steps, temperature)
375
376    def circular_original(self):
377        """Circular graph layout with original node order."""
378
379        orangeom.GraphLayout.circular_original(self)
380
381    def circular_random(self):
382        """Circular graph layout with random node order."""
383
384        orangeom.GraphLayout.circular_random(self)
385
386    def circular_crossing_reduction(self):
387        """Circular graph layout with edge crossing reduction (Michael Baur,
388        Ulrik Brandes).
389       
390        """
391
392        orangeom.GraphLayout.circular_crossing_reduction(self)
393
394    def get_vertices_in_rect(self, x1, y1, x2, y2):
395        """Return a list of nodes in the given rectangle."""
396
397        return orangeom.GraphLayout.get_vertices_in_rect(self, x1, y1, x2, y2)
398
399    def closest_vertex(self, x, y):
400        """Return the closest node to given point."""
401
402        return orangeom.GraphLayout.closest_vertex(self, x, y)
403
404    def vertex_distances(self, x, y):
405        """Return distances (a list of (distance, vertex) tuples) of all nodes
406        to the given position.
407       
408        """
409
410        return orangeom.GraphLayout.vertex_distances(self, x, y)
411
412    def rotate_vertices(self, components, phi):
413        """Rotate network components for a given angle.
414       
415        :param components: list of network components
416        :type components: list of lists of vertex indices
417       
418        :param phi: list of component rotation angles (unit: radians)
419        :type phi: float
420       
421        """
422        #print phi
423        for i in range(len(components)):
424            if phi[i] == 0:
425                continue
426
427            component = components[i]
428
429            x = self.coors[0][component]
430            y = self.coors[1][component]
431
432            x_center = x.mean()
433            y_center = y.mean()
434
435            x = x - x_center
436            y = y - y_center
437
438            r = numpy.sqrt(x ** 2 + y ** 2)
439            fi = numpy.arctan2(y, x)
440
441            fi += phi[i]
442            #fi += factor * M[i] * numpy.pi / 180
443
444            x = r * numpy.cos(fi)
445            y = r * numpy.sin(fi)
446
447            self.coors[0][component] = x + x_center
448            self.coors[1][component] = y + y_center
449
450    def rotate_components(self, maxSteps=100, minMoment=0.000000001,
451                          callbackProgress=None, callbackUpdateCanvas=None):
452        """Rotate the network components using a spring model."""
453
454        if self.items_matrix == None:
455            return 1
456
457        if self.graph == None:
458            return 1
459
460        if self.items_matrix.dim != self.graph.number_of_nodes():
461            return 1
462
463        self.stopRotate = 0
464
465        # rotate only components with more than one vertex
466        components = [component for component \
467            in Orange.network.nx.algorithms.components.connected_components(self.graph) \
468            if len(component) > 1]
469        vertices = set(range(self.graph.number_of_nodes()))
470        step = 0
471        M = [1]
472        temperature = [[30.0, 1] for i in range(len(components))]
473        dirChange = [0] * len(components)
474        while step < maxSteps and (max(M) > minMoment or \
475                                min(M) < -minMoment) and not self.stopRotate:
476            M = [0] * len(components)
477
478            for i in range(len(components)):
479                component = components[i]
480
481                outer_vertices = vertices - set(component)
482
483                x = self.coors[0][component]
484                y = self.coors[1][component]
485
486                x_center = x.mean()
487                y_center = y.mean()
488
489                for j in range(len(component)):
490                    u = component[j]
491
492                    for v in outer_vertices:
493                        d = self.items_matrix[u, v]
494                        u_x = self.coors[0][u]
495                        u_y = self.coors[1][u]
496                        v_x = self.coors[0][v]
497                        v_y = self.coors[1][v]
498                        L = [(u_x - v_x), (u_y - v_y)]
499                        R = [(u_x - x_center), (u_y - y_center)]
500                        e = math.sqrt((v_x - x_center) ** 2 + \
501                                      (v_y - y_center) ** 2)
502
503                        M[i] += (1 - d) / (e ** 2) * numpy.cross(R, L)
504
505            tmpM = numpy.array(M)
506            #print numpy.min(tmpM), numpy.max(tmpM),numpy.average(tmpM),numpy.min(numpy.abs(tmpM))
507
508            phi = [0] * len(components)
509            #print "rotating", temperature, M
510            for i in range(len(M)):
511                if M[i] > 0:
512                    if temperature[i][1] < 0:
513                        temperature[i][0] = temperature[i][0] * 5 / 10
514                        temperature[i][1] = 1
515                        dirChange[i] += 1
516
517                    phi[i] = temperature[i][0] * numpy.pi / 180
518                elif M[i] < 0:
519                    if temperature[i][1] > 0:
520                        temperature[i][0] = temperature[i][0] * 5 / 10
521                        temperature[i][1] = -1
522                        dirChange[i] += 1
523
524                    phi[i] = -temperature[i][0] * numpy.pi / 180
525
526            # stop rotating when phi is to small to notice the rotation
527            if max(phi) < numpy.pi / 1800:
528                #print "breaking"
529                break
530
531            self.rotate_vertices(components, phi)
532            if callbackUpdateCanvas: callbackUpdateCanvas()
533            if callbackProgress : callbackProgress(min([dirChange[i] for i \
534                                    in range(len(dirChange)) if M[i] != 0]), 9)
535            step += 1
536
537    def mds_update_data(self, components, mds, callbackUpdateCanvas):
538        """Translate and rotate the network components to computed positions."""
539
540        component_props = []
541        x_mds = []
542        y_mds = []
543        phi = [None] * len(components)
544        self.diag_coors = math.sqrt((\
545                    min(self.coors[0]) - max(self.coors[0])) ** 2 + \
546                    (min(self.coors[1]) - max(self.coors[1])) ** 2)
547
548        if self.mdsType == MdsType.MDS:
549            x = [mds.points[u][0] for u in range(self.graph.number_of_nodes())]
550            y = [mds.points[u][1] for u in range(self.graph.number_of_nodes())]
551            self.coors[0][range(self.graph.number_of_nodes())] = x
552            self.coors[1][range(self.graph.number_of_nodes())] = y
553            if callbackUpdateCanvas:
554                callbackUpdateCanvas()
555            return
556
557        for i in range(len(components)):
558            component = components[i]
559
560            if len(mds.points) == len(components):  # if average linkage before
561                x_avg_mds = mds.points[i][0]
562                y_avg_mds = mds.points[i][1]
563            else:                                   # if not average linkage before
564                x = [mds.points[u][0] for u in component]
565                y = [mds.points[u][1] for u in component]
566
567                x_avg_mds = sum(x) / len(x)
568                y_avg_mds = sum(y) / len(y)
569                # compute rotation angle
570                c = [numpy.linalg.norm(numpy.cross(mds.points[u], \
571                            [self.coors[0][u], self.coors[1][u]])) \
572                            for u in component]
573                n = [numpy.vdot([self.coors[0][u], \
574                                 self.coors[1][u]], \
575                                 [self.coors[0][u], \
576                                  self.coors[1][u]]) for u in component]
577                phi[i] = sum(c) / sum(n)
578                #print phi
579
580            x = self.coors[0][component]
581            y = self.coors[1][component]
582
583            x_avg_graph = sum(x) / len(x)
584            y_avg_graph = sum(y) / len(y)
585
586            x_mds.append(x_avg_mds)
587            y_mds.append(y_avg_mds)
588
589            component_props.append((x_avg_graph, y_avg_graph, \
590                                    x_avg_mds, y_avg_mds, phi))
591
592        w = max(self.coors[0]) - min(self.coors[0])
593        h = max(self.coors[1]) - min(self.coors[1])
594        d = math.sqrt(w ** 2 + h ** 2)
595        #d = math.sqrt(w*h)
596        e = [math.sqrt((self.coors[0][u] - self.coors[0][v]) ** 2 +
597                  (self.coors[1][u] - self.coors[1][v]) ** 2) for
598                  (u, v) in self.graph.edges()]
599
600        if self.scalingRatio == 0:
601            pass
602        elif self.scalingRatio == 1:
603            self.mdsScaleRatio = d
604        elif self.scalingRatio == 2:
605            self.mdsScaleRatio = d / sum(e) * float(len(e))
606        elif self.scalingRatio == 3:
607            self.mdsScaleRatio = 1 / sum(e) * float(len(e))
608        elif self.scalingRatio == 4:
609            self.mdsScaleRatio = w * h
610        elif self.scalingRatio == 5:
611            self.mdsScaleRatio = math.sqrt(w * h)
612        elif self.scalingRatio == 6:
613            self.mdsScaleRatio = 1
614        elif self.scalingRatio == 7:
615            e_fr = 0
616            e_count = 0
617            for i in range(self.graph.number_of_nodes()):
618                for j in range(i + 1, self.graph.number_of_nodes()):
619                    x1 = self.coors[0][i]
620                    y1 = self.coors[1][i]
621                    x2 = self.coors[0][j]
622                    y2 = self.coors[1][j]
623                    e_fr += math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
624                    e_count += 1
625            self.mdsScaleRatio = e_fr / e_count
626        elif self.scalingRatio == 8:
627            e_fr = 0
628            e_count = 0
629            for i in range(len(components)):
630                for j in range(i + 1, len(components)):
631                    x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, \
632                    y_avg_mds_i, phi_i = component_props[i]
633                    x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, \
634                    y_avg_mds_j, phi_j = component_props[j]
635                    e_fr += math.sqrt((x_avg_graph_i - x_avg_graph_j) ** 2 + \
636                                      (y_avg_graph_i - y_avg_graph_j) ** 2)
637                    e_count += 1
638            self.mdsScaleRatio = e_fr / e_count
639        elif self.scalingRatio == 9:
640            e_fr = 0
641            e_count = 0
642            for i in range(len(components)):
643                component = components[i]
644                x = self.coors[0][component]
645                y = self.coors[1][component]
646                for i in range(len(x)):
647                    for j in range(i + 1, len(y)):
648                        x1 = x[i]
649                        y1 = y[i]
650                        x2 = x[j]
651                        y2 = y[j]
652                        e_fr += math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
653                        e_count += 1
654            self.mdsScaleRatio = e_fr / e_count
655
656        diag_mds = math.sqrt((max(x_mds) - min(x_mds)) ** 2 + (max(y_mds) - \
657                                                              min(y_mds)) ** 2)
658        e = [math.sqrt((self.coors[0][u] - self.coors[0][v]) ** 2 +
659                  (self.coors[1][u] - self.coors[1][v]) ** 2) for
660                  (u, v) in self.graph.edges()]
661        e = sum(e) / float(len(e))
662
663        x = [mds.points[u][0] for u in range(len(mds.points))]
664        y = [mds.points[u][1] for u in range(len(mds.points))]
665        w = max(x) - min(x)
666        h = max(y) - min(y)
667        d = math.sqrt(w ** 2 + h ** 2)
668
669        if len(x) == 1:
670            r = 1
671        else:
672            if self.scalingRatio == 0:
673                r = self.mdsScaleRatio / d * e
674            elif self.scalingRatio == 1:
675                r = self.mdsScaleRatio / d
676            elif self.scalingRatio == 2:
677                r = self.mdsScaleRatio / d * e
678            elif self.scalingRatio == 3:
679                r = self.mdsScaleRatio * e
680            elif self.scalingRatio == 4:
681                r = self.mdsScaleRatio / (w * h)
682            elif self.scalingRatio == 5:
683                r = self.mdsScaleRatio / math.sqrt(w * h)
684            elif self.scalingRatio == 6:
685                r = 1 / math.sqrt(self.graph.number_of_nodes())
686            elif self.scalingRatio == 7:
687                e_mds = 0
688                e_count = 0
689                for i in range(len(mds.points)):
690                    for j in range(i):
691                        x1 = mds.points[i][0]
692                        y1 = mds.points[i][1]
693                        x2 = mds.points[j][0]
694                        y2 = mds.points[j][1]
695                        e_mds += math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
696                        e_count += 1
697                r = self.mdsScaleRatio / e_mds * e_count
698            elif self.scalingRatio == 8:
699                e_mds = 0
700                e_count = 0
701                for i in range(len(components)):
702                    for j in range(i + 1, len(components)):
703                        x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, \
704                        y_avg_mds_i, phi_i = component_props[i]
705                        x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, \
706                        y_avg_mds_j, phi_j = component_props[j]
707                        e_mds += math.sqrt((x_avg_mds_i - x_avg_mds_j) ** 2 + \
708                                           (y_avg_mds_i - y_avg_mds_j) ** 2)
709                        e_count += 1
710                r = self.mdsScaleRatio / e_mds * e_count
711            elif self.scalingRatio == 9:
712                e_mds = 0
713                e_count = 0
714                for i in range(len(mds.points)):
715                    for j in range(i):
716                        x1 = mds.points[i][0]
717                        y1 = mds.points[i][1]
718                        x2 = mds.points[j][0]
719                        y2 = mds.points[j][1]
720                        e_mds += math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
721                        e_count += 1
722                r = self.mdsScaleRatio / e_mds * e_count
723
724            #r = self.mdsScaleRatio / d
725            #print "d", d, "r", r
726            #r = self.mdsScaleRatio / math.sqrt(self.graph.number_of_nodes())
727
728        for i in range(len(components)):
729            component = components[i]
730            x_avg_graph, y_avg_graph, x_avg_mds, \
731            y_avg_mds, phi = component_props[i]
732
733#            if phi[i]:  # rotate vertices
734#                #print "rotate", i, phi[i]
735#                r = numpy.array([[numpy.cos(phi[i]), -numpy.sin(phi[i])], [numpy.sin(phi[i]), numpy.cos(phi[i])]])  #rotation matrix
736#                c = [x_avg_graph, y_avg_graph]  # center of mass in FR coordinate system
737#                v = [numpy.dot(numpy.array([self.coors[0][u], self.coors[1][u]]) - c, r) + c for u in component]
738#                self.coors[0][component] = [u[0] for u in v]
739#                self.coors[1][component] = [u[1] for u in v]
740
741            # translate vertices
742            if not self.rotationOnly:
743                self.coors[0][component] = \
744                (self.coors[0][component] - x_avg_graph) / r + x_avg_mds
745                self.coors[1][component] = \
746                (self.coors[1][component] - y_avg_graph) / r + y_avg_mds
747
748        if callbackUpdateCanvas:
749            callbackUpdateCanvas()
750
751    def mds_callback(self, a, b=None):
752        """Refresh the UI when running  MDS on network components."""
753
754        if not self.mdsStep % self.mdsRefresh:
755            self.mds_update_data(self.mdsComponentList,
756                               self.mds,
757                               self.callbackUpdateCanvas)
758
759            if self.mdsType == MdsType.exactSimulation:
760                self.mds.points = [[self.coors[0][i], \
761                                    self.coors[1][i]] \
762                                    for i in range(len(self.coors))]
763                self.mds.freshD = 0
764
765            if self.callbackProgress != None:
766                self.callbackProgress(self.mds.avg_stress, self.mdsStep)
767
768        self.mdsStep += 1
769
770        if self.stopMDS:
771            return 0
772        else:
773            return 1
774
775    def mds_components(self, mdsSteps, mdsRefresh, callbackProgress=None, \
776                       callbackUpdateCanvas=None, torgerson=0, \
777                       minStressDelta=0, avgLinkage=False, rotationOnly=False, \
778                       mdsType=MdsType.componentMDS, scalingRatio=0, \
779                       mdsFromCurrentPos=0):
780        """Position the network components according to similarities among
781        them.
782
783        """
784
785        if self.items_matrix == None:
786            self.information('Set distance matrix to input signal')
787            return 1
788
789        if self.graph == None:
790            return 1
791
792        if self.items_matrix.dim != self.graph.number_of_nodes():
793            return 1
794
795        self.mdsComponentList = Orange.network.nx.algorithms.components.connected_components(self.graph)
796        self.mdsRefresh = mdsRefresh
797        self.mdsStep = 0
798        self.stopMDS = 0
799        self.items_matrix.matrixType = Orange.core.SymMatrix.Symmetric
800        self.diag_coors = math.sqrt((min(self.coors[0]) - \
801                                     max(self.coors[0])) ** 2 + \
802                                     (min(self.coors[1]) - \
803                                      max(self.coors[1])) ** 2)
804        self.rotationOnly = rotationOnly
805        self.mdsType = mdsType
806        self.scalingRatio = scalingRatio
807
808        w = max(self.coors[0]) - min(self.coors[0])
809        h = max(self.coors[1]) - min(self.coors[1])
810        d = math.sqrt(w ** 2 + h ** 2)
811        #d = math.sqrt(w*h)
812        e = [math.sqrt((self.coors[0][u] - self.coors[0][v]) ** 2 +
813                  (self.coors[1][u] - self.coors[1][v]) ** 2) for
814                  (u, v) in self.graph.edges()]
815        self.mdsScaleRatio = d / sum(e) * float(len(e))
816        #print d / sum(e) * float(len(e))
817
818        if avgLinkage:
819            matrix = self.items_matrix.avgLinkage(self.mdsComponentList)
820        else:
821            matrix = self.items_matrix
822
823        #if self.mds == None:
824        self.mds = Orange.projection.mds.MDS(matrix)
825
826        if mdsFromCurrentPos:
827            if avgLinkage:
828                for u, c in enumerate(self.mdsComponentList):
829                    x = sum(self.coors[0][c]) / len(c)
830                    y = sum(self.coors[1][c]) / len(c)
831                    self.mds.points[u][0] = x
832                    self.mds.points[u][1] = y
833            else:
834                for u in range(self.graph.number_of_nodes()):
835                    self.mds.points[u][0] = self.coors[0][u]
836                    self.mds.points[u][1] = self.coors[1][u]
837
838        # set min stress difference between 0.01 and 0.00001
839        self.minStressDelta = minStressDelta
840        self.callbackUpdateCanvas = callbackUpdateCanvas
841        self.callbackProgress = callbackProgress
842
843        if torgerson:
844            self.mds.Torgerson()
845
846        self.mds.optimize(mdsSteps, Orange.projection.mds.SgnRelStress, self.minStressDelta, \
847                          progress_callback=self.mds_callback)
848        self.mds_update_data(self.mdsComponentList, self.mds, callbackUpdateCanvas)
849
850        if callbackProgress != None:
851            callbackProgress(self.mds.avg_stress, self.mdsStep)
852
853        del self.rotationOnly
854        del self.diag_coors
855        del self.mdsRefresh
856        del self.mdsStep
857        #del self.mds
858        del self.mdsComponentList
859        del self.minStressDelta
860        del self.callbackUpdateCanvas
861        del self.callbackProgress
862        del self.mdsType
863        del self.mdsScaleRatio
864        del self.scalingRatio
865        return 0
866
867    def mds_components_avg_linkage(self, mdsSteps, mdsRefresh, \
868                                   callbackProgress=None, \
869                                   callbackUpdateCanvas=None, torgerson=0, \
870                                   minStressDelta=0, scalingRatio=0, \
871                                   mdsFromCurrentPos=0):
872        return self.mds_components(mdsSteps, mdsRefresh, callbackProgress, \
873                                   callbackUpdateCanvas, torgerson, \
874                                   minStressDelta, True, \
875                                   scalingRatio=scalingRatio, \
876                                   mdsFromCurrentPos=mdsFromCurrentPos)
877
878    ##########################################################################
879    ### BEGIN: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0)                ###
880    ##########################################################################
881
882    def map_to_graph(self, graph):
883        nodes = sorted(graph.nodes())
884        return dict((v, (self.coors[0][i], self.coors[1][i])) for i, v in \
885                    enumerate(nodes))
886
887
888class NxView(object):
889    """Network View"""
890
891    def __init__(self, **attr):
892        self._network = None
893        self._nx_explorer = None
894
895    def set_nx_explorer(self, _nx_explorer):
896        self._nx_explorer = _nx_explorer
897
898    def init_network(self, graph):
899        return graph
900
901    def node_selection_changed(self):
902        pass
903
904    def update_network(self):
905        if self._nx_explorer is not None and self._network is not None:
906            subnet = self._network
907            self._nx_explorer.change_graph(subnet)
Note: See TracBrowser for help on using the repository browser.