Fix (Di)Graph incidence matrix

[videlec]

The incidence matrix of a graph is according to wikipedia:

• a matrix with 0, 1 and 2 if the graph is not oriented
• a matrix with 0, 1 and -1 if the graph is oriented
  And in the oriented case the column corresponding to a loop must be zero (in order for m * m.transpose() to be equal to the Kirchhoff matrix).

We keep the default of returning an oriented incidence matrix but add a keyword oriented in order to use the other convention.

This ticket comes from a question from David Joyner on this sage-support thread.

CC: @nathanncohen

Component: graph theory

Author: Vincent Delecroix

Branch/Commit: 7e0330b

Reviewer: Nathann Cohen

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

[videlec]

Branch: u/vdelecroix/18440

[sagetrac-git]

Commit: 6c5c67b

[sagetrac-git]

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

0824ca6	Add is_projective_plane to incidence_structure
6c5c67b	Trac #18440: fix (Di)Graph incidence matrix

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ce97fc8

Trac #18440: fix (Di)Graph incidence matrix

[sagetrac-git]

Changed commit from 6c5c67b to ce97fc8

[nathanncohen]

comment:6

Hellooooooo ! I do not understand the purpose of your 'oriented' argument. You are right that the current function is wrong in what it does, i.e. orient arbitrarily the edges of an undirected graph in order to have a -1,0,+1 matrix: why would you want to "keep this feature"?

To me it does not make much sense. We could just define this parameter from the value of self.is_directed. Also, but that's only a typo, the documentation of 'oriented' says that it can make the matrix 'oriented' or ... 'oriented'. Could you say somewhere that '2' only happens in the presence of loops? Real graphs don't have loops :-P

Thaaaaaaaaaanks,

Nathann

[videlec]

comment:8

Replying to @nathanncohen:

Hellooooooo ! I do not understand the purpose of your 'oriented' argument.

It seems that people are mostly interested in the oriented version, which needs an oriented graph. The reason is that

m * m.transpose() == m.kirckhhoff_matrix()

and this is true for oriented graph (even multiedges with loops with my branch ;-).

You are right that the current function is wrong in what it does, i.e. orient arbitrarily the edges of an undirected graph in order to have a -1,0,+1 matrix: why would you want to "keep this feature"?

I do not want to. It seems to be what people expect. I am 100% in favor of making the default unoriented for graphs but then we should find a simple solution to obtain the oriented version. Do you think that the following is simple enough

sage: G.to_directed().incidence_matrix()

To me it does not make much sense. We could just define this parameter from the value of self.is_directed. Also, but that's only a typo, the documentation of 'oriented' says that it can make the matrix 'oriented' or ... 'oriented'. Could you say somewhere that '2' only happens in the presence of loops?

Ha true true.

Real graphs don't have loops :-P

Ha right. I always forgot that I am not doing graph theory with my graph with one vertex and three edges ;-)

Vincent

[nathanncohen]

comment:9

It seems that people are mostly interested in the oriented version

"What's wrong with these people?"

I do not want to. It seems to be what people expect. I am 100% in favor of making the default unoriented for graphs but then we should find a simple solution to obtain the oriented version.

So why don't we do that? Guys who want to force an oriented version will only have to change the flag, won't they?

Do you think that the following is simple enough

sage: G.to_directed().incidence_matrix()

This doubles the number of edges. It is not an arbitrary orientation, it replaces every undirected edge with a 2-cycle.

Either way, could you say in the docstring that forcing an oriented graph will result in "some arbitrary orientation" to be picked?

Ha right. I always forgot that I am not doing graph theory with my graph with one vertex and three edges ;-)

Of course not.

Nathann

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

0b309a1	Trac #18440: fix (Di)Graph incidence matrix
59a365a	Trac #18440: default ordering given by the graph

[sagetrac-git]

Changed commit from ce97fc8 to 59a365a

[videlec]

comment:11

Hello,

Rebased on 6.8.beta0 + new commit for a coherent default ordering.

Vincent

[nathanncohen]

comment:12

Helloooooo !

I added a small commit at public/18440 with superficial changes. And I have
three remarks:

• You say in the documentation of incidence_matrix that a digraph cannot be
  recovered from its incidence matrix, which sounds rather unexpected for
  someone like me. That's the usual problem again: for me (and many others) a
  digraph is simple unless stated otherwise. Could you say that 'it is not
  possible to recover the loops of a digraph from its incidence matrix' instead?

• Documentation of oriented in the INPUT section: you do not exactly specify what the default behaviour is. It is implicitly done in the paragraphs before the 'INPUT' section. Could you say (unless you find something better) that when equal to None` it is inferred from the graph's type?

• It is a bit weird that an error is reported when loops=False but a loops is
  present in the matrix, while multiple edges are silently ignored when
  multiedges=False. I we stick to the behaviour of add_edge those edges should
  be silently ignored (and with deprecation Graph built from their edges are simple by default #15706 that should be the standard
  some day). What about doing the same here?

• Could you doctest the new exceptions you added?

Thanks,

Nathann

[nathanncohen]

Reviewer: Nathann Cohen

[videlec]

Changed commit from 59a365a to 1543608

[videlec]

comment:13

Thanks for your commit.

I took care of your three remarks in an additional commit.

Vincent

---

New commits:

b656a4c	trac #18440: Changes in exception messages, some missing spaces, ...
1543608	Trac #18440: more doctest + silently ignore loops when loops=False

[videlec]

Changed branch from u/vdelecroix/18440 to public/18440

[nathanncohen]

comment:14

Thanks !

Well, it looks good to me but the patchbot indicates a broken doctest in the matroid/ folder.

Nathann

[videlec]

comment:15

Replying to @nathanncohen:

Thanks !

Well, it looks good to me but the patchbot indicates a broken doctest in the matroid/ folder.

Damn!

[sagetrac-git]

Changed commit from 1543608 to 9b30b92

[sagetrac-git]

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

9b30b92

Trac #18440: fix the doctest in matroids

[nathanncohen]

comment:17

Theeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeen,

Nathann

[vbraun]

comment:18

PDF docs don't build

[videlec]

comment:19

Because of this ticket?!!?

[vbraun]

comment:20

{-1,0,1\}

[videlec]

comment:21

;-) Thanks!

[sagetrac-git]

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

7e0330b

Trac #18440: fix documentation

[sagetrac-git]

Changed commit from 9b30b92 to 7e0330b

[vbraun]

Changed branch from public/18440 to 7e0330b