Semplice modulo per implementare DAG Directed Acyclic Graph. Lo scopo è dare una interfaccia semplice per avere dei grafi che mantengano questa proprietà a ogni arco che viene aggiunto.
Questo progetto non:
- E' una implementazione ottimizata di grafi direzionati aciclici
- E' un framework di per algoritmi di grafi
Vuole essere solo una interfaccia generica per avere sotto controllo la proprietà che il grafo che stiamo costruendo è aciclico. Questo permette di costruire algoritmi che usano questa propietà senza preoccuparsi di doverla reimplementare.
Se poi si vuole usare i propri algoritmi chiedendo scalabilità e performance si può implementare un adapter a qualche libreria che implementa efficacemente i grafi e agganciarla al posto del backend di base.
Prevedo di fare una implementazione in
- Kotlin (in corso)
- Python (ASAP)
- C (a medio termine)
- Pure Java 8 (a medio termine)
- C++ (a medio termine)
Grafo direzionato aciclico
- Costruttore di base può prendere una collection di
T
per costruire i nodi iniziali (costruttore alternativo con nunmero variabile di nodi in ingresso) addNode(T)
aggiunge il nodo (se non esiste) e lo rendeaddEdge(from, to)
aggiunge un arco dafrom
ato
e manda eccezzione sefrom
eto
non fanno parte dello stesso grafo- il nuovo arco crea un ciclo
nodes()
la collection di nodiedges()
la collection di archi[T]
il nodo[T, T]
l'arco se esiste
Nodo del grafo.
context
property in letturaedges()
la colection di edge uscenti come Pair(from, to)nodes()
la colection di nodi collegati come valoribfs()
la lista dei nodi raggiungibili con una ricerca BFS dal nodobfsEdges()
la lista degli archi raggiungibili con una ricerca BFS dal nododfs()
la lista dei nodi raggiungibili con una ricerca DFS dal nododfsEdges()
la lista degli archi raggiungibili con una ricerca DFS dal nodoends()
Set
dei nodi raggiungibili
from
,to
nodi- Scompattabile (implementa
component1
ecomponent2
)