Opened 5 years ago
Last modified 5 years ago
#15632 new enhancement
improving subgraph search
Reported by: | azi | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | graph theory | Keywords: | |
Cc: | ncohen, slani, dcoudert | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
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
Change History (12)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
Hellooooooo !
David's suggestion is the right one for your problem.
I have to add that I would be glad to improve some algorithms in Sage, but that I can only do this if I am allowed to. In particular, it would be quite nice if somebody could review #14589, for it *can* definitely help to improve the performances of algorithms like subgraph_search
.
Nathann
comment:3 follow-up: ↓ 4 Changed 5 years ago by
Hey!
Allowed to by whom? :)))
For the #14589 thing if nobody helps you within a week I'm gonna review it.
Best,
Jernej
comment:4 in reply to: ↑ 3 Changed 5 years ago by
Yooooooo !
Allowed to by whom? :)))
By whoever reviews that patch :-P
For the #14589 thing if nobody helps you within a week I'm gonna review it.
Well... Nobody did for 8 months. Would you be willing to bet ? :-P
Nathann
comment:5 follow-up: ↓ 6 Changed 5 years ago by
Now you can tell me if you wish we include this preprocesing thing or you see a better way to improve subgraph search altogether?
Best,
Jernej
comment:6 in reply to: ↑ 5 ; follow-up: ↓ 8 Changed 5 years ago by
Yoooooo !
Now you can tell me if you wish we include this preprocesing thing or you see a better way to improve subgraph search altogether?
Well, it would definitely be cool to have this available through a flag in subgraph_search*
. Do you think it should be the default behaviour ?
Nathann
comment:7 Changed 5 years ago by
I am afraid of calling .subgraph
to remove just one or two vertices, in a function that must be fast...
Nathann
comment:8 in reply to: ↑ 6 ; follow-up: ↓ 9 Changed 5 years ago by
Replying to ncohen:
Yoooooo !
Now you can tell me if you wish we include this preprocesing thing or you see a better way to improve subgraph search altogether?
Well, it would definitely be cool to have this available through a flag in
subgraph_search*
. Do you think it should be the default behaviour ?
The answer to this most likely depends on the average structure of input graphs which we do not know anything about. Hence its definitely something that the user should know. So yeah, a preprocessing flag looks like a good option, though I am not sure we lose that much performance by always doing the preprocesing phase.
Nathann
comment:9 in reply to: ↑ 8 Changed 5 years ago by
though I am not sure we lose that much performance by always doing the preprocesing phase.
I have no idea. I am just scared of .subgraph
:-P
Nathann
comment:10 Changed 5 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:11 Changed 5 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:12 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
You can use the k-core of G instead, with k=min(H.degree()). So the pre-processing could be like: