How to generate a triangle free graph in Networkx (with randomseed)?

Question

After checking the documentation on triangles of networkx, I've wondered if there is a more efficient way of generating a triangle free graph than to randomly spawn graphs until a triangle free one happens to emerge, (in particular if one would like to use a constant random seed).

Below is code that spawns graphs until they are triangle free, yet with varying random seeds. For a graph of 10 nodes it already takes roughly 20 seconds.

def create_triangle_free_graph(show_graphs):
    seed = 42
    nr_of_nodes = 10
    probability_of_creating_an_edge = 0.85
    nr_of_triangles = 1  # Initialise at 1 to initiate while loop.
    while nr_of_triangles > 0:
        graph = nx.fast_gnp_random_graph(
            nr_of_nodes, probability_of_creating_an_edge
        )
        triangles = nx.triangles(G).values()
        nr_of_triangles = sum(triangles) / 3
        print(f"nr_of_triangles={nr_of_triangles}")

    return graph

Hence, I would like to ask: Are there faster ways to generate triangle free graphs (using random seeds) in networkx?

Answer 1

A triangle exists in a graph iff two vertices connected by an edge share one or more neighbours. A triangle-free graph can be expanded by adding edges between nodes that share no neighbours. The empty graph is triangle-free, so there is a straightforward algorithm to create triangle-free graphs.

#!/usr/bin/env python
"""
Create a triangle free graph.
"""

import random
import networkx as nx

from itertools import combinations

def triangle_free_graph(total_nodes):
    """Construct a triangle free graph."""
    nodes = range(total_nodes)
    g = nx.Graph()
    g.add_nodes_from(nodes)
    edge_candidates = list(combinations(nodes, 2))
    random.shuffle(edge_candidates)
    for (u, v) in edge_candidates:
        if not set(n for n in g.neighbors(u)) & set(n for n in g.neighbors(v)):
            g.add_edge(u, v)
    return g

g = triangle_free_graph(10)
print(nx.triangles(g))

The number of edges in the resulting graph is highly dependent on the ordering of edge_candidates. To get a graph with the desired edge density, repeat the process until a graph with equal or higher density is found (and then remove superfluous edges), or until your patience runs out.

cutoff = 0.85
max_iterations = 1e+4
iteration = 0
while nx.density(g) < cutoff:
    g = triangle_free_graph(10)
    iteration += 1
    if iteration == max_iterations:
        import warnings
        warnings.warn("Maximum number of iterations reached!")
        break

# TODO: remove edges until the desired density is achieved