Ggthjy

Can some of you check what's wrong in my implementation of Hopcroft Karp algorithm to find maximum matching in a bipartite graph?

I implemented it as a method of my Graph() class, the method input consists in two lists or set of nodes (representing the two sets of nodes of a bipartite graph).
It seems that the code, SOMETIMES, isn't able to find an augmenting path. Sometimes instead it works, but it seems casual.

 class Graph:



def __init__(self, TarjanSCC = False, Directed = True):

    self.TarjanSCC = TarjanSCC

    self.Directed = Directed

    self.Nodes = {}



def add_node(self,key):

    self.Nodes[str(key)] = {,'AdjacencyList':{}}



def add_edge(self, start_node, target_node, weight = 1):

    if(str(start_node) not in self.Nodes.keys()):

        self.add_node(start_node)

    if(str(target_node) not in self.Nodes.keys()):

        self.add_node(target_node)

    self.Nodes[str(start_node)]['AdjacencyList'][str(target_node)] = {'weight' : weight}

    if not self.Directed:

        self.Nodes[str(target_node)]['AdjacencyList'][str(start_node)] = {'weight' : weight}  



def HopcroftKarp(self,u,v):

    global U,V,M,unmatched_nodesU,unmatched_nodesV



    U = set(map(str,u))

    V = set(map(str,v))

    if self.Directed:

        raise Exception("Can't compute Hopcroft Karp algorithm for a DIRECTED graph.") 

    self._initializeHK()

    while True:

        AP = self._BFS_HK() 

        if not AP:

            return M

        else:

            M = M ^ AP

            unmatched_nodesU = U-set([el[0] for el in M])

            unmatched_nodesV = V-set([el[1] for el in M])



def _initializeHK(self):

    global U,V,M,unmatched_nodesU,unmatched_nodesV

    M = set()

    free_vertices = {el:True for el in V}

    for el in U:

        for node in self.Nodes[el]['AdjacencyList'].keys():

            if node in free_vertices:

                M.add((el,node))

                del free_vertices[node]

                break

    unmatched_nodesU = U-set([el[0] for el in M])

    unmatched_nodesV = V-set([el[1] for el in M])



def _BFS_HK(self):

    global unmatched_nodesU

    global unmatched_nodesV

    global M

    global U

    global V

    vis = set()

    vis.clear() 

    queue = list(copy.deepcopy(unmatched_nodesU))

    alt_g = Graph()

    while queue:

        tmp = queue.pop(0)

        vis.add(tmp)

        if tmp in U:

            for succ in self.Nodes[tmp]['AdjacencyList'].keys():

                if (tmp,succ) not in M and succ not in vis:

                    alt_g.add_edge(tmp,succ)

                    queue.append(succ)          

        else:

            for succ in self.Nodes[tmp]['AdjacencyList'].keys():

                if (succ,tmp) in M and succ not in vis:

                    alt_g.add_edge(tmp,succ)

                    queue.append(succ)                

    AP = self._DFS_HK(alt_g)

    if AP:

        return AP

    else:

        return None



def _DFS_HK(self,alt_g):

    global unmatched_nodesU,visited,fathers

    fathers = {}

    fathers.clear()

    visited = set()

    visited.clear()

    queue = list(copy.deepcopy(unmatched_nodesU))

    for node in unmatched_nodesU:

        if node not in visited and node in alt_g.Nodes.keys():

            fathers[node] = None

            AP = self._DFS_HK_xplore(alt_g,node)

            if AP:

                return AP  

        else:

            continue

    return None



def _DFS_HK_xplore(self,alt_g,node):

    global U,V,M,unmatched_nodesV,fathers,visited

    visited.add(node)

    if node in unmatched_nodesV:

        AP = []

        t = node

        while t != None:

            AP.insert(0,t)

            t = fathers[t]

        return self._get_edges(AP)

    for el in alt_g.Nodes[node]['AdjacencyList'].keys():

        if el not in visited:

            fathers[el] = node

            return self._DFS_HK_xplore(alt_g,el)



def _get_edges(self,AP):

    global U

    edges = set()

    edges.clear()

    for i in range(1,len(AP)):

        if AP[i-1] in U:

            edges.add((AP[i-1],AP[i]))

        else:

            edges.add((AP[i],AP[i-1]))

    return edges