Python networkx 模块，shortest_path() 实例源码

def _check_instance(hierarchy, graph_id, pattern, instance, pattern_typing):
    check_homomorphism(
        pattern,
        hierarchy.node[graph_id].graph,
        instance,
        total=True
    )
    # check that instance typing and lhs typing coincide
    for node in pattern.nodes():
        if pattern_typing:
            for typing_graph, typing in pattern_typing.items():
                try:
                    instance_typing = hierarchy.compose_path_typing(
                        nx.shortest_path(hierarchy, graph_id, typing_graph))
                    if node in pattern_typing.keys() and\
                       instance[node] in instance_typing.keys():
                        if typing[node] != instance_typing[instance[node]]:
                            raise RewritingError(
                                "Typing of the instance of LHS does not " +
                                " coincide with typing of LHS!")
                except NetworkXNoPath:
                    raise RewritingError(
                        "Graph '%s' is not typed by '%s' specified "
                        "as a typing graph of the lhs of the rule." %
                        (graph_id, typing_graph))

def get_paths_of_length(self, source, num_hops=1):
        """ Searchs for all nodes that are `num_hops` away.

        Returns:
            list of paths: A list of all shortest paths that have length
            `num_hops + 1`
        """
        # return a dictionary keyed by targets
        # with a list of nodes in a shortest path
        # from the source to one of the targets.
        all_paths = networkx.shortest_path(self.graph, source)

        return [
            path
            for path in all_paths.values()
            if len(path) == num_hops + 1
        ]

def compute_shortest_path_tree(self, dst_sw):

        spt = nx.DiGraph()

        mdg = self.network_graph.get_mdg()

        paths = nx.shortest_path(mdg, source=dst_sw.node_id)

        for src in paths:

            if src == dst_sw.node_id:
                continue

            for i in range(len(paths[src]) - 1):
                spt.add_edge(paths[src][i], paths[src][i+1])

        return spt

def test_routing_folium():

    import networkx as nx
    with httmock.HTTMock(get_mock_response_content('overpass-response-3.json.gz')):
        G = ox.graph_from_address('398 N. Sicily Pl., Chandler, Arizona', distance=800, network_type='drive')
    origin = (33.307792, -111.894940)
    destination = (33.312994, -111.894998)
    origin_node = ox.get_nearest_node(G, origin)
    destination_node = ox.get_nearest_node(G, destination)
    route = nx.shortest_path(G, origin_node, destination_node)

    attributes = ox.get_route_edge_attributes(G, route, 'length')

    fig, ax = ox.plot_graph_route(G, route, save=True, filename='route', file_format='png')
    fig, ax = ox.plot_graph_route(G, route, origin_point=origin, destination_point=destination,
                                  save=True, filename='route', file_format='png')

    graph_map = ox.plot_graph_folium(G, popup_attribute='name')
    route_map = ox.plot_route_folium(G, route)

def ShortestPathInstall(self, ev, src, dst):
            #Compute shortest path
            path = nx.shortest_path(self.directed_Topo, src, dst)

            #Backup path
            str_path = str(path).replace(', ', ',')
            self.path_db.append(path)

            #Add Flow along with the path
            for k, sw in enumerate(self.switches):
                if sw in path:
                    next = path[path.index(sw)+1]

                    out_port = self.directed_Topo[sw][next]['port']

                    actions = [self.switches_dp[k].ofproto_parser.OFPActionOutput(out_port)]
                    match = self.switches_dp[k].ofproto_parser.OFPMatch(eth_src=src, eth_dst=dst)
                    self.add_flow(self.switches_dp[k], 1, match, actions, ev.msg.buffer_id)

    #Add host and adjacent switch to directed_Topo

def _check_instance(hierarchy, graph_id, pattern, instance, pattern_typing):
    check_homomorphism(
        pattern,
        hierarchy.node[graph_id].graph,
        instance,
        total=True
    )
    # check that instance typing and lhs typing coincide
    for node in pattern.nodes():
        if pattern_typing:
            for typing_graph, typing in pattern_typing.items():
                try:
                    instance_typing = hierarchy.compose_path_typing(
                        nx.shortest_path(hierarchy, graph_id, typing_graph))
                    if node in pattern_typing.keys() and\
                       instance[node] in instance_typing.keys():
                        if typing[node] != instance_typing[instance[node]]:
                            raise RewritingError(
                                "Typing of the instance of LHS does not " +
                                " coincide with typing of LHS!")
                except NetworkXNoPath:
                    raise RewritingError(
                        "Graph '%s' is not typed by '%s' specified "
                        "as a typing graph of the lhs of the rule." %
                        (graph_id, typing_graph))

def notify_alert_response(self, responder, alert_ctx, mdmt_used):
        """
        Updates view of current network topology state based on the route traveled by this response.  Also records that
        this subscriber was reached so that future re-tries don't worry about reaching it.
        :param responder:
        :param alert_ctx:
        :type alert_ctx: RideD.AlertContext
        :param mdmt_used: we require this instead of gleaning it from the alert_ctx since this response may have been
        sent before the most recent alert attempt (i.e. we might calculate the response route wrong)
        :return:
        """

        # determine the path used by this response and notify RideD that it is currently functional
        route = nx.shortest_path(mdmt_used, self.get_server_id(), responder)
        log.debug("processing alert response via route: %s" % route)

        # NOTE: this likely won't do much as we probably already selected this MDMT since this route was functional...
        self.stt_mgr.route_update(route)

        alert_ctx.record_subscriber_reached(responder)

        if not alert_ctx.has_unreached_subscribers():
            log.info("alert %s successfully reached all subscribers! closing..." % alert_ctx)
            self.cancel_alert(alert_ctx, success=True)

def _get_shortest__path_between_subgraphs_helper(graph, a, b):
    """Calculate the shortest path that occurs between two disconnected subgraphs A and B going through nodes in
    the source graph

    :param nx.MultiGraph graph: A graph
    :param nx.MultiGraph a: A subgraph of :code:`graph`, disjoint from :code:`b`
    :param nx.MultiGraph b: A subgraph of :code:`graph`, disjoint from :code:`a`
    :return: A list of the shortest paths between the two subgraphs
    :rtype: list
    """
    shortest_paths = []

    for na, nb in itt.product(a, b):
        a_b_shortest_path = nx.shortest_path(graph, na, nb)
        shortest_paths.append(a_b_shortest_path)

        b_a_shortest_path = nx.shortest_path(graph, nb, na)
        shortest_paths.append(b_a_shortest_path)

    min_len = min(map(len, shortest_paths))
    return [p for p in shortest_paths if len(p) == min_len]

def InternalRecovery(code, terminal1, terminal2, type, charge_type):
    measure_chain = nx.shortest_path(code.Dual[type], terminal1, terminal2)
    chain_length = nx.shortest_path_length(code.Dual[type], terminal1, terminal2)
    for link in range(chain_length):
        vertex1 = measure_chain[link]
        vertex2 = measure_chain[link + 1]
        for data_qubit in code.Stabilizers[type][vertex1]['data']:
            if data_qubit in code.Stabilizers[type][vertex2]['data']:
                prior_charge = code.Primal.node[data_qubit]['charge'][charge_type]
                code.Primal.node[data_qubit]['charge'][charge_type] = (prior_charge + 1) % 2

    return code

def getOwnerToOwnerCentrality(self, graph):
        """ compute the network centrality of all the nodes owned by a person
        with respect to all shortest paths beteween any owner"""

        nodeOwner = {}  # node -> owner
        ownerNodes = defaultdict(list)  # owner -> [nodes]
        ownerCentrality = defaultdict(int)
        ownerNodes, nodeOwner = self.get_owner_distribution(graph)
        counter = 0
        shortestPathAndDistance = {}
        for n in graph.nodes():
            shortestPathAndDistance[n] = nx.single_source_dijkstra(graph, n)
            # returns a couple (distance, path)
        for i in range(len(ownerNodes)):
            from_owner, from_nodes = ownerNodes.items()[i]
            for j in range(i+1, len(ownerNodes)):
                to_owner, to_nodes = ownerNodes.items()[j]
                shortest_path = []
                shortest_cost = 0
                for s in from_nodes:
                    for d in to_nodes:
                        if not shortest_path or shortestPathAndDistance[s][0][d] < shortest_cost:
                                shortest_path = shortestPathAndDistance[s][1][d]
                                shortest_cost = shortestPathAndDistance[s][0][d]
                counter += 1
                path_set = set([nodeOwner[node] for node in shortest_path])
                for o in path_set:
                    ownerCentrality[o] += 1
        print "# owner".rjust(long_align_space), ",",\
              "owner-to-owner cent.".rjust(long_align_space)
        for (p, c) in sorted(ownerCentrality.items(), key=lambda x: -x[1]):
            print p.rjust(long_align_space), ",",\
                str(c*1.0/counter).rjust(long_align_space)
        print ""
        print ""
        return ownerCentrality, counter

def compute_path_intents(self, fs):

        intent_list = []

        fs.path = nx.shortest_path(self.network_graph.graph,
                                   source=fs.ng_src_host.node_id,
                                   target=fs.ng_dst_host.node_id,
                                   weight='weight')

        # Get the port where the host connects at the first switch in the path
        link_ports_dict = self.network_graph.get_link_ports_dict(fs.ng_src_host.node_id, fs.ng_src_host.sw.node_id)
        in_port = link_ports_dict[fs.ng_src_host.sw.node_id]

        # This loop always starts at a switch
        for i in range(1, len(fs.path) - 1):

            link_ports_dict = self.network_graph.get_link_ports_dict(fs.path[i], fs.path[i+1])

            fwd_flow_match = deepcopy(fs.flow_match)

            mac_int = int(fs.ng_src_host.mac_addr.replace(":", ""), 16)
            fwd_flow_match["ethernet_source"] = int(mac_int)

            mac_int = int(fs.ng_dst_host.mac_addr.replace(":", ""), 16)
            fwd_flow_match["ethernet_destination"] = int(mac_int)

            intent = Intent("primary",
                            fwd_flow_match,
                            in_port,
                            link_ports_dict[fs.path[i]],
                            True)

            # Store the switch id in the intent
            intent.switch_id = fs.path[i]

            intent_list.append(intent)
            in_port = link_ports_dict[fs.path[i+1]]

        return intent_list

def get_shortest_path(self, nx_graph, src_dpid, dst_dpid):

        if nx.has_path(nx_graph, src_dpid, dst_dpid):
            return nx.shortest_path(nx_graph, src_dpid, dst_dpid)

        return None

def get_shortest_path(self, nx_graph, src_dpid, dst_dpid):

        if nx.has_path(nx_graph, src_dpid, dst_dpid):
            return nx.shortest_path(nx_graph, src_dpid, dst_dpid)

        return None

def get_shortest_path(self, nx_graph, src_dpid, dst_dpid):

        if nx.has_path(nx_graph, src_dpid, dst_dpid):
            return nx.shortest_path(nx_graph, src_dpid, dst_dpid)

        return None

def get_conversion_path(self, start_type, target_type):
        start_type = self._normalise_type(start_type)
        target_type = self._normalise_type(target_type)
        try:
            # Retrieve node sequence that leads from start_type to target_type.
            path = networkx.shortest_path(self.conversion_graph, start_type, target_type)
            # Look up edges between nodes and retrieve the conversion function for each edge.
            return [self.conversion_graph.get_edge_data(node_a, node_b)['conversion_function'] for node_a, node_b in
                    zip(path[:-1], path[1:])]
        except networkx.NetworkXNoPath:
            raise UndefinedConversionError(
                start_type,
                target_type,
            )

def find_tree(sub_network, weight='x_pu'):
    """Get the spanning tree of the graph, choose the node with the
    highest degree as a central "tree slack" and then see for each
    branch which paths from the slack to each node go through the
    branch.

    """

    branches_bus0 = sub_network.branches()["bus0"]
    branches_i = branches_bus0.index
    buses_i = sub_network.buses_i()

    graph = sub_network.graph(weight=weight)
    sub_network.tree = nx.minimum_spanning_tree(graph)

    #find bus with highest degree to use as slack
    tree_slack_bus, slack_degree = max(degree(sub_network.tree), key=itemgetter(1))
    logger.info("Tree slack bus is %s with degree %d.", tree_slack_bus, slack_degree)

    #determine which buses are supplied in tree through branch from slack

    #matrix to store tree structure
    sub_network.T = dok_matrix((len(branches_i),len(buses_i)))

    for j,bus in enumerate(buses_i):
        path = nx.shortest_path(sub_network.tree,bus,tree_slack_bus)
        for i in range(len(path)-1):
            branch = next(iterkeys(graph[path[i]][path[i+1]]))
            branch_i = branches_i.get_loc(branch)
            sign = +1 if branches_bus0.iat[branch_i] == path[i] else -1
            sub_network.T[branch_i,j] = sign

def get_shortest_distance(pair_id):
    global graph
    id_1 = int(pair_id.split('_')[0])
    id_2 = int(pair_id.split('_')[1])
    try:
        return len(nx.shortest_path(graph, source=id_1, target=id_2)) - 1
    except:
        return -1

def timeit_summarize():
  global global_timeit_dict
  pass

# graph traversal
# computation flows from parents to children
# to find path from target to dependency, do
# nx.shortest_path(gg, dependency, target)

def shortest_path(dep, target):
  if hasattr(dep, "op"):
    dep = dep.op
  if hasattr(target, "op"):
    target = target.op
  return nx.shortest_path(nx_graph(), dep, target)

def timeit_summarize():
  global global_timeit_dict
  pass

# graph traversal
# computation flows from parents to children
# to find path from target to dependency, do
# nx.shortest_path(gg, dependency, target)

def shortest_path(dep, target):
  if hasattr(dep, "op"):
    dep = dep.op
  if hasattr(target, "op"):
    target = target.op
  return nx.shortest_path(nx_graph(), dep, target)

def timeit_summarize():
  global global_timeit_dict
  pass

# graph traversal
# computation flows from parents to children
# to find path from target to dependency, do
# nx.shortest_path(gg, dependency, target)

def timeit_summarize():
  global global_timeit_dict
  pass

# graph traversal
# computation flows from parents to children
# to find path from target to dependency, do
# nx.shortest_path(gg, dependency, target)

def shortest_path(dep, target):
  if hasattr(dep, "op"):
    dep = dep.op
  if hasattr(target, "op"):
    target = target.op
  return nx.shortest_path(nx_graph(), dep, target)

def timeit_summarize():
  global global_timeit_dict
  pass

# graph traversal
# computation flows from parents to children
# to find path from target to dependency, do
# nx.shortest_path(gg, dependency, target)

def shortest_path(dep, target):
  if hasattr(dep, "op"):
    dep = dep.op
  if hasattr(target, "op"):
    target = target.op
  return nx.shortest_path(nx_graph(), dep, target)

def timeit_summarize():
  global global_timeit_dict
  pass

# graph traversal
# computation flows from parents to children
# to find path from target to dependency, do
# nx.shortest_path(gg, dependency, target)

def getNextNodeInShortestPath(self, currentNode, goalNode):
        path = nx.shortest_path(self.g, currentNode, goalNode, weight = 'weight')
        if len(path) ==1:
            return path[0]
        else:
            return path[1]

    # Finds the next node in the path to the nearest node with unvisited paths

def getNextNodeToNearestUnvisited(self, currentNode):
        nearestUnvisited = self.getNearestUnvisited(currentNode)
        path = nx.shortest_path(self.g, currentNode, nearestUnvisited, weight = 'weight')
        if len(path) == 1:
            print "Next node with unvisited paths: ", path[0].uid, " (current node)"
            return path[0]
        else:
            print "Next node with unvisited paths: ", path[1].uid
            return path[1]

def add_edge(self, u, v, *args, **kwargs):
        changed = False
        if u == v:
            if self.flags['strict']:
                raise ValueError('Edge must be between two unique nodes!')
            return changed
        if self._undirected.has_edge(u, v):
            self.remove_edges_from([[u, v], [v,u]])
        elif len(self.nodes()) > 0:
            try: 
                path = nx.shortest_path(self._undirected, u, v)
                if self.flags['strict']:
                    raise ValueError('Multiple edge path exists between nodes!')
                self.disconnect_path(path)
                changed = True
            except (nx.NetworkXError, nx.NetworkXNoPath):
                pass
        self._undirected.add_edge(u,v)
        super(self.__class__, self).add_edge(u, v, *args, **kwargs)

        if self.flags['assert_forest']:
            # this is quite slow but makes very sure structure is correct 
            # so is mainly used for testing
            assert nx.is_forest(nx.Graph(self))

        return changed

def shortest_path_undirected(self, u, v):
        path = nx.shortest_path(self._undirected, u, v)
        return path

def _path_exists(graph, source, target):
    try:
        path = networkx.shortest_path(graph, source, target)
    except NetworkXException:
        path = []
    return bool(path)

def guess(graph, question, choices):
    MAX = 9999
    SUBMAX = 999
    ques_node = find_node(graph, question)
    dists = []
    for choice in choices:
        choice_node = find_node(graph, choice)
        if ques_node is None and choice_node is None:
            dist = MAX
        elif ques_node is None and choice_node is not None:
            dist = SUBMAX
        elif ques_node is not None and choice_node is None:
            dist = MAX
        else:
            if nx.has_path(graph, ques_node, choice_node):
                pl = len(nx.shortest_path(graph, ques_node, choice_node))
                dist = pl
            else:
                dist = MAX
        dists.append(dist)
    answer, dist = min(enumerate(dists), key=lambda x: x[1])
    max_dist = max(dists)
    if dist == MAX:
        return None
    if dist == max_dist:
        return None
    return answer

def getHopsTo(self, link):
        assert link != self
        path = networkx.shortest_path(
            sg.gnGraph.netGraph,
            self.as_nodeA,
            link.as_nodeA
        )
        path.remove(self.as_nodeA)
        path.remove(link.as_nodeA)
        if self.as_nodeB in path:
            path.remove(self.as_nodeB)
        if link.as_nodeB in path:
            path.remove(link.as_nodeB)
        return len(path) + 1

def get_path(self, source, destination):
        """Gets shortest path by weight attribute between the nodes.
        @:return a sequence of nodes representing the shortest path"""

        return nx.shortest_path(self.topo, source=source, target=destination)

def get_path(self, source, destination, weight='weight'):
        """Gets shortest path by the optionally specified weight attribute between the nodes.
        @:return a sequence of nodes representing the shortest path"""

        return nx.shortest_path(self.topo, source=source, target=destination, weight=weight)

def deploy_controller(self, sw, sw_to_ctrl_delays):
        sw_to_ctrl_delays[sw] = 0
        shortest_paths = nx.shortest_path(self.graph, target=sw, weight='delay')
        shortest_path_lengths = nx.shortest_path_length(self.graph, target=sw, weight='delay')
        log.info(shortest_paths)
        for n in self.graph.nodes():
            if n == sw:
                continue
            if n in shortest_path_lengths.keys():
                sw_to_ctrl_delays[n] = shortest_path_lengths[n]
            else:
                sw_to_ctrl_delays[n] = 1
        log.debug("sw to ctrl delays: %s" % str(sw_to_ctrl_delays))

def DSP_Path(DualGraph, terminal1, terminal2):
    return nx.shortest_path(DualGraph, terminal1, terminal2)

def hasConnectedBoundaries(code, loops_graph, Exts):
    if len(loops_graph.edges()) <= 1:
        return False
    for ext1 in loops_graph.nodes():
        for ext2 in loops_graph.nodes():
            if ext1 in Exts and ext2 in Exts and ext1 != ext2:
                if nx.has_path(loops_graph,ext1,ext2):
                    path = nx.shortest_path(loops_graph, ext1, ext2)
                    for node in path:
                        if node not in Exts:
                            return True
    return False

def connectedBoundaries(loops_graph, Exts):
    for ext1 in loops_graph.nodes():
        for ext2 in loops_graph.nodes():
            if ext1 in Exts and ext2 in Exts and ext1 != ext2:
                if nx.has_path(loops_graph,ext1,ext2):
                    path = nx.shortest_path(loops_graph, ext1, ext2)
                    for node in path:
                        if node not in Exts:
                            return ext1, ext2

def BoundTransport(code, fixed_node, mobile_node, dim, type, charge_type):
    if 'external' in mobile_node[1]:
        charge = mobile_node[1]['charge']
        first_link = code.External[type][mobile_node[0]]['measure']
        shared = code.External[type][mobile_node[0]]['data']

        count = code.External[type][mobile_node[0]]['order']
        num_sides = code.External[type][mobile_node[0]]['sides']
        sign = common.Sign(count, num_sides)
        delta_charge = sign * charge
        first_link_charge = code.Primal.node[shared]['charge'][charge_type]
        code.Primal.node[shared]['charge'][charge_type] = (first_link_charge - delta_charge)%dim

        mobile_node = first_link
        chain = nx.shortest_path(code.Dual[type], mobile_node, fixed_node[0])
        chain_length = len(chain) - 1
        for link in range(chain_length):
            previous, next = chain[link], chain[link + 1]
            for shared in code.Stabilizers[type][previous]['data']:
                if shared in code.Stabilizers[type][next]['data']:

                    num_sides = code.Stabilizers[type][previous]['sides']
                    count = code.Stabilizers[type][previous]['data'][shared]
                    sign = common.Sign(count, num_sides)
                    delta_charge = sign * charge
                    data_charge = code.Primal.node[shared]['charge'][charge_type]
                    code.Primal.node[shared]['charge'][charge_type] = (data_charge - delta_charge)%dim

    else:
        Transport(code, fixed_node, mobile_node, dim, type, charge_type)

def _generateDAG(self):
        '''
        Generate workflow DAG using networkx directed graph implementation.
        Return topological ordering of graphs. Note that nx.topological_sort(G)
        requires the graph to be acyclic. Cyclic behavior is hard to implement
        in practice since jobs are defined by calling specific dictionary elements.
        '''

        # Instantiate directed graph, add job dependency edges.
        G = nx.DiGraph()
        for job in self.jobs:
            G.add_node(job)
            if 'dependsOn' in self.jobs[job]:
                for dependency in self.jobs[job]['dependsOn']:
                    G.add_edge(dependency['jobKey'], self.jobs[job]['jobKey'])
        self.dag_graph = G # For printing purposes.

        # Sort jobs in graph using topological sort, assigning job buckets.
        # Jobs within the same bucket will be kicked off simultaneously.
        topology = nx.topological_sort(G)
        self.graph = [(0, topology[0])]
        for edge in topology[1:]:
            try:
                self.graph.append((len(nx.shortest_path(G, topology[0], edge)) - 1, edge))
            except nx.exception.NetworkXNoPath as error:
                self.graph.append((0, edge))

def extractMinSubgraphContainingNodes(self, minSet):
        """
        Find the minimum subgraph of the dependency graph that contains the provided set of nodes. Useful for finding dependency-path like structures

        :param minSet: List of token indices
        :type minSet: List of ints
        :return: All the nodes and edges in the minimal subgraph
        :rtype: Tuple of nodes,edges where nodes is a list of token indices, and edges are the associated dependency edges between those tokens
        """

        assert isinstance(minSet, list)
        for i in minSet:
            assert isinstance(i, int)
            assert i >= 0
            assert i < len(self.tokens)
        G1 = nx.Graph()
        for a,b,depType in self.dependencies:
            G1.add_edge(a,b,dependencyType=depType)

        G2 = nx.Graph()
        paths = {}

        minSet = sorted(list(set(minSet)))
        setCount1 = len(minSet)
        minSet = [ a for a in minSet if G1.has_node(a) ]
        setCount2 = len(minSet)
        if setCount1 != setCount2:
            sys.stderr.write("WARNING. %d node(s) not found in dependency graph!\n" % (setCount1-setCount2))
        for a,b in itertools.combinations(minSet,2):
            try:
                path = nx.shortest_path(G1,a,b)
                paths[(a,b)] = path
                G2.add_edge(a,b,weight=len(path))
            except nx.exception.NetworkXNoPath:
                sys.stderr.write("WARNING. No path found between nodes %d and %d!\n" % (a,b))

        # TODO: This may through an error if G2 ends up having multiple components. Catch it gracefully.
        minTree = nx.minimum_spanning_tree(G2)
        nodes = set()
        allEdges = set()
        for a,b in minTree.edges():
            path = paths[(min(a,b),max(a,b))]
            for i in range(len(path)-1):
                a,b = path[i],path[i+1]
                dependencyType = G1.get_edge_data(a,b)['dependencyType']
                edge = (min(a,b),max(a,b),dependencyType)
                allEdges.add(edge)
            nodes.update(path)

        return nodes,allEdges

def TraverseGraph(transitions, states, args=None):
  """Does that actual graph traversal, going through all transitions."""
  transition_graph, initial_vertex = stl.graph.BuildTransitionGraph(
      transitions, states)

  graph_file = None
  if args:
    graph_file = args.graph
  visualizer = Visualizer(transition_graph, graph_file)

  circuit_stack = stl.traverse.MinEdgeCoverCircuit(transition_graph,
                                                   initial_vertex)
  circuit_stack.reverse()

  success = True
  while circuit_stack:
    edge = circuit_stack.pop()
    source, target, edge_i = edge
    attr = transition_graph[source][target][edge_i]
    transition = attr['transition']
    visualizer.TransitionRunning(edge)
    if attr['weight'] != float('inf'):
      logging.info('\033[93m[ RUNNING ]\033[0m: %s', transition.name)
      if transition.Run():
        logging.info('\033[92m[ PASSED ]\033[0m: %s', transition.name)
        visualizer.TransitionPassed(edge)
        continue
      else:
        logging.error('\033[91m[ FAILED ]\033[0m: %s', transition.name)
        success = False
        attr['weight'] = float('inf')
    error_vertex_id = attr['error_vertex_id']
    visualizer.TransitionFailed(edge, error_vertex_id)
    new_path = nx.shortest_path(
        transition_graph, error_vertex_id, target, weight='weight')
    path_stack = []
    for i in range(len(new_path) - 1):
      s = new_path[i]
      t = new_path[i + 1]
      # Get the edge-index with the smallest weight
      multi_edge = transition_graph[s][t]
      min_weight = float('inf')
      min_edge_i = 0
      for key, value in multi_edge.iteritems():
        if value['weight'] < min_weight:
          min_weight = value['weight']
          min_edge_i = key
      if transition_graph[s][t][min_edge_i]['weight'] == float('inf'):
        return success
      path_stack.append((s, t, min_edge_i))
    # TODO(seantopping): Implement a better error recovery algorithm.
    circuit_stack.extend(reversed(path_stack))
  return success

def main():
    if len(sys.argv) != 3:
        print "Usage: send.py [this_host] [target_host]"
        print "For example: send.py h1 h2"
        sys.exit(1)

    src, dst = sys.argv[1:]

    nb_hosts, nb_switches, links = read_topo()

    port_map = {}

    for a, b in links:
        if a not in port_map:
            port_map[a] = {}
        if b not in port_map:
            port_map[b] = {}

        assert(b not in port_map[a])
        assert(a not in port_map[b])
        port_map[a][b] = len(port_map[a]) + 1
        port_map[b][a] = len(port_map[b]) + 1


    G = nx.Graph()
    for a, b in links:
        G.add_edge(a, b)

    shortest_paths = nx.shortest_path(G)
    shortest_path = shortest_paths[src][dst]

    print "path is:", shortest_path

    port_list = []
    first = shortest_path[1]
    for h in shortest_path[2:]:
        port_list.append(port_map[first][h])
        first = h

    print "port list is:", port_list

    port_str = ""
    for p in port_list:
        port_str += chr(p)

    while(1):
        msg = raw_input("What do you want to send: ")

        # finding the route
        first = None

        p = SrcRoute(num_valid = len(port_list)) / port_str / msg
        print p.show()
        sendp(p, iface = "eth0")
        # print msg

def _get_path(self, src_vnf, dst_vnf, src_vnf_intf, dst_vnf_intf):
        """
        Own implementation of the get_path function from DCNetwork, because we just want the path and not set up
        flows on the way.

        :param src_vnf: Name of the source VNF
        :type src_vnf: ``str``
        :param dst_vnf: Name of the destination VNF
        :type dst_vnf: ``str``
        :param src_vnf_intf: Name of the source VNF interface
        :type src_vnf_intf: ``str``
        :param dst_vnf_intf: Name of the destination VNF interface
        :type dst_vnf_intf: ``str``
        :return: path, src_sw, dst_sw
        :rtype: ``list``, ``str``, ``str``
        """
        # modified version of the _chainAddFlow from emuvim.dcemulator.net._chainAddFlow
        src_sw = None
        dst_sw = None
        logging.debug("Find shortest path from vnf %s to %s",
                      src_vnf, dst_vnf)

        for connected_sw in self.net.DCNetwork_graph.neighbors(src_vnf):
            link_dict = self.net.DCNetwork_graph[src_vnf][connected_sw]
            for link in link_dict:
                if (link_dict[link]['src_port_id'] == src_vnf_intf or
                            link_dict[link][
                                'src_port_name'] == src_vnf_intf):
                    # found the right link and connected switch
                    src_sw = connected_sw
                    break

        for connected_sw in self.net.DCNetwork_graph.neighbors(dst_vnf):
            link_dict = self.net.DCNetwork_graph[connected_sw][dst_vnf]
            for link in link_dict:
                if link_dict[link]['dst_port_id'] == dst_vnf_intf or \
                                link_dict[link][
                                    'dst_port_name'] == dst_vnf_intf:
                    # found the right link and connected
                    dst_sw = connected_sw
                    break
        logging.debug("From switch %s to %s " % (src_sw, dst_sw))

        # get shortest path
        try:
            # returns the first found shortest path
            # if all shortest paths are wanted, use: all_shortest_paths
            path = nx.shortest_path(self.net.DCNetwork_graph, src_sw, dst_sw)
        except:
            logging.exception("No path could be found between {0} and {1} using src_sw={2} and dst_sw={3}".format(
                src_vnf, dst_vnf, src_sw, dst_sw))
            logging.debug("Graph nodes: %r" % self.net.DCNetwork_graph.nodes())
            logging.debug("Graph edges: %r" % self.net.DCNetwork_graph.edges())
            for e, v in self.net.DCNetwork_graph.edges():
                logging.debug("%r" % self.net.DCNetwork_graph[e][v])
            return "No path could be found between {0} and {1}".format(src_vnf, dst_vnf)

        logging.info("Shortest path between {0} and {1}: {2}".format(src_vnf, dst_vnf, path))
        return path, src_sw, dst_sw

def main():
    if len(sys.argv) != 3:
        print "Usage: send.py [this_host] [target_host]"
        print "For example: send.py h1 h2"
        sys.exit(1)

    src, dst = sys.argv[1:]

    nb_hosts, nb_switches, links = read_topo()

    port_map = {}

    for a, b in links:
        if a not in port_map:
            port_map[a] = {}
        if b not in port_map:
            port_map[b] = {}

        assert(b not in port_map[a])
        assert(a not in port_map[b])
        port_map[a][b] = len(port_map[a]) + 1
        port_map[b][a] = len(port_map[b]) + 1


    G = nx.Graph()
    for a, b in links:
        G.add_edge(a, b)

    shortest_paths = nx.shortest_path(G)
    shortest_path = shortest_paths[src][dst]

    print "path is:", shortest_path

    port_list = []
    first = shortest_path[1]
    for h in shortest_path[2:]:
        port_list.append(port_map[first][h])
        first = h

    print "port list is:", port_list

    port_str = ""
    for p in port_list:
        port_str += chr(p)

    while(1):
        msg = raw_input("What do you want to send: ")

        # finding the route
        first = None

        p = SrcRoute(num_valid = len(port_list)) / port_str / msg
        print p.show()
        sendp(p, iface = "eth0")
        # print msg

def get_path_to_netbox(netbox):
    """Returns a likely path from netbox to its apparent gateway/router.

    If any switches on the path, or the router itself is down,
    no current path exists and a False value is returned. However,
    if there is insufficient information for NAV to find a likely path,
    a True value is returned.

    """
    prefix = netbox.get_prefix()
    if not prefix:
        _logger.warning("couldn't find prefix for %s", netbox)
        return True

    router_ports = prefix.get_router_ports()
    if router_ports:
        router_port = router_ports[0]
    else:
        _logger.warning("couldn't find router ports for %s", prefix)
        return True

    router = router_port.interface.netbox
    _logger.debug("reachability check for %s on %s (router: %s)",
                  netbox, prefix, router)

    graph = get_graph_for_vlan(prefix.vlan)
    try:
        netbox.add_to_graph(graph)
    except AttributeError:
        pass

    # first, see if any path exists
    if not _path_exists(graph, netbox, router):
        _logger.warning("cannot find a path between %s and %s on VLAN %s",
                        netbox, router, prefix.vlan)
        return True

    # now, remove nodes that are down and see if a path still exists
    strip_down_nodes_from_graph(graph, keep=netbox)

    if netbox not in graph or router not in graph:
        if router.up == router.UP_UP:
            _logger.warning("%(netbox)s topology problem: router %(router)s "
                            "is up, but not in VLAN graph for %(prefix)r. "
                            "Defaulting to 'reachable' status.", locals())
            return True
        _logger.debug("%s not reachable, router or box not in graph: %r",
                      netbox, graph.edges())
        return False

    try:
        path = networkx.shortest_path(graph, netbox, router)
    except NetworkXException as error:
        _logger.debug("an internal networkx exception was raised in "
                      "shortest_path, assuming no path was found: %s", error)
        path = []
    else:
        _logger.debug("path to %s: %r", netbox, path)
    return path

def _build_routes(self, boundary_ports, graph, logical_ports):

        root_ports = dict((lp.ofp_port.port_no, lp.root_port)
                          for lp in logical_ports if lp.root_port == True)

        routes = {}

        for source, source_port_no in boundary_ports.iteritems():
            for target, target_port_no in boundary_ports.iteritems():

                if source is target:
                    continue

                # Ignore NNI - NNI routes
                if source_port_no in root_ports \
                        and target_port_no in root_ports:
                    continue

                # Ignore UNI - UNI routes
                if source_port_no not in root_ports \
                        and target_port_no not in root_ports:
                    continue

                path = nx.shortest_path(graph, source, target)

                # number of nodes in valid paths is always multiple of 3
                if len(path) % 3:
                    continue

                # in fact, we currently deal with single fan-out networks,
                # so the number of hops is always 6
                assert len(path) == 6

                ingress_input_port, ingress_device, ingress_output_port, \
                egress_input_port, egress_device, egress_output_port = path

                ingress_hop = RouteHop(
                    device=graph.node[ingress_device]['device'],
                    ingress_port=graph.node[ingress_input_port]['port'],
                    egress_port=graph.node[ingress_output_port]['port']
                )
                egress_hop = RouteHop(
                    device=graph.node[egress_device]['device'],
                    ingress_port=graph.node[egress_input_port]['port'],
                    egress_port=graph.node[egress_output_port]['port']
                )

                routes[(source_port_no, target_port_no)] = [
                    ingress_hop, egress_hop
                ]

        return routes

def getNetworkTransP(s1, s2, graph, endpoints, segmentlengths, pathnodes, decayconstantNet):
    """
    Returns transition probability of going from segment s1 to s2, based on network distance of segments, as well as corresponding path
    """
    subpath = []
    s1_point = None
    s2_point = None

    if s1 == s2:
        dist = 0
    else:
        #Obtain edges (tuples of endpoints) for segment identifiers
        s1_edge = endpoints[s1]
        s2_edge = endpoints[s2]

        s1_l = segmentlengths[s1]
        s2_l = segmentlengths[s2]

        #This determines segment endpoints of the two segments that are closest to each other
        minpair = [0,0,100000]
        for i in range(0,2):
            for j in range(0,2):
                d = round(pointdistance(s1_edge[i],s2_edge[j]),2)
                if d<minpair[2]:
                    minpair = [i,j,d]
        s1_point = s1_edge[minpair[0]]
        s2_point = s2_edge[minpair[1]]

##        if (s1_point in pathnodes or s2_point in pathnodes): # Avoid paths reusing an old pathnode (to prevent self-crossings)
##            dist = 100
##        else:
        if s1_point == s2_point:
                #If segments are touching, use a small network distance
                    dist = 5
        else:
                try:
                    #Compute a shortest path (using segment length) on graph where segment endpoints are nodes and segments are (undirected) edges
                    if graph.has_node(s1_point) and graph.has_node(s2_point):
                        dist = nx.shortest_path_length(graph, s1_point, s2_point, weight='length')
                        path = nx.shortest_path(graph, s1_point, s2_point, weight='length')
                        #get path edges
                        path_edges = zip(path,path[1:])
                        #print "edges: "+str(path_edges)
                        subpath = []
                        # get object ids for path edges
                        for e in path_edges:
                            oid = graph.edge[e[0]][e[1]]["OBJECTID"]
                            subpath.append(oid)
                        #print "oid path:"+str(subpath)
                    else:
                        #print "node not in segment graph!"
                        dist = 3*decayconstantNet #600
                except nx.NetworkXNoPath:
                    #print 'no path available, assume a large distance'
                    dist = 3*decayconstantNet #700
    #print "network distance between "+str(s1) + ' and '+ str(s2) + ' = '+str(dist)
    return (getNDProbability(dist,decayconstantNet),subpath,s2_point)