Pages: [1]   Go Down
Print
Author Topic: Visite grafi e stampa  (Read 1395 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« on: 18-10-2011, 14:13:14 »

Ho provato ad implementare un grafo con lista di adiacenza, con le relative BFS e DFS. Solo che all' esecuzione del main le stringhe che dovrebbero contenere i nodi secondo le visite sono vuote, non so come fare a fare una stampa, potreste aiutarmi?

La coda che mi serve per la BFS

Code:
public class Queue
{
private GNode front;
private GNode rear;
private int size;

public Queue()
{
front=rear=null;

size=0;
}

public GNode getFront(){return front;}
public GNode getRear(){return rear;}
public int getSize(){return size;}

public void enqueue(GNode node)
{
GNode nuovo=node;
if(size==0)
front=rear=nuovo;
else{
rear.setNext(nuovo);
rear=nuovo;
}
size++;
}

public GNode dequeue()
{
if(size==0) return null;

GNode tmp=getFront();
front=tmp.getNext();
tmp.setNext(null);
size--;

return tmp;

}
}

La lista linkata dove inserirò i nodi del mio grafo:

Code:
public class LinkedList
{
protected int size;
protected GNode head;

public LinkedList()
{
head=null;
size=0;

}

public int getSize(){return size;}
public GNode getHead(){return head;}
public boolean isEmpty(){return (size==0);}
public void addFirst(GNode node)        //inserimento in testa
{
if(isEmpty())
head=node;
else
{
node.setNext(head);
head=node;
}

   size++;
}
}

La classe GNode del grafo:

Code:
public class GNode
{
protected int label;
protected Edge adiacent;
protected int degree;
protected GNode next;
protected int color;
protected int level;
protected GNode parent;          //servirà per la visita BFS

public GNode(int label)
{
this.label=label;
adiacent=null;
degree=0;
next=null;
color=0;
level=-1;
parent=null;
}

public void setParent(GNode node){parent=node;}
public GNode getParent(){return parent;}
public int getLevel(){return level;}
public void setLevel(int i){level=i;}
public int getColor(){return color;}
public void setColor(int i){color=i;}
public int getLabel(){return label;}
public void setLabel(int label){this.label=label;}
public int getDegree(){return degree;}
public GNode getNext(){return next;}
public void setNext(GNode next){this.next=next;}
public void addAdiacent(GNode u)
{
Edge arco=new Edge(this, u);
arco.setNext(adiacent);
adiacent=arco;
degree++;
}

public Edge getAdiacent(){return adiacent;}

public String toString()
{
String ret="";
return ret+=this.getLabel()+" ";
}

}

La classe arco:

Code:
public class Edge
{
private GNode origine;
private GNode destinazione;
private Edge next;

public Edge(GNode origine, GNode destinazione)
{
this.origine=origine;
this.destinazione=destinazione;
next=null;
}

public GNode getOrigine(){return origine;}
public GNode getDestinazione(){return destinazione;}
public Edge getNext(){return next;}
public void setNext(Edge next){this.next=next;}

}

E infine la classe Grafo:

Code:
public class Grafo
{
protected LinkedList list;
protected int node;
protected int edges;
protected String archi;        //APPOSITAMENTE PER QUESTO CASO
protected Queue coda;      //Supporto per BFS
protected String dfs="";    //Stamperò la DFS
protected String bfs="";

public Grafo()
{
coda=new Queue();
list=new LinkedList();
node=0;
edges=0;
archi="";                //APPOSITAMENTE PER QUESTO CASO
}

public int node(){return node;}
public int edges(){return edges;}

public void addEdge (GNode u, GNode v){
u.addAdiacent(v);
edges++;
}

public boolean isAdj(GNode u, GNode v)    //verifica se sono adiacenti
{
Edge arco=u.getAdiacent();

while(arco!=null)
{
if(arco.getDestinazione()==v)
return true;
arco=arco.getNext();
}
return false;
}

public int degree(GNode u){return u.getDegree();}

public void addNode(GNode nodo)
{
list.addFirst(nodo);
node++;
}

public boolean isPresent(GNode nodo)   //verifica se un nodo è contenuto
{
GNode tmp=list.head;
while(tmp!=null)
{
if(tmp.getLabel()==nodo.getLabel())
return true;
tmp=tmp.getNext();
}

  return false;
}

public void BFSVisit(GNode node)         
{
GNode nodo=list.head;

while(nodo!=null)        //per tutti i nodi del grafo setto questi parametri
{
nodo.setColor(0);
nodo.setLevel(-1);
nodo.setParent(null);
nodo=nodo.getNext();
}

node.setLevel(0);             //questo sarà il nodo da cui voglio iniziare la visita e setto così
node.setColor(1);
node.setParent(null);

coda.enqueue(node);                 //inserisco in coda

while(coda.getSize()>0){                    //qui tolgo l' elemento
GNode s=coda.dequeue();
//System.out.println(s.toString());
bfs+=s.toString();                     //lo aggiungo alla stringa che mi stamperà la visita
Edge arc=s.getAdiacent();         //prendo un arco
while(arc!=null){                       //finchè arc non è null ho altri nodi adiacenti
GNode dest=arc.getDestinazione();      //prendo il nodo adiacente e lo memorizzo in dest
if(dest.getColor()==0)
{
coda.enqueue(dest);
dest.setParent(s);
dest.setLevel(s.getLevel()+1);
dest.setColor(1);
}
arc=arc.getNext();    //avanzo per cercare gli altri archi e quindi i nodi adiacenti
}
    s.setColor(1);
}
}

public void DFS()
{
GNode nodo=list.head;
//Grafo corrente=this;

while(nodo!=null)            //per ogni nodo setto di default
{
nodo.setColor(0);
nodo.setParent(null);
nodo=nodo.getNext();
}

GNode nodo1=list.head;

while(nodo1!=null)
{
if(nodo1.getColor()==0)
DFSVisit(/*corrente,*/nodo1);

nodo1=nodo1.getNext();
}
}


public void DFSVisit(/*Grafo g, */GNode s)
{
dfs+=s.toString();        //concateno la stringa che conterrà i valori
s.setColor(1);

Edge arc=s.getAdiacent();
while(arc!=null)            //anche qui finchè ho nodi adiacenti se arc non uguale a null
{
GNode dest=arc.getDestinazione();      //trovo quello adiacente
if(dest.getColor()==(0))
{
dest.setParent(s);
DFSVisit(/*g,*/dest);
}

arc=arc.getNext();         //vado sugli altri archi cioè per cercare nodi adiacenti
}
s.setColor(2);
}


public String toStringDFS()
{
return dfs;
}

public String toStringBFS()
{
return bfs;
}
}


Però in questo main ottengo due stringhe vuote come stampa:

Code:
public class GrafoOrientato
{
public static void main(String []args)
{
Grafo gr=new Grafo();
GNode nodo1=new GNode(10);
GNode nodo2=new GNode(20);
GNode nodo3=new GNode(30);
GNode nodo4=new GNode(40);

gr.addNode(nodo1);
gr.addNode(nodo2);
gr.addNode(nodo3);
gr.addNode(nodo4);


gr.addEdge(nodo4,nodo3);
gr.addEdge(nodo3,nodo2);
gr.addEdge(nodo2,nodo1);

//System.out.println(gr.list.getHead().toString());
System.out.println(gr.toStringBFS());
System.out.println(gr.toStringDFS());
}
}
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
LtWorf
Forumista Esperto
****
Offline Offline

Posts: 1.079

Ogni cosa da me scritta è da intendersi come opinione personale e non come dato di fatto. Anche le eventuali dimostrazioni matematiche da me scritte saranno opinioni personali e quindi dovranno venire dimostrate da una terza parte di fiducia


WWW
« Reply #1 on: 18-10-2011, 20:29:01 »

Secondo me, nella tua posizione non dovresti chiedere aiuto.
http://forum.sdai.unict.it/index.php?topic=14033.0

Poi se qualcuno vuole darti una mano, buon per te :-)
Logged

There are some OO programming languages. I will create the first -_-' language.

LtWorf
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #2 on: 18-10-2011, 20:35:41 »

Secondo me, nella tua posizione non dovresti chiedere aiuto.
http://forum.sdai.unict.it/index.php?topic=14033.0

Poi se qualcuno vuole darti una mano, buon per te :-)

Cosa intendi esattamente?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Nessuno
Apprendista Forumista
**
Offline Offline

Posts: 204



« Reply #3 on: 18-10-2011, 20:58:44 »

sei simpatco...un consiglio,sii meno ermetico...
« Last Edit: 18-10-2011, 21:01:16 by Nessuno » Logged

Sorridi anche se il tuo sorriso è triste, perchè più triste di un sorriso triste c'è la tristezza di non saper sorridere.

::Jim Morrison::
LtWorf
Forumista Esperto
****
Offline Offline

Posts: 1.079

Ogni cosa da me scritta è da intendersi come opinione personale e non come dato di fatto. Anche le eventuali dimostrazioni matematiche da me scritte saranno opinioni personali e quindi dovranno venire dimostrate da una terza parte di fiducia


WWW
« Reply #4 on: 18-10-2011, 21:23:01 »

Mi scuso con Nessuno, ho sbagliato a copiare il link, intendevo questo:
http://forum.sdai.unict.it/index.php?topic=14019.0
Logged

There are some OO programming languages. I will create the first -_-' language.

LtWorf
denote
Apprendista Forumista
**
Offline Offline

Posts: 136


« Reply #5 on: 18-10-2011, 21:26:25 »

Ulala
Logged

Con la concorrenza di Java hanno ucciso 40 anni di computer science
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #6 on: 18-10-2011, 21:42:12 »

 

Allora? Il fatto che stia dando una mano ad un ragazzo non implica che debba sapere esattamente tutto o debba essere un professore e non chiedere. Magari ci sono delle cose che non mi quadrano e chiedo, fatto questo il resto funziona, non vedo perchè se una persona dà una mano a qualcuno non può avere qualcosa da chiedere e da sistemare, non sono un professore.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Nessuno
Apprendista Forumista
**
Offline Offline

Posts: 204



« Reply #7 on: 18-10-2011, 22:04:08 »

Mi scuso con Nessuno, ho sbagliato a copiare il link, intendevo questo:
http://forum.sdai.unict.it/index.php?topic=14019.0

scuse accettate..ci mancherebbe,neanche a parlarne!
(mi scuso io) Ammetto che c'è un po' di stress nell'aria.
Buon lavoro a tutti.
« Last Edit: 18-10-2011, 22:07:35 by Nessuno » Logged

Sorridi anche se il tuo sorriso è triste, perchè più triste di un sorriso triste c'è la tristezza di non saper sorridere.

::Jim Morrison::
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #8 on: 18-10-2011, 22:49:25 »

Pertanto se si dà una mano a qualcuno non è ammessa la richiesta di aiuto alla presenza di qualche dubbio.
Bene, in futuro mi riserverò di aiutare di meno la gente sul forum....non perché nessuno abbia accolto il mio post, ma perché certe risposte secondo me sono un pò esagerate......

Quote
.ci mancherebbe,neanche a parlarne!

Ma a chi ti stai riferendo?
« Last Edit: 18-10-2011, 22:57:57 by Daréios89 » Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Nessuno
Apprendista Forumista
**
Offline Offline

Posts: 204



« Reply #9 on: 19-10-2011, 18:44:25 »



Ma a chi ti stai riferendo?
..a Ltworf, perchè sul forum è facile fraintendere i toni e non vale la pena..siam tutti nella stessa barca,se non ci aiutiamo tra noi a chi dovremmo rivolgerci?
Logged

Sorridi anche se il tuo sorriso è triste, perchè più triste di un sorriso triste c'è la tristezza di non saper sorridere.

::Jim Morrison::
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #10 on: 19-10-2011, 20:08:44 »

Quote
siam tutti nella stessa barca,se non ci aiutiamo tra noi a chi dovremmo rivolgerci?

Appunto...
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: