python类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