Detecting a Cycle in a Directed Graph Python-CodePudding

I am trying to extract a directed graph from a text file that looks like this (1: is node, second number is neighbor, followed by weight, neighbor, weight, etc:

1: 2 3 4 5 6 2
2: 3 -4
3: 8 4
4: 5 6
5: 4 -3 8 8
6: 7 3
7: 6 -6 8 7
8:

Below is my code:

fileName = ("graphin_Fig1.txt")
dictionary = {}     # allocate dictionary space
with open(fileName,'r') as file:    # open file
    for line in file:   # read each line of the file
        tokens = line.strip().split(' ')    # separate each number, remove white space
        node = int (tokens[0].split(':')[0])    # remove :, separate node from neighbors and weights
        pos = 1 # initialize counter        
        listtups = []   # allocate array to hold neghbors and weights
        while pos < len(tokens):  # while end of line has not been reached              
            listtups.append((int(tokens[pos]), int (tokens[pos  1])))   # add ints to array
            pos  = 2    # counter
        if len(listtups) > 0:   # if neigbors and edges are detected
            dictionary[node] = listtups    # add to nodes
print (dictionary)

This is the output:

 `{1: [(2, 3), (4, 5), (6, 2)], 2: [(3, -4)], 3: [(8, 4)], 4: [(5, 6)], 5: [(4, -3), (8, 8)], 6: [(7, 3)], 7: [(6, -6), (8, 7)]}`

I am trying to use my dictionary for other algorithms, but they will only work if the dictionary looks like the example below:

dictionary = {
    1: {2: 3, 4: 5, 6: 2},
    2: {3: -4},
    3: {8: 4},
    4: {5: 6},
    5: {4: -3, 8: 8},
    6: {7: 3},
    7: {6: -6, 8: 7},
    8: {}
}

I am new to python and really struggling. How do I change my code to make my extracted dictionary look like the example directly above?

CodePudding user response：

You are very close. The only thing left is to convert your list of tuples to dictionary, so instead of:

dictionary[node] = listtups    # add to nodes

try

dictionary[node] = dict(listtups)

And remove if statement that checks for length of neigthbours, as your example shows that you want to add node even when there is no adjacent nodes.

CodePudding user response：

Well, you don't have the same datastructure at all. What you want is a dictionnary that contains dictionaries. E.g.:

outer_d = {"inner_d":{...}, ...}

What you're doing is a dictionnary, whose values for each key isn't a dictionnary but a list (of tuples), e.g.:

outer_d = {"key":[...], ... }

Do you understand the difference?

fileName = ("graphin_Fig1.txt")
dictionary = {}     
with open(fileName,'r') as file:    
    for line in file:  
        tokens = line.strip().split(' ')
        node = int (tokens[0].split(':')[0]) 
        pos = 1 # initialize counter        
        listtups = {}   # another dictionnary, not a list!
        while pos < len(tokens): 
            listtups[int(tokens[pos])] =  int(tokens[pos  1]) 
            pos  = 2    # counter
        if len(listtups) > 0:
            dictionary[node] = listtups 
print (dictionary)

Which yields:

{1: {2: 3, 4: 5, 6: 2}, 2: {3: -4}, 3: {8: 4}, 4: {5: 6}, 5: {4: -3, 8: 8}, 6: {7: 3}, 7: {6: -6, 8: 7}}