Mercurial > repos > guerler > springsuite
comparison planemo/lib/python3.7/site-packages/networkx/algorithms/triads.py @ 1:56ad4e20f292 draft
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author | guerler |
---|---|
date | Fri, 31 Jul 2020 00:32:28 -0400 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
0:d30785e31577 | 1:56ad4e20f292 |
---|---|
1 # triads.py - functions for analyzing triads of a graph | |
2 # | |
3 # Copyright 2015 NetworkX developers. | |
4 # Copyright 2011 Reya Group <http://www.reyagroup.com> | |
5 # Copyright 2011 Alex Levenson <alex@isnotinvain.com> | |
6 # Copyright 2011 Diederik van Liere <diederik.vanliere@rotman.utoronto.ca> | |
7 # | |
8 # This file is part of NetworkX. | |
9 # | |
10 # NetworkX is distributed under a BSD license; see LICENSE.txt for more | |
11 # information. | |
12 """Functions for analyzing triads of a graph.""" | |
13 | |
14 from networkx.utils import not_implemented_for | |
15 | |
16 __author__ = '\n'.join(['Alex Levenson (alex@isnontinvain.com)', | |
17 'Diederik van Liere (diederik.vanliere@rotman.utoronto.ca)']) | |
18 | |
19 __all__ = ['triadic_census'] | |
20 | |
21 #: The integer codes representing each type of triad. | |
22 #: | |
23 #: Triads that are the same up to symmetry have the same code. | |
24 TRICODES = (1, 2, 2, 3, 2, 4, 6, 8, 2, 6, 5, 7, 3, 8, 7, 11, 2, 6, 4, 8, 5, 9, | |
25 9, 13, 6, 10, 9, 14, 7, 14, 12, 15, 2, 5, 6, 7, 6, 9, 10, 14, 4, 9, | |
26 9, 12, 8, 13, 14, 15, 3, 7, 8, 11, 7, 12, 14, 15, 8, 14, 13, 15, | |
27 11, 15, 15, 16) | |
28 | |
29 #: The names of each type of triad. The order of the elements is | |
30 #: important: it corresponds to the tricodes given in :data:`TRICODES`. | |
31 TRIAD_NAMES = ('003', '012', '102', '021D', '021U', '021C', '111D', '111U', | |
32 '030T', '030C', '201', '120D', '120U', '120C', '210', '300') | |
33 | |
34 | |
35 #: A dictionary mapping triad code to triad name. | |
36 TRICODE_TO_NAME = {i: TRIAD_NAMES[code - 1] for i, code in enumerate(TRICODES)} | |
37 | |
38 | |
39 def _tricode(G, v, u, w): | |
40 """Returns the integer code of the given triad. | |
41 | |
42 This is some fancy magic that comes from Batagelj and Mrvar's paper. It | |
43 treats each edge joining a pair of `v`, `u`, and `w` as a bit in | |
44 the binary representation of an integer. | |
45 | |
46 """ | |
47 combos = ((v, u, 1), (u, v, 2), (v, w, 4), (w, v, 8), (u, w, 16), | |
48 (w, u, 32)) | |
49 return sum(x for u, v, x in combos if v in G[u]) | |
50 | |
51 | |
52 @not_implemented_for('undirected') | |
53 def triadic_census(G): | |
54 """Determines the triadic census of a directed graph. | |
55 | |
56 The triadic census is a count of how many of the 16 possible types of | |
57 triads are present in a directed graph. | |
58 | |
59 Parameters | |
60 ---------- | |
61 G : digraph | |
62 A NetworkX DiGraph | |
63 | |
64 Returns | |
65 ------- | |
66 census : dict | |
67 Dictionary with triad names as keys and number of occurrences as values. | |
68 | |
69 Notes | |
70 ----- | |
71 This algorithm has complexity $O(m)$ where $m$ is the number of edges in | |
72 the graph. | |
73 | |
74 See also | |
75 -------- | |
76 triad_graph | |
77 | |
78 References | |
79 ---------- | |
80 .. [1] Vladimir Batagelj and Andrej Mrvar, A subquadratic triad census | |
81 algorithm for large sparse networks with small maximum degree, | |
82 University of Ljubljana, | |
83 http://vlado.fmf.uni-lj.si/pub/networks/doc/triads/triads.pdf | |
84 | |
85 """ | |
86 # Initialize the count for each triad to be zero. | |
87 census = {name: 0 for name in TRIAD_NAMES} | |
88 n = len(G) | |
89 # m = dict(zip(G, range(n))) | |
90 m = {v: i for i, v in enumerate(G)} | |
91 for v in G: | |
92 vnbrs = set(G.pred[v]) | set(G.succ[v]) | |
93 for u in vnbrs: | |
94 if m[u] <= m[v]: | |
95 continue | |
96 neighbors = (vnbrs | set(G.succ[u]) | set(G.pred[u])) - {u, v} | |
97 # Calculate dyadic triads instead of counting them. | |
98 if v in G[u] and u in G[v]: | |
99 census['102'] += n - len(neighbors) - 2 | |
100 else: | |
101 census['012'] += n - len(neighbors) - 2 | |
102 # Count connected triads. | |
103 for w in neighbors: | |
104 if m[u] < m[w] or (m[v] < m[w] < m[u] and | |
105 v not in G.pred[w] and | |
106 v not in G.succ[w]): | |
107 code = _tricode(G, v, u, w) | |
108 census[TRICODE_TO_NAME[code]] += 1 | |
109 | |
110 # null triads = total number of possible triads - all found triads | |
111 # | |
112 # Use integer division here, since we know this formula guarantees an | |
113 # integral value. | |
114 census['003'] = ((n * (n - 1) * (n - 2)) // 6) - sum(census.values()) | |
115 return census |