Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Generators for interval graph.
3"""
5from collections.abc import Sequence
7import networkx as nx
9__all__ = ["interval_graph"]
12@nx._dispatchable(graphs=None, returns_graph=True)
13def interval_graph(intervals):
14 """Generates an interval graph for a list of intervals given.
16 In graph theory, an interval graph is an undirected graph formed from a set
17 of closed intervals on the real line, with a vertex for each interval
18 and an edge between vertices whose intervals intersect.
19 It is the intersection graph of the intervals.
21 More information can be found at:
22 https://en.wikipedia.org/wiki/Interval_graph
24 Parameters
25 ----------
26 intervals : a sequence of intervals, say (l, r) where l is the left end,
27 and r is the right end of the closed interval.
29 Returns
30 -------
31 G : networkx graph
33 Examples
34 --------
35 >>> intervals = [(-2, 3), [1, 4], (2, 3), (4, 6)]
36 >>> G = nx.interval_graph(intervals)
37 >>> sorted(G.edges)
38 [((-2, 3), (1, 4)), ((-2, 3), (2, 3)), ((1, 4), (2, 3)), ((1, 4), (4, 6))]
40 Raises
41 ------
42 :exc:`TypeError`
43 if `intervals` contains None or an element which is not
44 collections.abc.Sequence or not a length of 2.
45 :exc:`ValueError`
46 if `intervals` contains an interval such that min1 > max1
47 where min1,max1 = interval
48 """
49 intervals = list(intervals)
50 for interval in intervals:
51 if not (isinstance(interval, Sequence) and len(interval) == 2):
52 raise TypeError(
53 "Each interval must have length 2, and be a "
54 "collections.abc.Sequence such as tuple or list."
55 )
56 if interval[0] > interval[1]:
57 raise ValueError(f"Interval must have lower value first. Got {interval}")
59 graph = nx.Graph()
61 tupled_intervals = [tuple(interval) for interval in intervals]
62 graph.add_nodes_from(tupled_intervals)
64 while tupled_intervals:
65 min1, max1 = interval1 = tupled_intervals.pop()
66 for interval2 in tupled_intervals:
67 min2, max2 = interval2
68 if max1 >= min2 and max2 >= min1:
69 graph.add_edge(interval1, interval2)
70 return graph