Extend SubgraphSearch class

[videlec]

In ask-sagemath.org (question 133) one asked the following question. Given a collection of sets how do I find a subcollection with prescribed intersections cardinality between its members. The natural way to do this is through a subgraph search but the current implementation does not allow that problem to be solved.

The patch reimplement the main method of the class SubgraphSearch adding options that allow to solve the abolve problem. An instance of the above problem is written in the documentation of sage.graphs.generic_graph.search_subgraph method.

CC: @nathanncohen

Component: graph theory

Keywords: subgraph, search, subsets

Author: Vincent Delecroix

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

[videlec]

comment:1

Attachment: trac_13280-subgraph_search.patch.gz

Hi there,

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?

Vincent

[nathanncohen]

comment:2

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