Opened 9 years ago

Last modified 7 years ago

#13280 needs_work enhancement

Extend SubgraphSearch class

Reported by: vdelecroix Owned by: vdelecroix
Priority: major Milestone: sage-6.4
Component: graph theory Keywords: graph, subgraph, search, subsets
Cc: ncohen Merged in:
Authors: Vincent Delecroix Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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.

Attachments (1)

trac_13280-subgraph_search.patch (17.4 KB) - added by vdelecroix 9 years ago.

Download all attachments as: .zip

Change History (8)

Changed 9 years ago by vdelecroix

comment:1 Changed 9 years ago by vdelecroix

  • Status changed from new to needs_review

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

comment:2 Changed 9 years ago by ncohen

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

comment:3 Changed 9 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:4 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 7 years ago by vbraun_spam

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