How can I get the path from start to a specified node?

Question

I have file like this.

From	To
1	2
2	3
3	4
3	5
4	6
5	7
6	8

How can I find the path for each point?

For eg:

For 3 is [(1,2), (2,3)]

for 8 is [(1,2),(2,3),(3,4),(4,6),(6,8)]

Any Help would be appreciable!!!!!!!!!

You dont need pandas but you can set your data structure as `dict()` and use bfs or dfs — user1462442, Apr 18 '21 at 17:18
@user1462442 I just want to find the path from a start to any required point. — Abanish Tiwari, Apr 18 '21 at 17:20
This has nothing to do with pandas. Look up some path finding algorithms like [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) and [A*](https://en.wikipedia.org/wiki/A*_search_algorithm) — Code Different, Apr 18 '21 at 17:21
For 8 isn't it `[(1, 2), (2, 3), (3, 4), (3, 5), (4, 6), (5, 7), (6, 8)]` instead of `[(1,2),(2,3),(3,4),(4,6),(6,8)]` — Anurag Dabas, Apr 18 '21 at 17:22
https://stackoverflow.com/questions/2505431/breadth-first-search-and-depth-first-search https://trykv.medium.com/algorithms-on-graphs-lets-talk-depth-first-search-dfs-and-breadth-first-search-bfs-5250c31d831a It doesn't matter. The only difference is adding another function argument. You created a classic pathfinding problem — user1462442, Apr 18 '21 at 17:22
What happened when you tried putting `python find path in graph` into a search engine? — Karl Knechtel, Apr 18 '21 at 17:49
@KarlKnechtel I am a beginner didn't know of these modules, so tried to do on my way. — Abanish Tiwari, Apr 18 '21 at 17:56

score 3 · Answer 1 · answered Apr 18 '21 at 17:23

3

A data structure like dict is more suitable to store the graph information.

Set To as index, so that given a node x we can find out prev node using df.loc[x, 'From']. Start from the destination node and keep moving to the previous node until you get 1(source node).

Use:

df = df.set_index('To')
x = 8
output = []
while x!=1:
    y = df.loc[x, 'From']
    output = [(y, x)] + output
    x = y

Prints:

>>> output
[(1, 2), (2, 3), (3, 4), (4, 6), (6, 8)]

answered Apr 18 '21 at 17:23

Amit Vikram Singh

2,090
10
20

Thank you, I tried moving from forward to backward and that was must difficult since there can be multiple branches. I didn't think about the reverse that the last one would have only one point prior to it. It worked – Abanish Tiwari Apr 18 '21 at 17:36
[BFS](https://stackoverflow.com/questions/23477921/bfs-algorithm-in-python) is the most used algorithm for such purposes. However in your case, graph is a Tree which means there is a unique path from source to destination and we also have the access to back pointer from a node to its parent node, so here we can simply do backtracking(I hope it's correct name). – Amit Vikram Singh Apr 18 '21 at 17:39

score 2 · Answer 2 · answered Apr 18 '21 at 18:10

If it suits your purpose, you can resort to a "specialized" package for working with graphs. I'll give an example with networkx. In the example:

I've taken the data you provided;
converted it to networkx Graph;
printed a list of the nodes (not the edges, note) that make your path;
drawn a plot and saved it to a .png file.

import networkx
import pandas as pd
import matplotlib.pyplot as plt

df = pd.DataFrame(data=[(1, 2), (2, 3), (3, 4), (3, 5), (4, 6), (6, 8)],
                  columns=['from', 'to'])

g = networkx.from_pandas_edgelist(df, source='from', target='to')

# Print a list of the nodes in the path from 1 to 8
print(networkx.shortest_path(g, source=1, target=8))

# Plot the graph
networkx.draw_networkx(g)
plt.savefig("test.png", format="PNG")

How can I get the path from start to a specified node?

2 Answers2