### comparison env/lib/python3.9/site-packages/networkx/generators/interval_graph.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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]