def test_others(self):
        (P, D) = nx.bellman_ford(self.XG, 's')
        assert_equal(P['v'], 'u')
        assert_equal(D['v'], 9)
        (P, D) = nx.goldberg_radzik(self.XG, 's')
        assert_equal(P['v'], 'u')
        assert_equal(D['v'], 9)

        G = nx.path_graph(4)
        assert_equal(nx.bellman_ford(G, 0),
                     ({0: None, 1: 0, 2: 1, 3: 2}, {0: 0, 1: 1, 2: 2, 3: 3}))
        assert_equal(nx.goldberg_radzik(G, 0),
                     ({0: None, 1: 0, 2: 1, 3: 2}, {0: 0, 1: 1, 2: 2, 3: 3}))
        assert_equal(nx.bellman_ford(G, 3),
                     ({0: 1, 1: 2, 2: 3, 3: None}, {0: 3, 1: 2, 2: 1, 3: 0}))
        assert_equal(nx.goldberg_radzik(G, 3),
                     ({0: 1, 1: 2, 2: 3, 3: None}, {0: 3, 1: 2, 2: 1, 3: 0}))

        G = nx.grid_2d_graph(2, 2)
        pred, dist = nx.bellman_ford(G, (0, 0))
        assert_equal(sorted(pred.items()),
                     [((0, 0), None), ((0, 1), (0, 0)),
                      ((1, 0), (0, 0)), ((1, 1), (0, 1))])
        assert_equal(sorted(dist.items()),
                     [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)])
        pred, dist = nx.goldberg_radzik(G, (0, 0))
        assert_equal(sorted(pred.items()),
                     [((0, 0), None), ((0, 1), (0, 0)),
                      ((1, 0), (0, 0)), ((1, 1), (0, 1))])
        assert_equal(sorted(dist.items()),
                     [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)])

    def test_bellman_ford(self):
        # single node graph
        G = nx.DiGraph()
        G.add_node(0)
        assert_equal(nx.bellman_ford(G, 0), ({0: None}, {0: 0}))
        assert_raises(KeyError, nx.bellman_ford, G, 1)

        # negative weight cycle
        G = nx.cycle_graph(5, create_using=nx.DiGraph())
        G.add_edge(1, 2, weight=-7)
        for i in range(5):
            assert_raises(nx.NetworkXUnbounded, nx.bellman_ford, G, i)
        G = nx.cycle_graph(5)  # undirected Graph
        G.add_edge(1, 2, weight=-3)
        for i in range(5):
            assert_raises(nx.NetworkXUnbounded, nx.bellman_ford, G, i)
        # no negative cycle but negative weight
        G = nx.cycle_graph(5, create_using=nx.DiGraph())
        G.add_edge(1, 2, weight=-3)
        assert_equal(nx.bellman_ford(G, 0), ({0: None, 1: 0, 2: 1, 3: 2, 4: 3}, {0: 0, 1: 1, 2: -2, 3: -1, 4: 0}))

        # not connected
        G = nx.complete_graph(6)
        G.add_edge(10, 11)
        G.add_edge(10, 12)
        assert_equal(
            nx.bellman_ford(G, 0), ({0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}, {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1})
        )

        # not connected, with a component not containing the source that
        # contains a negative cost cycle.
        G = nx.complete_graph(6)
        G.add_edges_from([("A", "B", {"load": 3}), ("B", "C", {"load": -10}), ("C", "A", {"load": 2})])
        assert_equal(
            nx.bellman_ford(G, 0, weight="load"),
            ({0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}, {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1}),
        )

        # multigraph
        P, D = nx.bellman_ford(self.MXG, "s")
        assert_equal(P["v"], "u")
        assert_equal(D["v"], 9)
        P, D = nx.bellman_ford(self.MXG4, 0)
        assert_equal(P[2], 1)
        assert_equal(D[2], 4)

        # other tests
        (P, D) = nx.bellman_ford(self.XG, "s")
        assert_equal(P["v"], "u")
        assert_equal(D["v"], 9)

        G = nx.path_graph(4)
        assert_equal(nx.bellman_ford(G, 0), ({0: None, 1: 0, 2: 1, 3: 2}, {0: 0, 1: 1, 2: 2, 3: 3}))
        assert_equal(nx.bellman_ford(G, 3), ({0: 1, 1: 2, 2: 3, 3: None}, {0: 3, 1: 2, 2: 1, 3: 0}))

        G = nx.grid_2d_graph(2, 2)
        pred, dist = nx.bellman_ford(G, (0, 0))
        assert_equal(sorted(pred.items()), [((0, 0), None), ((0, 1), (0, 0)), ((1, 0), (0, 0)), ((1, 1), (0, 1))])
        assert_equal(sorted(dist.items()), [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)])

 def test_multigraph(self):
     P, D = nx.bellman_ford(self.MXG, 's')
     assert_equal(P['v'], 'u')
     assert_equal(D['v'], 9)
     P, D = nx.goldberg_radzik(self.MXG, 's')
     assert_equal(P['v'], 'u')
     assert_equal(D['v'], 9)
     P, D = nx.bellman_ford(self.MXG4, 0)
     assert_equal(P[2], 1)
     assert_equal(D[2], 4)
     P, D = nx.goldberg_radzik(self.MXG4, 0)
     assert_equal(P[2], 1)
     assert_equal(D[2], 4)

def peptideSequencing(spectralVector, proteins=None):
    
    if proteins is None:
        proteins = proteinMass
    graph = nx.DiGraph()
    maxIndex = len(spectralVector)
    graph.add_nodes_from(xrange(maxIndex))

    for idx in xrange(maxIndex):
        # Ignore nodes with no incoming edges except the 1st one.
        if idx > 0 and len(graph.in_edges(idx)) == 0:
            continue
        
        for p, mass in proteins.iteritems():
            if idx + mass < len(spectralVector):
                try:
                    graph.add_edge(idx, idx+mass,{'amino': p,
                                              'weight': -1 * spectralVector[idx+mass]})
                except IndexError as e:
                    pass
    
    pred, dist = nx.bellman_ford(graph, 0)
    proteinLookup = {v:k for k,v in proteins.iteritems()}    
    idx = len(spectralVector)-1
    path = []
    while idx > 0:
        path.append(proteinLookup[idx-pred[idx]])
        idx = pred[idx]
    return ''.join(path[::-1])

def SubSolve(G,pi):
    #print "pi=",pi
    G.edge[1][2]["cost"]-=pi[1]
    G.edge[1][3]["cost"]-=pi[1]
    G.edge[1]['t']["cost"]-=pi[1]
    G.edge[2][3]["cost"]-=pi[2]
    G.edge[2]['t']["cost"]-=pi[2]
    G.edge[3]['t']["cost"]-=pi[3]

    #print G.edges(data=True)
    
    pred, dist = nx.bellman_ford(G,'s',weight="cost")
    new_chemin=[]
    chemin=['t']
    predecesseur = pred['t']
    chemin.append(predecesseur)
    k=predecesseur
    while predecesseur != 's':
        predecesseur = pred[k]
        chemin.append(predecesseur)
        k=predecesseur

    chemin.reverse()

    G.edge[1][2]["cost"]+=pi[1]
    G.edge[1][3]["cost"]+=pi[1]
    G.edge[1]['t']["cost"]+=pi[1]
    G.edge[2][3]["cost"]+=pi[2]
    G.edge[2]['t']["cost"]+=pi[2]
    G.edge[3]['t']["cost"]+=pi[3]
    
    L=2*dist['t']+sum(pi[i] for i in [1,2,3])
    #print "chemin optimal=",chemin,"de cout",dist['t']
    print "L=",L
    return L,chemin

 def test_single_node_graph(self):
     G = nx.DiGraph()
     G.add_node(0)
     assert_equal(nx.bellman_ford(G, 0), ({0: None}, {0: 0}))
     assert_equal(nx.goldberg_radzik(G, 0), ({0: None}, {0: 0}))
     assert_raises(KeyError, nx.bellman_ford, G, 1)
     assert_raises(KeyError, nx.goldberg_radzik, G, 1)

    def test_bellman_ford(self):
        # single node graph
        G = nx.DiGraph()
        G.add_node(0)
        assert_equal(nx.bellman_ford(G, 0), ({0: None}, {0: 0}))

        # negative weight cycle
        G = nx.cycle_graph(5, create_using = nx.DiGraph())
        G.add_edge(1, 2, weight = -7)
        assert_raises(nx.NetworkXUnbounded, nx.bellman_ford, G, 0)
        G = nx.cycle_graph(5)
        G.add_edge(1, 2, weight = -7)
        assert_raises(nx.NetworkXUnbounded, nx.bellman_ford, G, 0)

        # not connected
        G = nx.complete_graph(6)
        G.add_edge(10, 11)
        G.add_edge(10, 12)
        assert_equal(nx.bellman_ford(G, 0),
                     ({0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0},
                      {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1}))

        # not connected, with a component not containing the source that
        # contains a negative cost cycle.
        G = nx.complete_graph(6)
        G.add_edges_from([('A', 'B', {'load': 3}),
                          ('B', 'C', {'load': -10}),
                          ('C', 'A', {'load': 2})])
        assert_equal(nx.bellman_ford(G, 0, weight = 'load'),
                     ({0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0},
                      {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1}))

        # multigraph
        P, D = nx.bellman_ford(self.MXG,'s')
        assert_equal(P['v'], 'u')
        assert_equal(D['v'], 9)
        P, D = nx.bellman_ford(self.MXG4, 0)
        assert_equal(P[2], 1)
        assert_equal(D[2], 4)

        # other tests
        (P,D)= nx.bellman_ford(self.XG,'s')
        assert_equal(P['v'], 'u')
        assert_equal(D['v'], 9)

        G=nx.path_graph(4)
        assert_equal(nx.bellman_ford(G,0),
                     ({0: None, 1: 0, 2: 1, 3: 2}, {0: 0, 1: 1, 2: 2, 3: 3}))
        G=nx.grid_2d_graph(2,2)
        pred,dist=nx.bellman_ford(G,(0,0))
        assert_equal(sorted(pred.items()),
                     [((0, 0), None), ((0, 1), (0, 0)), 
                      ((1, 0), (0, 0)), ((1, 1), (0, 1))])
        assert_equal(sorted(dist.items()),
                     [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)])

 def compute_paths(self):
     self.shortest_paths = list()
     for src in xrange(self.parameters.nodes_in):
         try:
             (pred, dist) = nx.bellman_ford(self, src)
         except:
             continue
         for tar in xrange(self.parameters.nodes_end_middle,\
                 self.parameters.nodes_total):
             if dist.has_key(tar):
                 self.shortest_paths.append(dist[tar])

def prog_20(fname):
    graph = nx.DiGraph()
    f = open(fname)
    value, num = map(int, f.readline().strip().split())
    for line in f:
        e1,e2,weight = map(int, line.strip().split())
        graph.add_weighted_edges_from([(e1,e2,weight)])
    graph.add_nodes_from(xrange(1,value+1))
    f.close()

    pred, dist = nx.bellman_ford(graph,1)

    for i in xrange(1,value+1):
        print dist.get(i, 'x'),

 def getTree(self,node,reverse=False):
     if self.dirty:
         self.createGraph()
     
     if reverse:
         myGraph = self.graph.reverse()
     else:
         myGraph = self.graph
         
     # Returns pred, weight
     pred, _ = nx.bellman_ford(myGraph, node)
     edges = [(v,u,myGraph[v][u]) for (u,v) in pred.items() if v is not None]
     
     return edges

    def test_not_connected(self):
        G = nx.complete_graph(6)
        G.add_edge(10, 11)
        G.add_edge(10, 12)
        assert_equal(nx.bellman_ford(G, 0),
                     ({0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0},
                      {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1}))
        assert_equal(nx.goldberg_radzik(G, 0),
                     ({0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0},
                      {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1}))

        # not connected, with a component not containing the source that
        # contains a negative cost cycle.
        G = nx.complete_graph(6)
        G.add_edges_from([('A', 'B', {'load': 3}),
                          ('B', 'C', {'load': -10}),
                          ('C', 'A', {'load': 2})])
        assert_equal(nx.bellman_ford(G, 0, weight='load'),
                     ({0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0},
                      {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1}))
        assert_equal(nx.goldberg_radzik(G, 0, weight='load'),
                     ({0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0},
                      {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1}))

def _bellman_ford_path(G, source, target, weight):
    "Returns shortest path using bellman_ford algorithm."
    pred, dist = nx.bellman_ford(G, source, weight)
    if target not in pred:
        raise nx.NetworkXNoPath(
            "Node %s not reachable from %s." % (source, target))
    # Since predecessors are given, build path backwards, then reverse.
    path = []
    curr = target
    while curr != source:
        path.append(curr)
        curr = pred[curr]
    path.append(source)
    path.reverse()
    return path

def objective(graph, centers):
    """Calculates the distance between nodes and centers.

    :param graph: Graph
    :param centers: list
    :return: float
    """
    if centers:
        # For big k networkx.floyd_warshall_numpy can be faster:
        # distance = networkx.floyd_warshall_numpy(graph)
        # return distance[numpy.ix_([graph.nodes().index(c) for c in centers])].min(axis=0).max(axis=1)[0,0]
        distance = {c: networkx.bellman_ford(graph, c)[1] for c in centers}
        return max([min([distance[c].get(n, float('inf')) for c in centers]) for n in graph.nodes_iter()])
    else:
        return float("inf")

def _get_longest_paths(g, source_nodes):
    ''' Get the longest path for nodes in 'source_nodes'
        Find with bellman_ford() by setting weight = -1
    '''

    ng = copy.deepcopy(g)
    for u, v in ng.edges():
        ng[u][v]["weight"] = -1

    ret = {}
    for cn in source_nodes:
        pred, dist = nx.bellman_ford(ng, cn, weight="weight")
        path = _get_path(pred, dist)
        assert path[0] == cn
        assert len(path) - 1 == -dist[path[-1]]
        ret[cn] = path

    return ret

def plot_big_graph(task):
    args = resolve_args(task._algorithm, *task._args)
    data = args[1]

    fig = pylab.figure(figsize=(5, 5))
    pylab.axis('off')
    ax = fig.add_subplot(111)
    ax.xaxis.set_major_locator(pylab.NullLocator())
    ax.yaxis.set_major_locator(pylab.NullLocator())
    ax.set_aspect('equal')

    pos = networkx.get_node_attributes(data, 'pos')
    nodes = data.nodes().copy()
    for c in task._result:
        nodes.remove(c)

    distance = {c: networkx.bellman_ford(data, c)[1] for c in task._result}
    node_colors = [
        COLORS[min(range(len(task._result)), key=lambda i: distance[task._result[i]].get(n, float('inf')))]
        for n in nodes
    ]

    networkx.draw_networkx(data, pos, with_labels=False, node_size=5, nodelist=nodes, node_color=node_colors,
                           linewidths=0)
    networkx.draw_networkx_nodes(data, pos, with_labels=False, node_size=100, node_color=COLORS,
                                 nodelist=task._result, node_shape='p')

    x = [p[0] for p in pos.values()]
    y = [p[1] for p in pos.values()]

    minx = min(x)
    maxx = max(x)
    extrax = 0.1 * (maxx - minx)
    miny = min(y)
    maxy = max(y)
    extray = 0.1 * (maxy - miny)
    ax.set_ylim([miny - extray, maxy + extray])
    ax.set_xlim([minx - extrax, maxx + extrax])

    stream = io.BytesIO()
    fig.savefig(stream, format='png', bbox_inches='tight', pad_inches=0)

    return stream.getvalue()

    def getTree(self, node, reverse=False):
        """
        Get
        :param node:    A start node
        :param reverse: Should the graph be reversed (upstream search)
        :return:        A list of edges
        """
        if self.dirty:
            self.createGraph()

        if reverse:
            my_graph = self.graph.reverse()
        else:
            my_graph = self.graph

        # Returns pred, weight
        pred, _ = nx.bellman_ford(my_graph, node)
        edges = [(v, u, my_graph[v][u]) for (u, v) in pred.items() if v is not None]

        return edges

def gonzalez(k, graph, randomized=True, heuristic=None, bellman_ford=True):
    """This function gives a 2-approximation for the k-center problem on a graph.
    See "Clustering to minimize the maximum intercluster distance" by
    Teofilo F. Gonzalez for more details.

    :param k: int
    :param graph: Graph
    :return: list
    """

    def distance(node, target):
        try:
            # return networkx.dijkstra_path_length(graph, node, target)
            return networkx.astar_path_length(graph, node, target, heuristic=heuristic)
        except networkx.NetworkXNoPath:
            return float('inf')

    if randomized:
        result = [random.choice(graph.nodes())]
    else:
        result = [graph.nodes()[0], ]
    for l in range(k - 1):
        dist = 0
        head = None
        if bellman_ford:
            distance = {c: networkx.bellman_ford(graph, c)[1] for c in result}
            head = max([
                (n, min([(c, distance[c].get(n, float('inf'))) for c in result], key=lambda i: i[1])[1])
                for n in graph.nodes_iter()
            ], key=lambda i: i[1])[0]
        else:
            for node in graph.nodes():
                tmp_dist = min(distance(node, target) for target in result)
                if tmp_dist > dist:
                    dist = tmp_dist
                    head = node
        if head:
            result.append(head)
        else:
            return result
    return result

 def _all_shortest_paths(self):
 
     """ Find all shortest paths from every node to destination """
     #make a reversed graph (reversing all the edges), so we can find single destination shortest paths problem
     
     _reverse_graph =  self._G.reverse(copy=True)
     _reverse_pred, _dist = nx.bellman_ford(_reverse_graph,'t') 
     print time.ctime(), "reverse_pred, & dist by using bellman ford "
     _pred = defaultdict(dict)
     for node, neighbor in _reverse_pred.iteritems():
         _pred[neighbor]=node
     for counter, node in enumerate(self._G.nodes()):
         try:
             self._G.node[node]['target_distance']=_dist[node]
         except KeyError:
             self._G.node[node]['target_distance']=float('inf')
         _path=self._get_path_from_predecessors((_reverse_pred), destination=node)
         path = list(reversed([(value, key) for key,value in _path]))
         self._G.node[node]['path']=path
         
     self.shortest_path_distance = self._G.node[self.source]['target_distance']

def routeOptimizer(topEvents, relWeight):
	# Gets a list of the top events from multiple areas, creates a weighted graph, finds best route

	l = len(topEvents)
	fullDist = 1.0*lldist( topEvents[0]['venLat'], topEvents[0]['venLon'], topEvents[l-1]['venLat'], topEvents[l-1]['venLon']) # lat/lon distance from start to end	
	
	# MUST MAKE SURE START AND END ARE IN THE LIST
	DG = nx.DiGraph() # create a new directed graph
	
	for i in topEvents:
		DG.add_node(i['ind'],date=i['date'])
		DG.add_node(i['ind'],venue=i['venue'])
		DG.add_node(i['ind'],band=i['band'])
  		for j in topEvents:
        		day1 = to_datetime(i['date']).date()
        		day2 = to_datetime(j['date']).date()
        		deltaDay = day2 - day1
			dist = 1.0*lldist( i['venLat'], i['venLon'], j['venLat'], j['venLon'] ) 
			#dist = 1.0*osrmDist( i['venLat'], i['venLon'], j['venLat'], j['venLon'] ) 
			tooFar = 500 # in miles
			#tooFar = 300000 # in 10ths of seconds, about 8 hours
        		if (deltaDay.days > 0):
				if (dist/deltaDay.days < tooFar): # only link two events if the second is forward in time, and they're not too far
            				#wght = dist*np.exp((float(j['rank'])/rank_norm)-1)
            				wght = ((1.0-relWeight/100.0) *(dist/fullDist) - (relWeight/100.0)*(1-float(j['rank'])/rank_norm))
		#			wght = np.exp(wght) # map wght to between 0 and 1
	#				if (wght <= 0): wght = (j['rank']/rank_norm)*(dist/fullDist)
					print i['ind'],j['ind'],wght
            				DG.add_weighted_edges_from([(i['ind'],j['ind'],wght)])

	pred, dist = nx.bellman_ford(DG,'Start','weight')
	node = 'End'
	nodeList = []
	while (node != 'Start'):
		nodeList.append(node)
		node = pred[node]
	#path = nx.shortest_path(DG,'Start','End','weight') # the nodes are labeled by ind, so that's all this will return at the moment
	#print path
	return nodeList

def paths_to_leaves(digraph, sort_paths=False):
  '''Return paths from the root of the graph to each leaf. A path is a list of commits'''
  if len(digraph.nodes()) > 0:
    root = [n for n in digraph.nodes() if digraph.in_degree(n) == 0][0]
    leaves = [n for n in digraph.nodes() if digraph.out_degree(n) == 0]
    neg_graph = nx.DiGraph(digraph)
    for u, v in neg_graph.edges():
      neg_graph[u][v]['weight'] = -1
    pred, dist = nx.bellman_ford(neg_graph, root)
    dist_paths = []
    for leaf in leaves:
      path = [leaf]
      curr = leaf
      while pred[curr] is not None:
        curr = pred[curr]
        path.append(curr)
      path.reverse()
      dist_paths.append((-dist[leaf], path))
    if sort_paths is True:
      dist_paths = sorted(dist_paths, key=lambda x:-x[0])
    return dist_paths
  else:
    return None