def initialize():

    G.add_node("A")
    G.add_node("B")
    G.add_node("C")
    G.add_node("D")
    G.add_node("E")
    G.add_node("F")

    labels = {k: k for k in G.nodes()}

    G.add_edge("A", "F", weight=1)
    G.add_edge("A", "E", weight=3)
    G.add_edge("A", "C", weight=4)
    G.add_edge("F", "B", weight=3)
    G.add_edge("F", "E", weight=2)
    G.add_edge("B", "D", weight=3)
    G.add_edge("B", "E", weight=2)
    G.add_edge("E", "D", weight=4)
    G.add_edge("E", "C", weight=2)
    G.add_edge("C", "D", weight=1)

    labels = nx.get_edge_attributes(G, "weight")
    plt.title("Single-Router Network")
    nx.draw(G, pos=nx.spectral_layout(G))
    nx.draw_networkx(G, with_labels=True, pos=nx.spectral_layout(G))
    nx.draw_networkx_edge_labels(G, pos=nx.spectral_layout(G), edge_labels=labels)
    plt.show()

def printClusters(msp_list_deleted, msp_list_remain, msp_list, name):
    G = nx.Graph()
    deleted = nx.Graph()
    remain = nx.Graph()

    for l in range(0, len(msp_list)):
        G.add_edge(msp_list[l][1], msp_list[l][2], weight="{0:.2f}".format(msp_list[l][0]))
    pos = nx.circular_layout(G)

    for l in range(0, len(msp_list_deleted)):
        deleted.add_edge(msp_list_deleted[l][1], msp_list_deleted[l][2],
                         weight="{0:.2f}".format(msp_list_deleted[l][0]))

    for l in range(0, len(msp_list_remain)):
        remain.add_edge(msp_list_remain[l][1], msp_list_remain[l][2], weight="{0:.2f}".format(msp_list_remain[l][0]))

    nx.draw(G, pos)
    edge_labels = dict([((u, v,), d['weight']) for u, v, d in G.edges(data=True)])
    edge_labels_deleted = dict([((u, v,), d['weight']) for u, v, d in deleted.edges(data=True)])
    edge_labels_remain = dict([((u, v,), d['weight']) for u, v, d in remain.edges(data=True)])

    nx.draw_networkx_edges(G, pos, edge_labels=edge_labels_deleted)
    nx.draw_networkx_edge_labels(remain, pos, edge_labels=edge_labels)
    nx.draw_networkx_edges(deleted, pos, edge_labels=edge_labels_remain, width=3, edge_color='w', style='dashed')
    plt.savefig(name + ".png")

def plot_graph_3D(graph, I_shape, plot_terminal=True, plot_weights=True, font_size=7):
    w_h = I_shape[1] * I_shape[2]
    X, Y = np.mgrid[:I_shape[1], :I_shape[2]]
    aux = np.array([Y.ravel(), X[::-1].ravel()]).T
    positions = {i: aux[i] for i in xrange(w_h)}

    for i in xrange(1, I_shape[0]):
        for j in xrange(w_h):
            positions[w_h * i + j] = [positions[j][0] + 0.3 * i, positions[j][1] + 0.2 * i]

    positions['s'] = np.array([-1, int(I_shape[1] / 2)])
    positions['t'] = np.array([I_shape[2] + 0.2 * I_shape[0], int(I_shape[1] / 2)])

    nxg = graph.get_nx_graph()
    if not plot_terminal:
        nxg.remove_nodes_from(['s', 't'])

    nx.draw(nxg, pos=positions)
    nx.draw_networkx_labels(nxg, pos=positions)
    if plot_weights:
        edge_labels = dict([((u, v,), d['weight'])
                     for u, v, d in nxg.edges(data=True)])
        nx.draw_networkx_edge_labels(nxg, pos=positions, edge_labels=edge_labels, label_pos=0.3, font_size=font_size)
    plt.axis('equal')
    plt.show()

def report_ctg(ctg, filename):
    """
    Reports Clustered Task Graph in the Console and draws CTG in file
    :param ctg: clustered task graph
    :param filename: drawing file name
    :return: None
    """
    print "==========================================="
    print "      REPORTING CLUSTERED TASK GRAPH"
    print "==========================================="
    cluster_task_list_dict = {}
    cluster_weight_dict = {}
    for node in ctg.nodes():
        print ("\tCLUSTER #: "+str(node)+"\tTASKS:"+str(ctg.node[node]['TaskList'])+"\tUTILIZATION: " +
               str(ctg.node[node]['Utilization']))
        cluster_task_list_dict[node] = ctg.node[node]['TaskList']
    for edge in ctg.edges():
        print ("\tEDGE #: "+str(edge)+"\tWEIGHT: "+str(ctg.edge[edge[0]][edge[1]]['Weight']))
        cluster_weight_dict[edge] = ctg.edge[edge[0]][edge[1]]['Weight']
    print ("PREPARING GRAPH DRAWINGS...")
    pos = networkx.shell_layout(ctg)
    networkx.draw_networkx_nodes(ctg, pos, node_size=2200, node_color='#FAA5A5')
    networkx.draw_networkx_edges(ctg, pos)
    networkx.draw_networkx_edge_labels(ctg, pos, edge_labels=cluster_weight_dict)
    networkx.draw_networkx_labels(ctg, pos, labels=cluster_task_list_dict)
    plt.savefig("GraphDrawings/"+filename)
    plt.clf()
    print ("\033[35m* VIZ::\033[0mGRAPH DRAWINGS DONE, CHECK \"GraphDrawings/"+filename+"\"")
    return None

def display(g, title):
    """Displays a graph with the given title."""
    pos = nx.circular_layout(g)
    plt.figure()
    plt.title(title)
    nx.draw(g, pos)
    nx.draw_networkx_edge_labels(g, pos, font_size=20)

    def draw(self):
        g = self.graph
        pos = nx.spring_layout(self.graph,scale=2)
	node_colors = []
	for node in g.nodes():
	    if self.is_logical_node(node):
	        node_colors.append('g')
	    else:
	        node_colors.append('r')

        nx.draw_networkx_nodes(g, pos, nodelist=g.nodes(), node_color=node_colors, node_size=500, alpha=0.8)
        nx.draw_networkx_edges(g, pos, edgelist=g.edges(), edge_color=[( (float(g[u][v]['capacity'])*0.01)+10000 ) for (u,v) in g.edges()], edge_vmin=100, edge_vmax=1000, width=5, alpha=0.8)
        #nx.draw(self.graph,pos,font_size=8)
        #nxd.draw(self.graph)
        node_labels = {}
        for node in g.nodes():
            node_labels[node] = str(node)
        nx.draw_networkx_labels(g, pos, node_labels, font_size=10)
        edge_labels = {}
        for edge in g.edges():
            edge_labels[edge] = g[edge[0]][edge[1]]['capacity']
        nx.draw_networkx_edge_labels(g, pos, edge_labels, font_size=10)

        #nx.draw(g)
        #plt.draw()
        plt.axis('off')
        plt.show()

 def draw_graph(self, H, u, v, flow1, F1, flow2, F2):
     if not HAVE_PLT:
         return
     pos = nx.spring_layout(self.G)
     plt.subplot(1,2,1)
     plt.axis('off')
     nx.draw_networkx_nodes(self.G,pos)
     nx.draw_networkx_edges(self.G,pos)
     nx.draw_networkx_labels(self.G,pos)
     nx.draw_networkx_edge_labels(
         self.G, pos,
         edge_labels={(u,v):'{}/{}'.format(
               F1[u][v],
               self.G[u][v]['capacity']
             ) for (u,v,data) in nx.to_edgelist(self.G)})
     plt.title('before: flow={}'.format(flow1))
     plt.subplot(1,2,2)
     plt.axis('off')
     nx.draw_networkx_nodes(self.G,pos)
     nx.draw_networkx_edges(self.G,pos)
     nx.draw_networkx_edges(
         self.G, pos,
         edgelist=[(u,v)],
         width=3.0,
         edge_color='b')
     nx.draw_networkx_labels(self.G,pos)
     nx.draw_networkx_edge_labels(
         self.G, pos,
         edge_labels={(u,v):'{}/{}'.format(
               F2[u][v],H[u][v]['capacity']
             ) for (u,v,data) in nx.to_edgelist(self.G)})
     plt.title('after: flow={}'.format(flow2))

    def draw(self, highlight_edges=None, show_weights=False, save_draw=False, map_name = 'duckietown_map'):
        plt.close('all')
        nxg = nx.DiGraph()
        edges = [(e.source, e.target, {'weight':e.weight, 'inv_weight':1.0/e.weight, 'action':e.action}) for node_set in self._edges.values() for e in node_set]
        nxg.add_edges_from(edges)
        if len(self.node_positions) < len(self._nodes):
            # Calculate positions for nodes whose pos is not specified.
            pos = nx.spring_layout(nxg, weight='inv_weight', pos=self.node_positions, fixed=self.node_positions.keys() if self.node_positions else None)
        else:
            pos = self.node_positions
        
        f = plt.figure(figsize=(12,20))
        plt.gca().set_aspect('auto')
        nx.draw_networkx_nodes(nxg, pos, node_color='w')
        nx.draw_networkx_edges(nxg, pos, edges)
        nx.draw_networkx_labels(nxg, pos)
        if show_weights:
            edge_labels=dict([((u,v,),"%s" % (d['weight'])) for u,v,d in nxg.edges(data=True)])
            nx.draw_networkx_edge_labels(nxg, pos, edge_labels=edge_labels)

        if highlight_edges:
            nx.draw_networkx_edges(nxg, pos, highlight_edges, edge_color='r')
        plt.axis('off')
        if not save_draw:
            plt.show()
        else:
            script_dir = os.path.dirname(__file__)
            map_path = script_dir + '/maps/' + map_name + '.png'
            plt.savefig(map_path)

def draw_graph(graph, graph_layout='shell',
               node_size=1600, node_color='blue', node_alpha=0.3, node_text_size=12,
               edge_color='blue', edge_alpha=0.3, edge_tickness=1, edge_text_pos=0.3,
               text_font='sans-serif', save=True, filename=None):

    edge_labels=dict([((u,v,),d['weight']) for u,v,d in graph.edges(data=True)])
    # these are different layouts for the network you may try
    # shell seems to work best
    if graph_layout == 'spring':
        graph_pos=nx.spring_layout(graph)
    elif graph_layout == 'spectral':
        graph_pos=nx.spectral_layout(graph)
    elif graph_layout == 'random':
        graph_pos=nx.random_layout(graph)
    elif graph_layout == 'circular':
        graph_pos=nx.circular_layout(graph)
    else:
        graph_pos=nx.shell_layout(graph)

    # draw graph
    nx.draw_networkx_nodes(graph, graph_pos, node_size=node_size, alpha=node_alpha, node_color=node_color)
    nx.draw_networkx_edges(graph, graph_pos, width=edge_tickness, alpha=edge_alpha, edge_color=edge_color)
    nx.draw_networkx_labels(graph, graph_pos, font_size=node_text_size, font_family=text_font)
    nx.draw_networkx_edge_labels(graph, graph_pos, edge_labels=edge_labels, label_pos=edge_text_pos)

    # show graph
    if save == True:
        plt.savefig(filename, dpi=1000)
    plt.show()

def draw_graph(G, labels=None, graph_layout='shell',
               node_size=1600, node_color='blue', node_alpha=0.3,
               node_text_size=12,
               edge_color='blue', edge_alpha=0.3, edge_tickness=1,
               edge_text_pos=0.3,
               text_font='sans-serif'):
                   
    # these are different layouts for the network you may try
    # shell seems to work best
    if graph_layout == 'spring':
        graph_pos=nx.spring_layout(G)
    elif graph_layout == 'spectral':
        graph_pos=nx.spectral_layout(G)
    elif graph_layout == 'random':
        graph_pos=nx.random_layout(G)
    else:
        graph_pos=nx.shell_layout(G)

    # draw graph
    nx.draw_networkx_nodes(G,graph_pos,node_size=node_size, 
                           alpha=node_alpha, node_color=node_color)
    nx.draw_networkx_edges(G,graph_pos,width=edge_tickness,
                           alpha=edge_alpha,edge_color=edge_color)
    nx.draw_networkx_labels(G, graph_pos, font_size=node_text_size,
                            font_family=text_font)
                            
    edge_labs=dict([((u,v,),d['label'])
             for u,v,d in G.edges(data=True)])     

    nx.draw_networkx_edge_labels(G, graph_pos, edge_labels=edge_labs, font_size=node_text_size,
                            font_family=text_font)

    # show graph
    plt.show()

    def draw(self, highlight_edges=None):
        nxg = nx.DiGraph()
        edges = [(e.source, e.target, {'weight':e.weight, 'inv_weight':1.0/e.weight}) for node_set in self._edges.values() for e in node_set]
        nxg.add_edges_from(edges)
        if len(self.node_positions) < len(self._nodes):
            # Calculate positions for nodes whose pos is not specified.
            pos = nx.spring_layout(nxg, weight='inv_weight', pos=self.node_positions, fixed=self.node_positions.keys() if self.node_positions else None)
        else:
            pos = self.node_positions

        f = plt.figure(figsize=(12,12))
        plt.gca().set_aspect('equal', adjustable='box')
        nx.draw_networkx_nodes(nxg, pos, node_color='w')
        nx.draw_networkx_edges(nxg, pos, edges)
        nx.draw_networkx_labels(nxg, pos)
        edge_labels=dict([((u,v,),"%s" % d['weight'])
                 for u,v,d in nxg.edges(data=True)])
        nx.draw_networkx_edge_labels(nxg, pos, edge_labels=edge_labels)


        if highlight_edges:
            nx.draw_networkx_edges(nxg, pos, highlight_edges, edge_color='r')
        
        plt.axis('off')
        plt.show()

def display_graph(graph, edge_width=2):
    nodes = graph.nodes(data=True)
    edges = graph.edges(data=True)
    edgecapwidth = [d['capacity'] for (u,v,d) in edges]
    edgeloadwidth = [d['load'] for (u,v,d) in edges]
    max_cap = 1.0
    
    for i in range(len(edgeloadwidth)): # reverse edges for negative load
        if edgeloadwidth[i] < 0:
            u,v,d = edges[i]
            edges[i] = (v,u,d) 
    for cap in edgecapwidth: # get max cap to scale edge drawing
        if cap > max_cap:
            max_cap = cap
    width_mod = edge_width/(1.0*max_cap)
    for i in range(len(edgecapwidth)):
        edgecapwidth[i] *= width_mod
        edgeloadwidth[i]*= width_mod
        
    #labels = [str(d['load']) + '/' + str(d['capacity']) for u,v,d in edges]
    labels = [str(abs(round(d['load'],3))) + '/' + str(round(d['capacity'],3)) for u,v,d in edges]
    e_labels=dict(zip(graph.edges(), labels))
    pos = nx.spring_layout(graph, iterations=100)
    nx.draw_networkx_nodes(graph, pos, node_size=300)
    nx.draw_networkx_labels(graph,pos)
    nx.draw_networkx_edges(graph, pos, edgelist=edges, width=edgecapwidth,edge_color = 'b')
    nx.draw_networkx_edges(graph, pos, edgelist=edges, width=edgeloadwidth,edge_color = 'r', alpha = 0.9)
    labels=dict(zip(graph.edges(),[d for u,v,d in graph.edges(data=True)]))
    nx.draw_networkx_edge_labels(graph, pos, edge_labels=e_labels)
    plt.show()

def plot_graph(g):
    pos = nx.spring_layout(g)
    pylab.figure(1)
    nx.draw(g, pos)
    edge_labels = dict([((u, v), d['weight']) for u, v, d in g.edges(data=True)])
    nx.draw_networkx_edge_labels(g, pos, edge_labels=edge_labels)
    pylab.show()

def draw_geograph(g, node_color='r', edge_color='b', node_label_field=None,
                  edge_label_field=None, node_size=200, node_label_x_offset=0, 
                  node_label_y_offset=0, node_label_font_size=12, 
                  node_label_font_color='k'):
    """
    Simple function to draw a geograph via matplotlib/networkx
    Uses geograph coords (projects if needed) as node positions
    """

    # transform to projected if not done so
    flat_coords = g.transform_coords(gm.PROJ4_FLAT_EARTH)

    node_pos = {nd: flat_coords[nd] for nd in g.nodes()}
    label_pos = {nd: [flat_coords[nd][0] + node_label_x_offset, 
                      flat_coords[nd][1] + node_label_y_offset] 
                      for nd in g.nodes()}

    # Draw nodes
    nx.draw_networkx(g, pos=node_pos, node_color=node_color,
        with_labels=False, edge_color=edge_color, node_size=node_size)

    if node_label_field:
        if node_label_field != 'ix':
            label_vals = nx.get_node_attributes(g, node_label_field)
            nx.draw_networkx_labels(g, label_pos, labels=label_vals, 
                font_size=node_label_font_size, font_color=node_label_font_color)

        else: # label via ids
            nx.draw_networkx_labels(g, label_pos, labels=g.nodes(), 
                font_size=node_label_font_size, font_color=node_label_font_color)

    # handle edge labels if needed
    if edge_label_field:
        edge_labels = nx.get_edge_attributes(g, edge_label_field)
        nx.draw_networkx_edge_labels(g, pos=node_pos, edge_labels=edge_labels)

    def TempCvsCgrapher(OriginalDict, DicDic):
        G = nx.DiGraph()
        keys1 = DicDic.keys()
        for item1 in keys1:
            G.add_node(item1)
        
        for item in keys1:
            Dic2 = DicDic[item]
            #f.write( item + " has "+ str(len(XMLutility.DicToList(Dic2))) +" " + key1 
            Keys2 = Dic2.keys()

            for item2 in Keys2:
                G.add_weighted_edges_from( [(item, item2, len(Dic2[item2]))]  )
                #G.add_edge(item, item2, weight = len(Dic2[item2]))
        
        #nx.draw(G, with_labels = True)
        edge_labels=dict([((u,v,),d['weight']) for u,v,d in G.edges(data=True)])
        
        edge_colors = ['black' for edge in G.edges()]
        pos=nx.spring_layout(G)
        nx.draw_networkx_edge_labels(G,pos, edge_labels=edge_labels)
        nx.draw(G ,pos, with_labels = True, edge_color=edge_colors, arrows =True)
        
        
        plt.show()

def draw_graph(arr_graph):
    """
    Draw a directed graph.
    """

    try:
        import matplotlib.pyplot as plt
    except:
        raise
    import networkx as nx

    g = nx.DiGraph()
    edge_set = {}

    # Set the edges and nodes
    for i in range(len(arr_graph)):
        for j in range(len(arr_graph[i])):
            if arr_graph[i][j] is not 0 and arr_graph[i][j] is not sys.maxsize:
                g.add_edge(i, j, weight=0.1)
                edge_set[(i, j)] = arr_graph[i][j]

    # Positions for all nodes.
    pos = nx.spring_layout(g)
    # Nodes
    nx.draw_networkx_nodes(g, pos, node_size=700, node_color="white")
    # Edges
    nx.draw_networkx_edges(g, pos, width=2, alpha=0.5, edge_color='black')
    # Labels
    nx.draw_networkx_labels(g, pos, font_size=15, font_family='sans-serif')
    # Edges' labels
    nx.draw_networkx_edge_labels(g, pos, edge_set, label_pos=0.3)

    plt.axis('off')
    # plt.savefig("weighted_graph.png")  # Save as png.
    plt.show()  # Display

def show_map(graph_data, node_colors = None):
    G = nx.Graph(graph_data['graph_dict'])
    node_colors = node_colors or graph_data['node_colors']
    node_positions = graph_data['node_positions']
    node_label_pos = graph_data['node_label_positions']
    edge_weights= graph_data['edge_weights']
    
    # set the size of the plot
    plt.figure(figsize=(18,13))
    # draw the graph (both nodes and edges) with locations from romania_locations
    nx.draw(G, pos={k: node_positions[k] for k in G.nodes()},
            node_color=[node_colors[node] for node in G.nodes()], linewidths=0.3, edgecolors='k')

    # draw labels for nodes
    node_label_handles = nx.draw_networkx_labels(G, pos=node_label_pos, font_size=14)
    
    # add a white bounding box behind the node labels
    [label.set_bbox(dict(facecolor='white', edgecolor='none')) for label in node_label_handles.values()]

    # add edge lables to the graph
    nx.draw_networkx_edge_labels(G, pos=node_positions, edge_labels=edge_weights, font_size=14)
    
    # add a legend
    white_circle = lines.Line2D([], [], color="white", marker='o', markersize=15, markerfacecolor="white")
    orange_circle = lines.Line2D([], [], color="orange", marker='o', markersize=15, markerfacecolor="orange")
    red_circle = lines.Line2D([], [], color="red", marker='o', markersize=15, markerfacecolor="red")
    gray_circle = lines.Line2D([], [], color="gray", marker='o', markersize=15, markerfacecolor="gray")
    green_circle = lines.Line2D([], [], color="green", marker='o', markersize=15, markerfacecolor="green")
    plt.legend((white_circle, orange_circle, red_circle, gray_circle, green_circle),
               ('Un-explored', 'Frontier', 'Currently Exploring', 'Explored', 'Final Solution'),
               numpoints=1, prop={'size':16}, loc=(.8,.75))
    
    # show the plot. No need to use in notebooks. nx.draw will show the graph itself.
    plt.show()

 def show_graph(self):
     graph = nx.Graph(self.graph)
     pos = nx.circular_layout(graph)
     # pos=nx.spectral_layout(graph)
     nx.draw_networkx_nodes(graph, pos, node_color="r", node_size=500, alpha=0.8)
     nx.draw_networkx_edges(graph, pos, width=1, alpha=0.5)
     nx.draw_networkx_edges(
         graph, pos, edge_labels={}, edgelist=self.get_edgelist(), width=8, alpha=0.5, edge_color="r"
     )
     nx.draw_networkx_edge_labels(graph, pos, self.get_list_weights_edge(), label_pos=0.3)
     labels = self.set_labels()
     nx.draw_networkx_labels(graph, pos, labels, font_size=16)
     plt.title("Dijkstra")
     plt.text(
         0.5,
         0.97,
         "Start: " + str(self.start) + " End: " + str(self.end),
         horizontalalignment="center",
         transform=plt.gca().transAxes,
     )
     plt.text(
         0.5,
         0.94,
         "Shortest Path: " + str(self.shortest_path),
         horizontalalignment="center",
         transform=plt.gca().transAxes,
     )
     plt.text(
         0.5, 0.90, "Weights: " + str(self.weights), horizontalalignment="center", transform=plt.gca().transAxes
     )
     plt.text(0.5, 0.86, "Pred: " + str(self.Preds), horizontalalignment="center", transform=plt.gca().transAxes)
     plt.axis("off")
     plt.ion()
     plt.show()

 def visualize(self, edgelabel='control', current_node=None,
               draw='pygraphviz'):
     """
     Visualizes a LOMAP system model.
     """
     assert edgelabel is None or nx.is_weighted(self.g, weight=edgelabel)
     if draw == 'pygraphviz':
         nx.view_pygraphviz(self.g, edgelabel)
     elif draw == 'matplotlib':
         pos = nx.get_node_attributes(self.g, 'location')
         if len(pos) != self.g.number_of_nodes():
             pos = nx.spring_layout(self.g)
         if current_node is None:
             colors = 'r'
         else:
             if current_node == 'init':
                 current_node = next(self.init.iterkeys())
             colors = dict([(v, 'r') for v in self.g])
             colors[current_node] = 'b'
             colors = colors.values()
         nx.draw(self.g, pos=pos, node_color=colors)
         nx.draw_networkx_labels(self.g, pos=pos)
         edge_labels = nx.get_edge_attributes(self.g, edgelabel)
         nx.draw_networkx_edge_labels(self.g, pos=pos,
                                      edge_labels=edge_labels)
     else:
         raise ValueError('Expected parameter draw to be either:'
                          + '"pygraphviz" or "matplotlib"!')

 def drawGraph(G):
     pos = nx.spring_layout(G)
     edge_labels = dict([((u, v,), d['weight'])
                         for u, v, d in G.edges(data=True)])
     nx.draw(G, pos, with_labels=True)
     nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
     plt.show()