def graphFromList(edge_list, node_prefix='', directed=True):
    """Creates a basic graph out of an edge list.
    
    The edge list has to be a list of tuples representing
    the nodes connected by the edge.
    The values can be anything: bool, int, float, str.
    
    If the graph is undirected by default, it is only
    calculated from one of the symmetric halves of the matrix.

    If the graph has weighted edges, edge_list will be of the 
    form:
        [ (vert1, vert2, weight), ... ]
    else:
        [ (vert1, vert2), ... ]
    
    """
    weighted = len(edge_list[0]) % 2
    if directed:
            graph = Dot(graph_type='digraph')
    else:
            graph = Dot(graph_type='graph')
    for edge in edge_list:
            e = Edge(node_prefix+str(edge[0]), node_prefix+str(edge[1]))
            if weighted:
                e.label = e.weight = edge[2]
            graph.add_edge(e)
    return graph

    def write(self, filename, format="png", append_ext=False, prog="dot"):
        "Builds a pydot graph and writes to file"
        from pydot import Dot, Edge, Node

        dot = Dot(graph_type='digraph', **self.graph_attributes)
        if format not in dot.formats:
            raise GraphException("invalid format '%s'" % format)
        node_cache = {}

        def get_node(s):
            try:
                return node_cache[s]
            except KeyError:
                node = Node(s, **self.node_attributes.get(s, {}))
                dot.add_node(node)
                node_cache[s] = node
                return node

        for (s0, s1), attr in self.edge_attributes.iteritems():
            dot.add_edge(Edge(get_node(s0), get_node(s1),
                            **self.edge_attributes.get((s0, s1), {})))

        for node in self.get_orphaned_nodes():
            get_node(node)

        if append_ext:
            filename = "%s.%s" % (filename, format)
        dot.write(filename, format=format, prog=prog)

def buildDependencyControlGraph(dependencies,sizes=[1,2],productionTarget=1.25):
    from pydot import Dot, Node, Edge, Cluster
    
    dgraph = Dot(graph_type='graph',fontname='Verdana',splines="line",maxiter="500")
    #splines="line",
    nodes = {}
    edges = {}
    
    for (controlMap,pvalue) in dependencies:
        targetNames = []
        size = len(controlMap)
        if size not in sizes:
            continue
        for (targetName,cvalue) in controlMap.items():
            #targetTag = "%s(%s)" % (targetName,cvalue)
            targetTag = targetName
            targetNames.append(targetTag)
            if size not in nodes.keys():
                nodes[size] = set()
            nodes[size].add((targetName,cvalue))            
        edgeCombos = combinations(targetNames,2)
        for value in edgeCombos:
            key = list(value)
            key.sort()
            (e1,e2) = key
            if (e1,e2) not in edges.keys() and (e2,e1) not in edges.keys():
                edge = Edge(e1,e2)
                edges[(e1,e2)] = edge
            else:
                #print "dup key %s %s" % (e1,e2)
                pass
            
    nodes = cleanNodeNames(nodes)
    
    for (key,nodeValues) in nodes.items():
        if key == 1:
            ishape = "rectangle"
        elif key == 2:
            ishape = "oval"
        elif key == 3:
            ishape = "hexagon"
        else:
            ishape = "circle"
        
        for (name,value) in nodeValues:
            icolor = "black"
            if value > 0:
                icolor = "red"
            if value < 0:
                icolor = "green"
            targetTag = "%s(%s)" % (name,value)
            targetTag = name       
            dgraph.add_node(Node(targetTag,shape=ishape,color=icolor))
            #print "Node: [%s] : size[%s] value[%s] shape[%s]" % (name,key,value,ishape)
        
    for (key,edge) in edges.items():
        dgraph.add_edge(edge)
    
    return dgraph 

    def write(self, f_name):
        """write the DOT file to *fName*

        """
        for node in self.node_list:
            node.sync()
        Dot.write(self, f_name)
        # FixQuoteBug(fName, float(self.net_desc['link_attr']['delay']))
        FixQuoteBug(f_name)

    def handle(self, filename=None, **options):
        try:
            from pydot import Dot, Edge, Node
        except ImportError:
            raise CommandError("need pydot python module ( apt-get install python-pydot )")

        graph = Dot()

        for status, description in STATUS_CHOICES:
            graph.add_node(Node(
                'status-%s' % status,
                label='"%s (%s)"' %
                    (description.encode('utf-8'), status))
            )

        from sadiki.core.workflow import workflow
        for transition_index in workflow.available_transitions():
            transition = workflow.get_transition_by_index(transition_index)
            graph.add_edge(Edge(
                'status-%s'% transition.src,
                'status-%s' % transition.dst,
                label='"%s (%s)"' % (transition.comment.encode('utf-8'), transition.index),
                style='solid' if transition.required_permissions else 'dashed',
            ))

        if filename:
            graph.write_png(filename)
        else:
            print graph.to_string()

class PydotAstWalker(object):

    def __init__(self, ast_root, course_code, valid_expr=True):
        self.course_code = course_code
        self.valid_expr = valid_expr
        self.ast = ast_root
        self.graph = Dot(graph_type='digraph')

    def _name_node(self, node):
        if node.is_course():
            # what if not leaf node?
            return node.code
        elif node.is_operator():
            name = str(node)
            for child in node.children:
                name += self._name_node(child)
            return name

    def generate_graph(self):
        course_root_node = Node(self.course_code, style="filled", colorscheme="set35", fillcolor="5")
        if not self.ast:
            if not self.valid_expr:
                return Node(self.course_code, style="filled", colorscheme="set35", fillcolor="4")
            else:
                return course_root_node
        edges = set()
        root_operator_node = self._visit_node(self.ast, edges)
        for edge in edges:
            self.graph.add_edge(edge.to_pydot_edge())
        self.graph.add_node(course_root_node)
        self.graph.add_edge(Edge(course_root_node, root_operator_node))
        return self.graph

    def _visit_node(self, ast_node, edges):
        if ast_node.is_course():
            node = Node(ast_node.code, style="filled", colorscheme="set35", fillcolor="2")
            self.graph.add_node(node)
            if not ast_node.is_leaf():
                child = self._visit_node(ast_node.child, edges)
                edge = UniqueEdge(node, child)
                edges.add(edge)
            return node
        elif ast_node.is_operator():
            name = self._name_node(ast_node)
            if isinstance(ast_node, AllOf):
                this_node = Node(name, label=str(ast_node), shape="square", style="filled", colorscheme="set35", fillcolor="3")
            else:
                this_node = Node(name, label=str(ast_node), shape="diamond", style="filled", colorscheme="set35", fillcolor="1")
            self.graph.add_node(this_node)
            child_nodes = [self._visit_node(child, edges) for child in ast_node.children]
            for child in child_nodes:
                edge = UniqueEdge(this_node, child)
                edges.add(edge)
            return this_node

    def create_graph_from_workflow(self, workflow):
        """
        :type workflow: Workflow
        :rtype: Dot
        """
        known_nodes = {}
        start = workflow.getStartNode()
        name = workflow.getName()
        g = Dot(graph_name=name, ranksep=1,
                labelloc="t", label="workflow: " + name, fontsize=18, fontcolor="blue")
        g.set_node_defaults(shape="box", fontsize=12)
        g.set_edge_defaults(fontsize=13, labeldistance=3)

        def add_node_rek(node):
            """Recurses through the workflow graph and adds nodes and edges.
            Repeated nodes are ignored (cycle detection).
            :type node: core.tree.Node
            """
            name = node.getName()
            if name in known_nodes:
                return known_nodes[name]
            dot_node = Node(name=name)
            g.add_node(dot_node)
            known_nodes[name] = dot_node
            logg.debug("created node %s", name)
            try:
                true_next_id = node.getTrueId()
            except:
                true_next_id = None
            if true_next_id:
                true_next = workflow.getStep(true_next_id)
                true_dot_next = add_node_rek(true_next)
                true_label = node.getTrueLabel() or " "
                g.add_edge(true_edge(dot_node, true_dot_next, label=true_label))
                logg.debug("created True edge: %s -> %s", name, true_next_id)
            try:
                false_next_id = node.getFalseId()
            except:
                false_next_id = None
            if false_next_id:
                false_next = workflow.getStep(false_next_id)
                false_dot_next = add_node_rek(false_next)
                false_label = node.getFalseLabel() or " "
                g.add_edge(false_edge(dot_node, false_dot_next, label=false_label))
                logg.debug("created False edge: %s -> %s", name, false_next_id)

            if not (true_next_id or false_next_id):
                # end node with no connections
                dot_node.set("color", "#04B45F")
            return dot_node
        # traverse from start node
        add_node_rek(start)
        return g

def main(infilename, outfilename):
    state_obj = yaml.load(open(infilename))
    assert(isinstance(state_obj, dict))
    assert(len(state_obj) == 1)
    state_obj = state_obj.values()[0]
    assert(isinstance(state_obj, list))
    graph = Dot("states", graph_type='digraph')

    # First, create all graph nodes
    nodes, nodemap = generate_nodes(graph, state_obj)
    # Then, generate our links
    generate_links(graph, state_obj, nodes, nodemap)
    graph.write(outfilename)

class Graph(object):
	def __init__(self, sentence):
		self.dot = Dot()
		self.parse_sentence(sentence)

	def add(self, word1, word2):
		self.dot.add_edge(Edge(word1, word2))
		return word1
		
	def instantiate(self, word):
		return self.add(uniqueid(), word)
	
	def parse_sentence(self, sentence):
		for word1, word2 in pairwise(map(self.instantiate,tokenize(sentence))):
			self.add(word1, word2)

def main():
    # setup.py install/develop creates an executable that calls this function
    options = parse_args(get_parser(), sys.argv[1:])
    deps = list(read_file(options.input))
    graph = Dot(
        "Dependencies",
        graph_type='digraph',
        rankdir='LR',
        label=sys.argv[1].split('.')[0],
        fontname='Impact',
        fontcolor="grey50",
        fontsize=36,
    )
    add_nodes(graph, get_tree(deps))
    add_edges(graph, deps)
    print(graph.to_string())

def RenderSIPCollection(sipGraph, dot=None):
    try:
        from pydot import Node, Edge, Dot
    except:
        import warnings
        warnings.warn("Missing pydot library", ImportWarning)
    if not dot:
        dot = Dot(graph_type='digraph')
        dot.leftNodesLookup = {}
    nodes = {}
    for N, prop, q in sipGraph.query(
            'SELECT ?N ?prop ?q {  ?prop a magic:SipArc . ?N ?prop ?q . }',
            initNs={u'magic': MAGIC}):

        if MAGIC.BoundHeadPredicate in sipGraph.objects(
                subject=N, predicate=RDF.type):
            NCol = [N]
        else:
            NCol = Collection(sipGraph, N)

        if q not in nodes:
            newNode = Node(makeMD5Digest(q),
                           label=normalizeTerm(q, sipGraph),
                           shape='plaintext')
            nodes[q] = newNode
            dot.add_node(newNode)

        bNode = BNode()
        nodeLabel = ', '.join([normalizeTerm(term, sipGraph)
                               for term in NCol])
        edgeLabel = ', '.join([var.n3()
                               for var in Collection(sipGraph,
                                                     first(sipGraph.objects(
                                                         prop, MAGIC.bindings)))])
        markedEdgeLabel = ''
        if nodeLabel in dot.leftNodesLookup:
            bNode, leftNode, markedEdgeLabel = dot.leftNodesLookup[nodeLabel]
            # print("\t", nodeLabel, edgeLabel,
            #       markedEdgeLabel, not edgeLabel == markedEdgeLabel
        else:
            leftNode = Node(makeMD5Digest(bNode),
                            label=nodeLabel, shape='plaintext')
            dot.leftNodesLookup[nodeLabel] = (bNode, leftNode, edgeLabel)
            nodes[bNode] = leftNode
            dot.add_node(leftNode)

        if not edgeLabel == markedEdgeLabel:
            edge = Edge(leftNode,
                        nodes[q],
                        label=edgeLabel)
            dot.add_edge(edge)
    return dot

 def draw(self, prob, targetFile):
     # Do the graphing stuff here...
     # Root graph
     g = Dot(graph_type="digraph", nodesep=2, overlap=False)
     #g.set_edge_defaults(weight="0", minlen="10")
     # Organise by adding constraints (adds edges too)
     for constr in prob.constrs:
         # Node for constraint
         constrNode = Node(constr.name, shape="ellipse", style="filled", fillcolor = "#aaaaff")
         constrNode.set_label(constr.name + ": " + constr.getTextFormula())
         g.add_node(constrNode)
         # Associated expressions
         for expr in constr.exprs:
             self.addNodesForChildren(g, expr, constr)
     # Finally, render
     #g.write_png("problem_structure.png", prog="dot")
     g.write_png(targetFile, prog="neato")

    def initPlugin(self, signalproxy):
        """Initialise the systemc block diagram plugin"""

        self.signalproxy = signalproxy
        self.do = signalproxy.distributedObjects

        # systemc stuff and and pointer type strings needed for casting in gdb
        # because systemc objects can be systemc modules, systemc ports, etc.
        self.ctx = None
        self.ctx_pointer = None
        self.ctx_func = "sc_get_curr_simcontext()"
        self.ctx_found = False

        self.ctx_type = "(sc_core::sc_simcontext*)"
        self.port_type = "(sc_core::sc_port_base*)"
        self.module_type = "(sc_core::sc_module*)"
        self.object_type = "(sc_core::sc_object*)"
        self.prim_channel_type = "(sc_core::sc_prim_channel*)"

        # dict with a string that represents the pointer as key and
        # a nested dict with parent, children, etc as key-values
        #   dst_dict[ptr] = {"wrapper":    vw,
        #                    "name":       None,
        #                    "parent_ptr": None,
        #                    "children":   {}}
        self.sysc_modules = {}
        self.sysc_objects = {}
        self.sysc_ports = {}
        self.sysc_prim_channels = {}

        # because of how we built the interface for the tracepoints on the
        # datagraph we first need to create an file obj. We choose StringIO
        # because it uses a string as buffer and does not acces the filesystem
        self._file_obj = StringIO()
        self.image = SVGImage("SystemC Block Diagram", self._file_obj)
        self.image_wrapper = SVGDataGraphVW(self.image, self.do)

        self.signalproxy.inferiorStoppedNormally.connect(self.update)

        # hook Datagraph variable wrapper into the datagraph controller
        # after self.action.commit is called the image will be displayed at the
        # datagraph
        self.action = self.do.actions.\
            getAddSVGToDatagraphAction(self.image_wrapper,
                                       self.do.
                                       datagraphController.addVar)

        # pydot graph visualization library
        self.block_diagram = Dot(graph_type='digraph')
        self.block_diagram.set_graph_defaults(compound='true',
                                              splines='ortho',
                                              rankdir='LR')
        self.block_diagram.set_node_defaults(shape='box')

        # Needed for creating the right variables and variable wrappers from
        # the systemc pointers
        self.vwFactory = VarWrapperFactory()
        self.variableList = VariableList(self.vwFactory, self.do)

    def save(self, cfg, filename, print_ir=False, format='dot', options=None):
        """Save basic block graph into a file.
        """
        if options is None:
            options = {}

        try:
            dot_graph = Dot(**self.graph_format)

            # Add nodes.
            nodes = {}
            for bb in cfg.basic_blocks:
                nodes[bb.address] = self._create_node(bb, cfg.name, print_ir, options)

                dot_graph.add_node(nodes[bb.address])

            # Add edges.
            for bb_src in cfg.basic_blocks:
                for bb_dst_addr, branch_type in bb_src.branches:
                    edge = self._create_edge(nodes[bb_src.address], nodes[bb_dst_addr], branch_type)

                    dot_graph.add_edge(edge)

            # Save graph.
            dot_graph.write("{}.{}".format(filename, format), format=format)
        except Exception:
            logger.error("Failed to save basic block graph: %s (%s)", filename, format, exc_info=True)

 def plot_state(self, boxes, deltas, name = '', outdir = None):
     """ Make a graph of a given state """
     graph = Dot(graph_type='digraph', fontname="Verdana", size="10, 5", fixedsize= True)
     i_box = 0
     for box in boxes:            
         textcolor = 'white' if sum( [ self.color_chars.index(col) for col in self.plots_conf[box]['color'].split('#')[1] ] ) < 35 else 'black' 
         node_box = Node(box, style="filled", label = '<<font POINT-SIZE="10" color="'+textcolor+'">'+box+'<br/> '+
                         "%.7f" % round(deltas[i_box], 7)+'</font>>',
             fillcolor = self.plots_conf[box]['color'], shape = self.plots_conf[box]['shape'])
         i_box += 1
         graph.add_node(node_box)
         
     for box_from, boxes_to in self.Flux.iteritems():
         for box_to, flux in boxes_to.iteritems():
             if flux !=0:
                 if flux > 0:
                     edge = Edge(box_from, box_to,  label = '<<font POINT-SIZE="10">'+str(flux)+'</font>>')
                 elif flux < 0:
                     edge = Edge(box_to, box_from,  label = '<<font POINT-SIZE="10">'+str(flux)+'</font>>')                
                 graph.add_edge(edge)
     
     if outdir is None:
         outdir = self.result_dir
         
     outfile = outdir+'/state'+name+'.png'
     graph.write_png(outfile)
     logger.info('State has been saved to '+set_style(outfile, 'emph'))

def get_session_svg(viz_data):
    """Take session visualization data and return svg."""
    
    graph = Dot('graphname', graph_type='digraph')
    
    #loop create all nodes and store by id
    node_dict = {}
    for i, node_data in enumerate(viz_data['nodes']):
        id = node_data['id']
        node_dict[id] = str(i)
        graph.add_node(Node(str(i)))
        
    #add edges by links
    for link_data in viz_data['links']:
        snode = node_dict[viz_data['nodes'][link_data['source']]['id']]
        tnode = node_dict[viz_data['nodes'][link_data['target']]['id']]
        graph.add_edge(Edge(snode, tnode))
    
    #get svg of graph
    file = NamedTemporaryFile()
    graph.write_svg(file.name)
    svg = file.read()
    file.close()
    
    #f = open('/tmp/session/session.svg', 'w')
    #f.write("%s\n" % svg)
    #f.close()

    return svg

    def save(self, filename, print_ir=False, format='dot'):
        """Save basic block graph into a file.
        """
        node_format = {
            'shape' : 'Mrecord',
            'rankdir' : 'LR',
            'fontname' : 'monospace',
            'fontsize' : '9.0'
        }

        edge_format = {
            'fontname' : 'monospace',
            'fontsize' : '8.0'
        }

        edge_colors = {
            'taken' : 'green',
            'not-taken' : 'red',
            'direct' : 'blue'
        }

        try:
            # for each conneted component
            for idx, gr in enumerate(networkx.connected_component_subgraphs(self._graph.to_undirected())):
                graph = Dot(graph_type="digraph", rankdir="TB")

                # add nodes
                nodes = {}
                for bb_addr in gr.node.keys():
                    dump = self._dump_bb(self._bb_by_addr[bb_addr], print_ir)

                    # html-encode colon character
                    dump = dump.replace("!", "!")
                    dump = dump.replace("#", "#")
                    dump = dump.replace(":", ":")
                    dump = dump.replace("{", "{")
                    dump = dump.replace("}", "}")

                    label = "{<f0> 0x%08x | %s}" % (bb_addr, dump)

                    nodes[bb_addr] = Node(bb_addr, label=label, **node_format)

                    graph.add_node(nodes[bb_addr])

                # add edges
                for bb_src_addr in gr.node.keys():
                    for bb_dst_addr, branch_type in self._bb_by_addr[bb_src_addr].branches:
                        graph.add_edge(Edge(nodes[bb_src_addr],
                            nodes[bb_dst_addr], label=branch_type, \
                            color=edge_colors[branch_type], **edge_format))

                graph.write("%s_%03d.%s" % (filename, idx, format), format=format)
        except Exception as err:
            import traceback
            import sys
            print("[E] Error loading BARF (%s:%d) : '%s'" %
                (__name__, sys.exc_traceback.tb_lineno, str(err)))
            print("")
            print(traceback.format_exc())

class TestUtilN3toDot(unittest.TestCase):
    def setUp(self):
        self.graph = Graph()
        self.graph.parse(StringIO(n3source), format="n3")
        self.dot = Dot()

    def test_util_graph_to_dot(self):
        res = graphutils.graph_to_dot(self.graph, self.dot)
        res = self.dot.to_string()
        self.assert_('swap/Primer#Person' in res, res)

def process_plan(filename, plan):
    graph = Dot()
    teams = fetch_teams()

    nodes = make_nodes(plan, teams)

    for team_node in nodes:
        graph.add_node(nodes[team_node])

    for team in plan:
        edges = graph_way(team, plan[team], nodes)
        for edge in edges:
            graph.add_edge(edge)

    graph.set_prog("circo")
    graph.write_png(filename)

 def build_site_graph(self):
     self.site_graph = Dot(graph_type='digraph')
     self.site_graph.set_label( 'Sitemap for "%s"' % self.base_uri )
     self.site_graph.set_simplify( True )
     # add nodes
     for page in self.site_dict['pages']:
         self.site_graph.add_node( page.to_node() )
     # add edges
     for page in self.site_dict['pages']:
         from_node = page.uri
         for link in page.attributes['links']:
           to_node = link
           self.site_graph.add_edge( Edge(from_node, to_node) )