In Addition, A Bi-Partition

bipartition.py

ArcMatchingDatum = coll.namedtuple('ArcMatchingDatum', ['inMatching' ])
NodeMatchingDatum = coll.namedtuple('NodeMatchingDatum', ['visited'])

def dfs_helper(snodes, G):
    sniter, do_stop = iter(snodes), False
    visited, visited_uids = set(), set()
    while(not do_stop):
        try:
            stack = [ next(sniter) ]
            while len(stack) > 0:
                curr = stack.pop()
                if curr.uid not in visited_uids:
                    visited = visited.union( frozenset( {Node(curr.uid, NodeMatchingDatum(False))} ) )
                    visited_uids = visited.union(frozenset({curr.uid}))
                    succ = frozenset({a.toNode for a in G.setOfArcs if a.fromNode == curr})
                    stack.extend( succ.difference( frozenset(visited) ) )
        except StopIteration as e:
            stack, do_stop = [], True
    return visited

def get_min_node_cover(matching, bipartition):
    nodes = frozenset( { Node(n.uid, NodeMatchingDatum(False)) for n in bipartition.G.setOfNodes} )
    G = DiGraph(nodes, None)
    charcs = frozenset( {a for a in matching if ( (a.fromNode in bipartition.firstPart) and (a.toNode in bipartition.secondPart) )} )
    arcs0 = frozenset( { Arc(find_node_by_uid(a.toNode.uid,G), find_node_by_uid(a.fromNode.uid,G), ArcMatchingDatum(True) ) for a in charcs } )
    arcs1 = frozenset( { Arc(find_node_by_uid(a.fromNode.uid,G), find_node_by_uid(a.toNode.uid,G), ArcMatchingDatum(True) ) for a in matching.difference(charcs) } )
    not_matching = bipartition.G.setOfArcs.difference( matching )
    charcs = frozenset( {a for a in not_matching if ( (a.fromNode in bipartition.secondPart) and (a.toNode in bipartition.firstPart) )} )
    arcs2 = frozenset( { Arc(find_node_by_uid(a.toNode.uid,G), find_node_by_uid(a.fromNode.uid,G), ArcMatchingDatum(False) ) for a in charcs } )
    arcs3 = frozenset( { Arc(find_node_by_uid(a.fromNode.uid,G), find_node_by_uid(a.toNode.uid,G), ArcMatchingDatum(False) ) for a in not_matching.difference(charcs) } )
    arcs = arcs0.union(arcs1.union(arcs2.union(arcs3)))

    G = DiGraph(nodes, arcs)
    bip = Bipartition({find_node_by_uid(n.uid,G) for n in bipartition.firstPart},{find_node_by_uid(n.uid,G) for n in bipartition.secondPart},G)
    match_from_nodes = frozenset({find_node_by_uid(a.fromNode.uid,G) for a in matching})
    match_to_nodes = frozenset({find_node_by_uid(a.toNode.uid,G) for a in matching})
    snodes = bip.firstPart.difference(match_from_nodes).difference(match_to_nodes)
    visited_nodes = dfs_helper(snodes, bip.G)
    not_visited_nodes = bip.G.setOfNodes.difference(visited_nodes)

    H = DiGraph(visited_nodes.union(not_visited_nodes), arcs)
    cover1 = frozenset( {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } )
    cover2 = frozenset( {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (not a.toNode.datum.visited) ) } )
    min_cover_nodes = cover1.union(cover2)
    true_min_cover_nodes = frozenset({find_node_by_uid(n.uid, bipartition.G) for n in min_cover_nodes})

    return min_cover_nodes