# Path: xenoGI/DTLOR_DP.py
# def check_tip(vh, eh1, eh2):
#     if eh1 is None and eh2 is None:
#         return True
#     elif eh1 is not None and eh2 is not None:
#         return False
#     else:
#         assert False, "Species node with one child: {}".format(vh)
# 
# def preorder(tree, rootEdgeName = None):
#     """ Takes a tree as input (see format description above) and returns a 
#     list of the edges in that tree in preorder (high edges to low edges)"""
# 
#     if rootEdgeName is None:
#         rootEdgeName = next(iter(tree))
# 
#     value = tree[rootEdgeName]
#     _,_,leftChildEdgeName,rightChildEdgeName = value
# 
#     # base case
#     if leftChildEdgeName == None: # then rightChildEdgeName == None also
#         return [rootEdgeName]
#     else:
#         return [rootEdgeName] + \
#                 preorder(tree, leftChildEdgeName) + \
#                 preorder(tree, rightChildEdgeName)
# 
# def postorder(tree, rootEdgeName = None):
#     """ Takes a tree as input (see format description above) and returns a 
#     list of the edges in that tree in postorder (low edges to high edges)"""
# 
#     if rootEdgeName is None:
#         rootEdgeName = next(iter(tree))
# 
#     value = tree[rootEdgeName]
#     _,_,leftChildEdgeName,rightChildEdgeName = value
#     # base case
#     if leftChildEdgeName == None: # then rightChildEdgeName == None also
#         return [rootEdgeName]
#     else:
#         return postorder(tree, leftChildEdgeName) + \
#                postorder(tree, rightChildEdgeName) + \
#                [rootEdgeName]
# 
# def delta_r(synteny1, synteny2, R):
#     if synteny1 == synteny2:
#         return 0
#     else:
#         return R
# 
# def find_min_events(events_list):
#     """
#     Combines the events list into a single events list
#     Each element of events_list is a tuple of (cost, [events])
#     Which holds the DP entry for some part of the DP and the associated events
#     This combines them into the entry of lowest cost, combining
#     all events that have lowest cost
#     """
#     cost = Infinity
#     events = []
#     for c,e in events_list:
#         if cost > c:
#             cost = c
#             events = []
#         if cost == c:
#             events.extend(e)
#     return (cost, events)


from collections import defaultdict
from enum import Enum, auto
from itertools import product
from functools import reduce
from .DTLOR_DP import check_tip, preorder, postorder, delta_r, find_min_events
import random
            cost = left_cost + right_cost
            Null[eg] = cost
            G[(NodeType.LOCATION_MAPPING, eg, "*")] = a_nodes
    # Compute the final choice node and cost: does the root get a location or "*"?
    root_null = (Null[gene_root], [(NodeType.LOCATION_MAPPING, gene_root, "*")])
    root_origin = Origin[gene_root]
    root_cost, root_events = find_min_events([root_null, root_origin])
    G[(NodeType.ROOT,)] = root_events
    # Remove the non-optimal parts of G
    G = prune_graph(G)
    return root_cost, G

def DTL_reconcile(species_tree, gene_tree, phi, D, T, L):
    A = {}
    # node -> cost
    C = {}
    # node -> [node]
    C_graph = {}
    O = {}
    # Holds the optimal species nodes to map a given gene node
    # gene_node -> (cost, [species_node])
    C_star = {}
    best_switch = {}
    species_root = next(iter(species_tree))
    for eg in postorder(gene_tree):
        C_star[eg] = (Infinity, [])
        _, vp, eg1, eg2 = gene_tree[eg]
        vp_is_a_tip = check_tip(vp, eg1, eg2)
        for es in postorder(species_tree):
            _, vh, es1, es2 = species_tree[es]

# Path: xenoGI/DTLOR_DP.py
# def check_tip(vh, eh1, eh2):
#     if eh1 is None and eh2 is None:
#         return True
#     elif eh1 is not None and eh2 is not None:
#         return False
#     else:
#         assert False, "Species node with one child: {}".format(vh)
# 
# def preorder(tree, rootEdgeName = None):
#     """ Takes a tree as input (see format description above) and returns a 
#     list of the edges in that tree in preorder (high edges to low edges)"""
# 
#     if rootEdgeName is None:
#         rootEdgeName = next(iter(tree))
# 
#     value = tree[rootEdgeName]
#     _,_,leftChildEdgeName,rightChildEdgeName = value
# 
#     # base case
#     if leftChildEdgeName == None: # then rightChildEdgeName == None also
#         return [rootEdgeName]
#     else:
#         return [rootEdgeName] + \
#                 preorder(tree, leftChildEdgeName) + \
#                 preorder(tree, rightChildEdgeName)
# 
# def postorder(tree, rootEdgeName = None):
#     """ Takes a tree as input (see format description above) and returns a 
#     list of the edges in that tree in postorder (low edges to high edges)"""
# 
#     if rootEdgeName is None:
#         rootEdgeName = next(iter(tree))
# 
#     value = tree[rootEdgeName]
#     _,_,leftChildEdgeName,rightChildEdgeName = value
#     # base case
#     if leftChildEdgeName == None: # then rightChildEdgeName == None also
#         return [rootEdgeName]
#     else:
#         return postorder(tree, leftChildEdgeName) + \
#                postorder(tree, rightChildEdgeName) + \
#                [rootEdgeName]
# 
# def delta_r(synteny1, synteny2, R):
#     if synteny1 == synteny2:
#         return 0
#     else:
#         return R
# 
# def find_min_events(events_list):
#     """
#     Combines the events list into a single events list
#     Each element of events_list is a tuple of (cost, [events])
#     Which holds the DP entry for some part of the DP and the associated events
#     This combines them into the entry of lowest cost, combining
#     all events that have lowest cost
#     """
#     cost = Infinity
#     events = []
#     for c,e in events_list:
#         if cost > c:
#             cost = c
#             events = []
#         if cost == c:
#             events.extend(e)
#     return (cost, events)


# Path: xenoGI/new_DTLOR_DP.py
from collections import defaultdict
from enum import Enum, auto
from itertools import product
from functools import reduce
from .DTLOR_DP import check_tip, preorder, postorder, delta_r, find_min_events
import random

            cost = left_cost + right_cost
            Null[eg] = cost
            G[(NodeType.LOCATION_MAPPING, eg, "*")] = a_nodes
    # Compute the final choice node and cost: does the root get a location or "*"?
    root_null = (Null[gene_root], [(NodeType.LOCATION_MAPPING, gene_root, "*")])
    root_origin = Origin[gene_root]
    root_cost, root_events = find_min_events([root_null, root_origin])
    G[(NodeType.ROOT,)] = root_events
    # Remove the non-optimal parts of G
    G = prune_graph(G)
    return root_cost, G

def DTL_reconcile(species_tree, gene_tree, phi, D, T, L):
    A = {}
    # node -> cost
    C = {}
    # node -> [node]
    C_graph = {}
    O = {}
    # Holds the optimal species nodes to map a given gene node
    # gene_node -> (cost, [species_node])
    C_star = {}
    best_switch = {}
    species_root = next(iter(species_tree))
    for eg in postorder(gene_tree):
        C_star[eg] = (Infinity, [])
        _, vp, eg1, eg2 = gene_tree[eg]
        vp_is_a_tip = check_tip(vp, eg1, eg2)
        for es in postorder(species_tree):
            _, vh, es1, es2 = species_tree[es]

            vh_is_a_tip = check_tip(vh, es1, es2)