2

Tengo un problema algo complejo, por un lado tengo una lista que contiene a su vez listas. Estas contienen numeros enteros que representan posiciones en un mapa:

rutas = [[0,1,2,3],[0,1,2],[7,4,8],...[5,6],[0,1,3,4]]

a su vez tengo otra lista, que contiene segun su posicion en la lista, las coordenadas de cada uno de esos numeros enteros y un tercer valor que dice si es un punto de entrada, de salida o intermedio.

mu = [[12,13,'ent'],[15,-3,'sal'],...[67,0,'med']]

Por tanto mu[0], corresponde al numero entero 0 en rutas.

Lo que intento hacer pero no consigo es lograr encontrar en rutas, secuencias de numeros que vayan desde un 'ent' a un 'sal' y poder plotearlas. Me explico mejor con un ejemplo.

Supongamos que el punto 0 es 'ent' y que 4 y 3 son 'sal', entre otros... Quiero poder encontrar en rutas, aquellas secuencias que vayan de 0 a 4 y de 0 a 3, sin importar si 0 es el primer valor en rutas y 4 o 3 el ultimo. Es decir, incluso estando en mitad de la lista. Y ademas si tengo una ruta que es: [0,1,2,3] y otra que es [0,1,2] que esta ultima cuenta como si perteneciera a [0,1,2,3].

La idea es pues una vez que tengo seleccionadas todas las rutas que van de ent -> sal plotear las coordenadas de mu correspondientes.

Si al menos sabeis como enfocarlo o si existe alguna funcion que pueda ayudar.

3
  • 1
    Me costó entender, pero lo que pides parece ser un grafo dirigido. ¿Estás tratando con listas muy grandes? Commented el 18 jul. 2017 a las 11:06
  • la lista rutas si que es bastante grande, pero las listas dentro de rutas suelen ser cortas, unos 10 valores maximo. De todas forma lo de plotearlas es lo que menos me importa.
    – Juanca M
    Commented el 18 jul. 2017 a las 12:10
  • 1
    Sería útil que proporcionaras un ejemplo mínimo verificable bien definido. Ahora cuesta un poco seguir el ejemplo.
    – fedorqui
    Commented el 18 jul. 2017 a las 12:39

1 respuesta 1

1

Sin estar bien definido como problema, intuyo que lo que intentas hacer es dibujar un grafo sin dibujar dos veces la misma conexión. Que un camino no pase dos veces por la misma arista es lo que se conoce por "caminio euleriano" y puedes encontrar bastante bibliografía sobre cómo afrontar este tipo de problemas, aunque no te extrañe si no encuentras una solución definitiva.

Antes de responder a tu problema, hay algunas dudas y suposiciones:

  1. ¿Están todas la rutas bien definidas? Supongo que sí y que todos las rutas empieza en un nodo ent y acaban en uno sal. (En caso contrario, lo primero sería depurar la lista de rutas).
  2. Dices que los nodos ent y sal pueden estar en medio, o sea, pueden hacer de med. ¿Es posible que un nodo ent aparezca en otra lado como sal o viceversa? ¿Es posible que se den ciclos, o sea, una ruta que empieza y acaba en el mismo punto? Voy a suponer que no hay cierres, que un punto ent siempre aparece como ent y uno sal siempre como sal.
  3. ¿Qué pasa con los solapes?¿Existe transitividad? Supongamos que tenemos dos rutas, [0,1,2] y [1,2,3], 0 y 1 son ent, y 2 y 3 son sal. ¿Hay que tomarlas como dos rutas independientes o formarían una única ruta [0,1,2,3]? Por simplicidad, consideraré que no hay solapes, o sea, una ruta se descarta únicamente si está contenida en otra.

Con estas suposiciones basta con comprobar que una ruta no está incluida en otra:

def is_included(ruta, rutas):
    n = len(ruta)
    subrutas = (r[i:i+n] for r in rutas for i in range(len(r)-n+1))
    return ruta in subrutas

sel = [ruta for (i,ruta) in enumerate(sorted(rutas, key=len))
      if not is_included(ruta, rutas[i+1:])]

Si la lista de rutas es muy grande, es necesario usar alguna estrategia que disminuya el número de comparaciones....

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.