Revision history [back]

Let $G$ be a graph. Toughness is defined as $$ t(G)=\min _S \frac{|S|}{c(G-S)} $$ where $c$ is the number of connected components and the minimum is taken over all vertex cuts $S$ of $G$ (Graph toughness was first introduced by Václav Chvátal (1973)).

Based on the definition, I have written a code that relies mainly on third-party libraries networkx and itertools. I'm wondering if there is hope to improve its efficiency in the Sage or Python environment

import networkx as nx
from itertools import combinations

def is_vertex_cut(G, vertex_cut):
    # Create a copy of the graph
    H = G.copy()
    # Remove the nodes from the given set
    H.remove_nodes_from(vertex_cut)
    # Check the connectivity of the graph
    return not nx.is_connected(H)

def toughness(G):
    nodes = G.nodes()
    order = G.number_of_nodes() - 2
    vertex_conn = nx.node_connectivity(G)
    min_toughness = float('inf')  # Initialize the minimum toughness to positive infinity
    for r in range(vertex_conn, order):
        for j in combinations(nodes, r):
        if is_vertex_cut(G, j):
            # Create a copy of the graph
            H = G.copy()
            # Remove the nodes from the given set
            H.remove_nodes_from(j)
            # Calculate the number of connected components in (G-j)
            num_connected_components = nx.number_connected_components(H)
            toughness_value = r / num_connected_components
            # Update the toughness value
            min_toughness = min(min_toughness, toughness_value)

# Return the minimum toughness value
return min_toughness

# Test code
G = nx.cycle_graph(20)
# G = nx.Graph()
# G.add_nodes_from([1, 2, 3, 4, 5, 6])
# G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1)])

min_toughness = toughness(G)
print("toughness:", min_toughness)

Let $G$ be a graph. Toughness is defined as $$ t(G)=\min _S \frac{|S|}{c(G-S)} $$ where $c$ is the number of connected components and the minimum is taken over all vertex cuts $S$ of $G$ (Graph toughness was first introduced by Václav Chvátal (1973)).

Based on the definition, I have written a code that relies mainly on third-party libraries networkx and itertools. I'm wondering if there is hope to improve its efficiency in the Sage or Python environment

#Import the networkx library
import networkx as nx
# Import the combinations function from itertools
from itertools import combinations

def is_vertex_cut(G, vertex_cut):
    # Create a copy of the graph
    H = G.copy()
    # Remove the nodes from the given set
    H.remove_nodes_from(vertex_cut)
    # Check the connectivity of the graph
    return not nx.is_connected(H)

def toughness(G):
    nodes = G.nodes()
    order = G.number_of_nodes() - 2
    vertex_conn = nx.node_connectivity(G)
    min_toughness = float('inf')  # Initialize the minimum toughness to positive infinity
    for r in range(vertex_conn, order):
        for j in combinations(nodes, r):
         if is_vertex_cut(G, j):
             # Create a copy of the graph
             H = G.copy()
             # Remove the nodes from the given set
             H.remove_nodes_from(j)
             # Calculate the number of connected components in (G-j)
             num_connected_components = nx.number_connected_components(H)
             toughness_value = r / num_connected_components
             # Update the toughness value
             min_toughness = min(min_toughness, toughness_value)

 # Return the minimum toughness value
 return min_toughness

# Test code
G = nx.cycle_graph(20)
nx.cycle_graph(14)

# # G = nx.Graph()
# # G.add_nodes_from([1, 2, 3, 4, 5, 6])
# # G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1)])

min_toughness = toughness(G)
print("toughness:", min_toughness)

Let $G$ be a graph. Toughness is defined as $$ t(G)=\min _S \frac{|S|}{c(G-S)} $$ where $c$ is the number of connected components and the minimum is taken over all vertex cuts $S$ of $G$ (Graph toughness was first introduced by Václav Chvátal (1973)).

Based on the definition, I have written a code that relies mainly on third-party libraries networkx and itertools. I'm wondering if there is hope to improve its efficiency in the Sage or Python environment

#Import the networkx library
import networkx as nx
# Import the combinations function from itertools
from itertools import combinations

def is_vertex_cut(G, vertex_cut):
    # Create a copy of the graph
    H = G.copy()
    # Remove the nodes from the given set
    H.remove_nodes_from(vertex_cut)
    # Check the connectivity of the graph
    return not nx.is_connected(H)

def toughness(G):
    nodes = G.nodes()
    order = G.number_of_nodes() - 2
    vertex_conn = nx.node_connectivity(G)
    min_toughness = float('inf')  # Initialize the minimum toughness to positive infinity
    for r in range(vertex_conn, order):
        for j in combinations(nodes, r):
            if is_vertex_cut(G, j):
                # Create a copy of the graph
                H = G.copy()
                # Remove the nodes from the given set
                H.remove_nodes_from(j)
                # Calculate the number of connected components in (G-j)
                num_connected_components = nx.number_connected_components(H)
                toughness_value = r / num_connected_components
                # Update the toughness value
                min_toughness = min(min_toughness, toughness_value)

    # Return the minimum toughness value
    return min_toughness

# Test code
G = nx.cycle_graph(14)
nx.cycle_graph(20)

# # G = nx.Graph()
# # G.add_nodes_from([1, 2, 3, 4, 5, 6])
# # G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1)])

min_toughness = toughness(G)
print("toughness:", min_toughness)

Let $G$ be a graph. Toughness is defined as $$ t(G)=\min _S \frac{|S|}{c(G-S)} $$ where $c$ is the number of connected components and the minimum is taken over all vertex cuts $S$ of $G$ (Graph toughness was first introduced by Václav Chvátal (1973)).

Based on the definition, I have written a code that relies mainly on third-party libraries networkx and itertools. I'm wondering if there is hope to improve its efficiency in the Sage or Python environment

#Import the networkx library
import networkx as nx
# Import the combinations function from itertools
from itertools import combinations

def is_vertex_cut(G, vertex_cut):
    # Create a copy of the graph
    H = G.copy()
    # Remove the nodes from the given set
    H.remove_nodes_from(vertex_cut)
    # Check the connectivity of the graph
    return not nx.is_connected(H)

def toughness(G):
    nodes = G.nodes()
    order = G.number_of_nodes() - 2
    vertex_conn = nx.node_connectivity(G)
    min_toughness = float('inf')  # Initialize the minimum toughness to positive infinity
    for r in range(vertex_conn, order):
        for j in combinations(nodes, r):
            if is_vertex_cut(G, j):
                # Create a copy of the graph
                H = G.copy()
                # Remove the nodes from the given set
                H.remove_nodes_from(j)
                # Calculate the number of connected components in (G-j)
                num_connected_components = nx.number_connected_components(H)
                toughness_value = r / num_connected_components
                # Update the toughness value
                min_toughness = min(min_toughness, toughness_value)

    # Return the minimum toughness value
    return min_toughness

# Test code
G = nx.cycle_graph(20)

# # G = nx.Graph()
# # G.add_nodes_from([1, 2, 3, 4, 5, 6])
# # G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1)])

min_toughness = toughness(G)
print("toughness:", min_toughness)

Then it gives us the following output:

toughness: 1.0 run 166.504868507385251.0

Let $G$ be a graph. Toughness is defined as $$ t(G)=\min _S \frac{|S|}{c(G-S)} $$ where $c$ is the number of connected components and the minimum is taken over all vertex cuts $S$ of $G$ (Graph toughness was first introduced by Václav Chvátal (1973)).

Based on the definition, I have written a code that relies mainly on third-party libraries networkx and itertools. I'm wondering if there is hope to improve its efficiency in the Sage or Python environment

#Import the networkx library
import networkx as nx
# Import the combinations function from itertools
from itertools import combinations

def is_vertex_cut(G, vertex_cut):
    # Create a copy of the graph
    H = G.copy()
    # Remove the nodes from the given set
    H.remove_nodes_from(vertex_cut)
    # Check the connectivity of the graph
    return not nx.is_connected(H)

def toughness(G):
    nodes = G.nodes()
    order = G.number_of_nodes() - 2
    vertex_conn = nx.node_connectivity(G)
    min_toughness = float('inf')  # Initialize the minimum toughness to positive infinity
    for r in range(vertex_conn, order):
        for j in combinations(nodes, r):
            if is_vertex_cut(G, j):
                # Create a copy of the graph
                H = G.copy()
                # Remove the nodes from the given set
                H.remove_nodes_from(j)
                # Calculate the number of connected components in (G-j)
                num_connected_components = nx.number_connected_components(H)
                toughness_value = r / num_connected_components
                # Update the toughness value
                min_toughness = min(min_toughness, toughness_value)

    # Return the minimum toughness value
    return min_toughness

# Test code
G = nx.cycle_graph(20)

# # G = nx.Graph()
# # G.add_nodes_from([1, 2, 3, 4, 5, 6])
# # G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1)])

min_toughness = toughness(G)
print("toughness:", min_toughness)

Then it gives us the following output:

toughness: 1.0

(run 166.50486850738525s)166.5s)

Let $G$ be a graph. Toughness is defined as $$ t(G)=\min _S \frac{|S|}{c(G-S)} $$ where $c$ is the number of connected components and the minimum is taken over all vertex cuts $S$ of $G$ (Graph toughness was first introduced by Václav Chvátal Chvátal (1973)).

Based on the definition, I have written a code that relies mainly on third-party libraries networkx networkx and itertools. itertools. I'm wondering if there is hope to improve its efficiency in the Sage or Python environmentenvironment.

#Import the networkx library
import networkx as nx
# Import the combinations function from itertools
from itertools import combinations

def is_vertex_cut(G, vertex_cut):
    # Create a copy of the graph
    H = G.copy()
    # Remove the nodes from the given set
    H.remove_nodes_from(vertex_cut)
    # Check the connectivity of the graph
    return not nx.is_connected(H)

def toughness(G):
    nodes = G.nodes()
    order = G.number_of_nodes() - 2
    vertex_conn = nx.node_connectivity(G)
    min_toughness = float('inf')  # Initialize the minimum toughness to positive infinity
    for r in range(vertex_conn, order):
        for j in combinations(nodes, r):
            if is_vertex_cut(G, j):
                # Create a copy of the graph
                H = G.copy()
                # Remove the nodes from the given set
                H.remove_nodes_from(j)
                # Calculate the number of connected components in (G-j)
                num_connected_components = nx.number_connected_components(H)
                toughness_value = r / num_connected_components
                # Update the toughness value
                min_toughness = min(min_toughness, toughness_value)

    # Return the minimum toughness value
    return min_toughness

# Test code
G = nx.cycle_graph(20)

# # G = nx.Graph()
# # G.add_nodes_from([1, 2, 3, 4, 5, 6])
# # G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1)])

min_toughness = toughness(G)
print("toughness:", min_toughness)

Then it gives us the following output:

toughness: 1.0

(run 166.5s)