Opened 3 years ago

Closed 3 years ago

#28837 closed defect (fixed)

Flow polytope does not work as expected on Multi-Digraphs

Reported by: Jonas Frede Owned by:
Priority: major Milestone: sage-9.0
Component: graph theory Keywords: flow polytopes, multi-digraphs, digraphs, linear programming, combinatorial optimization
Cc: Merged in:
Authors: David Coudert Reviewers: Jonas Frede
Report Upstream: N/A Work issues:
Branch: 5af4462 (Commits, GitHub, GitLab) Commit: 5af44625a95f04be2b0eb0c85a4942804820ee6d
Dependencies: Stopgaps:

Status badges

Description (last modified by Jonas Frede)

Flow polytopes of directed graphs are the convex hulls of nonnegative flow values for the arcs of said digraph such that the flow is conserved on internal vertices, and there is a unit of flow leaving the sources and entering the sinks.

Yet, while working with multi-digraphs where there are multiple arcs in the same (!) direction for some vertex pairs, the nonnegativity conditions may be violated and the flow polytope will not be a subset of the 0/1-cube any more.

A possible suggested temporary fix could be to intersect the resulting polytope with the needed halfspaces given by the nonnegativity constraints and the upper bounds of 1 for every variable, although that would not fix the underlying problem.

This already happens in the following small example:

sage: G = DiGraph(multiedges=True)
sage: G.add_edge(0,1)
sage: G.add_edge(0,1)
sage: G
Multi-digraph on 2 vertices
sage: P = G.flow_polytope()
sage: P
A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 line
sage: P.vertices()
(A vertex at (0, 1),)
sage: P.lines()
(A line in the direction (1, -1),)

P should be the polytope with vertices (0,1) and (1,0), without any lines.

Change History (15)

comment:1 Changed 3 years ago by Jonas Frede

Keywords: multi-digraphs digraphs linear programming combinatorial optimization added

comment:2 Changed 3 years ago by Jonas Frede

Description: modified (diff)

comment:3 Changed 3 years ago by David Coudert

Method flow_polytope builds a set of inequalities and a set of equalities and then gives them to Polyhedron. Here we get

ineqs = [[0, 1, 1], [0, 1, 1]]
eqs = [[1, -1, -1], [-1, 1, 1]]

so 2 inequalities are the same. I suspect that Polyhedron simplifies that, but I'm not sure.

comment:4 in reply to:  3 Changed 3 years ago by Jonas Frede

Replying to dcoudert:

ineqs = [[0, 1, 1], [0, 1, 1]]

Ah, so the building of inequalities is wrong, as they should be the nonnegativity constraints for every arc (exactly one entry should be 1, the others should be 0).

To generate the nonnegativity constraints we do

ineqs = [[0] + [Integer(j == u) for j in edges]
                 for u in edges] 

where instead it should be

ineqs = [[0] + [Integer(j is u) for j in edges]
                 for u in edges] 

to account for the variables referencing the same object instead of just being equal, which breaks exactly in the case of multiple arcs having the same head, tail and label, or in other words, when dealing with Multi-Digraphs.

Maybe this happens in other functions too, where Multi-Digraphs have not been taken into account.

Either I get around to push this fix after reading how to do it on the homepage, but feel free to do it before me, I would be very thankful!

comment:5 Changed 3 years ago by David Coudert

Authors: David Coudert
Branch: public/graphs/28837_flow_polytope
Commit: c39fbe31e100ed62f8b4ac0c750479d63d949d95
Status: newneeds_review

We cannot use j is u as

sage: edges = [(0, 1), (0, 1)]
sage: [[Integer(j is u) for j in edges] for u in edges]
[[1, 1], [1, 1]]

but we have a simpler and more efficient solution, as we only need a diagonal of 1's.

Is the following behavior we get with this patch also ok ?

sage: G = DiGraph([(0, 1, None)], multiedges=False)
sage: P = G.flow_polytope(edges=[(0, 1, None), (0, 1, None)])
sage: P
A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices
sage: P.vertices()
(A vertex at (1, 0), A vertex at (0, 1))
sage: P.lines()
[]

New commits:

c39fbe3trac #28837: fix flow polytope for digraphs with multiedges

comment:6 in reply to:  5 Changed 3 years ago by Jonas Frede

Replying to dcoudert:

We cannot use j is u as

sage: edges = [(0, 1), (0, 1)]
sage: [[Integer(j is u) for j in edges] for u in edges]
[[1, 1], [1, 1]]

Weird, this does not happen with my installation of sage (8.9 from 2019-09-29, using python 2.7.17):

sage: edges = [(0, 1), (0, 1)]
sage: [[Integer(j is u) for j in edges] for u in edges]
[[1, 0], [0, 1]]

but we have a simpler and more efficient solution, as we only need a diagonal of 1's.

You're right, that's all we need. I refrained from thinking about range because of the impending change to python 3, but its use is probably correct and suitable here, even more so after the change.

comment:7 in reply to:  5 Changed 3 years ago by Jonas Frede

In the commit you attached, the docstring is changed accordingly:

If not specified, the list of all edges of self is used with the default ordering of self.edges().

Just to make you aware of it, the ordering of edges in flow_polytope is not the default ordering of self.edges() (at least not in my case), but instead an explicitly unordered list:

if edges is None:
    edges = self.edges(sort=False)

This for me gives another ordering than self.edges() when called, which in my case is equal to

self.edges(sort=True)

This relates to #22349, where you have expertise. How to best write the docstring I don't know.

comment:8 Changed 3 years ago by git

Commit: c39fbe31e100ed62f8b4ac0c750479d63d949d955af44625a95f04be2b0eb0c85a4942804820ee6d

Branch pushed to git repo; I updated commit sha1. New commits:

5af4462trac #28837: fix doctest

comment:9 Changed 3 years ago by David Coudert

Well, we are currently finalizing the transition to Python 3. I'm working with version 9.0.beta9 and it is compiled with Python 3. Plus, our goal is to deprecate sorting edges by default. Most algorithms in the graph module are now working independently of the edge ordering. So I would prefer to avoid sorting, unless it creates a doctest error, which should not be the case here.

I don't have this [[1, 1], [1, 1]] anymore. I have certainly done something weird this morning. Anyway, the solution I proposed with range should be way faster.

I pushed a small correction of the doctest.

comment:10 in reply to:  9 Changed 3 years ago by Jonas Frede

Replying to dcoudert:

Well, we are currently finalizing the transition to Python 3. I'm working with version 9.0.beta9 and it is compiled with Python 3. Plus, our goal is to deprecate sorting edges by default. Most algorithms in the graph module are now working independently of the edge ordering. So I would prefer to avoid sorting, unless it creates a doctest error, which should not be the case here.

Ah, thanks for the information. By default, the output of self.edges() will always be the same as self.edges(sort=False) as soon as this deprecation process is completed? Then the docstring of flow_polytope is fine as is now, as far as I'm concerned.

I don't have this [[1, 1], [1, 1]] anymore. I have certainly done something weird this morning. Anyway, the solution I proposed with range should be way faster.

Great to see we're on the same page again, but I agree with you on the range solution. Thanks for everything.

comment:11 Changed 3 years ago by David Coudert

If you agree with this patch, you can set it to positive review (after review and test). If you are not confident with that, we can certainly ask for help.

comment:12 Changed 3 years ago by Jonas Frede

Status: needs_reviewpositive_review

comment:13 Changed 3 years ago by Volker Braun

Status: positive_reviewneeds_work

Reviewer name is missing

comment:14 Changed 3 years ago by Jonas Frede

Reviewers: Jonas Frede
Status: needs_workpositive_review

comment:15 Changed 3 years ago by Volker Braun

Branch: public/graphs/28837_flow_polytope5af44625a95f04be2b0eb0c85a4942804820ee6d
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.