def LabelFeature(self, graph):
        # for each graph
        # pick a random source and a random target
        # run each of the networkx src tgt shortest path algorithms one by one
        # time how long they each take
        # repeat for N different srcs/tgts
        # find the average time for each algorithm
        # make the label for that graph the one with the shortest time
        # feature key: 0 = dijkstra, 1 = bidijkstra 2 = astar
        numIters = 10
        n = networkx.number_of_nodes(graph)
        dijkstraTimes = np.zeros(numIters)
        biDijkstraTimes = np.zeros(numIters)
        aStarTimes = np.zeros(numIters)
        for i in xrange(numIters):
            # pick a random source and target
            src = np.random.randint(0, n) + 1
            tgt = np.random.randint(0, n) + 1
            while tgt == src:
                tgt = np.random.randint(0, n) + 1

            dijkstraTime = time.time()
            try:
                networkx.dijkstra_path(graph, src, tgt)
            except:
                # no path found
                i -= 1
                continue

            dijkstraTime = time.time() - dijkstraTime
            dijkstraTimes[i] = dijkstraTime

            biDijkstraTime = time.time()
            networkx.bidirectional_dijkstra(graph, src, tgt)
            biDijkstraTime = time.time() - biDijkstraTime
            biDijkstraTimes[i] = biDijkstraTime

            aStarTime = time.time()
            networkx.astar_path(graph, src, tgt)
            aStarTime = time.time() - aStarTime
            aStarTimes[i] = aStarTime

        meanDijkstra = np.mean(dijkstraTimes)
        meanBiDijkstra = np.mean(biDijkstraTimes)
        meanAStar = np.mean(aStarTimes)

        minTime = min(meanDijkstra, meanBiDijkstra, meanAStar)
        if meanDijkstra == minTime:
            label = 0
        elif meanBiDijkstra == minTime:
            label = 1
        else:
            label = 2

        return label

 def traceEndpoints(self, key=0):
     """Uses the bidirectional dijkstra to traceback the paths from the endpoints"""
     og = nx.DiGraph(spacing=None, origin=None, orientation=None)
     self._populateImageFeaturesToGraph(og)
     currentRoot = self.roots[(self.currentGraphKey,key)]
     og.graph["root"] = currentRoot
     endpoints = self.endpoints[self.currentGraphKey]
     bifurcations = self.bifurcations[self.currentGraphKey]
     cg = self.graphs[self.currentGraphKey]
     if( self.VERBOSE ):
         print("current root is",currentRoot)
     for e in endpoints:
         plen, path = nx.bidirectional_dijkstra(cg, currentRoot, e)
         i = 0
         start = currentRoot
         path = path[1:]
         while( path ):               
             try:
                 if( path[i] in bifurcations ):
                     og.add_edge(start,path[i],path=path[:i])
                     start = path[i]
                     path = path[i+1:]
                     i = 0
                 else:
                     i += 1
             except IndexError:
                 og.add_edge(start,e,{'path':path[:-1]})
                 path = None
     self.orderedGraphs[(self.currentGraphKey,key)] = og

    def set_random_loads(max_for_each_route):
        scheme_len = len(SystemBuilder.scheme.node)
        for route in SystemBuilder.routes:
            for k in range(int(random() * max_for_each_route)):

                dispatch_st_num = route.route_list[int(random() * route.length())]

                destination_is_founded = False
                counter = 0
                while not destination_is_founded:
                    counter += 1
                    assert counter < 999
                    destination_st_num = int(random() * scheme_len) + 1
                    try:
                        way_length, way_list = nx.bidirectional_dijkstra(
                            SystemBuilder.routes_scheme, dispatch_st_num, destination_st_num)
                        new_growth_coeff = GrowthCoeff(RandomFunctions.growth_coef_func(), way_list)
                        destination_is_founded = True
                        SystemBuilder.growth_coeffs.append(new_growth_coeff)
                        attr_name = SystemBuilder.ATTRIBUTE_GROWTH_LIST
                        SystemBuilder.scheme.node[dispatch_st_num][attr_name].append(new_growth_coeff)
                    except nx.exception.NetworkXError:
                        pass
                    except nx.exception.NetworkXNoPath:
                        pass

    def getPath(self, nd0, nd1, weight_name):
        
        try:
            _, nodes = networkx.bidirectional_dijkstra(
                self.digraph,
                nd0, nd1,
                weight_name
            )
        except networkx.NetworkXNoPath:
            raise NoPath('no path found between the points')


        def getKey(u, v):
            keys = []
            for k in self.digraph[u][v]:
                weight = self.digraph[u][v][k][weight_name]
                keys.append((weight, k))
            keys.sort()
            return keys[0][1]

        keys = []
        for a, b in zip(nodes[:-1], nodes[1:]):
            k = getKey(a,b)
            keys.append(k)

        return nodes, keys

def find_path(n1, n2, skip = []):
    start = time.time()
    path = None
    status = 'ok'

    a1 = find_artist(n1)
    a2 = find_artist(n2)

    if not a1:
        status = "Can't find " + n1
    if not a2:
        status = "Can't find " + n2

    if a1 and a2:
        if skip and len(skip) > 0:
            # graph = G.copy()
            graph = G
        else:
            graph = G

        remove_nodes(graph, skip)
        try:
            l, path = nx.bidirectional_dijkstra(graph, a1['id'], a2['id'], 'weight')

        except nx.NetworkXNoPath:
            status = 'No path found between ' + n1 + " and " + n2;
            
        restore_nodes(graph, skip)

    print 'find_path took %s seconds' % (time.time() - start,)
    return status, path

 def _areConnected(self, minkey1, minkey2):
     try:
         ret = nx.bidirectional_dijkstra(self.graph, minkey1, minkey2)
         if ret != None:
             return True
         else: return False
     except nx.NetworkXNoPath:
         return False

    def findNeighbours(src, dest):
        
        G = nx.Graph()
        db = MySQLdb.connect(host = "localhost", user = "root", passwd = "", db = "project")
        cursor = db.cursor()
        cursor.execute("SELECT * FROM nodes")
        for row in cursor.fetchall():
            G.add_node(int(row[0]))
         
        cursor.execute("SELECT * FROM lanes")
        for row in cursor.fetchall():
            G.add_edge(int(row[1]), int(row[2]))
            G[row[1]][row[2]]['weight'] = row[3]
         
        print G.edges()
        print G.nodes()
        
        query = "SELECT node_id FROM locations WHERE name like '" + src + "'"
        cursor.execute(query)
        try:
            fetch = cursor.fetchall()
            source = fetch[0][0]

            query = "SELECT node_id FROM locations WHERE type = '" + dest + "'"
            print query
            cursor.execute(query)
            results = cursor.fetchall()
            print results
            
            F = []
            for x in results:
                temp = nx.bidirectional_dijkstra(G, source, int(x[0]), weight = 'weight')
                F.append(temp)
            
            maxval = min(F[0:])
            index = []
            for ctr in range(len(F)):
                if F[ctr][0] == maxval[0]:
                    index.append(ctr)

            cursor.execute("SELECT nodes.node_id, nodes.x, nodes.y, name from nodes left join locations on nodes.node_id = locations.node_id")
            results = cursor.fetchall()
            Pathlist = []
            for y in index:
                A = []
                for x in F[y][1]:
                    for row in results:
                        if x == row[0]:
                            A.append((row[1],row[2],row[3]))
                Pathlist.append(A)
                
            return Pathlist
            
        except:
            print "Invalid Query"
            return []

 def areConnected(self, min1, min2):
     return self.connected_components.areConnected(min1, min2)
     try:
         ret = nx.bidirectional_dijkstra(self.graph, min1, min2)
         if ret != None:
             return True
         else: 
             return False
     except nx.NetworkXNoPath:
         return False

    def get_distance(self,source,sink):
        """
        find shortest path length
        """

        minDistance = 1e8
        if self.G.has_node(source) and self.G.has_node(sink):
            (dijkDist, dijkPath) = nx.bidirectional_dijkstra(self.G,source,sink)
            return dijkDist
        return None

 def _search_grammer_path(self, pos_via_point):
     pos_via_and_end = (self.START_NODE,) + pos_via_point + (self.END_NODE,)
     paths = []
     cost = 0
     for network_start_end in sliding_window(2, pos_via_and_end):
         path = networkx.bidirectional_dijkstra(self._grammer_graph, network_start_end[0], network_start_end[1])
         cost += path[0]
         node_path = path[1][1:]
         paths += node_path
     paths.pop()
     return cost, paths

def qfind(a1, a2):
    start = time.time()
    path = None

    if a1 and a2:
        graph = G
        try:
            l, path = nx.bidirectional_dijkstra(graph, a1['id'], a2['id'], 'weight')
        except nx.NetworkXNoPath:
            pass
    return path

    def path(self, source_name, target_name, skipset=set()):
        def get_weight(src, dest, attrs):
            if src in skipset or dest in skipset:
                # print "gw", srx, dest, attrs, 10000
                return 10000
            # print "gw", src, dest, attrs, 1
            return attrs['weight']

        results = { 
            'status': 'ok'
        }

        if len(source_name) == 0:
            results['status'] = 'error'
            results['reason'] = "No artist given"
        else:
            source_aid = self.search(source_name)
            if source_aid == None:
                results['status'] = 'error'
                results['reason'] = "Can't find " + source_name

            target_aid = self.search(target_name)
            if target_aid == None:
                results['status'] = 'error'
                results['reason'] = "Can't find " + target_name

            print "s=t", source_aid, target_aid
            if source_aid not in self.G:
                results['status'] = 'error'
                results['reason'] = "Can't find " + source_name + " in the artist graph"

            if target_aid not in self.G:
                results['status'] = 'error'
                results['reason'] = "Can't find " + target_name + " in the artist graph"

        if source_aid and target_aid and results['status'] == 'ok':
            start = time.time()
            if len(skipset) > 0:
                rpath = nx.dijkstra_path(self.G, source_aid, target_aid, get_weight)
                score = len(rpath)
            else:
                score, rpath = nx.bidirectional_dijkstra(self.G, source_aid, target_aid)
            pdelta = time.time() - start
            results['score'] = score
            populated_path = [self.get_artist(aid) for aid in rpath]
            fdelta = time.time() - start
                
            results['status'] = 'ok'
            results['raw_path'] = rpath
            results['path'] = populated_path
            results['pdelta'] = pdelta * 1000
            results['fdelta'] = fdelta * 1000
        return results

    def _dijkstra(self, verbose, debug):
        try:
            if verbose:
                print('Dijkstra algorithm', flush=True)

            length,triPath=nx.bidirectional_dijkstra(self._tGraph, self._startTriplet, self._endTriplet)


        except (nx.NetworkXNoPath, nx.NetworkXError):
            print('ERROR: Impossible to find a path')
            triPath = []

        return triPath

def get_best_path (init_dest, final_dest):
    DG = makeDiGraph()
    x= findCommonRoutes(init_dest, final_dest, DG)
    # check if any common bus is active
    activeRoutes = isActive(x)
    if(len(activeRoutes) == 0):
        print "You are fucked, buddy. No active routes"
    else:
        print activeRoutes
        # TOTAL TIME incomplete !!
        total_time(x,init_dest, activeRoutes)
        best = (nx.bidirectional_dijkstra(DG, init_dest, final_dest , weight = 'edge_weight') )
        print (best)

def mp_worker((source,sink,graphPath)):
    """
    find shortest path length
    """
    G = nx.read_gpickle(graphPath)
    minDistance = 1e8
    if G.has_node(source) and G.has_node(sink):
        (dijkDist, dijkPath) = nx.bidirectional_dijkstra(G,source,sink)
    else:
        dijkDist = None
    
    if dijkDist:
        return [source,sink,dijkDist]

    def build_random_routes(attempts_num, min_len):
        scheme_len = len(SystemBuilder.scheme.node)
        k = 0
        while k < attempts_num:
            first_station_number = int(random() * scheme_len) + 1
            second_station_number = int(random() * scheme_len) + 1
            way_len, way_list = \
                nx.bidirectional_dijkstra(SystemBuilder.scheme, first_station_number, second_station_number)
            if way_len >= min_len:
                way_list = way_list + way_list[::-1][1:]
                new_route = Route(way_list, RandomFunctions.launch_cost_func(way_list))
                SystemBuilder.routes.append(new_route)
            k += 1

        SystemBuilder._create_routes_scheme()

    def test_bidirectional_dijkstra(self):
        assert_equal(nx.bidirectional_dijkstra(self.XG, "s", "v"), (9, ["s", "x", "u", "v"]))
        assert_equal(nx.bidirectional_dijkstra(self.G, "s", "v"), (2, ["s", "x", "v"]))
        assert_equal(nx.bidirectional_dijkstra(self.cycle, 0, 3), (3, [0, 1, 2, 3]))
        assert_equal(nx.bidirectional_dijkstra(self.cycle, 0, 4), (3, [0, 6, 5, 4]))
        assert_equal(nx.bidirectional_dijkstra(self.XG3, 0, 3), (15, [0, 1, 2, 3]))
        assert_equal(nx.bidirectional_dijkstra(self.XG4, 0, 2), (4, [0, 1, 2]))

        # need more tests here
        assert_equal(nx.dijkstra_path(self.XG, "s", "v"), nx.single_source_dijkstra_path(self.XG, "s")["v"])

 def quickest_route(self, source, target, est_time=7200):
     """
     INPUT: source node 'stopid_timestamp' (a stop_timepoint string)
            target node stop_id
            estimated trip time in seconds
     OUTPUT: path_time (seconds), path (list of stop_timepoints)
            
     """
     t1 = source[-8:]
     p_t, p = None, None
     for n in self.schedule.all_stop_timepoints[target][::-1]:
         t2 = n[-8:]
         if (t2 > t1) and (ut.diff_timestamps(t1, t2) < est_time):
             try:
                 p_t, p = nx.bidirectional_dijkstra(self.G, source, n, weight='bees')
             except nx.NetworkXNoPath:
                 return p_t, p

  def obj_get_list(self, bundle, **kwargs):
    from_id = int(bundle.request.GET.get('from_id', -1))
    to_id = int(bundle.request.GET.get('to_id', -1))

    if from_id != -1 and to_id != -1:
      from_building = Building.objects.get(id=from_id)
      to_building = Building.objects.get(id=to_id)

      node_from_id = from_building.centroid_id
      node_to_id = to_building.centroid_id

      lz = LazyGraph()
      length, path = nx.bidirectional_dijkstra(lz.get_graph(), node_from_id, node_to_id, weight='weight')

      return [Node.objects.get(id=x) for x in path]

    return []

def hop_counts(graph, cutoff = None, samples = 100000):
	"""
		Calculating the length (in number of hops) with nodes  using dijkstra algorithm. 
		The input graph will be automaically turned into an undirected simple graph without loops.
		Note the function only focus on the largest connected component if graph is disconnected.

		To reduce the computation complexity, sampling method is used by default. Can use the argument
		'samples' to control the number of samples.

		Parameters:
		-----------
			graph: Networkx Graph, NetworkX DiGraph,
			cutoff: integer or float, optional
				Depth to stop search. Only paths of length <= cutoff are counted
			samples: int
				The number of sampling node pairs in order 
				If samples equals to 0, then all pairs of nodes will be included.
		Returns:
		--------
			a dictionary, keyed by hop count, of number of paths with specific hops
	"""
	graph = to_undirected(graph)
	from collections import Counter
	cnt = Counter()
	if samples > 0:
		def gen_pairs(p, n):
			"""
				generting the sampling node pairs.
				duplicated pairs is possible, but self loop is impossible
			"""
			import random
			random.seed()
			pairs = [ random.sample(p, 2) for s in xrange(n) ]
			return(pairs)
		pairs = gen_pairs(nx.connected_components(graph)[0], samples)
		pair_lens = map(lambda x: nx.bidirectional_dijkstra(graph, x[0], x[1], weight = None)[0], pairs)
		if cutoff: pair_lens = filter(lambda x: x <= cutoff, pair_lens)
		for pl in iter(pair_lens):
			cnt[pl] += 1
	else:
		plDict = nx.all_pairs_dijkstra_path_length(graph, cutoff = cutoff)
		for p in plDict.itervalues():
			for d in p.itervalues():
				cnt[d] += 1
	return(dict(cnt))