source: orange/Orange/network/deprecated.py @ 10320:c03ea831d0d9

Revision 10320:c03ea831d0d9, 70.2 KB checked in by Ales Erjavec <ales.erjavec@…>, 2 years ago (diff)

Removes a module level random.seed call

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