Add test if a matroid is ternary

[sagetrac-Rudi]

There is a straightforward test to see if a matroid is ternary: generate the ternary representation local to a basis, and check matroid isomorphism. Implement this algorithm. See Matroid.is_binary(), ticket #18448.

CC: @sagetrac-yomcat

Component: matroid theory

Author: Rudi Pendavingh

Branch/Commit: 032b0a0

Reviewer: Michael Welsh

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

[sagetrac-Rudi]

Branch: u/Rudi/ternary_matroid

[sagetrac-Rudi]

New commits:

b28d3b9	Ground work on ternary test
cf36955	Initial implementation
a04a1bb	Seems to work

[sagetrac-Rudi]

Author: Rudi Pendavingh

[sagetrac-Rudi]

Commit: a04a1bb

[sagetrac-git]

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

f0720af

Fixed docstring

[sagetrac-git]

Changed commit from a04a1bb to f0720af

[sagetrac-git]

Changed commit from f0720af to 3538a8f

[sagetrac-git]

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

3538a8f

Slightly more efficient shortest paths

[sagetrac-git]

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

55a4d0d

Docstring of _local_ternary_matroid now has ALGORITHM section

[sagetrac-git]

Changed commit from 3538a8f to 55a4d0d

[sagetrac-git]

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

9ed83b4

Make spanning forest, not spanning tree

[sagetrac-git]

Changed commit from 55a4d0d to 9ed83b4

[sagetrac-git]

Changed commit from 9ed83b4 to bba4ea5

[sagetrac-git]

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

bba4ea5

picking entries more efficiently

[sagetrac-git]

Changed commit from bba4ea5 to 3830bb5

[sagetrac-git]

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

3830bb5

Docstring fixes

[sagetrac-Rudi]

comment:10

All done as far as I can tell.

[sagetrac-yomcat]

comment:11

Two bits of extra whitespace, both in linear_matroid.pyx:

            :meth:`M.ternary_matroid() 

(this line, twice)

[sagetrac-git]

Changed commit from 3830bb5 to 032b0a0

[sagetrac-git]

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

032b0a0

Whitespace begone

[sagetrac-Rudi]

comment:13

Argh, I really thought they were all gone.

Needs review again.

[sagetrac-yomcat]

comment:14

Replying to @sagetrac-Rudi:

Argh, I really thought they were all gone.

If you use git trac review 18751 it gives you all of them highlighted with nasty red squares. For me at least.

Needs review again.

Happy with it. Just one question: If M is not ternary, then M.ternary_matroid() returns None, which appears to be a silent fail. Would an explicit error of some type be a better idea?

[sagetrac-Rudi]

comment:15

Replying to @sagetrac-yomcat:

Replying to @sagetrac-Rudi:

Argh, I really thought they were all gone.

If you use git trac review 18751 it gives you all of them highlighted with nasty red squares. For me at least.

Needs review again.

Happy with it. Just one question: If M is not ternary, then M.ternary_matroid() returns None, which appears to be a silent fail. Would an explicit error of some type be a better idea?

It's a matter of preference, I guess. Returning None is not a fail, it's giving information, and the docstring is quite explicit about that. If you are not certain if the matroid is ternary, you can test the output of ternary_matroid. This way, you can get the answer and the possible certificate in one fell swoop. If you just want to test, use is_ternary. Similarly, M.isomorphism(N) will also output None if the matroids are not isomorphic and is_isomorphic just performs the test.

To me, raising errors is what you do when something abnormal occurs. It is not abnormal that a matroid is not ternary.

[sagetrac-yomcat]

comment:16

Fair enough. All good now.

[tscrim]

comment:17

Reviewer name.

[sagetrac-Rudi]

Reviewer: Michael Welsh

[sagetrac-Rudi]

comment:18

Thanks for reviewing!

[vbraun]

Changed branch from u/Rudi/ternary_matroid to 032b0a0