Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/triads.py: 21%
146 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1# See https://github.com/networkx/networkx/pull/1474
2# Copyright 2011 Reya Group <http://www.reyagroup.com>
3# Copyright 2011 Alex Levenson <alex@isnotinvain.com>
4# Copyright 2011 Diederik van Liere <diederik.vanliere@rotman.utoronto.ca>
5"""Functions for analyzing triads of a graph."""
7from collections import defaultdict
8from itertools import combinations, permutations
10import networkx as nx
11from networkx.utils import not_implemented_for, py_random_state
13__all__ = [
14 "triadic_census",
15 "is_triad",
16 "all_triplets",
17 "all_triads",
18 "triads_by_type",
19 "triad_type",
20 "random_triad",
21]
23#: The integer codes representing each type of triad.
24#:
25#: Triads that are the same up to symmetry have the same code.
26TRICODES = (
27 1,
28 2,
29 2,
30 3,
31 2,
32 4,
33 6,
34 8,
35 2,
36 6,
37 5,
38 7,
39 3,
40 8,
41 7,
42 11,
43 2,
44 6,
45 4,
46 8,
47 5,
48 9,
49 9,
50 13,
51 6,
52 10,
53 9,
54 14,
55 7,
56 14,
57 12,
58 15,
59 2,
60 5,
61 6,
62 7,
63 6,
64 9,
65 10,
66 14,
67 4,
68 9,
69 9,
70 12,
71 8,
72 13,
73 14,
74 15,
75 3,
76 7,
77 8,
78 11,
79 7,
80 12,
81 14,
82 15,
83 8,
84 14,
85 13,
86 15,
87 11,
88 15,
89 15,
90 16,
91)
93#: The names of each type of triad. The order of the elements is
94#: important: it corresponds to the tricodes given in :data:`TRICODES`.
95TRIAD_NAMES = (
96 "003",
97 "012",
98 "102",
99 "021D",
100 "021U",
101 "021C",
102 "111D",
103 "111U",
104 "030T",
105 "030C",
106 "201",
107 "120D",
108 "120U",
109 "120C",
110 "210",
111 "300",
112)
115#: A dictionary mapping triad code to triad name.
116TRICODE_TO_NAME = {i: TRIAD_NAMES[code - 1] for i, code in enumerate(TRICODES)}
119def _tricode(G, v, u, w):
120 """Returns the integer code of the given triad.
122 This is some fancy magic that comes from Batagelj and Mrvar's paper. It
123 treats each edge joining a pair of `v`, `u`, and `w` as a bit in
124 the binary representation of an integer.
126 """
127 combos = ((v, u, 1), (u, v, 2), (v, w, 4), (w, v, 8), (u, w, 16), (w, u, 32))
128 return sum(x for u, v, x in combos if v in G[u])
131@not_implemented_for("undirected")
132@nx._dispatch
133def triadic_census(G, nodelist=None):
134 """Determines the triadic census of a directed graph.
136 The triadic census is a count of how many of the 16 possible types of
137 triads are present in a directed graph. If a list of nodes is passed, then
138 only those triads are taken into account which have elements of nodelist in them.
140 Parameters
141 ----------
142 G : digraph
143 A NetworkX DiGraph
144 nodelist : list
145 List of nodes for which you want to calculate triadic census
147 Returns
148 -------
149 census : dict
150 Dictionary with triad type as keys and number of occurrences as values.
152 Examples
153 --------
154 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1), (3, 4), (4, 1), (4, 2)])
155 >>> triadic_census = nx.triadic_census(G)
156 >>> for key, value in triadic_census.items():
157 ... print(f"{key}: {value}")
158 ...
159 003: 0
160 012: 0
161 102: 0
162 021D: 0
163 021U: 0
164 021C: 0
165 111D: 0
166 111U: 0
167 030T: 2
168 030C: 2
169 201: 0
170 120D: 0
171 120U: 0
172 120C: 0
173 210: 0
174 300: 0
176 Notes
177 -----
178 This algorithm has complexity $O(m)$ where $m$ is the number of edges in
179 the graph.
181 Raises
182 ------
183 ValueError
184 If `nodelist` contains duplicate nodes or nodes not in `G`.
185 If you want to ignore this you can preprocess with `set(nodelist) & G.nodes`
187 See also
188 --------
189 triad_graph
191 References
192 ----------
193 .. [1] Vladimir Batagelj and Andrej Mrvar, A subquadratic triad census
194 algorithm for large sparse networks with small maximum degree,
195 University of Ljubljana,
196 http://vlado.fmf.uni-lj.si/pub/networks/doc/triads/triads.pdf
198 """
199 nodeset = set(G.nbunch_iter(nodelist))
200 if nodelist is not None and len(nodelist) != len(nodeset):
201 raise ValueError("nodelist includes duplicate nodes or nodes not in G")
203 N = len(G)
204 Nnot = N - len(nodeset) # can signal special counting for subset of nodes
206 # create an ordering of nodes with nodeset nodes first
207 m = {n: i for i, n in enumerate(nodeset)}
208 if Nnot:
209 # add non-nodeset nodes later in the ordering
210 not_nodeset = G.nodes - nodeset
211 m.update((n, i + N) for i, n in enumerate(not_nodeset))
213 # build all_neighbor dicts for easy counting
214 # After Python 3.8 can leave off these keys(). Speedup also using G._pred
215 # nbrs = {n: G._pred[n].keys() | G._succ[n].keys() for n in G}
216 nbrs = {n: G.pred[n].keys() | G.succ[n].keys() for n in G}
217 dbl_nbrs = {n: G.pred[n].keys() & G.succ[n].keys() for n in G}
219 if Nnot:
220 sgl_nbrs = {n: G.pred[n].keys() ^ G.succ[n].keys() for n in not_nodeset}
221 # find number of edges not incident to nodes in nodeset
222 sgl = sum(1 for n in not_nodeset for nbr in sgl_nbrs[n] if nbr not in nodeset)
223 sgl_edges_outside = sgl // 2
224 dbl = sum(1 for n in not_nodeset for nbr in dbl_nbrs[n] if nbr not in nodeset)
225 dbl_edges_outside = dbl // 2
227 # Initialize the count for each triad to be zero.
228 census = {name: 0 for name in TRIAD_NAMES}
229 # Main loop over nodes
230 for v in nodeset:
231 vnbrs = nbrs[v]
232 dbl_vnbrs = dbl_nbrs[v]
233 if Nnot:
234 # set up counts of edges attached to v.
235 sgl_unbrs_bdy = sgl_unbrs_out = dbl_unbrs_bdy = dbl_unbrs_out = 0
236 for u in vnbrs:
237 if m[u] <= m[v]:
238 continue
239 unbrs = nbrs[u]
240 neighbors = (vnbrs | unbrs) - {u, v}
241 # Count connected triads.
242 for w in neighbors:
243 if m[u] < m[w] or (m[v] < m[w] < m[u] and v not in nbrs[w]):
244 code = _tricode(G, v, u, w)
245 census[TRICODE_TO_NAME[code]] += 1
247 # Use a formula for dyadic triads with edge incident to v
248 if u in dbl_vnbrs:
249 census["102"] += N - len(neighbors) - 2
250 else:
251 census["012"] += N - len(neighbors) - 2
253 # Count edges attached to v. Subtract later to get triads with v isolated
254 # _out are (u,unbr) for unbrs outside boundary of nodeset
255 # _bdy are (u,unbr) for unbrs on boundary of nodeset (get double counted)
256 if Nnot and u not in nodeset:
257 sgl_unbrs = sgl_nbrs[u]
258 sgl_unbrs_bdy += len(sgl_unbrs & vnbrs - nodeset)
259 sgl_unbrs_out += len(sgl_unbrs - vnbrs - nodeset)
260 dbl_unbrs = dbl_nbrs[u]
261 dbl_unbrs_bdy += len(dbl_unbrs & vnbrs - nodeset)
262 dbl_unbrs_out += len(dbl_unbrs - vnbrs - nodeset)
263 # if nodeset == G.nodes, skip this b/c we will find the edge later.
264 if Nnot:
265 # Count edges outside nodeset not connected with v (v isolated triads)
266 census["012"] += sgl_edges_outside - (sgl_unbrs_out + sgl_unbrs_bdy // 2)
267 census["102"] += dbl_edges_outside - (dbl_unbrs_out + dbl_unbrs_bdy // 2)
269 # calculate null triads: "003"
270 # null triads = total number of possible triads - all found triads
271 total_triangles = (N * (N - 1) * (N - 2)) // 6
272 triangles_without_nodeset = (Nnot * (Nnot - 1) * (Nnot - 2)) // 6
273 total_census = total_triangles - triangles_without_nodeset
274 census["003"] = total_census - sum(census.values())
276 return census
279@nx._dispatch
280def is_triad(G):
281 """Returns True if the graph G is a triad, else False.
283 Parameters
284 ----------
285 G : graph
286 A NetworkX Graph
288 Returns
289 -------
290 istriad : boolean
291 Whether G is a valid triad
293 Examples
294 --------
295 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1)])
296 >>> nx.is_triad(G)
297 True
298 >>> G.add_edge(0, 1)
299 >>> nx.is_triad(G)
300 False
301 """
302 if isinstance(G, nx.Graph):
303 if G.order() == 3 and nx.is_directed(G):
304 if not any((n, n) in G.edges() for n in G.nodes()):
305 return True
306 return False
309@not_implemented_for("undirected")
310@nx._dispatch
311def all_triplets(G):
312 """Returns a generator of all possible sets of 3 nodes in a DiGraph.
314 Parameters
315 ----------
316 G : digraph
317 A NetworkX DiGraph
319 Returns
320 -------
321 triplets : generator of 3-tuples
322 Generator of tuples of 3 nodes
324 Examples
325 --------
326 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 4)])
327 >>> list(nx.all_triplets(G))
328 [(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
330 """
331 triplets = combinations(G.nodes(), 3)
332 return triplets
335@not_implemented_for("undirected")
336@nx._dispatch
337def all_triads(G):
338 """A generator of all possible triads in G.
340 Parameters
341 ----------
342 G : digraph
343 A NetworkX DiGraph
345 Returns
346 -------
347 all_triads : generator of DiGraphs
348 Generator of triads (order-3 DiGraphs)
350 Examples
351 --------
352 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1), (3, 4), (4, 1), (4, 2)])
353 >>> for triad in nx.all_triads(G):
354 ... print(triad.edges)
355 [(1, 2), (2, 3), (3, 1)]
356 [(1, 2), (4, 1), (4, 2)]
357 [(3, 1), (3, 4), (4, 1)]
358 [(2, 3), (3, 4), (4, 2)]
360 """
361 triplets = combinations(G.nodes(), 3)
362 for triplet in triplets:
363 yield G.subgraph(triplet).copy()
366@not_implemented_for("undirected")
367@nx._dispatch
368def triads_by_type(G):
369 """Returns a list of all triads for each triad type in a directed graph.
370 There are exactly 16 different types of triads possible. Suppose 1, 2, 3 are three
371 nodes, they will be classified as a particular triad type if their connections
372 are as follows:
374 - 003: 1, 2, 3
375 - 012: 1 -> 2, 3
376 - 102: 1 <-> 2, 3
377 - 021D: 1 <- 2 -> 3
378 - 021U: 1 -> 2 <- 3
379 - 021C: 1 -> 2 -> 3
380 - 111D: 1 <-> 2 <- 3
381 - 111U: 1 <-> 2 -> 3
382 - 030T: 1 -> 2 -> 3, 1 -> 3
383 - 030C: 1 <- 2 <- 3, 1 -> 3
384 - 201: 1 <-> 2 <-> 3
385 - 120D: 1 <- 2 -> 3, 1 <-> 3
386 - 120U: 1 -> 2 <- 3, 1 <-> 3
387 - 120C: 1 -> 2 -> 3, 1 <-> 3
388 - 210: 1 -> 2 <-> 3, 1 <-> 3
389 - 300: 1 <-> 2 <-> 3, 1 <-> 3
391 Refer to the :doc:`example gallery </auto_examples/graph/plot_triad_types>`
392 for visual examples of the triad types.
394 Parameters
395 ----------
396 G : digraph
397 A NetworkX DiGraph
399 Returns
400 -------
401 tri_by_type : dict
402 Dictionary with triad types as keys and lists of triads as values.
404 Examples
405 --------
406 >>> G = nx.DiGraph([(1, 2), (1, 3), (2, 3), (3, 1), (5, 6), (5, 4), (6, 7)])
407 >>> dict = nx.triads_by_type(G)
408 >>> dict['120C'][0].edges()
409 OutEdgeView([(1, 2), (1, 3), (2, 3), (3, 1)])
410 >>> dict['012'][0].edges()
411 OutEdgeView([(1, 2)])
413 References
414 ----------
415 .. [1] Snijders, T. (2012). "Transitivity and triads." University of
416 Oxford.
417 https://web.archive.org/web/20170830032057/http://www.stats.ox.ac.uk/~snijders/Trans_Triads_ha.pdf
418 """
419 # num_triads = o * (o - 1) * (o - 2) // 6
420 # if num_triads > TRIAD_LIMIT: print(WARNING)
421 all_tri = all_triads(G)
422 tri_by_type = defaultdict(list)
423 for triad in all_tri:
424 name = triad_type(triad)
425 tri_by_type[name].append(triad)
426 return tri_by_type
429@not_implemented_for("undirected")
430@nx._dispatch
431def triad_type(G):
432 """Returns the sociological triad type for a triad.
434 Parameters
435 ----------
436 G : digraph
437 A NetworkX DiGraph with 3 nodes
439 Returns
440 -------
441 triad_type : str
442 A string identifying the triad type
444 Examples
445 --------
446 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1)])
447 >>> nx.triad_type(G)
448 '030C'
449 >>> G.add_edge(1, 3)
450 >>> nx.triad_type(G)
451 '120C'
453 Notes
454 -----
455 There can be 6 unique edges in a triad (order-3 DiGraph) (so 2^^6=64 unique
456 triads given 3 nodes). These 64 triads each display exactly 1 of 16
457 topologies of triads (topologies can be permuted). These topologies are
458 identified by the following notation:
460 {m}{a}{n}{type} (for example: 111D, 210, 102)
462 Here:
464 {m} = number of mutual ties (takes 0, 1, 2, 3); a mutual tie is (0,1)
465 AND (1,0)
466 {a} = number of asymmetric ties (takes 0, 1, 2, 3); an asymmetric tie
467 is (0,1) BUT NOT (1,0) or vice versa
468 {n} = number of null ties (takes 0, 1, 2, 3); a null tie is NEITHER
469 (0,1) NOR (1,0)
470 {type} = a letter (takes U, D, C, T) corresponding to up, down, cyclical
471 and transitive. This is only used for topologies that can have
472 more than one form (eg: 021D and 021U).
474 References
475 ----------
476 .. [1] Snijders, T. (2012). "Transitivity and triads." University of
477 Oxford.
478 https://web.archive.org/web/20170830032057/http://www.stats.ox.ac.uk/~snijders/Trans_Triads_ha.pdf
479 """
480 if not is_triad(G):
481 raise nx.NetworkXAlgorithmError("G is not a triad (order-3 DiGraph)")
482 num_edges = len(G.edges())
483 if num_edges == 0:
484 return "003"
485 elif num_edges == 1:
486 return "012"
487 elif num_edges == 2:
488 e1, e2 = G.edges()
489 if set(e1) == set(e2):
490 return "102"
491 elif e1[0] == e2[0]:
492 return "021D"
493 elif e1[1] == e2[1]:
494 return "021U"
495 elif e1[1] == e2[0] or e2[1] == e1[0]:
496 return "021C"
497 elif num_edges == 3:
498 for e1, e2, e3 in permutations(G.edges(), 3):
499 if set(e1) == set(e2):
500 if e3[0] in e1:
501 return "111U"
502 # e3[1] in e1:
503 return "111D"
504 elif set(e1).symmetric_difference(set(e2)) == set(e3):
505 if {e1[0], e2[0], e3[0]} == {e1[0], e2[0], e3[0]} == set(G.nodes()):
506 return "030C"
507 # e3 == (e1[0], e2[1]) and e2 == (e1[1], e3[1]):
508 return "030T"
509 elif num_edges == 4:
510 for e1, e2, e3, e4 in permutations(G.edges(), 4):
511 if set(e1) == set(e2):
512 # identify pair of symmetric edges (which necessarily exists)
513 if set(e3) == set(e4):
514 return "201"
515 if {e3[0]} == {e4[0]} == set(e3).intersection(set(e4)):
516 return "120D"
517 if {e3[1]} == {e4[1]} == set(e3).intersection(set(e4)):
518 return "120U"
519 if e3[1] == e4[0]:
520 return "120C"
521 elif num_edges == 5:
522 return "210"
523 elif num_edges == 6:
524 return "300"
527@not_implemented_for("undirected")
528@py_random_state(1)
529@nx._dispatch
530def random_triad(G, seed=None):
531 """Returns a random triad from a directed graph.
533 Parameters
534 ----------
535 G : digraph
536 A NetworkX DiGraph
537 seed : integer, random_state, or None (default)
538 Indicator of random number generation state.
539 See :ref:`Randomness<randomness>`.
541 Returns
542 -------
543 G2 : subgraph
544 A randomly selected triad (order-3 NetworkX DiGraph)
546 Raises
547 ------
548 NetworkXError
549 If the input Graph has less than 3 nodes.
551 Examples
552 --------
553 >>> G = nx.DiGraph([(1, 2), (1, 3), (2, 3), (3, 1), (5, 6), (5, 4), (6, 7)])
554 >>> triad = nx.random_triad(G, seed=1)
555 >>> triad.edges
556 OutEdgeView([(1, 2)])
558 """
559 if len(G) < 3:
560 raise nx.NetworkXError(
561 f"G needs at least 3 nodes to form a triad; (it has {len(G)} nodes)"
562 )
563 nodes = seed.sample(list(G.nodes()), 3)
564 G2 = G.subgraph(nodes)
565 return G2