Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / components / semiconnected.py @ 5cef0f13

History | View | Annotate | Download (1.8 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2004-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors: ysitu (ysitu@users.noreply.github.com)
10
"""Semiconnectedness."""
11
import networkx as nx
12
from networkx.utils import not_implemented_for, pairwise
13

    
14
__all__ = ['is_semiconnected']
15

    
16

    
17
@not_implemented_for('undirected')
18
def is_semiconnected(G, topo_order=None):
19
    """Returns True if the graph is semiconnected, False otherwise.
20

21
    A graph is semiconnected if, and only if, for any pair of nodes, either one
22
    is reachable from the other, or they are mutually reachable.
23

24
    Parameters
25
    ----------
26
    G : NetworkX graph
27
        A directed graph.
28

29
    topo_order: list or tuple, optional
30
        A topological order for G (if None, the function will compute one)
31

32
    Returns
33
    -------
34
    semiconnected : bool
35
        True if the graph is semiconnected, False otherwise.
36

37
    Raises
38
    ------
39
    NetworkXNotImplemented :
40
        If the input graph is undirected.
41

42
    NetworkXPointlessConcept :
43
        If the graph is empty.
44

45
    Examples
46
    --------
47
    >>> G=nx.path_graph(4,create_using=nx.DiGraph())
48
    >>> print(nx.is_semiconnected(G))
49
    True
50
    >>> G=nx.DiGraph([(1, 2), (3, 2)])
51
    >>> print(nx.is_semiconnected(G))
52
    False
53

54
    See Also
55
    --------
56
    is_strongly_connected
57
    is_weakly_connected
58
    is_connected
59
    is_biconnected
60
    """
61
    if len(G) == 0:
62
        raise nx.NetworkXPointlessConcept(
63
            'Connectivity is undefined for the null graph.')
64

    
65
    if not nx.is_weakly_connected(G):
66
        return False
67

    
68
    G = nx.condensation(G)
69
    if topo_order is None:
70
        topo_order = nx.topological_sort(G)
71

    
72
    return all(G.has_edge(u, v) for u, v in pairwise(topo_order))