I have created a Graph class along with a Node class that I've tested is working with basic tests however I'm not trying to test with a custom input file and I'm running into an error where some of the Nodes are being duplicated. In the graph class, there is a set called Nodes where the Node being created is added to however in my parser file, I have a checker which checks to see if the Node with the value has been added before but it's not working properly. What am I doing wrong?

Test File:

directed unweighted
Alpha=Hotel
Alpha=Beta
Beta=Charlie
Charlie=Juliett
Charlie=Juliett
Delta=Foxtrot
Delta=Golf
Echo=Charlie
Echo=Delta
Foxtrot=Golf
Golf=Juliett
Golf=Alpha
Hotel=Echo
Hotel=India
India=Beta
India=Golf
Juliett=Golf

Graph and Node Class:

class Graph:
    def __init__(self):
        self.Nodes = set()

    def addVertex(self, vertex):
        self.Nodes.add(vertex)
    
    def getVertices(self):
        return self.Nodes


    @staticmethod
    def addEdgeDirect(fromEdge, toEdge, cost=1):
        fromEdge.neighbors[toEdge] = cost


class Node():
    def __init__(self, val = None):
        self.value = val
        self.neighbors = {}

    def getEdges(self):
        return self.neighbors.keys()
    
    def __repr__(self):
        return str(self.value)

Test File Parser:

from graph import Graph, Node

graph = Graph()

file1 = open('Graphs/du.gl', 'r')
Lines = file1.readlines()

direction = Lines[0].split(" ")[0].strip()
weight = Lines[0].split(" ")[1].strip() 

count = 0
if(direction == "directed"):
    if(weight == "unweighted"):
        for line in Lines:
            count  = 1
            if(count == 1):
                continue
            node1 = Node(line.split("=")[0].strip())
            node2 = Node(line.split("=")[1].strip())
            if node1 not in graph.Nodes:
                print("not found, to be added")
                graph.addVertex(Node(node1))

            if node2 not in graph.Nodes:
                graph.addVertex(Node(node2))    

            print(graph.getVertices())
            graph.addEdgeDirect(node1,node2)
            # print("Line{}: {}".format(count, line.strip()))

CodePudding user response：

You are expecting that the set should contain nodes with unique names, but nowhere do you specify that uniqueness should depend on the property value of those nodes.

You should add the following method to your node class:

def __hash__(self):
    return hash(self.value)

CodePudding user response：

In a set objects are always distinguished by their object ID (reference). So it doesn't help to define __hash__ either.

I would suggest to:

• Use a dictionary instead of a set
• Only create Node instances when you already know that you need a new instance -- so after having checked that the Nodes dictionary doesn't have it yet
• By consequence: pass the string value to addVertex instead of a Node instance.

With some other little changes, your code could be:

class Graph:
    def __init__(self):
        self.nodes = {}

    def addVertex(self, key):
        if key not in self.nodes:
            self.nodes[key] = Node(key)
        return self.nodes[key]
    
    def getVertices(self):
        return self.nodes.values()

    @staticmethod
    def addEdgeDirect(fromEdge, toEdge, cost=1):
        fromEdge.neighbors[toEdge] = cost


class Node():
    def __init__(self, val=None):
        self.value = val
        self.neighbors = {}

    def getEdges(self):
        return self.neighbors.keys()
    
    def __repr__(self):
        return str(self.value)
    

graph = Graph()
file1 = open('du.gl', 'r')
firstline, *lines = file1.readlines()
direction, weight = firstline.split()
if direction == "directed":
    if weight == "unweighted":
        for line in lines:
            graph.addEdgeDirect(*(graph.addVertex(key.strip()) 
                                  for key in line.split("=")))
            print(graph.getVertices())

CodePudding user response：

There's a few issues, some related to a lack of type checking and some from the design of your class.

First, you have a Node class, instances of which you've kind of implied maybe should have a unique self.value, and that self.value is expected to always be a string (although these expectations are not contained in the code).

One problem causing the set() behavior, addressed in another comment, is the lack of a __hash__() method. Since it seems like you maybe want two Nodes to be equal if and only if their value parameter is the same string, adding

def __hash__(self):
    return hash(self.value)

is needed. However, for set() to work like you want, you also need to add an __eq__() function.

def __eq__(self, other):
    return isinstance(other, Node) and self.value == other.value

It's unclear to me whether the 'neighbors' attribute of a node should matter for its identity, as the terms node and graph don't carry information about what the classes actually are or represent, so maybe neighbors should be included in __eq__ too.

After adding those methods, the body of your loop is still incorrect. The problem line is graph.addVertex(Node(node1)) specifically the Node(node1). Supposedly that was intended to create a copy of node1, but it actually initializes a new node, where newnode.value is now an instance of Node, not a string. Using type hints and/or explicit type checking helps catch those problems, for example, adding a check for isinstance(value, str) to the initialization body.

Replacing those two conditionals from the loop body, the correct version would be:

if node1 not in graph.Nodes:
    graph.addVertex(node1)
if node2 not in graph.Nodes:
    graph.addVertex(node2)