Make objects behave like graphs without plugging them into type hierarchy

Abierto
  • ¿Algo no está bien?
#26 6 comentarios 2 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
22/100
Tipo de issue
Nueva funcionalidad
Claridad
Necesita aclaración
Estado de actividad
Estancado
Stack tecnológico
julia
Área
backend-api-design

Línea de trabajo

No se nombran archivos, pruebas ni puntos de entrada de la implementación. Empieza revisando la inspiración de Tables.jl y los traits y métodos de iteración propuestos de GraphsBase; después, inspecciona la interfaz existente de GraphsBase. El trabajo estaría terminado cuando exista un diseño acordado para hacer utilizables objetos externos por los algoritmos de grafos.

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

Descripción

question

I'm writing this at a request of @gdalle to pool random design ideas ;)

Aim

I'd be great if we could make other objects behave like graphs, cheaply without plugging into type hierarchy.
This idea is inspired by the design of Tables.jl which is exemplified by this discourse post.

TLDR: It's very easy to make things behave like row/column based Tables without plugging into any type system.

Usecase

I have my separate type-system where I implement graph-like structures, but focusing on other aspects (deterministic? complete/regular? etc.) It would be very convenient to define just a bunch of methods (like iterators ;)) to make my structures behave like graphs and work with graphs algorithms.

Example (?)

I have a dfsa (deterministic finite state automaton = directed, labeled graph); I'd like to find shortest loop in it. Run a backtrack search on it.

here is (it's just an example, not a proposal!) a rough way one could think in terms of code about this:

const GB = GraphsBase 
GB.isgraph(x::Any) = fale # the default
GB.Directness(::Type{...}) # GB.Directed()/GB.Undirected()/...
GB.Simplicity(::Type{...}) # GB.IsSimpleGraph()/GB.IsMultiGraph()/GB.IsHypergraph()/...
GB.Eagerness(::Type{...}) # GB.Eager()/GB.Lazy() # if vertices edges are given only locally
GB.vertex_type(::Type{...})
GB.edge_type(::Type{...})
.... # and (many?) more

and (based on those traits) a separate sets of interface functions

GB.vertices(graph) = GB.vertices(graph) # an iterator over vertices
GB.neighbours(graph, vertex) # required if GB.Undirected()
GB.out_neighbours(graph, vertex) # which is different from
GB.in_neighbours(graph, vertex) # these two are only required for GB.Directed()

GB.hasedge(graph, vertex, edge) # if graph is GB.Lazy(), otherwise
GB.hasedge(graph, edge)
... # and so on, these are just examples, not a fixed proposal

This way graph can stay un-typed and it'd be easy to "turn anything into a graph"™, including e.g. BitMatrix (hopefully without committing type piracy).

Cons:

  • potentially hard/complex "dispatch" path (but JuMP is an example that even more complex designs are possible ;);
  • explosion of different methods (signatures);
  • no clear type structure that we all love...
Lenguaje dominante
Julia
Estrellas
11
Forks
2
Sin PR fusionados en 30 d

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

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 JuliaGraphs/GraphsBase.jl

Todos los issues de JuliaGraphs/GraphsBase.jl

Issues similares

Más issues de Julia

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.