Created
July 9, 2017 01:24
-
-
Save darkhipo/d718c4456c9906c2f82f901ae3471291 to your computer and use it in GitHub Desktop.
In Addition, A Bi-Partition
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment