What is the fastest way to set up a DAG using a list of tuples, where first and second elements represent neighbor connections?

Question

Let's say I have a list of tuples: [(0,1),(0,2),(1,3),(4,5)..... In this list of tuples, the second element is always strictly greater than the first element. Let x_i be the first element of tuple i. And y_i be the second element of tuple i. I'd like to create a graph in the following way: 1). A single tuple is a single vertex. 2). If two tuples i and j, have y_i==x_j, then a directed arc should exist from i to j.

The result will be a directed acyclic graph. However, I'm not able to find an easy way to input this into networkx. The usual ways are edgelist, etc., but I don't see how the situation above will be treated appropriately by that. Is there an easy way to created a DAG using the inputs I just described?

Answer 1

Instanciate a DiGraph and add the nodes (add_nodes_from), the use a dictionary to identify the nodes linked to a particular j, then add the edges (add_edges_from):

lst = [(0,1),(0,2),(1,3),(4,5)]

d = {}
for i,j in lst:
    d.setdefault(i, set()).add((i, j))
# {0: {(0, 1), (0, 2)}, 1: {(1, 3)}, 4: {(4, 5)}}

G = nx.DiGraph()
G.add_nodes_from(lst)
G.add_edges_from(((i, j), k) for i, j in lst
                 if j in d for k in d[j])

Output: