title: How to convert a directed graph to its most minimal form?
body: <p>I'm dealing with <em>rooted, directed, potentially cyclic</em> graphs. Each vertex in the graph has a label, which might or might not be unique. Edges do not have labels. The graph has a designated <em>root</em> vertex from which every vertex is reachable. The order of the edges outgoing from a vertex is relevant.</p>
  <p>For my purposes, a vertex is <em>equal</em> to another vertex if they share the same label, and if their <em>outgoing</em> edges are also considered equal (and are in the same order). Two edges are equal if they have the same direction and if the vertices at their corresponding ends are equal.</p>
  <p>Because of the equality rules above, a graph can contain multiple &quot;sections&quot; that are effectively equal. For example, in the graph below, there are two isomorphic sections containing vertices with labels {1, 2, 3, 4}. The root of the graph is vertex 0.</p>
  <p><a href="https://i.stack.imgur.com/uN7aB.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/uN7aB.png" alt="graph" /></a><br />
  <sub>(source: <a href="https://graphonline.ru/tmp/saved/et/etaxPEvsuCWSkWQz.png" rel="nofollow noreferrer">graphonline.ru</a>)</sub></p>
  <p>I need to be able to identify sections that are identical, and then remove all duplication, without changing the &quot;meaning&quot; of the graph (with regard to the equality rules above). Using the above example as input, I need to produce this:</p>
  <p><a href="https://i.stack.imgur.com/zpBBY.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/zpBBY.png" alt="graph" /></a><br />
  <sub>(source: <a href="https://graphonline.ru/tmp/saved/BG/BGTeVQTooLvaDjEO.png" rel="nofollow noreferrer">graphonline.ru</a>)</sub></p>
  <p>Is there a known way of doing this within polynomial time?</p>