I have been able to implement a graph class where each individual vertex are given first and the edges are added later. But this is a waste of memory. Example of input:
total_vertices = 7
my_graph = Graph(total_vertices)
edges = []
edges.append((3,1,5))
edges.append((1,2,1))
my_graph.add_edges(edges)
Here is my code
class Graph:
def __init__(self, N):
self.vertices = [None] * N
for i in range(N):
self.vertices[i] = Vertex(i)
def add_edges(self, edges_list):
for edge in edges_list:
u = edge[0]
v = edge[1]
w = edge[2]
current_edge = Edge(u,v,w)
current_vertex = self.vertices[u]
current_vertex.add_edge_to_vertex(current_edge)
class Vertex:
def __init__(self, vertex):
self.vertex = vertex
self.vertex_edges = []
def add_edge_to_vertex(self, edge):
self.vertex_edges.append(edge)
class Edge:
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
So I want to be implementing a graph class in python in which the input is in the form <u,v,w>
where u
is the parent vertex, v
is the child vertex, and w
is the weight straight away without having to indicate the number of vertices first. Input looks like this:
edgelist = [(0,2,4),(0,1,2),(0,3,3),(2,3,2), (3,0,3)]
graph = Graph(edgelist)
print(graph)
Any help/suggestions are most welcome
CodePudding user response:
You probably could use dictionaries for storing vertices and edges:
import collections
class Graph:
def __init__(self, edge_list):
self.edges = collections.defaultdict(dict)
for u, v, w in edge_list:
self.edges[u][v] = w
def get_weight(self, u, v):
return self.edges[u][v]
def __repr__(self):
return f'{self.__class__.__qualname__}({dict(self.edges)})'
def __str__(self):
return str(dict(self.edges))
Usage:
# Create an instance of a graph
edgelist = [(0, 2, 4), (0, 1, 2), (0, 3, 3), (2, 3, 2), (3, 0, 3)]
graph = Graph(edgelist)
print(graph)
# Get the weight between u and v
u, v = 0, 1
print(graph.get_weight(u, v))
CodePudding user response:
Just two properties: self._nodes
and self._edges
which will be modified each time you add a node or an edge. I just remove Vertex
class but you can actually keep it (no need in your code), also the Edge
class that I eventually didn't remove.
I modified edge tuple to differentiate nodes from weight...
class Graph:
def __init__(self):
self._nodes = []
self._edges = []
def add_node(self, v):
self._nodes.append(v)
def add_edge(self, ab, w):
a, b = ab
if a not in self._nodes:
self._nodes.append(a)
if b not in self._nodes:
self._nodes.append(b)
my_new_edge = Edge(ab, w)
self._edges.append(my_new_edge)
def add_edges(self, e_list):
for ab, w in e_list:
self.add_edge(ab, w)
def __str__(self):
return f"{self._nodes}\n{self._edges}"
class Edge:
def __init__(self, ab, w):
a, b = ab
self._from = a
self._to = b
self._weight = w
def __repr__(self):
return f"from {self._from} to {self._to} weighted {self._weight}"
edgelist = [((0, 2), 4),
((0, 1), 2),
((0, 3), 3),
((2, 3), 2),
((3, 0), 3)]
g = Graph()
g.add_edges(edgelist)
print(g)
# [0, 2, 1, 3]
# [from 0 to 2 weighted 4, from 0 to 1 weighted 2, from 0 to 3 weighted 3, from 2 to 3 weighted 2, from 3 to 0 weighted 3]