CODEWITHSUNDEEP
pythonnetworkxgraph-theory
Laurent
Laurent

Reputation: 83

networkx: update edge weights during traversal

Consider this simple directed graph.

enter image description here

The problem is to find the shortest weighted path between A and D. This is trivially A-B-C-D.

Now consider this: The act of traversing the A-B edge has the consequence of increasing the C-D edge weight by 10. With this constraint, the shortest weighted path now becomes A-D.

More generally, I want the ability to modify the edge weights depending on what edges are part of the current path (where the order of edges doesn't matter).

Does this problem have a name? Is it possible to utilize networkx to solve it?

My thoughts so far is that I will need to keep the current edge weights in memory for each path, and copy that data structure over to the next path.

More context: I'm trying to represent a switch, where traversing an edge gives a physical constraint that disables other edges.

Upvotes: 1

Views: 94

Answers (1)

ravenspoint
ravenspoint

Reputation: 20596

This can be tackled using the A* algorithm https://en.wikipedia.org/wiki/A*_search_algorithm

At each step use Dijkstra to estimate the cost of reaching the goal from every leaf of the search tree, using the current edge costs, choosing to extend the leaf of the search tree that has the lowest estimated cost to reach the goal.

I will need to keep the current edge weights in memory for each path

Not so long as the edge cost cannot be changed AFTER is has been traversed. You need to store the total cost to reach every leaf of the current search tree. The estimate of the cost to reach the goal is the sum of the cost to reach the leaf and the total cost to reach the goal from the leaf, which can be calculated on the fly.

traversing an edge gives a physical constraint that disables other edges.

So, you will need a table listing for each edge the edges that cause it to be disabled. For your example

A->B    
B->C
C->D      A->B
A->D

Implementation of this is far too complex for python. Perhaps you might be interested in seeing a C++ implementation?

The A* for constant edge weights implementation signature looks like this

/// @brief Implement the A* algorithm with constant edge weights
/// @param g graph to be searched https://github.com/JamesBremner/PathFinder
/// @param edgeWeight function calculates edge weight based on edge index
/// @param start vertex index
/// @param goal vertex index
/// @param heuristic function calculates distance estimate from vertex to goal
/// @return vector of vertex indices on path from start to goal

std::vector<int> astar(
    raven::graph::cGraph &g,
    std::function<double(int)> edgeWeight,
    int start, int goal,
    std::function<double(int)> heuristic);

If the edge weights depend on the path traversed so far, then the signature becomes

/// @brief Implement the A* algorithm with dynamic edge weights
/// @param g graph to be searched https://github.com/JamesBremner/PathFinder
/// @param dynWeight function calculates edge weight based on path so far
/// @param start vertex index
/// @param goal vertex index
/// @param heuristic function calculates distance estimate from vertex to goal
/// @return vector of vertex indices on path from start to goal

std::vector<int> astarDynWeights(
    raven::graph::cGraph &g,
    std::function<double(int,const std::vector<int>&)> dynWeight,
    int start, int goal,
    std::function<double(int)> heuristic);

The implementation successfully passes a unit test based on your example https://github.com/JamesBremner/astar/blob/5708c7df59455276b8c21528bdbb4deff7cab7d0/src/test.cpp#L217-L296

Complete code at https://github.com/JamesBremner/astar

Upvotes: 1

Related Questions