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

1""" 

2Flow Hierarchy. 

3""" 

4import networkx as nx 

5 

6__all__ = ["flow_hierarchy"] 

7 

8 

9@nx._dispatch(edge_attrs="weight") 

10def flow_hierarchy(G, weight=None): 

11 """Returns the flow hierarchy of a directed network. 

12 

13 Flow hierarchy is defined as the fraction of edges not participating 

14 in cycles in a directed graph [1]_. 

15 

16 Parameters 

17 ---------- 

18 G : DiGraph or MultiDiGraph 

19 A directed graph 

20 

21 weight : string, optional (default=None) 

22 Attribute to use for edge weights. If None the weight defaults to 1. 

23 

24 Returns 

25 ------- 

26 h : float 

27 Flow hierarchy value 

28 

29 Notes 

30 ----- 

31 The algorithm described in [1]_ computes the flow hierarchy through 

32 exponentiation of the adjacency matrix. This function implements an 

33 alternative approach that finds strongly connected components. 

34 An edge is in a cycle if and only if it is in a strongly connected 

35 component, which can be found in $O(m)$ time using Tarjan's algorithm. 

36 

37 References 

38 ---------- 

39 .. [1] Luo, J.; Magee, C.L. (2011), 

40 Detecting evolving patterns of self-organizing networks by flow 

41 hierarchy measurement, Complexity, Volume 16 Issue 6 53-61. 

42 DOI: 10.1002/cplx.20368 

43 http://web.mit.edu/~cmagee/www/documents/28-DetectingEvolvingPatterns_FlowHierarchy.pdf 

44 """ 

45 if not G.is_directed(): 

46 raise nx.NetworkXError("G must be a digraph in flow_hierarchy") 

47 scc = nx.strongly_connected_components(G) 

48 return 1 - sum(G.subgraph(c).size(weight) for c in scc) / G.size(weight)