source: orange/Orange/network/network.py @ 10861:5f70ff13ecc2

Revision 10861:5f70ff13ecc2, 32.0 KB checked in by mstajdohar, 2 years ago (diff)

Fixed some bugs on directed graph.

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