Liste en compréhension

Tester si un graphe est régulier

Un graphe est dit régulier quand tous ses sommets ont le même degré.

def is_regular(G):
return len(set([G.degree(k) for k in G.nodes()])) == 1

Fonction à partir de matrice et liste d’adjacence

import networkx as nx

def from_matrix(M):
    G = nx.Graph()
    for k in range(len(M)-1):
        for l in range(k, len(M)):
            if M[k,l]:
                G.add_edge(k, l)
    return G

def from_dict(dico):
    G = nx.Graph()
    for k in dico:
        for l in dico[k]:
            G.add_edge(k, l)
    return G

import networkx as nx

def from_matrix(M):
    G = nx.Graph()
    for k in range(len(M)-1):
        for l in range(k, len(M)):
            if M[k,l]:
                G.add_edge(k, l)
    return G

def from_dict(dico):
    G = nx.Graph()
    for k in dico:
        for l in dico[k]:
            G.add_edge(k, l)
    return G

import numpy as np
import networkx as nx

adj_matrix_np = np.array([
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 1],
    [0, 1, 1, 0]
])
G = nx.from_numpy_array(adj_matrix_np)

adj_list = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [1, 2]
}
G = nx.from_dict_of_lists(adj_list)

Tester si un graphe est symétrique ou antisymétrique

def est_symetrique(G):
    for a, b in G.edges():
        if (b, a) not in G.edges():
            return False
    return True

def est_anti_symetrique(G):
    for a, b in G.edges():
        if (b, a) in G.edges():
            return False
    return True

Tester si un graphe est complémentaire

from itertools import product
import networkx as nx

def complementaire(G):
    comp = nx.DiGraph()
    comp.add_nodes_from(G.nodes)
    for a, b in product(G.nodes(), G.nodes()):
        if a != b and (a, b) not in list(G.edges()):
            comp.add_edge(a, b)
    return comp

Tester si un graphe est simple

def is_simple(G)
	return all(len(set(edge))==2 for edge in G.edges)

Tester si un graphe est complet

def is_complete(G):
	n = G.order()
	return is_simple(G) and (n*(n-1)/2 == G.size())

Tester si un graphe H est un sous-graphe de G

def is_subgraph(H, G):
	nodes_present = all(node in G.nodes for node in H.nodes)
	edges_present = all(edge in G.edges for edge in H.edges)
	# Les arêtes de G constituées de sommets de H sont des arêtes de H
	last_cond = all(edge in H.edges
									for edge in G.edges
									if set(edge).issubset(set(H.nodes)))
	return nodes_present and edges_present and last_cond