#13294: Add test for not necessarily induced subgraphs to Graph.is_subgraph()
method
-------------------------------------------+--------------------------------
Reporter: steven | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-5.3
Component: graph theory | Resolution:
Keywords: graph, induced subgraph | Work issues:
Report Upstream: N/A | Reviewers: David Coudert
Authors: Stefano Leucci | Merged in:
Dependencies: | Stopgaps:
-------------------------------------------+--------------------------------
Comment (by steven):
Hi,
thank you for your feedback. I have fixed the incorrect indentation
(whoops).
Regarding the problem that may arise when self and other are of two
different types, I think the best thing to do is just return an error and
let the user explicitly handle that situation.
For example let's assume that G is undirected and H is directed:
{{{
H.is_subgraph(G, induced=False)
}}}
raises a Value error.
{{{
H.is_subgraph(G.to_directed(), induced=False)
}}}
Tests whether H has *two* edges (u,v) and (v,u) for each of edge (u,v) in
G.
{{{
H.to_undirected().is_subgraph(G, induced=False)
}}}
Tests whether H has *at least one* edge (either (u,v) or (v,u)) for each
of edge (u,v) in G.
The only problem I see in this approach is that it might, in weird codes,
break backwards compatibility as there is no such test right now.
As for the doc tests, there was already one in place. I've added another
to test when induced=False and the method returns false. If it's not
enough or there's something else that I'm missing please let me know.
The proposed code looks something like this:
{{{
[...]
EXAMPLES::
sage: P = graphs.PetersenGraph()
sage: G = P.subgraph(range(6))
sage: G.is_subgraph(P)
True
sage: H=graphs.CycleGraph(5)
sage: G=graphs.PathGraph(5)
sage: G.is_subgraph(H)
False
sage: G.is_subgraph(H, induced=False)
True
sage: H.is_subgraph(G, induced=False)
False
"""
from sage.graphs.graph import Graph
from sage.graphs.digraph import DiGraph
if isinstance(self,Graph) and not isinstance(other,Graph):
raise ValueError('The input parameter must be a Graph.')
if isinstance(self,DiGraph) and not isinstance(other,DiGraph):
raise ValueError('The input parameter must be a DiGraph.')
if induced:
self_verts = self.vertices()
for v in self_verts:
if v not in other:
return False
return other.subgraph(self_verts) == self
else:
for v in self:
if v not in other:
return False
for e in self.edge_iterator():
if not other.has_edge(e):
return False
return True
}}}
If it looks right I'll post the updated patch file :)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13294#comment:8>
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.
