def test_predecessor(self):
     G=nx.path_graph(4)
     assert_equal(nx.predecessor(G,0),{0: [], 1: [0], 2: [1], 3: [2]})
     assert_equal(nx.predecessor(G,0,3),[2])
     G=nx.grid_2d_graph(2,2)
     assert_equal(sorted(nx.predecessor(G,(0,0)).items()),
                  [((0, 0), []), ((0, 1), [(0, 0)]), 
                   ((1, 0), [(0, 0)]), ((1, 1), [(0, 1), (1, 0)])])

 def test_predecessor_target(self):
     G=nx.path_graph(4)
     p = nx.predecessor(G,0,3)
     assert_equal(p,[2])
     p = nx.predecessor(G,0,3,cutoff=2)
     assert_equal(p,[])
     p,s = nx.predecessor(G,0,3,return_seen=True)
     assert_equal(p,[2])
     assert_equal(s,3)
     p,s = nx.predecessor(G,0,3,cutoff=2,return_seen=True)
     assert_equal(p,[])
     assert_equal(s,-1)

def LCA(n1, n2, GR):
    #This funciton was written by Evan Rees. Thanks Evan!
    #will construct directed graph with edges of (parent,child) tuples and nodes for every parent and child
    #Reverses the nodes s.t. root is last so max will be lowest common ancestor to both nodes
    preds_1 = nx.predecessor(GR, n1) # NOTE: Assign n1 and n2 for preds_1 and preds_2
    preds_2 = nx.predecessor(GR, n2)
    common_preds = set([n for n in preds_1]).intersection(set([n for n in preds_2]))
    LCA = max(common_preds, key=lambda n: preds_1[n])
    if max(common_preds) == n1:
        return(n1)
    elif max(common_preds) == n2:
        return(n2)
    else:
        return LCA

 def test_predecessor_cycle(self):
     G = nx.cycle_graph(4)
     pred = nx.predecessor(G, 0)
     assert_equal(pred[0], [])
     assert_equal(pred[1], [0])
     assert_true(pred[2] in [[1, 3], [3, 1]])
     assert_equal(pred[3], [0])

def all_shortest_paths(G, a, b):
    """ Return a list of all shortest paths in graph G between nodes a 
and b """
    ret = []
    pred = nx.predecessor(G, b)
    if not pred.has_key(a):  # b is not reachable from a
        return []
    pth = [[a, 0]]
    pthlength = 1  # instead of array shortening and appending, which are relatively
    ind = 0  # slow operations, we will just overwrite array elements at position ind
    while ind >= 0:
        n, i = pth[ind]
        if n == b:
            ret.append(map(lambda x: x[0], pth[: ind + 1]))
        if len(pred[n]) > i:
            ind += 1
            if ind == pthlength:
                pth.append([pred[n][i], 0])
                pthlength += 1
            else:
                pth[ind] = [pred[n][i], 0]
        else:
            ind -= 1
            if ind >= 0:
                pth[ind][1] += 1
    return ret

def _edge_betweenness(G,source,nodes,cutoff=False):
    """
    Edge betweenness helper.
    """
    between={}
    # get the predecessor data
    #(pred,length)=_fast_predecessor(G,source,cutoff=cutoff) 
    (pred,length)=nx.predecessor(G,source,cutoff=cutoff,return_seen=True)
    # order the nodes by path length
    onodes = [ nn for dd,nn in sorted( (dist,n) for n,dist in length.items() )]
    # intialize betweenness, doesn't account for any edge weights
    for u,v in G.edges(nodes):
        between[(u,v)]=1.0
        between[(v,u)]=1.0

    while onodes:           # work through all paths
        v=onodes.pop()
        if v in pred:
            num_paths=len(pred[v])   # Discount betweenness if more than 
            for w in pred[v]:        # one shortest path.
                if w in pred:
                    num_paths=len(pred[w])  # Discount betweenness, mult path  
                    for x in pred[w]:
                        between[(w,x)]+=between[(v,w)]/num_paths
                        between[(x,w)]+=between[(w,v)]/num_paths
    return between

def LCA(n1, n2, taxlist):
    G = nx.DiGraph()
    G.add_edges_from(taxlist)
    #will construct directed graph with edges of (parent,child) tuples and nodes for every parent and child
    GR = G.reverse()
    #Reverses the nodes s.t. root is last so max will be lowest common ancestor to both nodes
    preds_1 = nx.predecessor(GR, n1) # NOTE: Assign n1 and n2 for preds_1 and preds_2
    preds_2 = nx.predecessor(GR, n2)
    common_preds = set([n for n in preds_1]).intersection(set([n for n in preds_2]))
    LCA = max(common_preds, key=lambda n: preds_1[n])
    if max(common_preds) == n1:
        print("LCA is : %d" % n1)
    elif max(common_preds) == n2:
        print("LCA is : %d" % n2)
    else:
        print("LCA is : %d" % LCA)

    def can_join(self, wot, idty):
        """
        Checks if an individual must join the wot as a member regarding the wot rules
        Protocol 0.2
        :param wot:     Graph to analyse
        :param idty:    Pubkey of the candidate
        :return: False or True
        """

        # Extract the list of all connected members to idty at steps_max via certificates (edges)
        linked = networkx.predecessor(wot.reverse(copy=True), idty, cutoff=self.steps_max)
        sentries = [m for m in self.members if len(wot.out_edges(m)) > self.ySentries(len(self.members))]
        # List all sentries connected at steps_max from idty
        linked_in_range = [l for l in linked if l in sentries
                           and l != idty]

        # Checks if idty is connected to at least xpercent of sentries
        enough_sentries = len(linked_in_range) >= len(sentries)*self.xpercent
        if not enough_sentries:
            print("{0} : Cannot join : not enough sentries ({1}/{2})".format(idty,
                                                                             len(linked_in_range),
                                                                             len(sentries)*self.xpercent))

        # Checks if idty has enough certificates to be a member
        enough_certs = len(wot.in_edges(idty)) >= self.sig_qty
        if not enough_certs:
            print("{0} : Cannot join : not enough certifications ({1}/{2}".format(idty,
                                                                                  len(wot.in_edges(idty)),
                                                                                  self.sig_qty))

        return enough_certs and enough_sentries

def _edge_betweenness(G, source, nodes=None, cutoff=False):
    """
    Edge betweenness helper.
    """
    # get the predecessor data
    (pred, length) = nx.predecessor(G, source, cutoff=cutoff, return_seen=True)
    # order the nodes by path length
    onodes = [n for n, d in sorted(length.items(), key=itemgetter(1))]
    # intialize betweenness, doesn't account for any edge weights
    between = {}
    for u, v in G.edges(nodes):
        between[(u, v)] = 1.0
        between[(v, u)] = 1.0

    while onodes:           # work through all paths
        v = onodes.pop()
        if v in pred:
            # Discount betweenness if more than one shortest path.
            num_paths = len(pred[v])
            for w in pred[v]:
                if w in pred:
                    # Discount betweenness, mult path
                    num_paths = len(pred[w])
                    for x in pred[w]:
                        between[(w, x)] += between[(v, w)] / num_paths
                        between[(x, w)] += between[(w, v)] / num_paths
    return between

def dijkstra_all_shortest_paths(G, source, target, weight=None):
    ''' This function is the networkX's implementation of the "all-shortest-paths-problem" algorithm
        and is used as ground truth for our implementation. It uses a modified version of the 
        dijkstra algorithm that compute  the shortest path length and predecessors 
        on shortest paths.'''
        
    if weight is not None:
        pred,dist = nx.dijkstra_predecessor_and_distance(G,source,weight=weight)
    else:
        pred = nx.predecessor(G,source)
    if target not in pred:
        raise nx.NetworkXNoPath()
    stack = [[target,0]]
    top = 0
    while top >= 0:
        node,i = stack[top]
        if node == source:
            yield [p for p,n in reversed(stack[:top+1])]
        if len(pred[node]) > i:
            top += 1
            if top == len(stack):
                stack.append([pred[node][i],0])
            else:
                stack[top] = [pred[node][i],0]
        else:
            stack[top-1][1] += 1
            top -= 1

def _node_betweenness(G, source, cutoff=False, normalized=True, weight=None):
    """Node betweenness_centrality helper:

    See betweenness_centrality for what you probably want.
    This actually computes "load" and not betweenness.
    See https://networkx.lanl.gov/ticket/103

    This calculates the load of each node for paths from a single source.
    (The fraction of number of shortests paths from source that go
    through each node.)

    To get the load for a node you need to do all-pairs shortest paths.

    If weight is not None then use Dijkstra for finding shortest paths.
    """

    # get the predecessor and path length data
    if weight is None:
        (pred, length) = nx.predecessor(G, source, cutoff=cutoff,
                                        return_seen=True)
    else:
        (pred, length) = nx.dijkstra_predecessor_and_distance(G, source,
                                                              cutoff, weight)

    # order the nodes by path length
    onodes = [(l, vert) for (vert, l) in length.items()]
    onodes.sort()
    onodes[:] = [vert for (l, vert) in onodes if l > 0]

    # intialize betweenness
    between = {}.fromkeys(length, 1.0)

    while onodes:
        v = onodes.pop()
        if v in pred:
            num_paths = len(pred[v])  # Discount betweenness if more than
            for x in pred[v]:         # one shortest path.
                if x == source:  # stop if hit source because all remaining v
                    break        # also have pred[v]==[source]
                between[x] += between[v] / float(num_paths)
    #  remove source
    for v in between:
        between[v] -= 1
    # rescale to be between 0 and 1
    if normalized:
        l = len(between)
        if l > 2:
            # scale by 1/the number of possible paths
            scale = 1.0 / float((l - 1) * (l - 2))
            for v in between:
                between[v] *= scale
    return between

def init():
	mesh = MonotoneSystem()
	mesh.rectangular_mesh((0,0),(1,1),(10,10))
	a = 0.1
	inputs = [np.array([0,0]),np.array([0,a]),np.array([a,0]),np.array([-a,0]),np.array([0,-a])]
	fts = mesh.compute_FTS(inputs)



	init_elem = list(mesh.collision(np.array([0,0]),np.array([0.2,0.2])))
	avoid_elem = list(mesh.collision(np.array([0.4,0.4]),np.array([0.6,0.6])))
	final_elem = list(mesh.collision(np.array([0.8,0.8]),np.array([1.0,1.0])))

	init = random.choice(init_elem)
	fts.graph['initial'] = set([init])
	final = random.choice(final_elem)

	predecessor = nx.predecessor(fts,final)
	paths = [[k]+v for k,v in predecessor.items()]
	used_edges = list(flatten([ zip(p[1:],p[0:-1]) for p in paths if len(p)>1 ]))
	used_edges = list(flatten([ zip(p[0:-1],p[1:]) for p in paths if len(p)>1 ]))
	used_edges.append((final,final))
	fts.remove_edges_from(set(fts.edges()).difference(set(used_edges)))
	fts[final][final]['control'] = np.array([0,0])
	fts[final][final]['label'] = str(np.array([0,0]))

	#fts.show("lkjlkj")

	env = MonotoneEnvironment(mesh)

	for i,elem in enumerate(mesh.elements):
		if elem in init_elem:
			env.regions[i] = "i"
		if elem in avoid_elem:
			env.regions[i] = "c"
		if elem in final_elem:
			env.regions[i] = "f"

	print env.regions
	q1 = Quad("q1","i",env)
	planner = MonotonePlanner(q1,mesh,fts)


	sim = Simulator()

	sim.add("q1",q1)
	sim.add("q1_planner",planner)
	
	return sim,env

def optimal_point_option( g, gr, dest, max_length ):
    """Create an option that takes all connected states to dest"""
    paths = nx.predecessor(gr, source=dest, cutoff = max_length)

    I = set( paths.keys() )
    I.remove( dest )
    pi = {}
    for src, succ in paths.items():
        if src == dest: continue
        # Next link in the path
        succ = succ[ 0 ]

        # Choose the maximum probability action for this edge
        actions = [ (attrs['action'], attrs['pr']) for src, succ_, attrs in g.edges( src, data=True ) if succ_ == succ ] 
        action = max( actions, key = lambda (a,pr): pr )[ 0 ]

        pi[ src ] = ((action, 1.0),)
    B = { dest : 1.0 }
    
    return Option( I, pi, B )

def all_shortest_paths(G, source, target, weight=None):
    if weight is not None:
        pred,dist = nx.dijkstra_predecessor_and_distance(G,source,weight=weight)
    else:
        pred = nx.predecessor(G,source)
    if target not in pred:
        raise nx.NetworkXNoPath()
    stack = [[target,0]]
    top = 0
    while top >= 0:
        node,i = stack[top]
        if node == source:
            yield [p for p,n in reversed(stack[:top+1])]
        if len(pred[node]) > i:
            top += 1
            if top == len(stack):
                stack.append([pred[node][i],0])
            else:
                stack[top] = [pred[node][i],0]
        else:
            stack[top-1][1] += 1
            top -= 1

def Copy_all_shortest_paths_avoidnode(G, source, target, weight=None,avoid_node=None):
    if weight is not None:
        pred,dist = copy_dijkstra_predecessor_and_distance(G,source,weight=weight,avoid_node=avoid_node)
    else:
        pred = nx.predecessor(G,source)
    if target not in pred:
        raise Exception("No Path found with Given Bandwidth Constraint")
    stack = [[target,0]]
    top = 0
    while top >= 0:
        node,i = stack[top]
        if node == source:
            yield [p for p,n in reversed(stack[:top+1])]
        if len(pred[node]) > i:
            top += 1
            if top == len(stack):
                stack.append([pred[node][i],0])
            else:
                stack[top] = [pred[node][i],0]
        else:
            stack[top-1][1] += 1
            top -= 1

def all_shortest_paths(G, source, target, weight=None):
    """Compute all shortest paths in the graph.

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

    source : node
       Starting node for path.

    target : node
       Ending node for path.

    weight : None or string, optional (default = None)
       If None, every edge has weight/distance/cost 1.
       If a string, use this edge attribute as the edge weight.
       Any edge attribute not present defaults to 1.

    Returns
    -------
    paths: generator of lists
        A generator of all paths between source and target.

    Examples
    --------
    >>> G=nx.Graph()
    >>> G.add_path([0,1,2])
    >>> G.add_path([0,10,2])
    >>> print([p for p in nx.all_shortest_paths(G,source=0,target=2)])
    [[0, 1, 2], [0, 10, 2]]

    Notes
    -----
    There may be many shortest paths between the source and target.

    See Also
    --------
    shortest_path()
    single_source_shortest_path()
    all_pairs_shortest_path()
    """
    if weight is not None:
        pred,dist = nx.dijkstra_predecessor_and_distance(G,source,weight=weight)
    else:
        pred = nx.predecessor(G,source)
    if target not in pred:
        raise nx.NetworkXNoPath()
    stack = [[target,0]]
    top = 0
    while top >= 0:
        node,i = stack[top]
        if node == source:
          yield [p for p,n in reversed(stack[:top+1])]
        if len(pred[node]) > i:
            top += 1
            if top == len(stack):
                stack.append([pred[node][i],0])
            else:
                stack[top] = [pred[node][i],0]
        else:
            stack[top-1][1] += 1
            top -= 1

import networkx as nx

g = nx.read_edgelist('/home/dchen/git/vbi/sdal/mann2_simulations/src/simulations/lens_recurrent_attitudeDiffusion/edge_list_nx.gz')


nx.predecessor(g, )

 def dsubgraph_nodes(inp, out, nbunch):
     pred = NX.predecessor(G, inp, out)
     nbunch += pred
     for node in pred:
         dsubgraph_nodes(inp, node, nbunch)
     return nbunch

	def get_states_connected_to_accept(self):
		S = set([])
		for n in self.graph['accept']:
			pre = list(itertools.chain(*nx.predecessor(self,n).values()))
			S = S.union(set(pre))
		return S

# isolates
nx.is_isolate(G, 1)     # False
nx.is_isolate(G, 5)     # True

# HITS
nx.hits(G,max_iter=1000)  # cannot converge?

# maximal independent set
nx.maximal_independent_set(G)

# shortest path
nx.shortest_path(G)     # need "predecessors_iter"
nx.all_pairs_shortest_path(G)
nx.all_pairs_shortest_path_length(G)

nx.predecessor(G, 1)
nx.predecessor(G, 1, 378)

nx.dijkstra_path(G, 1, 300)
nx.dijkstra_path_length(G, 1, 300)
nx.single_source_dijkstra_path(G, 1)
nx.single_source_dijkstra_path_length(G, 1)
nx.all_pairs_dijkstra_path(G)
nx.all_pairs_dijkstra_path_length(G)

nx.bellman_ford(G, 1)

# Traversal
list(nx.dfs_edges(G))
list(nx.dfs_edges(G, 1))
nx.dfs_tree(G)  # return a networkx graph