How do I create adjacency matrix representation in Python

Question

0.00/5 (No votes)

See more:

I was given a sample file. Each row contains: two nodes, and a cost
I want to create a list where I have an adjacency matrix representation, from which I can implement Dijkstra's shortest path Algorithm.
For example, suppose I was given this sample graph:

0 3 .92
0 6 .97
1 2 .94
1 3 .91
1 4 .93
2 3 .95
2 4 .98
2 5 .92
3 5 .91
4 5 .94
4 6 .99
5 6 .92

How would I go about changing the contents of the file into adjacency matrix representation.

I would have hardcoded this, but I want a scenario where I do not know the contents of a file and I want to have adjacency matrix representation of the file which can contain up to 20 nodes.

I hope that makes sense.
Any help would be really appreciated. Thank you

What I have tried:

I just need an idea on how to do this

Posted 13-Nov-20 12:01pm

Nathania21

Updated 14-Nov-20 4:03am

Add a Solution

Comments

[no name] 14-Nov-20 4:52am

That is a mathematics question. Once you understand the maths then the Python code should be fairly easy.

1 solution

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Answer 1 · 2020-11-14T04:03:00

Solution 1

I would do that this way:

Scan the file in order to find the minimum and maximum row and column indices. For simplicity sake, let's say the minima are zeroes and maxima are max_row and max_col.
Create a bidimensional list having (max_row + 1) rows and (max_col + 1) columns. Initialise all the items of the bidimensional list with 0.
Scan the file again, assigning the proper value to the corresponding item of the bidimensional list (e.g. 0 3 .92 => m[0][3] = .92.

That's all, folks.

[update]
Fixed the wrong column index, thanks to Patrice T.
[/update]

Posted 14-Nov-20 4:03am

CPallini

Updated 14-Nov-20 11:06am

v2

Comments

Patrice T 14-Nov-20 10:17am

Are you sure ?

0 3 .92 => m[0][2] = .92
  ^             ^

[no name] 14-Nov-20 11:08am

You have heard of Polish notation; this is the Italian version, which is far more relaxed. :)

CPallini 14-Nov-20 17:07pm

Indeed. :-D

Patrice T 14-Nov-20 18:18pm

Personally, I prefer Reverse Polish Notation (RPN)?
Because I learned to use calculators with dad's HP67. :)

CPallini 14-Nov-20 17:07pm

Indeed, it is the relaxed Italian notation.
Thank you for pointing it out.

How do I create adjacency matrix representation in Python

1 solution

Solution 1

Add your solution here

Preview 0

How do I create adjacency matrix representation in Python

1 solution

Solution 1

Add your solution here

Preview 0

Existing Members

...or Join us