Opened 8 years ago
Closed 6 years ago
#14654 closed enhancement (fixed)
implement flow polytopes
Reported by:  ahmorales  Owned by:  graphcomponentowner 

Priority:  minor  Milestone:  sage6.6 
Component:  graph theory  Keywords:  flow polytopes, kostant partition function, sage days 47.5 
Cc:  saliola, ncohen  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Nathann Cohen, Darij Grinberg, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  37ef5cb (Commits, GitHub, GitLab)  Commit:  37ef5cbd6aaa4bc4938f55b420c7db15933322d4 
Dependencies:  Stopgaps: 
Description
Flow polytopes (or cones) of a directed graph is a polytope formed by assigning a nonnegative flow to each of edges of the graph such that the flow is conserved on internal vertices, and there is a unit of flow entering the sources and leaving the sinks.
The faces and volume of these polytopes are of interest. Examples of these polytopes are the ChanRobbinsYuen polytope and the PitmanStanley polytope.
Implement a class for these polytopes to compute the faces and the volume (maybe using #13249 or implementing known triangulations of them).
Change History (39)
comment:1 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:2 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:3 Changed 7 years ago by
 Milestone changed from sage6.2 to sagewishlist
 Type changed from PLEASE CHANGE to enhancement
comment:4 Changed 7 years ago by
 Branch set to u/chapoton/14654
 Commit set to 33472ec876b496cd45955fa7578e20faeca1b1fc
comment:5 Changed 7 years ago by
 Cc ncohen added
 Component changed from combinatorics to graph theory
 Owner changed from sagecombinat to graphcomponentowner
 Summary changed from implement class for flow polytopes to implement flow polytopes
comment:6 followup: ↓ 9 Changed 6 years ago by
Might I suggest to put this either into a digraph class or into src/sage/geometry/polyhedron/library.py
?
comment:7 Changed 6 years ago by
Yepyep.
This should probably be a digraph method. It should also appear in polytopes.<tab>
I guess.
Nathann
comment:8 Changed 6 years ago by
(You can also write the code in geometry/polyhedron and create a fake digraph function that calls it, btw)
Also, the docstring mentions sources/sinks but the code never heard of it.
Nathann
comment:9 in reply to: ↑ 6 Changed 6 years ago by
Replying to darij:
Might I suggest to put this either into a digraph class or into
src/sage/geometry/polyhedron/library.py
?
On the other hand, beware of another src/sage/graphs/generic_graph.py
which just contains too much stuff.
Note that you can import
methods into classes just the same way as you can import
other stuff.
comment:10 Changed 6 years ago by
 Commit changed from 33472ec876b496cd45955fa7578e20faeca1b1fc to 1b57c82f1eae104a3f6675f2f08c26e529f33f68
comment:11 Changed 6 years ago by
Why import line_graph
?
comment:12 Changed 6 years ago by
(please don't create a file for a 10 lines function)
comment:13 Changed 6 years ago by
 Commit changed from 1b57c82f1eae104a3f6675f2f08c26e529f33f68 to 1cbe9656be3255a956e3fcc19ab67cb5273ab928
Branch pushed to git repo; I updated commit sha1. New commits:
1cbe965  trac #14654 inclusion into digraph.py

comment:14 followup: ↓ 15 Changed 6 years ago by
(BTW, digraph.py for some reason imports deprecation without needing it.)
comment:15 in reply to: ↑ 14 Changed 6 years ago by
(BTW, digraph.py for some reason imports deprecation without needing it.)
Oh. Well, let's remove it then. Here or somewhere else.
Nathann
comment:16 Changed 6 years ago by
 Commit changed from 1cbe9656be3255a956e3fcc19ab67cb5273ab928 to a1fa21827894719e987b1ac3e41527e92df43f68
Branch pushed to git repo; I updated commit sha1. New commits:
a1fa218  trac #14654 remove deprecation import

comment:17 Changed 6 years ago by
 Status changed from new to needs_review
I do not know how to add this as a method of polytopes
comment:18 followup: ↓ 19 Changed 6 years ago by
It seems that what appears in polytopes.<tab>
are the functions defined in sage.geometry.polyhedron.library.Polytopes
.
Also, since you changed the status to needs_review
: the documentation of DiGraph.flow_polytope
mentions a source and a sink with a nonnull flow, while the function only takes one argument, i.e. the graph.... Is that normal ? O_o
Nathann
comment:19 in reply to: ↑ 18 ; followup: ↓ 20 Changed 6 years ago by
Replying to ncohen:
It seems that what appears in
polytopes.<tab>
are the functions defined insage.geometry.polyhedron.library.Polytopes
.
Yes, but is there a way to just import the function as a method polytopes.flow_polytope
?
Also, since you changed the status to
needs_review
: the documentation ofDiGraph.flow_polytope
mentions a source and a sink with a nonnull flow, while the function only takes one argument, i.e. the graph.... Is that normal ?O_o
Well, for quiver guys like me, a source is a vertex with only outgoing edges, and a sink with only incoming edges. Maybe you give them other names. So there is no need to provide them as arguments. Of course one needs to have as many sources as sinks for the flow polytope to make sense. Every source gets an input of 1 and every sink an output of 1.
comment:20 in reply to: ↑ 19 Changed 6 years ago by
Yo !
Yes, but is there a way to just import the function as a method
polytopes.flow_polytope
?
There is, but it may be a bit awkard for in one version the function takes a graph as an argument, and in the other polytopes.flow_polytope(G)
it needs to be provided explicitly... But maybe that is not a problem.
About importing the method:
sage: class A: ....: def hey(self): ....: print self sage: A.hey(1) ... TypeError: unbound method hey() must be called with A instance as first argument (got Integer instance instead) sage: A.hey.__func__(1) 1
But I am afraid that it does not preserve the docstring...
On the other hand it is possible to take a 'normal' function and make a copy of it inside of a class. You have many functions like that at the end of graphs/graph.py
Well, for quiver guys like me, a source is a vertex with only outgoing edges, and a sink with only incoming edge. Maybe you give them other names. So there is no need to provide them as arguments. Of course one needs to have as many sources as sinks for the flow polytope to make sense. Every source gets an input of 1 and every sink an output of 1.
Oh I see O_o
Well, for graph guys like me we expect the sources to be explicitly given, like in GenericGraph.flow
.
HMmmm... Well, if you are positive that this is the standard that people who call this method would expect, could you make it a bit clearer for the graph guys ? Something like:
... and there is a unit of flow entering the sources (i.e. vertices of indegree 0) and leaving the sinks (i.e. vertices of outdegree 0)
The point is that I would understand if you talk about "the sinks/sources of a graph", but in the context of flow problem we expect the sources/sinks to be specific vertices. Could you also add a sentence about the necessity to have as many sinks as sources ?
Thaaaaaaanks and sorry for that ! Different people, different standards ^^;
Nathann
comment:21 Changed 6 years ago by
 Commit changed from a1fa21827894719e987b1ac3e41527e92df43f68 to f0309ebc481de9b3cffda40807197c9390615ff8
Branch pushed to git repo; I updated commit sha1. New commits:
f0309eb  trac #14654 reviewer's comments

comment:22 Changed 6 years ago by
comment:23 Changed 6 years ago by
Helloooooo !
Sorry for having delayed this patch for so long. I am about to leave for a couple of months and I had a lot of things to attend to T_T
I found a way to make this polytopes.<tab>
thing work. Wasn't that hard after all. I also merged the branch with the latest release.
It seems all good to go, still I have one question: from the way your code is written, a digraph obtained from "any digraph + an isolated vertex" has an empty flow polyhedron. I don't think that it is the expected behaviour, but might it be what you want for your applications ?
Nathann
(the additional commits are to be found at public/14654)
comment:24 Changed 6 years ago by
 Commit changed from f0309ebc481de9b3cffda40807197c9390615ff8 to d74ca66ad183162f85ea4479810ba5909cbeec19
comment:25 Changed 6 years ago by
Thanks a lot, Nathann, for all the time you spend on my tickets.
I have made a modification that takes care of isolated points by considering them as both sources and sinks, and so letting a flow of 1 silently going through them.
comment:26 Changed 6 years ago by
Hmm. I don't like the idea that the sources and the sinks are inferred. I'd prefer to have the user provide them (and letting the code infer them only if so required), as I can see myself applying such a method for various sinksource configurations on a single graph, and it looks strange to build a new graph every time.
(I was planning to make these changes myself soon enough, once I'm done with GelfandTsetlin and BerensteinZelevinsky polytopes, but I caught something last week and now all I'm swamped with work.)
comment:27 Changed 6 years ago by
.......soooooooooooo ???
Nathann
comment:28 Changed 6 years ago by
Darij ? Do you have any plans to implement the change you mentionned ? You left your comment 7 weeks ago and this ticket is "on hold" since...
Nathann
comment:29 Changed 6 years ago by
OOPS, please don't regard my comments as blockers! I indeed wanted to do changes, but then I noticed that the polytopes class doesn't work the way I want it to and all these changes have to wait for my other patch, which has to wait for my endofterm work... so this might take some time. Meanwhile, feel free to review and merge this patch  whatever I want to change I will change later with my BZ polytopes patch.
comment:30 Changed 6 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
Okay, then let it get in. And you are welcome to make those source/sinks explicit, it also feels more natural to me ;)
Cheers,
Nathann
comment:31 Changed 6 years ago by
 Branch changed from u/chapoton/14654 to u/tscrim/flow_polytopes14654
 Commit changed from d74ca66ad183162f85ea4479810ba5909cbeec19 to 703016840815038fe79b466d67bb297a8fd43042
 Milestone changed from sagewishlist to sage6.5
comment:32 Changed 6 years ago by
 Status changed from positive_review to needs_work
File "src/sage/combinat/cluster_algebra_quiver/quiver.py", line 162, in sage.combinat.cluster_algebra_quiver.quiver.ClusterQuiver Failed example: Q = ClusterQuiver([[1,1]]) Expected: Traceback (most recent call last): ... ValueError: The input DiGraph contains a loop Got: <BLANKLINE> Traceback (most recent call last): File "/mnt/disk/home/release/Sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 488, in _run self.compile_and_execute(example, compiler, test.globs) File "/mnt/disk/home/release/Sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 850, in compile_and_execute exec(compiled, globs) File "<doctest sage.combinat.cluster_algebra_quiver.quiver.ClusterQuiver[37]>", line 1, in <module> Q = ClusterQuiver([[Integer(1),Integer(1)]]) File "sage/misc/lazy_import.pyx", line 383, in sage.misc.lazy_import.LazyImport.__call__ (build/cythonized/sage/misc/lazy_import.c:3398) return self._get_object()(*args, **kwds) File "/mnt/disk/home/release/Sage/local/lib/python2.7/sitepackages/sage/combinat/cluster_algebra_quiver/quiver.py", line 342, in __init__ dg = DiGraph( data ) File "/mnt/disk/home/release/Sage/local/lib/python2.7/sitepackages/sage/graphs/digraph.py", line 716, in __init__ deprecation(15706, "You created a graph with loops from a list. "+ NameError: global name 'deprecation' is not defined ********************************************************************** 1 item had failures: 2 of 41 in sage.combinat.cluster_algebra_quiver.quiver.ClusterQuiver [227 tests, 2 failures, 2.01 s]  sage t warnlong 38.5 src/sage/combinat/cluster_algebra_quiver/quiver.py # 2 doctests failed
comment:33 Changed 6 years ago by
 Branch changed from u/tscrim/flow_polytopes14654 to u/darij/flow_polytopes14654
 Commit changed from 703016840815038fe79b466d67bb297a8fd43042 to 187d1d8a216d763ae4c3af3ce5c4f449d5720c74
 Status changed from needs_work to needs_review
comment:34 Changed 6 years ago by
Sorry guys, just added some more complexity. I do not particularly trust self.edges()
to be consistent, let alone reasonable, about the order in which it outputs edges. And sources and sinks are now specifiable by the user.
comment:35 Changed 6 years ago by
 Branch changed from u/darij/flow_polytopes14654 to u/chapoton/14654
 Commit changed from 187d1d8a216d763ae4c3af3ce5c4f449d5720c74 to 37ef5cbd6aaa4bc4938f55b420c7db15933322d4
Ok, I have just added the word "optional" in a few places. I would have prefered more simplicity, but nevertheless this seems to be good to go. If somebody else agrees, please set it to positive review.
New commits:
586cf13  Merge branch 'u/darij/flow_polytopes14654' into 6.6.b2

37ef5cb  trac #14654 make more clear that ends and edges are optional in flow_polytope

comment:36 Changed 6 years ago by
I definitely agree with your "optional"s  they can never hurt. Does this mean I should set the ticket to positive_review?
comment:37 Changed 6 years ago by
 Reviewers changed from Nathann Cohen to Nathann Cohen, Darij Grinberg, Travis Scrimshaw
 Status changed from needs_review to positive_review
In short, yes (although I've just done it :P).
comment:38 Changed 6 years ago by
 Milestone changed from sage6.5 to sage6.6
comment:39 Changed 6 years ago by
 Branch changed from u/chapoton/14654 to 37ef5cbd6aaa4bc4938f55b420c7db15933322d4
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #14654 compute the flow polytope of a digraph