manca il testo del progetto cmq...
classi
//D.Forcisi & E.Galletti
import java.io.*;
class SitoWeb implements Serializable
{
protected int idSito;
protected String URL;
protected char Cat_Sito;
protected ListaID LinkEsterni=new ListaID();
public SitoWeb(int id,String url,char cat)
{
idSito=id;
URL=url;
Cat_Sito=cat;
}
}
class NodoListaID implements Serializable
{
protected int info;
protected NodoListaID next;
public NodoListaID(int i)
{
info=i;
next=null;
}
}
class ListaID implements Serializable
{
protected NodoListaID head;
protected int size;
public ListaID()
{
head=null;
}
public void insert(int i)
{
if(head==null)
head=new NodoListaID(i);
else
{
NodoListaID aux=head;
for(;aux.next!=null;aux=aux.next);
aux.next=new NodoListaID(i);
}
size++;
}
}
class NodoLista
{
protected NodoGrafo info;
protected NodoLista next;
public NodoLista(NodoGrafo x)
{
this(x,null);
}
public NodoLista(NodoGrafo x,NodoLista n)
{
info=x;next=n;
}
}
class lista
{
protected NodoLista head;
protected int size;
public lista()
{
head=null;
size=0;
}
public NodoLista insert(SitoWeb x)
{
if(head==null)
{
head=new NodoLista(new NodoGrafo(x));
size++;
return head;
}
NodoLista aux=head;
for(;aux.next!=null;aux=aux.next);
aux.next=new NodoLista(new NodoGrafo(x));
size++;
return aux.next;
}
public NodoGrafo get(int i)
{
NodoLista aux=head;
for(int j=0;j<i;j++)
{
aux=aux.next;
}
return aux.info;
}
public NodoGrafo searchSito(SitoWeb x)
{
NodoLista aux=head;
for(;aux!=null;aux=aux.next)
{
if(aux.info.inf.idSito==x.idSito)
return aux.info;
}
return null;
}
public NodoGrafo searchID(int s)
{
NodoLista aux=head;
for(;aux!=null;aux=aux.next)
{
if(aux.info.inf.idSito==s)
return aux.info;
}
return null;
}
}
class NodoGrafo
{
protected SitoWeb inf;
protected lista listaAdiacenza;
public NodoGrafo(SitoWeb x)
{
inf=x;
listaAdiacenza=new lista();
}
public boolean isArco(NodoGrafo x)
{
if(this.listaAdiacenza.searchSito(x.inf)!=null)
return true;
return false;
}
public int gradoUscente()
{
return this.listaAdiacenza.size;
}
public int indice(lista l)
{
int indice=0;
for(int i=0;i<l.size;i++)
{
NodoGrafo nodo=l.get(i);
if(nodo==this)
return indice;
indice++;
}
return-1;
}
}
class grafo
{
protected lista Nodi;
protected int numArchi;
public grafo()
{
Nodi=new lista();
numArchi=0;
}
public NodoGrafo getNodo(int i)
{
return this.Nodi.get(i);
}
public NodoGrafo aggiungiNodo(SitoWeb x)
{
if(Nodi.searchSito(x)==null)
return Nodi.insert(x).info;
return null;
}
public void aggiungiArco(NodoGrafo x,NodoGrafo y)
{
if(!x.isArco(y))
{
x.listaAdiacenza.insert(y.inf);
numArchi++;
}
}
public String toString()
{
String str = "GrafoLA:\n";
for(int i=0; i<Nodi.size; i++)
{
NodoGrafo nodoTemp= (NodoGrafo) Nodi.get(i);
str += "- " + nodoTemp.inf.idSito+ ":-->";
for(int j=0; j<nodoTemp.listaAdiacenza.size; j++)
{
NodoGrafo adiacente= (NodoGrafo) nodoTemp.listaAdiacenza.get(j);
str += "-" + adiacente.inf.idSito;
}
str += "\n";
}
return str;
}
public void aggiungiArchi()
{
NodoLista aux=Nodi.head;
for(;aux!=null;aux=aux.next)
{
NodoGrafo ng=aux.info;
NodoListaID aux1=aux.info.inf.LinkEsterni.head;
for(;aux1!=null;aux1=aux1.next)
{
int x=aux1.info;
NodoGrafo ng1=Nodi.searchID(x);
if(!ng.isArco(ng1))
{
aux.info.listaAdiacenza.insert(ng1.inf);
numArchi++;
}
}
}
}
public int gradoEntrante(NodoGrafo x)
{
int grado=0;
NodoLista aux=Nodi.head;
for(;aux!=null;aux=aux.next)
{
if(aux.info.isArco(x))
grado++;
}
return grado;
}
public void linkEntranti()
{
ListaCircolare c=new ListaCircolare();
NodoLista aux=Nodi.head;
int []link=new int[Nodi.size];
for(int i=0;aux!=null;aux=aux.next,i++)
{
link[i]=gradoEntrante(aux.info);
}
int []ordinato=quickSort(link,0,link.length-1);
for(int x=ordinato.length-1;x>0;x--)
{
int z=ordinato[x];
NodoLista aux2=Nodi.head;
for(;aux2!=null;aux2=aux2.next)
{
int k=gradoEntrante(aux2.info);
if(z==k)
if(c.search(aux2.info.inf)==false)
c.insert(aux2.info.inf);
}
}
NodoListaCircolare aux4=c.head;
for(int i=0,j=ordinato.length-1;i<ordinato.length;i++,j--)
{
System.out.println(aux4.info.URL+" link entranti "+ordinato[j]);
aux4=aux4.next;
}
}
public int [] quickSort(int[] array, int primo, int end)
{
if (end> primo)
{
int pivot = primo;
int mitte = primo;
for (int i=primo+1; i<= end; i++)
{
if (array[i]< array[pivot])
{
mitte++;
swap(array, i, mitte);
}
}
swap(array, pivot, mitte);
array= quickSort(array, mitte+1, end);
array =quickSort(array, primo, mitte-1);
}
return array;
}
private void swap(int[] result, int a, int b)
{
int temp = result[a];
result[a] = result[b];
result[b] = temp;
}
}
class DFS
{
protected enum Stato {INESPLORATO, APERTO, CHIUSO}
protected grafo g;
protected lista l=new lista();
protected Stato[] st;
public DFS(grafo g)
{
this.g = g;
st = new Stato[g.Nodi.size];
}
public void visita(NodoGrafo u)
{
for(int i = 0; i < g.Nodi.size; i++)
{
st[i] = Stato.INESPLORATO;
}
DFSvisit(u);
}
protected void DFSvisit(NodoGrafo u)
{
NodoGrafo u2=u;
DFSvisit(u,u2);
}
protected void DFSvisit(NodoGrafo u,NodoGrafo u2)
{
st[u2.indice(g.Nodi)] = Stato.APERTO;
NodoLista adj = u2.listaAdiacenza.head;
for(; adj != null; adj = adj.next)
{
NodoGrafo k=g.Nodi.searchSito(adj.info.inf);
int i=(int)u.inf.Cat_Sito;
int j=(int)adj.info.inf.Cat_Sito;
if(st[(k).indice(g.Nodi)] == Stato.INESPLORATO)
{
l.insert(adj.info.inf);
if(i==j&&u.inf.idSito!=adj.info.inf.idSito)
{
System.out.print(u.inf.idSito+"----->");
NodoLista aux=l.head;
for(;aux!=null;aux=aux.next)
System.out.print("-"+aux.info.inf.idSito);
System.out.println();
}
NodoGrafo nodes=g.Nodi.searchSito(adj.info.inf);
DFSvisit(u,nodes);
}
st[u2.indice(g.Nodi)] = Stato.CHIUSO;
}
}
}
class ListaCircolare
{
protected NodoListaCircolare head;
protected int size;
public ListaCircolare()
{
head=null;
size=0;
}
public void insert(SitoWeb s)
{
if(head==null)
head=new NodoListaCircolare(s);
else
{
NodoListaCircolare aux=head;
for(;aux.next!=null&&aux.next!=head;aux=aux.next);
if(aux==head)
{
aux.next=new NodoListaCircolare(s);
head.pred=head.next;
aux.next.next=head;
aux.next.pred=head;
}
else
{
aux.next=new NodoListaCircolare(s);
aux.next.pred=aux;
aux.next.next=head;
head.pred=aux.next;
}
}
size++;
}
public boolean search(SitoWeb s)
{
NodoListaCircolare aux=head;
for(int i=0;i<size;i++,aux=aux.next)
if(aux.info.idSito==s.idSito)
return true;
return false;
}
}
class NodoListaCircolare
{
protected SitoWeb info;
protected NodoListaCircolare next;
protected NodoListaCircolare pred;
public NodoListaCircolare(SitoWeb i)
{
info=i;
pred=next=null;
}
}
class grafom
{
protected grafo g;
protected lista vertici;
DFSForAdiacenza dfsF;
protected int [][]adiacenza;
public grafom(grafo _g)
{
g=_g;
vertici=g.Nodi;
adiacenza=new int[g.Nodi.size][g.Nodi.size];
dfsF=new DFSForAdiacenza(g,this);
}
public void insertArco()
{
dfsF.visita();
}
public void insertArco(NodoGrafo x, NodoGrafo y)
{
adiacenza[x.indice(vertici)][y.indice(vertici)]=1;
}
public void stampamatrice()
{
for(int i=0; i<adiacenza.length; i++)
{
for(int j=0;j<adiacenza.length;j++)
{
System.out.print(adiacenza[i][j]+" ");
}
System.out.println();
}
}
}
class DFSForAdiacenza
{
protected enum Stato {INESPLORATO, APERTO, CHIUSO}
protected grafo g;
protected grafom m;
protected lista l=new lista();
protected Stato[ ] st;
public DFSForAdiacenza(grafo g,grafom m)
{
this.g = g;
this.m=m;
st = new Stato[g.Nodi.size];
}
public void visita()
{
NodoLista aux=g.Nodi.head;
visita(aux);
}
public void visita(NodoLista n)
{
if(n==null)return;
for(int i = 0; i < g.Nodi.size; i++)
{
st[i] = Stato.INESPLORATO;
}
DFSvisit(n.info);
visita(n.next);
}
public void DFSvisit(NodoGrafo u)
{
NodoGrafo u2=u;
DFSvisit(u,u2);
}
public void DFSvisit(NodoGrafo u,NodoGrafo u2)
{
st[u2.indice(g.Nodi)] = Stato.APERTO;
NodoLista adj = u2.listaAdiacenza.head;
for(; adj != null; adj = adj.next)
{
NodoGrafo k=g.Nodi.searchSito(adj.info.inf);
if(st[(k).indice(g.Nodi)] == Stato.INESPLORATO)
{
m.insertArco(u,k);
NodoGrafo nodes=g.Nodi.searchSito(adj.info.inf);
DFSvisit(u,nodes);
}
st[u2.indice(g.Nodi)] = Stato.CHIUSO;
}
}
}
main
//E.Galletti & D.Forcisi
import java.io.*;
public class test implements Serializable
{
public static void main(String[]args) throws Exception
{
// creo i Siti
SitoWeb s1=new SitoWeb(1,"www.ask",'a');
SitoWeb s2=new SitoWeb(2,"http.ww",'a');
SitoWeb s3=new SitoWeb(3,"www.pi",'c');
SitoWeb s4=new SitoWeb(4,"www.key",'b');
SitoWeb s5=new SitoWeb(5,"dmi",'a');
SitoWeb s6=new SitoWeb(6,"www.lio",'c');
SitoWeb s7=new SitoWeb(7,"forum",'b');
SitoWeb s8=new SitoWeb(8,"www.gulp",'b');
SitoWeb s9=new SitoWeb(9,"www.user",'a');
SitoWeb s10 =new SitoWeb(10,"www.dmiInf",'c');
//riempio le loro liste interne
s1.LinkEsterni.insert(3);
s1.LinkEsterni.insert(7);
s1.LinkEsterni.insert(10);
s2.LinkEsterni.insert(6);
s2.LinkEsterni.insert(9);
s3.LinkEsterni.insert(8);
s4.LinkEsterni.insert(1);
s4.LinkEsterni.insert(3);
s5.LinkEsterni.insert(9);
s6.LinkEsterni.insert(9);
s7.LinkEsterni.insert(6);
s7.LinkEsterni.insert(1);
s7.LinkEsterni.insert(10);
s8.LinkEsterni.insert(9);
s9.LinkEsterni.insert(1);
s9.LinkEsterni.insert(2);
s9.LinkEsterni.insert(3);
s10.LinkEsterni.insert(8);
//Scrivo gli oggetti nel file
ObjectOutputStream out=new ObjectOutputStream(new FileOutputStream("WebSite.dat"));
out.writeObject(s1);
out.writeObject(s2);
out.writeObject(s3);
out.writeObject(s4);
out.writeObject(s5);
out.writeObject(s6);
out.writeObject(s7);
out.writeObject(s8);
out.writeObject(s9);
out.writeObject(s10);
out.close();
ObjectInputStream in=new ObjectInputStream(new FileInputStream("WebSite.dat"));
grafo g=new grafo();
SitoWeb aux=null;
try
{
aux=(SitoWeb)(in.readObject());
while(aux!=null)
{
g.aggiungiNodo(aux);
aux=(SitoWeb)(in.readObject());
}
}
catch(Exception e)
{
in.close();
}
g.aggiungiArchi();
System.out.println(g.toString());//stampa
System.out.println();
System.out.println("stampo i cammini di un dato nodo");
System.out.println();
DFS dfs=new DFS(g);//visita cammini
dfs.visita(g.Nodi.searchSito(s10));//stampa cammini
System.out.println();
System.out.println("metto in ordine dentro la lista circolare");
System.out.println();
g.linkEntranti();
System.out.println();
System.out.println("matrice di adiacenza");
grafom GMatrice=new grafom(g);
GMatrice.insertArco();
GMatrice.stampamatrice();
}
}
una nottata intera però funziona
