graph subgraph_search does not return copy of subgraph

[jasongrout]

Consider this example:

sage: k3=graphs.CompleteGraph(3)
sage: p3=graphs.PathGraph(3)
sage: s=k3.subgraph_search(p3)
sage: s.size()
3
sage: s==k3
True

The docs say that s should be a copy of p3. The problem is that subgraph_search returns an induced subgraph of the bigger graph with the vertices of the copy of the smaller graph.

apply: attachment: trac-12164-subgraph_search.patch

CC: @nathanncohen @sagetrac-brunellus

Component: graph theory

Author: Jason Grout

Reviewer: Nathann Cohen

Merged: sage-4.8.alpha5

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

[jasongrout]

comment:2

Steve Butler suggests that instead, we copy the smaller graph and relabel the vertices appropriately, using the vertices returned from SubgraphSearch. I like that solution. But it won't quite work to do that, since a subgraph of a graph inherits lots of properties, like a name, etc.

So instead, this patch just creates a subgraph where the vertices and the edges are specified. Before, just the vertices were specified, so you ended up getting an induced subgraph, even if the subgraph was not an induced subgraph.

[jasongrout]

Author: Jason Grout

[nathanncohen]

comment:6

Hellooooooo !! First, I'm glad to see somebody's using that function ! It needs to be totally rewritten anyway, as we now have.... Cython iterators ! O_O

So the whole class has become useless. This being said, what you are doing is much more urgent. Could I ask for a small "if induced" before those lines, so that the graph is copied/relabeled only if it is necessary ? :-)

Nathann

[jasongrout]

comment:7

Attachment: trac-12164-subgraph_search.patch.gz

Done. I also added a few more tests to the documentation (one of which would have caught this error originally---looking for the non-induced P_5_ in the petersen graph.

[nathanncohen]

comment:8

Then it's good to go ! All tests pass, and there is just nothing to add :-)

Nathann

[jdemeyer]

Reviewer: Nathann Cohen

[jdemeyer]

Merged: sage-4.8.alpha5