## Mercurial > repos > shellac > sam_consensus_v3

### comparison env/lib/python3.9/site-packages/networkx/generators/interval_graph.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

author | shellac |
---|---|

date | Mon, 22 Mar 2021 18:12:50 +0000 |

parents | |

children |

comparison

equal
deleted
inserted
replaced

-1:000000000000 | 0:4f3585e2f14b |
---|---|

1 """ | |

2 Generators for interval graph. | |

3 """ | |

4 from collections.abc import Sequence | |

5 import networkx as nx | |

6 | |

7 __all__ = ["interval_graph"] | |

8 | |

9 | |

10 def interval_graph(intervals): | |

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

12 | |

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

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

15 and an edge between vertices whose intervals intersect. | |

16 It is the intersection graph of the intervals. | |

17 | |

18 More information can be found at: | |

19 https://en.wikipedia.org/wiki/Interval_graph | |

20 | |

21 Parameters | |

22 ---------- | |

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

24 and r is the right end of the closed interval. | |

25 | |

26 Returns | |

27 ------- | |

28 G : networkx graph | |

29 | |

30 Examples | |

31 -------- | |

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

33 >>> G = nx.interval_graph(intervals) | |

34 >>> sorted(G.edges) | |

35 [((-2, 3), (1, 4)), ((-2, 3), (2, 3)), ((1, 4), (2, 3)), ((1, 4), (4, 6))] | |

36 | |

37 Raises | |

38 -------- | |

39 :exc:`TypeError` | |

40 if `intervals` contains None or an element which is not | |

41 collections.abc.Sequence or not a length of 2. | |

42 :exc:`ValueError` | |

43 if `intervals` contains an interval such that min1 > max1 | |

44 where min1,max1 = interval | |

45 """ | |

46 intervals = list(intervals) | |

47 for interval in intervals: | |

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

49 raise TypeError( | |

50 "Each interval must have length 2, and be a " | |

51 "collections.abc.Sequence such as tuple or list." | |

52 ) | |

53 if interval[0] > interval[1]: | |

54 raise ValueError( | |

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

56 ) | |

57 | |

58 graph = nx.Graph() | |

59 | |

60 tupled_intervals = [tuple(interval) for interval in intervals] | |

61 graph.add_nodes_from(tupled_intervals) | |

62 | |

63 while tupled_intervals: | |

64 min1, max1 = interval1 = tupled_intervals.pop() | |

65 for interval2 in tupled_intervals: | |

66 min2, max2 = interval2 | |

67 if max1 >= min2 and max2 >= min1: | |

68 graph.add_edge(interval1, interval2) | |

69 return graph |