0

I have used the thread Call Python function from MATLAB and have implemented it successfully in Matlab.

However, the following code in python reflects no output in Matlab, and due to my lack of familiarity with Python, I can't see where the problem may originate from!

So here is the python code which takes a graph as input like :

bipartiteMatch({0:[0,1,3],1:[3,4],2:[1,2,4],3:[2,3,4],4:[0,2,3]})

and gives the set of maximum matchings in the form above,

# Hopcroft-Karp bipartite max-cardinality matching and max independent set
# David Eppstein, UC Irvine, 27 Apr 2002
#import sys
def bipartiteMatch(graph):
'''Find maximum cardinality matching of a bipartite graph (U,V,E).
The input format is a dictionary mapping members of U to a list
of their neighbors in V.  The output is a triple (M,A,B) where M is a
dictionary mapping members of V to their matches in U, A is the part
of the maximum independent set in U, and B is the part of the MIS in V.
The same object may occur in both U and V, and is treated as two
distinct vertices if this happens.'''

# initialize greedy matching (redundant, but faster than full search)
matching = {}
for u in graph:
    for v in graph[u]:
        if v not in matching:
            matching[v] = u
            break

while 1:
    # structure residual graph into layers
    # pred[u] gives the neighbor in the previous layer for u in U
    # preds[v] gives a list of neighbors in the previous layer for v in V
    # unmatched gives a list of unmatched vertices in final layer of V,
    # and is also used as a flag value for pred[u] when u is in the first       layer
    preds = {}
    unmatched = []
    pred = dict([(u,unmatched) for u in graph])
    for v in matching:
        del pred[matching[v]]
    layer = list(pred)

    # repeatedly extend layering structure by another pair of layers
    while layer and not unmatched:
        newLayer = {}
        for u in layer:
            for v in graph[u]:
                if v not in preds:
                    newLayer.setdefault(v,[]).append(u)
        layer = []
        for v in newLayer:
            preds[v] = newLayer[v]
            if v in matching:
                layer.append(matching[v])
                pred[matching[v]] = v
            else:
                unmatched.append(v)

    # did we finish layering without finding any alternating paths?
    if not unmatched:
        unlayered = {}
        for u in graph:
            for v in graph[u]:
                if v not in preds:
                    unlayered[v] = None
        return (matching,list(pred),list(unlayered))

    # recursively search backward through layers to find alternating paths
    # recursion returns true if found path, false otherwise
    def recurse(v):
        if v in preds:
            L = preds[v]
            del preds[v]
            for u in L:
                if u in pred:
                    pu = pred[u]
                    del pred[u]
                    if pu is unmatched or recurse(pu):
                        matching[v] = u
                        return 1
        return 0

    for v in unmatched: recurse(v)

I can see the output and run the code in python successfully, but the output is not shown in Matlab and returns " " as the answer.

So any kind of help is extremely appreciated!

Community
  • 1
  • 1
HMDRZAA
  • 3
  • 2
  • there is not return statement at the bottom of the function, if it reaches the end without hitting a return statement it implicitly returns `None` (which I assume matlab converts to " ") – Tadhg McDonald-Jensen Mar 14 '17 at 16:01
  • you may want either `return all(recurse(v) for v in unmatched)` or similarly with `any` to return a boolean, but based on the other return statement you have I'm not sure a boolean is the desired result... – Tadhg McDonald-Jensen Mar 14 '17 at 16:02
  • thanks for the comment; but unfortunately this does not seem to work ... – HMDRZAA Mar 14 '17 at 17:34
  • What are you expecting to return to matlab? After looking at the other thread it looks like it doesn't call any functions but treats the script as the system call - which means you need to use `sys.argv` for the arguments passed from matlab and write to `sys.stdout` (by printing) to return stuff to matlab. Since you do neither your script is really only defining a function the quitting. – Tadhg McDonald-Jensen Mar 14 '17 at 18:18

0 Answers0