source: orange/orange/Orange/network/__init__.py @ 7772:54ba9ee6d0e7

Revision 7772:54ba9ee6d0e7, 69.9 KB checked in by miha <miha.stajdohar@…>, 3 years ago (diff)

Changed documentation to underscore case functions.

Line 
1"""
2.. index:: network
3
4Network analysis and layout optimization.
5
6*******
7Network
8*******
9
10.. autoclass:: Orange.network.Network
11   :members:
12   
13Examples
14========
15
16Reading and saving a network
17----------------------------
18
19This example demonstrates reading a network. Network class can read or write
20Pajek (.net) or GML file format.
21
22`network-read.py`_ (uses: `K5.net`_):
23
24.. literalinclude:: code/network-read.py
25    :lines: 4-5
26
27Visualize a network in NetExplorer widget
28-----------------------------------------
29
30This example demonstrates how to display a network in NetExplorer.
31
32part of `network-widget.py`_
33
34.. literalinclude:: code/network-widget.py
35    :lines: 10-16
36   
37.. image:: files/network-explorer.png
38    :width: 100%
39   
40***************************
41Network Layout Optimization
42***************************
43
44    .. autoclass:: Orange.network.NetworkOptimization
45       :members:
46       :exclude-members: collapse
47       
48Examples
49========
50
51Network constructor and random layout
52-------------------------------------
53
54In our first example we create a Network object with a simple full graph (K5).
55Vertices are initially placed randomly. Graph is visualized using pylabs
56matplotlib. NetworkOptimization class is not needed because we do not apply any
57layout optimization method in this example.
58
59`network-constructor.py`_
60
61.. literalinclude:: code/network-constructor.py
62
63Executing the above script pops-up a pylab window with the following graph
64drawing:
65
66.. image:: files/network-K5-random.png
67
68Network layout optimization
69---------------------------
70
71This example demonstrates how to optimize network layout using one of included
72algorithms.
73
74part of `network-optimization.py`_
75
76.. literalinclude:: code/network-optimization.py
77    :lines: 12-16
78   
79The following optimization algorithms are supported:
80
81* .random()
82* .fruchterman_reingold(steps, temperature, coolingFactor=Default, hiddenNodes=[], weighted=False)
83* .radial_fruchterman_reingold(center, steps, temperature)
84* .circular_original()
85* .circular_random()
86* .circular_crossing_reduction()
87
88Spring forces layout optimization is the result of the above script:
89
90.. image:: files/network-K5-fr.png
91   
92******
93Graphs
94******
95
96Orange offers a data structure for representing directed and undirected graphs
97with various types of weighted connections.
98
99Basic graphs have only one type of edges. Each edge can have an associated
100number, representing a strength of the edge - with whatever underlying
101physical interpretation. Orange's graphs are more general and two vertices
102can be connected by edges of various types. One use for this would be in
103genetics, where one gene can excite or inhibit another - or both
104simultaneously, which is why we can't simply assign negative numbers to the
105edges. The number of edge types is unlimited, but needs to be set in advance.
106
107Before constructing a graph, you will also need to decide for the underlying
108data structure. The differences for smaller graphs (e.g. with less than 100
109nodes) should be insignificant, while for the larger, the decision should be
110based upon the expected number of edges ("density" of the graph) and the
111operations you plan to execute. Graphs with large number of edges (eg.>n2/4,
112where n is the number of vertices) should be represented with adjacency
113matrices (class :obj:`Orange.network.GraphAsMatrix`), graphs with small number
114of edges with adjacency lists (:obj:`Orange.network.GraphAsList`) and those in
115between with adjacency trees (:obj:`Orange.network.GraphAsTree`). Regarding
116the speed, matrices are generally the fastest, while some operations, such as
117finding all edges leading from certain node, will sometimes be faster with
118lists or trees.
119
120One thing that is not supported (at the moment?) are multiple edges of the
121same type between two vertices.
122
123Construction
124============
125
126When constructing a graph, you will need to decide about the data structure for
127representation of edges, and call the corresponding constructor. All
128constructors take the same arguments: the number of vertices (needs to be given
129in advance, you cannot add additional vertices later), a flag telling whether
130the graph is directed or not, and the number of edge types. The default number
131of edge types is 1 (a normal graph), while the other two arguments are
132mandatory.
133
134You can choose between three constructors, all derived from a single ancestor
135:obj:`Orange.network.Graph`:
136
137.. class:: GraphAsMatrix(nVertices, directed[, nEdgeTypes])
138
139    Bases: :obj:`Orange.network.Graph`
140
141    Edges are stored in a matrix with either n^2 or n(n+1)/2 elements,
142    depending upon whether the graph is directed or not. (In C++, it is stored
143    as float * pointing to an array of length n*n*nEdgeTypes or
144    (n*(n+1))/2*nEdgeTypes elements, where nEdgeTypes is the number of edge
145    types.) This representation is suitable for smaller graphs and for dense
146    large graphs. For graph with only one edge type, this representation is
147    more economical than representation with lists or trees when the number of
148    edges is larger than n2/4. Inserting, deleting and checking the edges is
149    fast; listing the neighbours of a certain node is fast unless the graph is
150    sparse, in which case a graph represented with a list or a tree would be
151    faster.
152   
153.. class:: GraphAsList(nVertices, directed[, nEdgeTypes])
154   
155    Bases: :obj:`Orange.network.Graph`
156   
157    Edges are stored in an ordered lists of neighbours, one list for each node.
158    In C++, for each neighbour, the connection is stored in a structure with
159    the vertex number (int), a pointer to the next structure, and an array of
160    floats, one for each integer. With 16-byte alignment, this would take 16
161    bytes for graphs with one or two edge types on the usual 32-bit platforms.
162    For undirected graphs, each edge is stored only once, in the list of the
163    edge with the smaller index. This makes the structure smaller and insertion
164    and lookup faster; it slows down finding the neighbours of a given node.
165    This structure is convenient for graphs with a very small number of edges.
166    For them, inserting and removing edges is relatively fast; getting all
167    edges leading from a vertex is fast, while getting edges leading to a
168    vertex or getting all neighbours (in directed or undirected graph) is slow.
169   
170.. class:: GraphAsTree(nVertices, directed[, nEdgeTypes])
171   
172    Bases: :obj:`Orange.network.Graph`
173   
174    This structure is similar to GraphAsTree except that the edges are stored
175    in trees instead of lists. This should be a structure of choice for all
176    graph between really sparse and those having one quarter of possible edges.
177    As expected, queries are fast, while insertion and removal of edges is
178    somewhat slower (though still faster than for GraphAsList unless the number
179    of edges is really small). Internally, nodes of the tree contain the vertex
180    number, two pointers and a list of floats. With one edge type, this should
181    be 16 bytes on 32-bit platforms.
182
183Examples
184--------
185
186An ordinary undirected graph with 10 vertices stored in a matrix would thus be
187constructed by::
188
189    >>> graph = Orange.network.GraphAsMatrix(10, 0)
190
191A directed graph with 1000 vertices and edges of three types, stored with
192adjacency trees would be constructed by::
193
194    >>> graph = Orange.network.GraphAsTree(1000, 1, 3)
195
196Usage
197=====
198
199All three graph types are used in the same way, independent of the underlying
200structure. All methods are defined in basic class :obj:`Orange.network.Graph`.
201
202.. class:: Graph
203
204    .. attribute:: nVertices
205   
206        The number of vertices (read-only, set at construction)
207   
208    .. attribute:: nEdgeTypes
209   
210        The number of different edge types (read-only, set at construction)
211   
212    .. attribute:: directed
213   
214        Tells whether the graph is directed (read-only, set at construction)
215   
216    .. attribute:: objects
217   
218        A dictionary, list or other sequence of objects that correspond to
219        graph nodes. The use of this object is described in section on
220        indexing.
221
222    .. attribute:: forceMapping
223
224        Determines whether to map integer indices through 'objects'. Details are
225        described below.
226
227    .. attribute:: returnIndices
228
229        If set, the methods that return list of neighbours will return lists of
230        integers even when objects are given.
231
232    **Indexing**
233   
234    Vertices are referred to by either integer indices or Python objects of any
235    type. In the latter case, a mapping should be provided by assigning the
236    'objects' attribute. For instance, if you set graph.objects to ["Age",
237    "Gender", "Height", "Weight"] then graph["Age", "Height"] would be equivalent
238    to graph[0, 2] and graph.get_neighbours("Weight") to graph.get_neighbours(3).
239    Vertex identifier doesn't need to be a string, it can be any Python
240    object.
241   
242    If objects contains a dictionary, its keys are vertex identifiers and the
243    values in the dictionary should be integers, eg.
244       
245    part of `network-graph.py`_
246
247    .. literalinclude:: code/network-graph.py
248        :lines: 20-23
249 
250    If not a dictionary, objects can be any kind of sequence. Usually, you will
251    give it a list of the same length as the number of vertices in the graph,
252    so each element would identify a vertex. When indexing, the index is sought
253    for in the list. objects can also be a list of attributes, a domain, an
254    example table or even a single string; Orange will run a code equivalent to
255    "for o in graph.objects", so everything for which such a loop works, goes.
256   
257    Searching through the list is, of course, rather slow, so it is recommended
258    to use integer indices for larger graphs. So, if you request
259    graph.get_neighbours(0), the method will return the neighbours of the first
260    vertex, even if objects is given. But - what if you want to map all
261    indices, even integers, through objects? In this case, you need to set
262    graph.forceMapping to 1. If graph.forceMapping is set and graph.objects is
263    given, even get_neighbours(0) will search the graph.objects for 0 and return
264    the neighbours of the corresponding (not necessarily the first) node.
265
266    **Getting and Setting Edges**
267   
268    .. method:: graph[v1, v2]
269   
270        For graphs with a single edge type, graph[v1, v2] returns the weight of
271        the edge between v1 and v2, or None if there is no edge (edge's weight
272        can also be 0).
273       
274        For graphs with multiple edge types, graph[v1, v2] returns a list of
275        weights for various edge types. Some (or all, if there is no edge)
276        elements of the list can be None. If the edge does not exist, graph[v1,
277        v2] returns a list of Nones, not a None.
278       
279        Edges can also be set by assigning them a weight, e.g.graph[2, 5]=1.5.
280        As described above, if objects is a set, we can use other objects, such
281        as names, as v1 and v2 (the same goes for all other functions described
282        below).
283       
284        You can assign a list to graph[v1, v2]; in graph with three edge
285        types you can set graph[2, 5] = [1.5, None, -2.0]. After that, there
286        are two edges between vertices 2 and 5, one of the first type with
287        weight 1.5, and one of the third with weight -2.0. To remove an edge,
288        you can assign it a list of Nones or a single None, e.g. graph[2,
289        5]=None; this removes edges of all types between the two nodes.
290       
291        The list returned for graphs with multiple edge types is actually a
292        reference to the edge, therefore you can set e = graph[v1, v2] and then
293        manipulate e, for instance e[1]=10 or e[0]=None. Edge will behave just
294        as an ordinary list (well, almost - no slicing ets). However, don't try
295        to assign a list to e, eg e=[1, None, 4]. This assigns a list to e, not
296        to the corresponding edge...
297       
298    .. method:: graph[v1, v2, type]
299       
300        This is defined only for graph with multiple edge types; it returns the
301        weight for the edge of type type between v1 and v2, or None if there is
302        no such edge. You can also establish an edge by assigning a weight
303        (e.g. graph[2, 5, 2] = -2.0) or remove it by assigning it a None
304        (graph[2, 5, 2] = None).
305       
306    .. method:: edge_exists(v1, v2[, type])
307       
308        Returns true if the edge between v1 and v2 exists. For multiple edge
309        type graphs you can also specify the type of the edge you check for. If
310        the third argument is omitted, the method returns true if there is any
311        kind of edge between the two vertices. It is recommended to use this
312        method when you want to check for a node. In single edge type graphs,
313        if graph[v1, v2]: will fail when there is an edge but it has a weight
314        of zero. With multiple edge types, if graph[v1, v2]: will always
315        success since graph[v1, v2] returns a non- empty list; if there is no
316        edges, this will be a list of Nones, but Python still treats it as
317        "true".
318       
319    .. method:: add_cluster(list_of_vertices)
320       
321        Creates a cluster - adds edges between all listed vertices.
322   
323    **Queries**
324       
325    Graph provides a set of functions that return nodes connected to a certain
326    node.
327   
328    .. method:: get_neighbours(v1[, type])
329   
330        Returns all the nodes that are connected to v1. In directed graphs,
331        this includes vertices with edges toward or from v1. In graphs with
332        multiple edge types you can also specify the edge type you are
333        interested in: get_neighbours will the return only the vertices that are
334        connected to v1 by edges of that type.
335   
336    .. method:: get_edges_from(v1[, type])
337   
338        Return all the vertices which are connected to v1 by the edges leading
339        from v1. In edges with multiple edge types, you can specify the edge
340        type. In undirected graph, this function is equivalent to
341        get_neighbours.
342   
343    .. method:: get_edges_to(v1[, type])
344   
345        Returns all the vertices with edges leading to v1. Again, you can
346        decide for a single edge type to observe, and, again again, in
347        undirected graphs this function is equivalent to get_neighbours.
348       
349    If objects is set, functions return a list of objects (names of
350    vertices or whatever objects you stored in objects). Otherwise, a list
351    of integer indices is returned. If you want to force Graph to return
352    integer indices even if objects is set, set graph.returnIndices to
353    True.
354   
355    Of the three operations, the expensive one is to look for the vertices with
356    edges pointing to the given edge. There is no problem when graph is
357    represented as a matrix (:obj:`Orange.network.GraphAsMatrix`); these are
358    always fast. On directed graph, get_edges_from is always fast as well.
359   
360    In undirected graphs represented as lists or trees, the edge between
361    vertices with indices v1 and v2 is stored at the list/tree in the
362    smaller of the two indices. Therefore to list all neighbours of v1,
363    edges with v2<v1 are copied form v1's list, while for edges with v2>v1
364    the function needs to look for v1 in each v2's list/tree. Lookup in
365    trees is fast, while in representation with adjacency list, the
366    function is slower for v1 closer to nVertices/2. If v1 is small there
367    is a great number of v2>v1 whose lists are to be checked, but since the
368    lists are ordered, v1 is more to the beginning of these lists (and when
369    a vertex with index higher than v1 is encountered, we know that v1 is
370    not on the list). If v2 is great, there it is more toward the end of
371    the list, but there is smaller number of lists to be checked.
372    Generally, the average number of traversed list elements for
373    get_neighbours/get_edges_from/get_edges_to on undirected graphs with
374    p*nVertices2 edges is p(nVertices-v1)v1.
375   
376    To sum up, if you have a large undirected graph and intend to query for
377    neighbours (or, equivalently, edges to or from a node) a lot, don't use
378    :obj:`Orange.network.GraphAsList`. If the graph is small or you won't use
379    these functions, it doesn't matter.
380   
381    For directed graphs, get_edges_from is trivial. The other two functions are
382    even slower than for undirected graphs, since to find the edges leading
383    from any vertex to a given one, all lists/trees need to be searched. So, if
384    your algorithm will extensively use get_edges_to or get_neighbours and your
385    graph is large but the number of edges is less than nEdges2/2, you should
386    use :obj:`Orange.network.GraphAsTree` or, to be faster but consume more
387    memory store the graph as :obj:`Orange.network.GraphAsMatrix`. If the
388    number of edges is greater, :obj:`Orange.network.GraphAsMatrix` is more
389    economic anyway. This calculation is for graph with only one edge type;
390    see the description of graph types for details.
391   
392    However, this is all programmed in C++, so whatever you do, the bottleneck
393    will probably still be in your Python code and not in C++. You probably
394    cannot miss by using :obj:`Orange.Network.GraphAsTree` disregarding the
395    size of the graph and the operations you perform on it.
396
397    **Graph analysis**
398   
399    .. method:: get_sub_graph(vertices)
400   
401        Return a new graph of type :obj:`Orange.network.Graph` that is a
402        subgraph of the original graph and consists of given vertices.
403   
404    .. method:: get_clustering_coefficient()
405   
406        Return the graph average local clustering coefficient, described in
407        Watts DJ, Strogatz SH: Collective dynamics of 'small-world' networks.
408        Nature 1998, 393(6684):440-442.
409   
410    .. method:: get_connected_components()
411   
412        Return a list of all connected components sorted descending by
413        component size.
414   
415    .. method:: get_degree_distribution()
416   
417        Return degree distribution as dictionary of type
418        {degree:number_of_vertices}.
419   
420    .. method:: get_degrees()
421   
422        Return a list of degrees. List size matches number of vertices. Index
423        of given degree matches index of corresponding vertex.
424   
425    .. method:: get_hubs(n)
426   
427        Return a list of n largest hubs.
428   
429    .. method:: get_shortest_paths(u, v)
430   
431        Return a list of vertices in the shortest path between u and v.
432   
433    .. method:: get_distance(u, v)
434   
435        Return a distance between vertices u and v.
436   
437    .. method:: get_diameter()
438   
439        Return a diameter of the graph.
440       
441Examples
442--------
443
444How to use graphs, part of `network-graph.py`_
445
446.. literalinclude:: code/network-graph.py
447    :lines: 9-56
448
449Results::
450
451    [(1, 0), (2, 0), (2, 1)]
452    0.3
453    0.3
454    0.1
455    0.3
456    ['Gender', 'Height']
457    [1, 2]
458    (None, None, None)
459    12.0
460    (None, 12, None)
461    1
462    0
463    1
464    0
465    0
466    1
467    (None, None, 3)
468    (None, None, None)
469
470How to use graphs with objects on edges, part of `network-graph-obj.py`_
471
472.. literalinclude:: code/network-graph-obj.py
473    :lines: 9-59
474   
475Results::
476
477    [(1, 0), (2, 1)]
478    [1, 2, 3]
479    [1, 2, 3]
480    a string
481    None
482    a string
483    [1, 2, 3]
484    ['Gender']
485    [1]
486    (None, None, None)
487    12.0
488    (None, 12, None)
489    1
490    0
491    1
492    0
493    0
494    1
495    (None, None, 3)
496    (None, None, None)
497
498An example of network analysis, part of `network-graph-analysis.py`_ (uses:
499`combination.net`_):
500
501.. literalinclude:: code/network-graph-analysis.py
502    :lines: 12-49
503   
504Results::
505
506    Connected components
507    [[0, 1, 2, 3, 4, 5, 6, 7, 8], [13, 14, 15, 16, 17, 18], [9, 10, 11, 12]]
508   
509    Degree distribution
510    {1: 5, 2: 4, 3: 8, 4: 1, 5: 1}
511   
512    Degrees
513    [4, 3, 3, 2, 2, 3, 2, 3, 2, 3, 3, 3, 3, 5, 1, 1, 1, 1, 1]
514   
515    Hubs
516    [13, 0, 1]
517   
518    Shortest path
519    [2, 0]
520   
521    Distance
522    1
523   
524    Diameter
525    4
526
527Subgraph image:
528
529.. image:: files/network-subgraph.png
530
531Additional functionality
532------------------------
533
534Should you need any additional functionality, just tell us. Many things are
535trivial to implement in C++ and will be much faster than the corresponding
536scripts in Python. (In this regard, minimal span trees, maximal flows, coloring
537and shortest path search are, of course, not considered basic functionality. :)
538
539*****************************
540Community Detection in Graphs
541*****************************
542
543.. autoclass:: Orange.network.NetworkClustering
544   :members:
545
546.. _network-constructor.py: code/network-constructor.py
547.. _network-optimization.py: code/network-optimization.py
548.. _network-read.py: code/network-read.py
549.. _K5.net: code/K5.net
550.. _combination.net: code/combination.net
551.. _network-widget.py: code/network-widget.py
552.. _network-graph-analysis.py: code/network-graph-analysis.py
553.. _network-graph.py: code/network-graph.py
554.. _network-graph-obj.py: code/network-graph-obj.py
555
556"""
557import math
558import random
559import os
560
561import Orange.core
562import Orange.data
563import Orange.projection
564
565from Orange.core import Graph, GraphAsList, GraphAsMatrix, GraphAsTree
566
567class MdsTypeClass():
568    def __init__(self):
569        self.componentMDS = 0
570        self.exactSimulation = 1
571        self.MDS = 2
572
573MdsType = MdsTypeClass()
574
575class Network(Orange.core.Network):
576   
577    """Bases: :obj:`Orange.network.GraphAsList`, :obj:`Orange.network.Graph`
578   
579    Data structure for representing directed and undirected networks.
580   
581    Network class holds network structure information and supports basic
582    network analysis. Network class is inherited from
583    :obj:`Orange.network.GraphAsList`. Refer to
584    :obj:`Orange.network.GraphAsList` for more graph analysis tools. See the
585    Orange.core.Pathfinder class for a way to simplify your network.
586   
587    .. attribute:: coors
588   
589        Coordinates for all vertices. They are initialized to random positions.
590        You can modify them manually or use one of the optimization algorithms.
591        Usage: coors[0][i], coors[1][i]; 0 for x-axis, 1 for y-axis
592   
593   
594    .. attribute:: items
595   
596        ExampleTable with information about vertices. Number of rows should
597        match the number of vertices.
598       
599    .. attribute:: links
600   
601        ExampleTable with information about edges. Number of rows should match
602        the number of edges. Two float attributes named "u" and "v" must be in
603        links table domain to relate the data of an example to an edge. Here,
604        egde is defined by two vertices "u" and "v".
605
606    .. attribute:: optimization
607   
608        An instance of the NetworkOptimization class. Various network layout
609        optimization methods can be applied to the network through this
610        attribute.
611       
612    .. method:: from_distance_matrix(matrix, lower, upper, kNN=0):
613       
614        Creates edges between vertices with the distance within given
615        threshold. The DistanceMatrix dimension should equal the number of
616        vertices.
617       
618        :param matrix: number of objects in a matrix must match the number
619            of vertices in a network.
620        :type matrix: Orange.core.SymMatrix
621        :param lower: lower distance bound.
622        :type lower: float
623        :param upper: upper distance bound.
624        :type upper: float
625        :param kNN: specifies the minimum number of closest vertices to be
626            connected.
627        :type kNN: int
628       
629    .. method:: hide_vertices(vertices)
630       
631        Remove vertices from optimize list
632       
633    .. method:: show_vertices(vertices)
634   
635        Add vertices to optimize list
636       
637    .. method:: show_all()
638   
639        Add all vertices to optimize list
640       
641    .. method:: get_visible()
642   
643        Return optimize list
644   
645    """
646   
647    def __init__(self, *args):
648        """:param nVertices: number of vertices (default 1)
649        :param nEdges: number of edge types (default 1)
650        :param directedGraph: directed edges (default True)
651       
652        """
653        #print "orngNetwork.Network"
654        self.optimization = NetworkOptimization(self)
655        self.clustering = NetworkClustering(self)
656       
657    def get_distance_matrix_threshold(self, matrix, ratio):
658        """Return lower and upper distance threshold values for the given
659        ratio of edges
660       
661        """
662        values = []
663        for i in range(matrix.dim):
664            for j in range(i):
665                values.append((matrix[i,j], i, j))
666               
667        values.sort()
668        return values[0][0], values[int(ratio*len(values))][0]
669       
670    def save(self, fileName):
671        """Save the network to a Pajek (.net) or GML file format.
672        data.Table items and links are saved automatically if the value is not
673        None. They are saved to "file_items.tab" and "file_links.tab" files.
674       
675        :param fileName: file path
676        :type fileName: string
677       
678        """
679        try:
680            root, ext = os.path.splitext(fileName)
681            if ext == '':
682                fileName = root + '.net'
683            graphFile = open(fileName, 'w+')
684        except IOError:
685            return 1
686           
687        root, ext = os.path.splitext(fileName)
688        if ext.lower() == ".gml":
689            self.saveGML(graphFile)
690        else:
691            self.save_pajek(graphFile)
692
693    def save_gml(self, fp):
694        """Save network to GML (.gml) file format.
695       
696        :param fp: file pointer
697        :type fp: file
698       
699        """
700        fp.write("graph\n[\n")
701        tabs = "\t"
702        fp.write("%slabel\t\"%s\"\n" % (tabs, self.name))
703       
704        for v in range(self.nVertices):
705            try:
706                label = self.items[v]['label']
707            except:
708                label = ""
709           
710            fp.write("\tnode\n\t[\n\t\tid\t%d\n\t\tlabel\t\"%s\"\n\t]\n" % 
711                     (v, label))
712       
713        for u,v in self.getEdges():
714            fp.write("\tedge\n\t[\n\t\tsource\t%d\n\t\ttarget\t%d\n\t\tlabel\t\"%s\"\n\t]\n" % (u, v, ""))
715       
716        fp.write("]\n")
717       
718        if self.items != None and len(self.items) > 0:
719            (name, ext) = os.path.splitext(fp.name)
720            self.items.save(name + "_items.tab")
721           
722        if hasattr(self, 'links') and self.links != None and \
723                                                        len(self.links) > 0:
724            (name, ext) = os.path.splitext(fp.name)
725            self.links.save(name + "_links.tab")
726       
727    def save_pajek(self, fp):
728        """Save network to Pajek (.net) file format.
729       
730        :param fp: file pointer
731        :type fp: file
732       
733        """
734        name = ''
735        fp.write('### Generated with Orange Network Visualizer ### \n\n\n')
736        if name == '':
737            fp.write('*Network ' + '"no name" \n\n')
738        else:
739            fp.write('*Network ' + str(name) + ' \n\n')
740
741        # print node descriptions
742        fp.write('*Vertices %8d %8d\n' % (self.nVertices, self.nEdgeTypes))
743        for v in range(self.nVertices):
744            fp.write('% 8d ' % (v + 1))
745            try:
746                label = self.items[v]['label']
747                fp.write(str('"' + str(label) + '"') + ' \t')
748            except:
749                fp.write(str('"' + str(v) + '"') + ' \t')
750           
751            if hasattr(self, 'coors'):
752                x = self.coors[0][v]
753                y = self.coors[1][v]
754                z = 0.5000
755                fp.write('%.4f    %.4f    %.4f\t' % (x, y, z))
756            fp.write('\n')
757
758        # print edge descriptions
759        # not directed edges
760        if self.directed:
761            fp.write('*Arcs \n')
762            for (i, j) in self.getEdges():
763                if len(self[i, j]) > 0:
764                    if self.nEdgeTypes > 1:
765                        edge_str = str(self[i, j])
766                    else:
767                        edge_str = "%f" % float(str(self[i, j]))
768                    fp.write('%8d %8d %s' % (i + 1, j + 1, edge_str))                   
769                    fp.write('\n')
770        # directed edges
771        else:
772            fp.write('*Edges \n')
773            writtenEdges = {}
774            for (i, j) in self.getEdges():
775                if len(self[i, j]) > 0:
776                    if i > j: i,j = j,i
777                   
778                    if not (i,j) in writtenEdges:
779                        writtenEdges[(i,j)] = 1
780                    else:
781                        continue
782
783                    if self.nEdgeTypes > 1:
784                        edge_str = str(self[i, j])
785                    else:
786                        edge_str = "%f" % float(str(self[i, j]))
787                    fp.write('%8d %8d %s' % (i + 1, j + 1, edge_str))                   
788                    fp.write('\n')
789
790        fp.write('\n')
791       
792        if self.items != None and len(self.items) > 0:
793            (name, ext) = os.path.splitext(fp.name)
794            self.items.save(name + "_items.tab")
795           
796        if hasattr(self, 'links') and self.links != None \
797                                                    and len(self.links) > 0:
798            (name, ext) = os.path.splitext(fp.name)
799            self.links.save(name + "_links.tab")
800
801        return 0
802       
803    @staticmethod
804    def read(fileName, directed=0):
805        """Read network. Supported network formats: from Pajek (.net) file,
806        GML.
807       
808        :param fileName: file path
809        :type fileName: string
810        :param directed: (default False)
811        :type directed: bool
812       
813        """
814        if type(fileName) == file:
815            root, ext = os.path.splitext(fileName.name)
816            if ext.lower() == ".net":
817                net = Network(2,0).parseNetwork(fileName.read(), directed)
818                net.optimization = NetworkOptimization(net)
819                return net
820            else:
821                print "invalid network type", fileName.name
822                return None
823        else:
824            root, ext = os.path.splitext(fileName)
825            net = None
826            if ext.lower() == ".net":
827                net = Network(2,0).readPajek(fileName, directed)
828            elif ext.lower() == ".gml":
829                net = Network(2,0).readGML(fileName)
830            else:
831                print "Invalid file type %s" % fileName
832               
833            if net is not None:
834                net.optimization = NetworkOptimization(net)
835            return net
836
837    ##########################################################################
838    ### BEGIN: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0)                ###
839    ##########################################################################
840   
841    def getDistanceMatrixThreshold(self, matrix, ratio):
842        import warnings
843        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
844        "get_distance_matrix_threshold", DeprecationWarning)
845        return self.get_distance_matrix_threshold(matrix, ratio)
846   
847    def saveNetwork(self, fileName):
848        import warnings
849        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
850        "save", DeprecationWarning)
851        return self.save(fileName)
852       
853    def savePajek(fp):
854        import warnings
855        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
856        "save_pajek", DeprecationWarning)
857        return self.save_pajek(fp)
858       
859    def saveGML(self, fp):
860        import warnings
861        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
862        "save_gml", DeprecationWarning)
863        return self.save_gml(fp)
864
865    ##########################################################################
866    ### END: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0)                  ###
867    ##########################################################################
868   
869class NetworkOptimization(Orange.core.NetworkOptimization):
870   
871    """Perform network layout optimization. Network structure is defined in
872    :obj:`Orange.network.Network` class.
873   
874    :param network: Network to optimize
875    :type network: Orange.network.Network
876   
877    .. attribute:: graph
878   
879    Holds the :obj:`Orange.network.Network` object.
880   
881    .. method:: random()
882   
883    Random layout optimization.
884   
885    .. method:: fruchterman_reingold(steps=100, temperature=1000, coolFactor=default, hiddenNodes=[], weighted=False)
886       
887    Fruchterman-Reingold spring layout optimization. Set number of iterations
888    with argument steps, start temperature with temperature (for example: 1000)
889    and set list of hidden nodes with argument hidden_nodes.   
890       
891    .. method:: radial_fruchterman_reingold(center, steps=100, temperature=1000)
892   
893    Radial Fruchterman-Reingold spring layout optimization. Set center node
894    with attribute center, number of iterations with argument steps and start
895    temperature with temperature (for example: 1000).
896   
897    .. method:: circular_original()
898   
899    Circular layout optimization based on original order.
900   
901    .. method:: circular_random()
902   
903    Circular layout optimization based on random order.
904   
905    .. method:: circular_crossing_reduction()
906   
907    Circular layout optimization (Michael Baur, Ulrik Brandes) with crossing
908    reduction.
909   
910    .. method:: closest_vertex(x, y)
911   
912    Return the closest vertex to (x, y) coordinate. 
913   
914    .. method:: vertex_distances(x, y)
915   
916    Return distances (list of (distance, vertex) tuples) of all vertices to
917    the given coordinate.
918   
919    .. method:: get_vertices_in_rect(x1, y1, x2, y2)
920   
921    Return a list of all vertices in given rectangle.
922   
923    """
924   
925    def __init__(self, network=None, name="None"):
926        if network is None:
927            network = Orange.core.Network(2, 0)
928           
929        self.setGraph(network)
930        self.graph = network
931       
932        self.maxWidth = 1000
933        self.maxHeight = 1000
934       
935        self.attributeList = {}
936        self.attributeValues = {}
937        self.vertexDistance = None
938        self.mds = None
939       
940    def set_network(self, network):
941        """Set the network object for layout optimization.
942   
943        :param network: network object for layout optimization
944        :type network: Orange.network.Network
945       
946        """
947        self.setGraph(network)
948       
949    def _compute_forces(self):
950        """Compute forces for each vertex for force vector visualization."""
951        n = self.graph.nVertices
952        vertices = set(range(n))
953        e_avg = 0
954        edges = self.graph.getEdges()
955        for u,v in edges:
956            u_ = numpy.array([self.graph.coors[0][u], self.graph.coors[1][u]])
957            v_ = numpy.array([self.graph.coors[0][v], self.graph.coors[1][v]])
958            e_avg += numpy.linalg.norm(u_ - v_)
959        e_avg /= len(edges)
960       
961        forces = []
962        maxforce = []
963        components = self.graph.getConnectedComponents()
964        for component in components:
965            outer_vertices = vertices - set(component)
966           
967            for u in component:
968                u_ = numpy.array([self.graph.coors[0][u], 
969                                  self.graph.coors[1][u]])
970                force = numpy.array([0.0, 0.0])               
971                for v in outer_vertices:
972                    v_ = numpy.array([self.graph.coors[0][v], 
973                                      self.graph.coors[1][v]])
974                    d = self.vertexDistance[u, v]
975                    norm = numpy.linalg.norm(v_ - u_)
976                    force += (d - norm) * (v_ - u_) / norm
977           
978                forces.append(force)
979                maxforce.append(numpy.linalg.norm(force))
980           
981        maxforce = max(maxforce)
982        rv = []
983        for v in range(n):
984            force = forces[v]
985            v_ = numpy.array([self.graph.coors[0][v], self.graph.coors[1][v]])
986            f = force * e_avg / maxforce
987            rv.append(([v_[0], v_[0] + f[0]],[v_[1], v_[1] + f[1]]))
988
989        return rv
990   
991    def collapse(self):
992        """Experimental method to group cliques to meta nodes."""
993        if len(self.graph.getNodes(1)) > 0:
994            nodes = list(set(range(self.graph.nVertices)) - \
995                         set(self.graph.getNodes(1)))
996               
997            if len(nodes) > 0:
998                subgraph = Orange.core.Network(self.graph.getSubGraph(nodes))
999                oldcoors = self.coors
1000                self.setGraph(subgraph)
1001                self.graph = subgraph
1002                   
1003                for i in range(len(nodes)):
1004                    self.coors[0][i] = oldcoors[0][nodes[i]]
1005                    self.coors[1][i] = oldcoors[1][nodes[i]]
1006
1007        else:
1008            fullgraphs = self.graph.getLargestFullGraphs()
1009            subgraph = self.graph
1010           
1011            if len(fullgraphs) > 0:
1012                used = set()
1013                graphstomerge = list()
1014                #print fullgraphs
1015                for fullgraph in fullgraphs:
1016                    #print fullgraph
1017                    fullgraph_set = set(fullgraph)
1018                    if len(used & fullgraph_set) == 0:
1019                        graphstomerge.append(fullgraph)
1020                        used |= fullgraph_set
1021                       
1022                #print graphstomerge
1023                #print used
1024                subgraph = Orange.core.Network(
1025                            subgraph.getSubGraphMergeClusters(graphstomerge))
1026                                   
1027                nodescomp = list(set(range(self.graph.nVertices)) - used)
1028               
1029                #subgraph.setattr("items", self.graph.items.getitems(nodescomp))
1030                #subgraph.items.append(self.graph.items[0])
1031                oldcoors = self.coors
1032                self.setGraph(subgraph)
1033                self.graph = subgraph
1034                for i in range(len(nodescomp)):
1035                    self.coors[0][i] = oldcoors[0][nodescomp[i]]
1036                    self.coors[1][i] = oldcoors[1][nodescomp[i]]
1037                   
1038                # place meta vertex in center of cluster   
1039                x, y = 0, 0
1040                for node in used:
1041                    x += oldcoors[0][node]
1042                    y += oldcoors[1][node]
1043                   
1044                x = x / len(used)
1045                y = y / len(used)
1046               
1047                self.coors[0][len(nodescomp)] = x
1048                self.coors[1][len(nodescomp)] = y
1049           
1050    def get_vars(self):
1051        """Return a list of features in network items."""
1052        vars = []
1053        if (self.graph != None):
1054            if hasattr(self.graph, "items"):
1055                if isinstance(self.graph.items, Orange.data.Table):
1056                    vars[:0] = self.graph.items.domain.variables
1057               
1058                    metas = self.graph.items.domain.getmetas(0)
1059                    for i, var in metas.iteritems():
1060                        vars.append(var)
1061        return vars
1062   
1063    def get_edge_vars(self):
1064        """Return a list of features in network links."""
1065        vars = []
1066        if (self.graph != None):
1067            if hasattr(self.graph, "links"):
1068                if isinstance(self.graph.links, Orange.data.Table):
1069                    vars[:0] = self.graph.links.domain.variables
1070               
1071                    metas = self.graph.links.domain.getmetas(0)
1072                    for i, var in metas.iteritems():
1073                        vars.append(var)
1074                       
1075        return [x for x in vars if str(x.name) != 'u' and str(x.name) != 'v']
1076       
1077    def rotate_vertices(self, components, phi): 
1078        """Rotate network components for a given angle.
1079       
1080        :param components: list of network components
1081        :type components: list of lists of vertex indices
1082        :param phi: list of component rotation angles (unit: radians)
1083        """ 
1084        #print phi
1085        for i in range(len(components)):
1086            if phi[i] == 0:
1087                continue
1088           
1089            component = components[i]
1090           
1091            x = self.graph.coors[0][component]
1092            y = self.graph.coors[1][component]
1093           
1094            x_center = x.mean()
1095            y_center = y.mean()
1096           
1097            x = x - x_center
1098            y = y - y_center
1099           
1100            r = numpy.sqrt(x ** 2 + y ** 2)
1101            fi = numpy.arctan2(y, x)
1102           
1103            fi += phi[i]
1104            #fi += factor * M[i] * numpy.pi / 180
1105               
1106            x = r * numpy.cos(fi)
1107            y = r * numpy.sin(fi)
1108           
1109            self.graph.coors[0][component] = x + x_center
1110            self.graph.coors[1][component] = y + y_center
1111           
1112    def rotate_components(self, maxSteps=100, minMoment=0.000000001, 
1113                          callbackProgress=None, callbackUpdateCanvas=None):
1114        """Rotate the network components using a spring model."""
1115        if self.vertexDistance == None:
1116            return 1
1117       
1118        if self.graph == None:
1119            return 1
1120       
1121        if self.vertexDistance.dim != self.graph.nVertices:
1122            return 1
1123       
1124        self.stopRotate = 0
1125       
1126        # rotate only components with more than one vertex
1127        components = [component for component \
1128                      in self.graph.getConnectedComponents() \
1129                      if len(component) > 1]
1130        vertices = set(range(self.graph.nVertices))
1131        step = 0
1132        M = [1]
1133        temperature = [[30.0, 1] for i in range(len(components))]
1134        dirChange = [0] * len(components)
1135        while step < maxSteps and (max(M) > minMoment or min(M) < -minMoment) \
1136                                                     and not self.stopRotate:
1137            M = [0] * len(components) 
1138           
1139            for i in range(len(components)):
1140                component = components[i]
1141               
1142                outer_vertices = vertices - set(component)
1143               
1144                x = self.graph.coors[0][component]
1145                y = self.graph.coors[1][component]
1146               
1147                x_center = x.mean()
1148                y_center = y.mean()
1149               
1150                for j in range(len(component)):
1151                    u = component[j]
1152
1153                    for v in outer_vertices:
1154                        d = self.vertexDistance[u, v]
1155                        u_x = self.graph.coors[0][u]
1156                        u_y = self.graph.coors[1][u]
1157                        v_x = self.graph.coors[0][v]
1158                        v_y = self.graph.coors[1][v]
1159                        L = [(u_x - v_x), (u_y - v_y)]
1160                        R = [(u_x - x_center), (u_y - y_center)]
1161                        e = math.sqrt((v_x - x_center) ** 2 + \
1162                                      (v_y - y_center) ** 2)
1163                       
1164                        M[i] += (1 - d) / (e ** 2) * numpy.cross(R, L)
1165           
1166            tmpM = numpy.array(M)
1167            #print numpy.min(tmpM), numpy.max(tmpM),numpy.average(tmpM),numpy.min(numpy.abs(tmpM))
1168           
1169            phi = [0] * len(components)
1170            #print "rotating", temperature, M
1171            for i in range(len(M)):
1172                if M[i] > 0:
1173                    if temperature[i][1] < 0:
1174                        temperature[i][0] = temperature[i][0] * 5 / 10
1175                        temperature[i][1] = 1
1176                        dirChange[i] += 1
1177                       
1178                    phi[i] = temperature[i][0] * numpy.pi / 180
1179                elif M[i] < 0: 
1180                    if temperature[i][1] > 0:
1181                        temperature[i][0] = temperature[i][0] * 5 / 10
1182                        temperature[i][1] = -1
1183                        dirChange[i] += 1
1184                   
1185                    phi[i] = -temperature[i][0] * numpy.pi / 180
1186           
1187            # stop rotating when phi is to small to notice the rotation
1188            if max(phi) < numpy.pi / 1800:
1189                #print "breaking"
1190                break
1191           
1192            self.rotate_vertices(components, phi)
1193            if callbackUpdateCanvas: callbackUpdateCanvas()
1194            if callbackProgress : callbackProgress(min([dirChange[i] for i \
1195                                    in range(len(dirChange)) if M[i] != 0]), 9)
1196            step += 1
1197   
1198    def mds_update_data(self, components, mds, callbackUpdateCanvas):
1199        """Translate and rotate the network components to computed positions."""
1200        component_props = []
1201        x_mds = []
1202        y_mds = []
1203        phi = [None] * len(components)
1204        self.diag_coors = math.sqrt(( \
1205                    min(self.graph.coors[0]) - max(self.graph.coors[0]))**2 + \
1206                    (min(self.graph.coors[1]) - max(self.graph.coors[1]))**2)
1207       
1208        if self.mdsType == MdsType.MDS:
1209            x = [mds.points[u][0] for u in range(self.graph.nVertices)]
1210            y = [mds.points[u][1] for u in range(self.graph.nVertices)]
1211            self.graph.coors[0][range(self.graph.nVertices)] =  x
1212            self.graph.coors[1][range(self.graph.nVertices)] =  y
1213            if callbackUpdateCanvas:
1214                callbackUpdateCanvas()
1215            return
1216       
1217        for i in range(len(components)):   
1218            component = components[i]
1219           
1220            if len(mds.points) == len(components):  # if average linkage before
1221                x_avg_mds = mds.points[i][0]
1222                y_avg_mds = mds.points[i][1]
1223            else:                                   # if not average linkage before
1224                x = [mds.points[u][0] for u in component]
1225                y = [mds.points[u][1] for u in component]
1226       
1227                x_avg_mds = sum(x) / len(x) 
1228                y_avg_mds = sum(y) / len(y)
1229                # compute rotation angle
1230                c = [numpy.linalg.norm(numpy.cross(mds.points[u], \
1231                            [self.graph.coors[0][u],self.graph.coors[1][u]])) \
1232                            for u in component]
1233                n = [numpy.vdot([self.graph.coors[0][u], \
1234                                 self.graph.coors[1][u]], \
1235                                 [self.graph.coors[0][u], \
1236                                  self.graph.coors[1][u]]) for u in component]
1237                phi[i] = sum(c) / sum(n)
1238                #print phi
1239           
1240            x = self.graph.coors[0][component]
1241            y = self.graph.coors[1][component]
1242           
1243            x_avg_graph = sum(x) / len(x)
1244            y_avg_graph = sum(y) / len(y)
1245           
1246            x_mds.append(x_avg_mds) 
1247            y_mds.append(y_avg_mds)
1248
1249            component_props.append((x_avg_graph, y_avg_graph, \
1250                                    x_avg_mds, y_avg_mds, phi))
1251       
1252        w = max(self.graph.coors[0]) - min(self.graph.coors[0])
1253        h = max(self.graph.coors[1]) - min(self.graph.coors[1])
1254        d = math.sqrt(w**2 + h**2)
1255        #d = math.sqrt(w*h)
1256        e = [math.sqrt((self.graph.coors[0][u] - self.graph.coors[0][v])**2 + 
1257                  (self.graph.coors[1][u] - self.graph.coors[1][v])**2) for 
1258                  (u, v) in self.graph.getEdges()]
1259       
1260        if self.scalingRatio == 0:
1261            pass
1262        elif self.scalingRatio == 1:
1263            self.mdsScaleRatio = d
1264        elif self.scalingRatio == 2:
1265            self.mdsScaleRatio = d / sum(e) * float(len(e))
1266        elif self.scalingRatio == 3:
1267            self.mdsScaleRatio = 1 / sum(e) * float(len(e))
1268        elif self.scalingRatio == 4:
1269            self.mdsScaleRatio = w * h
1270        elif self.scalingRatio == 5:
1271            self.mdsScaleRatio = math.sqrt(w * h)
1272        elif self.scalingRatio == 6:
1273            self.mdsScaleRatio = 1
1274        elif self.scalingRatio == 7:
1275            e_fr = 0
1276            e_count = 0
1277            for i in range(self.graph.nVertices):
1278                for j in range(i + 1, self.graph.nVertices):
1279                    x1 = self.graph.coors[0][i]
1280                    y1 = self.graph.coors[1][i]
1281                    x2 = self.graph.coors[0][j]
1282                    y2 = self.graph.coors[1][j]
1283                    e_fr += math.sqrt((x1-x2)**2 + (y1-y2)**2)
1284                    e_count += 1
1285            self.mdsScaleRatio = e_fr / e_count
1286        elif self.scalingRatio == 8:
1287            e_fr = 0
1288            e_count = 0
1289            for i in range(len(components)):
1290                for j in range(i + 1, len(components)):
1291                    x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, \
1292                    y_avg_mds_i, phi_i = component_props[i]
1293                    x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, \
1294                    y_avg_mds_j, phi_j = component_props[j]
1295                    e_fr += math.sqrt((x_avg_graph_i-x_avg_graph_j)**2 + \
1296                                      (y_avg_graph_i-y_avg_graph_j)**2)
1297                    e_count += 1
1298            self.mdsScaleRatio = e_fr / e_count       
1299        elif self.scalingRatio == 9:
1300            e_fr = 0
1301            e_count = 0
1302            for i in range(len(components)):   
1303                component = components[i]
1304                x = self.graph.coors[0][component]
1305                y = self.graph.coors[1][component]
1306                for i in range(len(x)):
1307                    for j in range(i + 1, len(y)):
1308                        x1 = x[i]
1309                        y1 = y[i]
1310                        x2 = x[j]
1311                        y2 = y[j]
1312                        e_fr += math.sqrt((x1-x2)**2 + (y1-y2)**2)
1313                        e_count += 1
1314            self.mdsScaleRatio = e_fr / e_count
1315       
1316        diag_mds =  math.sqrt((max(x_mds) - min(x_mds))**2 + (max(y_mds) - \
1317                                                              min(y_mds))**2)
1318        e = [math.sqrt((self.graph.coors[0][u] - self.graph.coors[0][v])**2 + 
1319                  (self.graph.coors[1][u] - self.graph.coors[1][v])**2) for 
1320                  (u, v) in self.graph.getEdges()]
1321        e = sum(e) / float(len(e))
1322       
1323        x = [mds.points[u][0] for u in range(len(mds.points))]
1324        y = [mds.points[u][1] for u in range(len(mds.points))]
1325        w = max(x) - min(x)
1326        h = max(y) - min(y)
1327        d = math.sqrt(w**2 + h**2)
1328       
1329        if len(x) == 1:
1330            r = 1
1331        else:
1332            if self.scalingRatio == 0:
1333                r = self.mdsScaleRatio / d * e
1334            elif self.scalingRatio == 1:
1335                r = self.mdsScaleRatio / d
1336            elif self.scalingRatio == 2:
1337                r = self.mdsScaleRatio / d * e
1338            elif self.scalingRatio == 3:
1339                r = self.mdsScaleRatio * e
1340            elif self.scalingRatio == 4:
1341                r = self.mdsScaleRatio / (w * h)
1342            elif self.scalingRatio == 5:
1343                r = self.mdsScaleRatio / math.sqrt(w * h)
1344            elif self.scalingRatio == 6:
1345                r = 1 / math.sqrt(self.graph.nVertices)
1346            elif self.scalingRatio == 7:
1347                e_mds = 0
1348                e_count = 0
1349                for i in range(len(mds.points)):
1350                    for j in range(i):
1351                        x1 = mds.points[i][0]
1352                        y1 = mds.points[i][1]
1353                        x2 = mds.points[j][0]
1354                        y2 = mds.points[j][1]
1355                        e_mds += math.sqrt((x1-x2)**2 + (y1-y2)**2)
1356                        e_count += 1
1357                r = self.mdsScaleRatio / e_mds * e_count
1358            elif self.scalingRatio == 8:
1359                e_mds = 0
1360                e_count = 0
1361                for i in range(len(components)):
1362                    for j in range(i + 1, len(components)):
1363                        x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, \
1364                        y_avg_mds_i, phi_i = component_props[i]
1365                        x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, \
1366                        y_avg_mds_j, phi_j = component_props[j]
1367                        e_mds += math.sqrt((x_avg_mds_i-x_avg_mds_j)**2 + \
1368                                           (y_avg_mds_i-y_avg_mds_j)**2)
1369                        e_count += 1
1370                r = self.mdsScaleRatio / e_mds * e_count
1371            elif self.scalingRatio == 9:
1372                e_mds = 0
1373                e_count = 0
1374                for i in range(len(mds.points)):
1375                    for j in range(i):
1376                        x1 = mds.points[i][0]
1377                        y1 = mds.points[i][1]
1378                        x2 = mds.points[j][0]
1379                        y2 = mds.points[j][1]
1380                        e_mds += math.sqrt((x1-x2)**2 + (y1-y2)**2)
1381                        e_count += 1
1382                r = self.mdsScaleRatio / e_mds * e_count
1383               
1384            #r = self.mdsScaleRatio / d
1385            #print "d", d, "r", r
1386            #r = self.mdsScaleRatio / math.sqrt(self.graph.nVertices)
1387           
1388        for i in range(len(components)):
1389            component = components[i]
1390            x_avg_graph, y_avg_graph, x_avg_mds, \
1391            y_avg_mds, phi = component_props[i]
1392           
1393#            if phi[i]:  # rotate vertices
1394#                #print "rotate", i, phi[i]
1395#                r = numpy.array([[numpy.cos(phi[i]), -numpy.sin(phi[i])], [numpy.sin(phi[i]), numpy.cos(phi[i])]])  #rotation matrix
1396#                c = [x_avg_graph, y_avg_graph]  # center of mass in FR coordinate system
1397#                v = [numpy.dot(numpy.array([self.graph.coors[0][u], self.graph.coors[1][u]]) - c, r) + c for u in component]
1398#                self.graph.coors[0][component] = [u[0] for u in v]
1399#                self.graph.coors[1][component] = [u[1] for u in v]
1400               
1401            # translate vertices
1402            if not self.rotationOnly:
1403                self.graph.coors[0][component] = \
1404                (self.graph.coors[0][component] - x_avg_graph) / r + x_avg_mds
1405                self.graph.coors[1][component] = \
1406                (self.graph.coors[1][component] - y_avg_graph) / r + y_avg_mds
1407               
1408        if callbackUpdateCanvas:
1409            callbackUpdateCanvas()
1410   
1411    def mds_callback(self, a, b=None):
1412        """Refresh the UI when running  MDS on network components."""
1413        if not self.mdsStep % self.mdsRefresh:
1414            self.mds_update_data(self.mdsComponentList, 
1415                               self.mds, 
1416                               self.callbackUpdateCanvas)
1417           
1418            if self.mdsType == MdsType.exactSimulation:
1419                self.mds.points = [[self.graph.coors[0][i], \
1420                                    self.graph.coors[1][i]] \
1421                                    for i in range(len(self.graph.coors))]
1422                self.mds.freshD = 0
1423           
1424            if self.callbackProgress != None:
1425                self.callbackProgress(self.mds.avgStress, self.mdsStep)
1426               
1427        self.mdsStep += 1
1428
1429        if self.stopMDS:
1430            return 0
1431        else:
1432            return 1
1433           
1434    def mds_components(self, mdsSteps, mdsRefresh, callbackProgress=None, \
1435                       callbackUpdateCanvas=None, torgerson=0, \
1436                       minStressDelta=0, avgLinkage=False, rotationOnly=False,\
1437                       mdsType=MdsType.componentMDS, scalingRatio=0, \
1438                       mdsFromCurrentPos=0):
1439        """Position the network components according to similarities among
1440        them.
1441       
1442        """
1443
1444        if self.vertexDistance == None:
1445            self.information('Set distance matrix to input signal')
1446            return 1
1447       
1448        if self.graph == None:
1449            return 1
1450       
1451        if self.vertexDistance.dim != self.graph.nVertices:
1452            return 1
1453       
1454        self.mdsComponentList = self.graph.getConnectedComponents()
1455        self.mdsRefresh = mdsRefresh
1456        self.mdsStep = 0
1457        self.stopMDS = 0
1458        self.vertexDistance.matrixType = Orange.core.SymMatrix.Symmetric
1459        self.diag_coors = math.sqrt((min(self.graph.coors[0]) -  \
1460                                     max(self.graph.coors[0]))**2 + \
1461                                     (min(self.graph.coors[1]) - \
1462                                      max(self.graph.coors[1]))**2)
1463        self.rotationOnly = rotationOnly
1464        self.mdsType = mdsType
1465        self.scalingRatio = scalingRatio
1466
1467        w = max(self.graph.coors[0]) - min(self.graph.coors[0])
1468        h = max(self.graph.coors[1]) - min(self.graph.coors[1])
1469        d = math.sqrt(w**2 + h**2)
1470        #d = math.sqrt(w*h)
1471        e = [math.sqrt((self.graph.coors[0][u] - self.graph.coors[0][v])**2 + 
1472                  (self.graph.coors[1][u] - self.graph.coors[1][v])**2) for 
1473                  (u, v) in self.graph.getEdges()]
1474        self.mdsScaleRatio = d / sum(e) * float(len(e))
1475        #print d / sum(e) * float(len(e))
1476       
1477        if avgLinkage:
1478            matrix = self.vertexDistance.avgLinkage(self.mdsComponentList)
1479        else:
1480            matrix = self.vertexDistance
1481       
1482        #if self.mds == None:
1483        self.mds = Orange.projection.mds.MDS(matrix)
1484       
1485        if mdsFromCurrentPos:
1486            if avgLinkage:
1487                for u, c in enumerate(self.mdsComponentList):
1488                    x = sum(self.graph.coors[0][c]) / len(c)
1489                    y = sum(self.graph.coors[1][c]) / len(c)
1490                    self.mds.points[u][0] = x
1491                    self.mds.points[u][1] = y
1492            else:
1493                for u in range(self.graph.nVertices):
1494                    self.mds.points[u][0] = self.graph.coors[0][u] 
1495                    self.mds.points[u][1] = self.graph.coors[1][u]
1496           
1497        # set min stress difference between 0.01 and 0.00001
1498        self.minStressDelta = minStressDelta
1499        self.callbackUpdateCanvas = callbackUpdateCanvas
1500        self.callbackProgress = callbackProgress
1501       
1502        if torgerson:
1503            self.mds.Torgerson() 
1504
1505        self.mds.optimize(mdsSteps, Orange.projection.mds.SgnRelStress, self.minStressDelta,\
1506                          progressCallback=self.mdsCallback)
1507        self.mds_update_data(self.mdsComponentList, self.mds, callbackUpdateCanvas)
1508       
1509        if callbackProgress != None:
1510            callbackProgress(self.mds.avgStress, self.mdsStep)
1511       
1512        del self.rotationOnly
1513        del self.diag_coors
1514        del self.mdsRefresh
1515        del self.mdsStep
1516        #del self.mds
1517        del self.mdsComponentList
1518        del self.minStressDelta
1519        del self.callbackUpdateCanvas
1520        del self.callbackProgress
1521        del self.mdsType
1522        del self.mdsScaleRatio
1523        del self.scalingRatio
1524        return 0
1525
1526    def mds_components_avg_linkage(self, mdsSteps, mdsRefresh, \
1527                                   callbackProgress=None, \
1528                                   callbackUpdateCanvas=None, torgerson=0, \
1529                                   minStressDelta = 0, scalingRatio=0,\
1530                                   mdsFromCurrentPos=0):
1531        return self.mds_components(mdsSteps, mdsRefresh, callbackProgress, \
1532                                   callbackUpdateCanvas, torgerson, \
1533                                   minStressDelta, True, \
1534                                   scalingRatio=scalingRatio, \
1535                                   mdsFromCurrentPos=mdsFromCurrentPos)
1536   
1537    ##########################################################################
1538    ### BEGIN: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0)                ###
1539    ##########################################################################
1540   
1541    def setNetwork(self, network):
1542        import warnings
1543        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1544        "set_network", DeprecationWarning)
1545        return self.set_network(network)
1546   
1547    def _computeForces(self):
1548        import warnings
1549        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1550        "_compute_forces", DeprecationWarning)
1551        return self._compute_forces()
1552   
1553    def getVars(self):
1554        import warnings
1555        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1556        "get_vars", DeprecationWarning)
1557        return self.get_vars()
1558       
1559    def getEdgeVars(self):
1560        import warnings
1561        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1562        "get_edge_vars", DeprecationWarning)
1563        return self.get_edge_vars()
1564   
1565    def rotateVertices(self, components, phi):
1566        import warnings
1567        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1568        "rotate_vertices", DeprecationWarning)
1569        return self.rotate_vertices(components, phi)
1570       
1571    def rotateComponents(self, maxSteps=100, minMoment=0.000000001, 
1572                         callbackProgress=None, callbackUpdateCanvas=None):
1573        import warnings
1574        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1575        "rotate_components", DeprecationWarning)
1576        return self.rotate_components(maxSteps, minMoment, 
1577                                        callbackProgress, callbackUpdateCanvas)
1578   
1579    def mdsUpdateData(self, components, mds, callbackUpdateCanvas):
1580        import warnings
1581        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1582        "mds_update_data", DeprecationWarning)
1583        return self.mds_update_data(components, mds, 
1584                                                  callbackUpdateCanvas)
1585   
1586    def mdsCallback(self, a, b=None):
1587        import warnings
1588        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1589        "mds_callback", DeprecationWarning)
1590        return self.mds_callback(a, b)
1591       
1592    def mdsComponents(self, mdsSteps, mdsRefresh, callbackProgress=None, \
1593                      callbackUpdateCanvas=None, torgerson=0, \
1594                      minStressDelta=0, avgLinkage=False, rotationOnly=False, \
1595                      mdsType=MdsType.componentMDS, scalingRatio=0, \
1596                      mdsFromCurrentPos=0):
1597        import warnings
1598        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1599        "mds_components", DeprecationWarning)
1600        return self.mds_components(mdsSteps, mdsRefresh, \
1601                          callbackProgress, callbackUpdateCanvas, torgerson, \
1602                          minStressDelta, avgLinkage, rotationOnly, \
1603                          mdsType, scalingRatio, mdsFromCurrentPos)
1604       
1605    def mdsComponentsAvgLinkage(self, mdsSteps, mdsRefresh, \
1606                                callbackProgress=None, \
1607                                callbackUpdateCanvas=None, torgerson=0, \
1608                                minStressDelta = 0, scalingRatio=0,\
1609                                mdsFromCurrentPos=0):
1610        import warnings
1611        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1612        "mds_components_avg_linkage", DeprecationWarning)
1613        return self.mds_components_avg_linkage(mdsSteps, \
1614                    mdsRefresh, callbackProgress, callbackUpdateCanvas, \
1615                    torgerson, minStressDelta, scalingRatio, mdsFromCurrentPos)
1616   
1617    def getData(self, i, j):
1618        import warnings
1619        warnings.warn("Deprecated, will be deleted in Orange 3.0.", 
1620                      DeprecationWarning)
1621        if self.graph.items is Orange.data.Table:
1622            return self.data[i][j]
1623        elif self.graph.data is type([]):
1624            return self.data[i][j]
1625       
1626    def nVertices(self):
1627        import warnings
1628        warnings.warn("Deprecated, will be deleted in Orange 3.0.", 
1629                      DeprecationWarning)
1630        if self.graph:
1631            return self.graph.nVertices
1632       
1633    def saveNetwork(self, fn):
1634        import warnings
1635        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1636        "Orange.Network.save", DeprecationWarning)
1637        name = ''
1638        try:
1639            root, ext = os.path.splitext(fn)
1640            if ext == '':
1641                fn = root + '.net'
1642           
1643            graphFile = file(fn, 'w+')
1644        except IOError:
1645            return 1
1646
1647        graphFile.write('### Generated with Orange.network ### \n\n\n')
1648        if name == '':
1649            graphFile.write('*Network ' + '"no name" \n\n')
1650        else:
1651            graphFile.write('*Network ' + str(name) + ' \n\n')
1652
1653
1654        #izpis opisov vozlisc
1655        print "e", self.graph.nEdgeTypes
1656        graphFile.write('*Vertices %8d %8d\n' % (self.graph.nVertices, \
1657                                                 self.graph.nEdgeTypes))
1658        for v in range(self.graph.nVertices):
1659            graphFile.write('% 8d ' % (v + 1))
1660#            if verticesParms[v].label!='':
1661#                self.GraphFile.write(str('"'+ verticesParms[v].label + '"') + ' \t')
1662#            else:
1663            try:
1664                label = self.graph.items[v]['label']
1665                graphFile.write(str('"' + str(label) + '"') + ' \t')
1666            except:
1667                graphFile.write(str('"' + str(v) + '"') + ' \t')
1668           
1669            x = self.network.coors[0][v]
1670            y = self.network.coors[1][v]
1671            #if x < 0: x = 0
1672            #if x >= 1: x = 0.9999
1673            #if y < 0: y = 0
1674            #if y >= 1: y = 0.9999
1675            z = 0.5000
1676            graphFile.write('%.4f    %.4f    %.4f\t' % (x, y, z))
1677            graphFile.write('\n')
1678
1679        #izpis opisov povezav
1680        #najprej neusmerjene
1681        if self.graph.directed:
1682            graphFile.write('*Arcs \n')
1683            for (i, j) in self.graph.getEdges():
1684                if len(self.graph[i, j]) > 0:
1685                    graphFile.write('%8d %8d %f' % (i + 1, j + 1, \
1686                                                float(str(self.graph[i, j]))))
1687                    graphFile.write('\n')
1688        else:
1689            graphFile.write('*Edges \n')
1690            for (i, j) in self.graph.getEdges():
1691                if len(self.graph[i, j]) > 0:
1692                    graphFile.write('%8d %8d %f' % (i + 1, j + 1, \
1693                                                float(str(self.graph[i, j]))))
1694                    graphFile.write('\n')
1695
1696        graphFile.write('\n')
1697        graphFile.close()
1698       
1699        if self.graph.items != None and len(self.graph.items) > 0:
1700            (name, ext) = os.path.splitext(fn)
1701            self.graph.items.save(name + "_items.tab")
1702           
1703        if self.graph.links != None and len(self.graph.links) > 0:
1704            (name, ext) = os.path.splitext(fn)
1705            self.graph.links.save(name + "_links.tab")
1706
1707        return 0
1708   
1709    def readNetwork(self, fn, directed=0):
1710        import warnings
1711        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1712        "Orange.Network.read", DeprecationWarning)
1713        network = Network(1,directed)
1714        net = network.readPajek(fn, directed)
1715        self.setGraph(net)
1716        self.graph = net
1717        return net
1718   
1719    ##########################################################################
1720    ### END: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0)                  ###
1721    ##########################################################################
1722   
1723class NetworkClustering():
1724   
1725    """A collection of algorithms for community detection in graphs.
1726   
1727    :param network: network data for community detection
1728    :type network: Orange.network.Network
1729    """ 
1730   
1731    random.seed(0)
1732   
1733    def __init__(self, network):
1734        self.net = network
1735       
1736       
1737    def label_propagation(self, results2items=0, resultHistory2items=0):
1738        """Label propagation method from Raghavan et al., 2007
1739       
1740        :param results2items: append a new feature result to items
1741            (Orange.data.Table)
1742        :type results2items: bool
1743        :param resultHistory2items: append new features result to items
1744            (Orange.data.Table) after each iteration of the algorithm
1745        :type resultHistory2items: bool
1746        """
1747       
1748        vertices = range(self.net.nVertices)
1749        labels = range(self.net.nVertices)
1750        lblhistory = []
1751        #consecutiveStop = 0
1752        for i in range(1000):
1753            random.shuffle(vertices)
1754            stop = 1
1755            for v in vertices:
1756                nbh = self.net.get_neighbours(v)
1757                if len(nbh) == 0:
1758                    continue
1759               
1760                lbls = [labels[u] for u in nbh]
1761                lbls = [(len(list(c)), l) for l, c in itertools.groupby(lbls)]
1762                m = max(lbls)[0]
1763                mlbls = [l for c, l in lbls if c >= m]
1764                lbl = random.choice(mlbls)
1765               
1766                if labels[v] not in mlbls: stop = 0
1767                labels[v] = lbl
1768               
1769            lblhistory.append([str(l) for l in labels])
1770            # if stopping condition might be satisfied, check it
1771            if stop:
1772                for v in vertices:
1773                    nbh = self.net.get_neighbours(v)
1774                    if len(nbh) == 0: continue
1775                    lbls = [labels[u] for u in nbh]
1776                    lbls = [(len(list(c)), l) for l, c \
1777                            in itertools.groupby(lbls)]
1778                    m = max(lbls)[0]
1779                    mlbls = [l for c, l in lbls if c >= m]
1780                    if labels[v] not in mlbls: 
1781                        stop = 0
1782                        break
1783                if stop: break
1784                   
1785        if results2items and not resultHistory2items:
1786            attrs = [Orange.data.variable.Discrete(
1787                                        'clustering label propagation',
1788                                        values=list(set([l for l \
1789                                                        in lblhistory[-1]])))]
1790            dom = Orange.data.Domain(attrs, 0)
1791            data = Orange.data.Table(dom, [[l] for l in lblhistory[-1]])
1792            if self.net.items is None:
1793                self.net.items = data 
1794            else: 
1795                self.net.items = Orange.data.Table([self.net.items, data])
1796        if resultHistory2items:
1797            attrs = [Orange.data.variable.Discrete('c'+ str(i),
1798                values=list(set([l for l in lblhistory[0]]))) for i,labels \
1799                in enumerate(lblhistory)]
1800            dom = Orange.data.Domain(attrs, 0)
1801            # transpose history
1802            data = map(list, zip(*lblhistory))
1803            data = Orange.data.Table(dom, data)
1804            if self.net.items is None:
1805                self.net.items = data 
1806            else: 
1807                self.net.items = Orange.data.Table([self.net.items, data])
1808
1809        return labels
1810   
1811    ##########################################################################
1812    ### BEGIN: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0)                ###
1813    ##########################################################################
1814   
1815    def labelPropagation(self, results2items=0, resultHistory2items=0):
1816        import warnings
1817        warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \
1818        "label_propagation", DeprecationWarning)
1819        return self.label_propagation(results2items=0, resultHistory2items=0)
1820       
1821    ##########################################################################
1822    ### END: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0)                  ###
1823    ##########################################################################
Note: See TracBrowser for help on using the repository browser.