ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 25 Jul 2024 06:28:20 +0200Does Sage have a function to determine vertex cuts?https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/ I know about `is_cut_vertex(G, u)` for checking if a vertex is a cut-vertex. But is there a function in Sage to determine if a subset of vertices is a vertex cut? Although it's not too difficult to write, as shown below:
def is_vertex_cut(graph, subset):
subgraph = graph.copy()
subgraph.delete_vertices(subset)
return not subgraph.is_connected()
Mon, 22 Jul 2024 09:33:12 +0200https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/Comment by licheng for <p>I know about <code>is_cut_vertex(G, u)</code> for checking if a vertex is a cut-vertex. But is there a function in Sage to determine if a subset of vertices is a vertex cut? Although it's not too difficult to write, as shown below:</p>
<pre><code>def is_vertex_cut(graph, subset):
subgraph = graph.copy()
subgraph.delete_vertices(subset)
return not subgraph.is_connected()
</code></pre>
https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?comment=78405#post-id-78405Thank you. I am not testing whether a set of vertices are cut vertices individually, but rather whether a subset of vertices forms a vertex cut set. Indeed, my goal is to test many subsets to determine whether they are vertex cut sets.Tue, 23 Jul 2024 05:29:59 +0200https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?comment=78405#post-id-78405Comment by vdelecroix for <p>I know about <code>is_cut_vertex(G, u)</code> for checking if a vertex is a cut-vertex. But is there a function in Sage to determine if a subset of vertices is a vertex cut? Although it's not too difficult to write, as shown below:</p>
<pre><code>def is_vertex_cut(graph, subset):
subgraph = graph.copy()
subgraph.delete_vertices(subset)
return not subgraph.is_connected()
</code></pre>
https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?comment=78401#post-id-78401For each `graph`, do you want to use your function for a single `subset` or many? I ask because it might not be the most efficient for what you aim to do. For example, to compute the list of cut vertices there is a `O(m)` algorithm but running `.is_cut_vertex(v)` for each vertex `v` of the graph would be `O(m^2)`.Mon, 22 Jul 2024 16:00:41 +0200https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?comment=78401#post-id-78401Answer by vdelecroix for <p>I know about <code>is_cut_vertex(G, u)</code> for checking if a vertex is a cut-vertex. But is there a function in Sage to determine if a subset of vertices is a vertex cut? Although it's not too difficult to write, as shown below:</p>
<pre><code>def is_vertex_cut(graph, subset):
subgraph = graph.copy()
subgraph.delete_vertices(subset)
return not subgraph.is_connected()
</code></pre>
https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?answer=78400#post-id-78400Such function does not seem to exist. The most relevant page for such questions seems to be [Connectivity related functions](https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/connectivity.html) Alternatively, you could use the following
def is_vertex_cut_bis(graph, subset):
new_graph = graph.copy()
new_graph.merge_vertices(subset)
return new_graph.is_cut_vertex(subset[0])Mon, 22 Jul 2024 15:58:02 +0200https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?answer=78400#post-id-78400Comment by licheng for <p>Such function does not seem to exist. The most relevant page for such questions seems to be <a href="https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/connectivity.html">Connectivity related functions</a> Alternatively, you could use the following</p>
<pre><code>def is_vertex_cut_bis(graph, subset):
new_graph = graph.copy()
new_graph.merge_vertices(subset)
return new_graph.is_cut_vertex(subset[0])
</code></pre>
https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?comment=78450#post-id-78450@David Coundert Nice. A similar problem, I am not sure if there is an implementation for determining if a set of edges is a cut-set (removal results in disconnection of a graph).Thu, 25 Jul 2024 06:28:20 +0200https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?comment=78450#post-id-78450Comment by David Coudert for <p>Such function does not seem to exist. The most relevant page for such questions seems to be <a href="https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/connectivity.html">Connectivity related functions</a> Alternatively, you could use the following</p>
<pre><code>def is_vertex_cut_bis(graph, subset):
new_graph = graph.copy()
new_graph.merge_vertices(subset)
return new_graph.is_cut_vertex(subset[0])
</code></pre>
https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?comment=78442#post-id-78442This is now https://github.com/sagemath/sage/pull/38418Wed, 24 Jul 2024 18:33:17 +0200https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?comment=78442#post-id-78442Comment by licheng for <p>Such function does not seem to exist. The most relevant page for such questions seems to be <a href="https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/connectivity.html">Connectivity related functions</a> Alternatively, you could use the following</p>
<pre><code>def is_vertex_cut_bis(graph, subset):
new_graph = graph.copy()
new_graph.merge_vertices(subset)
return new_graph.is_cut_vertex(subset[0])
</code></pre>
https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?comment=78406#post-id-78406@David Coudert Your idea is worth implementing in Sage.Tue, 23 Jul 2024 05:31:35 +0200https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?comment=78406#post-id-78406Comment by David Coudert for <p>Such function does not seem to exist. The most relevant page for such questions seems to be <a href="https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/connectivity.html">Connectivity related functions</a> Alternatively, you could use the following</p>
<pre><code>def is_vertex_cut_bis(graph, subset):
new_graph = graph.copy()
new_graph.merge_vertices(subset)
return new_graph.is_cut_vertex(subset[0])
</code></pre>
https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?comment=78403#post-id-78403The most efficient method is to do a depth-first search starting from a neighbor of `subset`, avoiding to visit vertices in `subset`. On the way, we record visited vertices. When it's done, it suffices to check if there is a vertex that has not be visited by the search and that is not in `subset`. This can be done in time `O(n + m)`.Mon, 22 Jul 2024 19:03:03 +0200https://ask.sagemath.org/question/78391/does-sage-have-a-function-to-determine-vertex-cuts/?comment=78403#post-id-78403