Programmino in C

[mikael2]

devo scrivere un programmino in C che genera un grafo p-casuale e ne enumera i vertici ricorsivamente al fine
di trovare cicli di lunghezza massima. Come devo fare ?? dove posso prendere dei spunti??

[apatriarca]

Che cosa intendi con grafo \(p\)-casuale? Un grafo casuale con \(n\) nodi in cui la probabilità di ogni nodo è \(p\)? Oppure un grafo casuale con \(n\) nodi e \(p\) archi? Visto l'uso della lettera \(p\) immagino sia il primo caso, ma è meglio averne la certezza. Il grafo come deve essere? Deve essere orientato? Può contenere self-loops?

Nel seguente paper trovi diversi algoritmi per farlo: http://www.edbt.org/Proceedings/2011-Uppsala/papers/edbt/a30-nobari.pdf. È decisamente più leggibile del paper che stai cercando di capire e comprendere.. Su questo credo di poterti dare una mano se ti serve..

[mikael2]

grazie, ti faccio sapere appena mi risponde il prof con più precisione

[mikael2]

p casuale orientato, dove p è la probabilita' di un arco.

[apatriarca]

Credo che sia esattamente il caso preso in considerazione dall'articolo che ti ho postato in precedenza.. Potresti partire dall'algoritmo naive che viene descritto..

[mikael2]

Come faccio per l'implementazione in C ??come incomincio??

[apatriarca]

In cosa incontri problemi? Direi che il primo pseudocodice "Algorithm 1" a pagina due di quell'articolo è abbastanza immediato da implementare partendo dalla falsariga del codice che avevi postato nell'altra discussione..

[mikael2]

non capisco dove modificare partendo dalla falsa riga di quello che ho, e comunque mi devo ritrovare con grafo p-casuale e ne enumera i vertici ricorsivamente al fine di trovare cicli di lunghezza massima.

[apatriarca]

Bhe, invece di leggere il tuo grafo dal file, iteri su tutte le coppie \((u, v)\) di nodi. Ad ogni iterazione, scegli un numero casuale e se questo è minore di p allora aggiungi l'arco \( u \to v \) alle liste di adiacenze di \(u\) e \(v\). Direi che per iniziare puoi provare ad implementarlo in questo modo.. La parte in cui si cerca il ciclo di lunghezza massima lo vediamo dopo direi..

[mikael2]

va bene cosi?? però come lo inserisci nel contesto di quel programmino ??

/*
 *  randomGraph(pG, n, p)
 *
 *  Costruisce un grafo non orientato random con n vertici; ogni spigolo (u,v)
 *  esiste con probabilita' 0 <= p <= 1.
 */

int randomGraph(grafo *pG, int n, float p) {
  int i, j;

  srand((unsigned) time(NULL));
  pG->n = n;
  pG->V = malloc((n+1)*sizeof(elementoLista *));
  for (i=1; i<=n; i++)
    pG->V[i] = NULL;
  for (i=1; i<n; i++) {
    for (j=i+1; j<=n; j++) {
      if ((float)(rand() % 100)/100.0 < p) {
        addEdge(pG, i, j);
        addEdge(pG, j, i);
      }
    }
  }
  return(n);
}

[apatriarca]

Ma solo l'arco in una delle due direzione va inserito nel grafo.. Quello che intendevo sopra è che devi inserire l'arco che parte da u e finisce in v come uscente per l'arco u e entrante per l'arco v. Ma se memorizzi solo quelli uscenti allora devi solo inserire v come nodo raggiungibile da u. Per quanto riguarda la condizione (float)(rand() % 100)/100.0 < p, non generi una distribuzione uniforme. La ragione è da ricercarsi nel fatto che quasi sicuramente, 100 non divide RAND_MAX. Una versione migliore è probabilmente rand() < p * RAND_MAX e conviene usare i double rispetto ai float*.

* Di fatto i double dovrebbero essere considerati il tipo a virgola mobile di default.. Ci sono ragioni per usare numeri float, ma il più delle volte i double sono semplicemente superiori.

[mikael2]

non ho capito però praticamente come devo scrivere il pezzo di codice, me lo potresti linkare come va fatto con precisione

[mikael2]

comunque con precisione il prof vuole la generazione p-casuale di grafi direzionati dove n=numero vertici attraverso matrice di adiacenza. inizializzare a zero n che è una variabile globale, poi :
for(i=0...n-1)
for(j=0...n-1)
if(i != j)
random(P)
A [j]=1;

dove P=la probabilità che 2 vertici sono adiacenti.questa è una procedura che serve a dimostrare come è fatta G la matrice di adicenza.

Come si fa in C????

[apatriarca]

Ma con le matrici di adiacenza è ancora più semplice.. Devi crearti la matrice \(N \times N\) e quindi iterare su tutti gli elementi. A questo punto generi il tuo numero casuale e se è minore di \(p\) scrivi uno nella matrice, altrimenti zero. Ma in linguaggi come matlab sarebbe semplicissimo, perché usi il C?

[mikael2]

perchè cosi vuole il prof. dove posso vedere qualche esempio??

[apatriarca]

Bhe, puoi scrivere qualcosa del genere:

void genera_matrice(int *matrice, size_t n, double p)
{
    srand(/*.. inizializza srand come preferisci .. */)
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            matrice[i*n + j] = rand() < RAND_MAX*p ? 1 : 0;
        }
    }
}

EDIT: l'ho scritto sul momento e non l'ho testato..

[mikael2]

non mi funziona cosa devo mettere con precisione?'il C non lo conosco bene scusami

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define N 6


int matrice[N] [N];

void genera_matrice(int *matrice, size_t n, double p)
{
    srand((unsigned) n=4))
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            matrice[i*n + j] = rand() < RAND_MAX*p ? 1 : 0;
        }
    }
}




int main()
{
    int i,j;
    int matrice[N] [N];
	double p;
}
 

[apatriarca]

Pensavo lo conoscessi meglio il C visto il codice che avevi scritto nell'altro post.. Devi scrivere qualcosa come il sequente (sempre non testato)..

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

void genera_matrice(int *matrice, size_t n, double p)
{
    int i = 0, j = 0;

    srand((unsigned)time(NULL));
    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j) {
            matrice[i*n + j] = rand() < RAND_MAX*p ? 1 : 0;
        }
    }
}

int main()
{
    size_t n = 10; /* numero di nodi.. */
    double p = 0.3; /* probabilità archi.. */    
    int *matrice = calloc(10*10, sizeof(int)); /* alloco matrice di adiacenza */
    int i = 0, j = 0;    

    genera_matrice(matrice, n, p);
    
    /* stampo matrice.. */
    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j) {
            printf("%u ", matrice[i*n + j]);
        }
        puts("");
    }
}

[mikael2]

grazie mille, appena controllo come va ti faccio sapere

[mikael2]

funziona, mi fa l'eseguibile però quando lo vado ad aprire non si apre si chiude automaticamente.Da cosa dipende??
questo è il codice:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

void genera_matrice(int *matrice, size_t n, double p)
{
    int i = 0, j = 0;

    srand((unsigned)time(NULL));
    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j) {
            matrice[i*n + j] = rand() < RAND_MAX*p ? 1 : 0;
        }
    }
}

int main()
{
    size_t n = 10; /* numero di nodi.. */
    double p = 0.3; /* probabilità archi.. */    
    int *matrice = calloc(10*10, sizeof(int)); /* alloco matrice di adiacenza */
    int i = 0, j = 0;    

    genera_matrice(matrice, n, p);
    
    /* stampo matrice.. */
     printf("La matrice e':\n");
    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j) {
            printf("%u ", matrice[i*n + j]);
        }
        printf("\n");
    }
return(0);
}

[apatriarca]

Lanciano da linea di comando. Premi Shift+tasto destro nella cartella dove c'è l'eseguibile, quindi premi su qualcosa del tipo "Apri finestra di comando qui" (ho Windows in inglese e non so quale sia la traduzione italiana). A questo punto scrivi il nome dell'eseguibile e premi invio.. stampa qualcosa?