Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

Make objects behave like graphs without plugging them into type hierarchy

Aperta
  • Qualcosa non va?
#26 6 commenti 2 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
22/100
Tipo di issue
Funzionalità
Chiarezza
Da chiarire
Stato di attività
Ferma
Stack tecnologico
julia
Ambito
backend-api-design

Direzione di ricerca

Non sono indicati file, test o punti di ingresso dell'implementazione. Inizia esaminando l'ispirazione di Tables.jl e i traits e metodi di iterazione proposti di GraphsBase, quindi ispeziona l'interfaccia GraphsBase esistente. Il lavoro sarebbe completato quando fosse disponibile un design concordato per rendere utilizzabili oggetti esterni dagli algoritmi dei grafi.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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...
Lingua principale
Julia
Stelle
11
Fork
2
Nessuna PR unita negli ultimi 30g

Preparare l'ambiente

Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di JuliaGraphs/GraphsBase.jl

Tutte le issue di JuliaGraphs/GraphsBase.jl

Issue simili

Altre issue su Julia

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.