"""
greedy_algorithm.py
transits a graph tree using a greedy algorithm
"""

# Define a demonstration graph tree in list format.
# The list is formatted to show node relationships.
# The format of each node is:
#     [node number, node value, connected node a, connected node b]
graph = \
                            [[0, 22, 1, 2],

            [1, 23, 3, 4],                     [2, 26, 5, 6],

  [3, 22, 7, 8],  [4, 28, 9, 10],     [5, 29, 11, 12],  [6, 23, 13, 14],

[7, 26, 0, 0],
  [8, 29, 0, 0],

            [9, 27, 0, 0],
                    [10, 28, 0, 0],

                                    [11, 22, 0, 0],
                                           [12, 29, 0, 0],

                                                   [13, 21, 0, 0],
                                                             [14, 29, 0, 0]]


# Define a recursive function to transit the graph.
def transit_graph(graph_to_transit,
                  current_node_number,
                  current_values_total,
                  node_transit_counter):

    # Test for error exit.
    node_transit_counter += 1
    if node_transit_counter > len(graph_to_transit):
        print("GRAPH TRANSIT LIMIT REACHED, CHECK GRAPH VALUES.")
        print("Node Transit counter: " + str(node_transit_counter))
        return

    # Define the indexes of values in a graph node.
    node_number_index = 0
    node_value_index = 1
    connected_node_a_index = 2
    connected_node_b_index = 3

    # Set initial values.
    connected_node_a_value = 0
    connected_node_b_value = 0
    next_node_number = 0

    # Get the current noe values.
    current_node = graph_to_transit[current_node_number]
    print("NODE PROCESSING")
    print(current_node)
    node_value = current_node[node_value_index]
    connected_node_a = current_node[connected_node_a_index]
    connected_node_b = current_node[connected_node_b_index]

    # Increment the current node values total.
    current_node_values_total = current_values_total + node_value

    # Test for the function exit criteria.
    if connected_node_a == 0 and connected_node_b == 0:
        print("GRAPH TRANSIT COMPLETED")
        print("Node Transit counter: " + str(node_transit_counter))
        print("Node Number: " + str(current_node_number))
        print("Current Value Total: " + str(current_node_values_total))
        print(" ")
        return

    # Get values from the connected nodes.
    if connected_node_a != 0:
        connected_node_a_list = graph_to_transit[connected_node_a]
        connected_node_a_value = connected_node_a_list[node_value_index]
    if connected_node_b != 0:
        connected_node_b_list = graph_to_transit[connected_node_b]
        connected_node_b_value = connected_node_b_list[node_value_index]

    # Determine the next node to transit using greedy logic.
    if connected_node_a_value != 0:
        if connected_node_a_value >= connected_node_b_value:
            next_node_number = connected_node_a
        else:
            next_node_number = connected_node_b

    # Print current node data.
    print("Node Number: " + str(current_node_number))
    print("Node Value: " + str(current_node_number))
    print("Node Values Total: " + str(current_node_values_total))
    print("Connected Node A: " + str(connected_node_a))
    print("Connected Node B: " + str(connected_node_b))
    print("Next Node Number: " + str(next_node_number))
    print("Maximum Node Transits: " + str(len(graph_to_transit)))
    print("Node Transit counter: " + str(node_transit_counter))
    print(" ")

    # Call the transit graph function using current values.
    transit_graph(graph_to_transit,
                  next_node_number,
                  current_node_values_total,
                  node_transit_counter)


# Transit the graph.
transit_graph(graph, 0, 0, 0)