title: How to create a DAG from a list in python
body: <p>I am using networkx to manually input the (u, v, weights) to a graph. But when the input gets bigger this manual insertion of nodes and edges will become a really tiresome task and prone to errors. I'm trying but haven't figured out that how to perform this task without manual labour.</p>
  <p><strong>Sample Input:</strong></p>
  <blockquote>
  <p>my_list = [&quot;s1[0]&quot;, &quot;d1[0, 2]&quot;, &quot;s2[0]&quot;, &quot;d2[1, 3]&quot;, &quot;d3[0, 2]&quot;, &quot;d4[1, 4]&quot;, &quot;d5[2,
  3]&quot;, &quot;d6[1, 4]&quot;]</p>
  </blockquote>
  <p><strong>Manual Insertion:</strong></p>
  <p>Before inserting nodes into a graph I need to number them, so first occurrence of 's' or 'd' can be differentiate from later similar characters e.g. s1,s2,s3,... and d1,d2,d3,...
  I am aware it is something similar to SSA form (compilers) but I was not able to find something helpful for my case.</p>
  <p>Manually inserting (u, v, weights) to a DiGraph()</p>
  <pre><code>my_graph.add_weighted_edges_from([(&quot;s1&quot;, &quot;d1&quot;, 0), (&quot;d1&quot;, &quot;s2&quot;, 0), (&quot;d1&quot;, &quot;d3&quot;, 2), (&quot;s2&quot;, &quot;d3&quot;, 0), (
      &quot;d2&quot;, &quot;d4&quot;, 1), (&quot;d2&quot;, &quot;d5&quot;, 3), (&quot;d3&quot;, &quot;d5&quot;, 2), (&quot;d4&quot;, &quot;d6&quot;, 1), (&quot;d4&quot;, &quot;d6&quot;, 4)])
  
  </code></pre>
  <p><strong>Question:</strong></p>
  <p>How to automatically convert that input list(my_list) into a DAG(my_graph), avoiding manual insertion?</p>
  <p><strong>Complete Code:</strong>
  This is what I have written so far.</p>
  <pre><code>import networkx as nx
  from networkx.drawing.nx_agraph import write_dot, graphviz_layout
  from matplotlib import pyplot as plt
  
  my_graph = nx.DiGraph()
  my_graph.add_weighted_edges_from([(&quot;s1&quot;, &quot;d1&quot;, 0), (&quot;d1&quot;, &quot;s2&quot;, 0), (&quot;d1&quot;, &quot;d3&quot;, 2), (&quot;s2&quot;, &quot;d3&quot;, 0), (
      &quot;d2&quot;, &quot;d4&quot;, 1), (&quot;d2&quot;, &quot;d5&quot;, 3), (&quot;d3&quot;, &quot;d5&quot;, 2), (&quot;d4&quot;, &quot;d6&quot;, 1), (&quot;d4&quot;, &quot;d6&quot;, 4)])
  
  
  write_dot(my_graph, &quot;graph.dot&quot;)
  
  plt.title(&quot;draw graph&quot;)
  pos = graphviz_layout(my_graph, prog='dot')
  
  
  
  nx.draw(my_graph, pos, with_labels=True, arrows=True)
  
  plt.show()
  plt.clf()
  
  </code></pre>
  <p><strong>Explanation:</strong></p>
  <ol>
  <li><p>'s' and 'd' are some instructions that requires 1 or 2 registers respectively, to perform an operation.</p>
  </li>
  <li><p>In above example we have 2 's' operations and 6 'd' operations and there are five registers [0,1,2,3,4].</p>
  </li>
  <li><p>Each operation will perform some calculation and store the results in relevant register/s.</p>
  </li>
  <li><p>From input we can see that d1 uses register 0 and 2, so it cannot operate until both of these registers are free. Therefore, d1 is dependent on s1 because s1 comes before d1 and is using register 0. As soon as s1 finishes d1 can operate as register 2 is already free.</p>
  </li>
  <li><p>E.g. We initialize all registers with 1. s1 doubles its input while d1 sums two inputs and store the result in it's second register:</p>
  </li>
  </ol>
  <blockquote>
  <p>so after s1[0] reg-0 * 2 -&gt; 1 * 2 =&gt; reg-0 = 2</p>
  <p>and after d1[0, 2] reg-0 + reg-2 -&gt; 2 + 1 =&gt; reg-0 = 2 and reg-2 = 3</p>
  </blockquote>
  <p><strong>Update 1:</strong> The graph will be a dependency-graph based on some resources [0...4], each node will require 1(for 's') or 2(for 'd') of these resources.</p>
  <p><strong>Update 2:</strong> Two questions were causing confusion so I'm separating them. For now I have changed my input list and there is only a single task of converting that list into a DAG. I have also included an explanation section.</p>
  <p><em>PS: You might need to pip install graphviz if you don't already have it.</em></p>