es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Eliminando todos los bordes de un nodo, excepto el más corto.

23 Jul, 2023 Programación

Tengo un grafo en el que un par de nodos están conectados a todos los demás nodos mediante aristas. Esto se hizo con el siguiente código (por lo tanto, ya había un grafo Z1 con nodos conectados por algunas aristas):

for i in range(38,41):
    Z1.add_node(i)
for i in range(38,41):
    for j in range(0,38):
        Z1.add_edge(i, j)

Después de esto, le asigné a todas las aristas un peso igual a la distancia entre los nodos.

for i,j in Z1.edges():
    Z1[i][j]['weight'] = euclidean(coord[i],coord[j])

¿Hay alguna manera de eliminar todas las aristas hacia estos nuevos nodos, excepto la arista con la capacidad más baja? Por lo tanto, dado que agregué 3 nodos, estoy buscando que estos 3 nodos solo estén conectados por la arista más corta al resto del grafo.

Estaba pensando en usar esto:

for i in range(38,41):
    for j in range(0,38):

Y utilizar un condicional “if” para eliminar las aristas si son más largas que la arista más corta actual, pero no sé cómo hacerlo.

Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Sí, hay una forma de eliminar todos los bordes hacia los nuevos nodos excepto aquellos con la capacidad más baja. Aquí hay una forma de hacerlo utilizando la biblioteca networkx en Python:

    import networkx as nx

# supongamos que ya tienes Z1 con nodos y bordes

# agregar pesos a los bordes
for i,j in Z1.edges():
    Z1[i][j]['weight'] = euclidean(coord[i],coord[j])

# crear una lista de los nuevos nodos
new_nodes = list(range(38,41))

# iterar sobre los nuevos nodos
for node in new_nodes:
    # obtener todos los bordes conectados al nodo nuevo actual
    edges = list(Z1.edges(node))

    # encontrar el borde con el menor peso
    min_weight = float('inf') # establecer un valor inicial muy alto
    min_edge = None
    for edge in edges:
        weight = Z1[edge[0]][edge[1]]['weight']
        if weight < min_weight:
            min_weight = weight
            min_edge = edge

    # eliminar todos los demás bordes conectados al nuevo nodo
    for edge in edges:
        if edge != min_edge:
            Z1.remove_edge(*edge)

    Este código primero agrega pesos a todos los bordes del grafo. Luego crea una lista de los nuevos nodos (38, 39 y 40). Para cada nuevo nodo, obtiene todos los bordes conectados a él y encuentra el que tiene el peso más bajo. Luego elimina todos los demás bordes conectados al nuevo nodo, excepto por el borde de menor peso. El método remove_edge toma una tupla de los dos IDs de nodo que el borde conecta.

    Ten en cuenta que este enfoque asume que el peso del borde representa la capacidad, por lo que el borde de menor peso corresponde a la capacidad más alta. Si este no es el caso, es posible que debas modificar el código en consecuencia.

Comments are closed.