def __init__(self, data=None, **attr):
        """Initialize a graph with edges, name, or graph attributes.

        Parameters
        ----------
        data : input graph
            Data to initialize graph.  If data=None (default) an empty
            graph is created.  The data can be an edge list, or any
            NetworkX graph object.  If the corresponding optional Python
            packages are installed the data can also be a NumPy matrix
            or 2d ndarray, a SciPy sparse matrix, or a PyGraphviz graph.

        attr : keyword arguments, optional (default= no attributes)
            Attributes to add to graph as key=value pairs.

        See Also
        --------
        convert

        Examples
        --------
        >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
        >>> G = nx.Graph(name='my graph')
        >>> e = [(1, 2), (2, 3), (3, 4)] # list of edges
        >>> G = nx.Graph(e)

        Arbitrary graph attribute pairs (key=value) may be assigned

        >>> G = nx.Graph(e, day="Friday")
        >>> G.graph
        {'day': 'Friday'}

        """
        self.edge_key_dict_factory = self.edge_key_dict_factory
        Graph.__init__(self, data, **attr)

 def add_node(self, n):
     if n in self:
         return # already in tree
     elif len(self.adj)==0:
         Graph.add_node(self,n) # first node
     else:  # not allowed
         raise NetworkXError(\
             "adding single node %s not allowed in non-empty tree"%(n))

    def to_undirected(self, reciprocal=False):
        """Return an undirected representation of the digraph.

        Parameters
        ----------
        reciprocal : bool (optional)
          If True only keep edges that appear in both directions
          in the original digraph.

        Returns
        -------
        G : Graph
            An undirected graph with the same name and nodes and
            with edge (u,v,data) if either (u,v,data) or (v,u,data)
            is in the digraph.  If both edges exist in digraph and
            their edge data is different, only one edge is created
            with an arbitrary choice of which edge data to use.
            You must check and correct for this manually if desired.

        Notes
        -----
        If edges in both directions (u,v) and (v,u) exist in the
        graph, attributes for the new undirected edge will be a combination of
        the attributes of the directed edges.  The edge data is updated
        in the (arbitrary) order that the edges are encountered.  For
        more customized control of the edge attributes use add_edge().

        This returns a "deepcopy" of the edge, node, and
        graph attributes which attempts to completely copy
        all of the data and references.

        This is in contrast to the similar G=DiGraph(D) which returns a
        shallow copy of the data.

        See the Python copy module for more information on shallow
        and deep copies, http://docs.python.org/library/copy.html.

        Warning
        -------
        If you have subclassed DiGraph to use dict-like objects in the
        data structure, those changes do not transfer to the Graph
        created by this method.
        """
        H=Graph()
        H.name=self.name
        H.add_nodes_from(self)
        if reciprocal is True:
            H.add_edges_from( (u,v,deepcopy(d))
                              for u,nbrs in self.adjacency_iter()
                              for v,d in nbrs.items()
                              if v in self.pred[u])
        else:
            H.add_edges_from( (u,v,deepcopy(d))
                              for u,nbrs in self.adjacency_iter()
                              for v,d in nbrs.items() )
        H.graph=deepcopy(self.graph)
        H.node=deepcopy(self.node)
        return H

 def delete_node(self, n):
     try:
         if len(self.adj[n])==1: # allowed for leaf node
             Graph.delete_node(self,n)
         else:
             raise NetworkXError(
           "deleting interior node %s not allowed in tree"%(n))
     except KeyError: # NetworkXError if n not in self
         raise NetworkXError("node %s not in graph"%n)

 def delete_edge(self, u, v=None): 
     if v is None: (u,v)=u   # no v given, assume u is an edge tuple
     Graph.delete_edge(self,u,v)
     # this will always break a tree into two trees
     # put nodes connected to v in a new component
     vnodes=component.node_connected_component(self,v)
     for n in vnodes:
         self.comp[n]=self.nc
     self.nc+=1

 def add_edge(self, u, v=None):  
     if v is None: (u,v)=u  # no v given, assume u is an edge tuple
     if self.has_edge(u,v): return # no parallel edges allowed
     elif u in self and v in self:
         raise NetworkXError("adding edge %s-%s not allowed in tree"%(u,v))
     elif u in self or v in self:
         Graph.add_edge(self,u,v)
         return
     elif len(self.adj)==0: # first leaf
         Graph.add_edge(self,u,v)            
         return
     else:
         raise NetworkXError("adding edge %s-%s not allowed in tree"%(u,v))

    def to_undirected(self):
        """Return an undirected representation of the digraph.
 
        Returns
        -------
        G : Graph
            An undirected graph with the same name and nodes and 
            with edge (u,v,data) if either (u,v,data) or (v,u,data)
            is in the digraph.  If both edges exist in digraph and
            their edge data is different, only one edge is created
            with an arbitrary choice of which edge data to use.
            You must check and correct for this manually if desired.

        Notes
        -----
        If edges in both directions (u,v) and (v,u) exist in the
        graph, attributes for the new undirected edge will be a combination of
        the attributes of the directed edges.  The edge data is updated
        in the (arbitrary) order that the edges are encountered.  For
        more customized control of the edge attributes use add_edge().

        This is similar to Graph(self) which returns a shallow copy.  
        self.to_undirected() returns a deepcopy of edge, node and
        graph attributes.
        """
        H=Graph()
        H.name=self.name
        H.add_nodes_from(self)
        H.add_edges_from( (u,v,deepcopy(d)) 
                          for u,nbrs in self.adjacency_iter()
                          for v,d in nbrs.iteritems() )
        H.graph=deepcopy(self.graph)
        H.node=deepcopy(self.node)
        return H

 def __init__(self,data=None,**kwds):
     Graph.__init__(self,**kwds)
     if data is not None:
         try: # build a graph
             G=Graph()
             G=convert.from_whatever(data,create_using=G)
         except:
             raise NetworkXError, "Data %s is not a tree"%data
         # check if it is a tree.
         if G.order()==G.size()+1 and \
                component.number_connected_components(G)==1:
             self.adj=G.adj.copy()
             del G
         else:
             raise NetworkXError, "Data %s is not a tree"%data

    def to_undirected(self):

        H = Graph()
        H.name = self.name
        H.add_nodes_from(self)
        H.add_edges_from((u, v, deepcopy(d)) for u, nbrs in self.adjacency_iter() for v, d in nbrs.iteritems())
        H.graph = deepcopy(self.graph)
        H.node = deepcopy(self.node)
        return H

    def to_undirected(self):
        """Return an undirected representation of the digraph.

        Returns
        -------
        G : Graph
            An undirected graph with the same name and nodes and
            with edge (u,v,data) if either (u,v,data) or (v,u,data)
            is in the digraph.  If both edges exist in digraph and
            their edge data is different, only one edge is created
            with an arbitrary choice of which edge data to use.
            You must check and correct for this manually if desired.

        Notes
        -----
        If edges in both directions (u,v) and (v,u) exist in the
        graph, attributes for the new undirected edge will be a combination of
        the attributes of the directed edges.  The edge data is updated
        in the (arbitrary) order that the edges are encountered.  For
        more customized control of the edge attributes use add_edge().

        This returns a "deepcopy" of the edge, node, and
        graph attributes which attempts to completely copy
        all of the data and references.

        This is in contrast to the similar G=DiGraph(D) which returns a
        shallow copy of the data.

        See the Python copy module for more information on shallow
        and deep copies, http://docs.python.org/library/copy.html.

        """
        H=Graph()
        H.name=self.name
        H.add_nodes_from(self)
        H.add_edges_from( (u,v,deepcopy(d))
                          for u,nbrs in self.adjacency_iter()
                          for v,d in nbrs.iteritems() )
        H.graph=deepcopy(self.graph)
        H.node=deepcopy(self.node)
        return H

 def to_undirected(self):
     """Return an undirected representation of the digraph.
 
     A new graph is returned with the same name and nodes and
     with edge (u,v,data) if either (u,v,data) or (v,u,data) 
     is in the digraph.  If both edges exist in digraph and
     their edge data is different, only one edge is created
     with an arbitrary choice of which edge data to use.  
     You must check and correct for this manually if desired.
     
     """
     H=Graph()
     H.name=self.name
     H.add_nodes_from(self)
     H.add_edges_from([(v,u,d) for (u,v,d) in self.edges_iter(data=True)])
     return H

def make_nonmultigraph(multigraph):
    """
        Removes duplicate edges. Instead of having multiple edges going from the same source to the same target,
        this function adds one edge with a weight attribute,
        Parameters:
            multigraph: The multi-graph with multi-edges
        Return:
            G: A new graph which is equivalent to the multi-graph.
    """
    G = Graph()
    for node in multigraph.nodes_iter():
        G.add_node(node)
    for edge in multigraph.edges_iter():
        for existing_edge in G.edges_iter():
            if existing_edge[0] == edge[0] and existing_edge[1] == edge[1]: #If the edge is already in the existing edge list...
                G.edge[edge[0]][edge[1]]['weight'] += 1 # the existing edge's weight is incremented
        G.add_edge(edge[0], edge[1], weight=1)
    return G

 def __init__(self, data=None, **attr):
     self.edge_key_dict_factory = self.edge_key_dict_factory
     Graph.__init__(self, data, **attr)

    def to_undirected(self, reciprocal=False, as_view=False):
        """Returns an undirected representation of the digraph.

        Parameters
        ----------
        reciprocal : bool (optional)
          If True only keep edges that appear in both directions
          in the original digraph.
        as_view : bool (optional, default=False)
          If True return an undirected view of the original directed graph.

        Returns
        -------
        G : Graph
            An undirected graph with the same name and nodes and
            with edge (u, v, data) if either (u, v, data) or (v, u, data)
            is in the digraph.  If both edges exist in digraph and
            their edge data is different, only one edge is created
            with an arbitrary choice of which edge data to use.
            You must check and correct for this manually if desired.

        See Also
        --------
        Graph, copy, add_edge, add_edges_from

        Notes
        -----
        If edges in both directions (u, v) and (v, u) exist in the
        graph, attributes for the new undirected edge will be a combination of
        the attributes of the directed edges.  The edge data is updated
        in the (arbitrary) order that the edges are encountered.  For
        more customized control of the edge attributes use add_edge().

        This returns a "deepcopy" of the edge, node, and
        graph attributes which attempts to completely copy
        all of the data and references.

        This is in contrast to the similar G=DiGraph(D) which returns a
        shallow copy of the data.

        See the Python copy module for more information on shallow
        and deep copies, https://docs.python.org/2/library/copy.html.

        Warning: If you have subclassed DiGraph to use dict-like objects
        in the data structure, those changes do not transfer to the
        Graph created by this method.

        Examples
        --------
        >>> G = nx.path_graph(2)   # or MultiGraph, etc
        >>> H = G.to_directed()
        >>> list(H.edges)
        [(0, 1), (1, 0)]
        >>> G2 = H.to_undirected()
        >>> list(G2.edges)
        [(0, 1)]
        """
        graph_class = self.to_undirected_class()
        if as_view is True:
            return nx.graphviews.generic_graph_view(self, Graph)
        # deepcopy when not a view
        G = Graph()
        G.graph.update(deepcopy(self.graph))
        G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
        if reciprocal is True:
            G.add_edges_from((u, v, deepcopy(d))
                             for u, nbrs in self._adj.items()
                             for v, d in nbrs.items()
                             if v in self._pred[u])
        else:
            G.add_edges_from((u, v, deepcopy(d))
                             for u, nbrs in self._adj.items()
                             for v, d in nbrs.items())
        return G