#13280: Extend SubgraphSearch class
----------------------------------------------------+-----------------------
Reporter: vdelecroix | Owner:
vdelecroix
Type: enhancement | Status:
needs_review
Priority: major | Milestone: sage-5.3
Component: graph theory | Resolution:
Keywords: graph, subgraph, search, subsets | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Vincent Delecroix | Merged in:
Dependencies: | Stopgaps:
----------------------------------------------------+-----------------------
Comment (by ncohen):
Hellooo Vincent !> I start the review myself! I get into trouble between
the two methods search_subgraph() and search_subgraph_iterator() as they
do not return the same objects! In particular, as I mention in the
documentation (the patch has to be changed for that), in the method
search_subgraph() there is no way to get the map Vertex(H) -> Vertex(G).
What can I do? An option return_map like for isomorphism test?
Oh, there is a way to get it back ! When you call H.vertices() you are
given a list of H's vertices, and when you iterate over the subgraphs of G
isomorphic to H you get a list of lists.
So if H.vertices() yields [5, 2, 3, 4, 6] and one of the elements of the
list of lists is [50, 30, 15, 66, 88], then it means that the map you are
looking for is :
5 > 50
2 > 30
15 > 3
66 > 4
88 > 6
I cannot give you an example right now as I do not have Sage installed on
my computer (and sagenb.org is sloooooooooooooooooooooooooooooow), but
that's how it should work `:-)`
Nathann
P.S. : Oh, and even though I agree that the DenseGraph should be
rewritten, an integer on a 64-bits machine still uses 64 times more space
than a bit, and is slower. Ideally some class should be created that does
with dense graphs what "static sparce graphs" [1] does for sparse graphs,
so that there is no time lost on labels when using that class.
[1]
http://www.sagemath.org/doc/reference/sage/graphs/base/static_sparse_graph.html
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13280#comment:2>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
