Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

Optimizing DFS in Data.Graph

Abierto
  • ¿Algo no está bien?
#882 5 comentarios 0 reacciones 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
25/100
Tipo de issue
Refactorización
Claridad
Bastante claro
Estado de actividad
Estancado
Stack tecnológico
haskell
Área
performance

Línea de trabajo

Comience revisando la implementación de dfs de Data.Graph y los helpers generate, prune y chop descritos en el issue. Compare el enfoque dfsGraph propuesto con dfs, topSort, scc y bcc, usando los benchmarks enumerados como referencia. Se considerará completado cuando se eliminen los árboles intermedios innecesarios y se conserven los algoritmos de grafos afectados.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

Graph performance

dfs is the core function in Data.Graph that all other algorithms (topSort, scc, bcc, etc) are based on. It takes a Graph and generates a [Tree Vertex].

dfs makes use of generate, prune and chop to generate a [Tree Vertex] and chop it into the returned [Tree Vertex].

Other functions further transform this [Tree Vertex], for example topSort flattens the [Tree Vertex] into a [Vertex].

These intermediate trees are unnecessary.

  • The trees generated by generate are immediately chopped into other trees.
  • For topSort, the trees returned by dfs are immediately turned into a list.

There is no reason we need to create these trees in memory.

I propose combining the existing generate, prune, and chop function into a new core function that eliminates the intermediate trees from generate and also allows us to choose what to build from the DFS.

dfsGraph :: (Vertex -> a -> b) -> (b -> a -> a) -> a -> Graph -> [Vertex] -> a

Then we can define, for example

dfs = dfsGraph Node (:) []
topSort = dfsGraph <build the list directly>

Benchmarks on a random graph with 10,000 vertices and 100,000 edges:

  dfs:            OK (0.90s)
    3.51 ms ±  79 μs, 57% less than baseline
  topSort:        OK (0.47s)
    3.60 ms ± 107 μs, 59% less than baseline

Other function such as scc and bcc should also benefit, I've not implemented them yet.

Thoughts? I can clean up my code into a PR if this sounds good.

Lenguaje dominante
Haskell
Estrellas
355
Forks
194
Merge medio
2 d 12 h
PR fusionados (30 d)
6

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de haskell/containers

Todos los issues de haskell/containers

Issues similares

Más issues de Haskell

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.