def add_edges(self, G, graph_element):
        def edge_key_data(G):
            # helper function to unify multigraph and graph edge iterator
            if G.is_multigraph():
                for u, v, key, data in G.edges_iter(data=True, keys=True):
                    edge_data = data.copy()
                    edge_data.update(key=key)
                    edge_id = edge_data.pop("id", None)
                    if edge_id is None:
                        edge_id = next(self.edge_id)
                    yield u, v, edge_id, edge_data
            else:
                for u, v, data in G.edges_iter(data=True):
                    edge_data = data.copy()
                    edge_id = edge_data.pop("id", None)
                    if edge_id is None:
                        edge_id = next(self.edge_id)
                    yield u, v, edge_id, edge_data

        edges_element = Element("edges")
        for u, v, key, edge_data in edge_key_data(G):
            kw = {"id": make_str(key)}
            edge_weight = edge_data.pop("weight", False)
            if edge_weight:
                kw["weight"] = make_str(edge_weight)
            edge_type = edge_data.pop("type", False)
            if edge_type:
                kw["type"] = make_str(edge_type)
            edge_element = Element("edge", source=make_str(u), target=make_str(v), **kw)
            default = G.graph.get("edge_default", {})
            edge_data = self.add_viz(edge_element, edge_data)
            edge_data = self.add_attributes("edge", edge_element, edge_data, default)
            edges_element.append(edge_element)
        graph_element.append(edges_element)

    def add_graph_element(self, G):
        """
        Serialize graph G in GraphML to the stream.
        """
        if G.is_directed():
            default_edge_type = 'directed'
        else:
            default_edge_type = 'undirected'

        graphid = G.graph.pop('id', None)
        if graphid is None:
            graph_element = self.myElement("graph",
                                           edgedefault=default_edge_type)
        else:
            graph_element = self.myElement("graph",
                                           edgedefault=default_edge_type,
                                           id=graphid)
        default = {}
        data = dict((k, v) for k, v in G.graph.items()
                    if k not in ['node_default', 'edge_default'])
        self.add_attributes("graph", graph_element, data, default)
        self.add_nodes(G, graph_element)
        self.add_edges(G, graph_element)

        # self.attributes contains a mapping from XML Objects to a list of
        # data that needs to be added to them.
        # We postpone processing in order to do type inference/generalization.
        # See self.attr_type
        for (xml_obj, data) in self.attributes.items():
            for (k, v, scope, default) in data:
                xml_obj.append(self.add_data(make_str(k),
                                             self.attr_type(k, scope, v),
                                             make_str(v), scope, default))
        self.xml.append(graph_element)

    def add_nodes(self, G, graph_element):
        nodes_element = Element("nodes")
        for node, data in G.nodes_iter(data=True):
            node_data = data.copy()
            #
            node_id = node_data.pop("id", make_str(node))
            kw = {"id": node_id}
            label = node_data.pop("label", make_str(node))
            kw["label"] = label

            pid = node_data.pop("pid", False)
            if pid:
                kw["pid"] = pid

            # add node element with attributes
            node_element = Element("node", **kw)

            # add node element and attr subelements
            default = G.graph.get("node_default", {})
            node_data = self.add_parents(node_element, node_data)
            node_data = self.add_slices(node_element, node_data)
            node_data = self.add_viz(node_element, node_data)
            node_data = self.add_attributes("node", node_element, node_data, default)
            nodes_element.append(node_element)
        graph_element.append(nodes_element)

 def add_attributes(self, node_or_edge, xml_obj, data, default):
     # Add attrvalues to node or edge
     attvalues=Element('attvalues')
     if len(data)==0:
         return data
     if 'start' in data or 'end' in data:
         mode='dynamic'
     else:
         mode='static'
     for k,v in data.items():
         # rename generic multigraph key to avoid any name conflict
         if k == 'key':
             k='networkx_key' 
         attr_id = self.get_attr_id(make_str(k), self.xml_type[type(v)],
                                    node_or_edge, default, mode)
         if type(v)==list:
             # dynamic data
             for val,start,end in v:
                 e=Element("attvalue")                
                 e.attrib['for']=attr_id
                 e.attrib['value']=make_str(val)
                 e.attrib['start']=make_str(start)
                 e.attrib['end']=make_str(end)
                 attvalues.append(e)                    
         else:
             # static data
             e=Element("attvalue")
             e.attrib['for']=attr_id
             e.attrib['value']=make_str(v)
             attvalues.append(e)
     xml_obj.append(attvalues)
     return data

 def add_nodes(self, G, graph_element):
     nodes_element = Element("nodes")
     for node, data in G.nodes(data=True):
         node_data = data.copy()
         node_id = make_str(node_data.pop("id", node))
         kw = {"id": node_id}
         label = make_str(node_data.pop("label", node))
         kw["label"] = label
         try:
             pid = node_data.pop("pid")
             kw["pid"] = make_str(pid)
         except KeyError:
             pass
         # add node element with attributes
         node_element = Element("node", **kw)
         # add node element and attr subelements
         default = G.graph.get("node_default", {})
         node_data = self.add_parents(node_element, node_data)
         if self.version == "1.1":
             node_data = self.add_slices(node_element, node_data)
         else:
             node_data = self.add_spells(node_element, node_data)
         node_data = self.add_viz(node_element, node_data)
         node_data = self.add_attributes("node", node_element, node_data, default)
         nodes_element.append(node_element)
     graph_element.append(nodes_element)

 def add_attributes(self, scope, xml_obj, data, default):
     """Appends attributes to edges or nodes.
     """
     for k, v in data.items():
         default_value = default.get(k)
         obj = self.add_data(make_str(k), type(v), make_str(v), scope=scope, default=default_value)
         xml_obj.append(obj)

 def add_attributes(self, scope, xml_obj, data, default):
     """Appends attribute data."""
     for k, v in data.items():
         data_element = self.add_data(make_str(k),
                                      self.attr_type(make_str(k), scope, v),
                                      make_str(v), scope, default.get(k))
         xml_obj.append(data_element)

 def add_nodes(self, G, graph_element):
     nodes_element = Element('nodes')
     for node, data in G.nodes(data=True):
         node_data = data.copy()
         node_id = make_str(node_data.pop('id', node))
         kw = {'id': node_id}
         label = make_str(node_data.pop('label', node))
         kw['label'] = label
         try:
             pid = node_data.pop('pid')
             kw['pid'] = make_str(pid)
         except KeyError:
             pass
         # add node element with attributes
         node_element = Element('node', **kw)
         # add node element and attr subelements
         default = G.graph.get('node_default', {})
         node_data = self.add_parents(node_element, node_data)
         if self.version == '1.1':
             node_data = self.add_slices(node_element, node_data)
         else:
             node_data = self.add_spells(node_element, node_data)
         node_data = self.add_viz(node_element, node_data)
         node_data = self.add_attributes('node', node_element,
                                         node_data, default)
         nodes_element.append(node_element)
     graph_element.append(nodes_element)

 def add_attributes(self, node_or_edge, xml_obj, data, default):
     # Add attrvalues to node or edge
     attvalues = Element("attvalues")
     if len(data) == 0:
         return data
     if "start" in data or "end" in data:
         mode = "dynamic"
     else:
         mode = "static"
     for k, v in list(data.items()):
         # rename generic multigraph key to avoid any name conflict
         if k == "key":
             k = "networkx_key"
         attr_id = self.get_attr_id(make_str(k), self.xml_type[type(v)], node_or_edge, default, mode)
         if type(v) == list:
             # dynamic data
             for val, start, end in v:
                 e = Element("attvalue")
                 e.attrib["for"] = attr_id
                 e.attrib["value"] = make_str(val)
                 e.attrib["start"] = make_str(start)
                 e.attrib["end"] = make_str(end)
                 attvalues.append(e)
         else:
             # static data
             e = Element("attvalue")
             e.attrib["for"] = attr_id
             e.attrib["value"] = make_str(v)
             attvalues.append(e)
     xml_obj.append(attvalues)
     return data

    def add_nodes(self, G, graph_element):
        nodes_element = Element('nodes')
        for node,data in G.nodes_iter(data=True):
            node_data=data.copy()
            # 
            node_id=node_data.pop('id',make_str(node))
            kw={'id':node_id}
            label=node_data.pop('label',make_str(node))
            kw['label']=label

            pid=node_data.pop('pid',False)
            if pid:
                kw['pid']=pid
            if 'start' in node_data:
                kw['start']=make_str(node_data.pop('start'))
            if 'end' in node_data:
                kw['end']=make_str(node_data.pop('end'))
                
            # add node element with attributes                
            node_element = Element("node", **kw)

            # add node element and attr subelements
            default=G.graph.get('node_default',{})
            node_data=self.add_parents(node_element, node_data)
            if self.version=='1.1':
                node_data=self.add_slices(node_element, node_data)
            else:
                node_data=self.add_spells(node_element, node_data)
            node_data=self.add_viz(node_element,node_data)
            node_data=self.add_attributes("node", node_element, 
                                          node_data, default)
            nodes_element.append(node_element)
        graph_element.append(nodes_element)

def to_pydot(N, strict=True):
    """Return a pydot graph from a NetworkX graph N.

    Parameters
    ----------
    N : NetworkX graph
      A graph created with NetworkX

    Examples
    --------
    >>> K5 = nx.complete_graph(5)
    >>> P = nx.nx_pydot.to_pydot(K5)

    Notes
    -----

    """
    import pydotplus
    # set Graphviz graph type
    if N.is_directed():
        graph_type='digraph'
    else:
        graph_type='graph'
    strict=N.number_of_selfloops()==0 and not N.is_multigraph()

    name = N.name
    graph_defaults=N.graph.get('graph',{})
    if name is '':
        P = pydotplus.Dot('', graph_type=graph_type, strict=strict,
                      **graph_defaults)
    else:
        P = pydotplus.Dot('"%s"'%name, graph_type=graph_type, strict=strict,
                      **graph_defaults)
    try:
        P.set_node_defaults(**N.graph['node'])
    except KeyError:
        pass
    try:
        P.set_edge_defaults(**N.graph['edge'])
    except KeyError:
        pass

    for n,nodedata in N.nodes_iter(data=True):
        str_nodedata=dict((k,make_str(v)) for k,v in nodedata.items())
        p=pydotplus.Node(make_str(n),**str_nodedata)
        P.add_node(p)

    if N.is_multigraph():
        for u,v,key,edgedata in N.edges_iter(data=True,keys=True):
            str_edgedata=dict((k,make_str(v)) for k,v in edgedata.items())
            edge=pydotplus.Edge(make_str(u), make_str(v),
                    key=make_str(key), **str_edgedata)
            P.add_edge(edge)

    else:
        for u,v,edgedata in N.edges_iter(data=True):
            str_edgedata=dict((k,make_str(v)) for k,v in edgedata.items())
            edge=pydotplus.Edge(make_str(u),make_str(v),**str_edgedata)
            P.add_edge(edge)
    return P

def node_link_graph(data, directed=False, multigraph=True):
    """Return graph from node-link data format.

    Parameters
    ----------
    data : dict
        node-link formatted graph data

    directed : bool
        If True, and direction not specified in data, return a directed graph.

    multigraph : bool
        If True, and multigraph not specified in data, return a multigraph.

    Returns
    -------
    G : NetworkX graph
       A NetworkX graph object

    Examples
    --------
    >>> from networkx.readwrite import json_graph
    >>> G = nx.Graph([(1,2)])
    >>> data = json_graph.node_link_data(G)
    >>> H = json_graph.node_link_graph(data)

    See Also
    --------
    node_link_data, adjacency_data, tree_data
    """
    multigraph = data.get('multigraph',multigraph)
    directed = data.get('directed',directed)
    if multigraph:
        graph = nx.MultiGraph()
    else:
        graph = nx.Graph()
    if directed:
        graph = graph.to_directed()
    mapping=[]
    graph.graph = dict(data.get('graph',[]))
    c = count()
    for d in data['nodes']:
        node = d.get('id',next(c))
        mapping.append(node)
        nodedata = dict((make_str(k),v) for k,v in d.items() if k!='id')
        graph.add_node(node, **nodedata)
    for d in data['links']:
        link_data = d.copy()
        source = link_data.pop('source')
        target = link_data.pop('target')
        edgedata = dict((make_str(k),v) for k,v in d.items()
                        if k!='source' and k!='target')
        graph.add_edge(mapping[source],mapping[target],**edgedata)
    return graph

def _place_initial_states(trs_graph, pd_graph, tikz):
    init_subg = pydot.Subgraph('initial')
    init_subg.set_rank('source')

    for node in trs_graph.states.initial:
        pd_node = pydot.Node(make_str(node))
        init_subg.add_node(pd_node)

        phantom_node = 'phantominit' + str(node)
        pd_node = pydot.Node(make_str(phantom_node))
        init_subg.add_node(pd_node)

    pd_graph.add_subgraph(init_subg)

 def add_spells(self,node_or_edge_element,node_or_edge_data):
     spells=node_or_edge_data.pop('spells',False)
     if spells:
         spells_element=Element('spells')
         for start,end in spells:
             e=Element('spell')
             if start is not None:
                 e.attrib['start']=make_str(start)
             if end is not None:
                 e.attrib['end']=make_str(end)
             spells_element.append(e)
         node_or_edge_element.append(spells_element)
     return node_or_edge_data

 def add_edges(self, G, graph_element):
     if G.is_multigraph():
         for u, v, key, data in G.edges_iter(data=True, keys=True):
             edge_element = Element("edge", source=make_str(u), target=make_str(v))
             default = G.graph.get("edge_default", {})
             self.add_attributes("edge", edge_element, data, default)
             self.add_attributes("edge", edge_element, {"key": key}, default)
             graph_element.append(edge_element)
     else:
         for u, v, data in G.edges_iter(data=True):
             edge_element = Element("edge", source=make_str(u), target=make_str(v))
             default = G.graph.get("edge_default", {})
             self.add_attributes("edge", edge_element, data, default)
             graph_element.append(edge_element)

 def add_spells(self, node_or_edge_element, node_or_edge_data):
     spells = node_or_edge_data.pop("spells", False)
     if spells:
         spells_element = Element("spells")
         for start, end in spells:
             e = Element("spell")
             if start is not None:
                 e.attrib["start"] = make_str(start)
                 self.alter_graph_mode_timeformat(start)
             if end is not None:
                 e.attrib["end"] = make_str(end)
                 self.alter_graph_mode_timeformat(end)
             spells_element.append(e)
         node_or_edge_element.append(spells_element)
     return node_or_edge_data

def generate_adjlist(G, delimiter=' '):
    """Generate a single line of the graph G in adjacency list format.

    Parameters
    ----------
    G : NetworkX graph

    delimiter : string, optional
       Separator for node labels

    Returns
    -------
    lines : string
        Lines of data in adjlist format.

    Examples
    --------
    >>> G = nx.lollipop_graph(4, 3)
    >>> for line in nx.generate_adjlist(G):
    ...     print(line)
    0 1 2 3
    1 2 3
    2 3
    3 4
    4 5
    5 6
    6

    See Also
    --------
    write_adjlist, read_adjlist

    """
    directed = G.is_directed()
    seen = set()
    for s, nbrs in G.adjacency_iter():
        line = make_str(s) + delimiter
        for t, data in nbrs.items():
            if not directed and t in seen:
                continue
            if G.is_multigraph():
                for d in data.values():
                    line += make_str(t) + delimiter
            else:
                line += make_str(t) + delimiter
        if not directed:
            seen.add(s)
        yield line[:-len(delimiter)]

 def get_attr_id(self, title, attr_type, edge_or_node, default, mode):
     # find the id of the attribute or generate a new id
     try:
         return self.attr[edge_or_node][mode][title]
     except KeyError:
         # generate new id
         new_id = str(next(self.attr_id))
         self.attr[edge_or_node][mode][title] = new_id
         attr_kwargs = {'id': new_id, 'title': title, 'type': attr_type}
         attribute = Element('attribute', **attr_kwargs)
         # add subelement for data default value if present
         default_title = default.get(title)
         if default_title is not None:
             default_element = Element('default')
             default_element.text = make_str(default_title)
             attribute.append(default_element)
         # new insert it into the XML
         attributes_element = None
         for a in self.graph_element.findall('attributes'):
             # find existing attributes element by class and mode
             a_class = a.get('class')
             a_mode = a.get('mode', 'static') # default mode is static
             if a_class == edge_or_node and a_mode == mode:
                 attributes_element = a
         if attributes_element is None:
             # create new attributes element
             attr_kwargs = {'mode': mode, 'class': edge_or_node}
             attributes_element = Element('attributes', **attr_kwargs)
             self.graph_element.insert(0, attributes_element)
         attributes_element.append(attribute)
     return new_id

    def add_edges(self, G, graph_element):
        def edge_key_data(G):
            # helper function to unify multigraph and graph edge iterator
            if G.is_multigraph():
                for u,v,key,data in G.edges_iter(data=True,keys=True):
                    edge_data=data.copy()
                    edge_data.update(key=key)
                    edge_id=edge_data.pop('id',None)
                    if edge_id is None:
                        edge_id=next(self.edge_id)
                    yield u,v,edge_id,edge_data
            else:
                for u,v,data in G.edges_iter(data=True):
                    edge_data=data.copy()
                    edge_id=edge_data.pop('id',None)
                    if edge_id is None:
                        edge_id=next(self.edge_id)
                    yield u,v,edge_id,edge_data

        edges_element = Element('edges')
        for u,v,key,edge_data in edge_key_data(G):
            kw={'id':make_str(key)}
            try:
                edge_weight=edge_data.pop('weight')
                kw['weight']=make_str(edge_weight)
            except KeyError:
                pass
            try:
                edge_type=edge_data.pop('type')
                kw['type']=make_str(edge_type)
            except KeyError:
                pass
            source_id = make_str(G.node[u].get('id', u))
            target_id = make_str(G.node[v].get('id', v))
            edge_element = Element("edge",
                                   source=source_id,target=target_id,
                                   **kw)
            default=G.graph.get('edge_default',{})
            if self.version == '1.1':
                edge_data=self.add_slices(edge_element, edge_data)
            else:
                edge_data=self.add_spells(edge_element, edge_data)
            edge_data=self.add_viz(edge_element,edge_data)
            edge_data=self.add_attributes("edge", edge_element,
                                          edge_data, default)
            edges_element.append(edge_element)
        graph_element.append(edges_element)

def pydot_layout(G,prog='neato',root=None, **kwds):
    """Create node positions using Pydot and Graphviz.

    Returns a dictionary of positions keyed by node.

    Examples
    --------
    >>> G=nx.complete_graph(4)
    >>> pos=nx.pydot_layout(G)
    >>> pos=nx.pydot_layout(G,prog='dot')
    
    """
    try:
        import pydot
    except ImportError:
        raise ImportError('pydot_layout() requires pydot ',
                          'http://code.google.com/p/pydot/')

    P=to_pydot(G)
    if root is not None :
        P.set("root",make_str(root))

    D=P.create_dot(prog=prog)

    if D=="":  # no data returned
        print("Graphviz layout with %s failed"%(prog))
        print()
        print("To debug what happened try:")
        print("P=pydot_from_networkx(G)")
        print("P.write_dot(\"file.dot\")")
        print("And then run %s on file.dot"%(prog))
        return

    Q=pydot.graph_from_dot_data(D)

    node_pos={}
    for n in G.nodes():
        pydot_node = pydot.Node(make_str(n)).get_name().encode('utf-8')
        node=Q.get_node(pydot_node)

        if isinstance(node,list):
            node=node[0]
        pos=node.get_pos()[1:-1] # strip leading and trailing double quotes
        if pos != None:
            xx,yy=pos.split(",")
            node_pos[n]=(float(xx),float(yy))
    return node_pos