Implementing a weighted graph class where inputs are <u,v,w> Python-CodePudding

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]