## Mercurial > repos > shellac > sam_consensus_v3

### view 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 |

line wrap: on

line source

""" Generators for interval graph. """ from collections.abc import Sequence import networkx as nx __all__ = ["interval_graph"] def interval_graph(intervals): """ Generates an interval graph for a list of intervals given. In graph theory, an interval graph is an undirected graph formed from a set of closed intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. More information can be found at: https://en.wikipedia.org/wiki/Interval_graph Parameters ---------- intervals : a sequence of intervals, say (l, r) where l is the left end, and r is the right end of the closed interval. Returns ------- G : networkx graph Examples -------- >>> intervals = [(-2, 3), [1, 4], (2, 3), (4, 6)] >>> G = nx.interval_graph(intervals) >>> sorted(G.edges) [((-2, 3), (1, 4)), ((-2, 3), (2, 3)), ((1, 4), (2, 3)), ((1, 4), (4, 6))] Raises -------- :exc:`TypeError` if `intervals` contains None or an element which is not collections.abc.Sequence or not a length of 2. :exc:`ValueError` if `intervals` contains an interval such that min1 > max1 where min1,max1 = interval """ intervals = list(intervals) for interval in intervals: if not (isinstance(interval, Sequence) and len(interval) == 2): raise TypeError( "Each interval must have length 2, and be a " "collections.abc.Sequence such as tuple or list." ) if interval[0] > interval[1]: raise ValueError( f"Interval must have lower value first. " f"Got {interval}" ) graph = nx.Graph() tupled_intervals = [tuple(interval) for interval in intervals] graph.add_nodes_from(tupled_intervals) while tupled_intervals: min1, max1 = interval1 = tupled_intervals.pop() for interval2 in tupled_intervals: min2, max2 = interval2 if max1 >= min2 and max2 >= min1: graph.add_edge(interval1, interval2) return graph