#12164: graph subgraph_search does not return copy of subgraph
----------------------------+-----------------------------------------------
Reporter: jason | Owner: jason, ncohen, rlm
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.8
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Changes (by jason):
* status: new => needs_review
Old description:
> 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.
>
> 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.
New description:
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.
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.
'''apply''': [attachment:trac-12164-subgraph_search.patch]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12164#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
