#10482: Add Weisfeiler-Leman algorithm to sage.graphs
-------------------------------------+-------------------------------------
Reporter: kini | Owner: kini
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.13
Component: graph theory | Resolution:
Keywords: weisfeiler-leman | Merged in:
algorithm, graphs, coherent | Reviewers:
configurations, refinement | Work issues: fix the bug with wl-
Authors: Keshav Kini | bug example
Report Upstream: N/A | Commit:
Branch: | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by dimpase):
Replying to [comment:12 kini]:
> I'm not sure what to do with this now. As I recall, I did try stepping
carefully through the code back in 2011, and it was doing what I expected
it to do, and as far as I could tell it also matched what's written in the
paper I based the code on. Yet the answer is wrong for the `wl-bug` case.
The strategy for debugging is obvious: what happens, mathematically, is
that a basis of 0-1 matrices for a matrix algebra is built incrementally.
One just has to trace this carefully: at some point instead of creating a
minimal 0-1 basis, the procedure breaks.
This might need a bit of extra code, allowing outputting the current basis
in some "dumb" machine-readable form at any iteration. Then you can
compare what happens in the implementation (it computes the product A_i
A_j of two (presumed-)basis elements {A_k}, each of them represented as a
linked list, and tries to decompose it into a Z-linear combination of the
A_k's. When it fails, this means that it has to locate an A_k that needs
to be spit into a number of 0-1 matrices, do this splitting, etc).
--
Ticket URL: <http://trac.sagemath.org/ticket/10482#comment:13>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
