implement flow polytopes

[ahmorales]

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).

[chapoton]

New commits:

​33472ec

trac #14654 compute the flow polytope of a digraph

[darij]

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

[ncohen]

Yepyep.

This should probably be a digraph method. It should also appear in polytopes.<tab> I guess.

Nathann

[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

[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.

[git]

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

​e126623	Merge branch 'u/chapoton/14654' of trac.sagemath.org:sage into 14654
​1b57c82	trac #14654 flow polytope as a method of digraphs

[darij]

Why import line_graph?

[ncohen]

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

[git]

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

​1cbe965

trac #14654 inclusion into digraph.py

[darij]

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

[ncohen]

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

Oh. Well, let's remove it then. Here or somewhere else.

Nathann

[git]

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

​a1fa218

trac #14654 remove deprecation import

[chapoton]

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

[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

[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 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.

[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

[git]

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

​f0309eb

trac #14654 reviewer's comments

[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)

[git]

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

​1a5325d	trac #14654: Merged with 6.4.rc1
​11fee98	trac #14654: polytopes.<tab>
​d74ca66	trac #14654 case of isolated points (both source and sink)

[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.

[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.

[ncohen]

.......soooooooooooo ???

Nathann

[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

[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.

[ncohen]

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

[tscrim]

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

---

New commits:

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

[vbraun]

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

[darij]

New commits:

​8b3f582	reverted a merge-incompatible change
​187d1d8	customize order of edges + customize sources and sinks

[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.

[chapoton]

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_polytopes-14654' into 6.6.b2
​37ef5cb	trac #14654 make more clear that ends and edges are optional in flow_polytope

[darij]

I definitely agree with your "optional"s -- they can never hurt. Does this mean I should set the ticket to positive_review?

[tscrim]

In short, yes (although I've just done it :P).