Python/Algorithm: Find negative cycle (fill out #todo's in homework.py file)

- weighted/directed graph G (find negative cycle if one's present)

- return sequence of vertices w/ no repetition of there is one : [v0, v1, v2], instead of [v0, v1, v2, v0]

- return None if no negative cycles in G

-----------------------------------------------------------------------------------------------

[homework.py]

from typing import Optional, Sequence

import networkx as nx

from utils import is_negative_cycle, edges_form_cycle

def find_negative_cycle(G_in) -> Optional[Sequence]:

"""

@param G_in: A directed graph (nx.DiGraph)

@return seq: A sequence (e.g. a list or tuple) of vertices which form a negative cycle in G.

The sequence should not contain any repeated vertex, i.e. [1, 2, 3] instead of [1, 2, 3, 1].

Every pair of consecutive elements must be adjacent (including the first and last).

>>> G = nx.DiGraph()

>>> G.add_weighted_edges_from([('a', 'b', 0.5), ('b', 'c', 0.4), ('c', 'a', 0.0)])

>>> find_negative_cycle(G) is None

True

>>> G['c']['a']["weight"] = -1.0

>>> seq = find_negative_cycle(G)

>>> is_negative_cycle(G, seq)

True

"""

# Directly modifying the input graph is not allowed

nx.freeze(G_in)

assert nx.is_frozen(G_in)

# To make a copy, use G_in.copy()

# todo (Use Bellman-Ford?)

############## Fill Out #######################

if __name__ == "__main__":

# Run the doctests

import doctest

doctest.testmod()

# You can test your code manually here

-----------------------------------------------------------------------------------

[utils.py]

from itertools import tee, zip_longest

def edges_form_cycle(G, edges):

if not all(G.has_edge(*e) for e in edges):

raise ValueError(f"Edge(s) missing from G: {[e for e in edges if not G.has_edge(*e)]}")

vertices = [u for u, v in edges] + [edges[-1][1]]

return vertices[0] == vertices[-1] and len(set(vertices)) == len(vertices) - 1

def pairwise_circular(iterable):

"""s -> (s0,s1), (s1,s2), (s2, s3), ..., (sn, s0)"""

a, b = tee(iterable)

last = next(b, None)

return zip_longest(a, b, fillvalue=last)

def is_negative_cycle(G, seq) -> bool:

k = len(seq)

total_weight = 0.0

for i in range(k):

u, v = seq[i], seq[(i+1) % k]

if v not in G[u]:

raise ValueError(f"Sequence is not a cycle in G. Edge ({u}, {v}) is missing.")

total_weight += G[u][v]["weight"]

return total_weight < 0

-----------------------------------------------------------------------------------

[test_find_negative_cycle.py]

import random

import networkx as nx

from utils import pairwise_circular, is_negative_cycle

from homework import find_negative_cycle

def generate_graph(n):

G: nx.DiGraph = nx.algorithms.tournament.random_tournament(n)

for u, v in G.edges():

G[u][v]["weight"] = random.uniform(0, 1)

u = random.randint(0, n - 1)

v = (u + 1) % n

if v in G[u]:

negative_edge = (u, v)

G[u][v]["weight"] = -n

else:

negative_edge = (v, u)

G[v][u]["weight"] = -n

return G, negative_edge

def test_find_negative_cycle():

for _ in range(20):

n = 25

G, negative_edge = generate_graph(n)

seq = find_negative_cycle(G)

if nx.negative_edge_cycle(G):

assert is_negative_cycle(G, seq)

assert negative_edge in pairwise_circular(seq)

else:

assert seq is None

def test_no_negative_cycle():

for _ in range(5):

n = 15

G, negative_edge = generate_graph(n)

u, v = negative_edge

G[u][v]["weight"] = 0.0

assert find_negative_cycle(G) is None

def test_find_negative_cycle_large():

for _ in range(5):

n = 200

G, negative_edge = generate_graph(n)

seq = find_negative_cycle(G)

assert is_negative_cycle(G, seq)

assert negative_edge in pairwise_circular(seq)