Comp Sci Creating a City Graph with Nodes & Edges

  • Thread starter Thread starter fishturtle1
  • Start date Start date
  • Tags Tags
    Graph Nodes
AI Thread Summary
The discussion focuses on creating a city graph using nodes and edges in Python. Participants address issues related to adding nodes and edges, specifically encountering errors like NameError and ValueError due to incorrect node retrieval and graph structure. A key point of confusion was whether to create new Node instances or retrieve existing ones when adding edges. The problem was resolved by ensuring the getNode method correctly returns existing nodes and by returning the graph object from the buildCityGraph function. The final code successfully constructs and prints the city graph, demonstrating effective troubleshooting and problem-solving.
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)))
 
  • Like
Likes Mark44 and pbuk
That is a great example of self help! Glad you fixed it :smile:
 
  • Like
Likes fishturtle1
pbuk said:
That is a great example of self help! Glad you fixed it :smile:
Thanks!
 

Similar threads

Back
Top