def write_graphs_to_dots(self):
        assert self.build_graph
        self._load_packages()

        from pygraph.readwrite import dot

        base = self.output_dir

        with open(join(base, 'digraph.dot'), 'w') as f:
            data = dot.write(self.digraph)
            f.write(data)

        with open(join(base, 'bfs.dot'), 'w') as f:
            (st, order) = breadth_first_search(self.digraph)
            bfs = digraph()
            bfs.add_spanning_tree(st)
            data = dot.write(bfs)
            f.write(data)

        with open(join(base, 'dfs.dot'), 'w') as f:
            (st, pre, post) = depth_first_search(self.digraph)
            dfs = digraph()
            dfs.add_spanning_tree(st)
            data = dot.write(dfs)
            f.write(data)

 def test_a_b_c_d_square(self):
     depgraph = digraph()
     add_action(depgraph, "a#ta")
     add_action(depgraph, "b#tb")
     add_action(depgraph, "c#tc")
     add_action(depgraph, "d#td")
     depgraph.add_edge(("a#ta", "b#tb"))
     depgraph.add_edge(("a#ta", "d#td"))
     depgraph.add_edge(("c#tc", "b#tb"))
     depgraph.add_edge(("c#tc", "d#td"))
     (ise_model, xml, error) = self.order(depgraph)
     self.assertActionsNb(ise_model, 4)
     instructions = ise_model.instructions
     self.assertNotEquals(instructions, None)
     self.assertEquals(len(instructions), 1)
     par = instructions.pop()
     actions = self.assertParallel(par, nb=4)
     a = self.assertContainsAction(actions, "a#ta/Rule")
     b = self.assertContainsAction(actions, "b#tb/Rule")
     c = self.assertContainsAction(actions, "c#tc/Rule")
     d = self.assertContainsAction(actions, "d#td/Rule")
     self.assertAction(a, id="a#ta/Rule", deps=set(['b#tb/Rule', 'd#td/Rule']))
     self.assertAction(b, id="b#tb/Rule", deps=set())
     self.assertAction(c, id="c#tc/Rule", deps=set(['b#tb/Rule', 'd#td/Rule']))
     self.assertAction(d, id="d#td/Rule", deps=set())

def fix_orphan_nodes(commit_graph, release):
    new_graph = digraph()
    new_graph.add_nodes(commit_graph.nodes())
    [new_graph.add_edge(edge) for edge in commit_graph.edges()]
    orphan_nodes = [node for node in new_graph.nodes() if not new_graph.incidents(node)]
    [new_graph.add_edge((release, node)) for node in orphan_nodes if node != release]
    return new_graph

def init_graph():
	global g
	if(g):
		return g
	
	g = digraph()
	deps = []
	for cls, lst in manifest.declarations.iteritems():
		for declaration_id, dec in lst.iteritems():
			log.debug('adding node %r' % declaration_id)
			g.add_node(declaration_id)
			reqs = getattr(dec, 'require', [])
			if not(isinstance(reqs, (list, tuple))):
				reqs = [reqs]
			d = []
			for req in reqs:
				d.append([req.declaration_id, declaration_id])
			if(d):
				deps.append(d)
	
	for dep in deps:
		log.debug('adding edge %r' % dep)
		g.add_edge(*dep)
	
	return g

def create_object_graph(objects):
    # create dict to map objectname to file object
    mapped_objects = {}
    for o in objects:
        mapped_objects[o.get_object_name()] = o
    object_graph = digraph()
    object_graph.add_nodes([o.get_object_name() for o in objects])
    # Create relationship list
    successors = [(i.get_object_name(), [] if i.get_successors() is None else [mapped_objects[j] for j in i.get_successors()] ) for i in objects]
    #
    for obj, suc in successors:
        for s in suc:
            object_graph.add_edge((obj, s.get_object_name()))

    object_names = [o.get_object_name() for o in objects]
    for o in objects:
        # Bind objects to previous release
        predecessors = o.get_predecessors()
        if predecessors is not None:
            for p in predecessors:
                if p not in object_names:
                    if not object_graph.has_node(p):
                        object_graph.add_node(p)
                        object_graph.add_edge((p,o.get_object_name()))

    return object_graph

  def graphize(self):
    try:
      self.graph = pygraph.digraph()
    except (NameError, AttributeError):
      self.graph = digraph()   

    modules = [self.topModule] + self.moduleList
    # first, we must add all the nodes. Only then can we add all the edges
    self.graph.add_nodes(modules)

    # here we have a strictly directed graph, so we need only insert directed edges
    for module in modules:
      def checkParent(child):
        if module.name == child.parent:
          return True
        else:
          return False

      children = filter(checkParent, modules)
      for child in children:
        # due to compatibility issues, we need these try catch to pick the 
        # right function prototype.
        try:
          self.graph.add_edge(module,child) 
        except TypeError:
          self.graph.add_edge((module,child)) 

    def test_seq_a_b_n_actions(self):
        depgraph = digraph()
        na = random.randint(5, 10)
        actions = []
        for i in range(0, na):
            actions.append(("Rule"+str(i), "Cmd"+str(i)))

        add_action(depgraph, "a#ta", actions)

        nb = random.randint(5, 10)
        actions = []
        for i in range(0, nb):
            actions.append(("Rule"+str(i), "Cmd"+str(i)))

        add_action(depgraph, "b#tb", actions)
        depgraph.add_edge(("a#ta", "b#tb"))

        (ise_model, xml, error) = self.order(depgraph)
        self.assertActionsNb(ise_model, na+nb)
        instructions = ise_model.instructions
        self.assertNotEquals(instructions, None)
        self.assertEquals(len(instructions), 1)
        seq = instructions.pop()
        actions = self.assertSequence(seq, na+nb)
        for i in range(0, nb):
            self.assertAction(actions[i], id="b#tb/Rule"+str(i),
                              cs="b#tb", cmd="Cmd"+str(i))

        for i in range(0, na):
            self.assertAction(actions[nb+i], id="a#ta/Rule"+str(i),
                              cs="a#ta", cmd="Cmd"+str(i))

def build_bayes_graph(im,labels,sigma=1e2,kappa=2):
  """  Build a graph from 4-neighborhood of pixels.
    Foreground and background is determined from
    labels (1 for foreground, -1 for background, 0 otherwise)
    and is modeled with Gaussian Naive Bayes classifiers."""

  m,n = im.shape[:2]

  # RGB vector version (one pixel per row)
  vim = im.reshape((-1,3))

  # RGB for foreground and background
  foreground = im[labels==1].reshape((-1,3))
  background = im[labels==-1].reshape((-1,3))
  train_data = [foreground,background]

  print train_data
  # train naive Bayes classifier
  bc = bayes.BayesClassifier()
  bc.train(train_data)

  # get probabilities for all pixels
  bc_lables,prob = bc.classify(vim)
  prob_fg = prob[0]
  prob_bg = prob[1]

  # create graph with m*n+2 nodes
  gr = digraph()
  gr.add_nodes(range(m*n+2))

  source = m*n # second to last is source
  sink = m*n+1 # last node is sink

  # normalize
  for i in range(vim.shape[0]):
    vim[i] = vim[i] / linalg.norm(vim[i])

  # go through all nodes and add edges
  for i in range(m*n):
    # add edge from source
    gr.add_edge((source,i), wt=(prob_fg[i]/(prob_fg[i]+prob_bg[i])))

    # add edge to sink
    gr.add_edge((i,sink), wt=(prob_bg[i]/(prob_fg[i]+prob_bg[i])))

    # add edges to neighbors
    if i%n != 0: # left exists
      edge_wt = kappa*exp(-1.0*sum((vim[i]-vim[i-1])**2)/sigma)
      gr.add_edge((i,i-1), wt=edge_wt)
    if (i+1)%n != 0: # right exists
      edge_wt = kappa*exp(-1.0*sum((vim[i]-vim[i+1])**2)/sigma)
      gr.add_edge((i,i+1), wt=edge_wt)
    if i//n != 0: # up exists
      edge_wt = kappa*exp(-1.0*sum((vim[i]-vim[i-n])**2)/sigma)
      gr.add_edge((i,i-n), wt=edge_wt)
    if i//n != m-1: # down exists
      edge_wt = kappa*exp(-1.0*sum((vim[i]-vim[i+n])**2)/sigma)
      gr.add_edge((i,i+n), wt=edge_wt)

  return gr

def author_centrality(titles_to_authors):
    """
    Identifies the centrality of an author

    :param titles_to_authors: a dict keying title strings to the authors associated
    :type titles_to_authors: dict

    :return: a dict matching author to centrality
    :rtype: dict
    """
    author_graph = digraph()
    author_graph.add_nodes(map(lambda x: u"title_%s" % x, titles_to_authors.keys()))
    author_graph.add_nodes(list(set([u'author_%s' % author[u'user']
                                     for authors in titles_to_authors.values()
                                     for author in authors])))

    for title in titles_to_authors:
        for author in titles_to_authors[title]:
            try:
                author_graph.add_edge((u'title_%s' % title, u'author_%s' % author[u'user']))
            except AdditionError:
                pass

    centralities = dict([('_'.join(item[0].split('_')[1:]), item[1])
                         for item in pagerank(author_graph).items() if item[0].startswith(u'author_')])

    centrality_scaler = MinMaxScaler(centralities.values())

    return dict([(cent_author, centrality_scaler.scale(cent_val))
                 for cent_author, cent_val in centralities.items()])

def pygraphCrit(edgePairs, nameMap, timeMap, allEdts, allEvts, mainGuid):
    G = digraph()
    srcs = []
    dsts = []
    for i in range(len(edgePairs)):
        srcs.append(edgePairs[i][0])
        dsts.append(edgePairs[i][1])

    allNodes = set(srcs+dsts)
    for i in allNodes:
        if i == mainGuid:
            continue
        else:
            G.add_node(str(i))
    for i in range(len(edgePairs)):
        curTime = 0
        curSrc = str(edgePairs[i][0])
        curDst = str(edgePairs[i][1])
        if curSrc == mainGuid or curDst == mainGuid:
            continue
        if getNodeType(curSrc, allEdts, allEvts) == 'Event':
            curTime = 1
        else:
            curTime = edtGuidToTime(curSrc, timeMap)
        G.add_edge((curSrc, curDst), curTime)

    if len(critical_path(G)) == 0:
        print 'Cycle Detected, exiting; Please check that the OCR conifiguration file uses GUID type of COUNTED_MAP, and the application has no cycles.'
        print 'Dumping cycle below.'
        print find_cycle(G)
        os.remove(HTML_FILE_NAME)
        sys.exit(0)

    return critical_path(G)

def invert_weights(g):
    """
    Invert the weights of the given graph.

    The most expensive links will then be the cheapest and vice versa.
    """

    assert isinstance(g, digraph)

    # Determine the most expensive edge
    w = 0
    for (s,d) in g.edges():
        w = max(w, g.edge_weight((s,d)))
    print 'Maximum edge weight is %d' % w
    w += 1 # Make sure the most expensive edge will have a cost of 1 afterwards
    g_inv = digraph()
    for n in g.nodes():
        g_inv.add_node(n)
    for (s,d) in g.edges():
        assert g.edge_weight((s,d))<w
        w_inv = w-g.edge_weight((s,d))
        assert w_inv>0
        try:
            g_inv.add_edge((s,d), w_inv)
        except:
            assert g_inv.edge_weight((s,d)) == w_inv # This one fails
            print "Edge %d %d already in graph, ignoring .. " % (s,d)
    return g_inv

def sequential(m, nodes, coordinator):
    """
    Construct a simple two-level tree. The coordinator is the root, and all
    the other nodes are its children.

    The weights of edges are taken from m.

    @type m: graph
    @param m: The machine model. The weights for the edges in the binary_tree
        will be extracted from the model.

    @type nodes: list
    @param nodes: list of nodes to build a tree for. If list is
        empty, it will default to m.nodes()

    @type coordinator: number
    @param coordinator: This node will be the root of the tree

    @return digraph
    """
    assert(len(m.nodes())>0) # graph has nodes

    g = digraph()
    g.add_node(coordinator)

    for n in nodes:
        if n != coordinator:
            g.add_node(n)
            g.add_edge((coordinator, n), \
                           m.edge_weight((n, coordinator)))
    return g

def connect_graphs(g1, g2, connecting_edge, weight=1):
    """
    Build a new graph out of the two given graphs.

    Every node e in g1 will be represented as 1_e in the new graph and
    every node e' in g2 as 2_e'.

    @param connecting_edge: An edge (e_src, e_dst), where e_src is in
        g1 and e_dst is in g2. This edge will connect g1 with g2.
    @param weight: Weight of the connecting edge.
    """
    g = digraph()

    # Add nodes and edges
    for (index, gr) in [(1, g1), (2, g2)]:
        for n in gr.nodes():
            g.add_node('%d_%d' % (index, n))
        for (src, dst) in gr.edges():
            g.add_edge(('%d_%d' % (index, src),
                        '%d_%d' % (index, dst)),
                        g.edge_weight((src, dst)))

    # Connect subgraphs
    conn_src, conn_dst = connecting_edge
    g.add_edge(('%d_%d' % (1, conn_src),
                '%d_%d' % (2, conn_dst)))
    g.add_edge(('%d_%d' % (2, conn_dst),
                '%d_%d' % (1, conn_src)))

    return g

def merge_graphs(g1, g2):
    """
    Merge two graphs to a new graph (V, E) with V = g1.nodes \union g2.nodes
    and Edge e \in g1 or e \in g2 -> e \in E.
    """

    if g1.DIRECTED or g2.DIRECTED:
        g = digraph()
    else:
        g = graph()

    for n in g1.nodes():
        g.add_node(n)
    for n in g2.nodes():
        if not n in g.nodes():
            g.add_node(n)
    for e in g1.edges():
        try:
            g.add_edge(e, g1.edge_weight(e))
        except:
            logging.info("merge_graphs: adding edge %d %d failed" % (e[0], e[1]))
    for e in g2.edges():
        try:
            g.add_edge(e, g2.edge_weight(e))
        except:
            logging.info("merge_graphs: adding edge %d %d failed" % (e[0], e[1]))
    return g

def handle_recursive_calls(tpl_name, content):
    # create the call graph as a directed graph
    call_graph = digraph()

    # visited_templates items will look like this:
    # [("tpl1", "extends", "tpl2"), ...]
    visited_templates = [(tpl_name, "", "")]

    call_graph.add_node(tpl_name)
    i = 0
    while i < len(visited_templates):
        name = visited_templates[i][0]
        try:
            tpl_content = content if i == 0 else Template.objects.get(name=name).content
        except:
            i += 1
            continue

        called_tpls = get_called_templates(tpl_content, name)
        update_call_graph(call_graph, called_tpls)

        # raises InfiniteRecursivityError in case of a cycle
        cycle_test(call_graph, called_tpls)

        visited_templates.extend(called_tpls)
        i += 1

    def _build_tree(self, g):
        """
        We build a bad tree by inverting all edge weights and running
        an MST algorithm on the resulting graph.

        """
        # Build graph with inverted edges
        g_inv = algorithms.invert_weights(g)

        # Run binary tree algorithm
        mst_inv = minimal_spanning_tree(g_inv, self.get_root_node())

        # Build a new graph
        badtree = digraph()

        # Add nodes
        for n in g.nodes():
            badtree.add_node(n)

        # Add edges, copy weights from non-inverted graph
        for (e,s) in mst_inv.items():
            if s != None:
                badtree.add_edge((s, e), g.edge_weight((s, e)))

        return badtree

def author_centrality(titles_to_authors):
    author_graph = digraph()
    author_graph.add_nodes(map(lambda x: u"title_%s" % x,
                               titles_to_authors.keys()))
    author_graph.add_nodes(list(set(
        [u'author_%s' % author[u'user'] for authors in
         titles_to_authors.values() for author in authors])))

    for title in titles_to_authors:
        log.debug(u"Working on title: %s" % title)
        for author in titles_to_authors[title]:
            try:
                author_graph.add_edge(
                    (u'title_%s' % title, u'author_%s' % author[u'user']))
            except AdditionError:
                pass

    centralities = dict([
        ('_'.join(item[0].split('_')[1:]), item[1]) for item in
        pagerank(author_graph).items() if item[0].startswith(u'author_')])

    centrality_scaler = MinMaxScaler(centralities.values())

    return dict([(cent_author, centrality_scaler.scale(cent_val))
                 for cent_author, cent_val in centralities.items()])

    def referergraph(self, refererlist, drawpath):
        """
        Draw the graph of referers
        """

        gr = digraph()
        attr = list([('style', 'filled'), ('fillcolor', 'green'), ('shape', 'doublecircle')])

        #first add all referer
        for ref in refererlist:

            try:
                gr.add_node(ref.altname, attr)
            except pygraph.classes.exceptions.AdditionError as e:
                print e

            print "=========================="

        #now add the url that have the referer previously added
        for ref in refererlist:
            for url in ref.getlist:
                print url
                try:
                    gr.add_node(url[0])
                except pygraph.classes.exceptions.AdditionError as e:
                    print "From url: " + str(e)

                try:
                    gr.add_edge((ref.altname, url[0]),1,url[1])
                except pygraph.classes.exceptions.AdditionError as e:
                    print "Edge addition: " + str(e)

        return self.export(gr, drawpath, "referer")

    def calculate_results(self):

        # Don't bother if everyone's going to win
        super(SchulzeSTV, self).calculate_results()
        if hasattr(self, 'winners'):
            return

        # Generate the list of patterns we need to complete
        self.generate_completed_patterns()
        self.generate_vote_management_graph()

        # Build the graph of possible winners
        self.graph = digraph()
        for candidate_set in itertools.combinations(self.candidates, self.required_winners):
            self.graph.add_nodes([tuple(sorted(list(candidate_set)))])

        # Generate the edges between nodes
        for candidate_set in itertools.combinations(self.candidates, self.required_winners + 1):
            for candidate in candidate_set:
                other_candidates = sorted(set(candidate_set) - set([candidate]))
                completed = self.proportional_completion(candidate, other_candidates)
                weight = self.strength_of_vote_management(completed)
                if weight > 0:
                    for subset in itertools.combinations(other_candidates, len(other_candidates) - 1):
                        self.graph.add_edge((tuple(other_candidates), tuple(sorted(list(subset) + [candidate]))), weight)

        # Determine the winner through the Schwartz set heuristic
        self.graph_winner()

        # Split the "winner" into its candidate components
        self.winners = set(self.winner)
        del self.winner

    def __init__(self, robot, viewer = False):
        self.robot = robot
        self.env = robot.GetEnv ()
        self.grasping_locations_cache = {}
        self.viewMode = viewer
        self.tray_stack = []
        self.unMovableObjects = {self.env.GetKinBody('table')}
        self.objSequenceInPlan = []
        self.handled_objs = set()

        self.object_mover = ObjectMover(self.env, use_ros, self.unMovableObjects)

        self.obstruction_digraph = digraph()
        
        v = self.robot.GetActiveDOFValues()
        v[self.robot.GetJoint('torso_lift_joint').GetDOFIndex()]=1.0
        self.robot.SetDOFValues(v)      

        if use_ros:
            self.pr2robot = PR2Robot(self.env)
            self.pr2robot.robot = self.robot
            self.arm_mover = PR2MoveArm()
        
        #loading the IK models
        utils.pr2_tuck_arm(robot)
        robot.SetActiveManipulator('leftarm')
        ikmodel = openravepy.databases.inversekinematics.InverseKinematicsModel(
                        robot,iktype=openravepy.IkParameterization.Type.Transform6D)    
        if not ikmodel.load():
            ikmodel.autogenerate()            
        robot.SetActiveManipulator('rightarm')
        ikmodel = openravepy.databases.inversekinematics.InverseKinematicsModel(
            robot,iktype=openravepy.IkParameterization.Type.Transform6D)    
        if not ikmodel.load():
            ikmodel.autogenerate()