Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/components/semiconnected.py: 50%

1"""Semiconnectedness.""" 

2import networkx as nx 

3from networkx.utils import not_implemented_for, pairwise 

4 

5__all__ = ["is_semiconnected"] 

6 

7 

8@not_implemented_for("undirected") 

9@nx._dispatch 

10def is_semiconnected(G): 

11 r"""Returns True if the graph is semiconnected, False otherwise. 

12 

13 A graph is semiconnected if and only if for any pair of nodes, either one 

14 is reachable from the other, or they are mutually reachable. 

15 

16 This function uses a theorem that states that a DAG is semiconnected 

17 if for any topological sort, for node $v_n$ in that sort, there is an 

18 edge $(v_i, v_{i+1})$. That allows us to check if a non-DAG `G` is 

19 semiconnected by condensing the graph: i.e. constructing a new graph `H` 

20 with nodes being the strongly connected components of `G`, and edges 

21 (scc_1, scc_2) if there is a edge $(v_1, v_2)$ in `G` for some 

22 $v_1 \in scc_1$ and $v_2 \in scc_2$. That results in a DAG, so we compute 

23 the topological sort of `H` and check if for every $n$ there is an edge 

24 $(scc_n, scc_{n+1})$. 

25 

26 Parameters 

27 ---------- 

28 G : NetworkX graph 

29 A directed graph. 

30 

31 Returns 

32 ------- 

33 semiconnected : bool 

34 True if the graph is semiconnected, False otherwise. 

35 

36 Raises 

37 ------ 

38 NetworkXNotImplemented 

39 If the input graph is undirected. 

40 

41 NetworkXPointlessConcept 

42 If the graph is empty. 

43 

44 Examples 

45 -------- 

46 >>> G = nx.path_graph(4, create_using=nx.DiGraph()) 

47 >>> print(nx.is_semiconnected(G)) 

48 True 

49 >>> G = nx.DiGraph([(1, 2), (3, 2)]) 

50 >>> print(nx.is_semiconnected(G)) 

51 False 

52 

53 See Also 

54 -------- 

55 is_strongly_connected 

56 is_weakly_connected 

57 is_connected 

58 is_biconnected 

59 """ 

60 if len(G) == 0: 

61 raise nx.NetworkXPointlessConcept( 

62 "Connectivity is undefined for the null graph." 

63 ) 

64 

65 if not nx.is_weakly_connected(G): 

66 return False 

67 

68 H = nx.condensation(G) 

69 

70 return all(H.has_edge(u, v) for u, v in pairwise(nx.topological_sort(H)))