improving subgraph search

[ca0b67cc-9d10-44c6-be51-5d9e2cdee96a]

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

CC: @nathanncohen @lobiCode @dcoudert

Component: graph theory

Issue created by migration from https://trac.sagemath.org/ticket/15632

[dcoudert]

comment:1

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)

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:2

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

[ca0b67cc-9d10-44c6-be51-5d9e2cdee96a]

comment:3

Hey!

Allowed to by whom? :)))

For the #14589 thing if nobody helps you within a week I'm gonna review it.

Best,

Jernej

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:4

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

[ca0b67cc-9d10-44c6-be51-5d9e2cdee96a]

comment:5

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:6

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:7

I am afraid of calling .subgraph to remove just one or two vertices, in a function that must be fast...

Nathann

[ca0b67cc-9d10-44c6-be51-5d9e2cdee96a]

comment:8

Replying to @nathanncohen:

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:9

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