simplification.py

import numpy as np
import ast
from scipy.spatial.distance import cdist
import plotly.graph_objects as go
from numpy.linalg import norm



## nodes -- matrix [number, node coordinates], edges -- dict{[begin, end] : points}


def deletefakenode(edges, keys_with_new_node, new_index):

        edge1 = edges[keys_with_new_node[0]]
        edge2 = edges[keys_with_new_node[1]]
        A = ast.literal_eval(keys_with_new_node[0])
        B = ast.literal_eval(keys_with_new_node[1])

        
        if (A[0] == new_index) and (B[0] == new_index):
            #print('1')
            edge2[0][::] = edge2[0][::-1]
            edge2[1][::] = edge2[1][::-1]

            edge3x = np.concatenate((edge2[0], edge1[0]))
            edge3y = np.concatenate((edge2[1], edge1[1]))
            #print(str([B[1], A[1]]))
            edges[str([B[1], A[1]])] = (edge3x, edge3y)


            del edges[keys_with_new_node[0]]
            del edges[keys_with_new_node[1]]



        if (A[0] == new_index) and (B[1] == new_index):
            #print('2')
            edge3x = np.concatenate((edge2[0], edge1[0]))
            edge3y = np.concatenate((edge2[1], edge1[1]))

            edges[str([B[0], A[1]])] = (edge3x, edge3y)

            del edges[keys_with_new_node[0]]
            del edges[keys_with_new_node[1]]

        if (A[1] == new_index) and (B[0] == new_index):
            #print('3')
            edge3x = np.concatenate((edge1[0], edge2[0]))
            edge3y = np.concatenate((edge1[1], edge2[1]))

            edges[str([A[0], B[1]])] = (edge3x, edge3y)

            del edges[keys_with_new_node[0]]
            del edges[keys_with_new_node[1]]

        if (A[1] == new_index) and (B[1] == new_index):
            
            #print('4')
            edge2[0][::] = edge2[0][::-1]
            edge2[1][::] = edge2[1][::-1]

            edge3x = np.concatenate((edge1[0], edge2[0]))
            edge3y = np.concatenate((edge1[1], edge2[1]))

            edges[str([A[0], B[0]])] = (edge3x, edge3y)

            del edges[keys_with_new_node[0]]
            del edges[keys_with_new_node[1]]

        return edges


def simplification(nodes, edges, eps):

    dist = cdist(nodes, nodes)
    for k in range(0, len(nodes)):

        # looking for nearest neighboors that are close too much
        new_index = 100
        nearest = np.where(dist[k,:]-eps < 0)[0]

        # check whether there are loops in small neighborhood of vertex and delete it
        if str([k, k]) in list(edges.keys()):
            pair = str([k, k])
            distance_to_vertex = cdist(np.array([nodes[k,:]]), np.column_stack(edges[pair]))
            mask = (distance_to_vertex > eps)[0]
            mask = np.array(mask, dtype=int)
            if np.sum(mask) == 0:
                del edges[pair]
                print('delete loop with vertex', k)

        if len(nearest) > 1:
            print('node', k)
            mean_node = np.mean(nodes[nearest,:], axis = 0)
            other = list(range(len(nodes)))
            other = [r for r in other if r not in nearest]
            print('simplification can be done')
            print('in the neighborhood', nearest)
            print('outsiders:', other)
            other.append(new_index)
            new_indices = {value: index for index, value in enumerate(other)}

            #change nearest to newnode for all edges
            for pair in list(edges.keys()):
                [A,B] = ast.literal_eval(pair)
                if (A in nearest) and (B in nearest):
                    try:
                        del edges[str([A,B])]
                        print(f'delete edge {str([A,B])} in neighborhood')
                    except:
                        del edges[str([B,A])]
                        print(f'delete edge {str([B,A])} in neighborhood')
                else:
                    if A in nearest:
                        edges[str([new_index, B])] = edges.pop(pair)
                    if B in nearest:
                        edges[str([A, new_index])] = edges.pop(pair)

            #renumbering, new dict!!
            new_edges = {}
            for pair in list(edges.keys()):
                try:
                    [A,B] = ast.literal_eval(pair)
                    new_edges[str([new_indices[A], new_indices[B]])] = edges[pair]
                except:
                    print('What', A, B, pair, new_indices)
                    return

            new_nodes = nodes[other[:-1],:]
            new_nodes = np.vstack([new_nodes, mean_node])
            new_index = new_indices[new_index]
            print('index of new mean vertex', new_index)

            keys_with_new_node = [key for key in new_edges.keys() if ast.literal_eval(key)[0] == new_index or ast.literal_eval(key)[1] == new_index]

            if len(keys_with_new_node) == 2:
                #print('start to delete fake node wit new_index ', new_index)
                #print('edges to concatenate', keys_with_new_node)
                new_edges = deletefakenode(new_edges, keys_with_new_node, new_index)
                new_nodes = new_nodes[:-1,:]

            return new_nodes, new_edges, 'one simplification has been done'
    
    return nodes, edges, 'simplification is done'


def searchforfakenodes(nodes, edges):
    # add adjency matrix, it will be faster

    indeces = list(range(len(nodes)))

    for k in range(0, len(nodes)):

        keys_with_new_node = [key for key in edges.keys() if ast.literal_eval(key)[0] == indeces[k] or ast.literal_eval(key)[1] == indeces[k]]

        if len(keys_with_new_node) == 2:

            edges = deletefakenode(edges, keys_with_new_node, indeces[k])
            new_indices = [r for r in indeces if r != indeces[k]]
            new_nodes = nodes[new_indices,:]
            new_indices_dict = {value: index for index, value in enumerate(new_indices)}
            new_edges = {}
            # renumbering, new dict!!!
            for pair in list(edges.keys()):
                [A,B] = ast.literal_eval(pair)
                try:
                    new_edges[str([new_indices_dict[A], new_indices_dict[B]])] = edges[pair]
                except:
                    print('smth is wrong')
                    print(str([new_indices_dict[A], new_indices_dict[B]]), pair)
                
            
            return new_nodes, new_edges, 'fake node deleted'
    
    return nodes, edges, 'no fake nodes'


def simplify(nodes, edges, eps): 

    
    N, E, s = simplification(nodes, edges, eps)

    if s != 'simplification is done':
        print('start')
        while s != 'simplification is done':

            print('another simplification')


            new_nodes = N
            new_edges = E

            #fig = go.Figure()

            #for pair, edge1 in new_edges.items():

            #    pair = ast.literal_eval(pair)
            #    X1 = edge1[0]
            #    Y1 = edge1[1]


            #    fig.add_trace(go.Scatter(x = Y1, y = W-X1, mode='markers',
            #    name=f'edge{pair}'))
            #    fig.add_trace(go.Scatter(x=new_nodes[:,0], y=new_nodes[:,1], mode='markers', name='tps-rbp-nodes'))


            #fig.show()


            N, E, s = simplification(new_nodes, new_edges, eps)


        N, E, s = searchforfakenodes(new_nodes, new_edges)
        if s != 'no fake nodes':
            while s != 'no fake nodes':
                print('another fake node')
                new_nodes = N
                new_edges = E
                N, E, s = searchforfakenodes(new_nodes, new_edges)

            return new_nodes, new_edges
        else:
            return new_nodes, new_edges

    else:
        print('just fake nodes')
        # могли быть "угловатые" фейковые узлы
        N, E, s = searchforfakenodes(nodes, edges)
        if s != 'no fake nodes':
            while s != 'no fake nodes':
                print('another fake node')
                new_nodes = N
                new_edges = E
                N, E, s = searchforfakenodes(new_nodes, new_edges)

            return new_nodes, new_edges
        else:
            return nodes, edges