lab3.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

import copy
import sys

from pprint import pprint

max = 16
graf = {1: {4: 3, 'v': 1}, 2: {5: 1, 'v': 3}, 3: {13: 3, 'v': 2},
        4: {6: 4, 7: 2, 'v': 3}, 5: {8: 7, 9: 4, 'v': 1}, 6: {11: 2, 'v': 4},
        7: {10: 6, 'v': 2}, 8: {10: 6, 'v': 7}, 9: {10: 6, 11: 2, 'v': 4},
        10: {12: 8, 'v': 6}, 11: {13: 3, 'v': 2}, 12: {14: 3, 'v': 8},
        13: {15: 2, 'v': 3}, 14: {max+1: 1, 'v': 3}, 15: {max+1: 1, 'v': 2}}

grafif = {4: {6: 'T', 7: 'F'}, 5: {8: 'T', 9: 'F'}}


def dijkstra(graph, start_node, target=None):
    # initialize distance list
    dist = dict()
    previous = dict()
    dist[start_node] = 0
    Q = copy.deepcopy(graph)

    def extract_min():
        min = None
        ret = None
        for key in dist:
            if key in Q and ((dist[key] < min) if min is not None else True):
                min = dist[key]
                ret = key
        if ret is not None:
            del Q[ret]
        return ret
    while Q:
        u = extract_min()
        for v in graph[u]:
            alt = dist[u] + graph[u][v]
            if v not in dist or alt < dist[v]:
                dist[v] = alt
                previous[v] = u
    node_list = list()
    try:
        next = target
        while True:
            node_list.insert(0, next)
            next = previous[next]
    except:
        pass
    return len(node_list) - 1


def maidan():
    result = []
    for x in xrange(1, max):
        tmp = []
        for y in xrange(1, max):
            try:
                if y in graf[x].keys():
                    if x in grafif.keys():
                        tmp.append("%d%s" % (x, grafif[x][y]))
                    else:
                        tmp.append(1)
                else:
                    tmp.append(0)
            except KeyError:
                pass
        result.append(tmp)
    print 'Матрица следования S по заданному графу:'
    pprint(list(zip(*result)))
    res = list(zip(*result))
    tmp = []
    for x in res:
        tmp.append(list(x))
    res = tmp
    # print
    result.append([graf[r]['v'] for r in graf.keys()])
    norm_result = list(zip(*result))
    # pprint(norm_result)
    for x in range(max - 1):
        for y in xrange(1, max - 1):
            if res[x][y] != 0:
                i = x
                j = y
                res = matrix(i, j, res)
    print 'Матрица следования SR (с указанием весов):'
    pprint(norm_result)
    print 'Матрица следования ST с транзитивными связями:'
    pprint(res)


def matrix(i, j, res):
    for x in range(j):
        res = nematrix(i, j, x, res)
    return res


def nematrix(i, j, k, res):
    try:
        a1 = res[j][k]
        a2 = res[i][j]
        a3 = res[i][k]
        donbas = sum(nesum(a1, a2), a3)
        res[i][k] = donbas
        return res
    except:
        print i, j, k
        print a1, a2, a3
        print res[i][k]
        sys.exit(0)


def nesum(a, b):
    if a == 0 or b == 0:
        return 0
    elif a == 1:
        return b
    elif b == 1:
        return a
    else:
        return "%s,%s" % (a,b)


def sum(a, b):
    if b == 0:
        return a
    elif a == 0:
        return b
    else:
        return a


def main():
    maidan()

if __name__ == '__main__':
    main()