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

def nx_plot_tree(server, node_size=200, **options):
    """Visualize the tree using the networkx package.

    This plots to the current matplotlib figure.

    Args:
        server: A DataServer instance.
        options: Options passed to networkx.draw().
    """
    import networkx as nx
    edges = server.estimate_tree()
    perplexity = server.latent_perplexity()
    feature_names = server.feature_names

    V = 1 + len(edges)
    G = nx.Graph()
    G.add_nodes_from(range(V))
    G.add_edges_from(edges)
    H = nx.relabel_nodes(G, dict(enumerate(feature_names)))
    node_size = node_size * perplexity / perplexity.max()

    options.setdefault('alpha', 0.2)
    options.setdefault('font_size', 8)
    nx.draw(H, with_labels=True, node_size=node_size, **options)

def graphFromDB(c, g):


    for row in c.execute ("SELECT * FROM node"):
        print (row[1])
        g.add_node(row)



    'Constructs a graph from DB data.'
    'Initialize Graph.'
    'Retrieve Nodes.'
    'For each node, insert it in graph.'

    'Possibly edges should be inserted in the same loop.'




#c.close()
#GUI

#Main loop.

def generate_graphs(self, n_edges_list, use_seed=True):
        """For each number of edges (n_edges) in n_edges_list create
        an Erdos Renyi Precision Graph that allows us to sample
        from later.

        Parameters
        ----------
        n_edges : list[int] or int
            list of number of edges for each graph or scalar
            if only one graph is wanted
        use_seed : bool
            indicates if seed shall be reset
        """
        if use_seed and self.seed is not None:
            random.seed(self.seed)

        n_edges = n_edges_list if type(n_edges_list) is list \
            else [n_edges_list]

        self.graphs = [ErdosRenyiPrecisionGraph(self.n_vertices, n_es)
                       for n_es in n_edges]

def _graph_indices(T, changepoints):
        """Describes which graphs are active for each time
        by returning a list with the graphs indices

        Parameters
        ----------
        T : int
            number of total timesteps
        changepoints : list[int]
            list of changepoint indices

        Yields
        ------
        Graph indices for all t < T
        """
        graph = count = 0
        for cp in changepoints:
            while count < cp:
                count += 1
                yield graph
            graph += 1
        while count < T:
            count += 1
            yield graph

def setUp(self):
        self.GRAPHML_NS = '{http://graphml.graphdrawing.org/xmlns}'
        self.test_input = {
            'distances': {
                'format': 'networkx',
                'data': nx.Graph([
                    ('US', 'UK', {'distance': 4242}),
                    ('US', 'Australia', {'distance': 9429}),
                    ('UK', 'Australia', {'distance': 9443}),
                    ('US', 'Japan', {'distance': 6303})
                ])
            },
            'alphabetGraph': {
                'format': 'clique.json'
            }
        }

        with open(os.path.join('tests', 'data', 'clique.json'), 'rb') as fixture:
            self.test_input['alphabetGraph']['data'] = fixture.read()

def subgraph_within_box(self, bounding_box):
        """
        Extract a subgraph bounded by a box.
        :param bounding_box: the bounding coordinates in
            (minx, miny, maxx, maxy) or a Polygon instance
        :return: a subgraph of nx.Graph
        """
        if isinstance(bounding_box, Polygon):
            bbox = bounding_box
        else:
            bbox = box(bounding_box[0], bounding_box[1],
                       bounding_box[2], bounding_box[3])
        nbunch = set()
        for edge in self.graph.edges():
            s, e = edge
            if bbox.intersects(LineString([self.node_xy[s], self.node_xy[e]])):
                nbunch.add(s)
                nbunch.add(e)
        return self.graph.subgraph(nbunch)

def merge_rectangles_into_obstacles(self, centers, widths, heights, epsilon):
        """Merges rectangles defined by centers, widths, heights. Two rectangles
        with distance < epsilon are considered part of the same object."""

        G = nx.Graph()
        obstacles = {i: Obstacle(centers[i, :], widths[i, 0], heights[i, 0]) for i in range(len(centers))}
        G.add_nodes_from(obstacles.keys())

        for i in obstacles:
            for j in obstacles:
                if i != j and obstacles[i].distance_to_obstacle(obstacles[j]) < epsilon:
                    G.add_edge(i,j)

        merged_obstacles = {}
        conn_components = nx.connected_components(G)
        for cc in conn_components:
            cc = list(cc)
            new_obs = obstacles[cc[0]]
            for i in range(1, len(cc)):
                new_obs.merge(obstacles[cc[i]])

            merged_obstacles[cc[0]] = new_obs

        return merged_obstacles

def efficient_projected_graph(B, nodes):
    g = nx.Graph()
    nodes = set(nodes)
    g.add_nodes_from(nodes)
    b_nodes = set(B.nodes())
    i = 0
    nodes = set(nodes)
    tenpercent = len(b_nodes) / 10
    for n in b_nodes:
        if i % tenpercent == 0:
            logging.info(str(10 * i / tenpercent) + "%")
        i += 1  
        nbrs = list(set([nbr for nbr in B[n]]) & nodes - set([n]))
        if n in nodes:
            for nbr in nbrs:
                if not g.has_edge(n, nbr):
                    g.add_edge(n, nbr)
        for nbr1 in nbrs:
            for nbr2 in nbrs:
                if nbr1 < nbr2:
                    if not g.has_edge(nbr1, nbr2):
                        g.add_edge(nbr1, nbr2)
        del nbrs

    return g

def efficient_collaboration_weighted_projected_graph2(B, nodes):
    nodes = set(nodes)
    G = nx.Graph()
    G.add_nodes_from(nodes)
    all_nodes = set(B.nodes())
    i = 0
    tenpercent = len(all_nodes) / 10
    for m in all_nodes:
        if i % tenpercent == 0:
            logging.info(str(10 * i / tenpercent) + "%")
        i += 1  

        nbrs = B[m]
        target_nbrs = [t for t in nbrs if t in nodes]
        if m in nodes:
            for n in target_nbrs:
                if m < n:
                    if not G.has_edge(m, n):
                        G.add_edge(m, n)
        for n1 in target_nbrs:
            for n2 in target_nbrs:
                if n1 < n2:
                    if not G.has_edge(n1, n2):
                        G.add_edge(n1, n2)
    return G

def draw_graph(gv, ge, name):
  Gr = nx.Graph()
  for i in range(N):
    Gr.add_node(i, pos=gv[i])

  for i in range(N):
    for j in range(N):
      if ge[i][j]:
        Gr.add_edge(i,j)

  labels = dict()
  for i in range(N):
    labels[i] = str(i)

  pos=nx.get_node_attributes(Gr,'pos')

  nx.draw(Gr, pos=pos, 
      node_size=400, with_labels=False)
  nx.draw_networkx_labels(Gr, pos, labels)

  plt.savefig(name)

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 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 add_node(graph, node_id, attrs=None):
    """Add a node to a graph.

    Parameters
    ----------
    graph : networkx.(Di)Graph
    node_id : hashable
        Prefix that is prepended to the new unique name.
    attrs : dict, optional
        Node attributes.

    Raises
    -------
    regraph.exceptions.GraphError
        Raises an error if node already exists in the graph.
    """
    new_attrs = deepcopy(attrs)
    if new_attrs is None:
        new_attrs = dict()
    if node_id not in graph.nodes():
        graph.add_node(node_id)
        normalize_attrs(new_attrs)
        graph.node[node_id] = new_attrs
    else:
        raise GraphError("Node '%s' already exists!" % node_id)

def add_nodes_from(graph, node_list):
    """Add nodes from a node list.

    Parameters
    ----------
    graph : networkx.(Di)Graph
    node_list : iterable
        Iterable containing a collection of nodes, optionally,
        with their attributes


    Examples
    --------
    >>> import networkx as nx
    >>> from regraph.primitives import add_nodes_from
    >>> G = nx.Graph()
    >>> add_nodes_from(G, [1, (2, {"a": 1}), 3])
    """
    for n in node_list:
        try:
            node_id, node_attrs = n
            add_node(graph, node_id, node_attrs)
        except (TypeError, ValueError) as e:
            add_node(graph, n)

def remove_edge(graph, s, t):
    """Remove edge from a graph.

    Parameters
    ----------
    graph : networkx.(Di)Graph
    s : hashable, source node id.
    t : hashable, target node id.

    Raises
    ------
    GraphError
        If edge between `s` and `t` does not exist.

    """
    if graph.is_directed():
        if (s, t) not in graph.edges():
            raise GraphError(
                "Edge '%s->%s' does not exist!" % (str(s), str(t)))
    graph.remove_edge(s, t)

def copy_node(graph, node_id):
    """Copy node.

    Create a copy of a node in a graph. A new id for the copy is
    generated by regraph.primitives.unique_node_id.

    Parameters
    ----------
    graph : networkx.(Di)Graph
    node_id : hashable, node to copy.

    Returns
    -------
    new_name
        Id of the copy node.

    """
    new_name = unique_node_id(graph, node_id)
    add_node(graph, new_name, graph.node[node_id])
    return new_name

def remove_node(graph, node_id):
    """Remove node.

    Parameters
    ----------
    graph : networkx.(Di)Graph
    node_id : hashable, node to remove.

    Raises
    ------
    GraphError
        If a node with the specified id does not exist.

    """
    if node_id in graph.nodes():
        neighbors = set(graph.__getitem__(node_id).keys())
        neighbors -= {node_id}
        graph.remove_node(node_id)
    else:
        raise GraphError("Node %s does not exist!" % str(node_id))
    return

def filter_edges_by_attributes(graph, attr_key, attr_cond):
    """Filter graph edges by attributes.

    Removes all the edges of the graph (inplace) that do not
    satisfy `attr_cond`.

    Parameters
    ----------
    graph : networkx.(Di)Graph
    attrs_key : attribute key
    attrs_cond : callable
        Condition for an attribute to satisfy: callable that returns
        `True` if condition is satisfied, `False` otherwise.

    """
    for (s, t) in graph.edges():
        if (attr_key not in graph.edge[s][t].keys() or
                not attr_cond(graph.edge[s][t][attr_key])):
            graph.remove_edge(s, t)

def set_edge(graph, s, t, attrs):
    """Set edge attrs.

    Parameters
    ----------
    graph : networkx.(Di)Graph
    s : hashable, source node id.
    t : hashable, target node id.
    attrs : dictionary
        Dictionary with attributes to set.

    Raises
    ------
    GraphError
        If an edge between `s` and `t` does not exist.
    """
    new_attrs = deepcopy(attrs)
    if not graph.has_edge(s, t):
        raise GraphError(
            "Edge %s->%s does not exist" % (str(s), str(t)))

    normalize_attrs(new_attrs)
    graph.edge[s][t] = new_attrs
    if not graph.is_directed():
        graph.edge[t][s] = new_attrs

def unique_node_id(graph, prefix):
    """Generate a unique id starting by a prefix.

    Parameters
    ----------
    graph : networkx.Graph
    prefix : str
        Prefix that is prepended to the new unique name.


    Returns
    -------
    str
        New unique node id starting with a prefix.
    """
    if prefix not in graph.nodes():
        return prefix
    idx = 0
    new_id = "{}_{}".format(prefix, idx)
    while new_id in graph.nodes():
        idx += 1
        new_id = "{}_{}".format(prefix, idx)
    return new_id

def node_type(self, graph_id, node_id):
        """Get a list of the immediate types of a node."""
        if graph_id not in self.nodes():
            raise HierarchyError(
                "Graph '%s' is not defined in the hierarchy!"
                % graph_id
            )
        if node_id not in self.node[graph_id].graph.nodes():
            raise HierarchyError(
                "Graph '%s' does not have a node with id '%s'!"
                % (graph_id, node_id)
            )
        types = {}
        for _, typing in self.out_edges(graph_id):
            mapping = self.edge[graph_id][typing].mapping
            if node_id in mapping.keys():
                types[typing] = mapping[node_id]
        return types

def add_assets_to_graph(g, assets):
    """
    :param nx.Graph g:
    :param Sequence[Asset] assets:
    """
    for asset in assets:
        if not asset.referers and not asset.referents:
            continue

        add_node(g, asset)

    for asset in assets:
        if not asset.referers and not asset.referents:
            continue

        for ref in asset.referers:
            g.add_edge(ref.relative_path, asset.relative_path)

def add_node(g, asset):
    """
    :param nx.Graph g:
    :param Asset asset:
    """
    if isinstance(asset, Prefab):
        if not asset.referers:
            color = 'purple'
        elif not asset.referents:
            color = 'green'
        else:
            color = 'blue'
    else:
        color = 'red'

    if option.long:
        label = asset.relative_path
    else:
        label = asset.file.name
    g.add_node(asset.relative_path, label=label, color=color)

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



#draws the graph and displays the weights on the edges

def CreateGraph():
    G = nx.Graph()
    f = open('input.txt')
    n = int(f.readline())
    for i in range(n):
        G.add_node(i+1)
    no_of_edges = int(f.readline())
    for i in range(no_of_edges):
        graph_edge_list = f.readline().split()
        G.add_edge(int(graph_edge_list[0]), int(graph_edge_list[1])) 
    vert = int(f.readline())
    return G, vert



#draws the graph and displays the weights on the edges

def CreateGraph():
    G = nx.Graph()
    f = open('input.txt')
    n = int(f.readline())
    for i in range(n):
        G.add_node(i+1)
    no_of_edges = int(f.readline())
    for i in range(no_of_edges):
        graph_edge_list = f.readline().split()
        G.add_edge(int(graph_edge_list[0]), int(graph_edge_list[1])) 
    vert = int(f.readline())
    return G, vert



#draws the graph and displays the weights on the edges

def CreateGraph():
    G = nx.Graph()
    f = open('input.txt')
    n = int(f.readline())
    for i in range(n):
        G.add_node(i+1)
    no_of_edges = int(f.readline())
    for i in range(no_of_edges):
        graph_edge_list = f.readline().split()
        G.add_edge(int(graph_edge_list[0]), int(graph_edge_list[1])) 
    vert = int(f.readline())
    return G, vert



#draws the graph and displays the weights on the edges

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



# draws the graph and displays the weights on the edges

def find_biggest_cluster(radius, points, order=None):
    graph = nx.Graph()
    for point in points:
            if order is '9QM=':
                #is a lure module - 9QM=
                now = int(time.time())
                remaining = now - point['last_modified_timestamp_ms']
                f = point['latitude'], point['longitude'], remaining
            else:
                f = point['latitude'], point['longitude'], 0
            graph.add_node(f)
            for node in graph.nodes():
                if node != f and distance(f[0], f[1], node[0], node[1]) <= radius*2:
                    graph.add_edge(f, node)
    cliques = list(find_cliques(graph))
    if len(cliques) > 0:
        max_clique = max(list(find_cliques(graph)), key=lambda l: (len(l), sum(x[2] for x in l)))
        merc_clique = [coord2merc(x[0], x[1]) for x in max_clique]
        clique_x, clique_y = zip(*merc_clique)
        best_point = np.mean(clique_x), np.mean(clique_y)
        best_coord = merc2coord(best_point)
        return {'latitude': best_coord[0], 'longitude': best_coord[1], 'num_points': len(max_clique)}
    else:
        return None

def getOwnerRobustness(self, graph):
        """ compute the "owner robustness """

        ownerNodes, nodeOwner = self.get_owner_distribution(graph)
        print "# owner".rjust(long_align_space), ",",\
              "main C. size".rjust(long_align_space), ",",\
              "number of components".rjust(long_align_space)
        for owner, nodes in sorted(ownerNodes.items(),
                                   key=lambda(x): -len(x[1])):
            purged_graph = nx.Graph(graph)
            for n in nodes:
                purged_graph.remove_node(n)
            comp_list = list(nx.connected_components(purged_graph))
            main_comp = sorted(comp_list, key=len, reverse=True)[0]
            print owner.rjust(long_align_space), ",",\
                str(len(main_comp)).rjust(long_align_space), ",", \
                str(len(comp_list)).rjust(long_align_space)
        print ""
        print ""

    #  ################# helper functions
    # These functions are needed to handle data structures from
    # other sources of data. You can use a database and dump the
    # data in XML from a db. You probably do not need these functions.

def Leaflet_finder(traj, i, j, ii, jj, len_chunks, cutoff):
    g1 = np.load(os.path.abspath(os.path.normpath(os.path.join(os.getcwd(),traj))), mmap_mode='r')[i:i+len_chunks]
    g2 = np.load(os.path.abspath(os.path.normpath(os.path.join(os.getcwd(),traj))), mmap_mode='r')[j:j+len_chunks]

    block = np.zeros((len(g1),len(g2)),dtype=float)
    block[:,:] = cdist(g1, g2) <= cutoff
    adj_list = np.where(block[:,:] == True)        
    adj_list = np.vstack(adj_list)

    adj_list[0] = adj_list[0]+ii*len_chunks
    adj_list[1] = adj_list[1]+jj*len_chunks

    if adj_list.shape[1] == 0:
        adj_list=np.zeros((2,1))

    graph = nx.Graph()
    edges = [(adj_list[0,k],adj_list[1,k]) for k in range(0,adj_list.shape[1])]
    graph.add_edges_from(edges)
    leaflet = sorted(nx.connected_components(graph), key=len, reverse=True)
    l_connected = [] # Keep only connected components
    for lng in range(len(leaflet)):
        l_connected.append(leaflet[lng])

    return list(l_connected)

def Leaflet_finder(block, traj, cutoff, len_atom, len_chunks, block_id=None):
    id_0 = block_id[0]
    id_1 = block_id[1]

    block[:,:] = cdist(np.load(traj, mmap_mode='r')[id_0*len_chunks:(id_0+1)*len_chunks], np.load(traj, mmap_mode='r')[id_1*len_chunks:(id_1+1)*len_chunks]) <= cutoff 
    adj_list = np.where(block[:,:] == True)        
    adj_list = np.vstack(adj_list)

    adj_list[0] = adj_list[0]+id_0*len_chunks
    adj_list[1] = adj_list[1]+id_1*len_chunks

    if adj_list.shape[1] == 0:
        adj_list=np.zeros((2,1))

    graph = nx.Graph()
    edges = [(adj_list[0,k],adj_list[1,k]) for k in range(0,adj_list.shape[1])]
    graph.add_edges_from(edges)
    l = np.array({i: item for i, item in enumerate(sorted(nx.connected_components(graph)))}, dtype=np.object).reshape(1,1)

    return l

def Leaflet_finder(block, traj, cutoff, len_atom, len_chunks, block_id=None):
    id_0 = block_id[0]
    id_1 = block_id[1]

    block[:,:] = cdist(np.load(traj, mmap_mode='r')[id_0*len_chunks:(id_0+1)*len_chunks], np.load(traj, mmap_mode='r')[id_1*len_chunks:(id_1+1)*len_chunks]) <= cutoff 
    adj_list = np.where(block[:,:] == True)        
    adj_list = np.vstack(adj_list)

    adj_list[0] = adj_list[0]+id_0*len_chunks
    adj_list[1] = adj_list[1]+id_1*len_chunks

    if adj_list.shape[1] == 0:
        adj_list=np.zeros((2,1))

    graph = nx.Graph()
    edges = [(adj_list[0,k],adj_list[1,k]) for k in range(0,adj_list.shape[1])]
    graph.add_edges_from(edges)
    l = np.array({i: item for i, item in enumerate(sorted(nx.connected_components(graph)))}, dtype=np.object).reshape(1,1)

    return l

def shortest_path(graph, source, target):
    """Return the windowed shortest path between source and target
    in the given graph.

    Graph is expected to be a dict {node: {successors}}.

    Return value is a tuple of 2-tuple, each 2-tuple representing a
    window of size 2 on the path.

    """
    if source == target: return tuple()  # no move needed
    nxg = nx.Graph()
    for node, succs in graph.items():
        for succ in succs:
            nxg.add_edge(node, succ)
    return tuple(nx.dijkstra_path(nxg, source, target))

def _process_params(G, center, dim):
    # Some boilerplate code.

    if not isinstance(G, nx.Graph):
        empty_graph = nx.Graph()
        empty_graph.add_nodes_from(G)
        G = empty_graph

    if center is None:
        center = np.zeros(dim)
    else:
        center = np.asarray(center)

    if len(center) != dim:
        msg = "length of center coordinates must match dimension of layout"
        raise ValueError(msg)

    return G, center

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 _makeGraphFromM5(self, m5FN, qver_get_func, qvmean_get_func, ice_opts):
        """Construct a graph from a BLASR M5 file."""
        alignGraph = nx.Graph()

        for r in blasr_against_ref(output_filename=m5FN,
                                   is_FL=True,
                                   sID_starts_with_c=False,
                                   qver_get_func=qver_get_func,
                                   qvmean_get_func=qvmean_get_func,
                                   ece_penalty=ice_opts.ece_penalty,
                                   ece_min_len=ice_opts.ece_min_len):
            if r.qID == r.cID:
                continue # self hit, ignore
            if r.ece_arr is not None:
                logging.debug("adding edge {0},{1}".format(r.qID, r.cID))
                alignGraph.add_edge(r.qID, r.cID)
        return alignGraph

def _makeGraphFromLA4Ice(self, runner, qver_get_func, qvmean_get_func, ice_opts):
        """Construct a graph from a LA4Ice output file."""
        alignGraph = nx.Graph()

        for la4ice_filename in runner.la4ice_filenames:
            count = 0
            start_t = time.time()
            for r in daligner_against_ref(
                    query_dazz_handler=runner.query_dazz_handler,
                    target_dazz_handler=runner.target_dazz_handler,
                    la4ice_filename=la4ice_filename,
                    is_FL=True, sID_starts_with_c=False,
                    qver_get_func=qver_get_func, qvmean_get_func=qvmean_get_func,
                    qv_prob_threshold=.03, ece_min_len=ice_opts.ece_min_len,
                    ece_penalty=ice_opts.ece_penalty,
                    same_strand_only=True, no_qv_or_aln_checking=False):
                if r.qID == r.cID:
                    continue # self hit, ignore
                if r.ece_arr is not None:
                    alignGraph.add_edge(r.qID, r.cID)
                    count += 1
            logging.debug("total {0} edges added from {1}; took {2} sec"
                          .format(count, la4ice_filename, time.time()-start_t))
        return alignGraph

def peptide_db_graph(peps, db, id_regex=None):
    ''' search a set of peptides against a FASTA database  '''
    g = nx.Graph()
    prot_dict = dict()
    for header, seq, in fasta.read(db):
        seq = seq.replace('I', 'L').upper()  # convert DB sequence I -> L
        prot_id = header.split()[0]
        if id_regex is not None:
            find_id = re.findall(id_regex, header)
            if len(find_id) > 0:
                prot_id = find_id[0]
        prot_dict[prot_id] = seq

    def _map_seq(p):
        pairs = []
        for prot_id, seq, in prot_dict.items():
            if p in seq:
                pairs.append([p, prot_id])
        return pairs

    for p in peps:
        ppps = _map_seq(p)
        if len(ppps):
            g.add_edges_from(ppps)
    return g

def protein_grouping(df, proteinDb):
    '''
    Grouping peptide sequences in the given dataframe (df)
        by mapping to a protein database (FASTA);
        or by the first column of dataframe when the database is absent
    '''
    peptides = sorted(set(df.index))
    if not proteinDb:
        g = nx.Graph()
        for i, x in df.iterrows():
            for prot in x.values.astype('str')[0].split(';'):
                if len(prot) > 0:
                    g.add_edge(i, prot)
    else:
        g = peptide_db_graph(peptides, proteinDb)
    pg = parsimony_grouping(g, peptides)
    return pg

def approximate_betweenness(graph, max_depth):
    """
    Compute the approximate betweenness of each edge, using max_depth to reduce
    computation time in breadth-first search.

    You should call the bfs and bottom_up functions defined above for each node
    in the graph, and sum together the results. Be sure to divide by 2 at the
    end to get the final betweenness.

    Params:
      graph.......A networkx Graph
      max_depth...An integer representing the maximum depth to search.

    Returns:
      A dict mapping edges to betweenness. Each key is a tuple of two strings
      representing an edge (e.g., ('A', 'B')). Make sure each of these tuples
      are sorted alphabetically (so, it's ('A', 'B'), not ('B', 'A')).

    >>> sorted(approximate_betweenness(example_graph(), 2).items())
    [(('A', 'B'), 2.0), (('A', 'C'), 1.0), (('B', 'C'), 2.0), (('B', 'D'), 6.0), (('D', 'E'), 2.5), (('D', 'F'), 2.0), (('D', 'G'), 2.5), (('E', 'F'), 1.5), (('F', 'G'), 1.5)]
    """
    ###TODO
    pass

def evaluate(predicted_edges, graph):
    """
    Return the fraction of the predicted edges that exist in the graph.

    Args:
      predicted_edges...a list of edges (tuples) that are predicted to
                        exist in this graph
      graph.............a networkx Graph

    Returns:
      The fraction of edges in predicted_edges that exist in the graph.

    In this doctest, the edge ('D', 'E') appears in the example_graph,
    but ('D', 'A') does not, so 1/2 = 0.5

    >>> evaluate([('D', 'E'), ('D', 'A')], example_graph())
    0.5
    """
    ###TODO
    pass

def clean_by_closeness_centrality(Gr,cc_dict,kCutThreshold):
    max_cc_threshold = max(list(cc_dict.values()))
    min_cc_threshold = min(list(cc_dict.values()))
    cc_threshold = (max_cc_threshold-min_cc_threshold)*kCutThreshold
    #print('- Closeness centrality threshold:',cc_threshold)

    to_remove = [n for n in Gr if cc_dict[n] < cc_threshold]
    Gr.remove_nodes_from(to_remove)
    print('Graph cleaned.')
    print('Removed nodes:',len(to_remove))

    return to_remove


# ### Expansion functions

# #### > LEMMAS:

# * Adding synonymes (related lemmas) of each existing node. Expanding graph.

def graph_synsets(terms, pos=wn.NOUN, depth=2):
    """
    Create a networkx graph of the given terms to the given depth.
    """

    G = nx.Graph(
        name="WordNet Synsets Graph for {}".format(", ".join(terms)), depth=depth,
    )

    def add_term_links(G, term, current_depth):
        for syn in wn.synsets(term):
            for name in syn.lemma_names():
                G.add_edge(term, name)
                if current_depth < depth:
                    add_term_links(G, name, current_depth+1)

    for term in terms:
        add_term_links(G, term, 0)

    return G

def __init__(self, network_configuration):

        self.network_configuration = network_configuration
        self.total_flow_rules = 0

        self.OFPP_CONTROLLER = 0xfffffffd
        self.OFPP_ALL = 0xfffffffc
        self.OFPP_IN = 0xfffffff8
        self.OFPP_NORMAL = 0xfffffffa

        self.GROUP_FF = "group-ff"
        self.GROUP_ALL = "group-all"

        # Initialize the self.graph
        self.graph = nx.Graph()

        # Initialize lists of host and switch ids
        self.host_ids = set()
        self.switch_ids = []

        self.controller = self.network_configuration.controller

    # Gets a switch-only multi-di-graph for the present topology

def generate(self,n,bounds=DobotModel.limits):
        """
        Generates (or regenerates) the PRM given a target number of samples n 
        """
        self.G = nx.Graph()

        # Sample environment
        ps = self._sample_cs(n,bounds)
        # ps = self._sample_ws(n,np.array([[0,300],[-200,200],[0,200]]))

        self.tree = kdt.KDTree(ps)

        # Connect samples
        for k in xrange(self.tree.n):
            self._connect(k,self.tree.data[k])

        # Skipping enhancement stage based on the assumption that Qfree >> Q!free

def dataToGraph(fil):

    edges = []
    i = 0
    with open(fil, 'r') as source:
        for line in source:
            parse = line.rstrip().split(',')
            for j, w in enumerate(parse):
                if w != '-':
                    edges.append((i, j, int(w)))
            i += 1

    G = nx.Graph()
    G.add_weighted_edges_from(edges)

    return G

def __init__(self, *args, **kwargs):
        super(NetworkAwareness, self).__init__(*args, **kwargs)
        self.topology_api_app = self
        self.name = "awareness"
        self.link_to_port = {}                 # {(src_dpid,dst_dpid):(src_port,dst_port),}
        self.access_table = {}                # {(sw,port):(ip, mac),}
        self.switch_port_table = {}      # {dpid:set(port_num,),}
        self.access_ports = {}                # {dpid:set(port_num,),}
        self.interior_ports = {}              # {dpid:set(port_num,),}
        self.switches = []                         # self.switches = [dpid,]
        self.shortest_paths = {}            # {dpid:{dpid:[[path],],},}
        self.pre_link_to_port = {}
        self.pre_access_table = {}

        # Directed graph can record the loading condition of links more accurately.
        # self.graph = nx.Graph()
        self.graph = nx.DiGraph()
        # Get initiation delay.
        self.initiation_delay = self.get_initiation_delay(CONF.fanout)
        self.start_time = time.time()

        # Start a green thread to discover network resource.
        self.discover_thread = hub.spawn(self._discover)

def LFR_Community_Generator(fname = 'LFR_4.txt'):
    try:
        fdobj = open(fname,'r')
    except IOError as e:
        print "***file open error:",e
    else:
        G = nx.Graph()
        for i in range(0,12):
            eline = fdobj.readline()
        eline = fdobj.readline()
        while eline:
            line = eline.strip().split()
            G.add_edge(line[0],line[1])
            eline = fdobj.readline()
        #end while
        fdobj.close()
        return G

#************************************************************************

def plot(self):
        # print(list(self.root.edge_list()))
        labels = {}
        for i, j in self.root.edge_list():
            labels[i] = i
            labels[j] = j
        G = nx.Graph(self.root.edge_list())
        pos = graphviz_layout(G, prog='dot')

        nx.draw(G, pos)

        nx.draw_networkx_labels(G, pos, labels)

        plt.show()

# class BST_count(BST):
#     def __init__(self, url=None, file=None,tree=None):
#         if tree:
#             pass
#         else:
#             super(BST).__init__(url,file)