directed graph from polyhedron

[fchapoton]

This ticket proposes to implement a method taking a polyhedron and a linear form
and returning the directed graph made of vertices and edges of the polyhedron, oriented using the linear form.

Component: geometry

Keywords: polyhedron, digraph

Author: Frédéric Chapoton

Branch/Commit: 6c9f537

Reviewer: Thierry Monteil

Issue created by migration from https://trac.sagemath.org/ticket/17474

[fchapoton]

Branch: u/chapoton/17474

[fchapoton]

Commit: fa984b9

[fchapoton]

New commits:

fa984b9

trac #17xxx adding a method vertex_digraph to polyhedra

[videlec]

comment:2

Hello,

Why is it a cached method?

Vincent

[fchapoton]

comment:3

Well, vertex_graph is cached, so I just did the same. But if you prefer not, no problem.

[videlec]

comment:4

The thing is that caching costs (in memory) and these methods do not (in time). So I really do not see the point. Do you agree to also "uncache" the vertex_graph method?

I think that in most cases, the use of cached method is dirty programming (though it is very cool in development phase).

Vincent

[sagetrac-git]

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

dcf5264

trac #17474 removed 2 cached_method and two unused imports

[sagetrac-git]

Changed commit from fa984b9 to dcf5264

[sagetrac-tmonteil]

comment:6

In your implementation, there is no oriented edge associated to an edge of the polyhedron that belongs to the kernel of the linear form, hence the underlying undirected graph of your graph is only a subgraph of vertices and edges of the polyhedron, see for example:

sage: penta = Polyhedron([[0,0],[1,0],[0,1],[1,2],[3,2]])
sage: penta.vertex_digraph(vector([1,0]))

What is the purpose of this method ? Depending on this, the described behaviour may cause troubles. Other possibilities is to have two oriented edges facing eachother (just replace > 0 by >= 0), or choosing one (but you lose some symmetry).

[sagetrac-tmonteil]

comment:7

One could also want to provide a genuine linear form (see linear_transformation() function) as an input, instead of a vector (this could be useful in (possible future) case the underlying vector space is not euclidean).

Also, it seems not very natural that the edges of the graph go in the decreasing direction of the linear form (note that v-w is the vector that goes from w to v, hence if an oriented edge e of the polyhedron is viewed as a vector, it is selected if f(e)<0), but perhaps it makes sense in the use case (it looks weird from an optimization perspective such as simplex method (note that Sage's MILP maximizes by default)).

[sagetrac-git]

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

f0e479b

trac #17474 adding an increasing option to digraph of polytope

[sagetrac-git]

Changed commit from dcf5264 to f0e479b

[sagetrac-git]

Changed commit from f0e479b to 97083e9

[sagetrac-git]

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

97083e9

trac #17474 typos

[sagetrac-git]

Changed commit from 97083e9 to 887a2d1

[sagetrac-git]

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

887a2d1

trac #17474 another TAB removal

[sagetrac-git]

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

37a6f28

trac #17474 adding double edges when non-generic form

[sagetrac-git]

Changed commit from 887a2d1 to 37a6f28

[fchapoton]

comment:12

I am always using this with generic linear forms where every edge is not parallel to the kernel of the form. I then turn the digraphs into posets. Anyway, I have replaced > by >= so that doubled edges are added when this happen. This will raise an error when I use the Poset constructor, so I am happy with that.

I have also added a keyword to ask for the reverse orientation.

How can I check if the input is a linear form ?

[sagetrac-tmonteil]

Changed branch from u/chapoton/17474 to u/tmonteil/17474

[sagetrac-tmonteil]

Changed commit from 37a6f28 to 5878286

[sagetrac-tmonteil]

comment:14

Replying to @fchapoton:

How can I check if the input is a linear form ?

I uploaded a patch that checks if the input is an instance of VectorSpaceMorphism whose codomain has dimension 1.

I removed from the doc the possibility to input a list or a tuple since it was not working in the previous version (it is doable to try/except f = vector(f) but i am not sure we have to think for the user).

I have also added a keyword to ask for the reverse orientation.

It works well. Do you have some important reason to go in the decreasing direction by default ? If not, i would prefer to have it the other way by default, to be consistent with the MILP default, but perhaps i miss some other use case.

---

New commits:

5878286

#17474 allow genuine linear forms as input

[fchapoton]

Changed branch from u/tmonteil/17474 to u/chapoton/17474

[fchapoton]

comment:15

ok, thanks.

I have made it increasing by default, as you seem to prefer it so.

I have added a test to check that the orientation is correct.

I have also removed an usused import and made two minor pep8 changes.

---

New commits:

e1b06a2	Merge branch 'u/tmonteil/17474' of ssh://trac.sagemath.org:22/sage into 6.5.b4
6c9f537	trac #17474 increasing by default, plus one removed import, two pep8 changes

[fchapoton]

Changed commit from 5878286 to 6c9f537

[sagetrac-tmonteil]

comment:17

It looks good to me. Thanks.

[sagetrac-tmonteil]

Reviewer: Thierry Monteil

[vbraun]

Changed branch from u/chapoton/17474 to 6c9f537