List of objects affecting other object's list

Question

I'm trying to build a graph where a vertex has a string identifier and is connected to another vertex if the string identifiers of the 2 vertices differ by only a single character. For example, 'dog' and 'dot' can be connected by an edge. I'm maintaining the graph with an adjacency list. However, after I have validated that 2 vertices can be connected, I'm appending the to_vertex object to the list of the from_vertex object and vice versa. But this is causing the lists to contain duplicate objects. Following is the code(it is quite dense):

class vertex():
    def __init__(self, distance = -1, edges = [], name = ''):
        self.name = name
        self.distance = distance
        self.edges = edges

def create_graph(word_dict):
    graph = []

    num_words = len(word_dict)

    v = [vertex(name = word_dict[x]) for x in range(num_words)]

    for i in range(num_words):
        for j in range(i + 1, num_words):
            count = 0
            if len(word_dict[i]) == len(word_dict[j]):
                print word_dict[i], word_dict[j]
                k = 0
                is_valid = True
                while k < len(word_dict[i]):
                    print word_dict[i][k], word_dict[j][k]
                    if word_dict[i][k] != word_dict[j][k]:
                        if count == 1:
                            is_valid = False
                            break
                        else:
                            count += 1
                            k += 1
                    else:
                        k += 1

                if is_valid == True:
                    v[i].edges.append(v[j])
                    v[j].edges.append(v[i])

    graph = [v[i] for i in range(num_words)]

    return graph

if __name__ == '__main__':
    graph = create_graph(['bat', 'cot', 'dog', 'dag', 'dot', 'cat'])

    for v in graph:
        print 'Vertex name ' + v.name 
        for edge in v.edges:
            print edge.name
        print '-----------------------------'

Following is the output of the for loop in the main:

Vertex name bat
cat
bat
dot
cot
cat
cot
dag
dog
dot
dog
-----------------------------
Vertex name cot
cat
bat
dot
cot
cat
cot
dag
dog
dot
dog
-----------------------------
Vertex name dog
cat
bat
dot
cot
cat
cot
dag
dog
dot
dog
-----------------------------
Vertex name dag
cat
bat
dot
cot
cat
cot
dag
dog
dot
dog
-----------------------------
Vertex name dot
cat
bat
dot
cot
cat
cot
dag
dog
dot
dog
-----------------------------
Vertex name cat
cat
bat
dot
cot
cat
cot
dag
dog
dot
dog
-----------------------------

Through some debugging, I found that

if is_valid == True:
    v[i].edges.append(v[j])
    v[j].edges.append(v[i])

is causing the issue but I'm just not able to wrap my head around it. It's not like I am modifying the to_vertex's edges field in the first append statement but the first append statement is affecting it too.

Answer 1

I'm not completely sure but I think the problem is using the default value [] for edges which (I think) creates a unique object [] and then initialise by default to that unique object. So all your edges will essentially be the same object and when you append to one of them, you append to all the other as well. Does that make sense?

To avoid the problem, don't use the default init, but force self.edges = [].

Or if you really want to be able to initialise arbitrary edges, try something like:

def __init__(self, distance = -1, edges = None, name = ''):
    self.name = name
    self.distance = distance
    if edges is None:
        edges = []
    self.edges = edges

(Let me know if that works since I'm not sure about this...)