Widest (Bottleneck/Fattest) Path implementation

[Checho RP]

Hi, I'd like to know if  NetworkX provides an implementation of the widest path (aka maximum bottleneck path) in a graph.

Thanks. 

[Daniel Schult]

The widest path problem can be solved using the shortest_path routines by changing your weights appropriately. The algorithm is described on this wikipedia page

On Tue, Sep 6, 2016 at 12:00 PM, Checho RP <sergior...@gmail.com> wrote:

Hi, I'd like to know if  NetworkX provides an implementation of the widest path (aka maximum bottleneck path) in a graph.

Thanks. 

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to networkx-discuss@googlegroups.com.
Visit this group at https://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.

[Harris Teague]

I don't think this is true (but please correct me if wrong).  I think the solution is to enable

https://github.com/networkx/networkx/blob/master/networkx/algorithms/shortest_paths/weighted.py#L826

which says

            vu_dist = dist[v] + cost

to alternatively compute

            vu_dist = max(dist[v], cost)

I have tested this on a couple of digraphs and it works, but I haven't run any test suites to make sure.  I agree this would be a great feature to add to the algos.  Even if it were a simple weight function change, documentation on how to do that would be helpful.

On Tuesday, September 6, 2016 at 10:21:52 AM UTC-7, Dan Schult wrote:

The widest path problem can be solved using the shortest_path routines by changing your weights appropriately. The algorithm is described on this wikipedia page

On Tue, Sep 6, 2016 at 12:00 PM, Checho RP <sergior...@gmail.com> wrote:

Hi, I'd like to know if  NetworkX provides an implementation of the widest path (aka maximum bottleneck path) in a graph.

Thanks. 

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to networkx...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.

[Dan Schult]

You are correct that it is not trivial to set up the weight functions to convert from shortest_path to widest_path.

You have to somehow change the addition operator to a max operator.

Perhaps something like this:

class Widest_Add():

    def __init__(self, width):

        self.width = width

    def __add__(self, other):

        # maybe put a check that other has class Widest_Add. But shouldn't need.

        return Widest_Add(max(self.width, other.width))

    def __le__(self, other):

        return self.width <= other.width

    def __lt__(self, other):

        return self.width < other.width

    def __eq__(self, other):

        return self.width == other.width

    # might need > or >= too, but I don't think so... look at _dijkstra_multisource and operations on uv_dist

def widest_weight(node1, node2, datadict):

    # This assume the graph stores a number in edge attribute 'width'

    return Widest_Add(datadict['width'])

Then, in the shortest path algorithm (e.g. dijkstra) when it stores dist[u] it stores a Widest_Add object.

So, 

        uv_dist = dist[u] + cost

actually computes 

        uv_dist = Widest_Add(max(self.width, other.width))

Seems like this would be good to put in the docs somewhere, or maybe create a function that does it.

Thanks for the question!

Dan

[Harris Teague]

Very clever!

As a user I must admit a helper function called ..max_bottleneck() would be quite a bit more intuitive.  Admittedly fitting this into the "shortest path" algo module is also confusing, so not sure the cleanest way.

As a clarification, the solution I suggested would be the "reciprocal" of the problem as originally stated.  The original stated problem is to maximize the minimum path bottleneck.  The solution I suggest actually minimizes the maximum path cost.  They are the same solution with 1/w substituted as the edge costs.  Minimizing max path cost is also quite useful problem.  For example, minimizing local memory use in a compute schedule.

[Rajesh Raju]

Hi,

If I use 1/weight, is it possible to locate the edge with the highest weight value? How can i locate the edge with the largest weight in a shortest path? 

I appreciate your help.

Thanks

Rajesh

[Harris Teague]

It's an order m loop, so I would just do it directly.

maxw = -big number

for e in g.edges:

    maxw = max(maxw, g[e]['weight']

for shortest path edges, just loop over that

for e in shortest_path_edges:

   ...

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/e19a7d67-50a7-4750-b71d-121196e46597o%40googlegroups.com.

[Dan Schult]

Typically, finding the max of an iterator over the edges you want is the way to go.

Something like:         

max(G.edges(data='weight', default=1), key = lambda x: 1/x[2])

Paths are usually specified as lists of nodes, so you find/form the edges through pairwise consideration of the nodes.

max(nx.utils.pairwise(path), key = lambda x: G.edges[x[0], x[1]].get('weight', 1))

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

[Rajesh Raju]

Thanks !!!! It was  indeed a great help 

Rajesh

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CA%2BXMcTOkWwD0Yefj%2BPbbdMH9P1W7uUtcRvfQe-Q2RA-Oqr10%2BA%40mail.gmail.com.