Changeset 7999:72b0ec873850 in orange


Ignore:
Timestamp:
06/13/11 15:11:15 (3 years ago)
Author:
miha <miha.stajdohar@…>
Branch:
default
Convert:
9c5111e16ee24c529791962f544fcf3121be8447
Message:

New network documentation.

Location:
orange/Orange/network
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed
  • orange/Orange/network/__init__.py

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

    r7972 r7999  
     1"""  
     2.. index:: community detection in graphs 
     3 
     4.. index:: 
     5   single: network; community detection in graphs 
     6 
     7***************************** 
     8Community detection in graphs 
     9***************************** 
     10 
     11""" 
     12 
    113import random 
    214import itertools 
  • orange/Orange/network/network.py

    r7971 r7999  
    2121MdsType = MdsTypeClass() 
    2222 
    23  
    2423class BaseGraph(): 
     24    """A collection of methods inherited by all graph types (:obj:`Graph`,  
     25    :obj:`DiGraph`, :obj:`MultiGraph` and :obj:`MultiDiGraph`). 
     26     
     27    """ 
    2528     
    2629    def __init__(self): 
     
    2932         
    3033    def items(self): 
     34        """Return the :obj:`Orange.data.Table` items with data about network  
     35        nodes. 
     36         
     37        """ 
     38          
    3139        if self._items is not None and \ 
    3240                        len(self._items) != self.number_of_nodes(): 
     
    3644     
    3745    def set_items(self, items=None): 
     46        """Set the :obj:`Orange.data.Table` items to the given data. Notice  
     47        that the number of instances must match the number of nodes. 
     48         
     49        """ 
     50         
    3851        if items is not None: 
    3952            if not isinstance(items, Orange.data.Table): 
     
    4558         
    4659    def links(self): 
     60        """Return the :obj:`Orange.data.Table` links with data about network  
     61        edges. 
     62         
     63        """ 
     64         
    4765        if self._links is not None \ 
    4866                    and len(self._links) != self.number_of_edges(): 
     
    5270     
    5371    def set_links(self, links=None): 
     72        """Set the :obj:`Orange.data.Table` links to the given data. Notice  
     73        that the number of instances must match the number of edges. 
     74         
     75        """ 
     76         
    5477        if links is not None: 
    5578            if not isinstance(links, Orange.data.Table): 
     
    6184         
    6285    def to_orange_network(self): 
    63         """Convert the network to Orange NetworkX standard. All node IDs are transformed to range [0, no_of_nodes - 1]."""  
    64         if isinstance(self, Orange.network.Graph): 
    65             G = Orange.network.Graph() 
    66         elif isinstance(self, Orange.network.DiGraph): 
    67             G = Orange.network.DiGraph() 
    68         elif isinstance(self, Orange.network.MultiGraph): 
    69             G = Orange.network.MultiGraph() 
    70         elif isinstance(self, Orange.network.MultiDiGraph): 
    71             G = Orange.network.DiGraph() 
    72         else: 
    73             raise TypeError('WTF!?') 
    74          
     86        """Convert the current network to >>Orange<< NetworkX standard. To use 
     87        :obj:`Orange.network` in Orange widgets, set node IDs to be range  
     88        [0, no_of_nodes - 1]. 
     89         
     90        """  
     91         
     92        G = self.__class__() 
    7593        node_list = sorted(self.nodes()) 
    7694        node_to_index = dict(zip(node_list, range(self.number_of_nodes()))) 
     
    94112     
    95113    def items_vars(self): 
    96         """Return a list of features in network items.""" 
     114        """Return a list of features in the :obj:`Orange.data.Table` items.""" 
     115         
    97116        vars = [] 
    98117        if (self._items is not None): 
     
    105124     
    106125    def links_vars(self): 
    107         """Return a list of features in network links.""" 
     126        """Return a list of features in the :obj:`Orange.data.Table` links.""" 
     127         
    108128        vars = [] 
    109129        if (self._links is not None): 
     
    116136     
    117137class Graph(BaseGraph, nx.Graph): 
     138    """Bases: `NetworkX.Graph <http://networkx.lanl.gov/reference/classes.graph.html>`_,  
     139    :obj:`Orange.network.BaseGraph`  
     140     
     141    """ 
    118142     
    119143    def __init__(self, data=None, name='', **attr):   
    120144        nx.Graph.__init__(self, data, name, **attr) 
    121145        BaseGraph.__init__(self) 
    122          
     146     
     147    __doc__ += nx.Graph.__doc__ 
    123148    __init__.__doc__ = nx.Graph.__init__.__doc__ 
    124149      
    125150class DiGraph(BaseGraph, nx.DiGraph): 
     151    """Bases: `NetworkX.DiGraph <http://networkx.lanl.gov/reference/classes.digraph.html>`_,  
     152    :obj:`Orange.network.BaseGraph`  
     153     
     154    """ 
     155     
    126156     
    127157    def __init__(self, data=None, name='', **attr): 
    128158        nx.DiGraph.__init__(self, data, name, **attr) 
    129159        BaseGraph.__init__(self) 
    130          
     160     
     161    __doc__ += nx.Graph.__doc__ 
    131162    __init__.__doc__ = nx.DiGraph.__init__.__doc__ 
    132163      
    133164class MultiGraph(BaseGraph, nx.MultiGraph): 
     165    """Bases: `NetworkX.MultiGraph <http://networkx.lanl.gov/reference/classes.multigraph.html>`_,  
     166    :obj:`Orange.network.BaseGraph`  
     167     
     168    """ 
     169     
    134170     
    135171    def __init__(self, data=None, name='', **attr): 
     
    137173        BaseGraph.__init__(self) 
    138174         
     175    __doc__ += nx.Graph.__doc__ 
    139176    __init__.__doc__ = nx.MultiGraph.__init__.__doc__ 
    140177      
    141178class MultiDiGraph(BaseGraph, nx.MultiDiGraph): 
     179    """Bases: `NetworkX.MultiDiGraph <http://networkx.lanl.gov/reference/classes.multidigraph.html>`_,  
     180    :obj:`Orange.network.BaseGraph`  
     181     
     182    """ 
     183     
    142184     
    143185    def __init__(self, data=None, name='', **attr): 
    144186        nx.MultiDiGraph.__init__(self, data, name, **attr) 
    145187        BaseGraph.__init__(self) 
    146          
     188     
     189    __doc__ += nx.Graph.__doc__     
    147190    __init__.__doc__ = nx.MultiDiGraph.__init__.__doc__ 
    148191 
    149192class GraphLayout(orangeom.GraphLayout): 
    150      
    151     """A graph layout optimization class.""" 
     193    """A graph layout optimization class. 
     194     
     195    """ 
    152196     
    153197    def __init__(self): 
  • orange/Orange/network/readwrite.py

    r7970 r7999  
     1"""  
     2.. index:: reading and writing networks 
     3 
     4.. index:: 
     5   single: network; reading and writing networks 
     6 
     7**************************** 
     8Reading and writing networks 
     9**************************** 
     10 
     11 
     12 
     13""" 
     14 
    115import os.path 
    216import warnings 
     
    1125import Orange.network 
    1226 
    13 __all__ = ['read', 'generate_pajek', 'write_pajek', 'read_pajek', 'parse_pajek'] 
     27__all__ = ['read', 'write', 'read_gpickle', 'write_gpickle', 'read_pajek',  
     28           'write_pajek', 'parse_pajek', 'read_gml', 'write_gml'] 
    1429 
    1530def _wrap(g): 
Note: See TracChangeset for help on using the changeset viewer.