CODEWITHSUNDEEP
pythondata-structures
t-h-
t-h-

Reputation: 97

Python graph structure and surprising list handling

I'm implementing a graph structure (just for practicing purposes) and now I came to two behaviors I cannot explain to myself.

first, here the code

class Node:
    data = None
    def __init__(self, data):
        self.data = data
    def __str__(self):
        return str(self.data)
    def __repr__(self):
        return self.__str__()

class GraphNode(Node):
    children = []
    def __init__(self, list_of_nodes=None, data=None):
        if list_of_nodes != None:
            for node in list_of_nodes:
                children.add(node)
        self.data = data

def createGraphStructure():
    node1 = GraphNode(data=1)
    node2 = GraphNode(data=2)
    node3 = GraphNode(data=3)
    node4 = GraphNode(data=4)
    node5 = GraphNode(data=5)
    node6 = GraphNode(data=6)
    node7 = GraphNode(data=7)
    node8 = GraphNode(data=8)

    node1.children.append([node2, node3, node4])
    node2.children.append([node5, node6, node7])
    node4.children.append([node8])

    #just a random test/visualization
    print node1.children
    #another random printout to test/visualize
    for n in node1.children:
        print n.data

    return node1

if __name__ == "__main__":
    root = createGraphStructure()
    #do stuff with graph, bfs dfs whatever

Now first surprising thing: print node1.children in createGraphStructure() will print out the following: [[2, 3, 4], [5, 6, 7], [8]], but i expected it only to print out the immediate children of node 1, like [2, 3, 4]. I am completely clueless here.

Secondly, the part 

for n in node1.children:
    print n.data

throws following exception:

File "C:/yeah/you/would/like/to/see/my/path/right?/datastructures.py", line 54, in createGraphStructure
    print n.data
AttributeError: 'list' object has no attribute 'data'

As it seems, n is a list, but why? Shouldnt it be a node from the list? Im sure there are some obvious explanations for that but I cant figure them out. Also because im not too proficient with Python, especially not OO.

Thx!

Upvotes: 3

Views: 92

Answers (1)

SpoonMeiser
SpoonMeiser

Reputation: 20417

Firstly, when you do this:

class GraphNode(Node):
    children = []

children here is class data, not instance data. That is, all of your nodes are sharing the same children object, so each of the append calls is actually changing the same variable.

To have instance data, you need to create children in a method so that it can access a reference to an instance. Typically, this is done in __init__:

class GraphNode(Node):
    def __init__(self, list_of_nodes=None, data=None):
        self.children = []  # <-- initialised here
        if list_of_nodes != None:
            for node in list_of_nodes:
                children.add(node)
        self.data = data

The second problem, is that you've used append where it appears that you meant to use extend.

append takes an object, and adds this object to a list:

>>> l = [1, 2, 3]
>>> l.append([4, 5, 6])
>>> l
[1, 2, 3, [4, 5, 6]]

See here, the fourth item in the list is another list. Instead, use extend, which takes a list, and concatenates it with the list it is called on:

>>> l = [1, 2, 3]
>>> l.extend([4, 5, 6])
>>> l
[1, 2, 3, 4, 5, 6]

Upvotes: 2

Related Questions