Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#!/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(max - 2, 1, -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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment