pygorithm/pygorithm/data_structures/graph.py at master · OmkarPathak/pygorithm · GitHub

History

421 lines (360 loc) · 12.8 KB

Raw

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

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

"""

Author: OMKAR PATHAK

Created On: 12th August 2017

"""

from collections import defaultdict

import inspect

import math

class Graph(object):

"""Graph object

Creates the graph

"""

def __init__(self):

self.graph = defaultdict(list)

self.count = 0

def print_graph(self):

"""

Prints the contents of the graph

"""

for i in self.graph:

print(i, '->', ' -> '.join([str(j) for j in self.graph[i]]))

def add_edge(self, from_vertex, to_vertex):

"""

Adds an edge in the graph

"""

# check if vertex is already present

self.graph[from_vertex].append(to_vertex)

self.count += 1

def get_code(self):

"""

returns the code for the current class

"""

return inspect.getsource(Graph)

class WeightedGraph(object):

"""WeightedGraph object

A graph with a numerical value (weight) on edges

"""

def __init__(self):

self.vertexes = set()

self.graph = {}

self._forest = None

def get_weight(self, u, v):

"""

Returns the weight of an edge between vertexes u and v.

If there isnt one: return None.

"""

return self.graph.get((u,v), self.graph.get((v,u), None))

def add_edge(self, u, v, weight):

"""

:param u: from vertex - type : integer

:param v: to vertex - type : integer

:param weight: weight of the edge - type : numeric

"""

if self.get_weight(u, v) != None:

print("Such edge already exists!")

else:

self.vertexes.update((u, v))

self.graph[(u,v)] = weight

def print_graph(self):

"""

Print the graph

:return: None

"""

for (u, v) in self.graph:

print("%d -> %d weight: %d" % (u, v, self.graph[(u, v)]))

def _set_of(self, vertex):

"""

Helper method

:param vertex:

:return:

"""

for tree in self._forest:

if vertex in tree:

return tree

return None

def _union(self, u_set, v_set):

"""

Helper method

:param u_set:

:param v_set:

:return:

"""

self._forest.remove(u_set)

self._forest.remove(v_set)

self._forest.append(v_set + u_set)

def kruskal_mst(self):

"""

Kruskal algorithm for finding the minimum spanning tree of a weighted graph.

This version use a union-find data structure.

More detailed info here: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

Author: Michele De Vita <mik3dev@gmail.com>

"""

# sort by weight

self.graph = {k: self.graph[k] for k in sorted(self.graph, key=self.graph.get, reverse=False)}

edges_explored = []

self._forest = [[v] for v in self.vertexes]

for (u, v) in self.graph:

u_set, v_set = self._set_of(u), self._set_of(v)

if u_set != v_set:

self._union(u_set, v_set)

edges_explored.append(((u, v), self.graph[u, v]))

return edges_explored

# TODO: Is this necessary?

@staticmethod

def kruskal_time_complexity():

"""

Return time complexity of kruskal

:return: string

"""

return "Worst case: O(E log(V)) where E in the number of edges and V the number of vertexes"

@classmethod

def kruskal_code(cls):

"""

Returns the code for current class

"""

return inspect.getsource(cls.kruskal_mst)

class WeightedUndirectedGraph(object):

"""WeightedUndirectedGraph object

A graph with a numerical value (weight) on edges, which

is the same for both directions in an undirected graph.

"""

def __init__(self):

self.graph = {}

self.weights = {}

def add_edge(self, u, v, weight):

"""

Adds the specified edge to this graph. If the edge already exists,

this will only modify the weight (not create duplicates).

:param u: from vertex

:param v: to vertex

:param weight: weight of the edge - type : numeric

"""

changing_weight = (u, v) in self.weights.keys()

self.weights[(u, v)] = weight

self.weights[(v, u)] = weight

if changing_weight:

return

if u in self.graph.keys():

self.graph[u].append(v)

else:

self.graph[u] = [v]

if v in self.graph.keys():

self.graph[v].append(u)

else:

self.graph[v] = [u]

def get_edge_weight(self, u, v):

"""

Gets the weight between u and v if such an edge

exists, or None if it does not.

:param u: one edge

:param v: the other edge

:return: numeric or None

"""

return self.weights.get((u, v), None)

def remove_edge(self, edge, other_edge_or_none=None):

"""

Removes the specified edge from the grid entirely or,

if specified, the connection with one other edge.

Behavior is undefined if the connection does not

exist.

:param edge: the edge to remove

:param other_edge_or_none: an edge connected to edge or none

"""

if other_edge_or_none is not None:

del self.weights[(edge, other_edge_or_none)]

del self.weights[(other_edge_or_none, edge)]

edge_list = self.graph[edge]

other_edge_list = self.graph[other_edge_or_none]

if len(edge_list) == 1:

del self.graph[edge]

else:

self.graph[edge].remove(other_edge_or_none)

if len(other_edge_list) == 1:

del self.graph[other_edge_or_none]

else:

self.graph[other_edge_or_none].remove(edge)

else:

edge_list = self.graph[edge]

del self.graph[edge]

for other_edge in edge_list:

del self.weights[(edge, other_edge)]

del self.weights[(other_edge, edge)]

other_edge_list = self.graph[other_edge]

if len(other_edge_list) == 1:

del self.graph[other_edge]

else:

other_edge_list.remove(edge)

def gridify(self, size, weight):

"""

Constructs connections from a square grid starting at (0, 0)

until (size-1, size-1) with connections between adjacent and

diagonal nodes. Diagonal nodes have a weight of weight*sqrt(2)

:param size: the size of the square grid to construct - type : integer

:param weight: the weight between orthogonal nodes. - type: numeric

:return: None

"""

rt2 = math.sqrt(2)

acceptable_offsets = [

(-1, -1, rt2), (-1, 0, 1), (-1, 1, rt2),

(0, -1, 1), (0, 1, 1),

(1, -1, rt2), (1, 0, 1), (1, 1, rt2)

]

for x in range(0, size):

for y in range(0, size):

for offset in acceptable_offsets:

nx = x + offset[0]

ny = y + offset[1]

if nx >= 0 and ny >= 0 and nx < size and ny < size:

self.add_edge((x, y), (nx, ny), weight * offset[2])

class TopologicalSort(Graph):

def topological_sort(self):

"""

function for sorting graph elements using topological sort

"""

# Marking all vertices as not visited

visited = [False] * self.count

# Stack for storing the vertex

stack = []

for vertex in range(self.count):

# Call the recursive function only if not visited

if not visited[vertex]:

self.__topological_sort_rec(vertex, visited, stack)

return stack

def __topological_sort_rec(self, vertex, visited, stack):

"""

Recursive function for topological Sort

"""

# Mark the current node in visited

visited[vertex] = True

# mark all adjacent nodes of the current node

try:

for adjacent_node in self.graph[vertex]:

if not visited[adjacent_node]:

self.__topological_sort_rec(adjacent_node, visited, stack)

except KeyError:

return

# Push current vertex to stack which stores the result

stack.insert(0, vertex)

def get_code(self):

"""

returns the code for the current class

"""

return inspect.getsource(TopologicalSort)

class CheckCycleDirectedGraph(object):

"""CheckCycleDirectedGraph

Class to check cycle in directed graph

"""

def __init__(self):

self.graph = {}

self.count = 0

def print_graph(self):

"""

for printing the contents of the graph

"""

for i in self.graph:

print(i, '->', ' -> '.join([str(j) for j in self.graph[i]]))

def add_edge(self, from_vertex, to_vertex):

"""

function to add an edge in the graph

"""

# check if vertex is already present

if from_vertex in self.graph.keys():

self.graph[from_vertex].append(to_vertex)

self.count += 1

else:

self.graph[from_vertex] = [to_vertex]

self.count += 1

def check_cycle(self):

"""

This function will return True if graph is cyclic else return False

"""

visited = [False] * len(self.graph)

stack = [False] * len(self.graph)

for vertex in range(len(self.graph)):

if not visited[vertex]:

if self.__check_cycle_rec(visited, stack, vertex):

return True

return False

def __check_cycle_rec(self, visited, stack, vertex):

"""

Recursive function for finding the cycle

"""

# Mark the current node in visited and also add it to the stack

visited[vertex] = True

stack[vertex] = True

# mark all adjacent nodes of the current node

for adjacentNode in self.graph[vertex]:

if not visited[adjacentNode]:

if self.__check_cycle_rec(visited, stack, adjacentNode):

return True

elif stack[adjacentNode]:

return True

# The node needs to be popped from

# recursion stack before function ends

stack[vertex] = False

return False

@staticmethod

def get_code():

"""

returns the code for the current class

"""

return inspect.getsource(CheckCycleDirectedGraph)

class CheckCycleUndirectedGraph(object):

"""CheckCycleUndirectedGraph

Class to check cycle in undirected graph

"""

def __init__(self):

self.graph = {}

self.count = 0

def print_graph(self):

"""

for printing the contents of the graph

"""

for i in self.graph:

print(i, '->', ' -> '.join([str(j) for j in self.graph[i]]))

def add_edge(self, from_vertex, to_vertex):

"""

for adding the edge between two vertices

"""

# check if vertex is already present,

if from_vertex in self.graph.keys():

self.graph[from_vertex].append(to_vertex)

else:

# otherwise add it to the graph

self.graph[from_vertex] = [to_vertex]

if to_vertex in self.graph.keys():

self.graph[to_vertex].append(from_vertex)

else:

self.graph[to_vertex] = [from_vertex]

def check_cycle(self):

"""

This function will return True if graph is cyclic else return False

"""

# Marking all vertices as not visited

visited = [False] * len(self.graph)

for vertex in range(len(self.graph)):

# Call the recursive function only if not visited

if not visited[vertex]:

if self.__check_cycle_rec(visited, -1, vertex):

return True

return False

def __check_cycle_rec(self, visited, parent, vertex):

"""

Recursive function for finding the cycle

"""

# Mark the current node in visited

visited[vertex] = True

# mark all adjacent nodes of the current node

for adjacentNode in self.graph[vertex]:

if not visited[adjacentNode]:

if self.__check_cycle_rec(visited, vertex, adjacentNode):

return True

elif parent != adjacentNode:

return True

return False

@staticmethod

def get_code():

"""

returns the code for the current class

"""

return inspect.getsource(CheckCycleUndirectedGraph)

pygorithm/pygorithm/data_structures/graph.py at master · OmkarPathak/pygorithm · GitHub

Expand file tree

Breadcrumbs

graph.py

Latest commit

History

Breadcrumbs

graph.py

File metadata and controls