diff env/lib/python3.9/site-packages/networkx/algorithms/tournament.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/tournament.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,353 @@
+"""Functions concerning tournament graphs.
+
+A `tournament graph`_ is a complete oriented graph. In other words, it
+is a directed graph in which there is exactly one directed edge joining
+each pair of distinct nodes. For each function in this module that
+accepts a graph as input, you must provide a tournament graph. The
+responsibility is on the caller to ensure that the graph is a tournament
+graph.
+
+To access the functions in this module, you must access them through the
+:mod:`networkx.algorithms.tournament` module::
+
+    >>> from networkx.algorithms import tournament
+    >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 0)])
+    >>> tournament.is_tournament(G)
+    True
+
+.. _tournament graph: https://en.wikipedia.org/wiki/Tournament_%28graph_theory%29
+
+"""
+from itertools import combinations
+
+import networkx as nx
+from networkx.algorithms.simple_paths import is_simple_path as is_path
+from networkx.utils import arbitrary_element
+from networkx.utils import not_implemented_for
+from networkx.utils import py_random_state
+
+__all__ = [
+    "hamiltonian_path",
+    "is_reachable",
+    "is_strongly_connected",
+    "is_tournament",
+    "random_tournament",
+    "score_sequence",
+]
+
+
+def index_satisfying(iterable, condition):
+    """Returns the index of the first element in `iterable` that
+    satisfies the given condition.
+
+    If no such element is found (that is, when the iterable is
+    exhausted), this returns the length of the iterable (that is, one
+    greater than the last index of the iterable).
+
+    `iterable` must not be empty. If `iterable` is empty, this
+    function raises :exc:`ValueError`.
+
+    """
+    # Pre-condition: iterable must not be empty.
+    for i, x in enumerate(iterable):
+        if condition(x):
+            return i
+    # If we reach the end of the iterable without finding an element
+    # that satisfies the condition, return the length of the iterable,
+    # which is one greater than the index of its last element. If the
+    # iterable was empty, `i` will not be defined, so we raise an
+    # exception.
+    try:
+        return i + 1
+    except NameError as e:
+        raise ValueError("iterable must be non-empty") from e
+
+
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
+def is_tournament(G):
+    """Returns True if and only if `G` is a tournament.
+
+    A tournament is a directed graph, with neither self-loops nor
+    multi-edges, in which there is exactly one directed edge joining
+    each pair of distinct nodes.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+        A directed graph representing a tournament.
+
+    Returns
+    -------
+    bool
+        Whether the given graph is a tournament graph.
+
+    Notes
+    -----
+    Some definitions require a self-loop on each node, but that is not
+    the convention used here.
+
+    """
+    # In a tournament, there is exactly one directed edge joining each pair.
+    return (
+        all((v in G[u]) ^ (u in G[v]) for u, v in combinations(G, 2))
+        and nx.number_of_selfloops(G) == 0
+    )
+
+
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
+def hamiltonian_path(G):
+    """Returns a Hamiltonian path in the given tournament graph.
+
+    Each tournament has a Hamiltonian path. If furthermore, the
+    tournament is strongly connected, then the returned Hamiltonian path
+    is a Hamiltonian cycle (by joining the endpoints of the path).
+
+    Parameters
+    ----------
+    G : NetworkX graph
+        A directed graph representing a tournament.
+
+    Returns
+    -------
+    bool
+        Whether the given graph is a tournament graph.
+
+    Notes
+    -----
+    This is a recursive implementation with an asymptotic running time
+    of $O(n^2)$, ignoring multiplicative polylogarithmic factors, where
+    $n$ is the number of nodes in the graph.
+
+    """
+    if len(G) == 0:
+        return []
+    if len(G) == 1:
+        return [arbitrary_element(G)]
+    v = arbitrary_element(G)
+    hampath = hamiltonian_path(G.subgraph(set(G) - {v}))
+    # Get the index of the first node in the path that does *not* have
+    # an edge to `v`, then insert `v` before that node.
+    index = index_satisfying(hampath, lambda u: v not in G[u])
+    hampath.insert(index, v)
+    return hampath
+
+
+@py_random_state(1)
+def random_tournament(n, seed=None):
+    r"""Returns a random tournament graph on `n` nodes.
+
+    Parameters
+    ----------
+    n : int
+        The number of nodes in the returned graph.
+    seed : integer, random_state, or None (default)
+        Indicator of random number generation state.
+        See :ref:`Randomness<randomness>`.
+
+    Returns
+    -------
+    bool
+        Whether the given graph is a tournament graph.
+
+    Notes
+    -----
+    This algorithm adds, for each pair of distinct nodes, an edge with
+    uniformly random orientation. In other words, `\binom{n}{2}` flips
+    of an unbiased coin decide the orientations of the edges in the
+    graph.
+
+    """
+    # Flip an unbiased coin for each pair of distinct nodes.
+    coins = (seed.random() for i in range((n * (n - 1)) // 2))
+    pairs = combinations(range(n), 2)
+    edges = ((u, v) if r < 0.5 else (v, u) for (u, v), r in zip(pairs, coins))
+    return nx.DiGraph(edges)
+
+
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
+def score_sequence(G):
+    """Returns the score sequence for the given tournament graph.
+
+    The score sequence is the sorted list of the out-degrees of the
+    nodes of the graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+        A directed graph representing a tournament.
+
+    Returns
+    -------
+    list
+        A sorted list of the out-degrees of the nodes of `G`.
+
+    """
+    return sorted(d for v, d in G.out_degree())
+
+
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
+def tournament_matrix(G):
+    r"""Returns the tournament matrix for the given tournament graph.
+
+    This function requires SciPy.
+
+    The *tournament matrix* of a tournament graph with edge set *E* is
+    the matrix *T* defined by
+
+    .. math::
+
+       T_{i j} =
+       \begin{cases}
+       +1 & \text{if } (i, j) \in E \\
+       -1 & \text{if } (j, i) \in E \\
+       0 & \text{if } i == j.
+       \end{cases}
+
+    An equivalent definition is `T = A - A^T`, where *A* is the
+    adjacency matrix of the graph `G`.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+        A directed graph representing a tournament.
+
+    Returns
+    -------
+    SciPy sparse matrix
+        The tournament matrix of the tournament graph `G`.
+
+    Raises
+    ------
+    ImportError
+        If SciPy is not available.
+
+    """
+    A = nx.adjacency_matrix(G)
+    return A - A.T
+
+
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
+def is_reachable(G, s, t):
+    """Decides whether there is a path from `s` to `t` in the
+    tournament.
+
+    This function is more theoretically efficient than the reachability
+    checks than the shortest path algorithms in
+    :mod:`networkx.algorithms.shortest_paths`.
+
+    The given graph **must** be a tournament, otherwise this function's
+    behavior is undefined.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+        A directed graph representing a tournament.
+
+    s : node
+        A node in the graph.
+
+    t : node
+        A node in the graph.
+
+    Returns
+    -------
+    bool
+        Whether there is a path from `s` to `t` in `G`.
+
+    Notes
+    -----
+    Although this function is more theoretically efficient than the
+    generic shortest path functions, a speedup requires the use of
+    parallelism. Though it may in the future, the current implementation
+    does not use parallelism, thus you may not see much of a speedup.
+
+    This algorithm comes from [1].
+
+    References
+    ----------
+    .. [1] Tantau, Till.
+           "A note on the complexity of the reachability problem for
+           tournaments."
+           *Electronic Colloquium on Computational Complexity*. 2001.
+           <http://eccc.hpi-web.de/report/2001/092/>
+
+    """
+
+    def two_neighborhood(G, v):
+        """Returns the set of nodes at distance at most two from `v`.
+
+        `G` must be a graph and `v` a node in that graph.
+
+        The returned set includes the nodes at distance zero (that is,
+        the node `v` itself), the nodes at distance one (that is, the
+        out-neighbors of `v`), and the nodes at distance two.
+
+        """
+        # TODO This is trivially parallelizable.
+        return {
+            x for x in G if x == v or x in G[v] or any(is_path(G, [v, z, x]) for z in G)
+        }
+
+    def is_closed(G, nodes):
+        """Decides whether the given set of nodes is closed.
+
+        A set *S* of nodes is *closed* if for each node *u* in the graph
+        not in *S* and for each node *v* in *S*, there is an edge from
+        *u* to *v*.
+
+        """
+        # TODO This is trivially parallelizable.
+        return all(v in G[u] for u in set(G) - nodes for v in nodes)
+
+    # TODO This is trivially parallelizable.
+    neighborhoods = [two_neighborhood(G, v) for v in G]
+    return all(not (is_closed(G, S) and s in S and t not in S) for S in neighborhoods)
+
+
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
+def is_strongly_connected(G):
+    """Decides whether the given tournament is strongly connected.
+
+    This function is more theoretically efficient than the
+    :func:`~networkx.algorithms.components.is_strongly_connected`
+    function.
+
+    The given graph **must** be a tournament, otherwise this function's
+    behavior is undefined.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+        A directed graph representing a tournament.
+
+    Returns
+    -------
+    bool
+        Whether the tournament is strongly connected.
+
+    Notes
+    -----
+    Although this function is more theoretically efficient than the
+    generic strong connectivity function, a speedup requires the use of
+    parallelism. Though it may in the future, the current implementation
+    does not use parallelism, thus you may not see much of a speedup.
+
+    This algorithm comes from [1].
+
+    References
+    ----------
+    .. [1] Tantau, Till.
+           "A note on the complexity of the reachability problem for
+           tournaments."
+           *Electronic Colloquium on Computational Complexity*. 2001.
+           <http://eccc.hpi-web.de/report/2001/092/>
+
+    """
+    # TODO This is trivially parallelizable.
+    return all(is_reachable(G, u, v) for u in G for v in G)