Ejemplos de ordenación topológica en grandes DAG

Question

Estoy buscando aplicaciones del mundo real donde clasificación topológica se realiza en tamaños grandes de gráfico.

Algunos campos donde imagino que podría encontrar tales instancias serían bioinformática, resolución de dependencias, bases de datos, diseño de hardware, almacenamiento de datos ... pero espero que algunos de ustedes hayan encontrado o escuchado algún algoritmo/proyecto/aplicación específico/datasets que requieren una gran cantidad.

Incluso si los datos/proyectos pueden no ser de acceso público, cualquier sugerencia (y estimaciones en el orden de magnitud de los posibles tamaños de gráfico) podría ser útil.

Answer 1

He aquí algunos ejemplos que he visto hasta ahora para topológica Clasificación:

• Mientras que la programación de gráficos de trabajo en un sistema distribuido, por lo general es necesita para ordenar las tareas topológicamente y luego asignarlos a recursos. Estoy al tanto de los gráficos de tareas que contienen más de 100,000 tareas que se ordenan en un orden topológico. Ver this en este contexto.

• Érase una vez que estaba trabajando en un sistema de gestión de documentos. Cada documento en este sistema tiene algún tipo de restricción de precedencia para un conjunto de otros documentos , p. su tipo de contenido o referencia de campo. Luego, el sistema debería poder generar un orden de los documentos con el orden topológico preservado. Como puedo recordar, ¡había alrededor de 5,000,000 de documentos disponibles hace dos años!

• En el campo de las redes sociales, existe una consulta famosa para conocer la distancia de amistad más grande de en la red. Este problema necesita atravesar el gráfico por un enfoque BFS, igual al costo de una clasificación topológica . Considere los miembros de Facebook y encuentre su respuesta .

Si necesita más ejemplos reales, no dude en preguntarme. He trabajado en muchos proyectos trabajando en gráficos grandes.

P.S. para grandes conjuntos de datos DAG, puede echar un vistazo a Stanford Large Network Dataset Collection y Graphics@ Illinois página.

Answer 2

No estoy seguro de si esto se ajusta a lo que está buscando pero ¿sabía Bio4j proyecto?

No todos los contenidos almacenados en el DB basado en gráficos serían adecuados para la clasificación topológica (existen ciclos dirigidos en una parte importante del gráfico), sin embargo hay subgráficos como Gene Ontology and Taxonomy donde este orden puede tener sentido.

Answer 3

TopoR es un enrutador de PCB topológico comercial que funciona primero enrutando la PCB como un problema topológico y luego trasladando la topología al espacio físico. Admiten hasta 32 capas eléctricas, por lo que debe ser capaz de miles de conexiones (digamos 10^4).

Sospecho que los circuitos integrados pueden usar métodos similares.

Answer 4

El company where I work administra una base de datos (patentada) de vulnerabilidades y parches de software. Los parches suelen ser emitidos por un proveedor de software (como Microsoft, Adobe, etc.) a intervalos regulares, y los parches "nuevos y mejorados" "reemplazan" a los antiguos, en el sentido de que si aplica el parche más nuevo a un host, entonces el viejo el parche ya no es necesario.

Esto da lugar a un DAG donde cada parche de software es un nodo con arcos apuntando a un nodo para cada parche "supercedido". Actualmente hay cerca de 10K nodos en el gráfico, y se agregan nuevos parches cada semana.

La clasificación topológica es útil en este contexto para verificar que el gráfico no contenga ciclos; si surgen, significa que hubo un error en la adición de un nuevo registro de base de datos o que la replicación de datos fallidos entre instancias de DB.