A breadth-first graph search, generates paths with sorted (least-first) cost

README.md

Breadth-first Graph Search

Generates least-cost paths from an adjacency list with one cost factor per edge.

Why did @samba write this?

Simply because I needed the refresher, having taken my last Computer Science class nearly a decade ago, and having focused on a different domain of problems in recent years.

I wanted the practice. :)

graph-breadth.py

#!/usr/bin/python

import pprint
import sys
import re

RECORD = re.compile('^(\w)\s+(\w)\s+(\d+)$')


def readnodes(filename):
    for line in open(filename, 'rb'):
        for match in RECORD.finditer(line):
            start, end, cost = match.group(1, 2, 3)
            yield (start, end), int(cost)


def findStartingVectors(vectors, startpoint):
    for edge, weight in vectors:
        if edge[0] == startpoint:
            yield edge, weight


def findMatchingVectors(vectors, start, end):
    match = vectors.get((start, end), None)
    return ((start, end), match) if match is not None else (None, None)


def sortVectorsByWeight(vectors):
    """ Assumes a list of similar model as `readnodes` yields;
        vectors = [ ((start, end), weight), ... ]
    """
    return sorted(vectors, key = lambda x: x[1])


def iter_group(basedata, size = 2):
    _current = basedata[0:size]
    yield _current[:]
    for v in basedata[size:]:
        _current.pop(0)
        _current.append(v)
        yield _current[:]


def calculatePathCost(vectors, path):
    cost = 0
    for step in iter_group(path, 2):
        vector = findMatchingVectors(vectors, step[0], step[1])
        cost = cost + vector[1]
    return cost




def findpath(start, end, vectors, limit = 10):
    pathqueue = []
    pathtemp = [ start ]

    pathqueue.append(pathtemp[:])  # enqueue the current path :)

    while len(pathqueue) and (limit > 0):
        pathtemp = pathqueue.pop(0)
        _last = pathtemp[-1]

        if _last == end:
            limit = limit - 1
            yield pathtemp, calculatePathCost(vectors, pathtemp)

        else:
            _vectorlist = findStartingVectors(vectors.iteritems(), _last)
            for edge, weight in sortVectorsByWeight(_vectorlist):
                pathqueue.append(pathtemp + [ edge[1] ])


def main(args):
    vectors = dict(readnodes(args[0]))
    start = 'A' if len(args) < 2 else args[1]
    end = 'Z' if len(args) < 3 else args[2]
    paths = sorted(findpath(start, end, vectors), key = lambda x: x[1])
    pprint.pprint(paths)

if __name__ == '__main__':
    main(sys.argv[1:])

sample-output.txt

$ python graph-breadth.py  sampledata.txt
[(['A', 'B', 'C', 'K', 'Y', 'Z'], 16),
 (['A', 'C', 'K', 'Y', 'Z'], 17),
 (['A', 'B', 'C', 'K', 'S', 'W', 'Z'], 25),
 (['A', 'B', 'D', 'T', 'Q', 'Z'], 26),
 (['A', 'C', 'K', 'S', 'W', 'Z'], 26),
 (['A', 'B', 'C', 'D', 'T', 'Q', 'Z'], 27),
 (['A', 'C', 'D', 'T', 'Q', 'Z'], 28),
 (['A', 'B', 'C', 'K', 'S', 'Q', 'Z'], 29),
 (['A', 'C', 'K', 'S', 'Q', 'Z'], 30)]

sampledata.txt

A B  2
B C  3
A C  6
B D  3
C D  1
D T  5
C K  7
K Y  3
K S  2
S W 10
Y Z  1
T Q  5
S Q  4
Q Z 11
W Z  1