Opened 6 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 6 years ago by dcoudert

You can use the k-core of G instead, with k=min(H.degree()). So the pre-processing could be like:

 k = min(H.degree())
 if k>min(G.degree()):
    cores = G.cores(with_labels=True)
    G2 = G.subgraph([u for u in cores if cores[u]>=k])
 else:
    G2 = G
 return G2.subgraph_search(H)

comment:2 Changed 6 years ago by ncohen

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: Changed 6 years ago by azi

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 6 years ago by ncohen

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: Changed 6 years ago by azi

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: Changed 6 years ago by 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 ?

Nathann

comment:7 Changed 6 years ago by ncohen

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: Changed 6 years ago by azi

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 6 years ago by ncohen

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 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:11 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:12 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.