title: Construct a bipartite representation of a directed network for use with hopcroft-karp matching function in networkx
body: <p>I am using the hopcroft-karp algorithm in networkx on a directed network which I have transformed into a bipartite representation. However, the bipartite network is not allowed to have the same vertex in both left and right node sets. There is a self loop included in my directed network, so as a workaround, I rename the vertices in the left node set as (X1_+, X2_+,X3_+) and in the right set as (X1_-,X2_-,X3_-). The directed network and the corresponding bipartite representation are as follows:</p>
  <p><a href="https://i.stack.imgur.com/agS7W.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/agS7W.png" alt="enter image description here" /></a></p>
  <p>The correct result for the maximum matching, in terms of the dictionary output given by the hopcroft-karp algorithm in networkx, should be</p>
  <p><code>{X2-:X1+,X3-:X3+)]</code> so that <code>X1-</code> would be the only unmatched node since it does not appear as a key in the output dictionary.</p>
  <p>I followed the networkx documentation to get the corresponding bipartite network and then I used the hopcroft-karp function to obtain the maximum matching. The code that i implemented is outlined below along with the result:</p>
  <pre><code># Add nodes w/ the node attribute bipartite
  G_eg.add_nodes_from([&quot;X1_+&quot;, &quot;X3_+&quot;], bipartite=1)
  G_eg.add_nodes_from([&quot;X2_-&quot;, &quot;X3_-&quot;], bipartite=0)
  # Add edges only between nodes of opposite node sets
  G_eg.add_edges_from([(&quot;X1_+&quot;, &quot;X2_-&quot;), (&quot;X1_+&quot;, &quot;X3_-&quot;), (&quot;X3_+&quot;, &quot;X3_-&quot;)])
  
  #left, right nodes based on node attribute
  left_nodes = {n for n, d in G_eg.nodes(data=True) if d[&quot;bipartite&quot;] == 1}
  right_nodes = set(G_eg) - left_nodes
  
  #apply hopcroft-karp algorithm
  nx.bipartite.hopcroft_karp_matching(G_eg, left_nodes)
  </code></pre>
  <p>output:</p>
  <p><code>{'X3_+': 'X3_-', 'X1_+': 'X2_-', 'X3_-': 'X3_+', 'X2_-': 'X1_+'}</code></p>
  <p>From my output, I can see that <code>X1_-</code> is not listed as a key and therefore it is deemed unmatched. However, why is it that the output gives the result in this way, meaning, it ignores the fact that the network is directed. By including <code>X1_+:X2_-</code> in the output dictionary, it implies that <code>X1_+</code> is matched. Is my interpretation incorrect?</p>