Creating a City Graph with Nodes & Edges

  • Comp Sci
  • Thread starter fishturtle1
  • Start date
  • Tags
    Graph Nodes
  • #1

fishturtle1

394
81
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 line


class 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 line


class 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?
 

Answers and Replies

  • #2
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 line


class 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)))
 
  • #3
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 line


class 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 Mark44 and pbuk
  • #4
That is a great example of self help! Glad you fixed it :smile:
 
Reply
  • Like
Likes fishturtle1
  • #5
pbuk said:
That is a great example of self help! Glad you fixed it :smile:
Thanks!
 

Suggested for: Creating a City Graph with Nodes & Edges

Comp Sci Star network nodes problem
Replies
1
Views
320
Evaluate the complexity of this graph coloring algorithm
Replies
1
Views
753
Comp Sci Shortest path problem in bipartite graph
Replies
1
Views
844
Help with this mechanism (acceleration with graphic method)
Replies
3
Views
176
Engineering Spinodal and Isotherms graph on P-V diagram
Replies
8
Views
926
Comp Sci Low Pass Filter, plotting a graph
Replies
6
Views
995
Comp Sci Creating index vs adding document to index differences
Replies
1
Views
769
Algorithm for computing the depths of all the nodes of tree
Replies
1
Views
2K
Help Deciphering Voltage-vs-time Graph
Replies
7
Views
2K
Impedance graph of a transmission line powersystem in MATLAB/simulink
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top