Creating a City Graph with Nodes & Edges

  • Context: Comp Sci 
  • Thread starter Thread starter fishturtle1
  • Start date Start date
  • Tags Tags
    Graph Nodes
Click For Summary

Discussion Overview

The discussion revolves around creating a city graph using nodes and edges in Python. Participants are addressing issues related to the implementation of graph data structures, specifically focusing on the functionality of adding nodes and edges, and the behavior of methods within the classes defined for the graph.

Discussion Character

  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant encounters a NameError when trying to access a node by name, questioning the use of g.addEdge(Edge(g.getNode('Boston'), g.getNode('Providence'))) versus g.addEdge(Edge(Node('Boston'), Node('Providence'))).
  • Another participant suggests that the for loop in the buildCityGraph function is not functioning as expected, leading to a ValueError indicating that at least one node is not in the graph.
  • A participant mentions fixing the getNode method but then faces an issue where the code returns None when executed.
  • There are multiple instances of participants refining their code, such as adjusting the logic in the getNode method and the structure of the addEdge method.
  • Debugging statements are introduced to track the flow of execution and the state of the edges dictionary.

Areas of Agreement / Disagreement

Participants are actively discussing and refining their code, but there is no consensus on the specific issues being faced, as different participants are encountering different errors and proposing various solutions.

Contextual Notes

Limitations include unresolved issues with method functionality, such as the getNode method not returning the expected node and the implications of using different instances of Node in edge creation. The discussion reflects ongoing attempts to debug and clarify the intended functionality of the graph implementation.

fishturtle1
Messages
393
Reaction score
82
Homework Statement
This is code from a lecture but it won't work for me. My question is about the buildCityGraph function. It seems like the for loop doesn't work and I don't know why. Also i'm confused why we are adding edges the way we do. Why?
Relevant Equations
.
Edit: Trying to fix the formatting...

Python: 
class Node(object):
    def __init__(self, name):
        self.name = str(name)

    def get_name(self):
        return self.name

    def __str__(self):
        return self.name

class Edge(object):
    def __init__(self, src, dest):
        self.src = src
        self.dest = dest

    def getSource(self):
        return self.src

    def getDestination(self):
        return self.dest

    def __str__(self):
        return self.src.get_name() + "->" + self.dest.get_name()class Digraph(object):
    def __init__(self):
        self.edges = {}

    def addNode(self, node):
        if node in self.edges:
            raise ValueError("Duplicate node found.")
        else:
            self.edges[node] = []

    def addEdge(self, edge):
        src = edge.getSource()
        dest = edge.getDestination()
        if not (src in self.edges and dest in self.edges):
            raise ValueError("At least one node not in graph.")
        else:
            self.edges[src].append(dest)

    def childrenOf(self, node):
        return self.edges[node]

    def hasNode(self, node):
        return node in self.edges

    def getNode(self, name):
        for n in self.edges:
            if n.get_name == name:
                return n
            else:
                raise NameError(name)

    def __str__(self):
        result = ''
        for src in self.edges:
            for dest in self.edges[src]:
                result += src.get_name() + "->" + dest.get_name() + "\n"
        return result[:-1] #omit final new lineclass Graph(Digraph):
    def addEdge(self, edge):
        Digraph.addEdge(self, edge)
        rev = Edge(edge.getDestination(), edge.getSource())
        Digraph.addEdge(self, rev)

def buildCityGraph(graphType):
    g = graphType()
    for name in ('Boston', 'Providence', 'New York', 'Chicago',
             'Denver', 'Phoenix', 'Los Angeles'): #Create 7 nodes
        g.addNode(Node(name))
    g.addEdge(Edge(g.getNode('Boston'), g.getNode('Providence')))
    g.addEdge(Edge(g.getNode('Boston'), g.getNode('New York')))
    g.addEdge(Edge(g.getNode('Providence'), g.getNode('Boston')))
    g.addEdge(Edge(g.getNode('Providence'), g.getNode('New York')))
    g.addEdge(Edge(g.getNode('New York'), g.getNode('Chicago')))
    g.addEdge(Edge(g.getNode('Chicago'), g.getNode('Denver')))
    g.addEdge(Edge(g.getNode('Chicago'), g.getNode('Phoenix')))
    g.addEdge(Edge(g.getNode('Denver'), g.getNode('Phoenix')))
    g.addEdge(Edge(g.getNode('Denver'), g.getNode('New York')))
    g.addEdge(Edge(g.getNode('Los Angeles'), g.getNode('Boston')))

print(str(buildCityGraph(Digraph)))

When i run this i get the error: NameError: 'Boston'. Why do we use g.addEdge(Edge(g.getNode('Boston'), g.getNode('Providence')))? It seems like g.addEdge(Edge(Node('Boston'), Node('Providence'))) is what we want? When I try this

Python: 
class Node(object):
    def __init__(self, name):
        self.name = str(name)

    def get_name(self):
        return self.name

    def __str__(self):
        return self.name

class Edge(object):
    def __init__(self, src, dest):
        self.src = src
        self.dest = dest

    def getSource(self):
        return self.src

    def getDestination(self):
        return self.dest

    def __str__(self):
        return self.src.get_name() + "->" + self.dest.get_name()class Digraph(object):
    def __init__(self):
        self.edges = {}

    def addNode(self, node):
        if node in self.edges:
            raise ValueError("Duplicate node found.")
        else:
            self.edges[node] = []

    def addEdge(self, edge):
        src = edge.getSource()
        dest = edge.getDestination()
        if not (src in self.edges and dest in self.edges):
            raise ValueError("At least one node not in graph.")
        else:
            self.edges[src].append(dest)

    def childrenOf(self, node):
        return self.edges[node]

    def hasNode(self, node):
        return node in self.edges

    def getNode(self, name):
        for n in self.edges:
            if n.get_name == name:
                return n
            else:
                raise NameError(name)

    def __str__(self):
        result = ''
        for src in self.edges:
            for dest in self.edges[src]:
                result += src.get_name() + "->" + dest.get_name() + "\n"
        return result[:-1] #omit final new lineclass Graph(Digraph):
    def addEdge(self, edge):
        Digraph.addEdge(self, edge)
        rev = Edge(edge.getDestination(), edge.getSource())
        Digraph.addEdge(self, rev)

def buildCityGraph(graphType):
    g = graphType()
    for name in ('Boston', 'Providence', 'New York', 'Chicago',
             'Denver', 'Phoenix', 'Los Angeles'): #Create 7 nodes
        g.addNode(Node(name))
    g.addEdge(Edge(Node('Boston'), Node('Providence')))
    # g.addEdge(Edge(g.getNode('Boston'), g.getNode('New York')))
    # g.addEdge(Edge(g.getNode('Providence'), g.getNode('Boston')))
    # g.addEdge(Edge(g.getNode('Providence'), g.getNode('New York')))
    # g.addEdge(Edge(g.getNode('New York'), g.getNode('Chicago')))
    # g.addEdge(Edge(g.getNode('Chicago'), g.getNode('Denver')))
    # g.addEdge(Edge(g.getNode('Chicago'), g.getNode('Phoenix')))
    # g.addEdge(Edge(g.getNode('Denver'), g.getNode('Phoenix')))
    # g.addEdge(Edge(g.getNode('Denver'), g.getNode('New York')))
    # g.addEdge(Edge(g.getNode('Los Angeles'), g.getNode('Boston')))

print(str(buildCityGraph(Digraph)))

I get the error: ValueError: At least one node not in graph. Why is the for loop in buildCityGraph function not working?
 
Physics news on Phys.org
I fixed the getNode method but now it when i run, the code returns None.

Python: 
class Node(object):
    def __init__(self, name):
        self.name = str(name)

    def get_name(self):
        return self.name

    def __str__(self):
        return self.name

class Edge(object):
    def __init__(self, src, dest):
        self.src = src
        self.dest = dest

    def getSource(self):
        return self.src

    def getDestination(self):
        return self.dest

    def __str__(self):
        return self.src.get_name() + "->" + self.dest.get_name()class Digraph(object):
    def __init__(self):
        self.edges = {} 

    def addNode(self, node):
        if node in self.edges:
            raise ValueError("Duplicate node found.")
        else:
            self.edges[node] = []

    def addEdge(self, edge):
        src = edge.getSource()
        dest = edge.getDestination()
        if not (src in self.edges and dest in self.edges):
            raise ValueError("At least one node not in graph.")
        self.edges[src].append(dest)

    def childrenOf(self, node):
        return self.edges[node]

    def hasNode(self, node):
        return node in self.edges

    def getNode(self, name):
        for n in self.edges:
            if n.get_name() == name:
                return n
        raise NameError(name)

    def __str__(self):
        result = ''
        print(self.edges)
        for src in self.edges:
            print('hi')
            for dest in self.edges[src]:
                print('here')
                result += src.get_name() + "->" + dest.get_name() + "\n"
        return result #omit final new lineclass Graph(Digraph):
    def addEdge(self, edge):
        Digraph.addEdge(self, edge)
        rev = Edge(edge.getDestination(), edge.getSource())
        Digraph.addEdge(self, rev)

def buildCityGraph(graphType): 
    g = graphType()
    for name in ('Boston', 'Providence', 'New York', 'Chicago',
             'Denver', 'Phoenix', 'Los Angeles'): #Create 7 nodes
        g.addNode(Node(name))
    

    g.addEdge(Edge(g.getNode('Boston'), g.getNode('Providence')))
    g.addEdge(Edge(g.getNode('Boston'), g.getNode('New York')))
    g.addEdge(Edge(g.getNode('Providence'), g.getNode('Boston')))
    g.addEdge(Edge(g.getNode('Providence'), g.getNode('New York')))
    g.addEdge(Edge(g.getNode('New York'), g.getNode('Chicago')))
    g.addEdge(Edge(g.getNode('Chicago'), g.getNode('Denver')))
    g.addEdge(Edge(g.getNode('Chicago'), g.getNode('Phoenix')))
    g.addEdge(Edge(g.getNode('Denver'), g.getNode('Phoenix')))
    g.addEdge(Edge(g.getNode('Denver'), g.getNode('New York')))
    g.addEdge(Edge(g.getNode('Los Angeles'), g.getNode('Boston')))

print(str(buildCityGraph(Digraph)))
 
Now it works, I forgot to return g in the buildCityGraph.

Python: 
class Node(object):
    def __init__(self, name):
        self.name = str(name)

    def get_name(self):
        return self.name

    def __str__(self):
        return self.name

class Edge(object):
    def __init__(self, src, dest):
        self.src = src
        self.dest = dest

    def getSource(self):
        return self.src

    def getDestination(self):
        return self.dest

    def __str__(self):
        return self.src.get_name() + "->" + self.dest.get_name()class Digraph(object):
    def __init__(self):
        self.edges = {} 

    def addNode(self, node):
        if node in self.edges:
            raise ValueError("Duplicate node found.")
        else:
            self.edges[node] = []

    def addEdge(self, edge):
        src = edge.getSource()
        dest = edge.getDestination()
        if not (src in self.edges and dest in self.edges):
            raise ValueError("At least one node not in graph.")
        self.edges[src].append(dest)

    def childrenOf(self, node):
        return self.edges[node]

    def hasNode(self, node):
        return node in self.edges

    def getNode(self, name):
        for n in self.edges:
            if n.get_name() == name:
                return n
        raise NameError(name)

    def __str__(self):
        result = ''
        print(self.edges)
        for src in self.edges:
            for dest in self.edges[src]:
                result += src.get_name() + "->" + dest.get_name() + "\n"
        return result #omit final new lineclass Graph(Digraph):
    def addEdge(self, edge):
        Digraph.addEdge(self, edge)
        rev = Edge(edge.getDestination(), edge.getSource())
        Digraph.addEdge(self, rev)

def buildCityGraph(graphType): 
    g = graphType()
    for name in ('Boston', 'Providence', 'New York', 'Chicago',
             'Denver', 'Phoenix', 'Los Angeles'): #Create 7 nodes
        g.addNode(Node(name))
    

    g.addEdge(Edge(g.getNode('Boston'), g.getNode('Providence')))
    g.addEdge(Edge(g.getNode('Boston'), g.getNode('New York')))
    g.addEdge(Edge(g.getNode('Providence'), g.getNode('Boston')))
    g.addEdge(Edge(g.getNode('Providence'), g.getNode('New York')))
    g.addEdge(Edge(g.getNode('New York'), g.getNode('Chicago')))
    g.addEdge(Edge(g.getNode('Chicago'), g.getNode('Denver')))
    g.addEdge(Edge(g.getNode('Chicago'), g.getNode('Phoenix')))
    g.addEdge(Edge(g.getNode('Denver'), g.getNode('Phoenix')))
    g.addEdge(Edge(g.getNode('Denver'), g.getNode('New York')))
    g.addEdge(Edge(g.getNode('Los Angeles'), g.getNode('Boston')))

    return g

print(str(buildCityGraph(Digraph)))
 
Reply
  • Like
Likes   Reactions: Mark44 and pbuk
That is a great example of self help! Glad you fixed it :smile:
 
Reply
  • Like
Likes   Reactions: fishturtle1
pbuk said:
That is a great example of self help! Glad you fixed it :smile:
Thanks!
 

Similar threads

Python Create a binary search tree in python with the support of variables
  • · Replies 13 ·
Replies
13
Views
4K