def get_reg_live_subsets(instrs, code, igraph):
    """Computes the subsets of the instructions where each register is live.
    Retunrs a dictionary keyed with the register name."""

    # compute the live subsets
    live_regs = dict()
    for reg in ('eax', 'ebx', 'ecx', 'edx', 'edi', 'esi', 'ebp', 'esp'):  # TODO: insn.REGS[:8]
        live_regs[reg] = Lifetime(reg, len(instrs))

    class live_filter(null_filter):
        def __call__(self, other, node):
            # always check 'other' which is the candidate. (includes root)
            # but also check if node is set which takes care of root
            if node and self.cur_reg not in other.IN:
                # print "forward filtered %s from %s (reg=%s)" % (
                #    str(other), str(node), self.cur_reg)
                return False
            return True

    # compute live regions for register values "born" withing this function
    live_f = live_filter()
    for ins in instrs:
        diff = ins.OUT - ins.IN
        if len(diff) > 1 and ins.mnem not in ("call", "cpuid", "rdtsc"):
            print "WARNING: more than one regs defined at", ins, ins.OUT, ins.IN
        for reg in diff:
            live_f.cur_reg = reg
            st, order = breadth_first_search(igraph, ins, live_f)
            live_regs[live_f.cur_reg].add_subset(order)

    # if a DEFed register is not in OUT it's an one-instr live region.
    # if that register is also in the implicit set of the instruction,
    # it will be marked as unswappable
    for ins in instrs:
        for reg in ins.DEF:
            if reg not in ins.OUT:
                # print "one-instr live region, register", reg, " in ", ins
                live_regs[reg].add_subset([ins])

    # add live regions for registers that where alive before this function
    # was called.
    if not instrs[0].f_entry:  # debug!
        print "BUG: compute_live: instrs[0] is not f_entry!!!"

    # print "compute_live_regions: checking", instrs[0]
    for reg in instrs[0].IN:
        # print "compute_live_regions: checking", reg, "in", instrs[0]
        live_f.cur_reg = reg
        st, order = breadth_first_search(igraph, instrs[0], live_f)
        # print reg, "live region", [i.pos for i in order]
        # let's handle the special case of region splitting for indirect calls
        live_regs[live_f.cur_reg].add_subset(order)

    return live_regs

 def testSanityDigraph(self):
     G = pygraph.digraph()
     G.generate(100, 500)
     st, lo = breadth_first_search(G)
     for each in G:
         if (st[each] != None):
             assert lo.index(each) > lo.index(st[each])

    def getSSAroundSS(self, solarSystemID, jumps):
        ss = self.getSSInfo(solarSystemID)

        color = 0
        if ss[2] > 0.5:
            color = "green"
        else:
            color = "red"

        ssRegion = colored(ss[0], color)
        ssName = colored(ss[1], color)
        ssSecruity = colored("%.1f" % ss[2], color)

        if self.ssgraph:
            gr = self.ssgraph
        else:
            gr = graph()
            nodes = self.getAllSS()
            gr.add_nodes(nodes)
            for edge in self.getAllSSEdges():
                gr.add_edge(edge)

        print "Searching for Solar Systems around %s: %s(%s) in %d jumps." % (ssRegion, ssName, ssSecruity, jumps)

        ssinrad = breadth_first_search(gr, solarSystemID, radius(jumps))
        ssinrad = ssinrad[1]

        text = "Found %d systems" % len(ssinrad)
        text = colored(text, "cyan")
        print "Done. %s, including current one." % text

        return ssinrad

def bfs_set_label(g, root, data, value, radius):
    from pygraph.algorithms.filters.radius import radius as Radius
    from pygraph.algorithms.searching import breadth_first_search
    gr = graph_pygraph(g)
    filt_radius = Radius(radius)
    _, o = breadth_first_search(gr, root, filt_radius)
    data[o] = value

	def _invalidate_caches(self):
		'invalidate the downstream caches of updated nodes'
		
		if len(self.updated) == 0:
			return
			
		# Sort the nodes in worklist and remove duplicates
		sg = topological_sorting(self.digraph) # sorted graph
		
		worklist = []
		# insert nodes into worklist in sorted order
		for node in sg:
			if node in self.updated:
				worklist.append(node)
		self.updated.clear()
		
		# iterate through worklist
		while worklist:
			node = worklist.pop() # one item at a time
			downstream = breadth_first_search(self.digraph, root=node)[1] # get all downstream labels
			for n in downstream:
				if n in worklist:
					# remove labels that will already be done
					worklist.remove(n)
				# remove cache entries
				self.cache[n] = None

    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 handle(self, **options):
        gr = graph()

        cats_by_id = dict((c.id, c) for c in Category.objects.all())

        # Add nodes
        dups = count()
        for c in cats_by_id.itervalues():
            try:
                gr.add_node(c)
            except AdditionError:
                dups.next()
                parent = cats_by_id.get(c.parent_id)
                print 'WARNING: duplicate node :: <Category %i | %s>' % (c.id, c)
                print '\twith parent ' + '<Category %i | %s>' % (parent.id, parent) if parent else 'None'

        if dups.next() > 0: return

        # Add edges
        # gr.add_edge((CONCRETE_NODE, ROOT_NODE))
        for c in cats_by_id.itervalues():
            parent = cats_by_id.get(c.parent_id)
            if parent:
                gr.add_edge((c, parent))

        # import ipdb; ipdb.set_trace()
        # The whole tree from the root
        st, order = breadth_first_search(gr, root=Category.objects.get(title="Abstract"))
        gst = digraph()
        gst.add_spanning_tree(st)

        dot = write(gst)
        gvv = gv.readstring(dot)

        gv.layout(gvv, 'dot')
        gv.render(gvv, 'pdf', os.path.join(output_dir, 'abstract.pdf'))

        st, order = breadth_first_search(gr, root=Category.objects.get(title="Concrete"))
        gst = digraph()
        gst.add_spanning_tree(st)

        dot = write(gst)
        gvv = gv.readstring(dot)

        gv.layout(gvv, 'dot')
        gv.render(gvv, 'pdf', os.path.join(output_dir, 'concrete.pdf'))

 def test_bfs_in_digraph(self):
     gr = testlib.new_digraph()
     st, lo = breadth_first_search(gr)
     for each in gr:
         if (st[each] != None):
             assert lo.index(each) > lo.index(st[each])
     for node in st:
         assert gr.has_edge((st[node], node)) or st[node] == None

 def test_bfs_in_digraph(self):
     gr = testlib.new_digraph()
     gr.add_node('find-me')
     gr.add_edge((0, 'find-me'))
     st, lo = breadth_first_search(gr, root=0, filter=find('find-me'))
     assert st['find-me'] == 0
     for each in st:
         assert st[each] == None or st[each] == 0 or st[st[each]] == 0

 def search(self):
     st, order = breadth_first_search(self.net, "book")
     gst = digraph()
     gst.add_spanning_tree(st)
     dot = write(gst, True)
     out_file = open("file.gv", "w")
     out_file.write(dot)
     out_file.close()

 def testDigraphBFS(self):
     G = pygraph.digraph()
     G.add_nodes([1, 2, 3, 4, 5, 6, 7, 8, 9])
     G.add_edge(1, 2)
     G.add_edge(1, 3)
     G.add_edge(2, 4)
     G.add_edge(3, 5)
     G.add_edge(4, 6)
     G.add_edge(5, 7)
     G.add_edge(1, 8, wt=3)
     G.add_edge(7, 8, wt=3)
     G.add_edge(8, 9)
     G.add_edge(3, 9)
     st, lo = breadth_first_search(G, 1, filter=filters.radius(2))
     assert st == {1: None, 2: 1, 3: 1, 4: 2, 5: 3, 9: 3}
     st, lo = breadth_first_search(G, 7, filter=filters.radius(2))
     assert st == {7: None}

def sample_gene_interactions(c, args, idx_to_sample):
    #fetch variant gene dict for all samples
    get_variant_genes(c, args, idx_to_sample)
    #file handle for fetching the hprd graph
    file_graph = os.path.join(path_dirname, 'hprd_interaction_graph')
    #load the graph using cPickle and close file handle
    gr = graph()
    f = open(file_graph, 'rb')
    gr = cPickle.load(f)
    f.close()
    k = []
    variants = []
    #calculate nodes from the graph
    hprd_genes = gr.nodes()
    if args.gene == None or args.gene not in hprd_genes:
        sys.stderr.write("gene name not given else not represented in the p-p interaction file\n")
    elif args.gene in hprd_genes:
        x, y = \
            breadth_first_search(gr,root=args.gene,filter=radius(args.radius))
        gst = digraph()
        gst.add_spanning_tree(x)
        dot = write(gst)
        out.write(dot)
        st, sd = shortest_path(gst, args.gene)
        
        if args.var_mode:
            for sample in sam.iterkeys():
                var = sam[str(sample)]
                #for each level return interacting genes if they are 
                # variants in the sample. 
                # 0th order would be returned if the user chosen 
                # gene is a variant in the sample        
                for x in range(0, (args.radius+1)):
                    for each in var:
                        for key, value in sd.iteritems():
                            if value == x and key == each[0]:
                                print "\t".join([str(sample),str(args.gene), \
                                          str(x), \
                                          str(key), \
                                          str(each[1]), \
                                          str(each[2]), \
                                          str(each[3])])        
        elif (not args.var_mode):
            for sample in sam.iterkeys():
                for each in sam[str(sample)]:
                    variants.append(each[0])
                for x in range(0, (args.radius+1)):
                    for key, value in sd.iteritems():
                        if value == x and key in set(variants):
                            k.append(key)
                    if k:
                        print "\t".join([str(sample), str(args.gene), \
                                 str(x)+"_order:", 
                                 ",".join(k)])
                    else:
                        print "\t".join([str(sample), str(args.gene), str(x)+"_order:", "none"])
                    #initialize keys for next iteration
                    k = []

 def searchNodes(self, root):
     st, order = breadth_first_search(self._gr, root=root)
     gst = digraph()
     #gst.add_spanning_tree(st)
     #dot = write(gst)
     #with open("odata/grf.dot", 'w') as f:
     #    f.write(dot)
     #call(["dot", "odata/grf.dot", "-Tjpg", "-o", "odata/grf.jpg"])
     return order

 def testGraphBFS(self):
     G = pygraph.graph()
     G.add_nodes([1, 2, 3, 4, 5])
     G.add_edge(1, 2)
     G.add_edge(2, 3)
     G.add_edge(2, 4)
     G.add_edge(4, 5)
     G.add_edge(1, 5)
     G.add_edge(3, 5)
     st, lo = breadth_first_search(G, 1, filter=filters.find(5))
     assert st == {1: None, 2: 1, 5: 1}

 def testDigraph(self):
     G = pygraph.digraph()
     G.add_nodes([1, 2, 3, 4, 5])
     G.add_edge(1, 2)
     G.add_edge(2, 3)
     G.add_edge(2, 4)
     G.add_edge(4, 5)
     G.add_edge(1, 5)
     G.add_edge(3, 5)
     st, lo = breadth_first_search(G)
     assert st == {1: None, 2: 1, 3: 2, 4: 2, 5: 1}
     assert lo == [1, 2, 5, 3, 4]

def bfs_sub_graph(g, root, radius):
    from pygraph.algorithms.filters.radius import radius as Radius
    from pygraph.algorithms.searching import breadth_first_search
    gr = graph_pygraph(g)
    filt_radius = Radius(radius)
    _, o = breadth_first_search(gr, root, filt_radius)
    to_keep = sorted(o)
    new_indexes = np.zeros(len(g))
    new_indexes[to_keep] = range(len(to_keep))
    subg = g[to_keep]
    for nl in subg:
        for i in xrange(len(nl)):
            nl[i] = new_indexes[nl[i]]
    return subg, to_keep

 def level_up_down(graph):
     """
     Yield the nodes of the graph, for an arbitrary root, starting with the
     leaves, running up to the root node, and pushing back down toward the
     leaves, excepting the leaves themselves.
     
     Undefined behavior if the graph is not a tree.
     """
     arbitrary_root = next(NodeScheduler.uniform(graph))
     (_, ordering) = breadth_first_search(graph, root = arbitrary_root)
     for node in reversed(ordering):
         yield node
     for node in ordering[1 :]:
         if graph.node_order(node) > 1:
             yield node

    def get_word_st(self, word):
        """Create a Spanning Tree for a word passed as and arg.

        :Parameters:
            - `word`: (str) A word to build a spanning tree for.
        :Returns:
            - `word_st` (obj) A Directed Graph instance.
        :Raises:
            - None.
        """
        s_tree, order = breadth_first_search(self._graph,
                                             root=word.encode('utf-8'))
        word_st = digraph()
        word_st.add_spanning_tree(s_tree)

        return word_st

def GetPaths(gr, start, ends):
	"""produce shortest paths from 'start' to 'ends' on gr
	an empty list represents that there is no path from `start' to an `end'

	:param gr: undirected graph
	:type gr: pygraph.classes.graph
	:param start: node identifier of 'start' node
	:type start: string
	:param ends: a list of node identifiers
	:type ends: list of strings
	:returns: a list of paths
	:rtype: list"""

	paths = list()
	st, order = breadth_first_search(gr, root=start)
	for end in ends:
		paths.append(TracePath(st, end))
	
	return paths

gr.add_edge("Austria","Germany")
gr.add_edge("Austria","Italy")
gr.add_edge("Austria","Czech Republic")
gr.add_edge("Austria","Slovakia")
gr.add_edge("Austria","Hungary")
gr.add_edge("Denmark","Germany")
gr.add_edge("Poland","Czech Republic")
gr.add_edge("Poland","Slovakia")
gr.add_edge("Poland","Germany")
gr.add_edge("Czech Republic","Slovakia")
gr.add_edge("Czech Republic","Germany")
gr.add_edge("Slovakia","Hungary")

# Draw as PNG
dot = gr.write(fmt='dot')
gvv = gv.readstring(dot)
gv.layout(gvv,'dot')
gv.render(gvv,'png','europe.png')

# Then, draw the breadth first search spanning tree rooted in Switzerland
st, order = breadth_first_search(gr, root="Switzerland")
gst = pygraph.digraph()
gst.add_spanning_tree(st)

dot = gst.write(fmt='dot')
gvv = gv.readstring(dot)

gv.layout(gvv,'dot')
gv.render(gvv,'png','europe-st.png')