Source code for tryalgo.min_mean_cycle

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Minimum mean cycle by Karp
jill-jenn vie et christoph durr - 2014-2018
"""


# snip{
# pylint: disable=too-many-locals
[docs]def min_mean_cycle(graph, weight, start=0): """Minimum mean cycle by Karp :param graph: directed graph in listlist or listdict format :param weight: in matrix format or same listdict graph :param int start: vertex that should be contained in cycle :returns: cycle as vertex list, average arc weights or None if there is no cycle from start :complexity: `O(|V|*|E|)` """ INF = float('inf') n = len(graph) # compute distances dist = [[INF] * n] prec = [[None] * n] dist[0][start] = 0 for ell in range(1, n + 1): dist.append([INF] * n) prec.append([None] * n) for node in range(n): for neighbor in graph[node]: alt = dist[ell - 1][node] + weight[node][neighbor] if alt < dist[ell][neighbor]: dist[ell][neighbor] = alt prec[ell][neighbor] = node # -- find the optimal value valmin = INF argmin = None for node in range(n): valmax = -INF argmax = None for k in range(n): alt = (dist[n][node] - dist[k][node]) / float(n - k) # do not divide by float(n-k) => cycle of minimal total weight if alt >= valmax: # with >= we get simple cycles valmax = alt argmax = k if argmax is not None and valmax < valmin: valmin = valmax argmin = (node, argmax) # -- extract cycle if valmin == INF: # -- there is no cycle return None C = [] node, k = argmin for l in range(n, k, -1): C.append(node) node = prec[l][node] return C[::-1], valmin
# snip}