#19077: Greatly speed up equality check of equal graphs
-------------------------------------+-------------------------------------
Reporter: novoselt | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.9
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: Andrey | Reviewers: Jori Mäntysalo
Novoseltsev | Work issues:
Report Upstream: N/A | Commit:
Branch: | 959c85d02f96b679a1bc082543359554d496eeb7
u/novoselt/graph_eq | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Old description:
> The current code goes over all vertex pairs and checks existence of all
> possible edges, which is extremely inefficient for, say, posets, whose
> graphs are far from complete. This is a big problem when mixed with
> unique representation of finite posets.
>
> So let's iterate over edges directly. Multiple edges are trickier and are
> not dealt with here.
New description:
The current code goes over all vertex pairs and checks existence of all
possible edges, which is extremely inefficient for, say, posets, whose
graphs are far from complete. This is a big problem when mixed with unique
representation of finite posets.
So let's iterate over edges directly.
--
Comment (by novoselt):
OK - no more long lists and no relying on sorting but doing it in case it
helps. I guess complexity is now like `pairs_of_connected_vertices *
number_of_labels_per_pair * log(number_of_labels_per_pair)` when there is
order and without taking log when there is not.
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=e96b20cf61f0e4e9d6405a89313045c06dc29cef
e96b20c]||{{{trac #19077: Equality test for multigraphs}}}||
||[http://git.sagemath.org/sage.git/commit/?id=959c85d02f96b679a1bc082543359554d496eeb7
959c85d]||{{{Compare labels edge by edge without relying on total
order.}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/19077#comment:18>
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.
