------------------------------------------------------------------------------
MC logo
Graph Search
[^] Python Assignment 5
------------------------------------------------------------------------------
[Python Assignment 1] [Python Assignment 2] [Python Assignment 3] [Python Assignment 4] [Python Assignment 5]
[Graph Tester] [Correct Output For Graph Tester] [Graph Search] [Graph Search Test Input] [Graph Search Test Output]
search.py
#
# This finds shortest (acyclic) paths in a graph.  Input consists of lines
# which are are arcs, then a --- separator, then pairs which are
# requests for the shortest path.  The algorithm returns the cheapest
# acyclic path in the graph.  If there are no negative arcs, this is
# also the cheapest path.
#
from graph import Graph
#from graphsimp import Graph
import sys

g = Graph()
some_neg = False

# See if cost1 >= cost2, accounting for either or both being "infinity", which
# can't be directly compared with a number using >=.  (But can be 
# with == and !=).
def ge(cost1, cost2):
    """Tell if cost1 >= cost2, allowing either to be the string "infinity" """
    if cost1 == "infinity":
        return True
    elif cost2 == "infinity":
        # We already know cost1 isn't infinity, so cost2 is larger.
        return False
    else:
        return cost1 >= cost2

# See if cost1 > cost2, accounting for either or both being "infinity", which
# can't be directly compared with a number using >.  (But can be 
# with == and !=).
def gt(cost1, cost2):
    """Tell if cost1 > cost2, allowing either to be the string "infinity" """
    return cost1 != cost2 and ge(cost1,cost2)

def search(source, to):
    """Find the best (cheapest) cost route from source to to.  Print the route and cost"""
    # Initial best cost is to go directly.  Might be infinity, if there is no arc.
    best_cost =  g.weight(source, to)
    best_route = [ source, to ]

    # List of pending work.  Each list item is a tuple of the path so far, a map
    # representing those locations, and the cost.
    seen = {}
    seen[source] = 1
    pending = [ ( [ source ], seen, 0) ]

    # Go until we've tried everything.
    while len(pending) > 0:
        # Get the data at end of the list, then remove it from the list.
        path, pmap, cost = pending[-1]
        del pending[-1]

        # See if we've got there.
        if path[-1] == to:
            # If this is a better cost, record it as the new best.
            if gt(best_cost, cost):
                best_route = path
                best_cost = cost

            # Since we have arrived, there's really no point in extending this path.
            continue

        # If there are no negative links and we're past the current best cost, 
        # this path won't help and we can stop.
        if not some_neg and ge(cost, best_cost):
            continue

        # Now we need to extend the search one level.  Find each possible successor
        # which does not create a cycle.
        for s in g.successors(path[-1]):
            if not (s in pmap):
                # Add an extension to the list.
                newmap = pmap.copy()
                newmap[s] = 1
                pending.append((path + [s], newmap,
                                cost + g.weight(path[-1],s)))
    # Print the results.
    print (str(best_route)+":", best_cost)

# Load the graph arcs.
line = sys.stdin.readline()
while line:
    if line == "---\n":
        break
    source, to, weight = line.split()
    weight = int(weight)
    g.link(source, to, weight)

    if weight < 0:
        some_neg = True

    line = sys.stdin.readline()

# Process the length requests.
line = sys.stdin.readline()
while line:
    source, to = line.split()
    search(source, to)

    line = sys.stdin.readline()