#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 dcoudert):
Use the code bellow plus the tests. I did the following:
- adds a simple test before to speedup the function when the result is
obvious.
- moved the test on the vertex set to avoid duplicated code
- replace for loops with 'any' and 'all' statements. They do exactly the
same but are nicer.
{{{
[...]
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
TESTS:
Raise an error when self and other are of different types::
sage: G = Graph([(0,1)]).is_subgraph( DiGraph([(0,1)]) )
Traceback (most recent call last):
...
ValueError: The input parameter must be a Graph.
sage: G = DiGraph([(0,1)]).is_subgraph( Graph([(0,1)]) )
Traceback (most recent call last):
...
ValueError: The input parameter must be a DiGraph.
"""
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 self.num_verts() > other.num_verts():
return False
if any(v not in other for v in self.vertex_iterator()):
return False
if induced:
return other.subgraph(self.vertices()) == self
else:
return all(other.has_edge(e) for e in self.edge_iterator())
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13294#comment:9>
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.
