Special has_minor() routines in case both original matroid and minor are binary.

[dc979ce0-b8e8-485c-a50f-8cf6079a5d30]

Use pattern matching inspired by Hliněný's MACEK to test if a binary matroid has another binary matroid as a minor. Given a binary matroid, for each basis one can produce a matrix representation. We then look for a deletion set, a contraction set and a row-column permutation that yields a submatrix same as the representation of the given minor to be tested.

CC: @sagetrac-Stefan @sagetrac-Rudi

Component: matroid theory

Keywords: binary matroid, minor

Author: Jayant

Branch/Commit: u/Stefan/ticket/16545 @ 0abf885

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

[dc979ce0-b8e8-485c-a50f-8cf6079a5d30]

New commits:

da0a0f6

Added (not yet finished) method _has_binary_minor() to BinaryMatroid class.

[dc979ce0-b8e8-485c-a50f-8cf6079a5d30]

Commit: da0a0f6

[dc979ce0-b8e8-485c-a50f-8cf6079a5d30]

Branch: u/Jayant/ticket/16545

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

57ab8c9

Added _fundamental_graph() procedure to BinaryMatroid class

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from da0a0f6 to 57ab8c9

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

7357882	Created a new cython extension repminor_helpers.pyx
b27e3e7	Added procedure to implement Ullman's subgraph isomorphism algorithm to repminor_helpers extension.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 57ab8c9 to b27e3e7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0e02270

Added initialization of permutation matrices based on degrees.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b27e3e7 to 0e02270

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0e02270 to 320479c

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

320479c

Added new functions tp repminor_helpers.pyx including prune() and recurse() (not completely finished).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0fd0410

Added induced subgarph isomorphism check amound other things.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 320479c to 0fd0410

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

264a347

Finished putting together Ullman's algorithm implementation. Testing, profiling, documentation and compliance to follow.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0fd0410 to 264a347

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 264a347 to d089571

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

d089571

Fixed the bug in pruning.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d089571 to 9458a50

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9458a50

Modified code to deal only with simple matroids and then check if parallel classes find mappings(Still some bugs left). Turned off profiling in lean_matrix.pyx.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

76c5308

Fixed bugs and tested correctness with random tests. ToDo: Profile and add more static typing if needed.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9458a50 to 76c5308

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c55d09a

Added functionality to test induced subgraph isomorphism for only the unique reduced representations of simple matroid corresponding to ``self``(Exploits symmetry in a sense).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 76c5308 to c55d09a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1ff2155

repminor_helpers extension is now pep8 compliant.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c55d09a to 1ff2155

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1ff2155 to 32a6c9f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

8673ca2	Added some documentation to repminor_helpers extension
32a6c9f	Added documentation (except examples) to repminor_helpers extension. Added repminor_helpers to sage.matroids.advanced.py.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0f5f1eb	Switching branch.
fb0a391	Added examples. Passing doctests for both linear_matroid.pyx and repminor_helpers.pyx.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 32a6c9f to fb0a391

[90e8124e-743e-4424-88b0-22f5ae41372b]

Changed branch from u/Jayant/ticket/16545 to u/Stefan/ticket/16545

[90e8124e-743e-4424-88b0-22f5ae41372b]

Changed commit from fb0a391 to 34a5ca0

[90e8124e-743e-4424-88b0-22f5ae41372b]

comment:18

I rebased the code on 6.5.beta1; no further changes.

---

Last 10 new commits:

33f83df	Finished putting together Ullman's algorithm implementation. Testing, profiling, documentation and compliance to follow.
969e90f	Fixed the bug in pruning.
2c8e74b	Modified code to deal only with simple matroids and then check if parallel classes find mappings(Still some bugs left). Turned off profiling in lean_matrix.pyx.
bdd95a0	Fixed bugs and tested correctness with random tests. ToDo: Profile and add more static typing if needed.
ec57474	Added functionality to test induced subgraph isomorphism for only the unique reduced representations of simple matroid corresponding to ``self``(Exploits symmetry in a sense).
baa7769	repminor_helpers extension is now pep8 compliant.
5ce33dd	Added some documentation to repminor_helpers extension
801c187	Added documentation (except examples) to repminor_helpers extension. Added repminor_helpers to sage.matroids.advanced.py.
ea0d925	Switching branch.
34a5ca0	Added examples. Passing doctests for both linear_matroid.pyx and repminor_helpers.pyx.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 34a5ca0 to 0abf885

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0abf885

Fixed bitset include path

[90e8124e-743e-4424-88b0-22f5ae41372b]

comment:20

Doesn't merge with current version; doctest coverage is lacking.