Esercizio grafo trasposto

[Darèios89]

Ho un esercizio in cui devo costruire un grafo orientato i cui nodi sono valori numerici, leggendo un input che mi indica le relazioni tra nodi, ad esempio:

(1,3)
         (4,5)
         (3,1)

E via dicendo che mi indicano come sono gli archi, ad esempio c'è un arco tra il nodo con etichetta uno sorgente e quello con etichetta 3 destinazione.

L'esercizio mi chiede di costrire un grafo trasposto e di stampare gli archi, cioè bisogna costruire un grafo in cui gli archi siano invertiti e stampare gli archi.
Per invertire ho pensato al metodo:

public Grafo traspose() {
		TGrafo s=this;    //il grafo avrà gli stessi nodi di quello di partenza
		GNode h=head;
		while(h!=null){     //per ogni nodo del grafo
			Edge e=h.getAdiacent();    //ottengo un arco
			while(e!=null){     //scorro la lista di adiacenza
				s.addEdge(e.getDestinazione(), e.getOrigine());   //inverto l'arco
				e=e.getNext();
			}
			h=h.getNext();
		}
		return s;
	}

Ora il problema è come fare a stampare gli archi, devo visitare il grafo?
Avrei pensato di utilizzare una stringa che memorizza le etichette dei nodi facendo una visita BFS, ma temo che non mi funzioni in quanto ho un assurdo stackOverflow:

public void BFSVisit(GNode node)
	{
		coda.enqueue(node);
		
		while(coda.getSize()>0){
			GNode tmp=coda.dequeue();
			archi+=tmp.getLabel();	
		
			Edge arc=tmp.getAdiacent();
			while(arc!=null){
				GNode dest=arc.getDestinazione();
				if(dest.getColor()==0)
				BFSVisit(dest);      //l'overflow si genera qui
				arc=arc.getNext();
			}
			node.setColor(1);
			
		}
	}

Questa è la classe coda:

public class Queue
{
	private GNode front;
	private GNode tail;
	private int size;
	
	public Queue()
	{
		front=tail=null;
		
		size=0;
	}
	
	public GNode getFront(){return front;}
	public GNode getTail(){return tail;}
	public int getSize(){return size;}
	
	public void enqueue(GNode node)
	{
		GNode nuovo=node;
		if(size==0)
			front=tail=nuovo;
		else{
			tail.setNext(nuovo);
			tail=nuovo;
			}
		size++;
	}
	
	public GNode dequeue()
	{
		if(size==0) return null;
		
		GNode tmp=getFront();
		front=tmp.getNext();
		tmp.setNext(null);
		size--;
		
		return tmp;
		
	}
}

Classe nodo del grafo:

public class GNode
{
	private int label;
	private Edge adiacent;
	private int degree;
	private GNode next;
	private int color;
	private int level;
	
	public GNode(int label)
	{
		this.label=label;
		adiacent=null;
		degree=0;
		next=null;
		color=0;
		level=-1;
	}
	
	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;}
	
}

Classe arco:

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 Grafo:

interface Grafo {
public int node ();
// ritorna il numero di nodi del grafo
public int edges ();
// ritorna il numero di archi del grafo
public boolean isAdj(GNode u, GNode v);
// ritorna vero se il nodo v è adiacente il nodo u
public int degree(GNode u);
// ritorna il numero di nodi adiacenti il nodo u
public Grafo traspose();
// ritorna il grafo trasposto
}

public class TGrafo implements Grafo
{
	private Queue coda=new Queue();
	private int node;
	private int edges;
	private GNode head;
	private String archi;
	
	public TGrafo()
	{
		node=0;
		edges=0;
		head=null;
		archi="";
	}
	
	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)
	{
		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)
	{
		if(node==0) head=nodo;
		
		else{
			nodo.setNext(head);
			head=nodo;
		}
	  node++;
	}
	
	public boolean isPresent(GNode nodo)
	{
		GNode tmp=head;
		while(tmp!=null)
		{
			if(tmp.getLabel()==nodo.getLabel())
				return true;
			tmp=tmp.getNext();
		}
		
	  return false;
	}
		
	public Grafo traspose() {
		TGrafo s=this;
		GNode h=head;
		while(h!=null){
			Edge e=h.getAdiacent();
			while(e!=null){
				s.addEdge(e.getDestinazione(), e.getOrigine());
				e=e.getNext();
			}
			h=h.getNext();
		}
		return s;
	}
	
		
	public void BFSVisit(GNode node)
	{
		coda.enqueue(node);
		
		while(coda.getSize()>0){
			GNode tmp=coda.dequeue();
			archi+=tmp.getLabel();	
		
			Edge arc=tmp.getAdiacent();
			while(arc!=null){
				GNode dest=arc.getDestinazione();
				if(dest.getColor()==0)
				BFSVisit(dest);
				arc=arc.getNext();
			}
			node.setColor(1);
			
		}
	}
	
	public String toString()
	{
		String s="";
		
		BFSVisit(head);
		for(int i=0; i<archi.length(); i++)
		s+="("+archi.charAt(i)+","+archi.charAt(i+1)+")";
		
	return s;
	}
}

Cosa fareste voi?