source: orange/orange/Orange/network/__init__.py @ 7660:5f432be7cddc

Revision 7660:5f432be7cddc, 63.6 KB checked in by janezd <janez.demsar@…>, 3 years ago (diff)

Renamed Orange.data.feature to Orange.data.variable

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* .fruchtermanReingold(steps, temperature, coolingFactor=Default, hiddenNodes=[], weighted=False)
83* .radialFruchtermanReingold(center, steps, temperature)
84* .circularOriginal()
85* .circularRandom()
86* .circularCrossingReduction()
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.getNeighbours("Weight") to graph.getNeighbours(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.getNeighbours(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 getNeighbours(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:: edgeExists(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:: addCluster(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:: getNeighbours(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: getNeighbours will the return only the vertices that are
334        connected to v1 by edges of that type.
335   
336    .. method:: getEdgesFrom(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        getNeighbours.
342   
343    .. method:: getEdgesTo(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 getNeighbours.
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, getEdgeFrom 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    getNeighbours/getEdgesFrom/getEdgesTo 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, getEdgesFrom 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 getEdgesTo or getNeighbours 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:: getSubGraph(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:: getClusteringCoefficient()
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:: getConnectedComponents()
411   
412        Return a list of all connected components sorted descending by
413        component size.
414   
415    .. method:: getDegreeDistribution()
416   
417        Return degree distribution as dictionary of type
418        {degree:number_of_vertices}.
419   
420    .. method:: getDegrees()
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:: getHubs(n)
426   
427        Return a list of n largest hubs.
428   
429    .. method:: getShortestPaths(u, v)
430   
431        Return a list of vertices in the shortest path between u and v.
432   
433    .. method:: getDistance(u, v)
434   
435        Return a distance between vertices u and v.
436   
437    .. method:: getDiameter()
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:: fromDistanceMatrix(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:: hideVertices(vertices)
630       
631        Remove vertices from optimize list
632       
633    .. method:: showVertices(vertices)
634   
635        Add vertices to optimize list
636       
637    .. method:: showAll()
638   
639        Add all vertices to optimize list
640       
641    .. method:: getVisible()
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 getDistanceMatrixThreshold(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        self.saveNetwork(fileName)
680       
681    def saveNetwork(self, fileName):       
682        try:
683            root, ext = os.path.splitext(fileName)
684            if ext == '':
685                fileName = root + '.net'
686            graphFile = open(fileName, 'w+')
687        except IOError:
688            return 1
689           
690        root, ext = os.path.splitext(fileName)
691        if ext.lower() == ".gml":
692            self.saveGML(graphFile)
693        else:
694            self.savePajek(graphFile)
695
696    def saveGML(self, fp):
697        """Save network to GML (.gml) file format.
698       
699        :param fp: file pointer
700        :type fp: file
701       
702        """
703        fp.write("graph\n[\n")
704        tabs = "\t"
705        fp.write("%slabel\t\"%s\"\n" % (tabs, self.name))
706       
707        for v in range(self.nVertices):
708            try:
709                label = self.items[v]['label']
710            except:
711                label = ""
712           
713            fp.write("\tnode\n\t[\n\t\tid\t%d\n\t\tlabel\t\"%s\"\n\t]\n" % 
714                     (v, label))
715       
716        for u,v in self.getEdges():
717            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, ""))
718       
719        fp.write("]\n")
720       
721        if self.items != None and len(self.items) > 0:
722            (name, ext) = os.path.splitext(fp.name)
723            self.items.save(name + "_items.tab")
724           
725        if hasattr(self, 'links') and self.links != None and \
726                                                        len(self.links) > 0:
727            (name, ext) = os.path.splitext(fp.name)
728            self.links.save(name + "_links.tab")
729       
730    def savePajek(self, fp):
731        """Save network to Pajek (.net) file format.
732       
733        :param fp: file pointer
734        :type fp: file
735       
736        """
737        name = ''
738        fp.write('### Generated with Orange Network Visualizer ### \n\n\n')
739        if name == '':
740            fp.write('*Network ' + '"no name" \n\n')
741        else:
742            fp.write('*Network ' + str(name) + ' \n\n')
743
744        # print node descriptions
745        fp.write('*Vertices %8d %8d\n' % (self.nVertices, self.nEdgeTypes))
746        for v in range(self.nVertices):
747            fp.write('% 8d ' % (v + 1))
748            try:
749                label = self.items[v]['label']
750                fp.write(str('"' + str(label) + '"') + ' \t')
751            except:
752                fp.write(str('"' + str(v) + '"') + ' \t')
753           
754            if hasattr(self, 'coors'):
755                x = self.coors[0][v]
756                y = self.coors[1][v]
757                z = 0.5000
758                fp.write('%.4f    %.4f    %.4f\t' % (x, y, z))
759            fp.write('\n')
760
761        # print edge descriptions
762        # not directed edges
763        if self.directed:
764            fp.write('*Arcs \n')
765            for (i, j) in self.getEdges():
766                if len(self[i, j]) > 0:
767                    if self.nEdgeTypes > 1:
768                        edge_str = str(self[i, j])
769                    else:
770                        edge_str = "%f" % float(str(self[i, j]))
771                    fp.write('%8d %8d %s' % (i + 1, j + 1, edge_str))                   
772                    fp.write('\n')
773        # directed edges
774        else:
775            fp.write('*Edges \n')
776            writtenEdges = {}
777            for (i, j) in self.getEdges():
778                if len(self[i, j]) > 0:
779                    if i > j: i,j = j,i
780                   
781                    if not (i,j) in writtenEdges:
782                        writtenEdges[(i,j)] = 1
783                    else:
784                        continue
785
786                    if self.nEdgeTypes > 1:
787                        edge_str = str(self[i, j])
788                    else:
789                        edge_str = "%f" % float(str(self[i, j]))
790                    fp.write('%8d %8d %s' % (i + 1, j + 1, edge_str))                   
791                    fp.write('\n')
792
793        fp.write('\n')
794       
795        if self.items != None and len(self.items) > 0:
796            (name, ext) = os.path.splitext(fp.name)
797            self.items.save(name + "_items.tab")
798           
799        if hasattr(self, 'links') and self.links != None \
800                                                    and len(self.links) > 0:
801            (name, ext) = os.path.splitext(fp.name)
802            self.links.save(name + "_links.tab")
803
804        return 0
805       
806    @staticmethod
807    def read(fileName, directed=0):
808        """Read network. Supported network formats: from Pajek (.net) file,
809        GML.
810       
811        :param fileName: file path
812        :type fileName: string
813        :param directed: (default False)
814        :type directed: bool
815       
816        """
817        if type(fileName) == file:
818            root, ext = os.path.splitext(fileName.name)
819            if ext.lower() == ".net":
820                net = Network(2,0).parseNetwork(fileName.read(), directed)
821                net.optimization = NetworkOptimization(net)
822                return net
823            else:
824                print "invalid network type", fileName.name
825                return None
826        else:
827            root, ext = os.path.splitext(fileName)
828            net = None
829            if ext.lower() == ".net":
830                net = Network(2,0).readPajek(fileName, directed)
831            elif ext.lower() == ".gml":
832                net = Network(2,0).readGML(fileName)
833            else:
834                print "Invalid file type %s" % fileName
835               
836            if net is not None:
837                net.optimization = NetworkOptimization(net)
838            return net
839
840class NetworkOptimization(Orange.core.NetworkOptimization):
841   
842    """Perform network layout optimization. Network structure is defined in
843    :obj:`Orange.network.Network` class.
844   
845    :param network: Network to optimize
846    :type network: Orange.network.Network
847   
848    .. attribute:: graph
849   
850    Holds the :obj:`Orange.network.Network` object.
851   
852    .. method:: random()
853   
854    Random layout optimization.
855   
856    .. method:: fruchtermanReingold(steps=100, temperature=1000, coolFactor=default, hiddenNodes=[], weighted=False)
857       
858    Fruchterman-Reingold spring layout optimization. Set number of iterations
859    with argument steps, start temperature with temperature (for example: 1000)
860    and set list of hidden nodes with argument hidden_nodes.   
861       
862    .. method:: radialFruchtermanReingold(center, steps=100, temperature=1000)
863   
864    Radial Fruchterman-Reingold spring layout optimization. Set center node
865    with attribute center, number of iterations with argument steps and start
866    temperature with temperature (for example: 1000).
867   
868    .. method:: circularOriginal()
869   
870    Circular layout optimization based on original order.
871   
872    .. method:: circularRandom()
873   
874    Circular layout optimization based on random order.
875   
876    .. method:: circularCrossingReduction()
877   
878    Circular layout optimization (Michael Baur, Ulrik Brandes) with crossing
879    reduction.
880   
881    .. method:: closestVertex(x, y)
882   
883    Return the closest vertex to (x, y) coordinate. 
884   
885    .. method:: vertexDistances(x, y)
886   
887    Return distances (list of (distance, vertex) tuples) of all vertices to
888    the given coordinate.
889   
890    .. method:: getVerticesInRect(x1, y1, x2, y2)
891   
892    Return a list of all vertices in given rectangle.
893   
894    """
895   
896    def __init__(self, network=None, name="None"):
897        if network is None:
898            network = Orange.core.Network(2, 0)
899           
900        self.setGraph(network)
901        self.graph = network
902       
903        self.maxWidth = 1000
904        self.maxHeight = 1000
905       
906        self.attributeList = {}
907        self.attributeValues = {}
908        self.vertexDistance = None
909        self.mds = None
910       
911    def setNetwork(network):
912        """Set the network object for layout optimization.
913   
914        :param network: network object for layout optimization
915        :type network: Orange.network.Network
916       
917        """
918        self.setGraph(network)
919       
920    def _computeForces(self):
921        """Compute forces for each vertex for force vector visualization."""
922        n = self.graph.nVertices
923        vertices = set(range(n))
924        e_avg = 0
925        edges = self.graph.getEdges()
926        for u,v in edges:
927            u_ = numpy.array([self.graph.coors[0][u], self.graph.coors[1][u]])
928            v_ = numpy.array([self.graph.coors[0][v], self.graph.coors[1][v]])
929            e_avg += numpy.linalg.norm(u_ - v_)
930        e_avg /= len(edges)
931       
932        forces = []
933        maxforce = []
934        components = self.graph.getConnectedComponents()
935        for component in components:
936            outer_vertices = vertices - set(component)
937           
938            for u in component:
939                u_ = numpy.array([self.graph.coors[0][u], 
940                                  self.graph.coors[1][u]])
941                force = numpy.array([0.0, 0.0])               
942                for v in outer_vertices:
943                    v_ = numpy.array([self.graph.coors[0][v], 
944                                      self.graph.coors[1][v]])
945                    d = self.vertexDistance[u, v]
946                    norm = numpy.linalg.norm(v_ - u_)
947                    force += (d - norm) * (v_ - u_) / norm
948           
949                forces.append(force)
950                maxforce.append(numpy.linalg.norm(force))
951           
952        maxforce = max(maxforce)
953        rv = []
954        for v in range(n):
955            force = forces[v]
956            v_ = numpy.array([self.graph.coors[0][v], self.graph.coors[1][v]])
957            f = force * e_avg / maxforce
958            rv.append(([v_[0], v_[0] + f[0]],[v_[1], v_[1] + f[1]]))
959
960        return rv
961   
962    def collapse(self):
963        """Experimental method to group cliques to meta nodes."""
964        if len(self.graph.getNodes(1)) > 0:
965            nodes = list(set(range(self.graph.nVertices)) - \
966                         set(self.graph.getNodes(1)))
967               
968            if len(nodes) > 0:
969                subgraph = Orange.core.Network(self.graph.getSubGraph(nodes))
970                oldcoors = self.coors
971                self.setGraph(subgraph)
972                self.graph = subgraph
973                   
974                for i in range(len(nodes)):
975                    self.coors[0][i] = oldcoors[0][nodes[i]]
976                    self.coors[1][i] = oldcoors[1][nodes[i]]
977
978        else:
979            fullgraphs = self.graph.getLargestFullGraphs()
980            subgraph = self.graph
981           
982            if len(fullgraphs) > 0:
983                used = set()
984                graphstomerge = list()
985                #print fullgraphs
986                for fullgraph in fullgraphs:
987                    #print fullgraph
988                    fullgraph_set = set(fullgraph)
989                    if len(used & fullgraph_set) == 0:
990                        graphstomerge.append(fullgraph)
991                        used |= fullgraph_set
992                       
993                #print graphstomerge
994                #print used
995                subgraph = Orange.core.Network(
996                            subgraph.getSubGraphMergeClusters(graphstomerge))
997                                   
998                nodescomp = list(set(range(self.graph.nVertices)) - used)
999               
1000                #subgraph.setattr("items", self.graph.items.getitems(nodescomp))
1001                #subgraph.items.append(self.graph.items[0])
1002                oldcoors = self.coors
1003                self.setGraph(subgraph)
1004                self.graph = subgraph
1005                for i in range(len(nodescomp)):
1006                    self.coors[0][i] = oldcoors[0][nodescomp[i]]
1007                    self.coors[1][i] = oldcoors[1][nodescomp[i]]
1008                   
1009                # place meta vertex in center of cluster   
1010                x, y = 0, 0
1011                for node in used:
1012                    x += oldcoors[0][node]
1013                    y += oldcoors[1][node]
1014                   
1015                x = x / len(used)
1016                y = y / len(used)
1017               
1018                self.coors[0][len(nodescomp)] = x
1019                self.coors[1][len(nodescomp)] = y
1020           
1021    def getVars(self):
1022        """Return a list of features in network items."""
1023        vars = []
1024        if (self.graph != None):
1025            if hasattr(self.graph, "items"):
1026                if isinstance(self.graph.items, Orange.data.Table):
1027                    vars[:0] = self.graph.items.domain.variables
1028               
1029                    metas = self.graph.items.domain.getmetas(0)
1030                    for i, var in metas.iteritems():
1031                        vars.append(var)
1032        return vars
1033   
1034    def getEdgeVars(self):
1035        """Return a list of features in network links."""
1036        vars = []
1037        if (self.graph != None):
1038            if hasattr(self.graph, "links"):
1039                if isinstance(self.graph.links, Orange.data.Table):
1040                    vars[:0] = self.graph.links.domain.variables
1041               
1042                    metas = self.graph.links.domain.getmetas(0)
1043                    for i, var in metas.iteritems():
1044                        vars.append(var)
1045                       
1046        return [x for x in vars if str(x.name) != 'u' and str(x.name) != 'v']
1047   
1048    def getData(self, i, j):
1049        import warnings
1050        warnings.warn("Deprecated.", DeprecationWarning)
1051        if self.graph.items is Orange.data.Table:
1052            return self.data[i][j]
1053        elif self.graph.data is type([]):
1054            return self.data[i][j]
1055       
1056    def nVertices(self):
1057        import warnings
1058        warnings.warn("Deprecated.", DeprecationWarning)
1059        if self.graph:
1060            return self.graph.nVertices
1061       
1062    def rotateVertices(self, components, phi): 
1063        """Rotate network components for a given angle.
1064       
1065        :param components: list of network components
1066        :type components: list of lists of vertex indices
1067        :param phi: list of component rotation angles (unit: radians)
1068        """ 
1069        #print phi
1070        for i in range(len(components)):
1071            if phi[i] == 0:
1072                continue
1073           
1074            component = components[i]
1075           
1076            x = self.graph.coors[0][component]
1077            y = self.graph.coors[1][component]
1078           
1079            x_center = x.mean()
1080            y_center = y.mean()
1081           
1082            x = x - x_center
1083            y = y - y_center
1084           
1085            r = numpy.sqrt(x ** 2 + y ** 2)
1086            fi = numpy.arctan2(y, x)
1087           
1088            fi += phi[i]
1089            #fi += factor * M[i] * numpy.pi / 180
1090               
1091            x = r * numpy.cos(fi)
1092            y = r * numpy.sin(fi)
1093           
1094            self.graph.coors[0][component] = x + x_center
1095            self.graph.coors[1][component] = y + y_center
1096           
1097    def rotateComponents(self, maxSteps=100, minMoment=0.000000001, 
1098                         callbackProgress=None, callbackUpdateCanvas=None):
1099        """Rotate the network components using a spring model."""
1100        if self.vertexDistance == None:
1101            return 1
1102       
1103        if self.graph == None:
1104            return 1
1105       
1106        if self.vertexDistance.dim != self.graph.nVertices:
1107            return 1
1108       
1109        self.stopRotate = 0
1110       
1111        # rotate only components with more than one vertex
1112        components = [component for component \
1113                      in self.graph.getConnectedComponents() \
1114                      if len(component) > 1]
1115        vertices = set(range(self.graph.nVertices))
1116        step = 0
1117        M = [1]
1118        temperature = [[30.0, 1] for i in range(len(components))]
1119        dirChange = [0] * len(components)
1120        while step < maxSteps and (max(M) > minMoment or min(M) < -minMoment) \
1121                                                     and not self.stopRotate:
1122            M = [0] * len(components) 
1123           
1124            for i in range(len(components)):
1125                component = components[i]
1126               
1127                outer_vertices = vertices - set(component)
1128               
1129                x = self.graph.coors[0][component]
1130                y = self.graph.coors[1][component]
1131               
1132                x_center = x.mean()
1133                y_center = y.mean()
1134               
1135                for j in range(len(component)):
1136                    u = component[j]
1137
1138                    for v in outer_vertices:
1139                        d = self.vertexDistance[u, v]
1140                        u_x = self.graph.coors[0][u]
1141                        u_y = self.graph.coors[1][u]
1142                        v_x = self.graph.coors[0][v]
1143                        v_y = self.graph.coors[1][v]
1144                        L = [(u_x - v_x), (u_y - v_y)]
1145                        R = [(u_x - x_center), (u_y - y_center)]
1146                        e = math.sqrt((v_x - x_center) ** 2 + \
1147                                      (v_y - y_center) ** 2)
1148                       
1149                        M[i] += (1 - d) / (e ** 2) * numpy.cross(R, L)
1150           
1151            tmpM = numpy.array(M)
1152            #print numpy.min(tmpM), numpy.max(tmpM),numpy.average(tmpM),numpy.min(numpy.abs(tmpM))
1153           
1154            phi = [0] * len(components)
1155            #print "rotating", temperature, M
1156            for i in range(len(M)):
1157                if M[i] > 0:
1158                    if temperature[i][1] < 0:
1159                        temperature[i][0] = temperature[i][0] * 5 / 10
1160                        temperature[i][1] = 1
1161                        dirChange[i] += 1
1162                       
1163                    phi[i] = temperature[i][0] * numpy.pi / 180
1164                elif M[i] < 0: 
1165                    if temperature[i][1] > 0:
1166                        temperature[i][0] = temperature[i][0] * 5 / 10
1167                        temperature[i][1] = -1
1168                        dirChange[i] += 1
1169                   
1170                    phi[i] = -temperature[i][0] * numpy.pi / 180
1171           
1172            # stop rotating when phi is to small to notice the rotation
1173            if max(phi) < numpy.pi / 1800:
1174                #print "breaking"
1175                break
1176           
1177            self.rotateVertices(components, phi)
1178            if callbackUpdateCanvas: callbackUpdateCanvas()
1179            if callbackProgress : callbackProgress(min([dirChange[i] for i \
1180                                    in range(len(dirChange)) if M[i] != 0]), 9)
1181            step += 1
1182   
1183    def mdsUpdateData(self, components, mds, callbackUpdateCanvas):
1184        """Translate and rotate the network components to computed positions."""
1185        component_props = []
1186        x_mds = []
1187        y_mds = []
1188        phi = [None] * len(components)
1189        self.diag_coors = math.sqrt(( \
1190                    min(self.graph.coors[0]) - max(self.graph.coors[0]))**2 + \
1191                    (min(self.graph.coors[1]) - max(self.graph.coors[1]))**2)
1192       
1193        if self.mdsType == MdsType.MDS:
1194            x = [mds.points[u][0] for u in range(self.graph.nVertices)]
1195            y = [mds.points[u][1] for u in range(self.graph.nVertices)]
1196            self.graph.coors[0][range(self.graph.nVertices)] =  x
1197            self.graph.coors[1][range(self.graph.nVertices)] =  y
1198            if callbackUpdateCanvas:
1199                callbackUpdateCanvas()
1200            return
1201       
1202        for i in range(len(components)):   
1203            component = components[i]
1204           
1205            if len(mds.points) == len(components):  # if average linkage before
1206                x_avg_mds = mds.points[i][0]
1207                y_avg_mds = mds.points[i][1]
1208            else:                                   # if not average linkage before
1209                x = [mds.points[u][0] for u in component]
1210                y = [mds.points[u][1] for u in component]
1211       
1212                x_avg_mds = sum(x) / len(x) 
1213                y_avg_mds = sum(y) / len(y)
1214                # compute rotation angle
1215                c = [numpy.linalg.norm(numpy.cross(mds.points[u], \
1216                            [self.graph.coors[0][u],self.graph.coors[1][u]])) \
1217                            for u in component]
1218                n = [numpy.vdot([self.graph.coors[0][u], \
1219                                 self.graph.coors[1][u]], \
1220                                 [self.graph.coors[0][u], \
1221                                  self.graph.coors[1][u]]) for u in component]
1222                phi[i] = sum(c) / sum(n)
1223                #print phi
1224           
1225            x = self.graph.coors[0][component]
1226            y = self.graph.coors[1][component]
1227           
1228            x_avg_graph = sum(x) / len(x)
1229            y_avg_graph = sum(y) / len(y)
1230           
1231            x_mds.append(x_avg_mds) 
1232            y_mds.append(y_avg_mds)
1233
1234            component_props.append((x_avg_graph, y_avg_graph, \
1235                                    x_avg_mds, y_avg_mds, phi))
1236       
1237        w = max(self.graph.coors[0]) - min(self.graph.coors[0])
1238        h = max(self.graph.coors[1]) - min(self.graph.coors[1])
1239        d = math.sqrt(w**2 + h**2)
1240        #d = math.sqrt(w*h)
1241        e = [math.sqrt((self.graph.coors[0][u] - self.graph.coors[0][v])**2 + 
1242                  (self.graph.coors[1][u] - self.graph.coors[1][v])**2) for 
1243                  (u, v) in self.graph.getEdges()]
1244       
1245        if self.scalingRatio == 0:
1246            pass
1247        elif self.scalingRatio == 1:
1248            self.mdsScaleRatio = d
1249        elif self.scalingRatio == 2:
1250            self.mdsScaleRatio = d / sum(e) * float(len(e))
1251        elif self.scalingRatio == 3:
1252            self.mdsScaleRatio = 1 / sum(e) * float(len(e))
1253        elif self.scalingRatio == 4:
1254            self.mdsScaleRatio = w * h
1255        elif self.scalingRatio == 5:
1256            self.mdsScaleRatio = math.sqrt(w * h)
1257        elif self.scalingRatio == 6:
1258            self.mdsScaleRatio = 1
1259        elif self.scalingRatio == 7:
1260            e_fr = 0
1261            e_count = 0
1262            for i in range(self.graph.nVertices):
1263                for j in range(i + 1, self.graph.nVertices):
1264                    x1 = self.graph.coors[0][i]
1265                    y1 = self.graph.coors[1][i]
1266                    x2 = self.graph.coors[0][j]
1267                    y2 = self.graph.coors[1][j]
1268                    e_fr += math.sqrt((x1-x2)**2 + (y1-y2)**2)
1269                    e_count += 1
1270            self.mdsScaleRatio = e_fr / e_count
1271        elif self.scalingRatio == 8:
1272            e_fr = 0
1273            e_count = 0
1274            for i in range(len(components)):
1275                for j in range(i + 1, len(components)):
1276                    x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, \
1277                    y_avg_mds_i, phi_i = component_props[i]
1278                    x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, \
1279                    y_avg_mds_j, phi_j = component_props[j]
1280                    e_fr += math.sqrt((x_avg_graph_i-x_avg_graph_j)**2 + \
1281                                      (y_avg_graph_i-y_avg_graph_j)**2)
1282                    e_count += 1
1283            self.mdsScaleRatio = e_fr / e_count       
1284        elif self.scalingRatio == 9:
1285            e_fr = 0
1286            e_count = 0
1287            for i in range(len(components)):   
1288                component = components[i]
1289                x = self.graph.coors[0][component]
1290                y = self.graph.coors[1][component]
1291                for i in range(len(x)):
1292                    for j in range(i + 1, len(y)):
1293                        x1 = x[i]
1294                        y1 = y[i]
1295                        x2 = x[j]
1296                        y2 = y[j]
1297                        e_fr += math.sqrt((x1-x2)**2 + (y1-y2)**2)
1298                        e_count += 1
1299            self.mdsScaleRatio = e_fr / e_count
1300       
1301        diag_mds =  math.sqrt((max(x_mds) - min(x_mds))**2 + (max(y_mds) - \
1302                                                              min(y_mds))**2)
1303        e = [math.sqrt((self.graph.coors[0][u] - self.graph.coors[0][v])**2 + 
1304                  (self.graph.coors[1][u] - self.graph.coors[1][v])**2) for 
1305                  (u, v) in self.graph.getEdges()]
1306        e = sum(e) / float(len(e))
1307       
1308        x = [mds.points[u][0] for u in range(len(mds.points))]
1309        y = [mds.points[u][1] for u in range(len(mds.points))]
1310        w = max(x) - min(x)
1311        h = max(y) - min(y)
1312        d = math.sqrt(w**2 + h**2)
1313       
1314        if len(x) == 1:
1315            r = 1
1316        else:
1317            if self.scalingRatio == 0:
1318                r = self.mdsScaleRatio / d * e
1319            elif self.scalingRatio == 1:
1320                r = self.mdsScaleRatio / d
1321            elif self.scalingRatio == 2:
1322                r = self.mdsScaleRatio / d * e
1323            elif self.scalingRatio == 3:
1324                r = self.mdsScaleRatio * e
1325            elif self.scalingRatio == 4:
1326                r = self.mdsScaleRatio / (w * h)
1327            elif self.scalingRatio == 5:
1328                r = self.mdsScaleRatio / math.sqrt(w * h)
1329            elif self.scalingRatio == 6:
1330                r = 1 / math.sqrt(self.graph.nVertices)
1331            elif self.scalingRatio == 7:
1332                e_mds = 0
1333                e_count = 0
1334                for i in range(len(mds.points)):
1335                    for j in range(i):
1336                        x1 = mds.points[i][0]
1337                        y1 = mds.points[i][1]
1338                        x2 = mds.points[j][0]
1339                        y2 = mds.points[j][1]
1340                        e_mds += math.sqrt((x1-x2)**2 + (y1-y2)**2)
1341                        e_count += 1
1342                r = self.mdsScaleRatio / e_mds * e_count
1343            elif self.scalingRatio == 8:
1344                e_mds = 0
1345                e_count = 0
1346                for i in range(len(components)):
1347                    for j in range(i + 1, len(components)):
1348                        x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, \
1349                        y_avg_mds_i, phi_i = component_props[i]
1350                        x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, \
1351                        y_avg_mds_j, phi_j = component_props[j]
1352                        e_mds += math.sqrt((x_avg_mds_i-x_avg_mds_j)**2 + \
1353                                           (y_avg_mds_i-y_avg_mds_j)**2)
1354                        e_count += 1
1355                r = self.mdsScaleRatio / e_mds * e_count
1356            elif self.scalingRatio == 9:
1357                e_mds = 0
1358                e_count = 0
1359                for i in range(len(mds.points)):
1360                    for j in range(i):
1361                        x1 = mds.points[i][0]
1362                        y1 = mds.points[i][1]
1363                        x2 = mds.points[j][0]
1364                        y2 = mds.points[j][1]
1365                        e_mds += math.sqrt((x1-x2)**2 + (y1-y2)**2)
1366                        e_count += 1
1367                r = self.mdsScaleRatio / e_mds * e_count
1368               
1369            #r = self.mdsScaleRatio / d
1370            #print "d", d, "r", r
1371            #r = self.mdsScaleRatio / math.sqrt(self.graph.nVertices)
1372           
1373        for i in range(len(components)):
1374            component = components[i]
1375            x_avg_graph, y_avg_graph, x_avg_mds, \
1376            y_avg_mds, phi = component_props[i]
1377           
1378#            if phi[i]:  # rotate vertices
1379#                #print "rotate", i, phi[i]
1380#                r = numpy.array([[numpy.cos(phi[i]), -numpy.sin(phi[i])], [numpy.sin(phi[i]), numpy.cos(phi[i])]])  #rotation matrix
1381#                c = [x_avg_graph, y_avg_graph]  # center of mass in FR coordinate system
1382#                v = [numpy.dot(numpy.array([self.graph.coors[0][u], self.graph.coors[1][u]]) - c, r) + c for u in component]
1383#                self.graph.coors[0][component] = [u[0] for u in v]
1384#                self.graph.coors[1][component] = [u[1] for u in v]
1385               
1386            # translate vertices
1387            if not self.rotationOnly:
1388                self.graph.coors[0][component] = \
1389                (self.graph.coors[0][component] - x_avg_graph) / r + x_avg_mds
1390                self.graph.coors[1][component] = \
1391                (self.graph.coors[1][component] - y_avg_graph) / r + y_avg_mds
1392               
1393        if callbackUpdateCanvas:
1394            callbackUpdateCanvas()
1395   
1396    def mdsCallback(self, a,b=None):
1397        """Refresh the UI when running  MDS on network components."""
1398        if not self.mdsStep % self.mdsRefresh:
1399            self.mdsUpdateData(self.mdsComponents, 
1400                               self.mds, 
1401                               self.callbackUpdateCanvas)
1402           
1403            if self.mdsType == MdsType.exactSimulation:
1404                self.mds.points = [[self.graph.coors[0][i], \
1405                                    self.graph.coors[1][i]] \
1406                                    for i in range(len(self.graph.coors))]
1407                self.mds.freshD = 0
1408           
1409            if self.callbackProgress != None:
1410                self.callbackProgress(self.mds.avgStress, self.mdsStep)
1411               
1412        self.mdsStep += 1
1413
1414        if self.stopMDS:
1415            return 0
1416        else:
1417            return 1
1418           
1419    def mdsComponents(self, mdsSteps, mdsRefresh, callbackProgress=None, \
1420                      callbackUpdateCanvas=None, torgerson=0, \
1421                      minStressDelta=0, avgLinkage=False, rotationOnly=False, \
1422                      mdsType=MdsType.componentMDS, scalingRatio=0, \
1423                      mdsFromCurrentPos=0):
1424        """Position the network components according to similarities among
1425        them.
1426       
1427        """
1428
1429        if self.vertexDistance == None:
1430            self.information('Set distance matrix to input signal')
1431            return 1
1432       
1433        if self.graph == None:
1434            return 1
1435       
1436        if self.vertexDistance.dim != self.graph.nVertices:
1437            return 1
1438       
1439        self.mdsComponents = self.graph.getConnectedComponents()
1440        self.mdsRefresh = mdsRefresh
1441        self.mdsStep = 0
1442        self.stopMDS = 0
1443        self.vertexDistance.matrixType = Orange.core.SymMatrix.Symmetric
1444        self.diag_coors = math.sqrt((min(self.graph.coors[0]) -  \
1445                                     max(self.graph.coors[0]))**2 + \
1446                                     (min(self.graph.coors[1]) - \
1447                                      max(self.graph.coors[1]))**2)
1448        self.rotationOnly = rotationOnly
1449        self.mdsType = mdsType
1450        self.scalingRatio = scalingRatio
1451
1452        w = max(self.graph.coors[0]) - min(self.graph.coors[0])
1453        h = max(self.graph.coors[1]) - min(self.graph.coors[1])
1454        d = math.sqrt(w**2 + h**2)
1455        #d = math.sqrt(w*h)
1456        e = [math.sqrt((self.graph.coors[0][u] - self.graph.coors[0][v])**2 + 
1457                  (self.graph.coors[1][u] - self.graph.coors[1][v])**2) for 
1458                  (u, v) in self.graph.getEdges()]
1459        self.mdsScaleRatio = d / sum(e) * float(len(e))
1460        #print d / sum(e) * float(len(e))
1461       
1462        if avgLinkage:
1463            matrix = self.vertexDistance.avgLinkage(self.mdsComponents)
1464        else:
1465            matrix = self.vertexDistance
1466       
1467        #if self.mds == None:
1468        self.mds = Orange.projection.mds.MDS(matrix)
1469       
1470        if mdsFromCurrentPos:
1471            if avgLinkage:
1472                for u, c in enumerate(self.mdsComponents):
1473                    x = sum(self.graph.coors[0][c]) / len(c)
1474                    y = sum(self.graph.coors[1][c]) / len(c)
1475                    self.mds.points[u][0] = x
1476                    self.mds.points[u][1] = y
1477            else:
1478                for u in range(self.graph.nVertices):
1479                    self.mds.points[u][0] = self.graph.coors[0][u] 
1480                    self.mds.points[u][1] = self.graph.coors[1][u]
1481           
1482        # set min stress difference between 0.01 and 0.00001
1483        self.minStressDelta = minStressDelta
1484        self.callbackUpdateCanvas = callbackUpdateCanvas
1485        self.callbackProgress = callbackProgress
1486       
1487        if torgerson:
1488            self.mds.Torgerson() 
1489
1490        self.mds.optimize(mdsSteps, Orange.projection.mds.SgnRelStress, self.minStressDelta,\
1491                          progressCallback=self.mdsCallback)
1492        self.mdsUpdateData(self.mdsComponents, self.mds, callbackUpdateCanvas)
1493       
1494        if callbackProgress != None:
1495            callbackProgress(self.mds.avgStress, self.mdsStep)
1496       
1497        del self.rotationOnly
1498        del self.diag_coors
1499        del self.mdsRefresh
1500        del self.mdsStep
1501        #del self.mds
1502        del self.mdsComponents
1503        del self.minStressDelta
1504        del self.callbackUpdateCanvas
1505        del self.callbackProgress
1506        del self.mdsType
1507        del self.mdsScaleRatio
1508        del self.scalingRatio
1509        return 0
1510
1511    def mdsComponentsAvgLinkage(self, mdsSteps, mdsRefresh, \
1512                                callbackProgress=None, \
1513                                callbackUpdateCanvas=None, torgerson=0, \
1514                                minStressDelta = 0, scalingRatio=0,\
1515                                mdsFromCurrentPos=0):
1516        return self.mdsComponents(mdsSteps, mdsRefresh, callbackProgress, \
1517                                  callbackUpdateCanvas, torgerson, \
1518                                  minStressDelta, True, \
1519                                  scalingRatio=scalingRatio, \
1520                                  mdsFromCurrentPos=mdsFromCurrentPos)
1521
1522    def saveNetwork(self, fn):
1523        import warnings
1524        warnings.warn("Deprecated. Use Orange.network.Network.save", 
1525                      DeprecationWarning)
1526        name = ''
1527        try:
1528            root, ext = os.path.splitext(fn)
1529            if ext == '':
1530                fn = root + '.net'
1531           
1532            graphFile = file(fn, 'w+')
1533        except IOError:
1534            return 1
1535
1536        graphFile.write('### Generated with Orange.network ### \n\n\n')
1537        if name == '':
1538            graphFile.write('*Network ' + '"no name" \n\n')
1539        else:
1540            graphFile.write('*Network ' + str(name) + ' \n\n')
1541
1542
1543        #izpis opisov vozlisc
1544        print "e", self.graph.nEdgeTypes
1545        graphFile.write('*Vertices %8d %8d\n' % (self.graph.nVertices, \
1546                                                 self.graph.nEdgeTypes))
1547        for v in range(self.graph.nVertices):
1548            graphFile.write('% 8d ' % (v + 1))
1549#            if verticesParms[v].label!='':
1550#                self.GraphFile.write(str('"'+ verticesParms[v].label + '"') + ' \t')
1551#            else:
1552            try:
1553                label = self.graph.items[v]['label']
1554                graphFile.write(str('"' + str(label) + '"') + ' \t')
1555            except:
1556                graphFile.write(str('"' + str(v) + '"') + ' \t')
1557           
1558            x = self.network.coors[0][v]
1559            y = self.network.coors[1][v]
1560            #if x < 0: x = 0
1561            #if x >= 1: x = 0.9999
1562            #if y < 0: y = 0
1563            #if y >= 1: y = 0.9999
1564            z = 0.5000
1565            graphFile.write('%.4f    %.4f    %.4f\t' % (x, y, z))
1566            graphFile.write('\n')
1567
1568        #izpis opisov povezav
1569        #najprej neusmerjene
1570        if self.graph.directed:
1571            graphFile.write('*Arcs \n')
1572            for (i, j) in self.graph.getEdges():
1573                if len(self.graph[i, j]) > 0:
1574                    graphFile.write('%8d %8d %f' % (i + 1, j + 1, \
1575                                                float(str(self.graph[i, j]))))
1576                    graphFile.write('\n')
1577        else:
1578            graphFile.write('*Edges \n')
1579            for (i, j) in self.graph.getEdges():
1580                if len(self.graph[i, j]) > 0:
1581                    graphFile.write('%8d %8d %f' % (i + 1, j + 1, \
1582                                                float(str(self.graph[i, j]))))
1583                    graphFile.write('\n')
1584
1585        graphFile.write('\n')
1586        graphFile.close()
1587       
1588        if self.graph.items != None and len(self.graph.items) > 0:
1589            (name, ext) = os.path.splitext(fn)
1590            self.graph.items.save(name + "_items.tab")
1591           
1592        if self.graph.links != None and len(self.graph.links) > 0:
1593            (name, ext) = os.path.splitext(fn)
1594            self.graph.links.save(name + "_links.tab")
1595
1596        return 0
1597   
1598    def readNetwork(self, fn, directed=0):
1599        import warnings
1600        warnings.warn("Deprecated. Use Orange.network.Network.read", 
1601                      DeprecationWarning)
1602        network = Network(1,directed)
1603        net = network.readPajek(fn, directed)
1604        self.setGraph(net)
1605        self.graph = net
1606        return net
1607   
1608class NetworkClustering():
1609   
1610    """A collection of algorithms for community detection in graphs.
1611   
1612    :param network: network data for community detection
1613    :type network: Orange.network.Network
1614    """ 
1615   
1616    random.seed(0)
1617   
1618    def __init__(self, network):
1619        self.net = network
1620       
1621       
1622    def labelPropagation(self, results2items=0, resultHistory2items=0):
1623        """Label propagation method from Raghavan et al., 2007
1624       
1625        :param results2items: append a new feature result to items
1626            (Orange.data.Table)
1627        :type results2items: bool
1628        :param resultHistory2items: append new features result to items
1629            (Orange.data.Table) after each iteration of the algorithm
1630        :type resultHistory2items: bool
1631        """
1632       
1633        vertices = range(self.net.nVertices)
1634        labels = range(self.net.nVertices)
1635        lblhistory = []
1636        #consecutiveStop = 0
1637        for i in range(1000):
1638            random.shuffle(vertices)
1639            stop = 1
1640            for v in vertices:
1641                nbh = self.net.getNeighbours(v)
1642                if len(nbh) == 0:
1643                    continue
1644               
1645                lbls = [labels[u] for u in nbh]
1646                lbls = [(len(list(c)), l) for l, c in itertools.groupby(lbls)]
1647                m = max(lbls)[0]
1648                mlbls = [l for c, l in lbls if c >= m]
1649                lbl = random.choice(mlbls)
1650               
1651                if labels[v] not in mlbls: stop = 0
1652                labels[v] = lbl
1653               
1654            lblhistory.append([str(l) for l in labels])
1655            # if stopping condition might be satisfied, check it
1656            if stop:
1657                for v in vertices:
1658                    nbh = self.net.getNeighbours(v)
1659                    if len(nbh) == 0: continue
1660                    lbls = [labels[u] for u in nbh]
1661                    lbls = [(len(list(c)), l) for l, c \
1662                            in itertools.groupby(lbls)]
1663                    m = max(lbls)[0]
1664                    mlbls = [l for c, l in lbls if c >= m]
1665                    if labels[v] not in mlbls: 
1666                        stop = 0
1667                        break
1668                if stop: break
1669                   
1670        if results2items and not resultHistory2items:
1671            attrs = [Orange.data.variable.Discrete(
1672                                        'clustering label propagation',
1673                                        values=list(set([l for l \
1674                                                        in lblhistory[-1]])))]
1675            dom = Orange.data.Domain(attrs, 0)
1676            data = Orange.data.Table(dom, [[l] for l in lblhistory[-1]])
1677            if self.net.items is None:
1678                self.net.items = data 
1679            else: 
1680                self.net.items = Orange.data.Table([self.net.items, data])
1681        if resultHistory2items:
1682            attrs = [Orange.data.variable.Discrete('c'+ str(i),
1683                values=list(set([l for l in lblhistory[0]]))) for i,labels \
1684                in enumerate(lblhistory)]
1685            dom = Orange.data.Domain(attrs, 0)
1686            # transpose history
1687            data = map(list, zip(*lblhistory))
1688            data = Orange.data.Table(dom, data)
1689            if self.net.items is None:
1690                self.net.items = data 
1691            else: 
1692                self.net.items = Orange.data.Table([self.net.items, data])
1693
1694        return labels
1695   
1696   
Note: See TracBrowser for help on using the repository browser.