def getGhostPath(self):
     try:
         path = nx.dijkstra_path(self.graph, self.node_ghost, self.node_pacman)
         return (nx.dijkstra_path(self.graph, self.node_ghost, self.node_pacman))
     except nx.NetworkXError:
         print("error")
         return self.graph.neighbors(self.node_ghost)

 def test_feasible(self, new_sites = []):  #considering deviation 
     sites = new_sites
     
     temp_route = []
     temp_time = 0 
     if len(sites) == 1:
         ori_route = networkx.dijkstra_path(self.graph, self.origin, sites[-1])
         if route_distance(ori_route) > driving_range/2:
             return False
         else:
             des_route = networkx.dijkstra_path(self.graph, sites[-1], self.destination)
             if route_distance(des_route) > driving_range/2:
                 return False
             else:
                 return True
     else:
         ind = True
         for i in range(len(sites)):
             if i == 0:
                 temp_route = networkx.dijkstra_path(self.graph, self.origin, sites[i])
                 if route_distance(temp_route) > driving_range/2:
                     ind = False
                     break
             elif i == len(sites):
                 temp_route = networkx.dijkstra_path(self.graph, sites[i], self.destination)
                 if route_distance(temp_route) > driving_range/2:
                     ind = False
                     break
             else:
                 temp_route = networkx.dijkstra_path(self.graph, sites[i], sites[i+1])
                 if route_distance(temp_route) > driving_range:
                     ind = False
                     break
         return ind        

def checkConnection(network, from_node_id, to_node_id):
	try:
		nx.dijkstra_path(\
			network, \
			from_node_id,\
			to_node_id\
		)
	except nx.exception.NetworkXNoPath, e:
		return False

def cost_nsplit(G,cur,tremdstlist):
 #*print "Entering cnsplit"
 cnsplit=[]
 next=[]
 next2=[]
 tremdstlist2=list(tremdstlist)
 tablensplit=[[]  for i in xrange(len(tremdstlist))]
 max_len=0
 result=[]
 max_len_path_list=[]
 num=0
 for j in tremdstlist:
     tablensplit[num]=nx.dijkstra_path(G,cur,tremdstlist[num]) # make a list of all paths
     if (tablensplit[num][1] not in next2):
         next2.append(tablensplit[num][1])                   # make a list of unique next hops
     if len(tablensplit[num])>max_len:
         max_len=len(tablensplit[num])
	 max_len_path_list=[]
	 max_len_path_list.append(tablensplit[num])
     if len(tablensplit[num])==max_len:
	 max_len_path_list.append(tablensplit[num])	
     num=num+1
 
 back_flag=0
 for path in max_len_path_list:
    for j in tremdstlist:
       if path[1]!=j and cur in nx.dijkstra_path(G,path[1],j):
        back_flag=1
        break
    if back_flag==0:
       result=[path[1],G.edge[cur][path[1]]['weight']+cost_split(G,path[1],tremdstlist)]	
    break	
 # Filter
 if result==[]: 
     to_del=[]
     for i in next2: 			# Remove those next hops that would possibly send pkt back to cur node
         for j in tremdstlist:
             if i==j:
                continue
             path=nx.dijkstra_path(G,i,j)  # Ignoring those next hops that are end destinations
             if cur in path:
                  to_del.append(i)
             break

     for elem in to_del:
        next2.remove(elem)

     if (len(next2)!=0):      
       cmin=G.edge[cur][next2[0]]['weight']+cost_split(G,next2[0],tremdstlist)
       best_next=next2[0]
     else:
       cmin=99999
       best_next=0
     result=[best_next,cmin]
 return result 

    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 get_laziest_path(self, start='Cover', \
                         end='THE END FOR REAL THIS TIME'):
        # calculated the shortest number of passages
        # turned through from starting passage
        spl = nx.dijkstra_path(self.G, start, end)
        # nx.set_node_attributes(self.G, 'lazy_{}_length'.format(start.lower()), spl)

        sp = nx.dijkstra_path(self.G, 'Cover', end)
        # nx.set_node_attributes(self.G, 'lazy_{}_path'.format(start.lower()), sp)

        return spl, sp

	def get_closest_parking_section(self, dstNodeId, tolerance=5):
		paths = []
		for i in self.find_entrances():
			path = nx.dijkstra_path(self.g, i, dstNodeId)
			while (self.g.node[path[-1]]['type'].upper() != 'PARKING'):
				path.pop()
			paths.append(path)

		destinations = []
		for i in xrange(0, len(paths)):
			destinations.append(paths[i][-1])

		for i in xrange(0,len(destinations)):
			section = self.g.node[destinations[i]]['section']
			free = float(section['capacity']) / section['max'] * 100
			prevFound = [destinations[i]]
			while (free < tolerance):
				destinations[i] = self.find_neighbor_with_parking_spots(destinations[i], exclude=prevFound)
				prevFound.append(destinations[i])
				section = self.g.node[destinations[i]]['section']
				free = float(section['capacity']) / section['max'] * 100

		if len(destinations) == 1:
			destinations = destinations[0]

		return destinations

def cost_split(G,cur,tremdstlist):
 
 csplit=0
 tablesplit=[[]  for i in xrange(len(tremdstlist))]
 num=0
 for j in tremdstlist:
    
     if (cur!=tremdstlist[num]):
           tablesplit[num]=nx.dijkstra_path(G,cur,tremdstlist[num])
     num=num+1
     
 
 csplit=nx.dijkstra_path_length(G,cur,tremdstlist[0])
 #print "CSPLIT added cost from :",cur, "to ",tremdstlist[0],"as ",length[cur][tremdstlist[0]]
 #*print "tablesplit[0]=",tablesplit[0]
 for x in xrange(1,num):
     curpath=tablesplit[x]
     
     for y in xrange(len(curpath)):
         if (y!=len(curpath)-1):
             
             if  ((curpath[y+1] in tablesplit[0]) !=True):
                 curwt=G.edge[curpath[y]][curpath[y+1]]['weight']
                 #print "CSPLIT : Adding [",curpath[y],"][",curpath[y+1],"]"
                 csplit=csplit+curwt
 return csplit

    def generateNextPill(self):
        list_nodes_temp = self.aStar(self.node_pacman, self.node_ghost,self.graph)
        list_nodes = []
        array_nodes = []
        manhattan = {'node':[], 'distance': 0}
        possible_options = self.graph.neighbors(self.node_pacman)
        for node in possible_options:
            path_total = nx.dijkstra_path(self.graph, self.node_ghost, self.node_pacman)
            len_path = len(path_total)
            if(self.manhattan(node,self.node_ghost) > manhattan['distance'] -10 and len_path>4):
                manhattan['node'].append(node)
                manhattan['distance'] = self.manhattan(node,self.node_ghost)
        random.shuffle(manhattan['node'])
        for node in manhattan['node'] :
            if(node.graph_node.has_image ==True):
                return node
        if(len(manhattan['node']) == 0):
            possible_options = self.graph.neighbors(self.node_pacman)
            best = {'node': None, 'distance': 0}
            for node in possible_options:
                if(self.manhattan(node, self.node_ghost)> best['distance']):
                    best['node'] = node
                    best['distance'] = self.manhattan(node, self.node_ghost)
            return best['node']



        return manhattan['node'][0]

    def label_url(self, loc1, loc2):
        # Connection string replaced with "" for security
        conn_str = ""

        # Connect to db
        conn = psycopg2.connect(conn_str)
        
        # Determine the path using Dijkstra's algorithm
        self.d_path = networkx.dijkstra_path(self.graph, loc1, loc2)
        # Add markers to the url
        count = 0
        alpha_list = list(string.ascii_uppercase)
        for city in self.d_path:
            lat, lng = self.get_coords(conn,city)
            self.url = self.url + "&markers=color:yellow%7Clabel:" +\
                       alpha_list[count] + "%7C" +\
                       str(lat) + "," + str(lng)
            count = count + 1

        # Add a path to the url
        path = "&path=color:blue"

        for city in self.d_path:
            lat, lng = self.get_coords(conn,city)
            path = path + "|" +\
                   str(lat) + "," + str(lng)
            

        self.url = self.url + path

 def find_path(self, source_id, target_id):
     if source_id == target_id:
         shortest_path = [source_id]
     else:
         shortest_path = nx.dijkstra_path(self.graph, source_id, target_id,
                                          'cost')
     return shortest_path

    def __init__(self,graph,links): #Try to get all the combination of switches and destination hosts. 
        self.switches = [] 
        self.hosts = []
        self.srcSwitchdstIPportNumMac = {}
        self.NextHopIP_PortNum = {}
        self.HipMac = {}
        self.graph = graph
        self.links = links
        temp = self.graph.nodes()
        temp.sort()
	for node in temp:
	    if 'h' in node:
		self.hosts.append(node)
	    elif 's' in node:
		self.switches.append(node)
        for key in temp:
            if key == 'h1':
                self.HipMac[key] = "00:00:00:00:00:01"
            if key == 'h2':
                self.HipMac[key] = "00:00:00:00:00:02"
            if key == 'h3':
                self.HipMac[key] = "00:00:00:00:00:03"
            if key == 'h4':
                self.HipMac[key] = "00:00:00:00:00:04"
	    if key == 'h5':
		self.HipMac[key] = "00:00:00:00:00:05"
	    if key == 'h6':
		self.HipMac[key] = "00:00:00:00:00:06"
    	for switch in self.switches:
            for host in self.hosts:
                ipSeries = nx.dijkstra_path(graph,switch,host)
                nextHop = ipSeries[1]
		#print self.links.getNextHopPort((switch,nextHop))
                self.srcSwitchdstIPportNumMac[(switch,host)] = (self.links.getNextHopPort((switch,nextHop)), self.HipMac[host]) 

def shortestWalk(g,line,mode):
    
    # Get index of closest nodes to line endpoints
    nPts = [g.node[n]["point"] for n in g]
    nPts = rc.Collections.Point3dList(nPts)
    start = nPts.ClosestIndex(line.From)
    end = nPts.ClosestIndex(line.To)
    
    # Check that start and are not the same node
    if start == end:
        
        print "Start and end node is the same"
        
    else:
        
        # Check that a path exist between the two nodes
        if hasPath(g,start,end):
            
            # Calculate shortest path
            
            if mode == "dijkstra_path":
                sp = nx.dijkstra_path(g,start,end,weight = "weight")
                
            elif mode == "shortest_path":
                sp = nx.shortest_path(g,start,end,weight = "weight")
                
            # Make polyline through path
            pts = [g.node[i]["point"] for i in sp]
            pl = rc.Geometry.PolylineCurve(pts)
            
            return pl

 def getShortestPath(self, source_switch_id, target_switch_id):
     self.setTopologyGraph()
     try:
         path = nx.dijkstra_path(self.topology, source_switch_id, target_switch_id, self.WEIGHT_PROPERTY_NAME)
     except nx.NetworkXNoPath:
         path = None
     return path

	def get_patterns_a(self):
		leaves = []
		root_name = "%s//%s" %(root, root.data)
		for n in G.nodes():
			if not nx.has_path(G, root_name, n):
				G.remove_node(n)
		# for n in nx.descendants(G, root_name):
			elif G.successors(n) == []:
				leaves.append(n)
		if leaves == []:
			print '\n******No Pattern******\n'
		else:
			print '\n******Patterns******\n'
			print '\nExtracted Pattern <%i>' %len(leaves)

		i = 0
		for n in leaves:
			pattern = []
			if nx.has_path(G, root_name, n):
				for p in nx.dijkstra_path(G, root_name, n):
					if G.node[p].has_key('fontcolor'):
						pattern.append(G.node[p]['label'].split(r'\n')[1])
					elif G.node[p] == {}:
						pass
					else:
						label = G.node[p]['label'].split(r'\n')[:-1]
						pattern.append('<%s>:{%s}' %(label[0].split('(')[0], ', '.join(label[1:])))
			print '%d:' %i, u'//'.join(pattern)
			i += 1

    def optimize(self, gs):
        comps = self._find_components()

        self._zdd = { 'B': Node('B %d B B ' % (len(self.switches) + 1)),
                      'T': Node('T %d T T ' % (len(self.switches) + 1)) }
        for line in gs.dumps().split('\n'):
            if line.startswith('.'):
                break
            n = Node(line)
            self._zdd[n.n] = n
            self.search_space.start = n.n

        entries = set([self.search_space.start])
        for comp in comps:
            entries = self._rebuild(entries, comp)

        self.search_space.end = 'T'

        path = nx.dijkstra_path(self.search_space.graph, self.search_space.start,
                                self.search_space.end)

        closed_switches = []
        for i in range(len(path) - 1):
            x, y = path[i], path[i + 1]
            closed_switches.extend(list(self.search_space.graph[x][y]['config']))

        return sorted(list(set(closed_switches)))

	def get_patterns_b(self):
		roots = []
		for n in G.nodes():
			if not nx.has_path(G, n, '1'):
				G.remove_node(n)
		# for n in nx.ancestors(G, '1'):
			elif G.predecessors(n) == []:
				roots.append(n)
		if roots == []:
			print '\n******No Pattern******\n'
		else:
			print '\n******Patterns******\n'
			print '\nExtracted Pattern <%i>' %len(roots)
		i = 0
		for n in roots:
			pattern = []
			if nx.has_path(G, n, '1'):
				for p in nx.dijkstra_path(G, n, '1')[:-1]:
					if G.node[p].has_key('fontcolor'):
						pattern.append(G.node[p]['label'].split(r'\n')[1])
					else:
						label = G.node[p]['label'].split(r'\n')[:-1]
						pattern.append('%s:{%s}' %(label[0].split('(')[0], ', '.join(label[1:])))
			print '%d:' %i, u' '.join(pattern)
			i += 1

def getFindedIndexes(str_len,e_list,delta):
    G = nx.Graph()
    G.add_node(0)
    G.add_node(str_len)

    # Добавление обычных переходов
    for elem in e_list:
        G.add_edge(elem[0], elem[1], weight=elem[1] - elem[0] - delta)

    # Добавление "нулевых" переходов
    for (u1,v1) in G.nodes(data='weight'):
        for (u2,v2) in G.nodes(data='weight'):
            if u1!=u2:
                if not(G.has_edge(u1,u2)):
                    w = 2+abs(u1-u2)**2
                    G.add_edge(u1,u2, weight=w)

        path_ = nx.dijkstra_path(G, 0, str_len)

    len_path = len(path_)

    findedIndexes = []

    for i in range(len_path):
        if i+1<len_path:
            for ind,x in enumerate(e_list):
                if x[0]==path_[i] and x[1]==path_[i+1]:
                    findedIndexes.append(ind)

    return findedIndexes

def experiment_4():
    G = nx.Graph()
    G.add_edge(0, 11, weight=91)
    G.add_edge(1, 11, weight=72)
    G.add_edge(1, 13, weight=96)
    G.add_edge(2, 13, weight=49)
    G.add_edge(2, 6, weight=63)
    G.add_edge(2, 3, weight=31)
    G.add_edge(3, 9, weight=98)
    G.add_edge(3, 7, weight=1)
    G.add_edge(3, 12, weight=59)
    G.add_edge(4, 7, weight=6)
    G.add_edge(4, 9, weight=6)
    G.add_edge(4, 8, weight=95)
    G.add_edge(5, 11, weight=44)
    G.add_edge(6, 11, weight=53)
    G.add_edge(8, 10, weight=2)
    G.add_edge(8, 12, weight=48)
    G.add_edge(9, 12, weight=32)
    G.add_edge(10, 14, weight=16)
    G.add_edge(11, 13, weight=86)

    G = nx.read_gpickle('G.gpickle')
    
    path_nx = nx.dijkstra_path(G, 0, 14)
    path = dijkstra(G, 0, 14, True)
    if path_cost(G, path) > path_cost(G, path_nx):
        print 'Error'
    else:
        print 'Correct'
        
    return locals()

def fish_distance(point1,point2):
    """
    Returns the shortest distance around land (see the Land model) between the two points.  Returns the distance in miles and
    the geos linestring that represents the path.
    
    NOTE: I'm assuming that the native units of the points and line is meters.  This is true for the MLPA project but may
    not be true for other processes.
    """
    # This is the straight line between the two points
    line = geos.LineString(point1,point2)
    
    # See if the straight line crosses land
    if line_crosses_land(line): 
        # The straight line cut across land so we have to do it the hard way.
        G = PickledGraph.objects.all()[0].graph
        G = add_points_to_graph([point1,point2],G)
        # G.add_nodes_from([point1,point2])
        # G = add_ocean_edges_for_node(G,get_node_from_point(G,point1))
        # G = add_ocean_edges_for_node(G,get_node_from_point(G,point2))
        # Replace the straight line with the shortest path around land
        line = geos.LineString( nx.dijkstra_path(G,get_node_from_point(G,point1),get_node_from_point(G,point2)) )
        line.srid = settings.GEOMETRY_DB_SRID
    
    # Figure out the distance of the line (straight or otherwise) in miles
    distance = length_in_display_units(line)
    return distance, line