Hey,

I have a function, though it's not working as it should be. My program is Dijkstra's algorithm, and I am trying to build a list of a node's nearest neighbours using info contained in a text file of the network (7 nodes in this case), in the form:

0,2,4,1,6,0,0
2,0,0,0,5,0,0
4,0,0,0,5,5,0
1,0,0,0,1,1,0
6,5,0,1,0,5,5
0,0,5,1,5,0,0
0,0,0,0,5,0,0

This is the relevant parts of my code:

infinity = 1000000
invalid_node = -1
startNode = 0

#Values to assign to each node
class Node:
     distFromSource = infinity
     previous = invalid_node
     visited = False

#read in all network nodes
#node = the distance values between nodes
def network():
    f = open ('network.txt', 'r')
    theNetwork = [[int(node) for node in line.split(',')] for line in f.readlines()]
    print theNetwork

    return theNetwork

#for each node assign default values
#populate table with default values
def populateNodeTable(): 
    nodeTable = []
    index = 0
    f = open('network.txt', 'r')
    for line in f: 
      node = map(int, line.split(',')) 
      nodeTable.append(Node())
      
      print "The previous node is " ,nodeTable[index].previous 
      print "The distance from source is " ,nodeTable[index].distFromSource 
      index +=1
    nodeTable[startNode].distFromSource = 0 

    return nodeTable

#find the nearest neighbour to a particular node
def nearestNeighbour(nodeTable, theNetwork):
     listOfNeighbours = []
     nodeIndex = 0
     for node in nodeTable:
          if node != 0 and Node.visited == False:
             nearestNode = node[theNetwork] 
             listOfNeighbours.append(nearestNode)
             nodeIndex +=1
     print listOfNeighbours

     return listOfNeighbours

currentNode = startNode

if __name__ == "__main__":
    nodeTable = populateNodeTable()
    theNetwork = network()
    nearestNeighbour(nodeTable, theNetwork)
    tentativeDistance(theNetwork, nodeTable, nodeIndex)

I am getting the error message:

nearestNode = node[theNetwork]
AttributeError: Node instance has no attribute '__getitem__'

Even before I had any error messages, I was simply getting this output from the nearestNeighbour function:

[[0, 1, 2, 3, 4, 5, 6]]

So, yeah, I am stuck on how I can correctly populate the listOfNeighbours list correctly :s

Isn't nodeTable a list of classes? So you would access it like this:

for node in nodeTable:
        #if node != 0 and Node.visited == False:
            #nearestNode = node[theNetwork]
            #listOfNeighbours.append(nearestNode)
        print node.distFromSource, node.previous. node.visited

That is if your class is constructed correctly, which it is not, so that is where you want to start (it has to be self.previous to be a member of the class which can be accessed outside the class). Try to simplify this and start with 2 nodes, which will be a 2x2 matrix and see it that is easier to understand. Also what happens if there is more than one node that is the same distance.

class TestIt():
    def __init__(self):
        self.x = 1
        y = 2            ## no 'self'

if __name__ == "__main__":
    X = TestIt()
    print X.x
    X.x = 3
    print X.x

    Y = TestIt()
    Y.z = 5             ## new 'self.z' variable declared
    print Y.z, Y.x
    print Y.y

Edited 5 Years Ago by woooee: n/a

Isn't nodeTable a list of classes? So you would access it like this:

for node in nodeTable:
        #if node != 0 and Node.visited == False:
            #nearestNode = node[theNetwork]
            #listOfNeighbours.append(nearestNode)
        print node.distFromSource, node.previous. node.visited

That is if your class is constructed correctly, which it is not, so that is where you want to start (it has to be self.previous to be a member of the class which can be accessed outside the class). Try to simplify this and start with 2 nodes, which will be a 2x2 matrix and see it that is easier to understand. Also what happens if there is more than one node that is the same distance.

class TestIt():
    def __init__(self):
        self.x = 1
        y = 2            ## no 'self'

if __name__ == "__main__":
    X = TestIt()
    print X.x
    X.x = 3
    print X.x

    Y = TestIt()
    Y.z = 5             ## new 'self.z' variable declared
    print Y.z, Y.x
    print Y.y

I have changed my class Node code to:

class Node:
     def _init_(self):
       self.distFromSource = infinity
       self.previous = invalid_node
       self.visited = False

It now gives an error in my populateNodeTable function:

print "The previous node is " ,nodeTable[index].previous
AttributeError: Node instance has no attribute 'previous'

I thought I could put the word 'self' before the '.previous' though it doesn't like that either

The variable definitions come under the __init__ function (double underscores). If there is no __init__ function, then the code was never executed.

See if this code example helps.

class Node:
    def __init__(self):
        infinity = 1000000
        invalid_node = -1
        self.distFromSource = infinity
        self.previous = invalid_node
        self.visited = False

def print_variables(class_instance):
    print class_instance.distFromSource, \
          class_instance.previous, class_instance.visited 

def print_distance(from_node, to_node, distances, instances):
    this_nodes_distances = distances[from_node]
    print "node distance list for ", from_node, this_nodes_distances
    to_node_distance = this_nodes_distances[to_node]
    print "\nthe distance from %d to %d = %d" % \
          (from_node, to_node, to_node_distance)

    instances[from_node].previous = to_node    
    print "from_node class =",
    print_variables(instances[from_node])
    print "to_node class   =",
    print_variables(instances[to_node])
    
if __name__ == "__main__":
    distances = [ [0,2,4,1,6,0,0],
                  [2,0,0,0,5,0,0],
                  [4,0,0,0,5,5,0],
                  [1,0,0,0,1,1,0],
                  [6,5,0,1,0,5,5],
                  [0,0,5,1,5,0,0],
                  [0,0,0,0,5,0,0] ]

## a list of Node class instances.
## the same number as the list 'distances'
class_instances = []
for x in range(len(distances)):
    class_instances.append(Node())

print_distance(0, 3, distances, class_instances)
print_distance(3, 0, distances, class_instances)

Edited 5 Years Ago by woooee: n/a

See if this code example helps.

class Node:
    def __init__(self):
        infinity = 1000000
        invalid_node = -1
        self.distFromSource = infinity
        self.previous = invalid_node
        self.visited = False

def print_variables(class_instance):
    print class_instance.distFromSource, \
          class_instance.previous, class_instance.visited 

def print_distance(from_node, to_node, distances, instances):
    this_nodes_distances = distances[from_node]
    print "node distance list for ", from_node, this_nodes_distances
    to_node_distance = this_nodes_distances[to_node]
    print "\nthe distance from %d to %d = %d" % \
          (from_node, to_node, to_node_distance)

    instances[from_node].previous = to_node    
    print "from_node class =",
    print_variables(instances[from_node])
    print "to_node class   =",
    print_variables(instances[to_node])
    
if __name__ == "__main__":
    distances = [ [0,2,4,1,6,0,0],
                  [2,0,0,0,5,0,0],
                  [4,0,0,0,5,5,0],
                  [1,0,0,0,1,1,0],
                  [6,5,0,1,0,5,5],
                  [0,0,5,1,5,0,0],
                  [0,0,0,0,5,0,0] ]

## a list of Node class instances.
## the same number as the list 'distances'
class_instances = []
for x in range(len(distances)):
    class_instances.append(Node())

print_distance(0, 3, distances, class_instances)
print_distance(3, 0, distances, class_instances)

Thanks, the structure is different to what I have been tasked with, so I need to keep my structure as is. Here is my code, I don't quite know how your last question relates to my code, for example, do I have to write 'self' in all of my functions?

infinity = 1000000
invalid_node = -1
startNode = 0

#Values to assign to each node
class Node:
     def _init_(self):
       self.distFromSource = infinity
       self.previous = invalid_node
       self.visited = False

#read in all network nodes
#node = the distance values between nodes
def network():
    f = open ('network.txt', 'r')
    theNetwork = [[int(node) for node in line.split(',')] for line in f.readlines()]
    print theNetwork

    return theNetwork

#for each node assign default values
#populate table with default values
def populateNodeTable(self): 
    nodeTable = []
    index = 0
    f = open('network.txt', 'r')
    for line in f: 
      node = map(int, line.split(',')) 
      nodeTable.append(Node())
      
      print "The previous node is " ,nodeTable[index].previous 
      print "The distance from source is " ,nodeTable[index].distFromSource 
      index +=1
    nodeTable[startNode].distFromSource = 0 

    return nodeTable

#find the nearest neighbour to a particular node
def nearestNeighbour(nodeTable, theNetwork):
     listOfNeighbours = []
     nodeIndex = 0
     for node in nodeTable:
##          if node != 0 and Node.visited == False:
##             nearestNode = node[theNetwork] 
##             listOfNeighbours.append(nearestNode)
##             nodeIndex +=1
       print node.distFromSource, node.previous, node.visited

     return listOfNeighbours

##def tentativeDistance (theNetwork, nodeTable, nodeIndex ):
##    shortestPath = []
##    for nodeIndex in listOfNeighbours:
##         currentDistance = listOfNeighbours[node] + startNode
##         print currentDistance
##         if currentDistance < Node.distFromSource:
##            theNetwork[Node].previous = nodeIndex
##            theNetwork[Node].length = nodeIndex
##            theNetwork[Node].visited = True;
##            shortestPath.append(indexNode)
##            nodeIndex +=1
##    print shortestPath
##        
        
#def shortestPath(tentativeDistance)
#     shortestPath = []
#     f = open ('shortestPath.txt', 'w')
#     f.write(shortestPath) 


#     f.close()

currentNode = startNode

if __name__ == "__main__":
     self = populateNodeTable(self)
    #nodeTable = populateNodeTable(self)
     theNetwork = network()
     nearestNeighbour(nodeTable, theNetwork)
    #tentativeDistance(theNetwork, nodeTable, nodeIndex)

on line 7,
your

def _init_(self)

must be this ->

def __init__(self)

a double underscore!
:)

Ah yes! Tiredness, setting in!

I am now back to my original error even though i've put 'def __init__(self)' in:

if node != 0 and Node.visited == False:
AttributeError: class Node has no attribute 'visited'

I am now back to my original error even though i've put 'def __init__(self)' in:

if node != 0 and Node.visited == False:
AttributeError: class Node has no attribute 'visited'

You are mistaking your variable node for the class Node. The class Node actually does not have an attribute 'visited'. Only node instances created with x = Node() have this attribute.
I also think that after creation, you should print theNetwork and nodeTable to check that they contain what you are expecting. Your creation functions look strange.

Edited 5 Years Ago by Gribouillis: n/a

You are mistaking your variable node for the class Node. The class Node actually does not have an attribute 'visited'. Only node instances created with x = Node() have this attribute.
I also think that after creation, you should print theNetwork and nodeTable to check that they contain what you are expecting. Your creation functions look strange.

The output of my network function works ok:

[[0, 2, 4, 1, 6, 0, 0], [2, 0, 0, 0, 5, 0, 0], [4, 0, 0, 0, 5, 5, 0], [1, 0, 0, 0, 1, 1, 0], [6, 5, 0, 1, 0, 5, 5], [0, 0, 5, 1, 5, 0, 0], [0, 0, 0, 0, 5, 0, 0]]

This is fine as my network text file contents are:

0,2,4,1,6,0,0
2,0,0,0,5,0,0
4,0,0,0,5,5,0
1,0,0,0,1,1,0
6,5,0,1,0,5,5
0,0,5,1,5,0,0
0,0,0,0,5,0,0

The output of my populateNodeTable function is almost ok:

The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000

I have changed my nearestNeighbour code to:

def nearestNeighbour(currentNode, theNetwork):
     listOfNeighbours = []
     nodeIndex = 0
     for networkNode in nodeTable[currentNode]:
          if networkNode != 0 and networkNode.visited == False: 
             listOfNeighbours.append(nearestNode)
          nodeIndex +=1
     print listOfNeighbours
##     #print node.distFromSource, node.previous, node.visited
##
     return listOfNeighbours

Now I get this error:

for networkNode in nodeTable[currentNode]:
TypeError: iteration over non-sequence

The output of my network function works ok:

[[0, 2, 4, 1, 6, 0, 0], [2, 0, 0, 0, 5, 0, 0], [4, 0, 0, 0, 5, 5, 0], [1, 0, 0, 0, 1, 1, 0], [6, 5, 0, 1, 0, 5, 5], [0, 0, 5, 1, 5, 0, 0], [0, 0, 0, 0, 5, 0, 0]]

This is fine as my network text file contents are:

0,2,4,1,6,0,0
2,0,0,0,5,0,0
4,0,0,0,5,5,0
1,0,0,0,1,1,0
6,5,0,1,0,5,5
0,0,5,1,5,0,0
0,0,0,0,5,0,0

The output of my populateNodeTable function is almost ok:

The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000

I have changed my nearestNeighbour code to:

def nearestNeighbour(currentNode, theNetwork):
     listOfNeighbours = []
     nodeIndex = 0
     for networkNode in nodeTable[currentNode]:
          if networkNode != 0 and networkNode.visited == False: 
             listOfNeighbours.append(nearestNode)
          nodeIndex +=1
     print listOfNeighbours
##     #print node.distFromSource, node.previous, node.visited
##
     return listOfNeighbours

Now I get this error:

for networkNode in nodeTable[currentNode]:
TypeError: iteration over non-sequence

In populateTable(), I don't understand these lines

node = map(int, line.split(',')) 
      nodeTable.append(Node())

You first define a variable 'node' which you don't use later, then you append a new Node object to the table, which is unrelated to the node variable, or the network.
About your error message, nodeTable[currentNode] is not a list but a Node object, you can't use it in a for statement like this.

Edited 5 Years Ago by Gribouillis: n/a

In populateTable(), I don't understand these lines

node = map(int, line.split(',')) 
      nodeTable.append(Node())

You first define a variable 'node' which you don't use later, then you append a new Node object to the table, which is unrelated to the node variable, or the network.
About your error message, nodeTable[currentNode] is not a list but a Node object, you can't use it in a for statement like this.

Thanks for replying. I have a text file, representing the distance between nodes in a network, in this form:

0,2,4,1,6,0,0
2,0,0,0,5,0,0
4,0,0,0,5,5,0
1,0,0,0,1,1,0
6,5,0,1,0,5,5
0,0,5,1,5,0,0
0,0,0,0,5,0,0

So, there are seven nodes in the network, and the split is done so that they can be added to the list so that they can be manipulated.
The second line you mention, I put that in to assign all of the nodes in the network the values in my class Node, as per Dijkstra's algorithm.

Having made some tweaks to my nearestNeighbour function however, I am now getting output. Here is my updated code, with all of the output:

infinity = 1000000
invalid_node = -1
startNode = 0

#Values to assign to each node
class Node:
     def __init__(self):
       self.distFromSource = infinity
       self.previous = invalid_node
       self.visited = False

#read in all network nodes
#node = the distance values between nodes
def network():
    f = open ('network.txt', 'r')
    theNetwork = [[int(networkNode) for networkNode in line.split(',')] for line in f.readlines()]
    #theNetwork = [[int(node) for node in line.split(',')] for line in f.readlines()]
    #print theNetwork

    return theNetwork

#for each node assign default values
#populate table with default values
def populateNodeTable(): 
    nodeTable = []
    index = 0
    f = open('network.txt', 'r')
    for line in f: 
      networkNode = map(int, line.split(',')) 
      nodeTable.append(Node())
      
      #print "The previous node is " ,nodeTable[index].previous 
      #print "The distance from source is " ,nodeTable[index].distFromSource
      #print networkNode
      index +=1
    nodeTable[startNode].distFromSource = 0 

    return nodeTable

currentNode = startNode

#find the nearest neighbour to a particular node
def nearestNeighbour(currentNode, theNetwork):
     listOfNeighbours = []
     nodeIndex = 0
     for networkNode in theNetwork[currentNode]:
          if networkNode != 0 and nodeTable[networkNode].visited == False: 
             listOfNeighbours.append(networkNode)
          nodeIndex +=1
     print listOfNeighbours
##     #print node.distFromSource, node.previous, node.visited
##
     return listOfNeighbours

def tentativeDistance (theNetwork, listOfNeighbours):
    shortestPath = []
    for nodeIndex in listOfNeighbours:
         currentDistance = listOfNeighbours[currentNode] + startNode
         print currentDistance
         if currentDistance < Node.distFromSource:
            theNetwork[node].previous = nodeIndex
            theNetwork[node].length = nodeIndex
            theNetwork[node].visited = True;
            shortestPath.append(indexNode)
            nodeIndex +=1
    print shortestPath
        
        
#def shortestPath(tentativeDistance)
#     shortestPath = []
#     f = open ('shortestPath.txt', 'w')
#     f.write(shortestPath) 


#     f.close()

#currentNode = startNode

if __name__ == "__main__":
     nodeTable = populateNodeTable()
    #nodeTable = populateNodeTable(self)
     theNetwork = network()
     nearestNeighbour(currentNode, theNetwork)
     tentativeDistance(theNetwork, nodeTable)

The output:

The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
[[0, 2, 4, 1, 6, 0, 0], [2, 0, 0, 0, 5, 0, 0], [4, 0, 0, 0, 5, 5, 0], [1, 0, 0, 0, 1, 1, 0], [6, 5, 0, 1, 0, 5, 5], [0, 0, 5, 1, 5, 0, 0], [0, 0, 0, 0, 5, 0, 0]]
[2, 4, 1, 6]

So, I am getting the inital values for each node, followed by a 2D list of my network, then [2, 4, 1, 6] is the output of my nearestNeighbour function.
To be honest though, i'm not sure that the nearestNeighbour function output is working as it should be

Thanks for replying. I have a text file, representing the distance between nodes in a network, in this form:

0,2,4,1,6,0,0
2,0,0,0,5,0,0
4,0,0,0,5,5,0
1,0,0,0,1,1,0
6,5,0,1,0,5,5
0,0,5,1,5,0,0
0,0,0,0,5,0,0

So, there are seven nodes in the network, and the split is done so that they can be added to the list so that they can be manipulated.
The second line you mention, I put that in to assign all of the nodes in the network the values in my class Node, as per Dijkstra's algorithm.

Having made some tweaks to my nearestNeighbour function however, I am now getting output. Here is my updated code, with all of the output:

infinity = 1000000
invalid_node = -1
startNode = 0

#Values to assign to each node
class Node:
     def __init__(self):
       self.distFromSource = infinity
       self.previous = invalid_node
       self.visited = False

#read in all network nodes
#node = the distance values between nodes
def network():
    f = open ('network.txt', 'r')
    theNetwork = [[int(networkNode) for networkNode in line.split(',')] for line in f.readlines()]
    #theNetwork = [[int(node) for node in line.split(',')] for line in f.readlines()]
    #print theNetwork

    return theNetwork

#for each node assign default values
#populate table with default values
def populateNodeTable(): 
    nodeTable = []
    index = 0
    f = open('network.txt', 'r')
    for line in f: 
      networkNode = map(int, line.split(',')) 
      nodeTable.append(Node())
      
      #print "The previous node is " ,nodeTable[index].previous 
      #print "The distance from source is " ,nodeTable[index].distFromSource
      #print networkNode
      index +=1
    nodeTable[startNode].distFromSource = 0 

    return nodeTable

currentNode = startNode

#find the nearest neighbour to a particular node
def nearestNeighbour(currentNode, theNetwork):
     listOfNeighbours = []
     nodeIndex = 0
     for networkNode in theNetwork[currentNode]:
          if networkNode != 0 and nodeTable[networkNode].visited == False: 
             listOfNeighbours.append(networkNode)
          nodeIndex +=1
     print listOfNeighbours
##     #print node.distFromSource, node.previous, node.visited
##
     return listOfNeighbours

def tentativeDistance (theNetwork, listOfNeighbours):
    shortestPath = []
    for nodeIndex in listOfNeighbours:
         currentDistance = listOfNeighbours[currentNode] + startNode
         print currentDistance
         if currentDistance < Node.distFromSource:
            theNetwork[node].previous = nodeIndex
            theNetwork[node].length = nodeIndex
            theNetwork[node].visited = True;
            shortestPath.append(indexNode)
            nodeIndex +=1
    print shortestPath
        
        
#def shortestPath(tentativeDistance)
#     shortestPath = []
#     f = open ('shortestPath.txt', 'w')
#     f.write(shortestPath) 


#     f.close()

#currentNode = startNode

if __name__ == "__main__":
     nodeTable = populateNodeTable()
    #nodeTable = populateNodeTable(self)
     theNetwork = network()
     nearestNeighbour(currentNode, theNetwork)
     tentativeDistance(theNetwork, nodeTable)

The output:

The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
The previous node is  -1
The distance from source is  1000000
[[0, 2, 4, 1, 6, 0, 0], [2, 0, 0, 0, 5, 0, 0], [4, 0, 0, 0, 5, 5, 0], [1, 0, 0, 0, 1, 1, 0], [6, 5, 0, 1, 0, 5, 5], [0, 0, 5, 1, 5, 0, 0], [0, 0, 0, 0, 5, 0, 0]]
[2, 4, 1, 6]

So, I am getting the inital values for each node, followed by a 2D list of my network, then [2, 4, 1, 6] is the output of my nearestNeighbour function.
To be honest though, i'm not sure that the nearestNeighbour function output is working as it should be

What I don't understand in your program is

  1. Why do you need to open the file twice (in network() and populateTable)?
  2. In populateTable(), the variable near the split, which is now called networkNode, is never used in the code that follows. Then why do you need it ?

Edited 5 Years Ago by Gribouillis: n/a

1. I felt that was the only way I knew of doing what I wanted to do
2. I am getting confused with the variable passing, i've changed variables so much that I don't know what is right and wrong, once that has been worked out then I think I can finish the rest of the program off easily

1. I felt that was the only way I knew of doing what I wanted to do
2. I am getting confused with the variable passing, i've changed variables so much that I don't know what is right and wrong, once that has been worked out then I think I can finish the rest of the program off easily

The rule is very simple, a variable defined in a function (by a statement variable = ... ) does not exist outside the function. You don't need to change variable names, it is not important.

Edited 5 Years Ago by Gribouillis: n/a

The rule is very simple, a variable defined in a function (by a statement variable = ... ) does not exist outside the function. You don't need to change variable names, it is not important.

Ok, I understand. Am I passing the parameters ok? I'm getting output which is good, just doubtful that i'm doing it correctly

This article has been dead for over six months. Start a new discussion instead.