solves the traveling salesman problem

traveling_salesman.py

import numpy as np
import pandas as pd


def solve_traveling_salesman ( pdf:pd.DataFrame, group_name:str='city'  ) -> str :

    import impetuous.hierarchical as imph
    import impetuous.convert as impc

    M , L   = imph.calculate_hierarchy_matrix ( pdf )

    pc_info = imph.parent_child_matrix_relationships ( M ,  separators = [':','-']  )

    root_id = None
    RichTree = impc.NodeGraph()
    for idx in pc_info.index.values :

        pc = idx.split('-')
        p  = pc[0]

        if root_id is None :
            root_id=p
        c  = pc[1]

        if c[0] == '0' :
            ic = int(c.split(':')[-1])
            c  = M.columns[ic]

        n = impc.Node()
        n.set_id(p)
        n.add_label("")
        n.add_description("")
        n.add_links([c],linktype='links'       )
        n.add_links([c],linktype='descendants' )

        m = impc.Node()
        m.set_id(c)
        m.add_label("")
        m.add_description("")
        m.add_links([p],linktype='links'      )
        m.add_links([p],linktype='ascendants' )

        RichTree.add(n)
        RichTree.add(m)

    # print ( [c for c in RichTree.search( root_id=root_id, order='depth',linktype='descendants' )['path'] if group_name in c] )
    # ABOVE IS EQUIVALENT
    return ( [c for c in RichTree.search( root_id=root_id, order='breadth',linktype='descendants' )['path'] if group_name in c] )


if __name__=='__main__' :

    A = np.array([ [ 0  , 0  ] ,
                   [ 1  , 5  ] ,
                   [ 3  , 6  ] ,
                   [ 6  , 6  ] ,
                   [ 4  , 4  ] ] )

    pdf = pd.DataFrame( A, index    = ['city'+str(i) for i in range(len(A))] ,
                    columns  = ['x','y'] )

    print ( solve_traveling_salesman( pdf , group_name = 'city' ) )