Grafi orientati

[Javino89]

Prima di tutto saluto tutto il forum visto che sono un nuovo utente e questo è il mio primo
messaggio!!!

Allora, arrivando subito al dunque, sto operando con dei grafi orientati (digrafi).
Ho una classe astratta SccGraph che ha un costruttore senza argomenti più
quattro metodi astratti che dovrò implementare in una classe SccGraphSolver.
Le uniche informazioni che ho sono che il grafo è orientato ed i vertici sono int.

I metodi che devo implementare sono:

Aggiunge un nuovo arco orientato dal verticeSorgente al verticeDestinazione. Se l'arco è gia' presente nel grafo, ignorare la richiesta.

- public abstract void aggiungiArcoOrientato(int verticeSorgente, int verticeDestinazione)

Aggiunge un nuovo vertice al grafo. Se il vertice è già presente, ignorare la richiesta

- public abstract void aggiungiVertice(int vertice)

Calcola la componente fortemente connessa a cui appartiene il vertice passato come parametro.Assumere che il vertice appartiene al grafo.

- public abstract Set<Integer> calcolaComponenteFortementeConnessa(int vertice)

Calcola la somma dei valori dei vertici che sono raggiungibili a partire dal vertice passato come parametro, compreso il vertice stesso. Assumere che il vertice appartiene al grafo.

- public abstract int calcolaSommaRaggiungibilita(int vertice)


Innanzitutto ho scelto di utilizzare un DFS per la visita del grafo e di utilizzare una lista
delle adiacenze.

Ho creato una classe Vertice con campi:
-elemento (int)
-lista degli archi incidenti (ma non so se va bene per i grafi orientati)
-campo explored (boolean) indica se il vertice è visitato o meno, inizializzato a false.

Ho creato una classe Arco con campi:
- Vertice origine
- Vertice destinazione
- lista archi incidenti origine
- lista archi incidenti destinazione
- campo explored

I miei dubbi sono su queste liste di incidenze che vanno sicuramente bene per i grafi
non orientati, per quelli orientati forse devo considerare semplicemente archi uscenti?

Altro problema è che non so realizzare i rimanenti 2 metodi

Aiutooo grazie in anticipo

[Javino89]

up