Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/interval_graph.py: 24%

1""" 

2Generators for interval graph. 

3""" 

4from collections.abc import Sequence 

5 

6import networkx as nx 

7 

8__all__ = ["interval_graph"] 

9 

10 

11@nx._dispatch(graphs=None) 

12def interval_graph(intervals): 

13 """Generates an interval graph for a list of intervals given. 

14 

15 In graph theory, an interval graph is an undirected graph formed from a set 

16 of closed intervals on the real line, with a vertex for each interval 

17 and an edge between vertices whose intervals intersect. 

18 It is the intersection graph of the intervals. 

19 

20 More information can be found at: 

21 https://en.wikipedia.org/wiki/Interval_graph 

22 

23 Parameters 

24 ---------- 

25 intervals : a sequence of intervals, say (l, r) where l is the left end, 

26 and r is the right end of the closed interval. 

27 

28 Returns 

29 ------- 

30 G : networkx graph 

31 

32 Examples 

33 -------- 

34 >>> intervals = [(-2, 3), [1, 4], (2, 3), (4, 6)] 

35 >>> G = nx.interval_graph(intervals) 

36 >>> sorted(G.edges) 

37 [((-2, 3), (1, 4)), ((-2, 3), (2, 3)), ((1, 4), (2, 3)), ((1, 4), (4, 6))] 

38 

39 Raises 

40 ------ 

41 :exc:`TypeError` 

42 if `intervals` contains None or an element which is not 

43 collections.abc.Sequence or not a length of 2. 

44 :exc:`ValueError` 

45 if `intervals` contains an interval such that min1 > max1 

46 where min1,max1 = interval 

47 """ 

48 intervals = list(intervals) 

49 for interval in intervals: 

50 if not (isinstance(interval, Sequence) and len(interval) == 2): 

51 raise TypeError( 

52 "Each interval must have length 2, and be a " 

53 "collections.abc.Sequence such as tuple or list." 

54 ) 

55 if interval[0] > interval[1]: 

56 raise ValueError( 

57 f"Interval must have lower value first. " f"Got {interval}" 

58 ) 

59 

60 graph = nx.Graph() 

61 

62 tupled_intervals = [tuple(interval) for interval in intervals] 

63 graph.add_nodes_from(tupled_intervals) 

64 

65 while tupled_intervals: 

66 min1, max1 = interval1 = tupled_intervals.pop() 

67 for interval2 in tupled_intervals: 

68 min2, max2 = interval2 

69 if max1 >= min2 and max2 >= min1: 

70 graph.add_edge(interval1, interval2) 

71 return graph