CODEWITHSUNDEEP
pythonnetworkxshortest-path
Anathapindika
Anathapindika

Reputation: 141

networkx, moore-neighbourhood, shortest path issue

I am trying to build a rectangular graph in a Moore-neighbourhood. Within that, I am searching for the shortest path (nx.shortest_path) but get strange (zig-zag) results.

I am quite sure, the reason for that is how i build the graph, but dont find the problem.

First, I build the Grid and the nodes: 

#Building the Grid and the nodes
resolution = 1
length = 10
index = 0
xGrid = np.arange(0, length+1, resolution)
yGrid = np.arange(0, length+1, resolution)
G = nx.Graph()
print(xGrid)
meshNumber = np.zeros((length, length))
for i in range(length):
    for j in range(length):
        G.add_node(index, pos=(
            xGrid[j], yGrid[i]))
        meshNumber[j,i] = index
        index += 1

Then, i calcuate the edges and its weights

# Building the edges
diag = np.sqrt(2) * resolution
for i in range(1, length-2):
    for j in range(1, length-2):
        if meshNumber[j, i]:
            if meshNumber[j - 1, i]:
                G.add_edge(
                    meshNumber[j, i], meshNumber[j - 1, i], weight=resolution)
            if meshNumber[j + 1, i]:
                G.add_edge(
                    meshNumber[j, i], meshNumber[j + 1, i], weight=resolution)
            if meshNumber[j, i - 1]:
                G.add_edge(
                    meshNumber[j, i], meshNumber[j, i - 1], weight=resolution)
            if meshNumber[j, i + 1]:
                G.add_edge(
                    meshNumber[j, i], meshNumber[j, i + 1], weight=resolution)
            if meshNumber[j - 1, i - 1]:
                G.add_edge(
                    meshNumber[j, i], meshNumber[j - 1, i - 1], weight=diag)
            if meshNumber[j - 1, i + 1]:
                G.add_edge(
                    meshNumber[j, i], meshNumber[j - 1, i + 1], weight=diag)
            if meshNumber[j + 1, i + 1]:
                G.add_edge(
                    meshNumber[j, i], meshNumber[j + 1, i + 1], weight=diag)
            if meshNumber[j + 1, i - 1]:
                G.add_edge(
                    meshNumber[j, i], meshNumber[j + 1, i - 1], weight=diag)

searching for the path: 

# Finding the path
start = 5
end = 66
try:
    path = set(nx.shortest_path(G, start, end))

except nx.exception.NetworkXNoPath:
    raise AssertionError("Could not find a good Path")

plotting:

# Plotting
flatten = np.ones((index), dtype=np.int)
for p in path:
    flatten[int(p)] = 900
flatten[start] = 1000
flatten[end] = 1000
colors = []
for f in flatten:
    colors.append(str(f))
pos = nx.get_node_attributes(G, 'pos')
fig = plt.figure(1, figsize=(12, 12), dpi=90)
ax = fig.add_subplot(111)
pos = nx.get_node_attributes(G, 'pos')
nx.draw_networkx_nodes(G, pos, node_color=colors, node_size=500, alpha=0.8,
                       linewidths=3)
nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5)
nx.draw_networkx_edges(G, pos, width=4, alpha=0.5, edge_color='#6985a5')
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
plt.savefig("zigzag.png")
plt.show()

Upvotes: 3

Views: 451

Answers (1)

rodgdor
rodgdor

Reputation: 2630

That strange zigzag is a valid shortest path of 6 edges, I don't see what is the problem. On the other hand the zigzag is not the shortest path if we take into account the weight of the edges. For which case you must use:

try:
    path = set(nx.shortest_path(G, start, end, weight='weight'))

except nx.exception.NetworkXNoPath:
    raise AssertionError("Could not find a good Path")

Giving you the following path: new path

Upvotes: 1

Related Questions