-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathanalysis.py
153 lines (113 loc) · 4.64 KB
/
analysis.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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
from collections import defaultdict
#create a Graph class
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
def add_edge(self, u, v): #basic data structure functions
self.graph[u].append(v)
self.graph[v].append(u)
def remove_edge(self, u, v):
self.graph[u].remove(v)
self.graph[v].remove(u)
def is_valid_next_edge(self, u, v):
if len(self.graph[u]) == 1:
return True
else:
visited = [False] * (self.V)
count1 = self.dfs_count(u, visited)
self.remove_edge(u, v)
visited = [False] * (self.V)
count2 = self.dfs_count(u, visited)
self.add_edge(u, v)
return False if count1 > count2 else True
def dfs_count(self, v, visited):
count = 1
visited[v] = True
for i in self.graph[v]:
if not visited[i]:
count = count + self.dfs_count(i, visited)
return count
def is_eulerian_circuit(self): #all non-zero degree vertices connected?
if not self.is_connected():
return False
odd = 0
for i in range(self.V): #count odd vertices - must be even number!
if len(self.graph[i]) % 2 != 0:
odd += 1
if odd != 0 and odd != 2:
return False
return (odd == 0) or (odd == 2 and self.is_connected()) #check connected if odd ct. 2
def is_connected(self):
visited = [False] * (self.V) #init matrix - all vetices unvisited
for i in range(self.V): #get first vertex with degree >0, return false if none found
if len(self.graph[i]) > 1:
break
if i == self.V - 1: #or if its the last one it fails anyway bc what's it connecting to?
return True
self.dfs(i, visited) #depth-first search
for i in range(self.V): #was everything visited?
if not visited[i] and len(self.graph[i]) > 0:
return False
return True
def dfs(self, v, visited): #recursive depth-first search
visited[v] = True
for i in self.graph[v]:
if not visited[i]:
self.dfs(i, visited)
def is_hamiltonian(self):
def hamiltonian_util(path, pos):
if pos == V:
return self.graph[path[pos - 1]][path[0]] == 1 #vertex between these two points?
for v in range(1, V):
if is_valid(v, pos, path):
path[pos] = v
if hamiltonian_util(path, pos + 1): #recursive: check every possible path
return True
path[pos] = -1
return False
def is_valid(v, pos, path): #is this path valid? (vertex between both points)
if self.graph[path[pos - 1]][v] == 0:
return False
if v in path: #already visited (breaks rules of hamiltonian circuit)
return False
return True
V = len(self.graph) #vertices
path = [-1] * V #init
path[0] = 0
if not hamiltonian_util(path, 1): #check path from 1
return False
print("hamiltonian circuit found: ", end="") #print circuit if exists
for vertex in path:
print(vertex, end=", ")
print(path[0])
return True
def chromatic(self):
colors = [-1] * len(self.graph)
used_colors = set()
for vertex in range(len(self.graph)):
available_colors = set(range(len(self.graph))) #by using sets, avoid repitition
for neighbor in self.graph[vertex]:
if colors[neighbor] != -1:
available_colors.discard(colors[neighbor]) #eliminate not-available possibilities
if available_colors:
color = min(available_colors) #find the smallest one you can use (greedy)
else:
color = max(used_colors) + 1
colors[vertex] = color
used_colors.add(color)
chromatic_number = len(used_colors)
return chromatic_number
# TESTING
#import file
FILENAME = 'test_graph.txt'
file = open(FILENAME)
file.seek(0)
g = Graph(int(file.readline())) #create blank graph
#add edges
l = file.readlines()
for line in l:
g.add_edge(int(line.split()[0]) - 1, int(line.split()[1]) - 1)
euler = g.is_eulerian_circuit()
hamiltonian = g.is_hamiltonian()
chromatic = g.chromatic()