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

def rank(nodes, edges):
    ''' Creates the graph with the calculates nodes (sentences) and their weight'''
    graph = nx.DiGraph()
    graph.add_nodes_from(nodes)
    graph.add_weighted_edges_from(edges)
    ''' Uses google's pagerank formula to find the most important senteces'''
    return nx.pagerank(graph)

def __init__(self, graph=None):
        """
        Construct the graph object.

        Parameters
        ----------
            graph : networkx.DiGraph or NNGraph
                Graph to build the object from (optional).
        """
        super(Graph, self).__init__()
        # Privates
        self._thread_to_graph_mapping = {}
        self._creator_thread = threading.get_ident()
        self._creator_pid = mp.current_process().pid
        # Publics
        if graph is not None:
            self.graph = graph
        else:
            self.graph = NNGraph()

def parse_owl_rdf(url):
    """Downloads and parses an OWL resource in OWL/RDF format

    :param str url: The URL to the OWL resource
    :return: A directional graph representing the OWL document's hierarchy
    :rtype: networkx.DiGraph
    """
    g = nx.DiGraph(IRI=url)
    o = Ontospy(url)

    for cls in o.classes:
        g.add_node(cls.locale, type='Class')

        for parent in cls.parents():
            g.add_edge(cls.locale, parent.locale, type='SubClassOf')

        for instance in cls.instances():
            _, frag = urldefrag(instance)
            g.add_edge(frag, cls.locale, type='ClassAssertion')

    return g

def gdgnc(num_nodes, p, q):
    gen_graph = nx.DiGraph()
    counter = 1
    gen_graph.add_node(0)
    while counter < num_nodes:
        gen_graph.add_node(counter)
        if random.random() <= p:
            rand_node = random.randint(0, counter - 1)
            gen_graph.add_edge(counter, rand_node)
            for edge in gen_graph.out_edges(rand_node):
                gen_graph.add_edge(counter, edge[1])
            if random.random() <= q:
                rand_node = random.randint(0, counter - 1)
                for edge in gen_graph.out_edges(rand_node):
                    gen_graph.add_edge(counter, edge[1])
        else:
            rand_node = random.randint(0, counter - 1)
            gen_graph.add_edge(rand_node, counter)
        counter += 1
    return gen_graph


# Bollobas graph generator

def packages_to_graph(self, targets):
        G = nx.DiGraph()
        for package in targets:
            G.add_node(package)
            for dep_name in package.dependecies:
                q = Query(dep_name)
                dep_package = self._find_satisfier_in_set(targets, q)
                if dep_package is None:
                    # Swallow the error, since this is expected in some cases
                    continue
                    # raise Exception(
                    #     "Tried to make a graph out of packages that "
                    #     "have unresolved dependencies: " + str(q)
                    # )
                G.add_edge(package, dep_package)
        return G

def _expand_dependencies_to_graph(self, targets):
        G = nx.DiGraph()
        targets_copy = list(targets)
        queue = list(targets)
        seen = set(targets)
        while queue:
            package = queue.pop()
            G.add_node(package)
            for dep_name in package.dependecies:
                q = Query(dep_name)
                dep_package = self._find_satisfier(targets_copy, q)
                if dep_package is None:
                    self.unresolved.append(q)
                    continue

                G.add_edge(package, dep_package)
                if not dep_package in seen:
                    targets_copy.append(dep_package)
                    seen.add(dep_package)
                    queue.append(dep_package)
        return G

def draw(passage):
    G = nx.DiGraph()
    terminals = sorted(passage.layer(layer0.LAYER_ID).all, key=operator.attrgetter("position"))
    G.add_nodes_from([(n.ID, {"label": n.text, "node_color": "white"}) for n in terminals])
    G.add_nodes_from([(n.ID, {"label": "IMPLICIT" if n.attrib.get("implicit") else "",
                              "node_color": "gray" if isinstance(n, Linkage) else (
                                  "white" if n.attrib.get("implicit") else "black")})
                      for n in passage.layer(layer1.LAYER_ID).all])
    G.add_edges_from([(n.ID, e.child.ID, {"label": e.tag, "style": "dashed" if e.attrib.get("remote") else "solid"})
                      for layer in passage.layers for n in layer.all for e in n])
    pos = topological_layout(passage)
    nx.draw(G, pos, arrows=False, font_size=10,
            node_color=[d["node_color"] for _, d in G.nodes(data=True)],
            labels={n: d["label"] for n, d in G.nodes(data=True) if d["label"]},
            style=[d["style"] for _, _, d in G.edges(data=True)])
    nx.draw_networkx_edge_labels(G, pos, font_size=8,
                                 edge_labels={(u, v): d["label"] for u, v, d in G.edges(data=True)})

def draw_graph(nx_graph):
    """
    Draws the input graph on two axes with lines between the nodes

    Positions of the nodes are determined with reduce_graph, of course.

    Parameters
    ----------
    nx_graph : :class:`nx.Graph` or :class:`nx.DiGraph`
        The graph to be plotted
    """
    import matplotlib.pyplot as plt
    reduced_2 = reduce_graph(nx_graph, 2)
    for edge in nx_graph.edges():
        plt.plot([reduced_2[0, edge[0]], reduced_2[0, edge[1]]],
                 [reduced_2[1, edge[0]], reduced_2[1, edge[1]]],
                 'b-')
    plot_2d(reduced_2)

def parse_owl_rdf_resolver(iri):
    path = os.path.join(owl_dir_path, get_uri_name(iri))
    o = Ontospy(path)

    g = DiGraph(IRI=iri)

    for cls in o.classes:
        g.add_node(cls.locale, type='Class')

        for parent in cls.parents():
            g.add_edge(cls.locale, parent.locale, type='SubClassOf')

        for instance in cls.instances():
            _, frag = urldefrag(instance)
            g.add_edge(frag, cls.locale, type='ClassAssertion')

    return g

def gen_graph(directed):
    g = nx.Graph()

    if directed:
        g = nx.DiGraph()

    # Add 5 nodes
    for i in xrange(1, 6):
        g.add_node(i, node_weight=i)

    # Add edges
    g.add_edge(1, 2, weight=1.0)
    g.add_edge(1, 3, weight=2.0)
    g.add_edge(1, 4, weight=3.0)
    g.add_edge(3, 4, weight=4.0)
    g.add_edge(2, 5, weight=5.0)

    return g

def test_find_matching(self):
        pattern = nx.DiGraph()
        prim.add_nodes_from(pattern, [
            1,
            (2, {"a": 1}),
            3
        ])
        prim.add_edges_from(pattern, [
            (1, 2),
            (2, 3)
        ])
        pattern_typing = {1: "circle", 2: "square", 3: "triangle"}

        instances = self.hierarchy.find_matching(
            graph_id="g1",
            pattern=pattern,
            pattern_typing={
                "g0": pattern_typing,
                "g00": {1: "white", 2: "white", 3: "black"}
            }
        )
        assert(len(instances) == 1)

def new_rule(hie, parent, name, pattern_name=None):
    """create a new rule """
    if valid_child_name(hie, parent, name):
        if pattern_name is None:
            pattern = nx.DiGraph()
        else:
            pattern_id = child_from_name(hie, parent, pattern_name)
            pattern = hie.node[pattern_id].graph
        rule_id = hie.unique_graph_id(name)
        rule = Rule(pattern, pattern, pattern)
        hie.add_rule(rule_id, rule, {"name": name})
        if parent is not None:
            if pattern_name is None:
                hie.add_rule_typing(rule_id, parent, {}, {})
            else:
                mapping = hie.edge[pattern_id][parent].mapping
                hie.add_rule_typing(rule_id, parent, mapping, mapping)
    else:
        raise ValueError("Invalid new name")


# TODO : undirected ?

def rm_node(hie, g_id, parent, node_id, force=False):
    """remove a node from a graph """
    if isinstance(hie.node[g_id], GraphNode):
        if [c for c in all_children(hie, g_id)
                if node_id in hie.edge[c][g_id].mapping.values()]:
            if not force:
                raise ValueError(
                    "some nodes are typed by {}"
                    "set the force argument to"
                    "delete the as well"
                    .format(node_id))

        lhs = nx.DiGraph()
        lhs.add_node(node_id)
        ppp = nx.DiGraph()
        rhs = nx.DiGraph()
        rule = Rule(ppp, lhs, rhs)
        _rewrite(hie, g_id, rule, {node_id: node_id})
    elif isinstance(hie.node[g_id], RuleNode):
        hie.node[g_id].rule.remove_node_rhs(node_id)
        for _, typing in hie.out_edges(g_id):
            if node_id in hie.edge[g_id][typing].rhs_mapping.keys():
                del hie.edge[g_id][typing].rhs_mapping[node_id]
    else:
        raise ValueError("node is neither a rule nor a graph")

def rm_edge(hie, g_id, parent, node1, node2):
    """remove an edge from a graph, and all the edges typed by it"""
    if isinstance(hie.node[g_id], GraphNode):
        lhs = nx.DiGraph()
        lhs.add_node(node1)
        lhs.add_node(node2)
        lhs.add_edge(node1, node2)
        ppp = nx.DiGraph()
        ppp.add_node(node1)
        ppp.add_node(node2)
        rhs = nx.DiGraph()
        rhs.add_node(node1)
        rhs.add_node(node2)
        rule = Rule(ppp, lhs, rhs)
        _rewrite(hie, g_id, rule, {node1: node1, node2: node2})

    elif isinstance(hie.node[g_id], RuleNode):
        hie.node[g_id].rule.remove_edge_rhs(node1, node2)
    else:
        raise ValueError("node is neither a rule nor a graph")

def remove_attributes(hie, g_id, parent, node, json_attrs):
    """remove the attributes from json_attrs from the node"""
    attrs = prim.json_dict_to_attrs(json_attrs)
    if isinstance(hie.node[g_id], GraphNode):
        lhs = nx.DiGraph()
        lhs.add_node(node)
        add_node_attrs(lhs, node, attrs)
        ppp = nx.DiGraph()
        ppp.add_node(node)
        rhs = nx.DiGraph()
        rhs.add_node(node)
        rule = Rule(ppp, lhs, rhs)
        _rewrite(hie, g_id, rule, {node: node})
    elif isinstance(hie.node[g_id], RuleNode):
        hie.node[g_id].rule.remove_node_attrs_rhs(node, attrs)
    else:
        raise ValueError("node is neither a rule nor a graph")

def partial_pushout(a, b, c, a_b, a_c):
    """Find the partial pushout."""
    check_homomorphism(a, b, a_b, total=False)
    check_homomorphism(a, c, a_c, total=False)
    if a.is_directed():
        ab_dom = nx.DiGraph(a.subgraph(a_b.keys()))
        ac_dom = nx.DiGraph(a.subgraph(a_c.keys()))
    else:
        ab_dom = nx.Graph(a.subgraph(a_b.keys()))
        ac_dom = nx.Graph(a.subgraph(a_c.keys()))

    ac_a = {n: n for n in ac_dom.nodes()}
    ab_a = {n: n for n in ab_dom.nodes()}

    (c2, a_c2, c_c2) = pushout(ac_dom, a, c, ac_a, a_c)
    (b2, a_b2, b_b2) = pushout(ab_dom, a, b, ab_a, a_b)

    (d, b2_d, c2_d) = pushout(a, b2, c2, a_b2, a_c2)
    b_d = compose(b_b2, b2_d)
    c_d = compose(c_c2, c2_d)

    return(d, b_d, c_d)

def add_edge(self, s, t, attrs=None, **attr):
        # set up attribute dict (from Networkx to preserve the signature)
        if attrs is None:
            attrs = attr
        else:
            try:
                attrs.update(attr)
            except AttributeError:
                raise ValueError(
                    "The attr_dict argument must be a dictionary."
                )
        if s not in self.nodes():
            raise ValueError("Node %s is not defined!" % s)
        if t not in self.nodes():
            raise ValueError("Node %s is not defined!" % t)
        source_type = self.node[s].type_
        target_type = self.node[t].type_
        if self.metamodel_ is not None:
            if (source_type, target_type) not in self.metamodel_.edges():
                raise ValueError(
                    "Edge from '%s' to '%s' is not allowed by metamodel" %
                    (source_type, target_type)
                )
        normalize_attrs(attrs)
        nx.DiGraph.add_edge(self, s, t, attrs)

def CreateGraph():
    B = nx.DiGraph();
    f = open('input.txt')
    n = int(f.readline())
    cost = []

    for i in range(n):
        list1 = map(int, (f.readline()).split())
        cost.append(list1)
    people = []
    for i in range(n):
        people.append(i)
    job = [] 
    for c in ascii_lowercase[:n]:
        job.append(c)
    B.add_nodes_from(people, bipartite=0) # Add the node attribute "bipartite"
    B.add_nodes_from(job, bipartite=1)
    for i in range(n) :
        for c in ascii_lowercase[:n] :
            if cost[i][ord(c)-97] > 0 :
                B.add_edge(i, c, length = cost[i][ord(c)-97])  
    return B,cost

def CreateGraph():
    G = nx.DiGraph()
    f = open('input.txt')
    n = int(f.readline())
    wtMatrix = []
    for i in range(n):
        list1 = map(int, (f.readline()).split())
        wtMatrix.append(list1)
    source = int(f.readline()) #source vertex from where BFS has to start
    #Adds egdes along with their weights to the graph 
    for i in range(n):
        for j in range(n):
            if wtMatrix[i][j] > 0:
                    G.add_edge(i, j, length = wtMatrix[i][j]) 
    return G, source



#draws the graph and displays the weights on the edges

def CreateGraph():
    G = nx.DiGraph()
    f = open('input.txt')
    n = int(f.readline())
    wtMatrix = []
    for i in range(n):
        list1 = map(int, (f.readline()).split())
        wtMatrix.append(list1)
    source = int(f.readline()) #source vertex for dijsktra's algo 
    #Adds egdes along with their weights to the graph 
    for i in range(n) :
        for j in range(n) :
            if wtMatrix[i][j] > 0 :
                    G.add_edge(i, j, length = wtMatrix[i][j]) 
    return G, source



#draws the graph and displays the weights on the edges

def get_network(self, network_type: NetworkType, edge_type: EdgeType, quote_type: QuoteType) -> DiGraph:
        network_keys = self.redis_server.keys(self.get_redis_key(network_type, edge_type, quote_type) + '*')
        pipe = self.redis_server.pipeline()
        for network_key in network_keys:
            pipe.hgetall(network_key)
        res = pipe.execute()
        dg = DiGraph()
        for idx, val in enumerate(network_keys):
            start_currency = val.split(':')[-1]
            for end_currency, weight in res[idx].items():
                edge_weight = weight
                end_currency = end_currency
                dg.add_edge(start_currency, end_currency, weight=edge_weight)
        return dg

    # Portfolio hash is {currency_enum: currency_qty}
    # Return is ({currency_enum: (final_currency_qty, edge_val)}, total_qty)

def test_resolve_cyclical_build_test_dependency():
    g = nx.DiGraph()
    g.add_node('build-a')
    g.add_node('build-b')
    g.add_node('test-a')
    g.add_node('test-b')
    # normal test after build dependencies
    g.add_edge('build-a', 'test-a')
    # this one will shift from depending on build-b to depending on test-a, which depends on build-b
    g.add_edge('build-b', 'test-b')
    # the build-time dependence of B on A.
    #     This one has to be removed.  build-b instead must depend on build-a
    g.add_edge('test-a', 'build-b')
    # the runtime dependency of A on B.  This one stays.
    g.add_edge('build-b', 'test-a')

    compute_build_graph.reorder_cyclical_test_dependencies(g)
    assert not ('test-a', 'build-b') in g.edges()
    assert not ('build-b', 'test-b') in g.edges()
    assert ('test-a', 'test-b') in g.edges()
    assert ('build-b', 'test-a') in g.edges()

def get_test_graph():
    g = networkx.DiGraph()

    g.add_edges_from([
        ("1", "2"),
        ("1", "6"),
        ("2", "3"),
        ("2", "7"),
        ("3", "4"),
        ("3", "5"),
        ("4", "5"),
        ("5", "2"),
        ("5", "6"),
        ("6", "7"),
        ("7", "8")
    ])

    return g

def get_test_graph3():
    g = networkx.DiGraph()

    g.add_edges_from([
        (1, 2),
        (1, 3),
        (2, 5),
        (2, 4),
        (3, 9),
        (5, 6),
        (6, 4),
        (6, 7),
        (7, 8),
        (8, 10),
        (8, 11),
        (9, 8),
        (9, 11),
        (10, 12),
        (11, 12)
    ])

    return g

def draw_cfg(funks):
    fgs = {}
    for b in funks.values():
        fg = nx.DiGraph()
        for i in b.instrs.values():
            fg.add_node(i.addr, { 'label': '{}: {}'.format(i.addr, pretty(i)) })
        for i in b.instrs.values():
            if i.opcode == INSTR_INC:
                fg.add_edge(i.addr, i.next1)
            elif i.opcode == INSTR_DEC:
                fg.add_edge(i.addr, i.next1)
                fg.add_edge(i.addr, i.next2)
            elif i.opcode == INSTR_FRK:
                fg.add_edge(i.addr, i.next2)
            elif i.opcode == INSTR_JMP:
                fg.add_edge(i.addr, i.next1)
            else:
                assert i.opcode == INSTR_RET
        fgs[b.addr] = fg

        a = nx.nx_agraph.to_agraph(fg)
        a.layout(prog='dot')
        a.draw('function_{}.png'.format(b.addr))

def _get_calc_nodes(self, name):
        g = nx.DiGraph()
        g.add_nodes_from(self.dag.nodes())
        g.add_edges_from(self.dag.edges())
        for n in nx.ancestors(g, name):
            node = self.dag.node[n]
            state = node[_AN_STATE]
            if state == States.UPTODATE or state == States.PINNED:
                g.remove_node(n)

        ancestors = nx.ancestors(g, name)
        for n in ancestors:
            if state == States.UNINITIALIZED and len(self.dag.pred[n]) == 0:
                raise Exception("Cannot compute {} because {} uninitialized".format(name, n))
            if state == States.PLACEHOLDER:
                raise Exception("Cannot compute {} because {} is placeholder".format(name, n))

        ancestors.add(name)
        nodes_sorted = nx.topological_sort(g)
        return [n for n in nodes_sorted if n in ancestors]

def createGraph():
    global colors, pos

    # common.g=nx.DiGraph() # directed graph, instead of nx.Graph()
    common.g = nx.Graph()  # undirected, for oligopoly project
    colors = {}
    pos = {}
    common.g_labels = {}
    common.g_edge_labels = {}  # copy the address of the labels of the edges

    # setting Figure 1 (the switch of the control between Figure 1 and Figure 2
    # is managed in oActions.py

    if not common.IPython or common.graphicStatus == "PythonViaTerminal":
        # the or is about ipython running in a terminal
        plt.figure(1)
        mngr1 = plt.get_current_fig_manager()  # NB, after figure()
        mngr1.window.wm_geometry("+650+0")
        mngr1.set_window_title("Links Entrepreneurs - Workers")


# searching tools

def build_graph():
    graph = networkx.DiGraph()
    domain_ids = get_domains_ids()
    total = len(domain_ids)
    i = 0
    seen = dict()
    for d_id in domain_ids:
        i += 1
        domain     = Domain.get(id=d_id)
        links_from = domain.links_from()
        commit()
        if domain.host not in seen:
            graph.add_node(domain.host)
            seen[domain.host] = True

        for link in links_from:
            if link.host not in seen:
                graph.add_node(link.host)
                seen[link.host] = True
            graph.add_edge(domain.host, link.host) 

        if (i % 10) == 0:
            print("Processed %d / %d" % (i, total))

    return graph

def _create_nx_graph(self):
        self._nx_graph = nx.DiGraph()
        for thesaurus_entry in self.thesaurus.items():
            node = self.nodename_index[thesaurus_entry[0]]
            self._nx_graph.add_node(node)
            for child_entry in thesaurus_entry[1]['narrower']:
                child = self.nodename_index[child_entry]
                self._nx_graph.add_edge(node, child, weight=0)

            for parent_entry in thesaurus_entry[1]['broader']:
                parent = self.nodename_index[parent_entry]
                self._nx_graph.add_edge(parent, node, weight=0)
        # TODO add weights
        for n in self._nx_graph.nodes():
            edges = self._nx_graph.edges(n, data=True)
            n_edges = len(edges)
            for _, _, d in edges:
                d['weight'] = 1 / n_edges

def generate_graph(usm):
    current = usm.get_root()
    G = nx.DiGraph()
    labels = {}
    idx = 0
    queue = deque([(idx, current)])
    colors = [_get_color(current)]
    while len(queue) != 0:
        pidx, current = queue.popleft()
        for key, child in current.children.items():
            idx+=1
            G.add_node(idx, tree_node=child)
            colors.append(_get_color(child))
            G.add_edge(pidx, idx, label=key)
            labels[idx] = key
            queue.append((idx, child))
    return G, labels, colors

def retweet_network(collection, tweet_fields, user_fields):
    def replace_none(s):
        if s is None:
            return 'NULL'
        return s

    tp = TweetParser()
    dg = nx.DiGraph(name="retweet graph")

    for tweet in collection:

        um_dict = {field:replace_none(value) for field,value in tp.parse_columns_from_tweet(tweet['user'], user_fields)}
        t_dict = {field:replace_none(value) for field,value in tp.parse_columns_from_tweet(tweet, tweet_fields)}

        if tweet['user']['id_str'] not in dg:
            dg.add_node(tweet['user']['id_str'], attr_dict=um_dict)
        if 'retweeted_status' in tweet:
            rtu_dict = {field:replace_none(value) for field,value in tp.parse_columns_from_tweet(tweet['retweeted_status']['user'], user_fields)}
            dg.add_node(tweet['retweeted_status']['user']['id_str'], attr_dict=rtu_dict)
            dg.add_edge(tweet['user']['id_str'], tweet['retweeted_status']['user']['id_str'], attr_dict=t_dict)
    return dg

def compile(cls, source_net, compiled_net):
        """Add runtime instruction nodes to the computation graph.

        Parameters
        ----------
        source_net : nx.DiGraph
        compiled_net : nx.DiGraph

        Returns
        -------
        compiled_net : nx.Digraph

        """
        logger.debug("{} compiling...".format(cls.__name__))

        instruction_node_map = dict(_uses_batch_size='_batch_size', _uses_meta='_meta')

        for instruction, _node in instruction_node_map.items():
            for node, d in source_net.nodes_iter(data=True):
                if d.get(instruction):
                    if not compiled_net.has_node(_node):
                        compiled_net.add_node(_node)
                    compiled_net.add_edge(_node, node, param=_node[1:])

        return compiled_net

def compile(cls, source_net, compiled_net):
        """Remove redundant nodes from the computation graph.

        Parameters
        ----------
        source_net : nx.DiGraph
        compiled_net : nx.DiGraph

        Returns
        -------
        compiled_net : nx.Digraph

        """
        logger.debug("{} compiling...".format(cls.__name__))

        outputs = compiled_net.graph['outputs']
        output_ancestors = nbunch_ancestors(compiled_net, outputs)
        for node in compiled_net.nodes():
            if node not in output_ancestors:
                compiled_net.remove_node(node)
        return compiled_net

def nx_graph(self):
        """Convert the data in a ``nodelist`` into a networkx labeled directed graph."""
        import networkx as NX

        nx_nodelist = list(range(1, len(self.nodes)))
        nx_edgelist = [
            (n, self._hd(n))
            for n in nx_nodelist if self._hd(n)
        ]
        nx_labels = {}
        for n in nx_nodelist:
            nx_labels[n] = self.nodes[n]['word']

        g = NX.DiGraph()
        g.add_nodes_from(nx_nodelist)
        g.add_edges_from(nx_edgelist)

        return g, nx_labels

def isas(path):
    G = nx.DiGraph()

    with open(path, newline='') as f:
        reader = csv.reader(f, delimiter='\t')

        for row in reader:
            if len(row) > 1 and row[0] and row[1]:
                G.add_edge(sanitize(row[0]), sanitize(row[1]))

    # Note that we store the sense inventory as an attribute of G.
    # TODO: nx.DiGraph subclass?
    G.senses = defaultdict(list)

    for node in G.nodes():
        G.senses[node.rsplit('#', 1)[0]].append(node)

    return G

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 get_nx_graph(self):
        graph = nx.DiGraph()
        switches = topo_api.get_all_switch(self)
        links = topo_api.get_all_link(self)

        for switch in switches:
            dpid = switch.dp.id
            graph.add_node(dpid)

        for link in links:
            src_dpid = link.src.dpid
            dst_dpid = link.dst.dpid
            src_port = link.src.port_no
            dst_port = link.dst.port_no
            graph.add_edge(src_dpid,
                           dst_dpid,
                           src_port=src_port,
                           dst_port=dst_port)
        return graph

def network_from_json(json_data):
    # NOTE|dutc: we could use the following, but it would tie our data format
    #            too closely to the graph library
    # from networkx import node_link_graph
    g = DiGraph()

    nodes = {}
    for el in json_data['elements']:
        el = getattr(elements, el['type'])(el['id'], **el['metadata'])
        g.add_node(el)
        nodes[el.id] = el

    for cx in json_data['connections']:
        from_node, to_node = nodes[cx['from_node']], nodes[cx['to_node']]
        g.add_edge(from_node, to_node)

    return g

def __len__(self):
        """Return the number of nodes. Use the expression 'len(G)'.

        Returns
        -------
        nnodes : int
            The number of nodes in the graph.

        Examples
        --------
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
        >>> G.add_path([0,1,2,3])
        >>> len(G)
        4

        """
        return len(self.node)

def number_of_nodes(self):
        """Return the number of nodes in the graph.

        Returns
        -------
        nnodes : int
            The number of nodes in the graph.

        See Also
        --------
        order, __len__  which are identical

        Examples
        --------
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
        >>> G.add_path([0,1,2])
        >>> len(G)
        3
        """
        return len(self.node)

def adjacency_list(self):
        """Return an adjacency list representation of the graph.

        The output adjacency list is in the order of G.nodes().
        For directed graphs, only outgoing adjacencies are included.

        Returns
        -------
        adj_list : lists of lists
            The adjacency structure of the graph as a list of lists.

        See Also
        --------
        adjacency_iter

        Examples
        --------
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
        >>> G.add_path([0,1,2,3])
        >>> G.adjacency_list() # in order given by G.nodes()
        [[1], [0, 2], [1, 3], [2]]

        """
        return list(map(list,iter(self.adj.values())))

def adjacency_iter(self):
        """Return an iterator of (node, adjacency dict) tuples for all nodes.

        This is the fastest way to look at every edge.
        For directed graphs, only outgoing adjacencies are included.

        Returns
        -------
        adj_iter : iterator
           An iterator of (node, adjacency dictionary) for all nodes in
           the graph.

        See Also
        --------
        adjacency_list

        Examples
        --------
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
        >>> G.add_path([0,1,2,3])
        >>> [(n,nbrdict) for n,nbrdict in G.adjacency_iter()]
        [(0, {1: {}}), (1, {0: {}, 2: {}}), (2, {1: {}, 3: {}}), (3, {2: {}})]

        """
        return iter(self.adj.items())

def create_graph(predicted_ids, parent_ids, scores, vocab=None):
  def get_node_name(pred):
    return vocab[pred] if vocab else str(pred)

  seq_length = predicted_ids.shape[0]
  graph = nx.DiGraph()
  for level in range(seq_length):
    names = [get_node_name(pred) for pred in predicted_ids[level]]
    _add_graph_level(graph, level + 1, parent_ids[level], names, scores[level])
  graph.node[(0, 0)]["name"] = "START"
  return graph

def _create_eps_closure_func(table):
    edges = {(c.src, c.sym.text, c.dst[0]) for c in table.cells}
    graph = DiGraph((src, dst) for src, sym, dst in edges if sym == '')
    states = set(sum(((src, dst) for src, _, dst in edges), ()))

    cs = {s: descendants(graph, s) if s in graph else set() for s in states}
    return lambda ss: frozenset(set(ss).union(*(cs[s] for s in ss)))

def build_file_move_graph(file_frame):
    move_frame = file_frame[file_frame.move]
    move_graph = nx.from_pandas_dataframe(
        move_frame,
        source='file_path1', target='file_path2',
        edge_attr='hexsha', create_using=nx.DiGraph())
    return move_graph

def sdg(num_nodes, num_edges, epsilon1, epsilon2):
    gen_graph = nx.DiGraph()
    nodes = range(num_nodes)
    gen_graph.add_nodes_from(nodes)
    i = 0
    while i < num_edges:
        # choose out node uniformly
        if random.random() < epsilon1 or len(gen_graph.edges()) < 1:
            out_node = random.choice(nodes)
        # choose out based on preferential attachment
        else:
            out_nodes = gen_graph.out_degree().keys()
            out_degree = np.array(gen_graph.out_degree().values())

            out_node = np.random.choice(out_nodes, p=out_degree/(1.0 * i))
        # choose in node uniformly
        if random.random() < epsilon2 or len(gen_graph.edges()) < 1:
            if 0 not in gen_graph.in_degree().values():
                in_node = random.choice(nodes)
        # choose in based on preferential attachment
            else:

                if len(nx.isolates(gen_graph)) > 0:
                    in_node = random.choice(nx.isolates(gen_graph))
                else:
                    in_node_degree = 1
                    while in_node_degree > 0:
                        in_node = random.choice(gen_graph.nodes())
                        in_node_degree = gen_graph.in_degree(in_node)
        else:
            in_nodes = gen_graph.in_degree().keys()
            in_degree = np.array(gen_graph.in_degree().values())
            in_node = np.random.choice(in_nodes, p=in_degree / (1.0 * i))

        if out_node != in_node and (out_node, in_node) not in gen_graph.edges():
            gen_graph.add_edge(out_node, in_node)
            i += 1

    return gen_graph

def loadGraphFromEdgeListTxt(file_name):
    f = open(file_name, 'r')
    G = nx.DiGraph()
    for line in f:
        edge = line.split(';')
        n1 = int(edge[0])
        n2 = int(edge[1].split('\n')[0])
        G.add_edge(n1, n2)
    return G

def make_profile(self, local_repo):
        modlist_path = self.cfg.profile_dir / "modlist.txt"
        with open(modlist_path, "w") as f:
            G = nx.DiGraph()
            for package in local_repo.get_all_packages():
                G.add_node(package)
                for dep_name in package.dependecies:
                    q = Query(dep_name)
                    dep = local_repo.find_package(q)

                    if dep is None:
                        # Skip mising dependecies. If we have an installed
                        # package which has a not installed dependency, then we
                        # just want to skip it. It's up to the user to make
                        # sure everything is resolved, of course assisted by
                        # the tool.  @COMPLETE it might be useful give the user
                        # some way of doing a full dependency verification of
                        # the local repo
                        continue

                    G.add_edge(package, dep)
            for package in nx.lexicographical_topological_sort(
                    G,
                    key=lambda x: x.priority):
                print("+" + package.name, file=f)
            print("*Unmanaged: Dawnguard", file=f)
            print("*Unmanaged: Dragonborn", file=f)
            print("*Unmanaged: HearthFires", file=f)
            print("*Unmanaged: HighResTexturePack01", file=f)
            print("*Unmanaged: HighResTexturePack02", file=f)
            print("*Unmanaged: HighResTexturePack03", file=f)
            print("*Unmanaged: Unofficial Dawnguard Patch", file=f)
            print("*Unmanaged: Unofficial Dragonborn Patch", file=f)
            print("*Unmanaged: Unofficial Hearthfire Patch", file=f)
            print("*Unmanaged: Unofficial High Resolution Patch", file=f)
            print("*Unmanaged: Unofficial Skyrim Patch", file=f)

def visualize():
    import networkx as nx
    # How about we don't fire up a JVM just to start my script?
    from asciinet import graph_to_ascii

    G = nx.DiGraph()
    root = "Root"

    G.add_node(root)

    # @ENHANCEMENT
    # Right now we just visualize it as a stright up dependency graph. We might
    # want to show when we use provides instead in the future. This would
    # involve adding a fake node when we look for a provides and let that
    # depend on the actual implementors
    for package in local_repo.get_all_packages():
        G.add_node(package)
        if package.reason == InstallReason.REQ:
            G.add_edge(root, package)
        for dep_str in package.dependecies:
            q = Query(dep_str)
            dep = local_repo.find_package(q)
            if dep is None:
                print(package, q)
            G.add_edge(package, dep)

    print(graph_to_ascii(G))


# Show details about a package

def from_depends(subtrees):
        G = nx.DiGraph()
        root = RootNode()
        for subG in subtrees:
            self.G = nx.compose(G, subG.G)
            self.G.add_edge(root, subG.root)
        return InstalledGraph(G, root)