Pages: [1] 2   Go Down
Print
Author Topic: Grafi  (Read 3426 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« on: 27-05-2009, 19:38:07 »

Salve ragazzi ho provato a implementare la classe sui grafi ma ancora mi da parecchi errori , potreste darmi una mano , l'errore che non riesco a capire è il perchè mi dice in alcune parti che il tipo ListNode sia inconvertibile, come ad esempio questa parte

if(((NodoGrafo) nodi.get(i)).getInfo() == this.getInfo()) return i;   

Code:
class NodoGrafo
{
private String info;

public NodoGrafo(String f)
{
info = f;
}

public final void setInfo(String f)
{
info = f;
}

public final String getInfo()
{
return info;
}

// public int gradoUscente()
//  {
// return this.archiUscenti().getSize();
// }


public int indice(LinkedList nodi)
{
for(int i=0;i < nodi.getSize();i++)
{
if(((NodoGrafo) nodi.get(i)).getInfo() == this.getInfo()) return i;
}
return -1;
}
}



class GrafoMA
{
private final static int DIMENSIONE_INIZIALE = 3;

private LinkedList nodi; //elenco oggetti di tipo nodo

protected int [][] matriceDiAdiacenza;


public GrafoMA()
{
this.nodi = new LinkedList();
this.matriceDiAdiacenza = new int [DIMENSIONE_INIZIALE][DIMENSIONE_INIZIALE];
}


public void AggiungiArco(NodoGrafo x , NodoGrafo y , int info)
{
matriceDiAdiacenza[x.indice(nodi)][y.indice(nodi)] = info;
return;
}


public void AggiungiNodo(String info)
{
NodoGrafo in = new NodoGrafo(info);
nodi.insertTail((ListNode)in);

if (matriceDiAdiacenza.length < nodi.getSize())
{
int [][]tmp = new int [2*DIMENSIONE_INIZIALE][2*DIMENSIONE_INIZIALE];
for(int i = 0;i<DIMENSIONE_INIZIALE;i++)
{
for(int j=0;j<DIMENSIONE_INIZIALE;j++)
{
tmp[i][j] =matriceDiAdiacenza[i][j];

}
}

DIMENSIONE_INIZIALE = 2 *DIMENSIONE_INIZIALE;
matriceDiAdiacenza = tmp;
}

return;
}



public void inz()
{
for(int i=0; i < numeroNodi();i++)
{
for(int j=0; j<numeroNodi(); j++)
{
matriceDiAdiacenza[i][j]=-1;
}

}

}


public NodoGrafo getNodo(int indice)
{
return (NodoGrafo) nodi.get(indice);
}

public NodoGrafo [] nodiLista()
{
NodoGrafo [] arrayNodi = new NodoGrafo[nodi.getSize()];
int indice = 0;

for( int i=0; i<nodi.getSize() ; i++)
{
arrayNodi[indice++] = (NodoGrafo) nodi.get(i);
}
return arrayNodi;
}



public int numeroArchi()
{
int archi = 0;

for (int i = 0; i < numeroNodi(); i++)
{
for (int j = 0; j < numeroNodi(); j++)
{
if(matriceDiAdiacenza[i][j] != -1) archi++;
}
}
return archi;
}


public int numeroNodi()
{
return nodi.getSize();
}


public void rimuoviArco(NodoGrafo x, NodoGrafo y)
{
matriceDiAdiacenza[x.indice(nodi)][y.indice(nodi)] = -1;
}


public void rimuoviNodo(NodoGrafo v)
{
int indice = v.indice(nodi);
nodi.deleteAt(indice); // rimuovo v dalla lista dei nodi


for(int i=0;i<numeroNodi();i++)
{
matriceDiAdiacenza[indice][i] = -1;

}

for(int j=0;j<numeroNodi();j++)
{
matriceDiAdiacenza[j][indice] = -1;

}


}
}


class Arco
{

protected final NodoGrafo origine;
protected final NodoGrafo destinazione;

private int info;  //informazione associata all'arco

public Arco(NodoGrafo o, NodoGrafo d, int info)
{
origine= o;
destinazione = d;
setInfo(info);
}

public final int getInfo()
{
return info;
}

public final void SetInfo(int f)
{
info = f;
}

public NodoGrafo getOrigine()
{
return origine;
}

public NodoGrafo getDestinazione()
{
return destinazione;
}

}




e poi ho usato le LinkedList e i ListNode con i tipi genirici

Code:
public class ListNode<E>
{

  protected E info;
  protected ListNode<E> next;

  public ListNode(E x)
  {
    this(x,null);
  }

  public ListNode(E x, ListNode<E> n)
  {
      info = x;
      next = n;
  }

 /**
  * Ritorna il riferiemento all'oggetto info contenuto in questo nodo.
  * @return il riferimento di tipo Object all'oggetto info contenuto in tale nodo.
  */
  public E getInfo()
  {
    return info;
  }

  /**
   * Ritorna il riferimento next al nodo successivo.
   * @return il riferimento di tipo ListNode al nodo successivo.
   */
  public ListNode<E> getNext()
  {
    return next;
  }

  /**
   * Setta il riferimento all'oggetto info contenuto in questo nodo.
   */
    public void setInfo(E o)
    {
      info = o;
    }

   /**
    * Setta il riferimento next al nodo successivo.
    */
    public void setNext(ListNode<E> n)
    {
      next = n;
    }

}

public class LinkedList<E extends Comparable<E>>
{

       private ListNode<E> head;
       private int size = 0;


        /**
         * Costruisce una lista
         */
        public LinkedList( )
        {
            head =  null;
        }

        /**
         * Test se la lista è vuota.
         * @return true se vuota, false altrimenti.
         */
        public boolean isEmpty( )
        {
            return head == null;
        }

        /**
         * Svuota la lista.
         */
        public void clear( )
        {
            head = null;
            size = 0;
        }

        /**
        * Restituisce il numero effettivo di elementi nella lista.
        */
       public int getSize( )
       {
           return size;
       }



        /**
         * Restituisce la testa della lista.
         */
        public ListNode<E> getHead( )
        {
            return head;
        }


        /**
         * Setta la testa della lista ad un nuovo valore.
         */
      public void setHead( ListNode<E> h )
      {
      head = h;
      }


        /**
         * Inserisce un elemento in testa alla lista.
         */
      public void insertHead(E x)
      {
      head = new ListNode<E>(x,head);
      size++;
      }


         /**
          * Inserisce un elemento in coda alla lista.
          */
      public void insertTail(E x)
      {
    if (isEmpty()) head = new ListNode<E>(x);
    else
    {
    ListNode<E> aux = head;
    for(; aux.next!= null; aux = aux.next);
    aux.next = new ListNode<E>(x);
    }
    size++;
      }

          /**
           * Concatena una data lista alla lista in questione.
           */
      public void concat(LinkedList<E> l)
      {
     
      if (!l.isEmpty() && !this.isEmpty())
      {
      ListNode<E> aux = head;
      for(; aux.next!= null; aux = aux.next);
     
      aux.next = l.getHead();
      size += l.getSize();
      }
     
      if (!l.isEmpty() && this.isEmpty())
      {
      head = l.getHead();
      size = l.getSize();
      }
     
      }


         /**
          * Inserimento ordinato di un elemento. Per il confronto viene fatto
          * il cast esplicito dell'oggetto info nel tipo Comparable.
          * @param x l'elemento da inserire.
          * @see java.lang.Comparable
          */
         public void insertOrd(E x )
         {
           if (isEmpty())
           {
             head = new ListNode<E>( x );
             size++;
           }
           else
           {
       //if ( ((MyInteger)head.info).compareTo((MyInteger)x) >= 0 )
       if(head.info.compareTo(x) >= 0) insertHead ( x );
       else
   {
    ListNode<E> aux = head;
    for(; ( aux.next != null ) && ( aux.info.compareTo(x)) < 0 ;aux = aux.next );
   
    aux.next = new ListNode<E>(x, aux.next);
   
    size++;
   }
     }
   
   
}     
     
     


        /**
         * Restituisce il nodo contenente la prima occorrenza dell'elemento di chiave x.
         * Per il confronto viene fatto il cast esplicito dell'oggetto info nel tipo Comparable.
         * @param key la chiave dell'elemento da cercare.
         * @return il ListNode contenente l'elemento di chiave x, null altrimenti.
         * @see java.lang.Comparable
         */
         public ListNode searchOrd( E x )
         {
           ListNode<E> aux = head;
           for( ; aux != null && aux.info.compareTo(x) < 0; aux = aux.next);
           
           if (aux != null && aux.info.equals(x))
             return aux;

           return null;
         }


        /**
         * Restituisce il nodo contenente la prima occorrenza dell'elemento di chiave x.
         * @param key la chiave dell'elemento da cercare.
         * @return il ListNode contenente l'elemento di chiave x, null altrimenti.
         */
        public ListNode search( E x )
        {
          ListNode<E> aux = head;
          for( ; aux != null && !aux.info.equals( x ); aux = aux.next);
          return aux;
        }


        /**
         * Cancella l'elemento in testa e restituisce l'info.
         */
        public E deleteHead()
        {
          if (isEmpty())
              return null;

          ListNode<E> aux = head;
          head = head.next;
          size--;

          return aux.info;
        }


        /**
         * Cancella l'elemento in coda e restituisce l'info.
         */
        public E deleteTail()
        {
          if (isEmpty())
              return null;

          ListNode<E> aux = head;
          ListNode<E> pred = null;
          for(; aux.next != null; pred = aux, aux = aux.next);
          if (pred == null)
             head = null;
          else
             pred.next = null;
          size--;

          return aux.info;

        }


        /**
         * Cancella e restituisce il nodo di chiave x.
         */
         public ListNode<E> deleteKey(E x)
         {
             ListNode<E> aux = head;
             ListNode<E> pred = null;
             for(; aux != null && !aux.info.equals(x); pred = aux, aux = aux.next);
             if (aux != null)
             {
                if (pred == null) head = head.next;
                else
                  pred.next = aux.next;
                size--;
             }
             return aux;
          }

         /**
         * Cancella e restituisce il nodo alla posizione pos
         * (iniziando a contare da 0, 1, 2, 3 ...).
         */
         public ListNode<E> deleteAt(int pos)
         {

           ListNode<E> aux = head;
           ListNode<E> pred = null;

          for(int count = 0; aux != null && count != pos;pred = aux, aux = aux.next, count++);

          if (aux != null)
          {
           if (pred == null)
               head = head.next;
           else pred.next = aux.next;
           size --;
          }
         return aux;

        }

  //Un semplice metodo di stampa
        public void printList( )
        {
            if( this.isEmpty( ) )
                System.out.print( "Empty list" );
            else
            {
                ListNode<E> aux = this.head;
                for(; aux != null; aux = aux.next)
                    System.out.print( aux.info + " " );
            }

            System.out.println("\nSize = "+ this.size + " \n" );
        }
       
        public ListNode<E> get(int i)
        {
        ListNode<E> aux = head;
       
        int count =0;
       
        for(;(aux!= null)&&(count < i);aux= aux.next,count++ );
       
        return aux;
        }


     
    }


« Last Edit: 27-05-2009, 19:42:54 by Alex_47 » Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #1 on: 30-05-2009, 10:46:15 »

io ho implementato grafo e digrafo(grafo orientato) con matrice di adiacenza in questo modo..non so se mancano metodi o qualcosa non funziona..per le prove che ho fatto io dovrebbe essere tutto ok..
EDIT: ho messo anche grafo e digrafo con lista di adiacenza!
Code:
public class GrafoMA
{
private LinkedList nodi;
private int[][] matrice;
public GrafoMA()
{
nodi=new LinkedList();
matrice=new int[0][0];
}
public GrafoMA(LinkedList n)
{
nodi=n;
int d=getNumNodi();
matrice=new int[d][d];
}
public int getNumNodi()
{
int cont=0;
Nodo aux=nodi.getHead();
for(;aux!=null;aux=aux.getNext())
cont++;
return cont;
}
public int getNumArchi()
{
int cont=0;
for(int i=0;i<matrice.length;i++)
for(int j=0;j<matrice.length;j++)
if(matrice[i][j]!=0)
cont++;
return cont/2;
}
public int getIndice(Nodo n)
{
int index=-1;
Nodo aux=nodi.getHead();
for(int i=0;aux!=null&&index==-1;aux=aux.getNext(),i++)
if(aux.getInfo().compareTo(n.getInfo())==0)
index=i;
return index;
}
public void insertNodo(Comparable c)
{
nodi.insertTail(new Nodog(c));
matrice=ingrandisciMatrice();
}
public void insertArco(Comparable c,Comparable d)
{
insertArco(c,d,1);
}
public void insertArco(Comparable c,Comparable d, int peso)
{
Nodo n=nodi.search(cerca(c));
Nodo m=nodi.search(cerca(d));
insertArco(n,m,peso);
}
public void insertArco(Nodo x,Nodo y)
{
insertArco(x,y,1);
}
public void insertArco(Nodo x,Nodo y,int peso)
{
matrice[getIndice(x)][getIndice(y)]=peso;
matrice[getIndice(y)][getIndice(x)]=peso;
}
public Nodog cerca(Comparable c)
{
Nodo aux=nodi.getHead();
Nodog temp=null;
for(;aux!=null&&temp==null;aux=aux.getNext())
if((((Nodog)aux.getInfo()).info).compareTo(c)==0)
temp=(Nodog)aux.getInfo();
return temp;
}
public void deleteNodo(Comparable c)
{
Nodo n=nodi.search(cerca(c));
int rc=getIndice(n);
matrice=rimuovi(rc);
nodi.deleteKey(cerca(c));
}
public void deleteArco(Comparable c,Comparable d)
{
Nodo n=nodi.search(cerca(c));
Nodo m=nodi.search(cerca(d));
deleteArco(n,m);
}
public void deleteArco(Nodo x,Nodo y)
{
matrice[getIndice(x)][getIndice(y)]=0;
matrice[getIndice(y)][getIndice(x)]=0;
}
private int[][] rimuovi(int indice)
{
int[][] temp=new int[matrice.length-1][matrice.length-1];
for(int i=0;i<temp.length;i++)
for(int j=0;j<temp.length;j++)
if(i!=indice&&j!=indice)
temp[i][j]=matrice[i][j];
return temp;
}
private int[][] ingrandisciMatrice()
{
int[][] t=new int[matrice.length+1][matrice.length+1];
for(int i=0;i<matrice.length;i++)
for(int j=0;j<matrice.length;j++)
t[i][j]=matrice[i][j];
return t;
}
public String toString()
{
String s="Il grafo ha nodi: ";
Nodo aux=nodi.getHead();
for(;aux!=null;aux=aux.getNext())
s+=aux.getInfo()+"\t";
s+="\n e matrice di adiacenza:\n";
for(int i=0;i<matrice.length;i++)
{
for(int j=0;j<matrice.length;j++)
s+=matrice[i][j]+"\t";
s+="\n";
}
return s;
}
}

Code:
public class DigrafoMA
{
private LinkedList nodi;
private int[][] matrice;
public DigrafoMA()
{
nodi=new LinkedList();
matrice=new int[0][0];
}
public DigrafoMA(LinkedList n)
{
nodi=n;
int d=getNumNodi();
matrice=new int[d][d];
}
public int getNumNodi()
{
int cont=0;
Nodo aux=nodi.getHead();
for(;aux!=null;aux=aux.getNext())
cont++;
return cont;
}
public int getNumArchi()
{
int cont=0;
for(int i=0;i<matrice.length;i++)
for(int j=0;j<matrice.length;j++)
if(matrice[i][j]!=0)
cont++;
return cont;
}
public int getIndice(Nodo n)
{
int index=-1;
Nodo aux=nodi.getHead();
for(int i=0;aux!=null&&index==-1;aux=aux.getNext(),i++)
if(aux.getInfo().compareTo(n.getInfo())==0)
index=i;
return index;
}
public void insertNodo(Comparable c)
{
nodi.insertTail(new Nodog(c));
matrice=ingrandisciMatrice();
}
public void insertArco(Comparable c,Comparable d)
{
Nodo n=nodi.search(cerca(c));
Nodo m=nodi.search(cerca(d));
insertArco(n,m);
}
public void insertArco(Comparable c,Comparable d, int peso)
{
Nodo n=nodi.search(cerca(c));
Nodo m=nodi.search(cerca(d));
insertArco(n,m,peso);
}
public void insertArco(Nodo x,Nodo y)
{
insertArco(x,y,1);
}
public void insertArco(Nodo x,Nodo y,int peso)
{
matrice[getIndice(x)][getIndice(y)]=peso;
}
public Nodog cerca(Comparable c)
{
Nodo aux=nodi.getHead();
Nodog temp=null;
for(;aux!=null&&temp==null;aux=aux.getNext())
if((((Nodog)aux.getInfo()).info).compareTo(c)==0)
temp=(Nodog)aux.getInfo();
return temp;
}
public void deleteNodo(Comparable c)
{
Nodo n=nodi.search(cerca(c));
int rc=getIndice(n);
matrice=rimuovi(rc);
nodi.deleteKey(cerca(c));
}
public void deleteArco(Comparable c,Comparable d)
{
Nodo n=nodi.search(cerca(c));
Nodo m=nodi.search(cerca(d));
deleteArco(n,m);
}
public void deleteArco(Nodo x,Nodo y)
{
matrice[getIndice(x)][getIndice(y)]=0;
}
private int[][] rimuovi(int indice)
{
int[][] temp=new int[matrice.length-1][matrice.length-1];
for(int i=0;i<temp.length;i++)
for(int j=0;j<temp.length;j++)
if(i!=indice&&j!=indice)
temp[i][j]=matrice[i][j];
return temp;
}
private int[][] ingrandisciMatrice()
{
int[][] t=new int[matrice.length+1][matrice.length+1];
for(int i=0;i<matrice.length;i++)
for(int j=0;j<matrice.length;j++)
t[i][j]=matrice[i][j];
return t;
}
public int getNumArchiEntr(Comparable c)
{
return getNumArchiEntr(cerca(c));
}
public int getNumArchiUsc(Comparable c)
{
return getNumArchiUsc(cerca(c));
}
public int getNumArchiEntr(Nodog n)
{
int cont=0, i=getIndice(nodi.search(n));
for(int j=0;j<matrice.length;j++)
if(matrice[j][i]!=0)
cont++;
return cont;
}
public int getNumArchiUsc(Nodog n)
{
int cont=0, i=getIndice(nodi.search(n));
for(int j=0;j<matrice.length;j++)
if(matrice[i][j]!=0)
cont++;
return cont;
}
public String toString()
{
String s="Il grafo ha nodi: ";
Nodo aux=nodi.getHead();
for(;aux!=null;aux=aux.getNext())
s+=aux.getInfo()+"\t";
s+="\n e matrice di adiacenza:\n";
for(int i=0;i<matrice.length;i++)
{
for(int j=0;j<matrice.length;j++)
s+=matrice[i][j]+"\t";
s+="\n";
}
return s;
}
}

Code:
public class GrafoLA
{
protected int numArchi;;
protected LinkedList nodi;
public GrafoLA()
{
this(new LinkedList());
}
public GrafoLA(LinkedList l)
{
numArchi=0;
nodi=l;
}
public int getNumNodi()
{
int cont=0;
Nodo aux=nodi.getHead();
for(;aux!=null;aux=aux.getNext())
cont++;
return cont;
}
public int getNumArchi()
{
return numArchi;
}
public void insertNodo(Comparable c)
{
nodi.insertTail(new Nodogl(c));
}
public void insertArco(Comparable c,Comparable d)
{
Nodogl n=cerca(c);
Nodogl m=cerca(d);
insertArco(n,m);
}
public void insertArco(Nodogl x, Nodogl y)
{
if(x.isArco(y))
return;
else
{
x.lista.insertTail(y);
insertArco(y,x);
numArchi++;
}
}
public Nodogl cerca(Comparable c)
{
Nodo aux=nodi.getHead();
Nodogl temp=null;
for(;aux!=null&&temp==null;aux=aux.getNext())
if((((Nodogl)aux.getInfo()).info).compareTo(c)==0)
temp=(Nodogl)aux.getInfo();
return temp;
}
public void deleteNodo(Comparable c)
{
deleteNodo(cerca(c));
}
public void deleteNodo(Nodogl x)
{
nodi.deleteKey(x);
Nodo aux=nodi.getHead();
for(;aux!=null;aux=aux.getNext())
if(((Nodogl)aux.getInfo()).isArco(x))
deleteArco(aux.getInfo(),x);
}
public void deleteArco(Comparable c,Comparable d)
{
Nodogl n=cerca(c);
Nodogl m=cerca(d);
deleteArco(n,m);
}
public void deleteArco(Nodogl x,Nodogl y)
{
if(x.isArco(y))
{
x.lista.deleteKey(y);
deleteArco(y,x);
numArchi--;
}
}
public String toString()
{
String s="Il grafo ha nodi: ";
Nodo aux=nodi.getHead();
for(;aux!=null;aux=aux.getNext())
s+=aux.getInfo()+"\t";
s+="\n e i seguenti archi:\n";
for(aux=nodi.getHead();aux!=null;aux=aux.getNext())
{
Nodo t=((Nodogl)aux.getInfo()).lista.getHead();
for(;t!=null;t=t.getNext())
if(aux!=t)
s+=((Nodogl)aux.getInfo()).info+" <--> "+((Nodogl)t.getInfo()).info+"\n";
}
return s;

}
}

Code:
public class DigrafoLA
{
protected int numArchi;
protected LinkedList nodi;
public DigrafoLA()
{
this(new LinkedList());
}
public DigrafoLA(LinkedList l)
{
numArchi=0;
nodi=l;
}
public int getNumNodi()
{
int cont=0;
Nodo aux=nodi.getHead();
for(;aux!=null;aux=aux.getNext())
cont++;
return cont;
}
public int getNumArchi()
{
return numArchi;
}
public void insertNodo(Comparable c)
{
nodi.insertTail(new Nodogl(c));
}
public void insertArco(Comparable c,Comparable d)
{
Nodogl n=cerca(c);
Nodogl m=cerca(d);
insertArco(n,m);
}
public void insertArco(Nodogl x, Nodogl y)
{
if(x.isArco(y))
return;
else
{
x.lista.insertTail(y);
numArchi++;
}
}
public Nodogl cerca(Comparable c)
{
Nodo aux=nodi.getHead();
Nodogl temp=null;
for(;aux!=null&&temp==null;aux=aux.getNext())
if((((Nodogl)aux.getInfo()).info).compareTo(c)==0)
temp=(Nodogl)aux.getInfo();
return temp;
}
public void deleteNodo(Comparable c)
{
deleteNodo(cerca(c));
}
public void deleteNodo(Nodogl x)
{
nodi.deleteKey(x);
Nodo aux=nodi.getHead();
for(;aux!=null;aux=aux.getNext())
if(((Nodogl)aux.getInfo()).isArco(x))
deleteArco(aux.getInfo(),x);
}
public void deleteArco(Comparable c,Comparable d)
{
Nodogl n=cerca(c);
Nodogl m=cerca(d);
deleteArco(n,m);
}
public void deleteArco(Nodogl x,Nodogl y)
{
if(x.isArco(y))
{
x.lista.deleteKey(y);
numArchi--;
}
}
public int getNumArchiEntr(Comparable c)
{
return getNumArchiEntr(cerca(c));
}
public int getNumArchiUsc(Comparable c)
{
return getNumArchiUsc(cerca(c));
}
public int getNumArchiEntr(Nodogl n)
{
Nodo p=nodi.getHead();
int cont=0;
for(;p!=null;p=p.getNext())
{
Nodo q=((Nodogl)p.getInfo()).lista.getHead();
for(;q!=null;q=q.getNext())
if(q.getInfo()==n)
cont++;
}
return cont;
}
public int getNumArchiUsc(Nodogl n)
{
Nodo p=n.lista.getHead();
int cont=0;
for(;p!=null;p=p.getNext())
cont++;
return cont;
}
public String toString()
{
String s="Il grafo ha nodi: ";
Nodo aux=nodi.getHead();
for(;aux!=null;aux=aux.getNext())
s+=aux.getInfo()+"\t";
s+="\n e i seguenti archi:\n";
for(aux=nodi.getHead();aux!=null;aux=aux.getNext())
{
Nodo t=((Nodogl)aux.getInfo()).lista.getHead();
for(;t!=null;t=t.getNext())
if(aux!=t)
s+=((Nodogl)aux.getInfo()).info+" --> "+((Nodogl)t.getInfo()).info+"\n";
}
return s;

}
}
« Last Edit: 31-05-2009, 10:13:24 by Vivynz » Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #2 on: 30-05-2009, 11:34:32 »

pongo una domanda nuovamente a coloro che hanno già sostenuto l'esame di prog. 2;
nell'implementazione di un grafo, viene richiesto in modo specifico di scriverlo con liste o con matrice, oppure viene data libera scelta di implementazione?
Logged
france_88
Apprendista Forumista
**
Offline Offline

Posts: 119



« Reply #3 on: 30-05-2009, 23:25:27 »

viene richiesto in modo specifico
Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #4 on: 31-05-2009, 10:13:42 »

ho aggiornato il post sopra
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #5 on: 31-05-2009, 14:05:46 »

Ma la variabile "lista" sarebbe "LinkedList nodi" oppure  un altra variabile LinkedList che non hai implementato?
Logged
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #6 on: 31-05-2009, 15:26:08 »

Ragazzi ho implementato l'array degli archi presenti nel grafo in questa maniera , qualcuno mi saprebbe dire se è giusto?

Code:
public Arco[] archi()
{
int i=0;
int j=0;
int y=0:
boolean  P = false;
int indice = 0;
Arco [] elem  = new Arco[matrice.length];

for(i=0;i < matrice.length;i++)
{
for(j=0; j < matrice.length;j++;indice++)
{
P= false;
if(matrice[i][j] != null)
{

for(y=0; y < elem.length;y++)
{
if(elem[y] == matrice[i][j]) P=true;
}

if(P==false)
{
elem[indice] = matrice[i][j];
}
}
}
}
return elem;


}

P.S:HO implmentato questa istruzione su un grafo non orientato , ovvero senza freccette!

Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #7 on: 31-05-2009, 18:48:07 »

la variabile lista è una linkedlist che sta dentro la classe Nodogl
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #8 on: 01-06-2009, 10:48:59 »

qualcuno è riuscito ad impelementare i metodi "searchAdiacente" e "deleteKeyAdiacenza"?
 io non ho capito come si devono fare!
Logged
hax
Matricola
*
Offline Offline

Posts: 64


« Reply #9 on: 06-06-2009, 16:23:33 »

Code:
private int[][] rimuovi(int indice)
{
int[][] temp=new int[matrice.length-1][matrice.length-1];
for(int i=0;i<temp.length;i++)
for(int j=0;j<temp.length;j++)
if(i!=indice&&j!=indice)
temp[i][j]=matrice[i][j];
return temp;
}
se non ho capito male io dovrebbe esserci un errore nel metodo... gli indici di matrice non dovrebbero essere a parte? se li metti uguali a quelli di temp verrà saltato sia l'indice, sia l'ultima riga e colonna di matrice.
Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #10 on: 07-06-2009, 08:01:59 »

hai ragione non ci avevo fatto caso..ho modificato il metodo non so se c'era una soluzione migliore ma penso che non ci sia altro che considerare tutti i casi altrimenti si esce fuori dall'array...
Code:
private int[][] rimuovi(int indice)
{
int[][] temp=new int[matrice.length-1][matrice.length-1];
for(int i=0;i<matrice.length;i++)
for(int j=0;j<matrice.length;j++)
if(i!=indice&&j!=indice)
{
if(i<indice)
{
if(j<indice)
temp[i][j]=matrice[i][j];
if(j>indice)
temp[i][j-1]=matrice[i][j];
}
else
if(i>indice)
{
if(j<indice)
temp[i-1][j]=matrice[i][j];
if(j>indice)
temp[i-1][j-1]=matrice[i][j];
}
}
return temp;
}
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
hax
Matricola
*
Offline Offline

Posts: 64


« Reply #11 on: 07-06-2009, 10:13:34 »

potevi semplicemente usare un indice a parte per matrice tipo:
Code:
private int[][] rimuovi(int indice)
{
                int x=-1,y=-1;
int[][] temp=new int[matrice.length-1][matrice.length-1];
for(int i=0;i<temp.length;i++)
for(int j=0;j<temp.length;j++){
               if (++y>=matrice[x++].length) y=0;       //per evitare che si sfori
if(i!=indice&&j!=indice)
temp[i][j]=matrice[x][y];  }
return temp;
}
non l'ho provato, ma ad occhio dovrebbe funzionare...
EDIT: ho dimenticato che per saltare l'indice, x e y devono essere sempre incrementati, quindi ho fatto un'altra modifica.
« Last Edit: 07-06-2009, 10:28:33 by hax » Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #12 on: 07-06-2009, 10:37:58 »

onestamente non ho capito bene la logica..cmq l'ho provato ma va fuori dall'array..
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #13 on: 08-06-2009, 15:30:54 »

ragazzi scusatemi se rispondo adesso ma ho avuto da fare in questi due giorni tant'è vero che non ho potuto studiare.....c'è stato un ragazzo che mi ha chiesto come avevo fatto i grafi l'unica cosa da modificare dal file del professore e soltanto il metodo aggiungi arco e inserire il peso nel nodo della lista

1) per il metodo aggiungi nodo bisogna  cercare se nel grafo ci sono i nodi da inserire questo viene fatto con il metodo cerca implementato da vivynz qua sopra e inoltre dobbiamo stare attenti al peso perchè al momento dell'aggiunta bisogna passargli il peso in qualche modo.......

2)per inserire il peso basta andare a modificare il NodoLista e inserire un parametro peso......


Poi per il resto ho utilizzato i metodi scritti sulle slide del prof......in sostanza non ho fatto nulla di speciale.
Mi sono messo a fare esercizi e a poco a poco sono arrivato alla soluzione finale......

Spero che sia stato esaustivo se avete dubbi chiedete
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #14 on: 08-06-2009, 16:58:09 »

mhm allora...il mio metodo cerca non fa altro che restituire il nodo del grafo che ha come info il valore che prende come paramentro..non cerca se nel grafo ci sono i nodi da inserire..poi..come già detto il peso non è un parametro del nodo, ma dell'arco..un nodo può avere diversi archi e allora come peso quale dovresti mettere??
invece già da in un altro post avevo detto come aveva suggerito il prof di fare:

Quote
proprio ieri a lezione abbiamo visto che quando utilizziamo le liste, per memorizzare il peso dell'arco possiamo mettere nella lista di adiacenza:
delle coppie(nodo,peso)
degli archi(origine,destinazione,peso)
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Pages: [1] 2   Go Up
Print
Jump to: