svolgimento progetto 21/12/09

[delaserna]

manca il testo del progetto cmq...

classi

Code:

//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

Code:

//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

[Giuseppo]

Ed ecco il testo

Code:

Sia dato un file contenente oggetti di tipo sitoweb(idsito, urk, cat_sito, lista_link_esterni).
L'attributo lista_link_esterni è un oggetto contenente una lista di id di siti a cui il sito punta.

1. Leggere il file e caricare gli oggetti in un grafo orientato rappresentato con lista di adiacenza. Stampare a video il grafo.

2. Costruire un nuovo grafo rappresentato con matrice di adiacenza il quale contiene un arco tra due siti se esiste un
   cammino che li connette. Stampare a video il grafo.

3. Dato in input un sito web stampare i cammini che partono da esso ed hanno come destinazione siti web della stessa categoria.

4. Creare una lista circolare contenente i siti web ordinati per numero di link entranti (il numero di link entranti per un sito
   è dato dal numero di siti web che puntano ad esso). Stampare la lista circolare con il nome del sito ed il numero di link entranti associati.

Quoto che c'è voluta una nottata intera, ma mi sono divertito 

[Dhavamba]

si è stato moziafiatante!!!

Ma qualcuno non ha accettato il voto?