Colouring

di
gabry
il
10 risposte
G
gabry
Pochi posts
Iscritto da
apr, 2008
Messaggi:
6

Colouring

Ciao a tutti!!Ho un enorme problema. Per il mio ultimo esame devo scrivere una procedura in java per cercare la colorazione minima di un grafo ma non ho assolutamente idea di come si faccia!Ho sostenuto l'esame di programmazione in java circa 4 anni fa e ora ricordo ben poco.Spero che qualcuno mi possa aiutare(Vi prego sono disperata).
Grazie mille!!!

10 Risposte

  • K
    KeyroAscendent
    Pochi posts
    Iscritto da
    mar, 2008
    Messaggi:
    15

    Re: Colouring

    gabry ha scritto:

    Ciao a tutti!!Ho un enorme problema. Per il mio ultimo esame devo scrivere una procedura in java per cercare la colorazione minima di un grafo ma non ho assolutamente idea di come si faccia!Ho sostenuto l'esame di programmazione in java circa 4 anni fa e ora ricordo ben poco.Spero che qualcuno mi possa aiutare(Vi prego sono disperata).
    Grazie mille!!!
    Mmm io ti posso aiutare ma conosco poco dei grafi personalmente, cosa si intende per colorazione minima?
  • G
    gabry
    Pochi posts
    Iscritto da
    apr, 2008
    Messaggi:
    6

    Re: Colouring

    Per colorazione minima si intende il minimo numero di colori necessario per colorare un grafo in modo che due nodi adiacenti(collegati tra loro da un arco)non abbiano lo stesso colore.Mi rendo conto che per chi non conosce la teoria dei grafi è un pò difficile comunque grazie lo stesso.
  • K
    KeyroAscendent
    Pochi posts
    Iscritto da
    mar, 2008
    Messaggi:
    15

    Re: Colouring

    gabry ha scritto:

    Per colorazione minima si intende il minimo numero di colori necessario per colorare un grafo in modo che due nodi adiacenti(collegati tra loro da un arco)non abbiano lo stesso colore.Mi rendo conto che per chi non conosce la teoria dei grafi è un pò difficile comunque grazie lo stesso.
    Bene bene ho capito, e la complessita` dell'algoritmo e` richiesta? Cioe` devi farlo nel modo piu` efficiente possibile oppure va bene una cosa media?
  • G
    gabry
    Pochi posts
    Iscritto da
    apr, 2008
    Messaggi:
    6

    Re: Colouring

    La complessità non è richiesta, quello che mi chiede il prof è la procedura per la colorazione minima di un grafo e poi un'applicazione della procedura su un grafo. Io avevo pensato di dare come input una matrice di adiacenze, cioé una matrice che assume valore 1 se due nodi sono adiacenti e zero altrimenti, ma non so se può andar bene.
  • K
    KeyroAscendent
    Pochi posts
    Iscritto da
    mar, 2008
    Messaggi:
    15

    Re: Colouring

    gabry ha scritto:

    La complessità non è richiesta, quello che mi chiede il prof è la procedura per la colorazione minima di un grafo e poi un'applicazione della procedura su un grafo. Io avevo pensato di dare come input una matrice di adiacenze, cioé una matrice che assume valore 1 se due nodi sono adiacenti e zero altrimenti, ma non so se può andar bene.
    Generalmente quando si parla di grafi si intende l'utilizzo di strutture di dati come le liste (o catene per altri). Infatti potresti dare ad ogni nodo del grafo un'informazione ridondante che indica quanti rami partono da lui. Cosi` semplificheresti il lavoro. Le liste sono molto piu` veloci per quanto riguarda la ricerca delle informazioni, basti vedere l'algoritmo sugli alberi binari. (Il tutto chiede che tu sappia la ricorsione).
  • G
    gabry
    Pochi posts
    Iscritto da
    apr, 2008
    Messaggi:
    6

    Re: Colouring

    Innanzitutto grazie per il tuo interessamento,sei molto gentile.In teoria dovrei saperlo ma come ho scritto nel messaggio iniziale è molto che non uso Java e non ho molto tempo per andare a rivedere tutta la teoria che sta dietro questo linguaggio di programmazione a oggetti e comunque quando ho sostenuto l'esame non ci veniva chiesto di fare questo genere di cose.
  • K
    KeyroAscendent
    Pochi posts
    Iscritto da
    mar, 2008
    Messaggi:
    15

    Re: Colouring

    gabry ha scritto:

    Innanzitutto grazie per il tuo interessamento,sei molto gentile.In teoria dovrei saperlo ma come ho scritto nel messaggio iniziale è molto che non uso Java e non ho molto tempo per andare a rivedere tutta la teoria che sta dietro questo linguaggio di programmazione a oggetti e comunque quando ho sostenuto l'esame non ci veniva chiesto di fare questo genere di cose.
    Beh, i problemi che generalmente vengono posti per i grafi, girano sempre intorno sul fatto della ricorsione. Nelle librerie del java, in base alle mie conoscenze, ci sono gia` delle classi pronte per utilizzare Liste (java.util.LinkedList) se non mi sbaglio eh. Per cui io le riprenderei in mano, poi, da qualche parte nel modo piu` gratuito, c'e` sicuramente l'algoritmo della ricerca binaria (per quanto riguarda gli alberi binari, quindi grafi) e l'algoritmo, a rigor di logica che cerchi tu, e` molto simile. Se riesco faccio un salto dal mio prof e posso domandargli visto che insegna algoritmi all'universita`!
  • G
    gabry
    Pochi posts
    Iscritto da
    apr, 2008
    Messaggi:
    6

    Re: Colouring

    Grazie per i consigli, adesso farò un pò di ricerche.Che università frequenti?
  • K
    KeyroAscendent
    Pochi posts
    Iscritto da
    mar, 2008
    Messaggi:
    15

    Re: Colouring

    gabry ha scritto:

    Grazie per i consigli, adesso farò un pò di ricerche.Che università frequenti?
    Non ancora universita`, sono alle scuole superiori per periti informatici. Me ne intendo di programmazione, conosco vari linguaggi. C, C++, Java, C#, Ruby, Assembly bla bla..
  • G
    gabry
    Pochi posts
    Iscritto da
    apr, 2008
    Messaggi:
    6

    Re: Colouring

    Ciao a tutti, sto facendo dei passi avanti con il mio problema dalla colorazione dei grafi. Una mia amica mi ha passato il codice che lei ha usato per l'esplorazione ed atichettatura di un grafo, che è il seguente
    class VERTICE
    import java.awt.*;
    ////////////////////////////////////////////////////////////////
    class Queue
    {
    private final int SIZE = 20;
    private int[] queArray;
    private int front;
    private int rear;

    public Queue() // constructor
    {
    queArray = new int[SIZE];
    front = 0;
    rear = -1;
    }
    public void insert(int j) // put item at rear of queue
    {
    if(rear == SIZE-1)
    rear = -1;
    queArray[++rear] = j;
    }
    public int remove() // take item from front of queue
    {
    int temp = queArray[front++];
    if(front == SIZE)
    front = 0;
    return temp;
    }
    public boolean isEmpty() // true if queue is empty
    {
    return ( rear+1==front || (front+SIZE-1==rear) );
    }
    } // end class Queue
    ////////////////////////////////////////////////////////////////
    class Vertex
    {
    public char label; // label (e.g. 'A')
    public boolean wasVisited;
    // -------------------------------------------------------------
    public Vertex(char lab) // constructor
    {
    label = lab;
    wasVisited = false;
    }
    // -------------------------------------------------------------
    } // end class Vertex
    ////////////////////////////////////////////////////////////////
    class Graph
    {
    private final int MAX_VERTS = 20;
    private Vertex vertexList[]; // list of vertices
    private int adjMat[][]; // adjacency matrix
    private int nVerts; // current number of vertices
    private Vertex colorList[];
    private Vertex colorazione[];
    private Queue theQueue;

    // ------------------
    public Graph() // constructor
    {
    vertexList = new Vertex[MAX_VERTS]; // adjacency matrix
    adjMat = new int[MAX_VERTS][MAX_VERTS];
    nVerts = 0;
    for(int j=0; j<MAX_VERTS; j++) // set adjacency
    for(int k=0; k<MAX_VERTS; k++) // matrix to 0
    adjMat[j][k] = 0;
    theQueue = new Queue();

    } // end constructor
    // -------------------------------------------------------------
    public void addVertex(char lab)
    {
    vertexList[nVerts++] = new Vertex(lab);
    }
    // -------------------------------------------------------------
    public void addEdge(int start, int end)
    {
    adjMat[start][end] = 1;
    adjMat[end][start] = 1;
    }
    // -------------------------------------------------------------
    public void displayVertex(int v)
    {
    System.out.print(vertexList[v].label);
    }

    questa parte io la posso utilizzare perché è la stessa, quello che devo cambiare è il codice seguente:

    public void bfs() // breadth-first search
    {
    colorList = new Vertex[MAX_VERTS];
    colorazione = new Vertex [MAX_VERTS]; // begin at vertex 0
    vertexList[0].wasVisited = true; // mark it
    colorazione[0]=colorList[0];
    displayVertex(0); // display it
    theQueue.insert(0); // insert at tail
    int v2;

    while( !theQueue.isEmpty() ) // until queue empty,
    {
    int v1 = theQueue.remove(); // remove vertex at head
    // until it has no unvisited neighbors
    while( (v2=getAdjUnvisitedVertex(v1)) != -1 )
    { // get one,
    vertexList[v2].wasVisited = true; // mark it
    displayVertex(v2); // display it
    theQueue.insert(v2); // insert it
    } // end while
    } // end while(queue not empty)

    // queue is empty, so we're done
    for(int j=0; j<nVerts; j++) // reset flags
    vertexList[j].wasVisited = false;
    }
    // end bfs()
    // -------------------------------------------------------------
    // returns an unvisited vertex adj to v
    public int getAdjUnvisitedVertex(int v)
    {
    for(int j=0; j<nVerts; j++)
    if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
    return j;
    return -1;
    } // end getAdjUnvisitedVert()


    public int getAdjVertexSS(int v)
    {
    for(int j=0; j<nVerts; j++)
    if(adjMat[v][j]==0)
    return j;
    return -1;
    } // end getAdjUnvisitedVert()

    // -------------------------------------------------------------
    } // end class Graph

    Lei in questo caso esplora i vertici e li etichetta, io invece una volta esplorati li devo colorare con colori diversi in modo che due nodi adiacenti,cioé quando la adjMat ha valore 1, non abbiano lo stesso colore. Quindi come output dovrei avere le etichette dei vertici con il relativo colore e in teoria questa dovrebbe darmi la colorazione minima. Spero che ci sia qualcuno che mi sappia suggerire il codice da usare. Grazie a tutti!!
Devi accedere o registrarti per scrivere nel forum
10 risposte