#
source:
orange/Orange/network/deprecated.py
@
9671:a7b056375472

Revision 9671:a7b056375472, 70.2 KB checked in by anze <anze.staric@…>, 2 years ago (diff) |
---|

Line | |
---|---|

1 | """ |

2 | .. index:: deprecated network classes |

3 | |

4 | .. index:: |

5 | single: network; deprecated network classes |

6 | |

7 | ************************** |

8 | Deprecated network classes |

9 | ************************** |

10 | |

11 | Since Orange25, a NetworkX library is used in all Orange network modules and |

12 | widgets. Use :obj:`Orange.network.Graph`, :obj:`Orange.network.DiGraph`, |

13 | :obj:`Orange.network.MultiGraph` or :obj:`Orange.network.MultiDiGraph` that are |

14 | all NetworkX based network classes. |

15 | |

16 | Network (deprecated) |

17 | ==================== |

18 | |

19 | .. autoclass:: Orange.network.deprecated.Network |

20 | :members: |

21 | |

22 | Examples |

23 | -------- |

24 | |

25 | Reading and saving a network |

26 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |

27 | |

28 | This example demonstrates reading a network. Network class can read or write |

29 | Pajek (.net) or GML file format. |

30 | |

31 | :download:`network-read.py <code/network-read.py>` (uses: :download:`K5.net <code/K5.net>`): |

32 | |

33 | .. literalinclude:: code/network-read.py |

34 | :lines: 4-5 |

35 | |

36 | Visualize a network in NetExplorer widget |

37 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |

38 | |

39 | This example demonstrates how to display a network in NetExplorer. |

40 | |

41 | part of :download:`network-widget.py <code/network-widget.py>` |

42 | |

43 | .. literalinclude:: code/network-widget.py |

44 | :lines: 10-16 |

45 | |

46 | .. image:: files/network-explorer.png |

47 | :width: 100% |

48 | |

49 | |

50 | Network Layout Optimization (deprecated) |

51 | ======================================== |

52 | |

53 | .. autoclass:: Orange.network.NetworkOptimization |

54 | :members: |

55 | :exclude-members: collapse |

56 | |

57 | Examples |

58 | -------- |

59 | |

60 | Network constructor and random layout |

61 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |

62 | |

63 | In our first example we create a Network object with a simple full graph (K5). |

64 | Vertices are initially placed randomly. Graph is visualized using pylabs |

65 | matplotlib. NetworkOptimization class is not needed because we do not apply any |

66 | layout optimization method in this example. |

67 | |

68 | :download:`network-constructor.py <code/network-constructor.py>` |

69 | |

70 | .. literalinclude:: code/network-constructor.py |

71 | |

72 | Executing the above script pops-up a pylab window with the following graph |

73 | drawing: |

74 | |

75 | .. image:: files/network-K5-random.png |

76 | |

77 | Network layout optimization |

78 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ |

79 | |

80 | This example demonstrates how to optimize network layout using one of included |

81 | algorithms. |

82 | |

83 | part of :download:`network-optimization.py <code/network-optimization.py>` |

84 | |

85 | .. literalinclude:: code/network-optimization.py |

86 | :lines: 12-16 |

87 | |

88 | The following optimization algorithms are supported: |

89 | |

90 | * .random() |

91 | * .fruchterman_reingold(steps, temperature, coolingFactor=Default, hiddenNodes=[], weighted=False) |

92 | * .radial_fruchterman_reingold(center, steps, temperature) |

93 | * .circular_original() |

94 | * .circular_random() |

95 | * .circular_crossing_reduction() |

96 | |

97 | Spring forces layout optimization is the result of the above script: |

98 | |

99 | .. image:: files/network-K5-fr.png |

100 | |

101 | |

102 | Graphs (deprecated) |

103 | =================== |

104 | |

105 | Orange offers a data structure for representing directed and undirected graphs |

106 | with various types of weighted connections. |

107 | |

108 | Basic graphs have only one type of edges. Each edge can have an associated |

109 | number, representing a strength of the edge - with whatever underlying |

110 | physical interpretation. Orange's graphs are more general and two vertices |

111 | can be connected by edges of various types. One use for this would be in |

112 | genetics, where one gene can excite or inhibit another - or both |

113 | simultaneously, which is why we can't simply assign negative numbers to the |

114 | edges. The number of edge types is unlimited, but needs to be set in advance. |

115 | |

116 | Before constructing a graph, you will also need to decide for the underlying |

117 | data structure. The differences for smaller graphs (e.g. with less than 100 |

118 | nodes) should be insignificant, while for the larger, the decision should be |

119 | based upon the expected number of edges ("density" of the graph) and the |

120 | operations you plan to execute. Graphs with large number of edges (eg.>n2/4, |

121 | where n is the number of vertices) should be represented with adjacency |

122 | matrices (class :obj:`Orange.network.GraphAsMatrix`), graphs with small number |

123 | of edges with adjacency lists (:obj:`Orange.network.GraphAsList`) and those in |

124 | between with adjacency trees (:obj:`Orange.network.GraphAsTree`). Regarding |

125 | the speed, matrices are generally the fastest, while some operations, such as |

126 | finding all edges leading from certain node, will sometimes be faster with |

127 | lists or trees. |

128 | |

129 | One thing that is not supported (at the moment?) are multiple edges of the |

130 | same type between two vertices. |

131 | |

132 | Construction |

133 | ------------ |

134 | |

135 | When constructing a graph, you will need to decide about the data structure for |

136 | representation of edges, and call the corresponding constructor. All |

137 | constructors take the same arguments: the number of vertices (needs to be given |

138 | in advance, you cannot add additional vertices later), a flag telling whether |

139 | the graph is directed or not, and the number of edge types. The default number |

140 | of edge types is 1 (a normal graph), while the other two arguments are |

141 | mandatory. |

142 | |

143 | You can choose between three constructors, all derived from a single ancestor |

144 | :obj:`Orange.network.Graph`: |

145 | |

146 | .. class:: GraphAsMatrix(nVertices, directed[, nEdgeTypes]) |

147 | |

148 | Bases: :obj:`Orange.network.Graph` |

149 | |

150 | Edges are stored in a matrix with either n^2 or n(n+1)/2 elements, |

151 | depending upon whether the graph is directed or not. (In C++, it is stored |

152 | as float * pointing to an array of length n*n*nEdgeTypes or |

153 | (n*(n+1))/2*nEdgeTypes elements, where nEdgeTypes is the number of edge |

154 | types.) This representation is suitable for smaller graphs and for dense |

155 | large graphs. For graph with only one edge type, this representation is |

156 | more economical than representation with lists or trees when the number of |

157 | edges is larger than n2/4. Inserting, deleting and checking the edges is |

158 | fast; listing the neighbours of a certain node is fast unless the graph is |

159 | sparse, in which case a graph represented with a list or a tree would be |

160 | faster. |

161 | |

162 | .. class:: GraphAsList(nVertices, directed[, nEdgeTypes]) |

163 | |

164 | Bases: :obj:`Orange.network.Graph` |

165 | |

166 | Edges are stored in an ordered lists of neighbours, one list for each node. |

167 | In C++, for each neighbour, the connection is stored in a structure with |

168 | the vertex number (int), a pointer to the next structure, and an array of |

169 | floats, one for each integer. With 16-byte alignment, this would take 16 |

170 | bytes for graphs with one or two edge types on the usual 32-bit platforms. |

171 | For undirected graphs, each edge is stored only once, in the list of the |

172 | edge with the smaller index. This makes the structure smaller and insertion |

173 | and lookup faster; it slows down finding the neighbours of a given node. |

174 | This structure is convenient for graphs with a very small number of edges. |

175 | For them, inserting and removing edges is relatively fast; getting all |

176 | edges leading from a vertex is fast, while getting edges leading to a |

177 | vertex or getting all neighbours (in directed or undirected graph) is slow. |

178 | |

179 | .. class:: GraphAsTree(nVertices, directed[, nEdgeTypes]) |

180 | |

181 | Bases: :obj:`Orange.network.Graph` |

182 | |

183 | This structure is similar to GraphAsTree except that the edges are stored |

184 | in trees instead of lists. This should be a structure of choice for all |

185 | graph between really sparse and those having one quarter of possible edges. |

186 | As expected, queries are fast, while insertion and removal of edges is |

187 | somewhat slower (though still faster than for GraphAsList unless the number |

188 | of edges is really small). Internally, nodes of the tree contain the vertex |

189 | number, two pointers and a list of floats. With one edge type, this should |

190 | be 16 bytes on 32-bit platforms. |

191 | |

192 | Examples |

193 | ^^^^^^^^ |

194 | |

195 | An ordinary undirected graph with 10 vertices stored in a matrix would thus be |

196 | constructed by:: |

197 | |

198 | >>> graph = Orange.network.GraphAsMatrix(10, 0) |

199 | |

200 | A directed graph with 1000 vertices and edges of three types, stored with |

201 | adjacency trees would be constructed by:: |

202 | |

203 | >>> graph = Orange.network.GraphAsTree(1000, 1, 3) |

204 | |

205 | Usage |

206 | ----- |

207 | |

208 | All three graph types are used in the same way, independent of the underlying |

209 | structure. All methods are defined in basic class :obj:`Orange.network.Graph`. |

210 | |

211 | .. class:: Graph |

212 | |

213 | .. attribute:: nVertices |

214 | |

215 | The number of vertices (read-only, set at construction) |

216 | |

217 | .. attribute:: nEdgeTypes |

218 | |

219 | The number of different edge types (read-only, set at construction) |

220 | |

221 | .. attribute:: directed |

222 | |

223 | Tells whether the graph is directed (read-only, set at construction) |

224 | |

225 | .. attribute:: objects |

226 | |

227 | A dictionary, list or other sequence of objects that correspond to |

228 | graph nodes. The use of this object is described in section on |

229 | indexing. |

230 | |

231 | .. attribute:: forceMapping |

232 | |

233 | Determines whether to map integer indices through 'objects'. Details are |

234 | described below. |

235 | |

236 | .. attribute:: returnIndices |

237 | |

238 | If set, the methods that return list of neighbours will return lists of |

239 | integers even when objects are given. |

240 | |

241 | **Indexing** |

242 | |

243 | Vertices are referred to by either integer indices or Python objects of any |

244 | type. In the latter case, a mapping should be provided by assigning the |

245 | 'objects' attribute. For instance, if you set graph.objects to ["Age", |

246 | "Gender", "Height", "Weight"] then graph["Age", "Height"] would be equivalent |

247 | to graph[0, 2] and graph.get_neighbours("Weight") to graph.get_neighbours(3). |

248 | Vertex identifier doesn't need to be a string, it can be any Python |

249 | object. |

250 | |

251 | If objects contains a dictionary, its keys are vertex identifiers and the |

252 | values in the dictionary should be integers, eg. |

253 | |

254 | part of :download:`network-graph.py <code/network-graph.py>` |

255 | |

256 | .. literalinclude:: code/network-graph.py |

257 | :lines: 20-23 |

258 | |

259 | If not a dictionary, objects can be any kind of sequence. Usually, you will |

260 | give it a list of the same length as the number of vertices in the graph, |

261 | so each element would identify a vertex. When indexing, the index is sought |

262 | for in the list. objects can also be a list of attributes, a domain, an |

263 | example table or even a single string; Orange will run a code equivalent to |

264 | "for o in graph.objects", so everything for which such a loop works, goes. |

265 | |

266 | Searching through the list is, of course, rather slow, so it is recommended |

267 | to use integer indices for larger graphs. So, if you request |

268 | graph.get_neighbours(0), the method will return the neighbours of the first |

269 | vertex, even if objects is given. But - what if you want to map all |

270 | indices, even integers, through objects? In this case, you need to set |

271 | graph.forceMapping to 1. If graph.forceMapping is set and graph.objects is |

272 | given, even get_neighbours(0) will search the graph.objects for 0 and return |

273 | the neighbours of the corresponding (not necessarily the first) node. |

274 | |

275 | **Getting and Setting Edges** |

276 | |

277 | .. method:: graph[v1, v2] |

278 | |

279 | For graphs with a single edge type, graph[v1, v2] returns the weight of |

280 | the edge between v1 and v2, or None if there is no edge (edge's weight |

281 | can also be 0). |

282 | |

283 | For graphs with multiple edge types, graph[v1, v2] returns a list of |

284 | weights for various edge types. Some (or all, if there is no edge) |

285 | elements of the list can be None. If the edge does not exist, graph[v1, |

286 | v2] returns a list of Nones, not a None. |

287 | |

288 | Edges can also be set by assigning them a weight, e.g.graph[2, 5]=1.5. |

289 | As described above, if objects is a set, we can use other objects, such |

290 | as names, as v1 and v2 (the same goes for all other functions described |

291 | below). |

292 | |

293 | You can assign a list to graph[v1, v2]; in graph with three edge |

294 | types you can set graph[2, 5] = [1.5, None, -2.0]. After that, there |

295 | are two edges between vertices 2 and 5, one of the first type with |

296 | weight 1.5, and one of the third with weight -2.0. To remove an edge, |

297 | you can assign it a list of Nones or a single None, e.g. graph[2, |

298 | 5]=None; this removes edges of all types between the two nodes. |

299 | |

300 | The list returned for graphs with multiple edge types is actually a |

301 | reference to the edge, therefore you can set e = graph[v1, v2] and then |

302 | manipulate e, for instance e[1]=10 or e[0]=None. Edge will behave just |

303 | as an ordinary list (well, almost - no slicing ets). However, don't try |

304 | to assign a list to e, eg e=[1, None, 4]. This assigns a list to e, not |

305 | to the corresponding edge... |

306 | |

307 | .. method:: graph[v1, v2, type] |

308 | |

309 | This is defined only for graph with multiple edge types; it returns the |

310 | weight for the edge of type type between v1 and v2, or None if there is |

311 | no such edge. You can also establish an edge by assigning a weight |

312 | (e.g. graph[2, 5, 2] = -2.0) or remove it by assigning it a None |

313 | (graph[2, 5, 2] = None). |

314 | |

315 | .. method:: edge_exists(v1, v2[, type]) |

316 | |

317 | Returns true if the edge between v1 and v2 exists. For multiple edge |

318 | type graphs you can also specify the type of the edge you check for. If |

319 | the third argument is omitted, the method returns true if there is any |

320 | kind of edge between the two vertices. It is recommended to use this |

321 | method when you want to check for a node. In single edge type graphs, |

322 | if graph[v1, v2]: will fail when there is an edge but it has a weight |

323 | of zero. With multiple edge types, if graph[v1, v2]: will always |

324 | success since graph[v1, v2] returns a non- empty list; if there is no |

325 | edges, this will be a list of Nones, but Python still treats it as |

326 | "true". |

327 | |

328 | .. method:: add_cluster(list_of_vertices) |

329 | |

330 | Creates a cluster - adds edges between all listed vertices. |

331 | |

332 | **Queries** |

333 | |

334 | Graph provides a set of functions that return nodes connected to a certain |

335 | node. |

336 | |

337 | .. method:: get_neighbours(v1[, type]) |

338 | |

339 | Returns all the nodes that are connected to v1. In directed graphs, |

340 | this includes vertices with edges toward or from v1. In graphs with |

341 | multiple edge types you can also specify the edge type you are |

342 | interested in: get_neighbours will the return only the vertices that are |

343 | connected to v1 by edges of that type. |

344 | |

345 | .. method:: get_edges_from(v1[, type]) |

346 | |

347 | Return all the vertices which are connected to v1 by the edges leading |

348 | from v1. In edges with multiple edge types, you can specify the edge |

349 | type. In undirected graph, this function is equivalent to |

350 | get_neighbours. |

351 | |

352 | .. method:: get_edges_to(v1[, type]) |

353 | |

354 | Returns all the vertices with edges leading to v1. Again, you can |

355 | decide for a single edge type to observe, and, again again, in |

356 | undirected graphs this function is equivalent to get_neighbours. |

357 | |

358 | If objects is set, functions return a list of objects (names of |

359 | vertices or whatever objects you stored in objects). Otherwise, a list |

360 | of integer indices is returned. If you want to force Graph to return |

361 | integer indices even if objects is set, set graph.returnIndices to |

362 | True. |

363 | |

364 | Of the three operations, the expensive one is to look for the vertices with |

365 | edges pointing to the given edge. There is no problem when graph is |

366 | represented as a matrix (:obj:`Orange.network.GraphAsMatrix`); these are |

367 | always fast. On directed graph, get_edges_from is always fast as well. |

368 | |

369 | In undirected graphs represented as lists or trees, the edge between |

370 | vertices with indices v1 and v2 is stored at the list/tree in the |

371 | smaller of the two indices. Therefore to list all neighbours of v1, |

372 | edges with v2<v1 are copied form v1's list, while for edges with v2>v1 |

373 | the function needs to look for v1 in each v2's list/tree. Lookup in |

374 | trees is fast, while in representation with adjacency list, the |

375 | function is slower for v1 closer to nVertices/2. If v1 is small there |

376 | is a great number of v2>v1 whose lists are to be checked, but since the |

377 | lists are ordered, v1 is more to the beginning of these lists (and when |

378 | a vertex with index higher than v1 is encountered, we know that v1 is |

379 | not on the list). If v2 is great, there it is more toward the end of |

380 | the list, but there is smaller number of lists to be checked. |

381 | Generally, the average number of traversed list elements for |

382 | get_neighbours/get_edges_from/get_edges_to on undirected graphs with |

383 | p*nVertices2 edges is p(nVertices-v1)v1. |

384 | |

385 | To sum up, if you have a large undirected graph and intend to query for |

386 | neighbours (or, equivalently, edges to or from a node) a lot, don't use |

387 | :obj:`Orange.network.GraphAsList`. If the graph is small or you won't use |

388 | these functions, it doesn't matter. |

389 | |

390 | For directed graphs, get_edges_from is trivial. The other two functions are |

391 | even slower than for undirected graphs, since to find the edges leading |

392 | from any vertex to a given one, all lists/trees need to be searched. So, if |

393 | your algorithm will extensively use get_edges_to or get_neighbours and your |

394 | graph is large but the number of edges is less than nEdges2/2, you should |

395 | use :obj:`Orange.network.GraphAsTree` or, to be faster but consume more |

396 | memory store the graph as :obj:`Orange.network.GraphAsMatrix`. If the |

397 | number of edges is greater, :obj:`Orange.network.GraphAsMatrix` is more |

398 | economic anyway. This calculation is for graph with only one edge type; |

399 | see the description of graph types for details. |

400 | |

401 | However, this is all programmed in C++, so whatever you do, the bottleneck |

402 | will probably still be in your Python code and not in C++. You probably |

403 | cannot miss by using :obj:`Orange.Network.GraphAsTree` disregarding the |

404 | size of the graph and the operations you perform on it. |

405 | |

406 | **Graph analysis** |

407 | |

408 | .. method:: get_sub_graph(vertices) |

409 | |

410 | Return a new graph of type :obj:`Orange.network.Graph` that is a |

411 | subgraph of the original graph and consists of given vertices. |

412 | |

413 | .. method:: get_clustering_coefficient() |

414 | |

415 | Return the graph average local clustering coefficient, described in |

416 | Watts DJ, Strogatz SH: Collective dynamics of 'small-world' networks. |

417 | Nature 1998, 393(6684):440-442. |

418 | |

419 | .. method:: get_connected_components() |

420 | |

421 | Return a list of all connected components sorted descending by |

422 | component size. |

423 | |

424 | .. method:: get_degree_distribution() |

425 | |

426 | Return degree distribution as dictionary of type |

427 | {degree:number_of_vertices}. |

428 | |

429 | .. method:: get_degrees() |

430 | |

431 | Return a list of degrees. List size matches number of vertices. Index |

432 | of given degree matches index of corresponding vertex. |

433 | |

434 | .. method:: get_hubs(n) |

435 | |

436 | Return a list of n largest hubs. |

437 | |

438 | .. method:: get_shortest_paths(u, v) |

439 | |

440 | Return a list of vertices in the shortest path between u and v. |

441 | |

442 | .. method:: get_distance(u, v) |

443 | |

444 | Return a distance between vertices u and v. |

445 | |

446 | .. method:: get_diameter() |

447 | |

448 | Return a diameter of the graph. |

449 | |

450 | Examples |

451 | ^^^^^^^^ |

452 | |

453 | How to use graphs, part of :download:`network-graph.py <code/network-graph.py>` |

454 | |

455 | .. literalinclude:: code/network-graph.py |

456 | :lines: 9-56 |

457 | |

458 | Results:: |

459 | |

460 | [(1, 0), (2, 0), (2, 1)] |

461 | 0.3 |

462 | 0.3 |

463 | 0.1 |

464 | 0.3 |

465 | ['Gender', 'Height'] |

466 | [1, 2] |

467 | (None, None, None) |

468 | 12.0 |

469 | (None, 12, None) |

470 | 1 |

471 | 0 |

472 | 1 |

473 | 0 |

474 | 0 |

475 | 1 |

476 | (None, None, 3) |

477 | (None, None, None) |

478 | |

479 | How to use graphs with objects on edges, part of :download:`network-graph-obj.py <code/network-graph-obj.py>` |

480 | |

481 | .. literalinclude:: code/network-graph-obj.py |

482 | :lines: 9-59 |

483 | |

484 | Results:: |

485 | |

486 | [(1, 0), (2, 1)] |

487 | [1, 2, 3] |

488 | [1, 2, 3] |

489 | a string |

490 | None |

491 | a string |

492 | [1, 2, 3] |

493 | ['Gender'] |

494 | [1] |

495 | (None, None, None) |

496 | 12.0 |

497 | (None, 12, None) |

498 | 1 |

499 | 0 |

500 | 1 |

501 | 0 |

502 | 0 |

503 | 1 |

504 | (None, None, 3) |

505 | (None, None, None) |

506 | |

507 | An example of network analysis, part of :download:`network-graph-analysis.py <code/network-graph-analysis.py>` (uses: |

508 | :download:`combination.net <code/combination.net>`): |

509 | |

510 | .. literalinclude:: code/network-graph-analysis.py |

511 | :lines: 12-49 |

512 | |

513 | Results:: |

514 | |

515 | Connected components |

516 | [[0, 1, 2, 3, 4, 5, 6, 7, 8], [13, 14, 15, 16, 17, 18], [9, 10, 11, 12]] |

517 | |

518 | Degree distribution |

519 | {1: 5, 2: 4, 3: 8, 4: 1, 5: 1} |

520 | |

521 | Degrees |

522 | [4, 3, 3, 2, 2, 3, 2, 3, 2, 3, 3, 3, 3, 5, 1, 1, 1, 1, 1] |

523 | |

524 | Hubs |

525 | [13, 0, 1] |

526 | |

527 | Shortest path |

528 | [2, 0] |

529 | |

530 | Distance |

531 | 1 |

532 | |

533 | Diameter |

534 | 4 |

535 | |

536 | Subgraph image: |

537 | |

538 | .. image:: files/network-subgraph.png |

539 | |

540 | Additional functionality |

541 | ------------------------ |

542 | |

543 | Should you need any additional functionality, just tell us. Many things are |

544 | trivial to implement in C++ and will be much faster than the corresponding |

545 | scripts in Python. (In this regard, minimal span trees, maximal flows, coloring |

546 | and shortest path search are, of course, not considered basic functionality. :) |

547 | |

548 | Community Detection in Graphs (deprecated) |

549 | ========================================== |

550 | |

551 | .. autoclass:: Orange.network.NetworkClustering |

552 | :members: |

553 | |

554 | """ |

555 | import math |

556 | import random |

557 | import os |

558 | |

559 | import Orange.core |

560 | import Orange.data |

561 | import Orange.projection |

562 | |

563 | class MdsTypeClass(): |

564 | def __init__(self): |

565 | self.componentMDS = 0 |

566 | self.exactSimulation = 1 |

567 | self.MDS = 2 |

568 | |

569 | MdsType = MdsTypeClass() |

570 | |

571 | from Orange.core import GraphAsList, GraphAsMatrix, GraphAsTree |

572 | |

573 | class Network(Orange.core.Network): |

574 | |

575 | """Bases: :obj:`Orange.network.GraphAsList`, :obj:`Orange.network.Graph` |

576 | |

577 | Data structure for representing directed and undirected networks. |

578 | |

579 | Network class holds network structure information and supports basic |

580 | network analysis. Network class is inherited from |

581 | :obj:`Orange.network.GraphAsList`. Refer to |

582 | :obj:`Orange.network.GraphAsList` for more graph analysis tools. See the |

583 | Orange.core.Pathfinder class for a way to simplify your network. |

584 | |

585 | .. attribute:: coors |

586 | |

587 | Coordinates for all vertices. They are initialized to random positions. |

588 | You can modify them manually or use one of the optimization algorithms. |

589 | Usage: coors[0][i], coors[1][i]; 0 for x-axis, 1 for y-axis |

590 | |

591 | |

592 | .. attribute:: items |

593 | |

594 | ExampleTable with information about vertices. Number of rows should |

595 | match the number of vertices. |

596 | |

597 | .. attribute:: links |

598 | |

599 | ExampleTable with information about edges. Number of rows should match |

600 | the number of edges. Two float attributes named "u" and "v" must be in |

601 | links table domain to relate the data of an example to an edge. Here, |

602 | egde is defined by two vertices "u" and "v". |

603 | |

604 | .. attribute:: optimization |

605 | |

606 | An instance of the NetworkOptimization class. Various network layout |

607 | optimization methods can be applied to the network through this |

608 | attribute. |

609 | |

610 | .. method:: from_distance_matrix(matrix, lower, upper, kNN=0): |

611 | |

612 | Creates edges between vertices with the distance within given |

613 | threshold. The DistanceMatrix dimension should equal the number of |

614 | vertices. |

615 | |

616 | :param matrix: number of objects in a matrix must match the number |

617 | of vertices in a network. |

618 | :type matrix: Orange.core.SymMatrix |

619 | :param lower: lower distance bound. |

620 | :type lower: float |

621 | :param upper: upper distance bound. |

622 | :type upper: float |

623 | :param kNN: specifies the minimum number of closest vertices to be |

624 | connected. |

625 | :type kNN: int |

626 | |

627 | .. method:: hide_vertices(vertices) |

628 | |

629 | Remove vertices from optimize list |

630 | |

631 | .. method:: show_vertices(vertices) |

632 | |

633 | Add vertices to optimize list |

634 | |

635 | .. method:: show_all() |

636 | |

637 | Add all vertices to optimize list |

638 | |

639 | .. method:: get_visible() |

640 | |

641 | Return optimize list |

642 | |

643 | """ |

644 | |

645 | def __init__(self, *args): |

646 | """:param nVertices: number of vertices (default 1) |

647 | :param nEdges: number of edge types (default 1) |

648 | :param directedGraph: directed edges (default True) |

649 | |

650 | """ |

651 | #print "orngNetwork.Network" |

652 | self.optimization = NetworkOptimization(self) |

653 | self.clustering = NetworkClustering(self) |

654 | |

655 | def get_distance_matrix_threshold(self, matrix, ratio): |

656 | """Return lower and upper distance threshold values for the given |

657 | ratio of edges |

658 | |

659 | """ |

660 | values = [] |

661 | for i in range(matrix.dim): |

662 | for j in range(i): |

663 | values.append((matrix[i,j], i, j)) |

664 | |

665 | values.sort() |

666 | return values[0][0], values[int(ratio*len(values))][0] |

667 | |

668 | def save(self, fileName): |

669 | """Save the network to a Pajek (.net) or GML file format. |

670 | data.Table items and links are saved automatically if the value is not |

671 | None. They are saved to "file_items.tab" and "file_links.tab" files. |

672 | |

673 | :param fileName: file path |

674 | :type fileName: string |

675 | |

676 | """ |

677 | try: |

678 | root, ext = os.path.splitext(fileName) |

679 | if ext == '': |

680 | fileName = root + '.net' |

681 | graphFile = open(fileName, 'w+') |

682 | except IOError: |

683 | return 1 |

684 | |

685 | root, ext = os.path.splitext(fileName) |

686 | if ext.lower() == ".gml": |

687 | self.saveGML(graphFile) |

688 | else: |

689 | self.save_pajek(graphFile) |

690 | |

691 | def save_gml(self, fp): |

692 | """Save network to GML (.gml) file format. |

693 | |

694 | :param fp: file pointer |

695 | :type fp: file |

696 | |

697 | """ |

698 | fp.write("graph\n[\n") |

699 | tabs = "\t" |

700 | fp.write("%slabel\t\"%s\"\n" % (tabs, self.name)) |

701 | |

702 | for v in range(self.nVertices): |

703 | try: |

704 | label = self.items[v]['label'] |

705 | except: |

706 | label = "" |

707 | |

708 | fp.write("\tnode\n\t[\n\t\tid\t%d\n\t\tlabel\t\"%s\"\n\t]\n" % |

709 | (v, label)) |

710 | |

711 | for u,v in self.getEdges(): |

712 | fp.write("\tedge\n\t[\n\t\tsource\t%d\n\t\ttarget\t%d\n\t\tlabel\t\"%s\"\n\t]\n" % (u, v, "")) |

713 | |

714 | fp.write("]\n") |

715 | |

716 | if self.items != None and len(self.items) > 0: |

717 | (name, ext) = os.path.splitext(fp.name) |

718 | self.items.save(name + "_items.tab") |

719 | |

720 | if hasattr(self, 'links') and self.links != None and \ |

721 | len(self.links) > 0: |

722 | (name, ext) = os.path.splitext(fp.name) |

723 | self.links.save(name + "_links.tab") |

724 | |

725 | def save_pajek(self, fp): |

726 | """Save network to Pajek (.net) file format. |

727 | |

728 | :param fp: file pointer |

729 | :type fp: file |

730 | |

731 | """ |

732 | name = '' |

733 | fp.write('### Generated with Orange Network Visualizer ### \n\n\n') |

734 | if name == '': |

735 | fp.write('*Network ' + '"no name" \n\n') |

736 | else: |

737 | fp.write('*Network ' + str(name) + ' \n\n') |

738 | |

739 | # print node descriptions |

740 | fp.write('*Vertices %8d %8d\n' % (self.nVertices, self.nEdgeTypes)) |

741 | for v in range(self.nVertices): |

742 | fp.write('% 8d ' % (v + 1)) |

743 | try: |

744 | label = self.items[v]['label'] |

745 | fp.write(str('"' + str(label) + '"') + ' \t') |

746 | except: |

747 | fp.write(str('"' + str(v) + '"') + ' \t') |

748 | |

749 | if hasattr(self, 'coors'): |

750 | x = self.coors[0][v] |

751 | y = self.coors[1][v] |

752 | z = 0.5000 |

753 | fp.write('%.4f %.4f %.4f\t' % (x, y, z)) |

754 | fp.write('\n') |

755 | |

756 | # print edge descriptions |

757 | # not directed edges |

758 | if self.directed: |

759 | fp.write('*Arcs \n') |

760 | for (i, j) in self.getEdges(): |

761 | if len(self[i, j]) > 0: |

762 | if self.nEdgeTypes > 1: |

763 | edge_str = str(self[i, j]) |

764 | else: |

765 | edge_str = "%f" % float(str(self[i, j])) |

766 | fp.write('%8d %8d %s' % (i + 1, j + 1, edge_str)) |

767 | fp.write('\n') |

768 | # directed edges |

769 | else: |

770 | fp.write('*Edges \n') |

771 | writtenEdges = {} |

772 | for (i, j) in self.getEdges(): |

773 | if len(self[i, j]) > 0: |

774 | if i > j: i,j = j,i |

775 | |

776 | if not (i,j) in writtenEdges: |

777 | writtenEdges[(i,j)] = 1 |

778 | else: |

779 | continue |

780 | |

781 | if self.nEdgeTypes > 1: |

782 | edge_str = str(self[i, j]) |

783 | else: |

784 | edge_str = "%f" % float(str(self[i, j])) |

785 | fp.write('%8d %8d %s' % (i + 1, j + 1, edge_str)) |

786 | fp.write('\n') |

787 | |

788 | fp.write('\n') |

789 | |

790 | if self.items != None and len(self.items) > 0: |

791 | (name, ext) = os.path.splitext(fp.name) |

792 | self.items.save(name + "_items.tab") |

793 | |

794 | if hasattr(self, 'links') and self.links != None \ |

795 | and len(self.links) > 0: |

796 | (name, ext) = os.path.splitext(fp.name) |

797 | self.links.save(name + "_links.tab") |

798 | |

799 | return 0 |

800 | |

801 | @staticmethod |

802 | def read(fileName, directed=0): |

803 | """Read network. Supported network formats: from Pajek (.net) file, |

804 | GML. |

805 | |

806 | :param fileName: file path |

807 | :type fileName: string |

808 | :param directed: (default False) |

809 | :type directed: bool |

810 | |

811 | """ |

812 | if type(fileName) == file: |

813 | root, ext = os.path.splitext(fileName.name) |

814 | if ext.lower() == ".net": |

815 | net = Network(2,0).parseNetwork(fileName.read(), directed) |

816 | net.optimization = NetworkOptimization(net) |

817 | return net |

818 | else: |

819 | print "invalid network type", fileName.name |

820 | return None |

821 | else: |

822 | root, ext = os.path.splitext(fileName) |

823 | net = None |

824 | if ext.lower() == ".net": |

825 | net = Network(2,0).readPajek(fileName, directed) |

826 | elif ext.lower() == ".gml": |

827 | net = Network(2,0).readGML(fileName) |

828 | else: |

829 | print "Invalid file type %s" % fileName |

830 | |

831 | if net is not None: |

832 | net.optimization = NetworkOptimization(net) |

833 | return net |

834 | |

835 | ########################################################################## |

836 | ### BEGIN: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0) ### |

837 | ########################################################################## |

838 | |

839 | def getDistanceMatrixThreshold(self, matrix, ratio): |

840 | import warnings |

841 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

842 | "get_distance_matrix_threshold", DeprecationWarning) |

843 | return self.get_distance_matrix_threshold(matrix, ratio) |

844 | |

845 | def saveNetwork(self, fileName): |

846 | import warnings |

847 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

848 | "save", DeprecationWarning) |

849 | return self.save(fileName) |

850 | |

851 | def savePajek(fp): |

852 | import warnings |

853 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

854 | "save_pajek", DeprecationWarning) |

855 | return self.save_pajek(fp) |

856 | |

857 | def saveGML(self, fp): |

858 | import warnings |

859 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

860 | "save_gml", DeprecationWarning) |

861 | return self.save_gml(fp) |

862 | |

863 | ########################################################################## |

864 | ### END: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0) ### |

865 | ########################################################################## |

866 | |

867 | class NetworkOptimization(Orange.core.NetworkOptimization): |

868 | |

869 | """Perform network layout optimization. Network structure is defined in |

870 | :obj:`Orange.network.Network` class. |

871 | |

872 | :param network: Network to optimize |

873 | :type network: Orange.network.Network |

874 | |

875 | .. attribute:: graph |

876 | |

877 | Holds the :obj:`Orange.network.Network` object. |

878 | |

879 | .. method:: random() |

880 | |

881 | Random layout optimization. |

882 | |

883 | .. method:: fruchterman_reingold(steps=100, temperature=1000, coolFactor=default, hiddenNodes=[], weighted=False) |

884 | |

885 | Fruchterman-Reingold spring layout optimization. Set number of iterations |

886 | with argument steps, start temperature with temperature (for example: 1000) |

887 | and set list of hidden nodes with argument hidden_nodes. |

888 | |

889 | .. method:: radial_fruchterman_reingold(center, steps=100, temperature=1000) |

890 | |

891 | Radial Fruchterman-Reingold spring layout optimization. Set center node |

892 | with attribute center, number of iterations with argument steps and start |

893 | temperature with temperature (for example: 1000). |

894 | |

895 | .. method:: circular_original() |

896 | |

897 | Circular layout optimization based on original order. |

898 | |

899 | .. method:: circular_random() |

900 | |

901 | Circular layout optimization based on random order. |

902 | |

903 | .. method:: circular_crossing_reduction() |

904 | |

905 | Circular layout optimization (Michael Baur, Ulrik Brandes) with crossing |

906 | reduction. |

907 | |

908 | .. method:: closest_vertex(x, y) |

909 | |

910 | Return the closest vertex to (x, y) coordinate. |

911 | |

912 | .. method:: vertex_distances(x, y) |

913 | |

914 | Return distances (list of (distance, vertex) tuples) of all vertices to |

915 | the given coordinate. |

916 | |

917 | .. method:: get_vertices_in_rect(x1, y1, x2, y2) |

918 | |

919 | Return a list of all vertices in given rectangle. |

920 | |

921 | """ |

922 | |

923 | def __init__(self, network=None, name="None"): |

924 | if network is None: |

925 | network = Orange.core.Network(2, 0) |

926 | |

927 | self.setGraph(network) |

928 | self.graph = network |

929 | |

930 | self.maxWidth = 1000 |

931 | self.maxHeight = 1000 |

932 | |

933 | self.attributeList = {} |

934 | self.attributeValues = {} |

935 | self.vertexDistance = None |

936 | self.mds = None |

937 | |

938 | def set_network(self, network): |

939 | """Set the network object for layout optimization. |

940 | |

941 | :param network: network object for layout optimization |

942 | :type network: Orange.network.Network |

943 | |

944 | """ |

945 | self.setGraph(network) |

946 | |

947 | def _compute_forces(self): |

948 | """Compute forces for each vertex for force vector visualization.""" |

949 | n = self.graph.nVertices |

950 | vertices = set(range(n)) |

951 | e_avg = 0 |

952 | edges = self.graph.getEdges() |

953 | for u,v in edges: |

954 | u_ = numpy.array([self.graph.coors[0][u], self.graph.coors[1][u]]) |

955 | v_ = numpy.array([self.graph.coors[0][v], self.graph.coors[1][v]]) |

956 | e_avg += numpy.linalg.norm(u_ - v_) |

957 | e_avg /= len(edges) |

958 | |

959 | forces = [] |

960 | maxforce = [] |

961 | components = self.graph.getConnectedComponents() |

962 | for component in components: |

963 | outer_vertices = vertices - set(component) |

964 | |

965 | for u in component: |

966 | u_ = numpy.array([self.graph.coors[0][u], |

967 | self.graph.coors[1][u]]) |

968 | force = numpy.array([0.0, 0.0]) |

969 | for v in outer_vertices: |

970 | v_ = numpy.array([self.graph.coors[0][v], |

971 | self.graph.coors[1][v]]) |

972 | d = self.vertexDistance[u, v] |

973 | norm = numpy.linalg.norm(v_ - u_) |

974 | force += (d - norm) * (v_ - u_) / norm |

975 | |

976 | forces.append(force) |

977 | maxforce.append(numpy.linalg.norm(force)) |

978 | |

979 | maxforce = max(maxforce) |

980 | rv = [] |

981 | for v in range(n): |

982 | force = forces[v] |

983 | v_ = numpy.array([self.graph.coors[0][v], self.graph.coors[1][v]]) |

984 | f = force * e_avg / maxforce |

985 | rv.append(([v_[0], v_[0] + f[0]],[v_[1], v_[1] + f[1]])) |

986 | |

987 | return rv |

988 | |

989 | def collapse(self): |

990 | """Experimental method to group cliques to meta nodes.""" |

991 | if len(self.graph.getNodes(1)) > 0: |

992 | nodes = list(set(range(self.graph.nVertices)) - \ |

993 | set(self.graph.getNodes(1))) |

994 | |

995 | if len(nodes) > 0: |

996 | subgraph = Orange.core.Network(self.graph.getSubGraph(nodes)) |

997 | oldcoors = self.coors |

998 | self.setGraph(subgraph) |

999 | self.graph = subgraph |

1000 | |

1001 | for i in range(len(nodes)): |

1002 | self.coors[0][i] = oldcoors[0][nodes[i]] |

1003 | self.coors[1][i] = oldcoors[1][nodes[i]] |

1004 | |

1005 | else: |

1006 | fullgraphs = self.graph.getLargestFullGraphs() |

1007 | subgraph = self.graph |

1008 | |

1009 | if len(fullgraphs) > 0: |

1010 | used = set() |

1011 | graphstomerge = list() |

1012 | #print fullgraphs |

1013 | for fullgraph in fullgraphs: |

1014 | #print fullgraph |

1015 | fullgraph_set = set(fullgraph) |

1016 | if len(used & fullgraph_set) == 0: |

1017 | graphstomerge.append(fullgraph) |

1018 | used |= fullgraph_set |

1019 | |

1020 | #print graphstomerge |

1021 | #print used |

1022 | subgraph = Orange.core.Network( |

1023 | subgraph.getSubGraphMergeClusters(graphstomerge)) |

1024 | |

1025 | nodescomp = list(set(range(self.graph.nVertices)) - used) |

1026 | |

1027 | #subgraph.setattr("items", self.graph.items.getitems(nodescomp)) |

1028 | #subgraph.items.append(self.graph.items[0]) |

1029 | oldcoors = self.coors |

1030 | self.setGraph(subgraph) |

1031 | self.graph = subgraph |

1032 | for i in range(len(nodescomp)): |

1033 | self.coors[0][i] = oldcoors[0][nodescomp[i]] |

1034 | self.coors[1][i] = oldcoors[1][nodescomp[i]] |

1035 | |

1036 | # place meta vertex in center of cluster |

1037 | x, y = 0, 0 |

1038 | for node in used: |

1039 | x += oldcoors[0][node] |

1040 | y += oldcoors[1][node] |

1041 | |

1042 | x = x / len(used) |

1043 | y = y / len(used) |

1044 | |

1045 | self.coors[0][len(nodescomp)] = x |

1046 | self.coors[1][len(nodescomp)] = y |

1047 | |

1048 | def get_vars(self): |

1049 | """Return a list of features in network items.""" |

1050 | vars = [] |

1051 | if (self.graph != None): |

1052 | if hasattr(self.graph, "items"): |

1053 | if isinstance(self.graph.items, Orange.data.Table): |

1054 | vars[:0] = self.graph.items.domain.variables |

1055 | |

1056 | metas = self.graph.items.domain.getmetas(0) |

1057 | for i, var in metas.iteritems(): |

1058 | vars.append(var) |

1059 | return vars |

1060 | |

1061 | def get_edge_vars(self): |

1062 | """Return a list of features in network links.""" |

1063 | vars = [] |

1064 | if (self.graph != None): |

1065 | if hasattr(self.graph, "links"): |

1066 | if isinstance(self.graph.links, Orange.data.Table): |

1067 | vars[:0] = self.graph.links.domain.variables |

1068 | |

1069 | metas = self.graph.links.domain.getmetas(0) |

1070 | for i, var in metas.iteritems(): |

1071 | vars.append(var) |

1072 | |

1073 | return [x for x in vars if str(x.name) != 'u' and str(x.name) != 'v'] |

1074 | |

1075 | def rotate_vertices(self, components, phi): |

1076 | """Rotate network components for a given angle. |

1077 | |

1078 | :param components: list of network components |

1079 | :type components: list of lists of vertex indices |

1080 | :param phi: list of component rotation angles (unit: radians) |

1081 | """ |

1082 | #print phi |

1083 | for i in range(len(components)): |

1084 | if phi[i] == 0: |

1085 | continue |

1086 | |

1087 | component = components[i] |

1088 | |

1089 | x = self.graph.coors[0][component] |

1090 | y = self.graph.coors[1][component] |

1091 | |

1092 | x_center = x.mean() |

1093 | y_center = y.mean() |

1094 | |

1095 | x = x - x_center |

1096 | y = y - y_center |

1097 | |

1098 | r = numpy.sqrt(x ** 2 + y ** 2) |

1099 | fi = numpy.arctan2(y, x) |

1100 | |

1101 | fi += phi[i] |

1102 | #fi += factor * M[i] * numpy.pi / 180 |

1103 | |

1104 | x = r * numpy.cos(fi) |

1105 | y = r * numpy.sin(fi) |

1106 | |

1107 | self.graph.coors[0][component] = x + x_center |

1108 | self.graph.coors[1][component] = y + y_center |

1109 | |

1110 | def rotate_components(self, maxSteps=100, minMoment=0.000000001, |

1111 | callbackProgress=None, callbackUpdateCanvas=None): |

1112 | """Rotate the network components using a spring model.""" |

1113 | if self.vertexDistance == None: |

1114 | return 1 |

1115 | |

1116 | if self.graph == None: |

1117 | return 1 |

1118 | |

1119 | if self.vertexDistance.dim != self.graph.nVertices: |

1120 | return 1 |

1121 | |

1122 | self.stopRotate = 0 |

1123 | |

1124 | # rotate only components with more than one vertex |

1125 | components = [component for component \ |

1126 | in self.graph.getConnectedComponents() \ |

1127 | if len(component) > 1] |

1128 | vertices = set(range(self.graph.nVertices)) |

1129 | step = 0 |

1130 | M = [1] |

1131 | temperature = [[30.0, 1] for i in range(len(components))] |

1132 | dirChange = [0] * len(components) |

1133 | while step < maxSteps and (max(M) > minMoment or min(M) < -minMoment) \ |

1134 | and not self.stopRotate: |

1135 | M = [0] * len(components) |

1136 | |

1137 | for i in range(len(components)): |

1138 | component = components[i] |

1139 | |

1140 | outer_vertices = vertices - set(component) |

1141 | |

1142 | x = self.graph.coors[0][component] |

1143 | y = self.graph.coors[1][component] |

1144 | |

1145 | x_center = x.mean() |

1146 | y_center = y.mean() |

1147 | |

1148 | for j in range(len(component)): |

1149 | u = component[j] |

1150 | |

1151 | for v in outer_vertices: |

1152 | d = self.vertexDistance[u, v] |

1153 | u_x = self.graph.coors[0][u] |

1154 | u_y = self.graph.coors[1][u] |

1155 | v_x = self.graph.coors[0][v] |

1156 | v_y = self.graph.coors[1][v] |

1157 | L = [(u_x - v_x), (u_y - v_y)] |

1158 | R = [(u_x - x_center), (u_y - y_center)] |

1159 | e = math.sqrt((v_x - x_center) ** 2 + \ |

1160 | (v_y - y_center) ** 2) |

1161 | |

1162 | M[i] += (1 - d) / (e ** 2) * numpy.cross(R, L) |

1163 | |

1164 | tmpM = numpy.array(M) |

1165 | #print numpy.min(tmpM), numpy.max(tmpM),numpy.average(tmpM),numpy.min(numpy.abs(tmpM)) |

1166 | |

1167 | phi = [0] * len(components) |

1168 | #print "rotating", temperature, M |

1169 | for i in range(len(M)): |

1170 | if M[i] > 0: |

1171 | if temperature[i][1] < 0: |

1172 | temperature[i][0] = temperature[i][0] * 5 / 10 |

1173 | temperature[i][1] = 1 |

1174 | dirChange[i] += 1 |

1175 | |

1176 | phi[i] = temperature[i][0] * numpy.pi / 180 |

1177 | elif M[i] < 0: |

1178 | if temperature[i][1] > 0: |

1179 | temperature[i][0] = temperature[i][0] * 5 / 10 |

1180 | temperature[i][1] = -1 |

1181 | dirChange[i] += 1 |

1182 | |

1183 | phi[i] = -temperature[i][0] * numpy.pi / 180 |

1184 | |

1185 | # stop rotating when phi is to small to notice the rotation |

1186 | if max(phi) < numpy.pi / 1800: |

1187 | #print "breaking" |

1188 | break |

1189 | |

1190 | self.rotate_vertices(components, phi) |

1191 | if callbackUpdateCanvas: callbackUpdateCanvas() |

1192 | if callbackProgress : callbackProgress(min([dirChange[i] for i \ |

1193 | in range(len(dirChange)) if M[i] != 0]), 9) |

1194 | step += 1 |

1195 | |

1196 | def mds_update_data(self, components, mds, callbackUpdateCanvas): |

1197 | """Translate and rotate the network components to computed positions.""" |

1198 | component_props = [] |

1199 | x_mds = [] |

1200 | y_mds = [] |

1201 | phi = [None] * len(components) |

1202 | self.diag_coors = math.sqrt(( \ |

1203 | min(self.graph.coors[0]) - max(self.graph.coors[0]))**2 + \ |

1204 | (min(self.graph.coors[1]) - max(self.graph.coors[1]))**2) |

1205 | |

1206 | if self.mdsType == MdsType.MDS: |

1207 | x = [mds.points[u][0] for u in range(self.graph.nVertices)] |

1208 | y = [mds.points[u][1] for u in range(self.graph.nVertices)] |

1209 | self.graph.coors[0][range(self.graph.nVertices)] = x |

1210 | self.graph.coors[1][range(self.graph.nVertices)] = y |

1211 | if callbackUpdateCanvas: |

1212 | callbackUpdateCanvas() |

1213 | return |

1214 | |

1215 | for i in range(len(components)): |

1216 | component = components[i] |

1217 | |

1218 | if len(mds.points) == len(components): # if average linkage before |

1219 | x_avg_mds = mds.points[i][0] |

1220 | y_avg_mds = mds.points[i][1] |

1221 | else: # if not average linkage before |

1222 | x = [mds.points[u][0] for u in component] |

1223 | y = [mds.points[u][1] for u in component] |

1224 | |

1225 | x_avg_mds = sum(x) / len(x) |

1226 | y_avg_mds = sum(y) / len(y) |

1227 | # compute rotation angle |

1228 | c = [numpy.linalg.norm(numpy.cross(mds.points[u], \ |

1229 | [self.graph.coors[0][u],self.graph.coors[1][u]])) \ |

1230 | for u in component] |

1231 | n = [numpy.vdot([self.graph.coors[0][u], \ |

1232 | self.graph.coors[1][u]], \ |

1233 | [self.graph.coors[0][u], \ |

1234 | self.graph.coors[1][u]]) for u in component] |

1235 | phi[i] = sum(c) / sum(n) |

1236 | #print phi |

1237 | |

1238 | x = self.graph.coors[0][component] |

1239 | y = self.graph.coors[1][component] |

1240 | |

1241 | x_avg_graph = sum(x) / len(x) |

1242 | y_avg_graph = sum(y) / len(y) |

1243 | |

1244 | x_mds.append(x_avg_mds) |

1245 | y_mds.append(y_avg_mds) |

1246 | |

1247 | component_props.append((x_avg_graph, y_avg_graph, \ |

1248 | x_avg_mds, y_avg_mds, phi)) |

1249 | |

1250 | w = max(self.graph.coors[0]) - min(self.graph.coors[0]) |

1251 | h = max(self.graph.coors[1]) - min(self.graph.coors[1]) |

1252 | d = math.sqrt(w**2 + h**2) |

1253 | #d = math.sqrt(w*h) |

1254 | e = [math.sqrt((self.graph.coors[0][u] - self.graph.coors[0][v])**2 + |

1255 | (self.graph.coors[1][u] - self.graph.coors[1][v])**2) for |

1256 | (u, v) in self.graph.getEdges()] |

1257 | |

1258 | if self.scalingRatio == 0: |

1259 | pass |

1260 | elif self.scalingRatio == 1: |

1261 | self.mdsScaleRatio = d |

1262 | elif self.scalingRatio == 2: |

1263 | self.mdsScaleRatio = d / sum(e) * float(len(e)) |

1264 | elif self.scalingRatio == 3: |

1265 | self.mdsScaleRatio = 1 / sum(e) * float(len(e)) |

1266 | elif self.scalingRatio == 4: |

1267 | self.mdsScaleRatio = w * h |

1268 | elif self.scalingRatio == 5: |

1269 | self.mdsScaleRatio = math.sqrt(w * h) |

1270 | elif self.scalingRatio == 6: |

1271 | self.mdsScaleRatio = 1 |

1272 | elif self.scalingRatio == 7: |

1273 | e_fr = 0 |

1274 | e_count = 0 |

1275 | for i in range(self.graph.nVertices): |

1276 | for j in range(i + 1, self.graph.nVertices): |

1277 | x1 = self.graph.coors[0][i] |

1278 | y1 = self.graph.coors[1][i] |

1279 | x2 = self.graph.coors[0][j] |

1280 | y2 = self.graph.coors[1][j] |

1281 | e_fr += math.sqrt((x1-x2)**2 + (y1-y2)**2) |

1282 | e_count += 1 |

1283 | self.mdsScaleRatio = e_fr / e_count |

1284 | elif self.scalingRatio == 8: |

1285 | e_fr = 0 |

1286 | e_count = 0 |

1287 | for i in range(len(components)): |

1288 | for j in range(i + 1, len(components)): |

1289 | x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, \ |

1290 | y_avg_mds_i, phi_i = component_props[i] |

1291 | x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, \ |

1292 | y_avg_mds_j, phi_j = component_props[j] |

1293 | e_fr += math.sqrt((x_avg_graph_i-x_avg_graph_j)**2 + \ |

1294 | (y_avg_graph_i-y_avg_graph_j)**2) |

1295 | e_count += 1 |

1296 | self.mdsScaleRatio = e_fr / e_count |

1297 | elif self.scalingRatio == 9: |

1298 | e_fr = 0 |

1299 | e_count = 0 |

1300 | for i in range(len(components)): |

1301 | component = components[i] |

1302 | x = self.graph.coors[0][component] |

1303 | y = self.graph.coors[1][component] |

1304 | for i in range(len(x)): |

1305 | for j in range(i + 1, len(y)): |

1306 | x1 = x[i] |

1307 | y1 = y[i] |

1308 | x2 = x[j] |

1309 | y2 = y[j] |

1310 | e_fr += math.sqrt((x1-x2)**2 + (y1-y2)**2) |

1311 | e_count += 1 |

1312 | self.mdsScaleRatio = e_fr / e_count |

1313 | |

1314 | diag_mds = math.sqrt((max(x_mds) - min(x_mds))**2 + (max(y_mds) - \ |

1315 | min(y_mds))**2) |

1316 | e = [math.sqrt((self.graph.coors[0][u] - self.graph.coors[0][v])**2 + |

1317 | (self.graph.coors[1][u] - self.graph.coors[1][v])**2) for |

1318 | (u, v) in self.graph.getEdges()] |

1319 | e = sum(e) / float(len(e)) |

1320 | |

1321 | x = [mds.points[u][0] for u in range(len(mds.points))] |

1322 | y = [mds.points[u][1] for u in range(len(mds.points))] |

1323 | w = max(x) - min(x) |

1324 | h = max(y) - min(y) |

1325 | d = math.sqrt(w**2 + h**2) |

1326 | |

1327 | if len(x) == 1: |

1328 | r = 1 |

1329 | else: |

1330 | if self.scalingRatio == 0: |

1331 | r = self.mdsScaleRatio / d * e |

1332 | elif self.scalingRatio == 1: |

1333 | r = self.mdsScaleRatio / d |

1334 | elif self.scalingRatio == 2: |

1335 | r = self.mdsScaleRatio / d * e |

1336 | elif self.scalingRatio == 3: |

1337 | r = self.mdsScaleRatio * e |

1338 | elif self.scalingRatio == 4: |

1339 | r = self.mdsScaleRatio / (w * h) |

1340 | elif self.scalingRatio == 5: |

1341 | r = self.mdsScaleRatio / math.sqrt(w * h) |

1342 | elif self.scalingRatio == 6: |

1343 | r = 1 / math.sqrt(self.graph.nVertices) |

1344 | elif self.scalingRatio == 7: |

1345 | e_mds = 0 |

1346 | e_count = 0 |

1347 | for i in range(len(mds.points)): |

1348 | for j in range(i): |

1349 | x1 = mds.points[i][0] |

1350 | y1 = mds.points[i][1] |

1351 | x2 = mds.points[j][0] |

1352 | y2 = mds.points[j][1] |

1353 | e_mds += math.sqrt((x1-x2)**2 + (y1-y2)**2) |

1354 | e_count += 1 |

1355 | r = self.mdsScaleRatio / e_mds * e_count |

1356 | elif self.scalingRatio == 8: |

1357 | e_mds = 0 |

1358 | e_count = 0 |

1359 | for i in range(len(components)): |

1360 | for j in range(i + 1, len(components)): |

1361 | x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, \ |

1362 | y_avg_mds_i, phi_i = component_props[i] |

1363 | x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, \ |

1364 | y_avg_mds_j, phi_j = component_props[j] |

1365 | e_mds += math.sqrt((x_avg_mds_i-x_avg_mds_j)**2 + \ |

1366 | (y_avg_mds_i-y_avg_mds_j)**2) |

1367 | e_count += 1 |

1368 | r = self.mdsScaleRatio / e_mds * e_count |

1369 | elif self.scalingRatio == 9: |

1370 | e_mds = 0 |

1371 | e_count = 0 |

1372 | for i in range(len(mds.points)): |

1373 | for j in range(i): |

1374 | x1 = mds.points[i][0] |

1375 | y1 = mds.points[i][1] |

1376 | x2 = mds.points[j][0] |

1377 | y2 = mds.points[j][1] |

1378 | e_mds += math.sqrt((x1-x2)**2 + (y1-y2)**2) |

1379 | e_count += 1 |

1380 | r = self.mdsScaleRatio / e_mds * e_count |

1381 | |

1382 | #r = self.mdsScaleRatio / d |

1383 | #print "d", d, "r", r |

1384 | #r = self.mdsScaleRatio / math.sqrt(self.graph.nVertices) |

1385 | |

1386 | for i in range(len(components)): |

1387 | component = components[i] |

1388 | x_avg_graph, y_avg_graph, x_avg_mds, \ |

1389 | y_avg_mds, phi = component_props[i] |

1390 | |

1391 | # if phi[i]: # rotate vertices |

1392 | # #print "rotate", i, phi[i] |

1393 | # r = numpy.array([[numpy.cos(phi[i]), -numpy.sin(phi[i])], [numpy.sin(phi[i]), numpy.cos(phi[i])]]) #rotation matrix |

1394 | # c = [x_avg_graph, y_avg_graph] # center of mass in FR coordinate system |

1395 | # v = [numpy.dot(numpy.array([self.graph.coors[0][u], self.graph.coors[1][u]]) - c, r) + c for u in component] |

1396 | # self.graph.coors[0][component] = [u[0] for u in v] |

1397 | # self.graph.coors[1][component] = [u[1] for u in v] |

1398 | |

1399 | # translate vertices |

1400 | if not self.rotationOnly: |

1401 | self.graph.coors[0][component] = \ |

1402 | (self.graph.coors[0][component] - x_avg_graph) / r + x_avg_mds |

1403 | self.graph.coors[1][component] = \ |

1404 | (self.graph.coors[1][component] - y_avg_graph) / r + y_avg_mds |

1405 | |

1406 | if callbackUpdateCanvas: |

1407 | callbackUpdateCanvas() |

1408 | |

1409 | def mds_callback(self, a, b=None): |

1410 | """Refresh the UI when running MDS on network components.""" |

1411 | if not self.mdsStep % self.mdsRefresh: |

1412 | self.mds_update_data(self.mdsComponentList, |

1413 | self.mds, |

1414 | self.callbackUpdateCanvas) |

1415 | |

1416 | if self.mdsType == MdsType.exactSimulation: |

1417 | self.mds.points = [[self.graph.coors[0][i], \ |

1418 | self.graph.coors[1][i]] \ |

1419 | for i in range(len(self.graph.coors))] |

1420 | self.mds.freshD = 0 |

1421 | |

1422 | if self.callbackProgress != None: |

1423 | self.callbackProgress(self.mds.avgStress, self.mdsStep) |

1424 | |

1425 | self.mdsStep += 1 |

1426 | |

1427 | if self.stopMDS: |

1428 | return 0 |

1429 | else: |

1430 | return 1 |

1431 | |

1432 | def mds_components(self, mdsSteps, mdsRefresh, callbackProgress=None, \ |

1433 | callbackUpdateCanvas=None, torgerson=0, \ |

1434 | minStressDelta=0, avgLinkage=False, rotationOnly=False,\ |

1435 | mdsType=MdsType.componentMDS, scalingRatio=0, \ |

1436 | mdsFromCurrentPos=0): |

1437 | """Position the network components according to similarities among |

1438 | them. |

1439 | |

1440 | """ |

1441 | |

1442 | if self.vertexDistance == None: |

1443 | self.information('Set distance matrix to input signal') |

1444 | return 1 |

1445 | |

1446 | if self.graph == None: |

1447 | return 1 |

1448 | |

1449 | if self.vertexDistance.dim != self.graph.nVertices: |

1450 | return 1 |

1451 | |

1452 | self.mdsComponentList = self.graph.getConnectedComponents() |

1453 | self.mdsRefresh = mdsRefresh |

1454 | self.mdsStep = 0 |

1455 | self.stopMDS = 0 |

1456 | self.vertexDistance.matrixType = Orange.core.SymMatrix.Symmetric |

1457 | self.diag_coors = math.sqrt((min(self.graph.coors[0]) - \ |

1458 | max(self.graph.coors[0]))**2 + \ |

1459 | (min(self.graph.coors[1]) - \ |

1460 | max(self.graph.coors[1]))**2) |

1461 | self.rotationOnly = rotationOnly |

1462 | self.mdsType = mdsType |

1463 | self.scalingRatio = scalingRatio |

1464 | |

1465 | w = max(self.graph.coors[0]) - min(self.graph.coors[0]) |

1466 | h = max(self.graph.coors[1]) - min(self.graph.coors[1]) |

1467 | d = math.sqrt(w**2 + h**2) |

1468 | #d = math.sqrt(w*h) |

1469 | e = [math.sqrt((self.graph.coors[0][u] - self.graph.coors[0][v])**2 + |

1470 | (self.graph.coors[1][u] - self.graph.coors[1][v])**2) for |

1471 | (u, v) in self.graph.getEdges()] |

1472 | self.mdsScaleRatio = d / sum(e) * float(len(e)) |

1473 | #print d / sum(e) * float(len(e)) |

1474 | |

1475 | if avgLinkage: |

1476 | matrix = self.vertexDistance.avgLinkage(self.mdsComponentList) |

1477 | else: |

1478 | matrix = self.vertexDistance |

1479 | |

1480 | #if self.mds == None: |

1481 | self.mds = Orange.projection.mds.MDS(matrix) |

1482 | |

1483 | if mdsFromCurrentPos: |

1484 | if avgLinkage: |

1485 | for u, c in enumerate(self.mdsComponentList): |

1486 | x = sum(self.graph.coors[0][c]) / len(c) |

1487 | y = sum(self.graph.coors[1][c]) / len(c) |

1488 | self.mds.points[u][0] = x |

1489 | self.mds.points[u][1] = y |

1490 | else: |

1491 | for u in range(self.graph.nVertices): |

1492 | self.mds.points[u][0] = self.graph.coors[0][u] |

1493 | self.mds.points[u][1] = self.graph.coors[1][u] |

1494 | |

1495 | # set min stress difference between 0.01 and 0.00001 |

1496 | self.minStressDelta = minStressDelta |

1497 | self.callbackUpdateCanvas = callbackUpdateCanvas |

1498 | self.callbackProgress = callbackProgress |

1499 | |

1500 | if torgerson: |

1501 | self.mds.Torgerson() |

1502 | |

1503 | self.mds.optimize(mdsSteps, Orange.projection.mds.SgnRelStress, self.minStressDelta,\ |

1504 | progressCallback=self.mdsCallback) |

1505 | self.mds_update_data(self.mdsComponentList, self.mds, callbackUpdateCanvas) |

1506 | |

1507 | if callbackProgress != None: |

1508 | callbackProgress(self.mds.avgStress, self.mdsStep) |

1509 | |

1510 | del self.rotationOnly |

1511 | del self.diag_coors |

1512 | del self.mdsRefresh |

1513 | del self.mdsStep |

1514 | #del self.mds |

1515 | del self.mdsComponentList |

1516 | del self.minStressDelta |

1517 | del self.callbackUpdateCanvas |

1518 | del self.callbackProgress |

1519 | del self.mdsType |

1520 | del self.mdsScaleRatio |

1521 | del self.scalingRatio |

1522 | return 0 |

1523 | |

1524 | def mds_components_avg_linkage(self, mdsSteps, mdsRefresh, \ |

1525 | callbackProgress=None, \ |

1526 | callbackUpdateCanvas=None, torgerson=0, \ |

1527 | minStressDelta = 0, scalingRatio=0,\ |

1528 | mdsFromCurrentPos=0): |

1529 | return self.mds_components(mdsSteps, mdsRefresh, callbackProgress, \ |

1530 | callbackUpdateCanvas, torgerson, \ |

1531 | minStressDelta, True, \ |

1532 | scalingRatio=scalingRatio, \ |

1533 | mdsFromCurrentPos=mdsFromCurrentPos) |

1534 | |

1535 | ########################################################################## |

1536 | ### BEGIN: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0) ### |

1537 | ########################################################################## |

1538 | |

1539 | def setNetwork(self, network): |

1540 | import warnings |

1541 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1542 | "set_network", DeprecationWarning) |

1543 | return self.set_network(network) |

1544 | |

1545 | def _computeForces(self): |

1546 | import warnings |

1547 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1548 | "_compute_forces", DeprecationWarning) |

1549 | return self._compute_forces() |

1550 | |

1551 | def getVars(self): |

1552 | import warnings |

1553 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1554 | "get_vars", DeprecationWarning) |

1555 | return self.get_vars() |

1556 | |

1557 | def getEdgeVars(self): |

1558 | import warnings |

1559 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1560 | "get_edge_vars", DeprecationWarning) |

1561 | return self.get_edge_vars() |

1562 | |

1563 | def rotateVertices(self, components, phi): |

1564 | import warnings |

1565 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1566 | "rotate_vertices", DeprecationWarning) |

1567 | return self.rotate_vertices(components, phi) |

1568 | |

1569 | def rotateComponents(self, maxSteps=100, minMoment=0.000000001, |

1570 | callbackProgress=None, callbackUpdateCanvas=None): |

1571 | import warnings |

1572 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1573 | "rotate_components", DeprecationWarning) |

1574 | return self.rotate_components(maxSteps, minMoment, |

1575 | callbackProgress, callbackUpdateCanvas) |

1576 | |

1577 | def mdsUpdateData(self, components, mds, callbackUpdateCanvas): |

1578 | import warnings |

1579 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1580 | "mds_update_data", DeprecationWarning) |

1581 | return self.mds_update_data(components, mds, |

1582 | callbackUpdateCanvas) |

1583 | |

1584 | def mdsCallback(self, a, b=None): |

1585 | import warnings |

1586 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1587 | "mds_callback", DeprecationWarning) |

1588 | return self.mds_callback(a, b) |

1589 | |

1590 | def mdsComponents(self, mdsSteps, mdsRefresh, callbackProgress=None, \ |

1591 | callbackUpdateCanvas=None, torgerson=0, \ |

1592 | minStressDelta=0, avgLinkage=False, rotationOnly=False, \ |

1593 | mdsType=MdsType.componentMDS, scalingRatio=0, \ |

1594 | mdsFromCurrentPos=0): |

1595 | import warnings |

1596 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1597 | "mds_components", DeprecationWarning) |

1598 | return self.mds_components(mdsSteps, mdsRefresh, \ |

1599 | callbackProgress, callbackUpdateCanvas, torgerson, \ |

1600 | minStressDelta, avgLinkage, rotationOnly, \ |

1601 | mdsType, scalingRatio, mdsFromCurrentPos) |

1602 | |

1603 | def mdsComponentsAvgLinkage(self, mdsSteps, mdsRefresh, \ |

1604 | callbackProgress=None, \ |

1605 | callbackUpdateCanvas=None, torgerson=0, \ |

1606 | minStressDelta = 0, scalingRatio=0,\ |

1607 | mdsFromCurrentPos=0): |

1608 | import warnings |

1609 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1610 | "mds_components_avg_linkage", DeprecationWarning) |

1611 | return self.mds_components_avg_linkage(mdsSteps, \ |

1612 | mdsRefresh, callbackProgress, callbackUpdateCanvas, \ |

1613 | torgerson, minStressDelta, scalingRatio, mdsFromCurrentPos) |

1614 | |

1615 | def getData(self, i, j): |

1616 | import warnings |

1617 | warnings.warn("Deprecated, will be deleted in Orange 3.0.", |

1618 | DeprecationWarning) |

1619 | if self.graph.items is Orange.data.Table: |

1620 | return self.data[i][j] |

1621 | elif self.graph.data is type([]): |

1622 | return self.data[i][j] |

1623 | |

1624 | def nVertices(self): |

1625 | import warnings |

1626 | warnings.warn("Deprecated, will be deleted in Orange 3.0.", |

1627 | DeprecationWarning) |

1628 | if self.graph: |

1629 | return self.graph.nVertices |

1630 | |

1631 | def saveNetwork(self, fn): |

1632 | import warnings |

1633 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1634 | "Orange.Network.save", DeprecationWarning) |

1635 | name = '' |

1636 | try: |

1637 | root, ext = os.path.splitext(fn) |

1638 | if ext == '': |

1639 | fn = root + '.net' |

1640 | |

1641 | graphFile = file(fn, 'w+') |

1642 | except IOError: |

1643 | return 1 |

1644 | |

1645 | graphFile.write('### Generated with Orange.network ### \n\n\n') |

1646 | if name == '': |

1647 | graphFile.write('*Network ' + '"no name" \n\n') |

1648 | else: |

1649 | graphFile.write('*Network ' + str(name) + ' \n\n') |

1650 | |

1651 | |

1652 | #izpis opisov vozlisc |

1653 | print "e", self.graph.nEdgeTypes |

1654 | graphFile.write('*Vertices %8d %8d\n' % (self.graph.nVertices, \ |

1655 | self.graph.nEdgeTypes)) |

1656 | for v in range(self.graph.nVertices): |

1657 | graphFile.write('% 8d ' % (v + 1)) |

1658 | # if verticesParms[v].label!='': |

1659 | # self.GraphFile.write(str('"'+ verticesParms[v].label + '"') + ' \t') |

1660 | # else: |

1661 | try: |

1662 | label = self.graph.items[v]['label'] |

1663 | graphFile.write(str('"' + str(label) + '"') + ' \t') |

1664 | except: |

1665 | graphFile.write(str('"' + str(v) + '"') + ' \t') |

1666 | |

1667 | x = self.network.coors[0][v] |

1668 | y = self.network.coors[1][v] |

1669 | #if x < 0: x = 0 |

1670 | #if x >= 1: x = 0.9999 |

1671 | #if y < 0: y = 0 |

1672 | #if y >= 1: y = 0.9999 |

1673 | z = 0.5000 |

1674 | graphFile.write('%.4f %.4f %.4f\t' % (x, y, z)) |

1675 | graphFile.write('\n') |

1676 | |

1677 | #izpis opisov povezav |

1678 | #najprej neusmerjene |

1679 | if self.graph.directed: |

1680 | graphFile.write('*Arcs \n') |

1681 | for (i, j) in self.graph.getEdges(): |

1682 | if len(self.graph[i, j]) > 0: |

1683 | graphFile.write('%8d %8d %f' % (i + 1, j + 1, \ |

1684 | float(str(self.graph[i, j])))) |

1685 | graphFile.write('\n') |

1686 | else: |

1687 | graphFile.write('*Edges \n') |

1688 | for (i, j) in self.graph.getEdges(): |

1689 | if len(self.graph[i, j]) > 0: |

1690 | graphFile.write('%8d %8d %f' % (i + 1, j + 1, \ |

1691 | float(str(self.graph[i, j])))) |

1692 | graphFile.write('\n') |

1693 | |

1694 | graphFile.write('\n') |

1695 | graphFile.close() |

1696 | |

1697 | if self.graph.items != None and len(self.graph.items) > 0: |

1698 | (name, ext) = os.path.splitext(fn) |

1699 | self.graph.items.save(name + "_items.tab") |

1700 | |

1701 | if self.graph.links != None and len(self.graph.links) > 0: |

1702 | (name, ext) = os.path.splitext(fn) |

1703 | self.graph.links.save(name + "_links.tab") |

1704 | |

1705 | return 0 |

1706 | |

1707 | def readNetwork(self, fn, directed=0): |

1708 | import warnings |

1709 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1710 | "Orange.Network.read", DeprecationWarning) |

1711 | network = Network(1,directed) |

1712 | net = network.readPajek(fn, directed) |

1713 | self.setGraph(net) |

1714 | self.graph = net |

1715 | return net |

1716 | |

1717 | ########################################################################## |

1718 | ### END: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0) ### |

1719 | ########################################################################## |

1720 | |

1721 | class NetworkClustering(): |

1722 | |

1723 | """A collection of algorithms for community detection in graphs. |

1724 | |

1725 | :param network: network data for community detection |

1726 | :type network: Orange.network.Network |

1727 | """ |

1728 | |

1729 | random.seed(0) |

1730 | |

1731 | def __init__(self, network): |

1732 | self.net = network |

1733 | |

1734 | |

1735 | def label_propagation(self, results2items=0, resultHistory2items=0): |

1736 | """Label propagation method from Raghavan et al., 2007 |

1737 | |

1738 | :param results2items: append a new feature result to items |

1739 | (Orange.data.Table) |

1740 | :type results2items: bool |

1741 | :param resultHistory2items: append new features result to items |

1742 | (Orange.data.Table) after each iteration of the algorithm |

1743 | :type resultHistory2items: bool |

1744 | """ |

1745 | |

1746 | vertices = range(self.net.nVertices) |

1747 | labels = range(self.net.nVertices) |

1748 | lblhistory = [] |

1749 | #consecutiveStop = 0 |

1750 | for i in range(1000): |

1751 | random.shuffle(vertices) |

1752 | stop = 1 |

1753 | for v in vertices: |

1754 | nbh = self.net.get_neighbours(v) |

1755 | if len(nbh) == 0: |

1756 | continue |

1757 | |

1758 | lbls = [labels[u] for u in nbh] |

1759 | lbls = [(len(list(c)), l) for l, c in itertools.groupby(lbls)] |

1760 | m = max(lbls)[0] |

1761 | mlbls = [l for c, l in lbls if c >= m] |

1762 | lbl = random.choice(mlbls) |

1763 | |

1764 | if labels[v] not in mlbls: stop = 0 |

1765 | labels[v] = lbl |

1766 | |

1767 | lblhistory.append([str(l) for l in labels]) |

1768 | # if stopping condition might be satisfied, check it |

1769 | if stop: |

1770 | for v in vertices: |

1771 | nbh = self.net.get_neighbours(v) |

1772 | if len(nbh) == 0: continue |

1773 | lbls = [labels[u] for u in nbh] |

1774 | lbls = [(len(list(c)), l) for l, c \ |

1775 | in itertools.groupby(lbls)] |

1776 | m = max(lbls)[0] |

1777 | mlbls = [l for c, l in lbls if c >= m] |

1778 | if labels[v] not in mlbls: |

1779 | stop = 0 |

1780 | break |

1781 | if stop: break |

1782 | |

1783 | if results2items and not resultHistory2items: |

1784 | attrs = [Orange.data.variable.Discrete( |

1785 | 'clustering label propagation', |

1786 | values=list(set([l for l \ |

1787 | in lblhistory[-1]])))] |

1788 | dom = Orange.data.Domain(attrs, 0) |

1789 | data = Orange.data.Table(dom, [[l] for l in lblhistory[-1]]) |

1790 | if self.net.items is None: |

1791 | self.net.items = data |

1792 | else: |

1793 | self.net.items = Orange.data.Table([self.net.items, data]) |

1794 | if resultHistory2items: |

1795 | attrs = [Orange.data.variable.Discrete('c'+ str(i), |

1796 | values=list(set([l for l in lblhistory[0]]))) for i,labels \ |

1797 | in enumerate(lblhistory)] |

1798 | dom = Orange.data.Domain(attrs, 0) |

1799 | # transpose history |

1800 | data = map(list, zip(*lblhistory)) |

1801 | data = Orange.data.Table(dom, data) |

1802 | if self.net.items is None: |

1803 | self.net.items = data |

1804 | else: |

1805 | self.net.items = Orange.data.Table([self.net.items, data]) |

1806 | |

1807 | return labels |

1808 | |

1809 | ########################################################################## |

1810 | ### BEGIN: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0) ### |

1811 | ########################################################################## |

1812 | |

1813 | def labelPropagation(self, results2items=0, resultHistory2items=0): |

1814 | import warnings |

1815 | warnings.warn("Deprecated, will be deleted in Orange 3.0. Use %s" % \ |

1816 | "label_propagation", DeprecationWarning) |

1817 | return self.label_propagation(results2items=0, resultHistory2items=0) |

1818 | |

1819 | ########################################################################## |

1820 | ### END: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0) ### |

1821 | ########################################################################## |

**Note:**See TracBrowser for help on using the repository browser.