I'm implementing the following algorithm in Python 3.
Below is what I have so far. My solution is a list comprehension. But I don't know how to do the early escape demanded by the algorithm. In the case that k is even and (u,path[-1]) not in matching, I'd like to stop collecting path + [u] and simply return path + [u].
The reason this is important is that extend_alternating_path is being called from a loop. Every time the parent calls the function it gets back a possibly empty list of paths each of length 1 greater than was given. It tests for some condition, and if false, turns around and calls extend_alternating_path with that list of larger lists. The test on line 6.9 of the pseudocode, allows this exponentially growing set of lists to attenuate early.
def extend_alternating_paths(adj,matching,k,unused_var,paths):
# return list of alternating paths by extending each of the given paths along every
# possible edge, but avoiding self intersection
# this returns a list in dependable order because adj[i] is already in increasing order.
# we assume that the given path is an alternating path so we don't have
# to check it every time.
return [path + [u] for path in paths
for u in adj[path[-1]]
if u not in path
# if k is odd take a matching edge
# if k is even take a not-matching edge
if ((k % 2 == 1) == ((u,path[-1]) in matching or
(path[-1],u) in matching))
]
The following WRONG python code is what I'd like to write. I'd like to collect the values of p which is assigned as p = path + [u] if either the if or elif succeeds. But within the elif if the additional condition un in free is met, then simply return [p] as a singleton list directly from extend_alternating_paths.
def extend_alternating_paths_experimental(adj,matching,k,free,paths):
# return list of alternating paths by extending each of the given paths along every
# possible edge, but avoiding self intersection
# this returns a list in dependable order because adj[i] is already in increasing order.
# we assume that the given path is an alternating path so we don't have
# to check it every time.
return [p for path in paths
for u in adj[path[-1]]
if u not in path
# if k is odd take a matching edge
if ((k % 2 == 1) and ((u,path[-1]) in matching or
(path[-1],u) in matching)):
p = path + [u]
# if k is even take a not-matching edge
elif ((k % 2 == 0) and not ((u,path[-1]) in matching or
(path[-1],u) in matching)):
p = path + [u]
if p in free:
return [p] # return from extend-alternating-paths-experimental
]
