Opened 8 years ago

Closed 6 years ago

#14654 closed enhancement (fixed)

implement flow polytopes

Reported by: ahmorales Owned by: graphcomponentowner
Priority: minor Milestone: sage-6.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) 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 Chan-Robbins-Yuen polytope and the Pitman-Stanley 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 jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 7 years ago by chapoton

  • Milestone changed from sage-6.2 to sage-wishlist
  • Type changed from PLEASE CHANGE to enhancement

comment:4 Changed 7 years ago by chapoton

  • Branch set to u/chapoton/14654
  • Commit set to 33472ec876b496cd45955fa7578e20faeca1b1fc

New commits:

33472ectrac #14654 compute the flow polytope of a digraph

comment:5 Changed 6 years ago by chapoton

  • Cc ncohen added
  • Component changed from combinatorics to graph theory
  • Owner changed from sage-combinat to graphcomponentowner
  • Summary changed from implement class for flow polytopes to implement flow polytopes

comment:6 follow-up: Changed 6 years ago by darij

Might I suggest to put this either into a digraph class or into src/sage/geometry/polyhedron/library.py?

Last edited 6 years ago by darij (previous) (diff)

comment:7 Changed 6 years ago by ncohen

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 ncohen

(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 jdemeyer

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 git

  • Commit changed from 33472ec876b496cd45955fa7578e20faeca1b1fc to 1b57c82f1eae104a3f6675f2f08c26e529f33f68

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

e126623Merge branch 'u/chapoton/14654' of trac.sagemath.org:sage into 14654
1b57c82trac #14654 flow polytope as a method of digraphs

comment:11 Changed 6 years ago by darij

Why import line_graph?

comment:12 Changed 6 years ago by ncohen

(please don't create a file for a 10 lines function)

comment:13 Changed 6 years ago by git

  • Commit changed from 1b57c82f1eae104a3f6675f2f08c26e529f33f68 to 1cbe9656be3255a956e3fcc19ab67cb5273ab928

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

1cbe965trac #14654 inclusion into digraph.py

comment:14 follow-up: Changed 6 years ago by darij

(BTW, digraph.py for some reason imports deprecation without needing it.)

comment:15 in reply to: ↑ 14 Changed 6 years ago by ncohen

(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 git

  • Commit changed from 1cbe9656be3255a956e3fcc19ab67cb5273ab928 to a1fa21827894719e987b1ac3e41527e92df43f68

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

a1fa218trac #14654 remove deprecation import

comment:17 Changed 6 years ago by chapoton

  • Status changed from new to needs_review

I do not know how to add this as a method of polytopes

comment:18 follow-up: Changed 6 years ago by ncohen

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 non-null flow, while the function only takes one argument, i.e. the graph.... Is that normal ? O_o

Nathann

comment:19 in reply to: ↑ 18 ; follow-up: Changed 6 years ago by chapoton

Replying to ncohen:

It seems that what appears in polytopes.<tab> are the functions defined in sage.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 of DiGraph.flow_polytope mentions a source and a sink with a non-null 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 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.

Version 0, edited 6 years ago by chapoton (next)

comment:20 in reply to: ↑ 19 Changed 6 years ago by ncohen

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 git

  • Commit changed from a1fa21827894719e987b1ac3e41527e92df43f68 to f0309ebc481de9b3cffda40807197c9390615ff8

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

f0309ebtrac #14654 reviewer's comments

comment:22 Changed 6 years ago by chapoton

  • Authors changed from ahmorales to Frédéric Chapoton

comment:23 Changed 6 years ago by ncohen

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 git

  • Commit changed from f0309ebc481de9b3cffda40807197c9390615ff8 to d74ca66ad183162f85ea4479810ba5909cbeec19

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

1a5325dtrac #14654: Merged with 6.4.rc1
11fee98trac #14654: polytopes.<tab>
d74ca66trac #14654 case of isolated points (both source and sink)

comment:25 Changed 6 years ago by chapoton

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 darij

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 sink-source 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 Gelfand-Tsetlin and Berenstein-Zelevinsky polytopes, but I caught something last week and now all I'm swamped with work.)

Last edited 6 years ago by darij (previous) (diff)

comment:27 Changed 6 years ago by ncohen

.......soooooooooooo ???

Nathann

comment:28 Changed 6 years ago by ncohen

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 darij

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 end-of-term 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 ncohen

  • 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 tscrim

  • Branch changed from u/chapoton/14654 to u/tscrim/flow_polytopes-14654
  • Commit changed from d74ca66ad183162f85ea4479810ba5909cbeec19 to 703016840815038fe79b466d67bb297a8fd43042
  • Milestone changed from sage-wishlist to sage-6.5

I allowed myself to make the trivial change for speed: len(ins) == 0 to not ins.


New commits:

3aadd39Merge branch 'u/chapoton/14654' of trac.sagemath.org:sage into u/tscrim/flow_polytopes-14654
7030168Minor speedup tweak.

comment:32 Changed 6 years ago by vbraun

  • 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/site-packages/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/site-packages/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/site-packages/sage/combinat/cluster_algebra_quiver/quiver.py", line 342, in __init__
        dg = DiGraph( data )
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/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 --warn-long 38.5 src/sage/combinat/cluster_algebra_quiver/quiver.py  # 2 doctests failed

comment:33 Changed 6 years ago by darij

  • Branch changed from u/tscrim/flow_polytopes-14654 to u/darij/flow_polytopes-14654
  • Commit changed from 703016840815038fe79b466d67bb297a8fd43042 to 187d1d8a216d763ae4c3af3ce5c4f449d5720c74
  • Status changed from needs_work to needs_review

New commits:

8b3f582reverted a merge-incompatible change
187d1d8customize order of edges + customize sources and sinks

comment:34 Changed 6 years ago by darij

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 chapoton

  • Branch changed from u/darij/flow_polytopes-14654 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:

586cf13Merge branch 'u/darij/flow_polytopes-14654' into 6.6.b2
37ef5cbtrac #14654 make more clear that ends and edges are optional in flow_polytope

comment:36 Changed 6 years ago by darij

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 tscrim

  • 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 chapoton

  • Milestone changed from sage-6.5 to sage-6.6

comment:39 Changed 6 years ago by vbraun

  • Branch changed from u/chapoton/14654 to 37ef5cbd6aaa4bc4938f55b420c7db15933322d4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.