Graph() construction with edge function

[Rob Beezer]

The following used to work (based on regular private doctesting outside of Sage source code) and give you the path you wanted:

P9 = Graph([[0..8], lambda i,j: i-j == 1])

Now it silently produces an empty graph (9 vertices, no edges).  The fix:

P9 = Graph([[0..8], lambda i,j: i-j == -1])

Is this a bug, or does part 4 of the Graph() constructor documentation need clarification?

Rob

[Vincent Delecroix]

I would rather use

P9 = Graph([[0..8], lambda i,j: abs(i-j) == 1])

since edges have no reason to be ordered with i>j or i<j.

... but that does not answer your question of course ;-)

Vincent

[Rob Beezer]

Well, the first thing I tried was   (i-j)^2 == 1.  ;-)

Partially answering my own question, by reading the code (graphs/graph.py):

from itertools import combinations
self.add_vertices(verts)
self.add_edges(e for e in combinations(verts,2) if f(*e))
self.add_edges((v,v) for v in verts if f(v,v))

The "combinations()" iterator appears to produce unordered pairs, as you would expect (and "f" is the supplied function).

So should the "edge-detection" function be required to return true for any pair of vertices joined by an edge, or should there be an edge constructed between any pair of vertices for which the edge-detection function returns true?

I'd argue the former requires some help with the documentation, while the latter would be a change to the code/behavior.

Rob

[Nathann Cohen]

Hello,

Sorry for the change in behaviour, perhaps I should write somewhere that 'f' must be symmetric. I could do so in #19390, for it actually cleans the constructor code and their documentation.

So should the "edge-detection" function be required to return true for any pair of vertices joined by an edge, or should there be an edge constructed between any pair of vertices for which the edge-detection function returns true?

The best for me is to request that the function should be symmetric (as it is required in theory anyway: a graph is the result of a symmetric binary relation), and that anything else is "undefined behaviour". This way building a graph calls f for a total of n(n-1)/2 times (if there are no loops), and not twice that amount.

Furthermore, I wonder where that change came from. It "may" come from the graph code but really I do not see how: the constructor was patched heavily recently, but that's not in the beta yet. itertools.combinations always respected the ordering you give it: if 0 comes before 1 in the list, it will give you (0,1) (thus the -1 in your code) and not (1,0). I don't think that [0..8] ever returned [8,7,6,....,0] either. Weird.

I'd argue the former requires some help with the documentation, while the latter would be a change to the code/behavior.

I will add a "symmetric" somewhere in the doc. The amount of of guessing that the graph constructor does is already beyond sanity. Just a funny example I showed to a colleague yesterday:

{1 : [2,3], 2: [3, 4]} # we all think of the same graph, even if 2 does not name 1 as its neighbors

{1 : [2,3], 2: [3, 4]} # with multiedges=True. Same result ? What do you expect now ?

{1 : [2,3], 2: [3, 4], 3: [1]} # with multiedges=True. And now ?

{1 : [2,2], 2: [1]} # with multiedges=True. And now ? How many edges between 1 and 2 ?

More headaches in the two comments starting at: http://trac.sagemath.org/ticket/19385#comment:17

Have fuuuuuuuuuuun,

Nathann

[Jori Mäntysalo]

Quoting Nathann Cohen <nathan...@gmail.com>:

>> So should the "edge-detection" function be required to return true for any
>> pair of vertices joined by an edge, or should there be an edge constructed
>> between any pair of vertices for which the edge-detection function returns
>> true?

> The best for me is to request that the function should be symmetric (as it
> is required in theory anyway: a graph is the result of a symmetric binary
> relation), and that anything else is "undefined behaviour". This way
> building a graph calls f for a total of n(n-1)/2 times (if there are no
> loops), and not twice that amount.

Whatever. I can give reasons to do it either way...

But we should have a documented unified policy to this. As an example,
if Graph(.., f) assumes f to be symmetric without checking, then
Poset(..., f) should assume that f does not define a loop on elements
and so on.

--
Jori Mäntysalo

[Nathann Cohen]

> But we should have a documented unified policy to this. As an example, if
> Graph(.., f) assumes f to be symmetric without checking, then Poset(..., f)
> should assume that f does not define a loop on elements and so on.

Right now the Poset function does not delegate the job of building the
digraph from "vertices,f" to DiGraph but does the job itself. Could be
simplified I guess.

Nathann

[Rob Beezer]

Dear Nathann,

Yes, I think if the documentation screams "implements a symmetric relation" that would be a big improvement.  And maybe a doctest illustrating how it can go bad?

Thanks very much for looking after this one.  I am a little familiar with that constructor, I'm sure you will have fuuuuuuuuun with it.  ;-)

Rob

[Nathann Cohen]

Helloooooo,

> Yes, I think if the documentation screams "implements a symmetric relation"
> that would be a big improvement. And maybe a doctest illustrating how it
> can go bad?

I added a mention that the function should be symmetric, and just
pushed a new doctest for that:

http://git.sagemath.org/sage.git/commit/?id=3b724240f9aba068d4495b4600c3f4a9190d5043

(still on #19390)

Have fuuuuuun,

Nathann

[Rob Beezer]

Nathann - Looks great - thanks!  -Rob