diff env/lib/python3.9/site-packages/networkx/algorithms/triads.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /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 <[e-mail]>
+# Copyright 2011 Diederik van Liere <[e-mail]>
+"""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
+"""