Detecting a Cycle in a Directed Graph Python

Question

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?

user_3361462 · Answer

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.

user_3633696 · Answer

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

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

What you're doing is a dictionary, whose values for each key isn't a dictionary 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 dictionary, 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}}

Detecting a Cycle in a Directed Graph Python

2 Answers