Interval Graph¶

Overview¶

class dynetworkx.IntervalGraph(**attr)¶

Base class for undirected interval graphs.

The IntervalGraph class allows any hashable object as a node and can associate key/value attribute pairs with each undirected edge.

Each edge must have two integers, begin and end for its interval.

Self-loops are allowed but multiple edges (two or more edges with the same nodes, begin and end interval) are not.

Two nodes can have more than one edge with different overlapping or non-overlapping intervals.

Parameters:	attr (keyword arguments, optional (default= no attributes)) – Attributes to add to graph as key=value pairs.

Examples

Create an empty graph structure (a “null interval graph”) with no nodes and no edges.

>>> G = dnx.IntervalGraph()

G can be grown in several ways.

Nodes:

Add one node at a time:

>>> G.add_node(1)

Add the nodes from any container (a list, dict, set or even the lines from a file or the nodes from another graph).

Add the nodes from any container (a list, dict, set)

>>> G.add_nodes_from([2, 3])
>>> G.add_nodes_from(range(100, 110))

Edges:

G can also be grown by adding edges. This can be considered the primary way to grow G, since nodes with no edge will not appear in G in most cases. See G.to_snapshot().

Add one edge, which starts at 0 and ends at 10. Keep in mind that the interval is [0, 10). Thus, it does not include the end.

>>> G.add_edge(1, 2, 0, 10)

a list of edges,

>>> G.add_edges_from([(1, 2, 0, 10), (1, 3, 3, 11)])

If some edges connect nodes not yet in the graph, the nodes are added automatically. There are no errors when adding nodes or edges that already exist.

Attributes:

Each interval graph, node, and edge can hold key/value attribute pairs in an associated attribute dictionary (the keys must be hashable). By default these are empty, but can be added or changed using add_edge, add_node.

Keep in mind that the edge interval is not an attribute of the edge.

>>> G = dnx.IntervalGraph(day="Friday")
>>> G.graph
{'day': 'Friday'}

Add node attributes using add_node(), add_nodes_from()

>>> G.add_node(1, time='5pm')
>>> G.add_nodes_from([3], time='2pm')

Add edge attributes using add_edge(), add_edges_from().

>>> G.add_edge(1, 2, 0, 10, weight=4.7 )
>>> G.add_edges_from([(3, 4, 3, 11), (4, 5, 0, 33)], color='red')

Shortcuts:

Here are a couple examples of available shortcuts:

>>> 1 in G  # check if node in interval graph during any interval
True
>>> len(G)  # number of nodes in the entire interval graph
5

Subclasses (Advanced): Edges in interval graphs are represented by Interval Objects and are kept in an IntervalTree. Both are based on intervaltree available in pypi (https://pypi.org/project/intervaltree). IntervalTree allows for fast interval based search through edges, which makes interval graph analysis possible.

The Graph class uses a dict-of-dict-of-dict data structure. The outer dict (node_dict) holds adjacency information keyed by nodes. The next dict (adjlist_dict) represents the adjacency information and holds edge data keyed by interval objects. The inner dict (edge_attr_dict) represents the edge data and holds edge attribute values keyed by attribute names.

Methods¶

Adding and removing nodes and edges¶

`IntervalGraph.__init__`(**attr)	Initialize an interval graph with edges, name, or graph attributes.
`IntervalGraph.add_node`(node_for_adding, **attr)	Add a single node node_for_adding and update node attributes.
`IntervalGraph.add_nodes_from`(…)	Add multiple nodes.
`IntervalGraph.remove_node`(n[, begin, end])	Remove the presence of a node n within the given interval.
`IntervalGraph.add_edge`(u, v, begin, end, **attr)	Add an edge between u and v, during interval [begin, end).
`IntervalGraph.add_edges_from`(ebunch_to_add, …)	Add all the edges in ebunch_to_add.
`IntervalGraph.remove_edge`(u, v[, begin, …])	Remove the edge between u and v in the interval graph, during the given interval.

Reporting interval graph, nodes and edges¶

`IntervalGraph.nodes`([begin, end, data, default])	A NodeDataView of the IntervalGraph nodes.
`IntervalGraph.has_node`(n[, begin, end])	Return True if the interval graph contains the node n, during the given interval.
`IntervalGraph.edges`([u, v, begin, end, …])	Returns a list of Interval objects of the IntervalGraph edges.
`IntervalGraph.has_edge`(u, v[, begin, end, …])	Return True if there exists an edge between u and v in the interval graph, during the given interval.
`IntervalGraph.__contains__`(n)	Return True if n is a node, False otherwise.
`IntervalGraph.__str__`()	Return the interval graph name.
`IntervalGraph.interval`()	Return a 2-tuple as (begin, end) interval of the entire

Counting nodes and edges¶

`IntervalGraph.number_of_nodes`([begin, end])	Return the number of nodes in the interval graph between the given interval.
`IntervalGraph.__len__`()	Return the number of nodes.

Making copies and subgraphs¶

`IntervalGraph.to_subgraph`(begin, end[, …])	Return a networkx Graph or MultiGraph which includes all the nodes and edges which have overlapping intervals with the given interval.
`IntervalGraph.to_snapshots`(number_of_snapshots)	Return a list of networkx Graph or MultiGraph objects as snapshots of the interval graph in consecutive order.

Loading an interval graph¶

`IntervalGraph.load_from_txt`(path[, …])	Read interval graph in from path.
`IntervalGraph.save_to_txt`(path[, delimiter])	Write interval graph to path.

Analyzing interval graphs¶

IntervalGraph.degree([node, begin, end, delta]) Return the degree of a specified node between time begin and end.