import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
#import igraph
import collections
import copy
import os
import sys
from igraph import *
from collections import defaultdict
import pyfiglet
#from difflib import SequenceMatcher
#import sqlite3 as Sql
import multiprocessing
#from lattpy import Lattice
from itertools import combinations
import random
import glob
import time
from icecream import ic
#import matplotlib.animation as animation
#========================================================================================================
# General use functions
#========================================================================================================

#----------------------------------------------
# 1. Import information for database functions
#----------------------------------------------

def create_sheet(systemdf, input_string,key):
    """
    Separate full database into input, output and other data
    """
    df = pd.DataFrame(systemdf.columns)
    vallist = pd.DataFrame(df).apply(lambda row: row.astype(str).str.contains(f'{input_string}').any(), axis=1)
    columnlist = [key] # save all system names to check
    columnlist += list(df[vallist][0]) # add columns with name "input_string*" for sheet
    df2 = systemdf[columnlist].copy()
    df2 = df2.set_index(key).T.reset_index(drop=True) # transpose data for further use
    return df2

def search_automation_sheets(mygraph,path):
    """
    Figure out the automation files that need to be imported and import them into dataframes
    """
    systems=mygraph.vs["name"]
    files=os.listdir(path)
    files_to_import=[i for i in files for key in systems if i.startswith(key)]
    files_to_import=list(set(files_to_import))
    automation_sheets=[]
    ainput=pd.DataFrame()
    aoutput=pd.DataFrame()
    a_util=pd.DataFrame()
    a_group=pd.DataFrame()
    for file in files_to_import:
        automation_sheets.append(pd.read_excel(path+file).replace(np.nan,'None'))       
    for sheet in automation_sheets:
        ainput=pd.concat([ainput, create_sheet(sheet, "Input","Automation_Component")], axis=1).replace(np.nan,'None') 
        aoutput=pd.concat([aoutput, create_sheet(sheet, "Output","Automation_Component")], axis=1).replace(np.nan,'None') 
        a_util=pd.concat([a_util, create_sheet(sheet, "Distribution","Automation_Component")], axis=1).replace(np.nan,'None') 
        a_group=pd.concat([a_group, create_sheet(sheet, "Group","Automation_Component")], axis=1).replace(np.nan,'None') 
    return automation_sheets,ainput,aoutput,a_util,a_group

#----------------------------------------------
# 2. Various search functions
#----------------------------------------------
def search_dict_keykey(dictionary, searchstring):
    return [key for key, val in dictionary.items() if searchstring in key]

def search_dict_keyval(dictionary, searchstring):
    return [key for key, val in dictionary.items() if searchstring in val]

def search_dict_valval(dictionary, searchstring):
    return [val for key, val in dictionary.items() if searchstring in val]

def search_string(dataframe, input_string):
    return dataframe.apply(lambda row: row.astype(str).str.contains(f'{input_string}').any(), axis=0)

def unused_list(system, unused, system_data, i=0):
    l1 = list(system_data[f'{system}'][:])
    for name in l1:
        if name == "None":
            break
        elif name in unused[f'{system}']:
            break
        else:
            if i > 0:
                unused[f'{system}_{i}'].append(f'{name}') 
            else:
                unused[f'{system}'].append(f'{name}')
    return unused

def start_dict():
    """
    Function to shape dictionary with multiple.
    """
    
    in_out_dict = defaultdict(list)
    
    used_inputs = defaultdict(list) # empty lists
    unused_inputs = defaultdict(list)
    used_outputs = defaultdict(list)
    unused_outputs = defaultdict(list)
    edgelist = []
    mediumlist = []
    
    in_out_dict = {'edgelist' : edgelist, 'mediumlist' : mediumlist, 'used_inputs' : used_inputs, 
               'used_outputs' : used_outputs, 'unused_inputs': unused_inputs, 'unused_outputs' : unused_outputs}
    
    return in_out_dict

#---------------------------------------------------
# 3. Functions used for connections,input and output
#---------------------------------------------------
def connect_insides(system, edgelist, mediumlist, used_inputs, unused_inputs, used_outputs, unused_outputs):
    """
    Function connects unused in&outputs from start system 
    to all inputs & outputs from a that are already within that graph.
    Aim is to avoid loops
    """
    # Isolate unused inputs from system to check against other unused outputs
    for inputs in unused_inputs[f'{system}']:
        if len(search_dict_keyval(unused_outputs, inputs)) > 0:
            print('loop in')
            next_system = search_dict_keyval(unused_outputs, inputs)[0]
            # change input
            used_inputs[f'{system}'].append(f'{inputs}')
            unused_inputs[f'{system}'].remove(f'{inputs}') 
            
            # change output
            used_outputs[f'{next_system}'].append(f'{inputs}')    
            unused_outputs[f'{next_system}'].remove(f'{inputs}')
            
            # change medium & edges
            edgelist.append((next_system, system)) # add step to edges
            mediumlist.append(inputs)
            
    # Isolate unused outputs from that system to check against other unused inputs
    for outputs in unused_outputs[f'{system}']:
        if len(search_dict_keyval(unused_inputs, outputs)) > 0:
            print('loop out')
            next_system = search_dict_keyval(unused_inputs, outputs)[0]
            
            # change input
            used_inputs[f'{next_system}'].append(f'{outputs}')
            unused_inputs[f'{next_system}'].remove(f'{outputs}') 
            
            # change output
            used_outputs[f'{system}'].append(outputs)    
            unused_outputs[f'{system}'].remove(f'{outputs}')
            
            # change medium & edges
            edgelist.append((system, next_system)) # add step to edges
            mediumlist.append(outputs)
            
    print('used_inputs',used_inputs)
    print('unused_inputs',unused_inputs)
    print('----------------')
    print('used_outputs',used_outputs)
    print('unused_outputs',unused_outputs)

    print('')
    print('done')
    print('edge')
    print(edgelist)
    print('medium')
    print(mediumlist)
    print(edgelist, mediumlist, used_inputs, unused_inputs, used_outputs, unused_outputs)
    return edgelist, mediumlist, used_inputs, unused_inputs, used_outputs, unused_outputs

def update_inout(insystem, outsystem, medium, system_list, in_out_dict,myinput,myoutput,mydistr):
    """
    Update function for in & output, assumption is that insystem is already found. 

    """
    
    # clean inputs
    used_inputs = defaultdict(list) # empty lists
    unused_inputs = defaultdict(list)
    used_outputs = defaultdict(list)
    unused_outputs = defaultdict(list)
    
    print(f'#    update_inout called with insystem: {insystem} and outsystem: {outsystem} for {medium} as medium')
    
    edgelist = []
    mediumlist = []
    
    if bool(in_out_dict) == True:
        used_inputs = in_out_dict['used_inputs']
        unused_inputs = in_out_dict['unused_inputs']
        used_outputs = in_out_dict['used_outputs']
        unused_outputs = in_out_dict['unused_outputs']

        edgelist = in_out_dict['edgelist']
        mediumlist = in_out_dict['mediumlist']

    try: # Check if connection already exists
        test = edgelist.index((f'{insystem}', f'{outsystem}'))
        indices = [index for (index,item) in enumerate(edgelist) if item == (f'{insystem}', f'{outsystem}') or item == (f'{outsystem}',f'{insystem}')]
        for i in indices:
            if mediumlist[i] == medium:
                print(f'{medium} connection from {outsystem} to {insystem} already exists, skipping ...')
                break
    except:
        try: # Check if other way already exists
            test = edgelist.index((f'{outsystem}',f'{insystem}'))
            indices = [index for (index,item) in enumerate(edgelist) if item == (f'{insystem}', f'{outsystem}') or item == (f'{outsystem}',f'{insystem}')]
            for i in indices:
                if mediumlist[i] == medium:
                    print(f'{medium} connection from {outsystem} to {insystem} already exists, skipping ...')
                    break
        except:
            sep = search_dict_keykey(used_outputs,f'{outsystem}')
            if len(sep) == 0: # if first time called, create unused outputs and edgelist
                """'target = '       Next node is called for the first time (could not be found)
                Add next node & its medium to used input or output
                Add unused list
                remove medium in unused 
                """
                print(f'First time calling {outsystem}, adding all unused values')
                # insystem
                if len(search_dict_keykey(used_inputs,f'{insystem}')) == 0:
                    used_inputs[f'{insystem}'].append(medium)
                    unused_inputs = unused_list(insystem, unused_inputs, myinput)
                    unused_inputs[f'{insystem}'].remove(f'{medium}') 
                    unused_outputs = unused_list(insystem, unused_outputs, myoutput)
                    
                else:
                    # if outsystem has already been called do not update all unused values
                    print(f'First time {outsystem}, but already called {insystem}')    
                    used_inputs[f'{insystem}'].append(medium)
                    unused_inputs[f'{insystem}'].remove(f'{medium}') 
                    
                # outsystem
                used_outputs[f'{outsystem}'].append(medium)    
                unused_outputs = unused_list(outsystem, unused_outputs, myoutput)
                unused_outputs[f'{outsystem}'].remove(f'{medium}')
                unused_inputs = unused_list(outsystem, unused_inputs, myinput)
                    
                # lists: 
                edgelist.append((outsystem, insystem)) # add step to edges
                mediumlist.append(medium) # name medium between edges
                system_list.append(outsystem) # add new system to todolist

            else:
                if collections.Counter(unused_outputs[f'{outsystem}'])[f'{medium}'] > 0: #check if output is unused
                    """
                    Next node is already called but medium of node is unused
                    Move unused to used input or output
                    """
                    # inputs
                    print('node called, medium unused')

                    if len(search_dict_keykey(used_inputs,f'{insystem}')) == 0:
                        # if insystem does not exist yet, add it
                        print(f'adding insystem {insystem} to unused inputs')

                        # insystem
                        used_inputs[f'{insystem}'].append(medium)
                        unused_inputs = unused_list(insystem, unused_inputs, myinput) 
                        unused_inputs[f'{insystem}'].remove(f'{medium}') 
                        unused_outputs = unused_list(insystem, unused_outputs, myoutput)

                        # outputs
                        used_outputs[f'{outsystem}'].append(medium)    
                        unused_outputs[f'{outsystem}'].remove(f'{medium}')

                        # lists: 
                        edgelist.append((outsystem, insystem)) # add step to edges
                        mediumlist.append(medium) # name medium between edges
                        # next system already in todolist

                    else: 
                        used_inputs[f'{insystem}'].append(medium)
                        unused_inputs[f'{insystem}'].remove(f'{medium}') 

                        # outputs
                        used_outputs[f'{outsystem}'].append(medium)    
                        unused_outputs[f'{outsystem}'].remove(f'{medium}')

                        # lists: 
                        edgelist.append((outsystem, insystem)) # add step to edges
                        mediumlist.append(medium) # name medium between edges
                        # next system already in todolist
                        print("Here")
                elif medium not in unused_inputs[f'{insystem}'] and len(search_dict_keykey(used_inputs,f'{insystem}')) > 0:
                    """medium is not available from existing input"""
                    print(f'skipping, {medium} is already used by {insystem}')

                
                else: # if used check if separated
                    if mydistr[f'{outsystem}'][0] == 'Separated': # if separated add new numbered system
                        """
                        Next node is already called and medium of node is not unused
                        next node system is separated, so need to create a new system number
                            add new node & medium to used input or output
                            add unused list
                            remove medium in unused
                        Original node has medium so does not need a new system
                        But assumed that 
                        """

                        # insystem
                        print('node called, medium used')
                        used_inputs[f'{insystem}'].append(medium)
                        unused_inputs[f'{insystem}'].remove(f'{medium}') 

                        # outsystem
                        used_outputs[f'{outsystem}_{len(sep)}'].append(medium)    
                        unused_outputs = unused_list(outsystem, unused_outputs, myoutput, i = len(sep))
                        unused_outputs[f'{outsystem}_{len(sep)}'].remove(f'{medium}')
                        unused_inputs = unused_list(outsystem, unused_inputs, myinput, i = len(sep))

                       # lists: 
                        edgelist.append((f'{outsystem}_{len(sep)}', insystem)) # add step to edges
                        mediumlist.append(medium) # name medium between edges
                        system_list.append(f'{outsystem}_{len(sep)}') # add new system to todolist

                    else:
                        """
                        out node is already called and medium of node is not unused
                        out node system is distributing, so: 
                            - add medium to used: medium will never become unused, so can remain
                        in node has medium so does not need a new system
                            remove from unused and add to used
                        """
                        # inputs
                        used_inputs[f'{insystem}'].append(medium)
                        unused_inputs[f'{insystem}'].remove(f'{medium}') 

                        # outputs
                        used_outputs[f'{outsystem}_{len(sep)}'].append(medium)

                        # lists: 
                        edgelist.append((outsystem, insystem)) # add step to edges
                        mediumlist.append(medium) # name medium between edges
                        # next system already in todolist

            # Already connect looping connections
            edgelist, mediumlist, used_inputs, unused_inputs, used_outputs, unused_outputs = connect_insides(insystem, edgelist, mediumlist, used_inputs, unused_inputs, used_outputs, unused_outputs)
    
    print("++++++++++++++")
    print('unused output')
    print(unused_outputs)
    print('')
    print('used output')
    print(used_outputs)
    print('')
    print('unused input')
    print(unused_inputs)
    print('')
    print('used input')
    print(used_inputs)
    print('')
    print('Connections')
    print(pd.DataFrame({'start, end': in_out_dict['edgelist'],'connection': in_out_dict['mediumlist']}))
    print("++++++++++++++")
    
    in_out_dict1 = {'edgelist' : edgelist, 'mediumlist' : mediumlist, 'used_inputs' : used_inputs, 
                   'used_outputs' : used_outputs, 'unused_inputs': unused_inputs, 'unused_outputs' : unused_outputs}
    return in_out_dict1, system_list
#----------------------------------------------
# 4. Functions used for graph making
#----------------------------------------------

def onesystem(myinput, myoutput, system, in_out_dict, external_graph, hold_test,mydistr,edgelist,mediumlist): 
    """
    Stable system input output check function with network copy
    """
    next_system_list = []
    prev_system_list = []
    hold_system_list = []
    hold = defaultdict(list)
    internal_graph = defaultdict(list)
    
    for inval, inname in enumerate(myinput[f'{system.split("_")[0]}'][:]): # Check what inputs the system has
            if inname == "None":
                break
            
            else:
                system_list = search_string(myoutput,f'{inname}') # Identify systems that supply the input
                if sum(system_list) == 0: # If no supply, ask for addition
                    print(f'Inputs Warning: Add {system} system to supply {inname} to database')
                    break
                
                elif sum(system_list) > 1 and (len(search_dict_keyval(in_out_dict['unused_inputs'], inname)) or 
                len(search_dict_keyval(in_out_dict['unused_outputs'], inname))): # im not sure about the and/or statement
                    # if multiple systems supply the input and the medium occurs in either 
                    systems = list(system_list[system_list].index[:])
                    
                    if any(ele in hold_test for ele in [(f'{system},{systems}'), (f'{systems},{system}')]) == True:
                        print('breaking input')

                        break
                    else:
                        for system_val, system_name in enumerate(systems):
                            hold['system'].append(system)
                            hold['next_system'].append(system_name)
                            hold['medium'].append(inname)
                            print(f'added: from {system}, {system_name}, {inname}')
                            # system, next_system, inname
                        hold_test.append((f'{system},{systems}'))
                
                else: 
                    next_system = system_list[system_list==True].index[0]
                    print('|',system, next_system, inname,'|')
                    if system == next_system: # Continue with next system after no input remains   
                        break
                    elif inname == 'None':
                        break
                    else: # create edgelist, mediumlist and used output dictionary 
                        in_out_dict, next_system_list  = update_inout(system, next_system, inname, next_system_list, in_out_dict,myinput,myoutput,mydistr) 

    
    for outval, outname in enumerate(myoutput[f'{system.split("_")[0]}'][:]): # Check what outputs the system has
            if outname == "None":
                break
            
            else:
                system_list = search_string(myinput,f'{outname}') # Identify systems that supply the output
                
                if sum(system_list) == 0: # If no sink, ask for addition
                    print(f'Outputs Warning: {system} has remaining outputs without system:{outname}, creating sink')
                    edgelist.append((system, f'{outname}_sink'))
                    mediumlist.append((f'{outname}_sink'))
                    break
                
                elif sum(system_list) > 1 and (len(search_dict_keyval(in_out_dict['unused_inputs'], outname)) or 
                len(search_dict_keyval(in_out_dict['unused_outputs'], outname))): # multiple systems use this output & is not used yet
                    systems = list(system_list[system_list].index[:])
                    if any(ele in hold_test for ele in [(f'{system},{systems}'), (f'{systems},{system}')]) == True:
                        print('breaking output')
                        print('')
                        break
                    else:
                        for system_val, system_name in enumerate(systems):
                            hold['system'].append(system_name)
                            hold['next_system'].append(system)
                            hold['medium'].append(outname)
                            print('added:', system_name, system, outname)
                        hold_test.append((f'{system},{systems}')) # reset hold list
                            
                else: # outputs can be coupled
                    prev_system = system_list[system_list==True].index[0]
                    print('|',prev_system, system, outname,'|')
                    if system == prev_system: # Continue with next system after no input remains   
                        break
                    elif outname == 'None':
                        break
                    else: # create edgelist, mediumlist and used output dictionary 
                        
                        in_out_dict, prev_system_list  = update_inout(prev_system, system, outname, prev_system_list, in_out_dict,myinput,myoutput,mydistr)
    
    print('-------------------------') 
    print('')
    if len(hold['system']) > 0:
        systems = hold['system']
        next_systems = hold['next_system']
        mediums = hold['medium']
        
        print(systems, next_systems, mediums)
        
        for vi, ni in enumerate(systems):
            system = ni
            next_system = next_systems[vi]
            medium = mediums[vi]
            print('#############')
            print(f'Copying network, starting with {system} to {next_system} connected by {medium}')
            print('#############')
            if system == next_system: # Continue with next system after no input remains   
                break
            elif medium == 'None':
                break
            else: # create edgelist, mediumlist and used output dictionary 
                in_out_dict3 = copy.deepcopy(in_out_dict)
                hold_system_list = []
                internal_graph, hold_system_list  = update_inout(system, next_system, medium, hold_system_list, in_out_dict3,myinput,myoutput,mydistr)                                                                                                                              
                external_graph[f'{system}_{next_system}_{medium}'] = internal_graph # save 
        in_out_dict = internal_graph # at the end keep going with last updatelist
        
        
    tot_system_list = pd.Series(next_system_list + prev_system_list + hold_system_list)
    return in_out_dict, tot_system_list, external_graph, hold_test

def runthrough(myinput, myoutput, mydistr, todolist, in_out_dict, external_graph, hold_test,edgelist,mediumlist,flag):
    """
    This code defines the `runthrough` function, which iterates through a list of tasks and performs operations on a database. It also includes several helper functions for automation system functions, graph plotting, and fault generation.

    Inputs:
    - myinput: The input data for the automation system.
    - myoutput: The output data for the automation system.
    - mydistr: The distribution data for the automation system.
    - todolist: A list of tasks to be performed.
    - in_out_dict: A dictionary containing input and output data.
    - external_graph: The external graph data.
    - hold_test: A variable used for testing.
    - edgelist: A list of edges in the graph.
    - mediumlist: A list of mediums used in the graph.
    - flag: A flag variable used for conditional operations.

    Outputs:
    - The updated `in_out_dict` variable.

    Example Usage:
    ```python
    myinput = ...
    myoutput = ...
    mydistr = ...
    todolist = ...
    in_out_dict = ...
    external_graph = ...
    hold_test = ...
    edgelist = ...
    mediumlist = ...
    flag = ...

    result = runthrough(myinput, myoutput, mydistr, todolist, in_out_dict, external_graph, hold_test, edgelist, mediumlist, flag)
    print(result)
    ```
    """
    edgelist = []
    mediumlist = [] 
    used_outputs = defaultdict(list)
    i=1
    while i <= len(todolist):
        print("#######################")
        print(i,todolist.loc[i-1])
        print("#######################")
        if ((flag=='a')):
            in_out_dict = prepare_database_for_automation(in_out_dict)
        in_out_dict, system_list, external_graph, hold_test = onesystem(myinput,myoutput, todolist.loc[i-1], in_out_dict, external_graph, hold_test,mydistr,edgelist,mediumlist)
    
        todolist = pd.concat([todolist,system_list],ignore_index=True)
        todolist.drop_duplicates(inplace=True)#,ignore_index=True)#.reset_index(drop=True)
        todolist = todolist.reset_index(drop=True)
        i +=1
        
    return in_out_dict

#========================================================================================================
#Automation system_functions
#========================================================================================================
def merge_used_unused(dict1,dict2):
    dict0=defaultdict(list)
    for d in (dict1, dict2): # you can list as many input dicts as you want here
        for key, value in d.items():
            dict0[key].append(value)
    for key, value in dict0.items():        
        dict0[key] = [item for sublist in dict0[key] for item in sublist]
    return dict0
def physical_connect(database,path):
    """
    This function modifies the database by rendering all I/O unused for the automation level
    Input: Database in dictionary format
    Output: Database ready for level 2
    """
    # Automation physical graph
    adatabase=database
    graph = Graph.TupleList(database['edgelist'],directed=True)
    sheets,ainput,aoutput,a_util,a_group=search_automation_sheets(graph,path)
    df_graph = graph.get_edge_dataframe()
    graph.layout = graph.layout(layout='auto')
    graph=graph.simplify(multiple=True,combine_edges="random")
    df_graph = graph.get_edge_dataframe()
    df_graph['medium'] = database['mediumlist']
    df_graph['start']=graph.vs(df_graph.source)["name"]
    df_graph['end']=graph.vs(df_graph.target)["name"]
    graph = Graph.TupleList(database['edgelist'],directed=True)
    cyber_mediums_interest=[]
    for jj in list(ainput):
        for name in graph.vs["name"]:# Add controllers
            if (((aoutput[jj].iloc[0] in adatabase["unused_inputs"][name])) and ("Controller" in jj)): 
                adatabase['mediumlist'].append(aoutput[jj].iloc[0])
                adatabase['edgelist'].append((jj,name))
                adatabase['used_outputs'][jj]=[aoutput[jj].iloc[0]]
                adatabase['unused_outputs'][jj]=[]
                adatabase['used_inputs'][jj]=[]
                adatabase['unused_inputs'][jj]=ainput[jj].to_list()
                try:
                    adatabase['used_inputs'][name].append(aoutput[jj].iloc[0])
                except:
                    adatabase['used_inputs'][name]=[aoutput[jj].iloc[0]]
                adatabase['unused_inputs'][name].remove(aoutput[jj].iloc[0])
                graph.add_vertex(name=jj)
                graph.add_edges([(jj,name)])
                break
    for jj in list(ainput): # Add hardware sensors
        for name in graph.vs["name"]:
            if ((ainput[jj].iloc[0] in adatabase["unused_outputs"][name]) or (ainput[jj].iloc[0] in adatabase["used_outputs"][name]) and ("virtual" not in jj) and ("reference" not in jj)): 
                adatabase['mediumlist'].append(ainput[jj].iloc[0])
                adatabase['edgelist'].append((name,jj))
                try:
                    adatabase['used_outputs'][name].append(ainput[jj].iloc[0])
                except:
                    adatabase['used_outputs'][name]=[ainput[jj].iloc[0]]
                try:
                    adatabase['unused_outputs'][name].remove(ainput[jj].iloc[0])
                except:
                    pass
                adatabase['used_inputs'][jj]=[ainput[jj].iloc[0]]
                adatabase['unused_inputs'][jj]=[]
                adatabase['used_outputs'][jj]=aoutput[jj].to_list()
                adatabase['unused_outputs'][jj]=[]
                if 'Controller' not in jj:
                    graph.add_vertex(name=jj)
                    cyber_mediums_interest.append((jj,ainput[jj].iloc[0]))
                graph.add_edges([(name,jj)])
                break
    sensors=[name for name in graph.vs["name"] if "sensor" in name]
    controllers=[name for name in graph.vs["name"] if "Controller" in name]
    for sensor in sensors:
        for controller in controllers:
            if ((adatabase["used_inputs"][controller]==adatabase["used_outputs"][sensor]) and ((sensor,controller) not in adatabase['edgelist'])):
                adatabase['mediumlist'].append(adatabase["unused_inputs"][controller])
                graph.add_edges([(sensor,controller)])
                adatabase['edgelist'].append((sensor,controller))
    df_graph = graph.get_edge_dataframe()
    df_graph['medium'] = adatabase['mediumlist']
    df_graph['start']=graph.vs(df_graph.source)["name"]
    df_graph['end']=graph.vs(df_graph.target)["name"] 
    return adatabase,graph,df_graph

def cyber_connect(database,path):
    """
    This function modifies the database by rendering all I/O unused for the automation level
    Input: Database in dictionary format
    Output: Database ready for level 2
    """
    # Automation software graph
    adatabase=database
    graph = Graph.TupleList(database['edgelist'],directed=True)
    sheets,ainput,aoutput,a_util,a_group=search_automation_sheets(graph,path)
    #df_graph = graph.get_edge_dataframe()
    #graph.layout = graph.layout(layout='auto')
    #graph=graph.simplify(multiple=True,combine_edges="random")
    #df_graph = graph.get_edge_dataframe()
    #df_graph['medium'] = database['mediumlist']
    #df_graph['start']=graph.vs(df_graph.source)["name"]
    #df_graph['end']=graph.vs(df_graph.target)["name"]
    #graph = Graph.TupleList(database['edgelist'],directed=True)
    virtual_sensors_in=pd.DataFrame([])
    virtual_sensors_out=pd.DataFrame([])
    controllers=[x for x in range(graph.vcount()) if 'Controller' in graph.vs["name"][x]]
    for jj in list(ainput):
        if 'virtual' in jj:
            virtual_sensors_in=pd.concat([virtual_sensors_in,ainput[jj]],axis=1)
            virtual_sensors_out=pd.concat([virtual_sensors_out,aoutput[jj]],axis=1)
        elif 'reference' in jj:
            graph.add_vertex(jj)
            for c in controllers:
                if (aoutput[jj].iloc[0]==ainput[graph.vs["name"][c]].iloc[0]):
                    adatabase['mediumlist'].append(aoutput[jj].iloc[0])
                    graph.add_edges([(jj,c)])
                    database['edgelist'].append((jj,c))
    for jj in list(virtual_sensors_in): # Add software sensors
        for name in graph.vs["name"]:
            for ii in range(virtual_sensors_in.shape[0]):
                if ((virtual_sensors_in[jj][ii] in adatabase["unused_outputs"][name]) and (virtual_sensors_in[jj][ii]!='None')):
                    if (jj not in graph.vs["name"]):
                        graph.add_vertex(jj)
                    adatabase['mediumlist'].append(virtual_sensors_in[jj][ii])
                    adatabase['edgelist'].append((name,jj))
                    adatabase['used_outputs'][name].append(virtual_sensors_in[jj][ii])
                    try:
                        adatabase['unused_outputs'][name].remove(virtual_sensors_in[jj][ii])
                    except:
                        pass
                    adatabase['used_inputs'][jj]=[virtual_sensors_in[jj][ii]]
                    adatabase['unused_inputs'][jj]=virtual_sensors_in[jj].to_list().remove(virtual_sensors_in[jj][ii])
                    adatabase['unused_outputs'][jj]=virtual_sensors_out[jj][0]
                    adatabase['used_outputs'][jj]=[]
                    graph.add_edges([(name,jj)])
                elif ((virtual_sensors_in[jj][ii] in adatabase["used_outputs"][name]) and (virtual_sensors_in[jj][ii]!='None')):
                    if (jj not in graph.vs["name"]):
                        graph.add_vertex(jj)
                    adatabase['mediumlist'].append(virtual_sensors_in[jj][ii])
                    adatabase['edgelist'].append((name,jj))
                    adatabase['used_inputs'][jj]=[virtual_sensors_in[jj][ii]]
                    adatabase['unused_inputs'][jj]=virtual_sensors_in[jj].to_list().remove(virtual_sensors_in[jj][ii])
                    adatabase['unused_outputs'][jj]=virtual_sensors_out[jj][0]
                    adatabase['used_outputs'][jj]=[]
                    graph.add_edges([(name,jj)])
        for controller in graph.vs["name"]:
            for virtual_sensor in graph.vs["name"]:
                if (("Controller" in controller) and ("virtual" in virtual_sensor) and (adatabase['unused_outputs'][virtual_sensor] in adatabase['used_inputs'][controller])):
                    graph.add_edges([(virtual_sensor,controller)])
                    adatabase['mediumlist'].append(adatabase['unused_outputs'][virtual_sensor])
                    adatabase['edgelist'].append((virtual_sensor,controller))
                    adatabase['used_outputs'][virtual_sensor]=adatabase['unused_outputs'][virtual_sensor]
                    adatabase['unused_outputs'][virtual_sensor]=[]
    df_graph = graph.get_edge_dataframe()
    df_graph['medium'] = adatabase['mediumlist']
    df_graph['start']=graph.vs(df_graph.source)["name"]
    df_graph['end']=graph.vs(df_graph.target)["name"] 
    return adatabase,graph,df_graph

# Semantic database use for control
def closed_loop_creation(adatabase):
    pass

def generate_monitoring_agents (minter):
    # Monitoring modules creation
    sensor_groups=[x for x in a_group.T[0].unique() if x!='None']
    for ii in range(1,len(sensor_groups)+1):
        new_node="Monitoring agent "+sensor_groups[ii-1].split('S')[-1]
        graph.add_vertex(new_node)
        for sensor in list(a_group):
            if (a_group[sensor][0]==sensor_groups[ii-1]):
                graph.add_edges([(sensor,new_node)])
                adatabase['mediumlist'].append(aoutput[sensor].iloc[0])
                adatabase['edgelist'].append((sensor,new_node))
                adatabase['used_outputs'][sensor].append(aoutput[sensor].iloc[0])
                try:
                    adatabase['unused_outputs'][sensor].remove(aoutput[sensor].iloc[0])
                except:
                    pass
                adatabase['used_inputs'][new_node]=aoutput[sensor].iloc[0]
                adatabase['unused_inputs'][new_node]=''
                adatabase['used_outputs'][new_node]=''
                adatabase['unused_outputs'][new_node]=['dec'+sensor_groups[ii-1].split('S')[-1],'dec'+sensor_groups[ii-1].split('S')[-1]+'g']
    for ii in range(1,len(sensor_groups)+1):
        for pred_indices in graph.predecessors("Monitoring agent "+sensor_groups[ii-1].split('S')[-1]):
            for ppred_indices in graph.predecessors(pred_indices):
                for pppred_indices in graph.predecessors(ppred_indices):
                    if (('Controller' in graph.vs["name"][pppred_indices])):
                        graph.add_edges([(pppred_indices,"Monitoring agent "+sensor_groups[ii-1].split('S')[-1])])
                        adatabase['mediumlist'].append(aoutput[graph.vs["name"][pppred_indices]].iloc[0])
                        adatabase['edgelist'].append((graph.vs["name"][pppred_indices],"Monitoring agent "+sensor_groups[ii-1].split('S')[-1]))
                        try:
                            adatabase['used_outputs'][graph.vs["name"][pppred_indices]].append(aoutput[graph.vs["name"][pppred_indices]].iloc[0])
                        except:
                            adatabase['used_outputs'][graph.vs["name"][pppred_indices]]=[aoutput[graph.vs["name"][pppred_indices]].iloc[0]]
                        try:
                            adatabase['unused_outputs'][graph.vs["name"][pppred_indices]].remove(aoutput[graph.vs["name"][pppred_indices]].iloc[0])
                        except:
                            pass
                        adatabase['used_inputs']["Monitoring agent "+sensor_groups[ii-1].split('S')[-1]]=aoutput[graph.vs["name"][pppred_indices]].iloc[0]
                        adatabase['unused_inputs']["Monitoring agent "+sensor_groups[ii-1].split('S')[-1]]=''
                        adatabase['used_outputs']["Monitoring agent "+sensor_groups[ii-1].split('S')[-1]]=''
                        adatabase['unused_outputs']["Monitoring agent "+sensor_groups[ii-1].split('S')[-1]]=''#['dec'+sensor_groups[ii-1].split('S')[-1],'dec'+sensor_groups[ii-1].split('S')[-1]+'g']
                        break
    monitoring_agents=sorted([x for x in graph.vs["name"] if 'Monitoring' in x ])
    for ii in range(len(monitoring_agents)):
        for jj in range (minter.shape[1]):
            if minter[ii,jj]==1:
                graph.add_edges([(monitoring_agents[ii],monitoring_agents[jj])])
                adatabase['mediumlist'].append(adatabase['used_inputs'][monitoring_agents[ii]])
                adatabase['edgelist'].append((monitoring_agents[ii],monitoring_agents[jj]))
# Semantic database use for diagnosis
def fault_generation(adatabase):
    '''This function populates the database with potential sensor faults. A sensor fault is considered as an extra node to the graph connected to the
    respective sensor it affects.
    Input: Hardware components graph 
    Output: Hardware components graph with the addition of sensor faults'''
    graph = Graph.TupleList(adatabase['edgelist'],directed=True)
    sensors=[name for name in graph.vs["name"] if "sensor" in name]
    ii=1
    for sensor in sensors:
        fault_name="f_"+str(ii)
        graph.add_vertex(fault_name)
        graph.add_edges([(fault_name,sensor)])
        adatabase['mediumlist'].append("fault")
        adatabase['edgelist'].append((fault_name,sensor))
        ii=ii+1
    df_graph = graph.get_edge_dataframe()
    df_graph['medium'] = adatabase['mediumlist']
    df_graph['start']=graph.vs(df_graph.source)["name"]
    df_graph['end']=graph.vs(df_graph.target)["name"] 
    return adatabase,graph,df_graph

def start_lat(base):
    """
    Initializes a lattice dictionary with a base list, number of levels, and an empty list for branches.

    Args:
    - base (list): The base list for the lattice.

    Returns:
    - lattice (dictionary): A dictionary containing the base list, the number of levels, and an empty list for branches.
    """
    lattice = defaultdict(list)
    levels = len(base) 
    branches = []
    unavailable_branches=[]
    available_branches=[]
    lattice = {'base' : base, 'levels':levels,'branches' : branches,'unavailable_branches': unavailable_branches,'available_branches':available_branches}
    return lattice

def generate_tree(lattice):
    """
    Generate a tree structure by creating combinations of elements from the `lattice["base"]` list.
    
    Args:
        lattice (dict): A dictionary containing the base elements (`lattice["base"]`) and the number of levels (`lattice["levels"]`).
        
    Returns:
        dict: The updated `lattice` dictionary with the combinations of elements appended to the `lattice["branches"]` list.
    """
    depth = lattice["levels"] - 1
    while depth > 0:
        lattice["branches"].append(list(combinations(lattice["base"], depth)))
        depth = depth - 1
    lattice["branches"].append([tuple(lattice["base"])])
    return lattice

def lattice_gen(graph):
    """
    Generates a lattice structure based on a given database.

    Args:
        adatabase (dict): A dictionary containing the edgelist of a graph. The edgelist is a list of tuples representing the connections between vertices in the graph.

    Returns:
        dict: A dictionary representing the lattice structure, containing the base, levels, and branches.

    Example:
        adatabase = {
            'edgelist': [('sensor1', 'sensor2'), ('sensor2', 'sensor3'), ('sensor3', 'sensor4')]
        }
        lattice = lattice_gen(adatabase)
        print(lattice)
    """
    #graph = Graph.TupleList(adatabase['edgelist'], directed=True)
    sensid=[]
    for v in graph.vs["name"]:
        try:
            if (("sensor" in v) and ("virtual" not in v)):
                sensid.append(graph.vs.find(name=v).index)
        except:
            pass
    lattice=start_lat(sensid)
    lattice=generate_tree(lattice)
    lattice["available_branches"]=lattice["branches"]
    return lattice
    

def distributed_monitoring(adatabase):
    """
    Generates a finite state machine (FSM) based on a given database.

    Args:
        adatabase (dict): A dictionary containing the edge list of the graph representing the database.

    Returns:
        None: The function only prints the dependencies, faults, and signature for each instance.

    Example Usage:
        adatabase = {
            'edgelist': [('sensor1', 'virtual_sensor1'), ('sensor2', 'virtual_sensor2')]
        }
        FSM_generator(adatabase)

    Code Analysis:
        - Convert the edge list in `adatabase` to a directed graph.
        - Identify the sensors and virtual sensors in the graph.
        - Create pairs of sensors and virtual sensors that match based on their names.
        - For each pair, create an instance of the `ARR` class with the sensor, estimator, and an ID.
        - Calculate the fault signature for each instance by finding the dependencies and faults in the graph.
        - Print the dependencies, faults, and signature for each instance.
    """
    
    # Residual generation
    print(graph.vs["name"])
    sensors = [name for name in graph.vs["name"] if str(name).endswith("sensor")]
    print(sensors)
    virtual_sensors = [name for name in graph.vs["name"] if "virtual" in str(name)]
    print(virtual_sensors)
    sensor_pairs = []
    for measurer in sensors:
        for estimator in virtual_sensors:
            if (measurer.split(' sensor')[0].lower() == estimator.split('for ')[1]):
                sensor_pairs.append([measurer, estimator])
    id = 0
    print(sensor_pairs)
    for pair in sensor_pairs:
        arr_id = ARR(pair[0], pair[1], str(id))
        arr_id.fault_signature(graph)
        #print(arr_id.dependencies)
        #print(arr_id.faults)
        #print(arr_id.signature)
        id = id + 1

def Hamm(sign1,sign2):
    """ 
    This function calculates the Hamming distance between two fault signaure vectors.

    Args:
    -sign1,sign2 (signature vectors)

    Returns:
    -Output: Hamm(sign1,sign2) (Hamming distance)
    """
    return np.linalg.norm(sign1 - sign2)

def uncol(FSM):
    """
    Calculates the number of unique columns in a given matrix by comparing the Hamming distance between each pair of columns.

    Args:
    - FSM: A matrix representing a given fault signature matrix.

    Returns:
    - col_unique: The number of unique columns in the given matrix.
    """
    print(FSM)
    if FSM.columns.nlevels > 1:
        data = FSM.iloc[:, 1:]
    else:
        data = FSM

    # Use Pandas' drop_duplicates to get unique rows (treated as columns)
    unique_columns = data.drop_duplicates()
    print(unique_columns)
    print('unique columns=',len(unique_columns))
    # Return the number of unique columns
    return len(unique_columns)
    

class ARR():
    def __init__(self,sensor,estimator,id):
            self.sensor=sensor
            self.estimator=estimator
            self.dependencies=[]
            self.signature=[]
            self.faults=[]
            self.id=id
    def find_dependencies(self, graph):
        self.dependencies=[graph.vs[d]["name"] for d in graph.predecessors(self.estimator) if ("virtual" not in graph.vs[d]["name"]) and ("sensor" in graph.vs[d]["name"])]
        self.dependencies.append(self.sensor)
        dependencies=[]
        for sublist in self.dependencies:
            for item in sublist:
                if type(sublist) is str:
                    dependencies.append(sublist)
                else:
                    dependencies.append(item)
        self.dependencies=dependencies
        self.dependencies = list(dict.fromkeys(self.dependencies))
    def fault_signature(self,graph):
        self.find_dependencies(graph)
        #print(self.dependencies)
        for d in self.dependencies:
            self.signature.append('1')
            self.faults=[graph.vs(f)["name"] for d in self.dependencies for f in graph.predecessors(d)  if "f_" in graph.vs(f)["name"][0]]
        #self.faults.insert(0, 'ID')
        #Multiple faults
        #number_of_faults=len(self.faults)
        #for ii in range(1,number_of_faults):
        #    multiple_faults=combinations(self.faults, ii+1)
        #    self.faults=self.faults+[list(item) for item in multiple_faults]
        #   for com in multiple_faults:
        #        self.signature.append('1')
        self.signature.insert(0, 'ARR '+str(self.id))
        self.signature=[item for item in self.signature]
        self.faults=[item2 for item in self.faults for item2 in item]
        #data=[self.faults,self.signature]
        #df = pd.DataFrame(data[1],columns=data[0]).set_index('ID')

class Division:
    def __init__(self, ssets):
        self.sensor_sets=ssets
        self.discardable=[]
        self.exchangeable=[]
        self.exchangeable_ids=[]
    def sensor_importance(self,graph,dependencies):
        #self.discardable.append(agent,dependencies)
        self.exchangeable.append(dependencies)
        self.exchangeable_ids=[graph.vs.find(name=item).index for sublist in self.exchangeable for item in sublist]
        self.exchangeable_ids=list(set(self.exchangeable_ids))

def generate_FSM(lattice,graph,sensor_sets,run):
    N=len(sensor_sets.sensor_sets)
    virtual_sensors = [name for name in graph.vs["name"] if "virtual" in str(name)]
    ind=1
    sensor_pairs_all=[]
    ARRs_all=[]
    flag='incomplete'
    while (flag=='incomplete'): #Satisfy virtual sensor dependencies [Global]
        sensor_sets.exchangeable=[]
        for selection in sensor_sets.sensor_sets: 
            sensor_pairs=[]
            for sensor_id in selection: # Matching hardware to virtual sensors for residual formation
                    for estimator in virtual_sensors:
                        if (graph.vs[sensor_id]["name"].split(' sensor')[0].lower() == estimator.split('for ')[1]):
                            sensor_pairs.append([graph.vs[sensor_id]["name"], estimator])
            ARRs=[]
            for pair in sensor_pairs: # Confirming requirements and Producing local fault signature matrix F^{(I)}
                    arr_id = ARR(pair[0], pair[1], graph.vs.find(name=pair[0]).index)
                    arr_id.fault_signature(graph)
                    sensor_sets.sensor_importance(graph,arr_id.dependencies)
                    ARRs.append(arr_id)
                    ARRs_all.append(arr_id)
        #print(sensor_sets.exchangeable_ids)
        #print(set().union(*sensor_sets.sensor_sets))
        unsatisfied=list(set(sensor_sets.exchangeable_ids)-set().union(*sensor_sets.sensor_sets))
        #print("Available before:",lattice["available_branches"])
        lattice["unavailable_branches"].extend(sublist for sublist in lattice["available_branches"] if any(x in sublist for x in unsatisfied))
        lattice["available_branches"] = [sublist for sublist in lattice["available_branches"] if not any(x in sublist for x in unsatisfied)]
        #print("Available after:",lattice["available_branches"])
        #print(sensor_sets.sensor_sets)
        #print(sensor_sets.exchangeable_ids)
        #print(unsatisfied)
        for sublist in sensor_sets.sensor_sets:
            empty_spots=len([item for item in sublist if item==0])
            sublist[abs(len(sublist)-empty_spots):len(sublist)]=unsatisfied[0:empty_spots]
            for item in unsatisfied[0:empty_spots]:
                unsatisfied.remove(item)
            if len(sublist) <= 12:
                        sublist.extend([0] * (12 - len(sublist)))
        if (len(unsatisfied)==0):
            flag='complete'
    ARRs_all=[]
    for selection in sensor_sets.sensor_sets: 
        sensor_pairs=[]
        for sensor_id in selection: # Matching hardware to virtual sensors for residual formation
                for estimator in virtual_sensors:
                    if (graph.vs[sensor_id]["name"].split(' sensor')[0].lower() == estimator.split('for ')[1]):
                        sensor_pairs.append([graph.vs[sensor_id]["name"], estimator])
        ARRs=[]
        for pair in sensor_pairs: # Producing local fault signature matrix F^{(I)}
                arr_id = ARR(pair[0], pair[1], graph.vs.find(name=pair[0]).index)
                arr_id.fault_signature(graph)
                #print(arr_id.faults)
                #print(arr_id.signature)
                ARRs.append(arr_id)
                ARRs_all.append(arr_id)
        fault_columns=list(dict.fromkeys([item for sublist in [arr.faults for arr in ARRs] for item in sublist for item2 in item]))
        arrs=[arr.signature[0] for arr in ARRs]
        arrs=list(dict.fromkeys(arrs))
        F_I=pd.DataFrame(np.zeros((len(arrs),len(fault_columns))),columns=fault_columns,index=arrs)
        #print(F_I)
        for fault in fault_columns:
            for arr in ARRs:
                if (fault in arr.faults):
                    F_I.at[arr.signature[0],fault]=1
    #F_I.drop_duplicates(inplace=True)
    # find duplicate rows
    #duplicate_rows = F_I.duplicated()
        number_single_faults=len(fault_columns)
        for ii in range(1,number_single_faults):
            com=combinations(fault_columns,ii+1)
            com=[list(item) for item in com]
            for sublist in com:
                for item in sublist:
                    if (item in arr.faults):
                        F_I.at[arr.signature[0],sublist]=1
                
    # print duplicate rows
    #print(duplicate_rows)
        F_I.to_excel("SFDI_Results/"+str(N)+"_Agent/FSM_"+str(ind)+"("+str(run)+").xlsx")
        ind=ind+1
    #for pair in sensor_pairs_all: # Producing local fault signature matrix F^{(I)}
    #        arr_id = ARR(pair[0], pair[1], graph.vs.find(name=pair[0]).index)
    #        arr_id.fault_signature(graph)
            #print(arr_id.faults)
            #print(arr_id.signature)
    #        ARRs.append(arr_id)
    fault_columns=list(dict.fromkeys([item for sublist in [arr.faults for arr in ARRs_all] for item in sublist for item2 in item]))
    arrs=[arr.signature[0] for arr in ARRs_all]
    arrs=list(dict.fromkeys(arrs))
    F_total=pd.DataFrame(np.zeros((len(arrs),len(fault_columns))),columns=fault_columns,index=arrs)
    #print(F_I)
    for fault in fault_columns:
        for arr in ARRs_all:
            if (fault in arr.faults):
                F_total.at[arr.signature[0],fault]=1
    F_total.drop_duplicates()
    #F_I=0
    #print(F_total)
    cost0=generate_global_FSM(N,uncol(F_total),run)
    return cost0,lattice;
def generate_global_FSM(number_of_agents,cost0,run):
    csv_files = glob.glob(os.path.join("SFDI_Results/"+str(number_of_agents)+"_Agent", "FSM_*("+str(run)+").xlsx"))
    #print('Files considered',csv_files)
    fault_list=[]
    #print(number_of_agents)
    for f in csv_files:
        if ('_chi' not in f):
            df=pd.read_excel(f)
            faults=list(df.columns)
            print(faults)
            try:
                faults.pop(0)
            except:
                pass
            fault_list.append(faults)
    propagated_faults=[item for sublist in fault_list for item in sublist]
    cnt=collections.Counter(propagated_faults)
    propagated_faults=[k for k, v in cnt.items() if v>1]
    agents=["M_"+str(k+1) for k in range(0,number_of_agents)]
    F_chi=pd.DataFrame(np.zeros((number_of_agents,len(propagated_faults))),columns=propagated_faults,index=agents)
    #print(F_chi)
    for fault in propagated_faults:
        for agent in range(0,len(fault_list)):
            if fault in fault_list[agent]:
                F_chi.at["M_"+str(agent+1),fault]=1
    F_chi.to_excel("SFDI_Results/"+str(number_of_agents)+"_Agent/FSM_chi("+str(run)+").xlsx")
    return uncol(F_chi)+cost0;
def rand_select(graph, number_of_agents):
    """
    Randomly selects combinations of elements from the lattice structure generated by the lattice_gen function.

    Args:
    - graph (dict): A dictionary containing the edgelist of a graph.
    - number_of_agents (int): The number of agents for which sensor sets need to be selected.

    Returns:
    - selections (list): A list of randomly selected sensor sets.
    - search_space (dict): A dictionary representing the lattice structure, containing the base, levels, branches, unavailable branches, and available branches.
    """

    selections = []

    while not selections:
        try:
            search_space = lattice_gen(graph)
            search_space["available_branches"] = [list(item) for sublist in search_space["branches"] for item in sublist]
            sensors_used = []
            #dependencies=[]
            for agent in range(0, number_of_agents + 1):
                choices = search_space["available_branches"]

                for sublist in choices:
                    if len(sublist) <= search_space["levels"]:
                        sublist.extend([0] * (search_space["levels"] - len(sublist)))

                choices = np.array(choices)
                selection = choices[np.random.choice(choices.shape[0], replace=False), :]
                selections.append(selection.tolist())
                sensors_used = [item for sublist in selections for item in sublist if item != 0]
                search_space["unavailable_branches"].extend(sublist for sublist in search_space["available_branches"] if any(x in sublist for x in sensors_used))
                search_space["available_branches"] = [sublist for sublist in search_space["available_branches"] if not any(x in sublist for x in sensors_used)]

        except ValueError:
            selections = []

    return selections, search_space

def strategy(agent,my_division,lattice,graph,cost0,run):
    print('My starting division is',my_division.sensor_sets)
    # Going up-down possibilities
    sensors_used = [item for item in copy.deepcopy(my_division.sensor_sets)[agent] if item != 0]
    sensors_for_exchange=[item for item in sensors_used if item in copy.deepcopy(my_division.exchangeable_ids)]
    sensors_for_discard=list(set(sensors_used)-set(sensors_for_exchange))
    #print("Exchange:",sensors_for_exchange)
    #print("Discard:",sensors_for_discard)
    #print("Current division:",my_division.sensor_sets)
    available=[]
    #print("Available branches:", lattice["available_branches"])
    for sublist in lattice["available_branches"]:
        sublist=[i for i in sublist if i!=0]
        available.append(sublist)
    upgrades=[sorted(sensors_used+choices) for choices in available] 
    upgrades=[choices for choices in upgrades if len(sensors_used)+1==len(choices)]#Add one sensor
    #downgrades=[choices for choices in [list(item) for sublist in lattice["branches"] for item in sublist] if ((set(choices).issubset(sensors_used)))]
    #downgrades=[choices for choices in downgrades if len(sensors_used)-1==len(choices)] #Lose one sensor
    downgrades=[]
    if (len(sensors_used)>1):
        downgrades=list(combinations(sensors_used,len(sensors_used)-1))
        downgrades=[list(sublist) for sublist in downgrades]
        for sublist in downgrades:
            if len(sublist) <= lattice["levels"]:
                sublist.extend([0] * (lattice["levels"] - len(sublist)))
        #print("Downgrades", downgrades)
        exchanges=[sublist for sublist in downgrades if any(x not in sublist for x in sensors_for_exchange)]
        #print('Available exchanges',exchanges)
        downgrades=[sublist for sublist in downgrades if sublist not in exchanges]
        #print("Exchanges",exchanges)
        #print("Downgrades", downgrades)
        #removed_sensors=[]
    else:
        downgrades=[]
        exchanges=[]
    for sublist in upgrades:
        if len(sublist) <= lattice["levels"]:
            sublist.extend([0] * (lattice["levels"] - len(sublist)))
    # Determine best move based on 5 random up and 5 random down throws
    #generate_FSM(graph,sensor_sets)
    #print("Current set")
    #print(sensor_sets[agent])
    initial_solution=copy.deepcopy(my_division.sensor_sets)
    #print("Available upgrades")
    #print (upgrades)
    #print("Available downgrades")
    #print (downgrades)
    #print("Chosen upgrades")
    #print(upgrades_tbt)
    #print("Chosen downgrades")
    #print(downgrades_tbt)
    upgrades_tbt=[]
    downgrades_tbt=[]
    exchanges_tbt=[]
    targets=[]
    try:
        upgrades_tbt=random.choices(upgrades,k=5)
        #print("Chosen upgrades")
        #print(upgrades_tbt)
    except:
        pass
        #print("No more upgrades available!")
    try:
        downgrades_tbt=random.choices(downgrades,k=5)
        #print("Chosen downgrades")
        #print(downgrades_tbt)
    except:
        pass
        #print("No more downgrades available!")
    if (len(my_division.sensor_sets)>1) and (exchanges):
        exchanges_tbt=random.choices(exchanges,k=5)
        #print('Suggested exchanges',exchanges_tbt)
        players=list(range(1,len(my_division.sensor_sets)+1))
        #print("Players",players)
        players.remove(agent+1)
        #print("Available to exchange",players)
        targets=random.choices(players,k=5)
    #print("Chosen targets",targets)
    #print("Chosen downgrades")
    #print(downgrades_tbt)
    cost_eval_up=[]
    cost_eval_down=[]
    cost_eval_exch=[]
    conf=copy.deepcopy(my_division.sensor_sets)
    print(conf)
    for up in upgrades_tbt:
        del conf[agent]
        conf.insert(agent,up)
        cost_eval_up.append(generate_FSM(lattice,graph,Division(conf),run)[0]);
    for down in downgrades_tbt:
        del conf[agent]
        conf.insert(agent,down)
        cost_eval_down.append(generate_FSM(lattice,graph,Division(conf),run)[0]);
    if len(my_division.sensor_sets)>1:
        for exch in copy.deepcopy(exchanges_tbt):
            del conf[agent]
            conf.insert(agent,exch)
            cost_eval_exch.append(generate_FSM(lattice,graph,Division(conf),run)[0]);
    difference=0
    action="do nothing"
    if len(cost_eval_exch) <= 5:
        cost_eval_exch.extend([0] * (5 - len(cost_eval_exch)))
    if len(cost_eval_down) <= 5:
        cost_eval_down.extend([0] * (5 - len(cost_eval_down)))
    if len(cost_eval_up) <= 5:
        cost_eval_up.extend([0] * (5 - len(cost_eval_up)))
    costs_total=copy.deepcopy(cost_eval_exch)+copy.deepcopy(cost_eval_down)+copy.deepcopy(cost_eval_up)
    best_cost_index=costs_total.index(max(costs_total))
    print("Decision heuristics",costs_total)
    best_cost=costs_total[best_cost_index]
    new_division=copy.deepcopy(my_division)
    agent_sensors=copy.deepcopy(new_division.sensor_sets)[agent]
    agent_sensors=[item for item in agent_sensors if item!=0]
    print(agent_sensors)
    print('Agent',agent+1,'has',len(agent_sensors),'sensors')
    #print('Suggested exchanges',exchanges_tbt)
    if (best_cost!=0):
        if (best_cost_index<=4): #Exchange is best
            if ((best_cost>cost0) and (len(agent_sensors)>1)):
                action="exchange"
                cost0=best_cost
                print('Initial solution of agent',agent+1,'was',initial_solution[agent])
                print('Suggested solution of agent',agent+1,'is',copy.deepcopy(exchanges_tbt)[best_cost_index])
                difference=list(set(initial_solution[agent])-set(copy.deepcopy(exchanges_tbt)[best_cost_index]))
                print('Sensor division',new_division.sensor_sets)
                print('Agent',agent+1,'passed',difference)
                del new_division.sensor_sets[agent]
                new_division.sensor_sets.insert(agent,exchanges_tbt[cost_eval_exch.index(best_cost)])
                del new_division.sensor_sets[targets[cost_eval_exch.index(best_cost)]-1]
                new_division.sensor_sets.insert(targets[cost_eval_exch.index(best_cost)]-1,list(set(initial_solution[targets[cost_eval_exch.index(best_cost)]-1]).union(set(difference))))
                print('New division is',new_division.sensor_sets)
                #ic(my_division)
            else:
                pass
        elif (best_cost_index<=9): #Downgrade is best
            if ((best_cost>=cost0) and (len(agent_sensors)>1)):
                action="throw"
                cost0=best_cost
                difference=list(set(initial_solution[agent])-set(copy.deepcopy(downgrades_tbt)[cost_eval_down.index(best_cost)]))
                del new_division.sensor_sets[agent]
                new_division.sensor_sets.insert(agent,downgrades_tbt[cost_eval_down.index(best_cost)])
                lattice["available_branches"].append(difference)
            else:
                pass
        else:
            print("Available branches",lattice["available_branches"])
            if (best_cost>cost0):
                action="add"
                cost0=best_cost
                difference=list(set(copy.deepcopy(upgrades_tbt)[cost_eval_up.index(best_cost)])-set(initial_solution[agent]))
                del new_division.sensor_sets[agent]
                new_division.sensor_sets.insert(agent,upgrades_tbt[cost_eval_up.index(best_cost)])
                try:
                    lattice["available_branches"].remove(difference)
                except:
                    pass
                for sublist in lattice["available_branches"]:
                    if (difference in sublist):
                        lattice["available_branches"].remove(sublist)
                    else:
                        pass
                lattice["unavailable_branches"].append(difference)
                print("Available branches (after sensor addition)",lattice["available_branches"])
    print("Last action",action)
    print('Sensor division passed',new_division.sensor_sets)
    generate_FSM(lattice,graph,new_division,run)
    #print("New chosen solution")
    #print(sensor_sets[agent])
    #print("Available branches")
    #print(lattice["available_branches"])
    #print("Sensor sets for next round",my_division.sensor_sets)
    #print(available)
    #print([list(item) for sublist in lattice["branches"] for item in sublist])
    return cost0,copy.deepcopy(new_division),action,difference,copy.deepcopy(lattice);

def objective_function(FSM, FSM_global):
    """
    Calculates the total number of unique columns in two given matrices.

    Parameters:
    FSM (numpy.ndarray): A matrix representing a fault signature matrix.
    FSM_global (numpy.ndarray): Another matrix representing a global fault signature matrix.

    Returns:
    int: The total number of unique columns in FSM and FSM_global.
    """

    return (uncol(FSM) + uncol(FSM_global))

class Solution:
    def __init__(self,sensor_sets):
        self.sensor_division=sensor_sets
        self.cost=0
        self.epoch=0
        self.elapsed=0;
        self.used_sensors=[]
        self.unused_sensors=[]
    def update(self,cost,r,sensor_sets):
        self.sensor_division=sensor_sets
        self.cost=cost
        self.epoch=r
        self.elapsed=time.time();

def gsa(adatabase,run_number):
    graph = Graph.TupleList(adatabase['edgelist'], directed=True)
    N_max=5                            # Maximum number of monitoring agents [search limitation]
    for N in range(0,N_max):
        # Initial solution
        print(f"{bcolors.WARNING}Starting sensor set divisions for monitoring agents{bcolors.ENDC}")
        sensor_sets,lattice=rand_select(graph,N)
        my_division=Division(sensor_sets.copy())
        cost0,lattice=generate_FSM(lattice,graph,my_division,run_number)
        sol=Solution(my_division.sensor_sets)
        print("==>[Epoch",0,"] Cost function: ",cost0," ETA: ",0)
        #Optimisation process
        #error=cost-cost0
        
        flag=0
        cost=cost0
        epoch=1
        column_names=["Agent "+str(item) for item in range (0,N+1)]
        target_names=["Target "+str(item) for item in range (0,N+1)]
        column_names=column_names+target_names
        column_names.insert(0,"Round")
        column_names.append("Cost")
        #print(column_names)
        df=pd.DataFrame(columns=column_names)
        div_copy=copy.deepcopy(my_division)
        while flag<=4:
            print("What is going on",div_copy.sensor_sets)
            actions=[]
            diffs=[]
            for agent in range(0,N+1):
                cost=cost0
                cost,div_copy,action,difference,lattice=strategy(agent,copy.deepcopy(div_copy),lattice,graph,cost,run_number)
                actions.append(action)
                diffs.append(difference)
            log_data=[actions+diffs]
            log_data=[item for sublist in log_data for item in sublist]
            log_data.insert(0,epoch)
            log_data.append(cost)
            df=pd.concat([df,pd.DataFrame([log_data], columns=column_names)], ignore_index=True)
            cost,lattice=generate_FSM(lattice,graph,div_copy,run_number)
            if (cost==cost0):
                flag=flag+1
            elif (cost>cost0):
                flag=flag-1
            sol.update(cost,epoch,div_copy.sensor_sets)
            print("==>[Epoch ",sol.epoch,"] Cost function: ",sol.cost," ETA: ",sol.elapsed)
            epoch=epoch+1
            cost0=cost
        df.to_excel("SFDI_Results/"+str(N+1)+"_Agent/game_"+str(run_number)+"_log.xlsx")

    return 0;



#========================================================================================================
#Graph plotting
#========================================================================================================
# Set colors function
class bcolors:
    HEADER = '\033[95m'
    OKBLUE = '\033[94m'
    OKCYAN = '\033[96m'
    OKGREEN = '\033[92m'
    WARNING = '\033[93m'
    FAIL = '\033[91m'
    ENDC = '\033[0m'
    BOLD = '\033[1m'
    UNDERLINE = '\033[4m'
def colorlist(df_graph):
    """
    Create list of colors that follow the used mediums
    """
    colorlist = sns.color_palette('deep',len(np.unique(df_graph.medium)))
    medlist = np.unique(df_graph.medium)
    
    # Make color dataframe
    dfcolor = pd.DataFrame()
    dfcolor['medium'] = medlist 
    dfcolor['color'] = colorlist

    clist = []
    for imed, namemed in enumerate(df_graph.medium): # for each medium add color to list
        clist.append(dfcolor.color[dfcolor.medium==f'{namemed}'][dfcolor.index[dfcolor.medium==f'{namemed}'][0]])
        
    return clist # output list

# Edge data
#g2.es["label"] = medium
def plot_graph(medium,edgelist,filename):
    g2 = Graph.TupleList(edgelist,directed=True)
    g2=g2.simplify()
    g2.es["medium"] = medium
    print()

    df_graph = g2.get_edge_dataframe()
    df_graph['label'] = medium
    df_graph['medium'] = df_graph.label.str.split("_", n = 1, expand = True)[0]
    df_graph['factor'] = df_graph.label.str.split("_", n = 1, expand = True)[1]
    df_graph['color'] = colorlist(df_graph)

    # Vertice data
    g2.vs["medium"] = df_graph.medium
    g2.vs["color"] = df_graph.medium
    g2.vs["label"] = g2.get_vertex_dataframe().name

    # Create visual stile
    visual_style = {}
    out_name = filename

    # Set bbox and margin
    #visual_style["bbox"] = (400,400)
    visual_style["margin"] = 27# Set vertex colours
    visual_style["edge_color"] = df_graph['color']
    visual_style["vertex_color"] = 'white'# Set vertex size
    #visual_style["vertex_size"] = 45# Set vertex lable size
    #visual_style["vertex_label_size"] = 22# Don't curve the edges
    visual_style["edge_curved"] = False# Set the layout

    # Create layout
    my_layout = g2.layout_auto()# bipartite() #layout("grid")# layout("kamada_kawai")#layout_lgl()
    visual_style["layout"] = my_layout

    # Plot the graph
    return plot(g2, out_name, **visual_style)

def plot_automation_graph(graph,graph_as_dataframe,filename):
    graph_as_dataframe['color'] = colorlist(graph_as_dataframe)
    # Vertice data
    graph.vs["medium"] = graph_as_dataframe.medium
    graph.vs["color"] = graph_as_dataframe.medium
    graph.vs["label"] = graph.get_vertex_dataframe().name

    # Create visual stile
    visual_style = {}
    out_name = filename

    # Set bbox and margin
    #visual_style["bbox"] = (400,400)
    visual_style["margin"] = 27# Set vertex colours
    visual_style["edge_color"] = graph_as_dataframe['color']
    visual_style["vertex_color"] = 'white'# Set vertex size
    #visual_style["vertex_size"] = 45# Set vertex lable size
    #visual_style["vertex_label_size"] = 22# Don't curve the edges
    visual_style["edge_curved"] = True# Set the layout

    # Create layout
    my_layout = graph.layout_auto()#layout("sugiyama")#layout("grid")#layout_auto()# bipartite() ## layout("kamada_kawai")#layout_lgl()
    visual_style["layout"] = my_layout

    # Plot the graph
    return plot(graph, out_name, **visual_style)
    # Plot the graph
    return plot(graph, out_name, **visual_style)