The task was: Write a function generate_semieuler that returns some directed semi-Eulerian graph on n vertices with m edges that has no bidirectional edges, or None if such a graph does not exist. Justify the correctness of the algorithm.
You must use only networkX and built-in libraries.
Problem Statement:
I need to write a function generate_semieuler that generates a directed graph with n vertices and m edges, which satisfies the following conditions:
1. The graph must be semi-Eulerian, i.e., it has an Eulerian path.
2. It must not contain bidirectional edges (no u -> v and v -> u ).
3. If no such graph exists, the function should return None.
Template:
def generate_semieuler(n: int, m: int) -> nx.DiGraph | None:
# your code goes here
pass
Tests:
%%pytests
@pytest.mark.parametrize(
"n, m",
((n, m) for n in range(0, 10) for m in range((n - 1) * (n - 2) // 2))
)
def test_generate_semieuler(n: int, m: int):
graph = generate_semieuler(n, m)
assert graph is not None
assert graph.number_of_nodes() == n
assert graph.size() == m
graph.remove_nodes_from(list(nx.isolates(graph)))
assert not graph or nx.has_eulerian_path(graph)
def test_generate_semieuler_edge_cases():
check_semieulerian(7, 22)
assert generate_semieuler(7, 23) is None
check_semieulerian(6, 13)
assert generate_semieuler(6, 14) is None
My code:
from itertools import permutations, combinations
import networkx as nx
from typing import Optional
def generate_semieuler(n: int, m: int) -> Optional[nx.DiGraph]:
max_edges = n * (n - 1) // 2
if m < 0 or m > max_edges:
return None
if n < 0:
return None
if n == 0:
return nx.DiGraph() if m == 0 else None
if n == 1:
return nx.DiGraph() if m == 0 else None
if m < 0 or m > n * (n - 1):
return None
G = nx.DiGraph()
G.add_nodes_from(range(n))
def can_add_cycle(H: nx.DiGraph, cycle_nodes):
k = len(cycle_nodes)
for i in range(k):
u = cycle_nodes[i]
v = cycle_nodes[(i + 1) % k]
if H.has_edge(u, v) or H.has_edge(v, u):
return False
return True
def add_cycle(H: nx.DiGraph, cycle_nodes):
k = len(cycle_nodes)
for i in range(k):
u = cycle_nodes[i]
v = cycle_nodes[(i + 1) % k]
H.add_edge(u, v)
def find_and_add_cycle(H: nx.DiGraph, length: int) -> bool:
for cycle_nodes in combinations(range(n), length):
for perm in permutations(cycle_nodes):
if can_add_cycle(H, perm):
add_cycle(H, perm)
return True
return False
if m == 0:
return G
if 0 < m < n:
# Создаём простой путь длиной m
for i in range(m):
G.add_edge(i, i + 1)
return G
if m == n - 1:
# Путь через все n вершин
for i in range(n - 1):
G.add_edge(i, i + 1)
return G
if m == n:
# Цикл из n рёбер
for i in range(n):
G.add_edge(i, (i + 1) % n)
return G
if m > n:
# Основной n-цикл
for i in range(n):
G.add_edge(i, (i + 1) % n)
L = m - n
def add_single_edge(H: nx.DiGraph) -> bool:
for u in range(n):
for v in range(n):
if u != v and not H.has_edge(u, v) and not H.has_edge(v, u):
H.add_edge(u, v)
return True
return False
def add_two_edges_in_path(H: nx.DiGraph) -> bool:
for a, b, c in permutations(range(n), 3):
if (not H.has_edge(a, b) and not H.has_edge(b, a) and
not H.has_edge(b, c) and not H.has_edge(c, b)):
H.add_edge(a, b)
H.add_edge(b, c)
return True
return False
def add_extra_edges(H: nx.DiGraph, L: int) -> bool:
if L == 0:
return True
mod = L % 3
if mod == 0:
count_3 = L // 3
for _ in range(count_3):
if not find_and_add_cycle(H, 3):
# Если не получилось добавить трёхцикл, попробуем добавлять одиночные рёбра
for __ in range(3):
if not add_single_edge(H):
return False
# Проверим, что всё ещё корректно
if H.size() > m:
return False
return True
elif mod == 1:
if L >= 4:
# Пытаемся добавить один четырёхцикл
if not find_and_add_cycle(H, 4):
# Если не удалось, попробуем другой подход:
# Добавим одиночное ребро, уменьшим L на 1 (теперь L делится на 3).
if not add_single_edge(H):
return False
L -= 1
return add_extra_edges(H, L)
L -= 4
count_3 = L // 3
for _ in range(count_3):
if not find_and_add_cycle(H, 3):
# Попытка заменить трёхцикл несколькими ребрами, если не получается
for __ in range(3):
if not add_single_edge(H):
return False
if H.size() > m:
return False
return True
else:
# L=1: добавляем одиночное ребро
return add_single_edge(H)
else: # mod == 2
if L >= 4:
# Добавляем один четырёхцикл
if not find_and_add_cycle(H, 4):
# Попытка замены на одиночные ребра, если 4-цикл не удался
for __ in range(4):
if not add_single_edge(H):
return False
L -= 4
return add_extra_edges(H, L)
L -= 4
return add_extra_edges(H, L)
else:
# L=2: пытаемся добавить два ребра в путь
if not add_two_edges_in_path(H):
# Если не получилось, добавляем по одному ребру
if not add_single_edge(H):
return False
if not add_single_edge(H):
return False
return True
if not add_extra_edges(G, L):
return None
# Дозаполняем до m рёбер, если чего-то не хватает
while G.size() < m:
if not add_single_edge(G):
return None
return G
return None
def check_semieulerian(n: int, m: int):
max_edges = n * (n - 1)
if m < 0 or m > max_edges:
return None
graph = generate_semieuler(n, m)
assert graph is not None, f"Граф не должен быть None для n={n}, m={m}"
assert graph.number_of_nodes() == n, f"Граф должен содержать {n} вершины, а содержит {graph.number_of_nodes()}"
assert graph.size() == m, f"Граф должен содержать {m} рёбер, а содержит {graph.size()}"
graph_filtered = graph.copy()
graph_filtered.remove_nodes_from(list(nx.isolates(graph_filtered)))
assert nx.has_eulerian_path(graph_filtered), f"Граф для n={n}, m={m} должен иметь эйлеров путь"
for u, v in graph.edges():
assert not graph.has_edge(v, u), f"В графе не должно быть двунаправленных рёбер между {u} и {v}"
I don’t understand how I can rewrite the code to check the condition for the existence of an Euler path (0 or 2 vertices with odd degrees as far as I remember)
I tried balancing the degrees of vertices with additional edges.
I modified helper functions to prioritize balancing degrees, but this broke the edge constraints.
All tests are passed except the last part of testing-code.
New contributor
cyrexskywalker is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.