Add utility: max_path_set

[math1um]

Return a set of vertices which induces a maximum-cardinality (with respect to vertices) path. This won't generally be unique.The cardinality of this set of vertices in the induced-path-number, investigated for instance in: Erdös, Paul, Michael Saks, and Vera T. Sós. "Maximum induced trees in graphs." Journal of Combinatorial Theory, Series B 41.1 (1986): 61-79.

This should work, but needs testing. Requires is_path(g) for graph g. See: #409

def max_path_set(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(is_path(Gprime)):
        #print "{} is not path".format(SCopy)
        return max_path_set(g, s, CCopy)

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

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

[math1um]

this is an improvement, with an invariant, a function which only takes the graph as input, and an auxilliary function which is recursive

this still needs further testing (and doctests!)

this uses is_path, also defined here:

check 3 conditions:

1. graph is connected

2. sum of degrees = 2*order

3. maximum degree <= 2

def is_path(g): if not g.is_connected(): return False sum_of_degrees = sum(g.degree()) if sum_of_degrees != 2*g.order()-2: return False if max(g.degree()) > 2: return False else: return True

input just the graph into main functio, which calls the auxilliary function

def length_max_induced_path(g): return len(max_path_set(g))

def max_path_set(g): return max_path_set_aux(g,[],g.vertices())

def max_path_set_aux(g,s,c): #auxilliary function

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(is_path(Gprime)):
    #print "{} is not path".format(SCopy)
    return max_path_set_aux(g, s, CCopy)

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

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

[math1um]

2nd naive version of the code for testing purposes

naive algorithm for finding the cardinality of a max_induced_path

verts keeps track of the largest set which induces a path thats been seen so far

this algorith will look at every single subset of vertices

so this won't work for anything very big - but good enough for testing small graphs

def naive_max_induced_path(g):

set_of_subsets = Set(g.vertices()).subsets()

verts = 0

for x in set_of_subsets:
    #print x
    h = g.subgraph(list(x))
    if is_path(h):
        if h.order() > verts:
            verts = h.order()

return verts

[a234]

It seems that something is going wrong in the code, or I may not understand the code correctly. When applied to the Moebius-Kantor Graph , the function returns [1, 2, 3, 4, 5, 6, 7, 9, 15] as a max_path_set. But there is a longer induced path:[13, 8, 11, 5, 6, 7, 3, 2, 1, 9, 12], which could be found by the naive version.

Something similar is happening on the Errera Graph: the function returns [3, 4, 5, 6, 8, 9, 14, 15] , while [15, 7, 1, 14, 8, 10, 3, 11, 5] is a longer max_path_set.

And so does the Kittell Graph: the function returns [2, 4, 5, 6, 7, 8, 9, 11, 12, 20, 22], while [20, 10, 13, 8, 18, 17, 15, 12, 3, 5, 0, 2] is a longer max_path_set.