FW: Graphtool: Finding the paths that the maximum flow algorithm produces

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

FW: Graphtool: Finding the paths that the maximum flow algorithm produces

Hobé  Alex
Hi Tiago and everyone else on the list

Thank you for your swift reply.
The attached png is one example of a max flow calculation result.
The flow is limited in four places in this graph.
I would like to extract the order of the edges in the four paths I drew.

The shortest path solution you described corresponds to path 3 in the drawing.
all_shortest_paths gives my path 3 and another completely different path before crashing with a memoryError.

Looking forward to hearing from you.
Best,

Alex
________________________________________
From: Tiago de Paula Peixoto [[hidden email]]
Sent: Thursday, March 09, 2017 18:43
To: Hobé  Alex
Subject: Re: Graphtool: Finding the paths that the maximum flow algorithm produces

Hi Hobé,

I'm not sure I understand what you want. Any path containing edges with
positive flow is a "flow path". There are many of them. Which one do you
want? If you just want _some_ path, just filter out the edges with zero flow
and get the shortest path. But there are many other ways to proceed...

Best,
Tiago

PS. There is a mailing list of the graph-tool project, where questions like
this can be posted. It is better to use the list than to ask me directly,
since it builds a repository of questions others can consult, and other
people can help you as well.

On 09.03.2017 17:04, Hobé  Alex wrote:

> Dear Mr. de Paula Peixoto
>
> I am using the python graphtool for my master thesis and am enjoying the
> beautiful pictures it produces.
> When computing the maximum flow I would like to use other edge properties
> along the computed path for further calculations.
> I am therefore looking for a way to find an array, which contains the edges
> along a flow path, similar to the shortest_path result.
> I looked through all the pages of the online tutorial, learnt a couple of
> new tricks, but haven't found a way to solve this.
>
> I would be very thankful for any assistance you would be able to provide and
> I look forward to hearing from you.
> Best wishes,
>
> Alex Hobé

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

image.png (928K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: FW: Graphtool: Finding the paths that the maximum flow algorithm produces

Tiago Peixoto
Administrator
On 10.03.2017 15:17, Hobé  Alex wrote:
> Hi Tiago and everyone else on the list
>
> Thank you for your swift reply.
> The attached png is one example of a max flow calculation result.
> The flow is limited in four places in this graph.

I'll have to trust you. It is not possible to tell from the image that there
are only four possible paths.

> I would like to extract the order of the edges in the four paths I drew.
>
> The shortest path solution you described corresponds to path 3 in the drawing.
> all_shortest_paths gives my path 3 and another completely different path before crashing with a memoryError.

I'm not sure why you get a memory error. I can only guess, since you are not
giving me a concrete example of what you are trying to do (i.e. code).

If you are not filtering the graph, or if there are more than 4 possible
paths, you may run out of memory if you try to store them all. Note that
even if there are 4 paths in the filtered graph, there is definitely a huge
number of them in the unmodified graph.

If you want to consider all paths instead of the shortest paths, you should
use the function all_paths().

If you need more detailed assistance, please provide a _minimal_ and
_self-contained_ example that shows the problem.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: FW: Graphtool: Finding the paths that the maximum flow algorithm produces

Tiago Peixoto
Administrator
On 10.03.2017 15:50, Tiago de Paula Peixoto wrote:
> I'll have to trust you. It is not possible to tell from the image that there
> are only four possible paths.

Looking again at your image, since two of your paths cross in the node in
the middle, there is definitely more than four possible paths...

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: FW: Graphtool: Finding the paths that the maximum flow algorithm produces

Hobé  Alex
Hi Tiago

I guess I need to be a little clearer on what I am trying to achieve.
The previous image has 41 possible paths according to the graph tool (using all_paths).
I have now been able to reduce these to 6 by removing all of the edges with a weight of 0.0 (attached png).

I am setting the flow through each path as the minimum weight encountered on that path.
When I then sum over each path, the total flow should equal to the max flow result.

When I sum over the six paths obtained, I get a too high result.
Using the rules I just described, the paths 1-4 add up to the desired result.

I apologize for not including the code.
I would have to create something new that does not include my research.

Thank you for your help.
Best,

Alex


________________________________________
From: graph-tool [[hidden email]] on behalf of Tiago de Paula Peixoto [[hidden email]]
Sent: Friday, March 10, 2017 16:55
To: [hidden email]
Subject: Re: [graph-tool] FW: Graphtool: Finding the paths that the maximum flow algorithm produces

On 10.03.2017 15:50, Tiago de Paula Peixoto wrote:
> I'll have to trust you. It is not possible to tell from the image that there
> are only four possible paths.

Looking again at your image, since two of your paths cross in the node in
the middle, there is definitely more than four possible paths...

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

image2.png (994K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: FW: Graphtool: Finding the paths that the maximum flow algorithm produces

Tiago Peixoto
Administrator
On 10.03.2017 16:16, Hobé  Alex wrote:

> Hi Tiago
>
> I guess I need to be a little clearer on what I am trying to achieve.
> The previous image has 41 possible paths according to the graph tool (using all_paths).
> I have now been able to reduce these to 6 by removing all of the edges with a weight of 0.0 (attached png).
>
> I am setting the flow through each path as the minimum weight encountered on that path.
> When I then sum over each path, the total flow should equal to the max flow result.
>
> When I sum over the six paths obtained, I get a too high result.
> Using the rules I just described, the paths 1-4 add up to the desired result.
What you want seems to be the solution of a constrained optimization
problem, i.e. sets of paths that collectively exhaust the maximum flow.
There is not ready algorithm for this in graph-tool, you have to come up
with your own.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: FW: Graphtool: Finding the paths that the maximum flow algorithm produces

Hobé  Alex
Very well.

Thank you.
Best,

Alex
________________________________________
From: graph-tool [[hidden email]] on behalf of Tiago de Paula Peixoto [[hidden email]]
Sent: Friday, March 10, 2017 17:35
To: Main discussion list for the graph-tool project
Subject: Re: [graph-tool] FW: Graphtool: Finding the paths that the maximum flow algorithm produces

On 10.03.2017 16:16, Hobé  Alex wrote:

> Hi Tiago
>
> I guess I need to be a little clearer on what I am trying to achieve.
> The previous image has 41 possible paths according to the graph tool (using all_paths).
> I have now been able to reduce these to 6 by removing all of the edges with a weight of 0.0 (attached png).
>
> I am setting the flow through each path as the minimum weight encountered on that path.
> When I then sum over each path, the total flow should equal to the max flow result.
>
> When I sum over the six paths obtained, I get a too high result.
> Using the rules I just described, the paths 1-4 add up to the desired result.

What you want seems to be the solution of a constrained optimization
problem, i.e. sets of paths that collectively exhaust the maximum flow.
There is not ready algorithm for this in graph-tool, you have to come up
with your own.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>

_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: FW: Graphtool: Finding the paths that the maximum flow algorithm produces

Percy
Hi, Alex!

I encountered the same problem as you described in this issue. Generally, I
would like to list all the integer flows in a single-source-single target
maximal flow problem. According to the integer max flow theorem, I think the
search should be polynomial. Nonetheless, I am not sure how to do it using
graph-tool although it is fast and efficient. Could you please share some
intuitive ideas to ? I am very appreciate your kindness.

Best,
Percy.



--
Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: FW: Graphtool: Finding the paths that the maximum flow algorithm produces

Hobé  Alex
Hi Percy

Could you give me a reference on the polynomial nature of this problem?

The way I understand max-flow problems, what you are asking for does not have a unique solution.
The amount of flow will always be the same, but how much flow is found on which edges differs between algorithms.
The obtained list of integer flows will therefore differ depending on how you obtained the total flow solution and how you extract the integer flows from it.

The solution of the problem I described is described in my submitted paper:
https://www.researchgate.net/publication/322714014_Estimating_Flow_Rates_through_Fracture_Networks_using_Combinatorial_Optimization

Please, let me know if you need further assistance.
All the best,

Alex

________________________________________
From: graph-tool [[hidden email]] on behalf of Percy [[hidden email]]
Sent: Tuesday, May 29, 2018 9:22
To: [hidden email]
Subject: Re: [graph-tool] FW: Graphtool: Finding the paths that the maximum flow algorithm produces

Hi, Alex!

I encountered the same problem as you described in this issue. Generally, I
would like to list all the integer flows in a single-source-single target
maximal flow problem. According to the integer max flow theorem, I think the
search should be polynomial. Nonetheless, I am not sure how to do it using
graph-tool although it is fast and efficient. Could you please share some
intuitive ideas to ? I am very appreciate your kindness.

Best,
Percy.



--
Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: FW: Graphtool: Finding the paths that the maximum flow algorithm produces

Percy
Hi Alex,

Sorry for the delay. I forgot to check the discussion list.

The main references are theorem 2.24 in Jon Kleinberg's Ph.D thesis,
Approximation Algorithms for Disjoint Path Problems, and Chapter 12,
Approximation algorithms by Vijay Vazirani.

Before briefly answering your question, I think it is necessary to make
something more specific. Consider a directional graph G = (N,E) and a
source-termination pair (s, t) with demand p. Each link e in E attaches a
parameter referred to bandwidth B_e. We refer a flow as a sequence of links
each of which receives a flow. The total flow over an edge cannot exceed its
bandwidth. If the bandwidths are positive integers, we have the following
interesting integral version of max-flow min cut theorem.

The max-flow is fractionally realizable if and only if it is realizable by p
flow paths each carrying one unit of flow.

In the simplest case I have ever known, these flow paths can be constructed
using augmenting paths (Ford-Fulkerson Algorithm) each carrying just one
unit flow originated from source s. Its time complexity is O(Np).

Best,
Percy



--
Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool