Problems while generating manually a graph

[ProGM]

I'm trying to obtain a graph that looks like this one:

I should obtain a graph like the one explained here: http://www.cs.utexas.edu/~grauman/courses/fall2011/handouts/examples/Adrian_demo_with_notes.pdf

I'm in trouble while adding the tedges, because I can't understand how add_grid_tedges works. Why is it asking to add both sink node and terminal node weights? I want to connect s only to the leftmost nodes and t only to the rightmost nodes. My actual solution is setting their weights to 0 when I don't want to set them. Here's my code:

g.add_grid_tedges(left_most, np.ones(left_most.shape) * np.inf, np.zeros(left_most.shape))
g.add_grid_tedges(right_most, np.zeros(right_most.shape), np.ones(right_most.shape) * np.inf)

right_most is a list of the right-most nodes of the image. The same for left_most.

The problem is that I'm obtaining strange results: When I add no s and t link, the internal graph is correct. When I add either s or t (or both), the internal nodes lose some of their edges... Here's an image that should explain the behaviour: The graph without s and t: The graph after adding s and t edges:

As you can see, all the edges between the first and the second column disappears... I think I misunderstood how to use add_grid_tedges and add_tedge methods. What I'm doing wrong? Sorry if I'm asking so many questions, and thank you for your help!

[pmneila]

Hi,

Why is it asking to add both sink node and terminal node weights? I want to connect s only to the leftmost nodes and t only to the rightmost nodes. My actual solution is setting their weights to 0 when I don't want to set them.

That is perfectly correct and it is the way it is meant to be done. If you want to know more details about why this is so, read the following section.

Note: the section between horizontal rules contains many internal details about the implementation of maxflow, the C++ core of PyMaxflow. You may want to skip it. :)

---

The behaviour of add_grid_tedges (and add_tedge) is a consequence of how maxflow internally deals with the terminal edges: every node stores internally the capacities of both terminal edges (the edge from s and the edge to t). Thus, all nodes are already connected to both s and t with capacities 0 when the graph is created. Despite its name, calling add_grid_tedges does not actually create new terminal edges, but adds the given capacities to the edges that already exist.

If you do not want to change the default 0 capacity of a terminal edge, just call add_grid_tedges with the corresponding capacity set to 0. Since calling add_grid_tedges does not add new edges, no extra memory or computational resources are required when you call it many times.

You might also wonder why maxflow has a method add_grid_tedges for both terminal nodes instead of having a method for s and another method for t. Again, this is related to how maxflow stores the capacities to terminal edges. The key idea is that, internally, the capacity of at least one of the terminal edges connected to a node is always 0. For example, if you write

    g = maxflow.Graph[float]()
    n = g.add_nodes(1)
    g.add_tedge(n[0], 3, 1)

and plot it, you will get The sink capacity is 0, even when we set it to 1. This is not wrong. In fact, setting the source capacity to 3 and the sink capacity to 1 is equivalent to setting the source to 2 and sink to 0. For the terminal edges of a node, the only relevant quantity is the difference between source and sink capacities. This is the value stored internally in maxflow.

If you call g.add_tedge(n[0], 3, 3), no extra capacity will be added (3-3=0).

If you call g.add_tedge(n[0], 1, 3), internally it will store 1-3=-2. This means that the sink edge will have a capacity of 2.

Briefly, changing the capacities of the source or the sink edge is internally equivalent to changing the difference between these capacities, and therefore a single function is provided for both.

---

By the way, note that PyMaxflow already performs broadcasting over the arguments of the grid_* methods so you do not have to do it. I.e., if you want to set all edges to inf or to 0, you could simply write

    g.add_grid_tedges(left_most, np.inf, 0)
    g.add_grid_tedges(right_most, 0, np.inf)

Read the NumPy documentation about broadcasting for more details.

Regarding your second problem, I have not been able to reproduce it as you describe it. This is the graph I get:

Probably you are building the graph AFTER calling g.maxflow(). In that case, the weights you are plotting are the residuals capacities after the maximum flow computation. In this process, a virtual flow goes from the source node to the sink node filling the edges, and the residual capacity for an edge is the total capacity minus the amount of flow passing through that edge. When an edge is full (the residual capacity is 0), the weight is 0, and it is not included in the NetworkX graph when calling to get_nx_graph.

If you call g.get_nx_graph before g.maxflow you should get the graph you expect.

Let me know if this solves your problems!

[pmneila]

Just in case you need it, you can find the code to generate the graph here.

[ProGM]

Oh, this is very very useful! Now everything is pretty clear. You're right, the problem was that I was computing the maxflow before generating the nx_graph. I think you should add some of this informations to your documentation. For example a graph generation with differents weigths in every direction (like the one in your last post).

Moreover you should write something not to compute maxflow before generate the nx_graph... without your help I would never figure out such a thing!

Thank you again :)

[pmneila]

Yes, you are right. I'm aware that the documentation is weak and has to be improved and extended. Unfortunately I do not have much time for that now.

As a quick fix, I have included this example in the examples folder and I have improved the documentation for get_nx_graph.

I will write a decent tutorial that explains all these details (and some others) when I have enough time.

In the meantime, of course, you can ask any question you might have.