import parameters as params
import networkx as nx
import osmnx as ox

def check_directed_eulerian(G):
    """
    Check si le graph ORIENTÉ donné est Eulérien [en O(V)] et si ce dernier l'est
    renvoie les sommets qui ont un degré impair (si il en existe). Sinon renvoie none.
    None = non eulérien
    (None, None) = eulérien mais pas de sommets de degrée impair
    (V1, V2) = eulérien et possède 2 sommets de degrée impaires
    Parameters:
        G: Graph à tester
    """
    V = list(G.nodes)
    odd_start = None
    odd_end = None
    for node in V:
        # This is the implementation used when you want to play with a directed graph
        # Sadly NetworkX cannor eulerize directed graph
        # Eulerzing a directed graph is... NP-Hard
        if (G.in_degree(node) + 1 == G.out_degree(node)):
            # We have one more edge exitting than entering
            # This is the potential start of an eulerian path
            if (odd_start != None):
                # We already found a node that could make a staring point ?
                # We have too much odd degree vertices in this graph
                return None
            odd_start = node
        elif (G.in_degree(node) == G.out_degree(node) + 1):
            # We have one more edge entering than exitting
            # This is the potential end of an eulerian path
            if (odd_end != None):
                # We already found a node that could make an ending point ?
                # We have too much odd degree vertices in this graph
                return None
            odd_end = node
        elif (G.in_degree(node) != G.out_degree(node)):
            # Something's wrong, this is not at all an eulerian graph
            return None

    # There is no clean XOR in python...
    # Sad...
    if (bool(odd_start) != bool(odd_end)):
        # We only have one vertice with and odd degree
        return None
    return (odd_start, odd_end)

def check_non_directed_eulerian(G):
    """
    Check si le graph NON ORIENTÉ donné est Eulérien [en O(V)] et si ce dernier l'est
    renvoie les sommets qui ont un degré impair (si il en existe). Sinon renvoie none.
    None = non eulérien
    (None, None) = eulérien mais pas de sommets de degrée impair
    (V1, V2) = eulérien et possède 2 sommets de degrée impaires
    Parameters:
        G: Graph à tester
    """
    V = list(G.nodes)
    odd_start = None
    odd_end = None

    for node in V:
            if (G.degree(node) % 2 == 1):
                if (odd_start == None):
                    odd_start = node
                elif (odd_end == None):
                    odd_end = node
                else:
                    return None

    # There is no clean XOR in python...
    # Sad...
    if (bool(odd_start) != bool(odd_end)):
        # We only have one vertice with and odd degree
        return None
    return (odd_start, odd_end)