source: orange/orange/Orange/network/network.py @ 9349:fa13a2c52fcd

Revision 9349:fa13a2c52fcd, 32.9 KB checked in by mitar, 2 years ago (diff)

Changed way of linking to code in documentation.

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   
887class NxView(object):
888    """Network View
889   
890    """
891   
892    def __init__(self, **attr):
893        self._network = None
894        self._nx_explorer = None
895       
896    def set_nx_explorer(self, _nx_explorer):
897        self._nx_explorer = _nx_explorer
898       
899    def init_network(self, graph):
900        return graph
901       
902    def nodes_selected(self):
903        pass
Note: See TracBrowser for help on using the repository browser.