#15632: improving subgraph search
----------------------------+----------------------------
Reporter: azi | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.1
Component: graph theory | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
----------------------------+----------------------------
Hello!
I recently needed to decide whether some large graphs contain the Petersen
graph P. As it turned out the task was time consuming since almost none of
the graphs contained P.
My original graphs had many vertices of degree 1 and 2 but apparently
subgraph_search does not make use of this. The above optimization was a
big improvement for this scenario
{{{
def subgraph_search_wrapper(G, H):
G2 = G.copy()
d = min(H.degree())
while min(G2.degree()) < d:
G2.delete_vertices([v for v in G2 if G2.degree(v) < c])
return G2.subgraph_search(H)
}}}
as an example
{{{
sage: %timeit G.subgraph_search(H)
1 loops, best of 3: 41.9 s per loop
sage: %timeit subgraph_search_wrapper(G, H)
10 loops, best of 3: 78 ms per loop
}}}
While I think the above optimization is valid I believe there has to be a
more proper way to implement it (perhaps in generic_graph.pyx?) hence I
leave this here for further discussion by you guys.
Best,
Jernej
--
Ticket URL: <http://trac.sagemath.org/ticket/15632>
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.
