CODEWITHSUNDEEP
pythontree
Lab-Brat
Lab-Brat

Reputation: 43

Calculating binary tree nodes

Thank you for taking some time to look at my problem.

I am trying to plot a tree graph by reading paths that are in the form of a list of binary numbers. The way I am doing this is first I create a list of tuples that contain 2 lists, the right ones are paths from test_d in the same order they are in the dictionary (starting from the 2nd one), left ones are the paths that have the most number of same nodes with the right paths. This way, I could tell the algorithm from which place the branching should happen.

To label the paths properly, unique integers are assigned to previously unvisited nodes, and for the visited nodes labels are copied from the visited paths. So the first path, no matter what it is, gets a path [1,2,3,4,5,6]. The second path is [7,8,9,10,11,12], because the first nodes of the two paths are different, which means that they have different paths. For the third path, the first nodes of the left and right paths are the same (1 and 0), which means that for the first two nodes, their path is the same, therefore [7,8,13,14,15,16].

Here is my data: This is the dictionary containing all the paths:

test_d = {'d1':  [0, 1, 0, 1, 1, 0],
          'd2':  [1, 0, 0, 0, 0, 1],
          'd3':  [1, 0, 1, 1, 1, 1],
          'd4':  [1, 1, 1, 1, 1, 0],
          'd5':  [0, 1, 0, 1, 1, 1],
          'd6':  [0, 0, 0, 1, 1, 1],
          'd7':  [0, 0, 1, 1, 0, 1],
          'd8':  [0, 0, 0, 1, 0, 1],
          'd9':  [0, 0, 1, 0, 0, 1],
          'd10': [0, 0, 1, 1, 0, 0],
          'd11': [1, 0, 1, 1, 1, 0]}

And this is the list of tuples containing paths from dictionary and paths that are the most similar to them:

MAX = [([0, 1, 0, 1, 1, 0], [1, 0, 0, 0, 0, 1]),
       ([1, 0, 0, 0, 0, 1], [1, 0, 1, 1, 1, 1]),
       ([1, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 0]),
       ([0, 1, 0, 1, 1, 0], [0, 1, 0, 1, 1, 1]),
       ([0, 1, 0, 1, 1, 0], [0, 0, 0, 1, 1, 1]),
       ([0, 0, 0, 1, 1, 1], [0, 0, 1, 1, 0, 1]),
       ([0, 0, 0, 1, 1, 1], [0, 0, 0, 1, 0, 1]),
       ([0, 0, 1, 1, 0, 1], [0, 0, 1, 0, 0, 1]),
       ([0, 0, 1, 1, 0, 1], [0, 0, 1, 1, 0, 0]),
       ([1, 0, 1, 1, 1, 1], [1, 0, 1, 1, 1, 0])]

This is the code I wrote to obtain unique paths:

init_v = list(range(1, len(MAX[0][0])+1))
ind_d = {'i1': init_v}
same_path = True 
count = len(MAX[0][0])

for i in range(0, len(MAX)):
    temp = []
    left = MAX[i][0]
    right = MAX[i][1]

    for j in range(len(left)):
        if right[j] == left[j] and same_path==True:
            for k in MAX:
                if left == k[0]:
                    HALF = k[1]
                    break
            IND = MAX.index((left, HALF))
            temp.append(ind_d['i'+str(IND+1)][j])
        else:
            count += 1
            temp.append(count)
            same_path = False
        
    ind_d['i'+str(i+2)] = temp
    same_path=True

print(ind_d)

To summarize the problem, this is how my end results looks like:

{'i1':  [1, 2, 3, 4, 5, 6],
 'i2':  [7, 8, 9, 10, 11, 12],
 'i3':  [7, 8, 13, 14, 15, 16],
 'i4':  [7, 17, 18, 19, 20, 21],
 'i5':  [1, 2, 3, 4, 5, 22],
 'i6':  [1, 23, 24, 25, 26, 27],
 'i7':  [1, 23, 28, 29, 30, 31],
 'i8':  [1, 23, 24, 25, 32, 33],
 'i9':  [1, 23, 24, 34, 35, 36], #correct: [1, 23, 28, 34, 35, 36]
 'i10': [1, 23, 24, 25, 32, 37], #correct: [1, 23, 28, 29, 30, 37]
 'i11': [1, 23, 24, 25, 32, 38]} #correct: [7, 8, 13, 14, 15, 38]

The tree with red nodes was plotted using the incorrect output. The tree with grey nodes is how the correct tree is supposed to look like

I understand that this is a lot of text, and I apologize for that. Thank you everyone in advance!

Upvotes: 0

Views: 117

Answers (2)

Lab-Brat
Lab-Brat

Reputation: 43

Corrected code for my problem:

init_v = list(range(1, len(MAX[0][0])+1))
ind_d = {'i1': init_v}
same_path = True 
count = len(MAX[0][0])

for i in range(0, len(MAX)):
    temp = []
    left = MAX[i][0]
    right = MAX[i][1]

    for j in range(len(left)):
        if right[j] == left[j] and same_path==True:
            for k in range(len(MAX)):
                if left == test_d['d1']:
                    IND = 0
                elif left == MAX[k][1]:
                    IND = MAX.index(MAX[k]) + 1
                    break
            temp.append(ind_d['i'+str(IND+1)][j])
        else:
            count += 1
            temp.append(count)
            same_path = False
        
    ind_d['i'+str(i+2)] = temp
    same_path=True

Upvotes: 1

GrimTrigger
GrimTrigger

Reputation: 591

You match the nodes visited in if right[j] == left[j] and same_path==True: but do not track left or right path from already visited nodes. i6 and i7 differentiate after node 23 but in constructing i9 your simple match via right[j] == left[j] always yields the same path. You should use established binary tree traversals (see enter link description here for a general intro or enter link description here for a concrete Python implementation.

Upvotes: 0

Related Questions