[Java] Scelta struttura dati

[Giobbo]

Buongiorno a tutti.
Scrivo perché mi sto esercitando con Java e, dopo aver fatto un po' di teoria, vorrei eseguire un esercizio un po' complesso per vedere cosa sono in grado o meno di fare.
Peccato che, pronti via, sono andato un po' nel pallone.
Nell'esercizio che ho preso in considerazione mi si chiede di creare una struttura dati adatta a supportare una rete metropolitana. In particolare, devo essere in grado di stampare le fermate (divise per linea) e aggiungere o togliere una fermata e/o un collegamento tra fermate.

Chiaramente la struttura dati adatta per farlo è un grafo (o sbaglio).
Qui sorge il dubbio: implementato come?
Innanzitutto, ecco la classe Fermata, che chiaramente modella le singole fermate, di cui vi mostro i campi (giusto per far capire):


public class Fermata {

private String nome;
private ArrayList<Linea> linea;
private boolean capolinea}

L'attributo linea è costituito da un ArrayList perché una singola fermata può appartenere a più linee.
E poi la classe Linea:


public class Linea {

private int numero;
private int num_fermate;
private Fermata capolinea;}

Ora, tornando al problema posto.
L'intera "mappa" delle fermate io avevo pensato di farla tramite l'utilizzo di un HashMap, dove le chiavi fossero le varie fermate e i valori riferiti fossero l'insieme di archi che rappresentano i collegamenti tra la fermata (che fa da chiave) e le altre.
E' un procedimento corretto? Troppo complesso? Troppo semplice? Ve ne sono di migliori?
Se come idea va bene, sorge una ulteriore domanda: come faccio, se è possibile, a fare in modo che la chiave sia identificata solamente dal campo contenente il nome della fermata?
Questo in modo che sia possibile accedere sia alle altre informazioni contenute nella chiave (come la lista delle linee di appartenenza o il fatto che sia capolinea o meno) sia chiaramente ai valori riferiti?

Spero mi sia espresso in modo abbastanza chiaro.
Grazie in anticipo a chi avrà la voglia e la pazienza di rispondermi.

[Oceans11]

Chiaramente la struttura dati adatta per farlo è un grafo (o sbaglio).
Qui sorge il dubbio: implementato come?
Un grafo potrebbe essere una struttura dati adatta, ma non è l'unica.
Inutile parlare di migliore o peggiore, dipende dalla propria conoscenza e dal tipo di astrazione si vuole dare.
Tu devi "astrarre" il problema e trovare la tua soluzione. Solo dopo puoi chiederti se si può migliorare e come.
I grafi normalmente vengono astratti con matrici di adiacenza, incidenza o liste di adiacenza.

Innanzitutto, ecco la classe Fermata, che chiaramente modella le singole fermate, di cui vi mostro i campi (giusto per far capire):

public class Fermata {
private String nome;
private ArrayList<Linea> linea;
private boolean capolinea}
L'attributo linea è costituito da un ArrayList perché una singola fermata può appartenere a più linee.
Una fermata può essere capolinea per una linea sì e per un'altra no?
(se la risposta è sì, allora un unico boolean non basta ;) )

E poi la classe Linea:
public class Linea {
private int numero;
private int num_fermate;
private Fermata capolinea;}

Una linea ha un solo capolinea? Se la riposta è no, un solo capolinea ovviamente non basta.
Per come la vedo io, una Linea ha l'informazione dell'insieme di Fermate. (st'info ti manca)

L'intera "mappa" delle fermate io avevo pensato di farla tramite l'utilizzo di un HashMap, dove le chiavi fossero le varie fermate e i valori riferiti fossero l'insieme di archi che rappresentano i collegamenti tra la fermata (che fa da chiave) e le altre.
E' un procedimento corretto? Troppo complesso? Troppo semplice? Ve ne sono di migliori?
Va benissimo "mappare" le fermate e il ragionamento fila, ma hai ben chiaro che vuol dire "i valori riferiti fossero l'insieme di archi che rappresentano i collegamenti tra fermate"? ecco che entrano in gioco le liste di adiacenza :)


Se come idea va bene, sorge una ulteriore domanda: come faccio, se è possibile, a fare in modo che la chiave sia identificata solamente dal campo contenente il nome della fermata?
Questo in modo che sia possibile accedere sia alle altre informazioni contenute nella chiave (come la lista delle linee di appartenenza o il fatto che sia capolinea o meno) sia chiaramente ai valori riferiti?
Non credo di aver capito la domanda.

[Giobbo]

Innanzitutto ti ringrazio per la risposta.
Vado con ordine.


Una fermata può essere capolinea per una linea sì e per un'altra no?
(se la risposta è sì, allora un unico boolean non basta ;) )


Hai ragione, non ci avevo pensato.
Una soluzione potrebbe essere una classe Capolinea formata da due campi, un boolean per stabilire se la fermata è o meno un capolinea e un int che identifica (nel caso la fermata sia effettivamente un capolinea) la linea per cui lo è (a cui potrei dare un valore di default se la fermata non è un capolinea).


Una linea ha un solo capolinea? Se la riposta è no, un solo capolinea ovviamente non basta.
Per come la vedo io, una Linea ha l'informazione dell'insieme di Fermate. (st'info ti manca)


L'insieme delle fermate non l'ho messa come informazione perché sarebbe ridondante rispetto agli archi (di giù mi spiego meglio).
Il capolinea singolo mi serve solamente per iniziare a visitare i nodi del mio grafo (quindi le fermate) da uno in particolare.


Va benissimo "mappare" le fermate e il ragionamento fila, ma hai ben chiaro che vuol dire "i valori riferiti fossero l'insieme di archi che rappresentano i collegamenti tra fermate"? ecco che entrano in gioco le liste di adiacenza :)


Ho proceduto in questo modo.
Ho creato un HashMap del tipo <String, HashSet<Tratta>>; dove String è il nome della fermata e l'HashSet è l'insieme delle tratte (banalmente, da quella fermata ad un altra) che la coinvolgono. Un oggetto Tratta è fatto di questi campi:


private String fermata_collegata; // fermata collegata tramite la tratta
private int linea; // linea di cui fa parte la tratta, visto che due fermate possono essere collegate da più linee
private int lunghezza; // durata della tratta, ovvero peso dell'arco


Le fermate le distinguo esclusivamente tramite stringhe perché, oltre al'HashMap descritto sopra, ne utilizzo un secondo che collega il nome della fermata con le sue informazioni (quindi del tipo <String, Fermata>).

Per quanto riguarda l'ultima domanda che non hai capito, chiedevo se fosse possibile utilizzare un HashMap del tipo <Fermata, HashSet<Tratta>> (in modo da non dover utilizzare du HashMap) ma recuperare informazioni della chiave e del valore corrispondente attraverso esclusivamente un campo specifico dell'oggetto Fermata (ovvero il nome).

[Oceans11]

Una soluzione potrebbe essere una classe Capolinea formata da due campi, un boolean per stabilire se la fermata è o meno un capolinea e un int che identifica (nel caso la fermata sia effettivamente un capolinea) la linea per cui lo è (a cui potrei dare un valore di default se la fermata non è un capolinea).

La classe Capolinea è una buona idea e viene naturale pensarla come sottoclasse di Fermata, non credi?
I dettagli implementativi sono sempre relativi alla quantità di informazioni che vuoi rappresentare nel programma. Ad esempio, una fermata può essere capolinea per una linea e una fermata qualsiasi per un'altra. (non voglio complicarti la vita, solo esporre le possibilità).


L'insieme delle fermate non l'ho messa come informazione perché sarebbe ridondante rispetto agli archi (di giù mi spiego meglio).
Il capolinea singolo mi serve solamente per iniziare a visitare i nodi del mio grafo (quindi le fermate) da uno in particolare.

Va bene se l'info delle fermate la ricavi solo dagli archi. Ma allora la classe che gestisce gli archi di una linea io la chiamerei Linea, mentre la classe che gestisce l'intero grafo la chiamerei ReteMetropolitana. Nel rispetto della OOP che mantiene alto il livello di astrazione. (spero di essere stato chiaro)

Ho proceduto in questo modo.
Ho creato un HashMap del tipo <String, HashSet<Tratta>>; dove String è il nome della fermata e l'HashSet è l'insieme delle tratte (banalmente, da quella fermata ad un altra) che la coinvolgono. Un oggetto Tratta è fatto di questi campi:


private String fermata_collegata; // fermata collegata tramite la tratta
private int linea; // linea di cui fa parte la tratta, visto che due fermate possono essere collegate da più linee
private int lunghezza; // durata della tratta, ovvero peso dell'arco


Le fermate le distinguo esclusivamente tramite stringhe perché, oltre al'HashMap descritto sopra, ne utilizzo un secondo che collega il nome della fermata con le sue informazioni (quindi del tipo <String, Fermata>).

Ah ora ho capito, quindi per ricostruirti la linea in sostanza tu interroghi l'hashmap dal capolinea fino a che non hai trovato tutte le fermate nelle tratte.
Io onestamente avrei utilizzato un ArrayList<Fermate>, ma non dico che sarebbe stato meglio.

Per quanto riguarda l'ultima domanda che non hai capito, chiedevo se fosse possibile utilizzare un HashMap del tipo <Fermata, HashSet<Tratta>> (in modo da non dover utilizzare du HashMap) ma recuperare informazioni della chiave e del valore corrispondente attraverso esclusivamente un campo specifico dell'oggetto Fermata (ovvero il nome).

Ok, ci sono! E si può fare.
Devi fare l'override di hashCode() della classe Fermata (e di equals() perchè i due devono essere consistenti) e calcolarlo solo in base alle info che ti servono (ovvero il nome)

[Giobbo]

La classe Capolinea è una buona idea e viene naturale pensarla come sottoclasse di Fermata, non credi?
I dettagli implementativi sono sempre relativi alla quantità di informazioni che vuoi rappresentare nel programma. Ad esempio, una fermata può essere capolinea per una linea e una fermata qualsiasi per un'altra. (non voglio complicarti la vita, solo esporre le possibilità).

Sì, direi che la sottoclasse è la soluzione migliore e più ovvia.


Ah ora ho capito, quindi per ricostruirti la linea in sostanza tu interroghi l'hashmap dal capolinea fino a che non hai trovato tutte le fermate nelle tratte.
Io onestamente avrei utilizzato un ArrayList<Fermate>, ma non dico che sarebbe stato meglio.

Mmmm.
Ma l'ArrayList<Fermate> intendi al posto dell'HashMap<Tratta>?
Oppure creare, nella classe principale che gestisce la mappa intera (quello che hai citato tu, ReteMetropolitana), oltre alle HashMap delle tratte e delle info delle varie fermate un'ulteriore HashMap del tipo <Linea, ArrayList<Fermate>> (ovvero che ad ogni linea associa la lista delle sue fermate?)


Ok, ci sono! E si può fare.
Devi fare l'override di hashCode() della classe Fermata (e di equals() perchè i due devono essere consistenti) e calcolarlo solo in base alle info che ti servono (ovvero il nome)

Ho capito.
E, perdona la domanda diretta, come si fa?
Provo a scriverti qualcosina, giusto per farmi dire "NO, non così" :D
Allora, se non ho capito male i metodi hashcode() e equals() dovrei inserirli all'interno della classe Fermata (ovvero la classe che vorrei utilizzare come chiave). E per fare in modo che l'hashcode sia calcolato solo in base al nome della mia fermata, potrei fare:

public int hashcode()
int risultato;
risultato = this.nome.hashcode(); // dove this.nome è la stringa che contiene il nome della fermata
return risultato;


Per il metodo equals della classe Fermata poi farei la stessa cosa, confrontando solamente le stringhe che contengono il nome della mia fermata.
Corretto?

Due domande.
Una volta messo l'oggetto Fermata come chiave, è possibile modificare i valori dei campi che formano l'oggetto (tolto chiaramente il nome della Fermata)?
Mi spiego con un esempio: stavo pensando di inserire un colore nella mia classe che utilizzerei poi per effettuare visite in ampiezza (e/o profondità). Potrei andare a aggiornare il valore di tale campo anche se l'oggetto Fermata è utilizzato come chiave?

Seconda domanda: siccome alla fine della costruzione della mia struttura dati, dovrei effettuare una ricerca dei possibili percorsi che collegano due fermate date, la struttura dati che sto portando avanti è funzionale in questo senso? O è troppo complicata?
Nel caso lo sia, come potrei farla migliore? (non voglio la pappa pronta eh, chiedo solo dei suggerimenti).

[Oceans11]

ti rispondo solo ad alcune domande per adesso perchè sono a corto di tempo.

Allora, se non ho capito male i metodi hashcode() e equals() dovrei inserirli all'interno della classe Fermata (ovvero la classe che vorrei utilizzare come chiave). E per fare in modo che l'hashcode sia calcolato solo in base al nome della mia fermata, potrei fare:

Codice:
public int hashcode()
int risultato;
risultato = this.nome.hashcode(); // dove this.nome è la stringa che contiene il nome della fermata
return risultato;
Per il metodo equals della classe Fermata poi farei la stessa cosa, confrontando solamente le stringhe che contengono il nome della mia fermata.
Corretto?

Corretto. (Per equals cerca online le implementazioni tipo, che inizialmente si fanno controlli su tipo della classe e su parametri null)


Una volta messo l'oggetto Fermata come chiave, è possibile modificare i valori dei campi che formano l'oggetto (tolto chiaramente il nome della Fermata)?
Mi spiego con un esempio: stavo pensando di inserire un colore nella mia classe che utilizzerei poi per effettuare visite in ampiezza (e/o profondità). Potrei andare a aggiornare il valore di tale campo anche se l'oggetto Fermata è utilizzato come chiave?


Sì, proprio grazie alla modifica consistente di equals.
Immagina questo, cosa fa la jvm quando ti deve far aggiornare il valore di un campo di Fermata? Cerca la chiave nella mappa. E come la cerca? equals e hashcode che tu hai sovrascritto!

Seconda domanda: siccome alla fine della costruzione della mia struttura dati, dovrei effettuare una ricerca dei possibili percorsi che collegano due fermate date, la struttura dati che sto portando avanti è funzionale in questo senso? O è troppo complicata?
Nel caso lo sia, come potrei farla migliore? (non voglio la pappa pronta eh, chiedo solo dei suggerimenti).

Complicata no. Migliore, in termini di prestazioni, non te lo saprei dire su due piedi.

Appena ho tempo rispondo anche alle altre domande, per quel che so.

[Giobbo]

Ti ringrazio nuovamente.
Al momento, ho optato per questo tipo di struttura:

class Mappa {

private ArrayList<Linea> linee; // salvo le varie linee con relative informazioni
private HashMap<String, Fermata>; // associo alla fermata le relative informazioni
private HashMap<String, HashSet<Tratta>> // associo alla fermata tutte le tratte che la coinvolgono

...


Ora dovrei implementare queste operazioni:

- carica Mappa, che consiste nel caricare una mappa da file (con formato prestabilito, dato come argomento): su questo sono già a posto.

- visualizza, che consiste nel visualizzare tutte le fermate di una linea (la numero n data come argomento): pensavo di fare così. Parto dal capolinea (salvato come ti ho detto nell'oggetto Linea) e cerco tra le sue tratte quella relativa alla linea che voglio stampare. Una volta trovata, stampo la fermata "di arrivo" di tale tratta e passo a cercare tra le tratte di quest'ultima una tratta relativa alla linea che voglio stampare in cui la fermata di arrivo non sia uguale a quella precedente.
Esempio: abbiamo le fermate A---B---C---D della linea 5. Stampo A; cerco tra le sue tratte e trovo "-->B, linea 5"; stampo B; cerco tra le tratte di B, trovo "-->A, linea 5" e "-->C, linea 5", la prima no perché A è la fermata da cui sono arrivato; stampo C; e così via...

- inserisci Tratta, che consiste nell'inserire una nuova tratta (dando come argomenti le due fermate, la linea e la durata della tratta): banalmente, inserisco la tratta negli insiemi delle due fermate coinvolte.

- inserisci Fermata, che consiste nell'inserire una nuova fermata: altrettanto banalmente, aggiungo tale fermata sia nel HashMap delle info che in quello relativo alle varie tratte

- cancella Tratta, che consiste nel cancellare una tratta (come argomento ho le due fermate coinvolte e la linea): anche qui, basta che vado a cercare la tratta negli insiemi delle due fermate e la cancello

- cancella Fermata, che consiste nel cancellare una fermata: cancello la relativa chiave (e di conseguenza i valori associati) dale due HashMap. Dopodichè, scorro l'HashMap relativo alle tratte e cancello tutte quelle in cui la fermata di arrivo è quella che ho cancellato.

- controlla, che consiste nel controllare la mappa e verificare non ci siano linee con biforcazioni: ho pensato che basta vedere se una Fermata ha tre tratte relative ad una linea, visto che può essere collegata solamente a due fermate per essere "regolare".

- percorsi, che consiste nel trovare tutti i percorsi possibili tra due fermate (date come argomento): qui ho difficoltà. Come posso fare? In pratica si dovrebbe implementare la visita in ampiezza (o profondità), giusto? Ma come fare con la struttura dati che utilizzo.

Ti ringrazio in anticipo per la pazienza e la disponibilità.