Add utility: bipartite set

[cjoshea9]

def bs(g,s,c):
    #print "s is {}".format(s)
    #print "c is {}".format(c)
    if len(c) == 0:
        return s

    v = c[0]
    #print "v is {}".format(v)
    SCopy = copy(s)
    SCopy.append(v)
    Gprime = g.subgraph(SCopy)

    CCopy = copy(c)
    CCopy.remove(v) #CCopy is C with v removed
    if not(Gprime.is_bipartite()):
        #print "{} is not bipartite".format(SCopy)
        return bs(g, s, CCopy)

    temp1 = bs(g, SCopy, CCopy)
    temp2 = bs(g, s, CCopy)

    if len(temp1) > len(temp2):
        return temp1
    else:
        return temp2

[math1um]

Need docstring (what are the input parameters???)

[yirkajk]

@rbarden @cjoshea9 Can you explain what this function is meant to do? I'd like to add a docstring about it. Also, when I run max_bipartite_set(k6, [0,1,2], [3,4]), I get back [0,1,2], which I don't think is a bipartite subgraph...

[math1um]

It looks like this is an auxilliary function for computing the bipartite number of a graph: that is, the size of a maximum set of vertices that induces a bipartite subgraph.

This number comes up, for instance, in investigations of the independence number of a graph (alpha >= 0.5*bipartite number).

The function above looks like maybe it is trying to use the idea of the Tarjan-Trojanowski maximum independent set algorithm to find a maximum bipartite subgraph. The basic idea here would be: either a vertex v is in a maximum bipartite subgraph or it is not.

In an case, a properly written function should return a 2-element set if the input is a complete graph (with order at least 2) and bipartite_number(Kn)=2.