#!/usr/bin/python3
# ====================================================================
# generate a random graph for testing the shortest path code
#
# due to the random nature of the compact cost data, it is possible
# for bugs to be introduced into in the graph. only extensive
# test will tell. (for example every node should have an inbound
# and an outbound connection.)
#
# see function fix_zero (fix zero inbound connections error)
# ====================================================================

import json
from random import randint, choice

CMINMAX = (10,100)         # minimum/maximum connection cost
VMAX    = 12               # maximum number of vertices
ECON    = (1,4)            # range of edge (outbound) connections
                           # per vertex (minimum,maximum)

jfile   = 'compact_cost_data.json'


class Vertex:

    def __init__(self,idx,cons,name=None):
        self.idx  = idx                 # list index
        self.cons = cons                # outbound connections
        self.name = name                # name


# --------------------------------------------------------------------
# ---- title string
# --------------------------------------------------------------------

def title_str(title,length=70):
    if not title:
        t = '-' * length
    elif len(title) > length:
        t = title[:length]
    else:
        t = title + '-' * (length - len(title))
    return t


# --------------------------------------------------------------------
# ---- display vertex's (outbound) connections (node,cost)
# --------------------------------------------------------------------

def display_vertex_outbound_connections(v):
    print(f'cons: {v.cons}')


# --------------------------------------------------------------------
# ---- display vertex
# --------------------------------------------------------------------

def display_vertex(v):
    print(title_str(f'---- vertex {v.idx} ',20))
    print(f'idx : {v.idx}')
    display_vertex_outbound_connections(v)


# --------------------------------------------------------------------
# ---- display graph
# --------------------------------------------------------------------

def display_graph(g):
    for v in g:
        display_vertex(v)
        

# -------------------------------------------------------------------
# ---- create a randomly connected graph
# -------------------------------------------------------------------

def create_random_graph(vmax,econ,cminmax):

    # ---- create a list of the vertices (indexes) in the graph

    vlst = [i for i in range(vmax)]
    
    # ---- create a graph
    
    graph = []

    # ---- for every source node (vertex) in the graph create
    # ---- outbound connection list
        
    for sidx in range(vmax):

        # ---- remove source idx from the list of vertices leaving
        # ---- a list of potential nodes (vertices) to connect to
    
        vvlst = vlst.copy()
        vvlst.remove(sidx)
                                   
        # ---- generate a random list of outbound connections

        cons = []
        
        for _ in range(randint(econ[0],econ[1])):
            cidx  = choice(vvlst)
            ccost = randint(cminmax[0],cminmax[1])
            cons.append((cidx,ccost))
            vvlst.remove(cidx)
            
        graph.append(Vertex(sidx,cons))

    return graph


# --------------------------------------------------------------------
# ---- display outbound connections
# --------------------------------------------------------------------

def display_outbound_connections(outbound,max=45):
    print(title_str('---- outbound connections ',max))
    for idx,rcn in enumerate(outbound):
        print(f'{idx:<2} {str(rcn[1]):40} {rcn[2]}')
    print(title_str('',max))


# --------------------------------------------------------------------
# ---- output JSON file
# --------------------------------------------------------------------

def output_json_file(jdata,outfile):
    with open(outfile,'w') as ofile:
        ofile.write(json.dumps(jdata))


# --------------------------------------------------------------------
# ---- verify the number of inbound and outbound connections
# --------------------------------------------------------------------

def verify_connection_counts(costs):

    siz = len(costs)           # number of rows (nodes)
    
    inbound_count  = [0 for _ in range(siz)]
    outbound_count = [0 for _ in range(siz)]
    
    for i,r in enumerate(costs):
        outbound_count[i] = len(r[1])
        for c in r[1]:
            inbound_count[c[0]] += 1

    print()
    print(' row  outbound  inbound')
    for i in range(siz):
        print(f'[{i:2}]   {outbound_count[i]:4}     {inbound_count[i]:4}')

    # ---- test for zero counts

    for c in inbound_count:
        if c < 1:
            return False
    for c in outbound_count:
        if c < 1:
            return False
    
    return True


# --------------------------------------------------------------------
# ---- fix zero inbound connections error
# ---- 
# ---- because the compact cost data consists of outbound connections
# ---- generated randomly, some nodes may not have an inbound
# ---- connection. this function adds an inbound connection. the
# ---- inbound connection is a mirror of the node's first outbound
# ---- connection in the compact cost data.
# ----
# ---- note: because of the way outbound connections are generated,
# ----       every node has at least one outbound connection
# --------------------------------------------------------------------

def fix_zero(costs):

    siz = len(costs)
    
    inbound_count = [0 for _ in range(siz)]
    
    for i,r in enumerate(costs):
        for c in r[1]:
            inbound_count[c[0]] += 1

    # ---- check each connection count (row (node) and count)

    for r,c in enumerate(inbound_count):

        if c < 1:

            print(f'row {r} has zero inbound connections')
            
            # ---- outbound connections of row r

            cons = costs[r][1]

            # ---- first outbound connection

            con = cons[0]        # first outbound connection
            
            print(f'first outbound connection row={r} cost={con}')

            # ---- create mirror connection

            print(f'adding mirror row={con[0]} cost=({r},{con[1]})')
            
            costs[con[0]][1].append((r,con[1]))

    return

# --------------------------------------------------------------------
# ---- main
# --------------------------------------------------------------------

if __name__ == '__main__':

    # ---- create and initialize a graph (list of vertices)

    graph = create_random_graph(VMAX,ECON,CMINMAX)

    # ---- create compact cost data

    costs = []
    for v in graph:
        costs.append([v.idx,v.cons,v.name])

    print()
    display_outbound_connections(costs,60)
    
    # ---- verify connection counts

    print()
    print('verify connection count')
    
    tf = verify_connection_counts(costs)

    if not tf:
        print()
        print('error: found node(s) with zero inbound connections')

        print()
        print('Fixing node(s) with zero inbound connections')

        fix_zero(costs)

        print()
        print(title_str('---- fixed node(s) with no inbound connections',60))
        display_outbound_connections(costs,60)

    else:
        print()
        print('no nodes with zero inbound connections found')

    # ---- output compact cost data to a json file

    output_json_file(costs,jfile)

    print()
    print(f'created JSON file {jfile}')
    print()