Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# anirudhjayaraman/graphUndirected.ipynb

Created Jul 28, 2016
Python Implementation of Undirected Graphs (Adjacency List and Adjacency Matrix)
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

### AST9712 commented Nov 29, 2017

 It gives syntax error on print graph(g). What do I do?

### itaditya commented Jan 4, 2018

 ```class Vertex: def __init__(self, vertex): self.name = vertex self.neighbors = [] def add_neighbor(self, neighbor): if isinstance(neighbor, Vertex): if neighbor.name not in self.neighbors: self.neighbors.append(neighbor.name) neighbor.neighbors.append(self.name) self.neighbors = sorted(self.neighbors) neighbor.neighbors = sorted(neighbor.neighbors) else: return False def add_neighbors(self, neighbors): for neighbor in neighbors: if isinstance(neighbor, Vertex): if neighbor.name not in self.neighbors: self.neighbors.append(neighbor.name) neighbor.neighbors.append(self.name) self.neighbors = sorted(self.neighbors) neighbor.neighbors = sorted(neighbor.neighbors) else: return False def __repr__(self): return str(self.neighbors) class Graph: def __init__(self): self.vertices = {} def add_vertex(self, vertex): if isinstance(vertex, Vertex): self.vertices[vertex.name] = vertex.neighbors def add_vertices(self, vertices): for vertex in vertices: if isinstance(vertex, Vertex): self.vertices[vertex.name] = vertex.neighbors def add_edge(self, vertex_from, vertex_to): if isinstance(vertex_from, Vertex) and isinstance(vertex_to, Vertex): vertex_from.add_neighbor(vertex_to) if isinstance(vertex_from, Vertex) and isinstance(vertex_to, Vertex): self.vertices[vertex_from.name] = vertex_from.neighbors self.vertices[vertex_to.name] = vertex_to.neighbors def add_edges(self, edges): for edge in edges: self.add_edge(edge,edge) def adjacencyList(self): if len(self.vertices) >= 1: return [str(key) + ":" + str(self.vertices[key]) for key in self.vertices.keys()] else: return dict() def adjacencyMatrix(self): if len(self.vertices) >= 1: self.vertex_names = sorted(g.vertices.keys()) self.vertex_indices = dict(zip(self.vertex_names, range(len(self.vertex_names)))) import numpy as np self.adjacency_matrix = np.zeros(shape=(len(self.vertices),len(self.vertices))) for i in range(len(self.vertex_names)): for j in range(i, len(self.vertices)): for el in g.vertices[self.vertex_names[i]]: j = g.vertex_indices[el] self.adjacency_matrix[i,j] = 1 return self.adjacency_matrix else: return dict() def graph(g): """ Function to print a graph as adjacency list and adjacency matrix. """ return str(g.adjacencyList()) + '\n' + '\n' + str(g.adjacencyMatrix()) ################################################################################### a = Vertex('A') b = Vertex('B') c = Vertex('C') d = Vertex('D') e = Vertex('E') a.add_neighbors([b,c,e]) b.add_neighbors([a,c]) c.add_neighbors([b,d,a,e]) d.add_neighbor(c) e.add_neighbors([a,c]) g = Graph() print(graph(g)) print("\n") g.add_vertices([a,b,c,d,e]) g.add_edge(b,d) print("\n") print(graph(g))```

### itaditya commented Jan 4, 2018

 You must be using Python 3.x whereas the author's code is for Python 2.x. Try to run mine...

### isiddharthsingh commented Dec 22, 2019

 `class Vertex: def init(self,key): self.id = key self.connectedTo = {} ``````def addNeighbor(self,nbr,weight=0): self.connectedTo[nbr] = weight def __str__(self): return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo]) def getConnections(self): return self.connectedTo.keys() def getId(self): return self.id def getWeight(self,nbr): return self.connectedTo[nbr] `````` class Graph: def init(self): self.vertList = {} self.numVertices = 0 ``````def addVertex(self,key): self.numVertices = self.numVertices + 1 newVertex = Vertex(key) self.vertList[key] = newVertex return newVertex def getVertex(self,n): if n in self.vertList: return self.vertList[n] else: return None def addEdge(self,f,t,cost=0): if f not in self.vertList: nv = self.addVertex(f) if t not in self.vertList: nv = self.addVertex(t) self.vertList[f].addNeighbor(self.vertList[t], cost) def getVertices(self): return self.vertList.keys() def __iter__(self): return iter(self.vertList.values()) def __contains__(self,n): return n in self.vertList` ``````
to join this conversation on GitHub. Already have an account? Sign in to comment