Salve ragazzi,
sono in difficoltà nell'utilizzare la libreria open source GraphViz per rappresentare graficamente un Heap Binario. Sono costretto ad usare questa libreria poichè mi è specificamente richiesta dal testo del progetto che vi posto qui di seguito:
Heap Sort
Descrizione del problema
Il progetto consiste nell’ordinare in modo crescente una serie di numeri dati
come input leggendoli da un file di testo. L’algoritmo di ordinamento utilizzato
deve essere l’Heap Sort. In seguito sarà possibile aggiungere numeri tenendo
sempre la struttura ordinata. E’ richiesta quindi l’implementazione di un Heap
Tree, visibile graficamente al termine dell’ordinamento.
Quindi, il programma legge dal file di testo eventuali numeri, li ordina con
l’heap sort e visualizza l’heap tree generato. A questo punto chiede all’utente se
vuole aggiungere altri numeri. Una volta aggiunto un altro numero si procede di
nuovo con l’ordinamento e la visualizzazione del nuovo albero.
Dati in input
Il file in input è composto da 1 riga con la lista dei numeri da ordinare. La lista
potrebbe essere anche vuota, inserendo manualmente i numeri uno alla volta a
run-time.
Dati di output
Un file immagine che rappresenta l’Heap Tree generato
Suggerimenti
Per la visualizzazione grafica delle strutture dati, specie dei grafi e alberi,
esistono librerie open-source. Una di queste è http://www.graphviz.org.
Con GraphViz basta fornire dei dati secondo una certa sintassi, e lui
automaticamente creerà l’immagine della struttura dati. Ovviamente la
visualizzazione grafica dell’albero è indipendente dal resto del progetto, quindi
può essere integrata alla fine, aggiungendo una classe che converte il vostro
HeapTree in un formato compatibile con GraphViz. La documentazione sul sito
http://www.graphviz.org spiega come fare e fornisce degli esempi.
Il codice che ho implementato fin'ora:
codice:
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
public class ArrayInput {
public int[] loadArray(String nomefile,int n) throws IOException {
// Creazione dell'array
int v []=new int [n];
FileInputStream fstream = new FileInputStream(nomefile);
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
int i=0;
String linea = br.readLine(); //assegno alla variabile linea la prima riga del nostro file di testo
while ((linea!=null)&& (i<n)) {
v[i] = Integer.parseInt(linea); //converto la stringa in un intero e l'assegno al mio array nella i-esima posizione
linea = br.readLine();
i++;
}
in.close();
return v;
}
}
codice:
import java.io.IOException;
import java.util.Scanner;
public class HeapSort
{
private static int[] a;
private static int n;
private static int left;
private static int right;
private static int largest;
// Build-Heap Function
public static void buildheap(int []a){
n=a.length-1;
for(int i=n/2;i>=0;i--){
System.out.println(i);
maxheap(a,i);
}
}
// Max-Heap Function
public static void maxheap(int[] a, int i){
left=2*i;
right=2*i+1;
System.out.println(i + " " + left + " " + right);
if(left <= n && a[left] > a[i]){
largest=left;
}
else{
largest=i;
}
if(right <= n && a[right] > a[largest]){
largest=right;
}
if(largest!=i){
exchange(i,largest);
maxheap(a, largest);
}
}
// Exchange Function
public static void exchange(int i, int j){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
// Sort Function
public static void sort(int []a0){
a=a0;
buildheap(a);
for(int i=n;i>0;i--){
exchange(0, i);
n=n-1;
maxheap(a, 0);
}
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in); // Creo l'oggetto sc che rappresenta la tastiera
System.out.println("Inserire percorso file" + "");
String percorsoinput = sc.nextLine(); // Assegno a percorso input il percorso immesso tramite tastiera grazie al metodo nextLine() dello classe scanner
System.out.println("Inserisci la dimensione dell'array" + "");
String dimensione = sc.nextLine();// Assegno a percorso input il percorso immesso tramite tastiera grazie al metodo nextLine() dello classe scanner
sc.close();
int dim=Integer.parseInt(dimensione);
ArrayInput v = new ArrayInput();
int a []= v.loadArray(percorsoinput, dim);
sort(a);
//ciclo per la visualizzazione per l'heap array
for(int i=0;i<a.length;i++){
System.out.print(a[i] + " ");
}
}
}
Funzionano entrambe le classi il mio problema è proprio implementare la parte grafica con graphviz!
Se avete suggerimenti o consigli su come procedere mi sareste di grandissimo aiuto!
Vi ringrazio in anticipo!