Mercurial > repos > shellac > sam_consensus_v3
diff env/lib/python3.9/site-packages/networkx/algorithms/triads.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/env/lib/python3.9/site-packages/networkx/algorithms/triads.py Mon Mar 22 18:12:50 2021 +0000 @@ -0,0 +1,440 @@ +# See https://github.com/networkx/networkx/pull/1474 +# Copyright 2011 Reya Group <http://www.reyagroup.com> +# Copyright 2011 Alex Levenson <alex@isnotinvain.com> +# Copyright 2011 Diederik van Liere <diederik.vanliere@rotman.utoronto.ca> +"""Functions for analyzing triads of a graph.""" + +from itertools import combinations, permutations +from collections import defaultdict +from random import sample + +import networkx as nx +from networkx.utils import not_implemented_for + +__all__ = [ + "triadic_census", + "is_triad", + "all_triplets", + "all_triads", + "triads_by_type", + "triad_type", + "random_triad", +] + +#: The integer codes representing each type of triad. +#: +#: Triads that are the same up to symmetry have the same code. +TRICODES = ( + 1, + 2, + 2, + 3, + 2, + 4, + 6, + 8, + 2, + 6, + 5, + 7, + 3, + 8, + 7, + 11, + 2, + 6, + 4, + 8, + 5, + 9, + 9, + 13, + 6, + 10, + 9, + 14, + 7, + 14, + 12, + 15, + 2, + 5, + 6, + 7, + 6, + 9, + 10, + 14, + 4, + 9, + 9, + 12, + 8, + 13, + 14, + 15, + 3, + 7, + 8, + 11, + 7, + 12, + 14, + 15, + 8, + 14, + 13, + 15, + 11, + 15, + 15, + 16, +) + +#: The names of each type of triad. The order of the elements is +#: important: it corresponds to the tricodes given in :data:`TRICODES`. +TRIAD_NAMES = ( + "003", + "012", + "102", + "021D", + "021U", + "021C", + "111D", + "111U", + "030T", + "030C", + "201", + "120D", + "120U", + "120C", + "210", + "300", +) + + +#: A dictionary mapping triad code to triad name. +TRICODE_TO_NAME = {i: TRIAD_NAMES[code - 1] for i, code in enumerate(TRICODES)} + + +def _tricode(G, v, u, w): + """Returns the integer code of the given triad. + + This is some fancy magic that comes from Batagelj and Mrvar's paper. It + treats each edge joining a pair of `v`, `u`, and `w` as a bit in + the binary representation of an integer. + + """ + combos = ((v, u, 1), (u, v, 2), (v, w, 4), (w, v, 8), (u, w, 16), (w, u, 32)) + return sum(x for u, v, x in combos if v in G[u]) + + +@not_implemented_for("undirected") +def triadic_census(G): + """Determines the triadic census of a directed graph. + + The triadic census is a count of how many of the 16 possible types of + triads are present in a directed graph. + + Parameters + ---------- + G : digraph + A NetworkX DiGraph + + Returns + ------- + census : dict + Dictionary with triad type as keys and number of occurrences as values. + + Notes + ----- + This algorithm has complexity $O(m)$ where $m$ is the number of edges in + the graph. + + See also + -------- + triad_graph + + References + ---------- + .. [1] Vladimir Batagelj and Andrej Mrvar, A subquadratic triad census + algorithm for large sparse networks with small maximum degree, + University of Ljubljana, + http://vlado.fmf.uni-lj.si/pub/networks/doc/triads/triads.pdf + + """ + # Initialize the count for each triad to be zero. + census = {name: 0 for name in TRIAD_NAMES} + n = len(G) + # m = dict(zip(G, range(n))) + m = {v: i for i, v in enumerate(G)} + for v in G: + vnbrs = set(G.pred[v]) | set(G.succ[v]) + for u in vnbrs: + if m[u] <= m[v]: + continue + neighbors = (vnbrs | set(G.succ[u]) | set(G.pred[u])) - {u, v} + # Calculate dyadic triads instead of counting them. + if v in G[u] and u in G[v]: + census["102"] += n - len(neighbors) - 2 + else: + census["012"] += n - len(neighbors) - 2 + # Count connected triads. + for w in neighbors: + if m[u] < m[w] or ( + m[v] < m[w] < m[u] and v not in G.pred[w] and v not in G.succ[w] + ): + code = _tricode(G, v, u, w) + census[TRICODE_TO_NAME[code]] += 1 + # null triads = total number of possible triads - all found triads + # + # Use integer division here, since we know this formula guarantees an + # integral value. + census["003"] = ((n * (n - 1) * (n - 2)) // 6) - sum(census.values()) + return census + + +def is_triad(G): + """Returns True if the graph G is a triad, else False. + + Parameters + ---------- + G : graph + A NetworkX Graph + + Returns + ------- + istriad : boolean + Whether G is a valid triad + """ + if isinstance(G, nx.Graph): + if G.order() == 3 and nx.is_directed(G): + if not any((n, n) in G.edges() for n in G.nodes()): + return True + return False + + +@not_implemented_for("undirected") +def all_triplets(G): + """Returns a generator of all possible sets of 3 nodes in a DiGraph. + + Parameters + ---------- + G : digraph + A NetworkX DiGraph + + Returns + ------- + triplets : generator of 3-tuples + Generator of tuples of 3 nodes + """ + triplets = combinations(G.nodes(), 3) + return triplets + + +@not_implemented_for("undirected") +def all_triads(G): + """A generator of all possible triads in G. + + Parameters + ---------- + G : digraph + A NetworkX DiGraph + + Returns + ------- + all_triads : generator of DiGraphs + Generator of triads (order-3 DiGraphs) + """ + triplets = combinations(G.nodes(), 3) + for triplet in triplets: + yield G.subgraph(triplet).copy() + + +@not_implemented_for("undirected") +def triads_by_type(G): + """Returns a list of all triads for each triad type in a directed graph. + + Parameters + ---------- + G : digraph + A NetworkX DiGraph + + Returns + ------- + tri_by_type : dict + Dictionary with triad types as keys and lists of triads as values. + """ + # num_triads = o * (o - 1) * (o - 2) // 6 + # if num_triads > TRIAD_LIMIT: print(WARNING) + all_tri = all_triads(G) + tri_by_type = defaultdict(list) + for triad in all_tri: + name = triad_type(triad) + tri_by_type[name].append(triad) + return tri_by_type + + +@not_implemented_for("undirected") +def triad_type(G): + """Returns the sociological triad type for a triad. + + Parameters + ---------- + G : digraph + A NetworkX DiGraph with 3 nodes + + Returns + ------- + triad_type : str + A string identifying the triad type + + Notes + ----- + There can be 6 unique edges in a triad (order-3 DiGraph) (so 2^^6=64 unique + triads given 3 nodes). These 64 triads each display exactly 1 of 16 + topologies of triads (topologies can be permuted). These topologies are + identified by the following notation: + + {m}{a}{n}{type} (for example: 111D, 210, 102) + + Here: + + {m} = number of mutual ties (takes 0, 1, 2, 3); a mutual tie is (0,1) + AND (1,0) + {a} = number of assymmetric ties (takes 0, 1, 2, 3); an assymmetric tie + is (0,1) BUT NOT (1,0) or vice versa + {n} = number of null ties (takes 0, 1, 2, 3); a null tie is NEITHER + (0,1) NOR (1,0) + {type} = a letter (takes U, D, C, T) corresponding to up, down, cyclical + and transitive. This is only used for topologies that can have + more than one form (eg: 021D and 021U). + + References + ---------- + .. [1] Snijders, T. (2012). "Transitivity and triads." University of + Oxford. + http://www.stats.ox.ac.uk/snijders/Trans_Triads_ha.pdf + """ + if not is_triad(G): + raise nx.NetworkXAlgorithmError("G is not a triad (order-3 DiGraph)") + num_edges = len(G.edges()) + if num_edges == 0: + return "003" + elif num_edges == 1: + return "012" + elif num_edges == 2: + e1, e2 = G.edges() + if set(e1) == set(e2): + return "102" + elif e1[0] == e2[0]: + return "021D" + elif e1[1] == e2[1]: + return "021U" + elif e1[1] == e2[0] or e2[1] == e1[0]: + return "021C" + elif num_edges == 3: + for (e1, e2, e3) in permutations(G.edges(), 3): + if set(e1) == set(e2): + if e3[0] in e1: + return "111U" + # e3[1] in e1: + return "111D" + elif set(e1).symmetric_difference(set(e2)) == set(e3): + if {e1[0], e2[0], e3[0]} == {e1[0], e2[0], e3[0]} == set(G.nodes()): + return "030C" + # e3 == (e1[0], e2[1]) and e2 == (e1[1], e3[1]): + return "030T" + elif num_edges == 4: + for (e1, e2, e3, e4) in permutations(G.edges(), 4): + if set(e1) == set(e2): + # identify pair of symmetric edges (which necessarily exists) + if set(e3) == set(e4): + return "201" + if {e3[0]} == {e4[0]} == set(e3).intersection(set(e4)): + return "120D" + if {e3[1]} == {e4[1]} == set(e3).intersection(set(e4)): + return "120U" + if e3[1] == e4[0]: + return "120C" + elif num_edges == 5: + return "210" + elif num_edges == 6: + return "300" + + +@not_implemented_for("undirected") +def random_triad(G): + """Returns a random triad from a directed graph. + + Parameters + ---------- + G : digraph + A NetworkX DiGraph + + Returns + ------- + G2 : subgraph + A randomly selected triad (order-3 NetworkX DiGraph) + """ + nodes = sample(G.nodes(), 3) + G2 = G.subgraph(nodes) + return G2 + + +""" +@not_implemented_for('undirected') +def triadic_closures(G): + '''Returns a list of order-3 subgraphs of G that are triadic closures. + + Parameters + ---------- + G : digraph + A NetworkX DiGraph + + Returns + ------- + closures : list + List of triads of G that are triadic closures + ''' + pass + + +@not_implemented_for('undirected') +def focal_closures(G, attr_name): + '''Returns a list of order-3 subgraphs of G that are focally closed. + + Parameters + ---------- + G : digraph + A NetworkX DiGraph + attr_name : str + An attribute name + + + Returns + ------- + closures : list + List of triads of G that are focally closed on attr_name + ''' + pass + + +@not_implemented_for('undirected') +def balanced_triads(G, crit_func): + '''Returns a list of order-3 subgraphs of G that are stable. + + Parameters + ---------- + G : digraph + A NetworkX DiGraph + crit_func : function + A function that determines if a triad (order-3 digraph) is stable + + Returns + ------- + triads : list + List of triads in G that are stable + ''' + pass +"""