0

I have a programming assignment where I must read in a tree from a text file to an adjacency matrix, then empirically compare Prim's and Kruskal's Minimum Spanning Tree (MST) algorithms. I could do this in Java, but I'm trying to learn Python (this is my first week with Python).

For me, the hardest thing (I believe) will be converting the .txt file into workable keys that the algos can work with.

If my .txt file is given in the format:

Sample input file
1 : 2 2, 4 5
2 : 1 2, 3 14, 4 5, 5 4
3 : 2 14, 5 34
4 : 1 5, 2 5, 5 58
5 : 2 4, 3 34, 4 58

Where the number before the colon is the vertex, and the next numbers are the vertices it can reach and their costs (For example, vertex 3 can reach vertex 2 with a cost of 14, and vertex 5 with a cost of 34), how can I read this file into a workable adjacency matrix?

The little I know about python makes me assume I will use the "open" method to open the file, and a split method with separate delimiters to collect that information, but how?

Thank you in advance for your help!

Ben Kluger
  • 82
  • 6

1 Answers1

2

You can do something like this:

with open('your_text_file.txt') as f:
    # Let's consider `line` equals to '2 : 1 2, 3 14, 4 5, 5 4'
    for line in f:
        # from_vertex: '2', remaining_line: '1 2, 3 14, 4 5, 5 4'
        from_vertex, remaining_line = line.strip().split(" : ")

        # remaining_tokens: ['1 2', '3 14', '4 5', '5 4']
        remaining_tokens = remaining_line.split(", ")

        # remaning_values: [['1', '2'], ['3', '14'], ['4', '5'], ['5', '4']]
        remaining_values = [value.split(" ") for value in remaining_tokens]

        # to_vertex: '1', weight: '2'
        # to_vertex: '3', weight: '14'
        # to_vertex: '4', weight: '5'
        # to_vertex: '5', weight: '4'
        for to_vertex, weight in remaining_values:
            print(from_vertex, to_vertex, weight)

This will output

1 2 2
1 4 5
2 1 2
2 3 14
2 4 5
2 5 4
3 2 14
3 5 34
4 1 5
4 2 5
4 5 58
5 2 4
5 3 34
5 4 58

for your sample file. Then, you can choose a data structure to handle these verticies.

enzo
  • 9,861
  • 3
  • 15
  • 38
  • 1
    That looks amazing! Thank you, and especially for the comments! Much easier to figure out what's going on. I'll be working on it over the course of the next few days. This should be perfect. Small update: For some reason the output skips the first two rows, any idea why? Output: (hyphens added so the format is a little better) ```2 1 2--- 2 3 14--- 2 4 5--- 2 5 4--- 3 2 14--- 3 5 34--- 4 1 5--- 4 2 5--- 4 5 58--- 5 2 4--- 5 3 34--- 5 4 58``` – Ben Kluger Jul 29 '21 at 05:12
  • 1
    Sorry, your file does not contain a header. I've updated my answer. Consider accepting my answer clicking on the big fat green checkmark if I helped you! – enzo Jul 29 '21 at 06:39
  • 1
    Thank you, and I just hit the checkmark! You helped me a ton. I must have been tired last night because I completely missed the f.readline() - thank you for fixing it though! Also, if you don't mind explaining, could you elaborate on the syntax a bit? You have ```from_vertex, remaining_line = line.strip().split(" : ")``` - does this make both from_vertex & remaining_line = to the split? Or fromVertex = before the delimiter and remainingLine = the rest of the line? Also, how do both toVertex and weight take on the correct values? Thank you :) – Ben Kluger Jul 29 '21 at 19:42
  • Of course! This is called *sequence unpacking* and you can take a look at [this answer](https://stackoverflow.com/q/12923059/9997212) to understand what it's doing. Note that `line.strip().split(" : ")` equals to a list of length 2. On the for-loop, something similar happens. [This answer](https://stackoverflow.com/a/28072982/9997212), specially its section "Breaking it down - a step by step explanation", explains how does sequence unpacking work in a for-loop, using as example the `enumerate` function. Note that `remaining_values` contains lists of length 2. – enzo Jul 29 '21 at 22:45