CODEWITHSUNDEEP
pythongraphnetworkx
bala bharath
bala bharath

Reputation: 63

Count steps between nodes using adjacency list

adj_list={1:[2,4],2:[1,3,4,8],3:[2,6,8,7],4:[1,5,2],5:[4,6],6:[3,9,5],7:[3,8,9,10],8:[2,3,7],9:[6,7,10],10:[7,9]}

def func(x,y):
t=0
xx=x
global i
for i in range(len(adj_list[xx])):
    if y in adj_list[xx]:
        t=t+1
        # print(x,y,t)
        break
    else:
        if xx<y:
            t = t + 1
            xx = xx + 1
    i=0
print(x,y,t)

func(1,6)

I except the output like: 

func(1,10) :1-2-3-7-10(4) or 1-2-8-7-10(4)

4 should be no of steps from 1 to 10

Upvotes: 0

Views: 510

Answers (3)

yatu
yatu

Reputation: 88236

You can use networkx for this. Start by building a network using the keys as nodes and the values as edges. A little extra work will be necessary for the edges however, given that edges must be lists of tuples containing (source_node, dest_node).

So a way to deal with this is to get all key-value combinations from all entries in the dictionary.

For the nodes you'll simply need:

nodes = list(adj_list.keys())

Now lets get the list of edges from the dictionary. For that you can use the following list comprehension:

edges = [(k,val) for k, vals in adj_list.items() for val in vals]
# [(1, 2), (1, 4), (2, 1), (2, 3), (2, 4)...

So, this list contains the entries in the dict as a flat list of tuples:

1: [2, 4]         ->    (1, 2), (1, 4)
2: [1, 3, 4, 8]   ->    (2, 1), (2, 3), (2, 4), (2, 8)
...

Now lets build the network with the corresponding nodes and edges:

import networkx as nx
G=nx.Graph()
G.add_edges_from(edges)
G.add_nodes_from(nodes)

Having built the network, in order to find the steps between different nodes, you can use shortest_path, which will give you precisely the shortest path between two given nodes. So if you wanted to find the shortest path between nodes 1 and 10:

nx.shortest_path(G, 1,10)
# [1, 2, 3, 7, 10]

If you're interested in the length simply take the len of the list. Lets look at another example:

nx.shortest_path(G, 1,6)
# [1, 2, 3, 6]

This can more easily checked by directly plotting the network:

nx.draw(G, with_labels = True)
plt.show()

enter image description here

Where in the case of the shortest path between nodes 1 and 10, as it can be seen the intermediate nodes are [1, 2, 3, 7, 10]:

enter image description here

Upvotes: 1

William Kluge
William Kluge

Reputation: 21

If you want a quick and easy implementation in pure Python you can use recursion to traverse the adjacent list and count the number of steps it takes to get to the destination from each node, then only record whichever path took the least amount of steps.

def count_steps(current_vertex, destination, steps=0, calling=0):
    """
    Counts the number of steps between two nodes in an adjacent array
    :param current_vertex: Vertex to start looking from
    :param destination: Node we want to count the steps to
    :param steps: Number of steps taken so far (only used from this method, ignore when calling)
    :param calling: The node that called this function (only used from this method, ignore when calling)
    :return: 
    """
    # Start at illegal value so we know it can be changed
    min_steps = -1
    # Check every vertex at the current index
    for vertex in adj_list[current_vertex]:
        if destination in adj_list[current_vertex]:
            # We found the destination in the current array of vertexes
            return steps + 1
        elif vertex > calling:
            # Make sure the vertex we will go to is greater than wherever we want to go so we don't end up in a loop
            counted = count_steps(vertex, destination, steps + 1, current_vertex)
            if counted != -1 and (min_steps == -1 or counted < min_steps):
                # If this is actually the least amount of steps we have found
                min_steps = counted
    return min_steps

Note that when we find the destination in the current vertex's array we add one. This is because one more step would be needed to actually get to the node we found.

Upvotes: 2

Kaiwen Chen
Kaiwen Chen

Reputation: 322

If you're looking into the least amount of steps to get from a specific node to any other node, I would suggest Dijkstra's Algorithm. This isn't a problem that is solvable in a single loop, it requires a queue of values that keeps in mind the shortest amount of steps.

Upvotes: 1

Related Questions