-
Notifications
You must be signed in to change notification settings - Fork 1
/
MDM1 22-02-22.py
138 lines (104 loc) · 4.84 KB
/
MDM1 22-02-22.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
import numpy as np
import Generator as G
import Graph_Generator as Map
import math as m
def RandMatGen (N):
a = np.random.rand(N, N) # set diagonal to 0
np. fill_diagonal(a, 0) # np.tril returns a copy of an array with elements above the k-th diagonal zeroed.
M = np.tril(a) + np.tril(a, -1).T # lower triangle + a transpose of upper triangle
return (M)
def MatToUTList(M,N): # Converts the matrix to and upper triangular list
UTList = []
X = 0
while X < N-1: # Loops through Rows until penultimate (last row isnt in upper triangular)
# Note loop starts from 0 because matrix row 1 is known as 0 in programming
for Y in range(X+1,N): # Loops through the columns for the upper triangular
UTList.append(M[X,Y]) # appends item to the list
X += 1 # selects next row
return(UTList)
def CreateTuple(InputList,N):
CharacterList = G.MatrixPairingList(N) # Creates the list of letter pairs
TupleList = list(zip(InputList,CharacterList)) # Joins Inputs and letter pairs in ordered pairs
return(TupleList)
def CombinedListSort(ProcessingList):
ProcessingList.sort(key = lambda x: x[0]) # Sorts the combined list by matrix values
return(ProcessingList)
def MemberCheck(TestSet, Letters): #
First = 0
Second = 0
Returns = ""
if Letters[0] in TestSet:
First = True
Returns = Letters[0]
if Letters[1] in TestSet:
Second = True
Returns = Letters[1]
if First == Second == True:
return("none")
return(Returns)
def MinimumSpanningTree(Sorted,N): # Sorted: list of paths, order of mag
Divisions = [] # Attempt to avoid loops
CorrectPaths = [] # The programs aim
for item in Sorted: # Loops through every item and also provides their position in the set
Merging = []
Located = []
PathLoop = False
TestLetters = list(item[1]) # Turns the two letter path into two list elements
if len(Divisions) == 0: # The first path becomes a subset
Divisions.append([TestLetters[0],TestLetters[1]])
CorrectPaths.append(item) # Shortest path is always part of MST
continue
for index,subset in enumerate(Divisions):
FoundLetter = MemberCheck(subset,TestLetters)
if FoundLetter == "none":
PathLoop = True
continue
if len(FoundLetter) != 0:
Merging.append(index)
Located.append(FoundLetter)
if PathLoop == True:
continue
CorrectPaths.append(item)
if len(Located)== 1:
Divisions[Merging[0]].extend(TestLetters)
Divisions[Merging[0]]= list(set(Divisions[Merging[0]]))
elif len(Located) == 0:
Divisions.append(TestLetters)
else:
Divisions[Merging[0]].extend(Divisions[Merging[1]])
Divisions.remove(Divisions[Merging[1]])
return(CorrectPaths)
def Weights(All,MST):
AllLen = MSTLen = 0
for item1 in All:
AllLen += item1[0]
for item2 in MST:
print(type(item2),item2)
MSTLen += item2[0]
print("Total length of all paths = ",AllLen)
print("Total Length of MST paths = ",MSTLen)
# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# ~~ Temporary Value Assignment ~~
# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
N = 5 # Matrix size (NxN)
# ~~~~~~~~~~~~~~~~~
# ~~ Running Hub ~~
# ~~~~~~~~~~~~~~~~~
#InputList = [,4,67,23,]
InputMatrix = RandMatGen(N) # Makes the input matrix
InputList = MatToUTList(InputMatrix,N) # Turns input matrix into an upper triangular list
Joined = CreateTuple(InputList, N) # Pairs the upper triangular list with letter pairs
Sorted = CombinedListSort(Joined) # Sorts the combined list
Output = MinimumSpanningTree(Sorted,N)
Weights(Sorted,Output)
Map.GenerateGraph(Output)
#print("\n\n", MinimumSpanningTree(Sorted,N))
#Debug(Sorted)
# ~~~~~~~~~~~~~~~~~~~~~~~
# ~~ Temporary outputs ~~
# ~~~~~~~~~~~~~~~~~~~~~~~
# print(InputMatrix, "\n")
# print(InputList, "\n")
# print(Joined, "\n")
# print (Sorted)
# Map.GenerateGraph()