#11736: Linear time implementation of lex_BFS()
-------------------------+-------------------------------------------------
Reporter: | Owner: jason, ncohen, rlm
ddestrada | Status: needs_info
Type: | Milestone: sage-6.4
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
lexbfs | 588c43140644c9d43cfae2e27e116566eda9ac54
Authors: | Stopgaps:
Report Upstream: N/A |
Branch: |
public/11736 |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by dcoudert):
* status: needs_work => needs_info
Comment:
Hello,
This patch has been sleeping for very very long time.
I did a first git version of the patch with some corrections. This is far
from final version and we have currently 2 implementations to ease tests.
To use the new version, you need to set parameter `new_version=True`.
Since the code has no comments, it is hard to know whats going on. I have
corrected at least one bug (a missing `j = l`), but I have the following
issue:
{{{
sage: g =
graphs.PathGraph(3).lexicographic_product(graphs.CompleteGraph(2))
sage: g.lex_BFS(reverse=True)
[(2, 1), (2, 0), (1, 1), (1, 0), (0, 1), (0, 0)]
sage: g.lex_BFS(reverse=True, new_version=True)
[(2, 1), (2, 0), (1, 1), (1, 0), (0, 1), (0, 0)]
sage: g.lex_BFS(reverse=False)
[(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]
sage: g.lex_BFS(reverse=False, new_version=True)
[(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]
}}}
The new version is more consistant (and also way faster). Furthermore, on
this example, both reverse orderings are correct.
However, when making the new version the default one, many tests for
`is_chordal` and `is_interval` are broken.
Any help is welcome.
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/11736#comment:22>
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/d/optout.
