# MATH 566 - Implement Minimum Mean Cycle # # Implement Minimum Mean Cycle algorithm and use it on few test cases # # It might be useful to look at the following links when looking for # help with dealing with directed graphs # # http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html # http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/digraph.html # # For a directed graph G find a Minimum Mean Cycle. Returns # a subgraph corresponding to the cycle and mu. # def MeanCostCycle(G): # number of vertices n = G.order() # This will serve as a copy, where we return only edges of the smallest # cycle, or we return empty graph if no cycle found min_mean_cycle = copy(G) min_mean_cycle.delete_edges(G.edge_iterator()) # Prepare matrix to store Fk Fk = [dict() for x in range(n+1)] for k in range(n+1): for v in G: if k == 0: Fk[k][v] = 0 else: Fk[k][v] = Infinity # Might be usefull to look at Fk if you are trying to implement the algorithm # print Fk # prepare storage for Pk Pk = [dict() for x in range(n+1)] # compute all Fk (and Pk) # TODO # test if Fk[n] contains all infinities # TODO # if Fk[n-1] does not contain all infinities get the minium mean cycle # TODO # Return graph that is a subgraph of G, contains only edges of # the Minimum Mean Cycle and also return mu return [min_mean_cycle, mu] # creating a directed graph graph # the third number is edge label, in our case we use it as # a cost of the edge # Try all 3 test cases g = DiGraph([(1,2,1), (2,3,2), (3,4,-1), (4,1,1), (4,2,2) ]) g.show(edge_labels=True) [cycle,mu] = MeanCostCycle(g) print "Mu=",mu cycle.show(edge_labels=True) g = DiGraph([(1,2,3), (1,3,2), (2,4,-1), (3,4,1), (4,5,0), (5,6,1), (5,7,2), (6,8,1), (7,8,3), (8,1,2) ]) g.show(edge_labels=True) [cycle,mu] = MeanCostCycle(g) print "Mu=",mu cycle.show(edge_labels=True) g = DiGraph([(1,2,1), (2,3,1), (3,4,1), (1,4,1), (4,5,2) ]) g.show(edge_labels=True) [cycle,mu] = MeanCostCycle(g) print "Mu=",mu cycle.show(edge_labels=True)