Codice in C
Doveri scrivere un codice in C dove si considerano i criteri di scelta in base al grado di ingresso ed uscita dell'ultimo vertice inserito in una permutazione ed adottare 3 strategie:
1) se in-deg(v) e out-deg(v) sono entrambi minimali scegli vi.
2)se in-deg(v) è minimale scegli tra tutti i vertici v con in-deg(v) minimale quello con out-deg(v) minimale.
3)se out-deg(v) minimale scegli tra tutti i vertici v con out-deg(v)minimale quello con in-deg(v) minimale.
1) se in-deg(v) e out-deg(v) sono entrambi minimali scegli vi.
2)se in-deg(v) è minimale scegli tra tutti i vertici v con in-deg(v) minimale quello con out-deg(v) minimale.
3)se out-deg(v) minimale scegli tra tutti i vertici v con out-deg(v)minimale quello con in-deg(v) minimale.
Risposte
Il problema non lo trovo molto chiaro, dovresti esplicitare meglio i vari oggetti con cui hai a che fare. Inoltre dovresti esplicitare meglio qual'è la tua domanda.
Ho scritto un codice che effettua delle permutazioni su un grafo , devo modificarlo la generazione considerando solo i prossimi vertici adiacenti , se non sbaglio tipo la matrice di incidenza.Come prima cosa, poi cerco di spiegarti meglio il resto
/*
VARIABILI GLOBALI:
n
nChr = numero di permutazioni alcolate (inizialmente 0)
Chr = permutazione
Chr1 = permutazione inversa (Chr1[i] = n equivale ad elemento di permutazione non definito
(se Chr[i]=j, allora Chr1[i]=j)
Succ = risposta della procedura genTPerm (inizialmente 1)
*/
int Chr[100]; /* vettore soluzione (permutazione) */
int Chr1[100]; /* soluzione inversa */
int nChr=0; /* numero soluzioni costruite dalla procedura esaustiva */
int Succ=1; /* flag che indica il successo della procedura esaustiva */
int n=3; /* numero vertici digrafi */
/* procedura di inizializzazione dei vettori soluzione (Chr[] e Chr1[]) */
void initChr()
{
int i=0;
for(i=0;i<n;i++)
{
Chr[i]=n;
Chr1[i]=n;
}
}
/* procedura di stampa di Chr[] */
void stampaVett()
{
int i=0;
for(i=0;i<n;i++)
printf ("%d ",Chr[i]);
printf("\n");
}
/* procedura esaustiva di calcolo soluzioni */
void genTPerm(int k)
{
int i=0;
if(k>(n-1))
{
stampaVett();
/* verifica se la soluzione trovata è un ciclo: se si succ=1 e termina genTPerm */
nChr++;
if(nChr>n)
{
Succ=0;
return ;
}
}
else
for(i=0;i<n;i++)
{if(Chr1[i]==n)
{Chr[k]=i;
Chr1[i]=k;
genTPerm(k+1);
Chr1[i]=n;
Chr[k]=n;
}
}
}
/* programma principale */
int main(void)
{
int i=0, k=0;
/* inizializza variabili, vettori e strutture dati */
nChr = 0;
initChr(); /* procedura che inizializza Chr e Chr1 */
genTPerm(0); /* procedura esaustiva per il calcolo di soluzioni */
}
apatriarca cosa mi consigli?
Ma che cosa intendi con minimali? Rispetto all'intero grafo?
se l'in-degrees e l'out-degrees sono entrambi minimali scegli Vi.in base al grado di ingresso e uscita dell'ultimo vertice inserito nella permutazione.Non me l ha scrittoil prof ma penso che sia riferito al grafo.Comunque devo modificare anche la generazione della permutazione (genTperm()) in modo da considerare solo i prossimi vertici adiacenti.
é possibile modificare il codice sottostante in modo che se Indegree(v) e Outdegree(v) sono entrambi minimali scegli Vi(1 strategia).
invece se Indegree(v)è minimale scegli tra tutti vertici V con Indegree(v) minimale quello con Outdegree(v) minimale(2 Strategia).
oppure se invece se Outdegree(v) è minimale scegli tra tutti vertici V con Outdegree(v) minimale quello con Indegree(v) minimale(3 strategia).
invece se Indegree(v)è minimale scegli tra tutti vertici V con Indegree(v) minimale quello con Outdegree(v) minimale(2 Strategia).
oppure se invece se Outdegree(v) è minimale scegli tra tutti vertici V con Outdegree(v) minimale quello con Indegree(v) minimale(3 strategia).
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
/* Definisco un nuovo tipo per le matrici.. */
#define N 10
typedef int matrice[N][N];
void degrees();
void genera_matrice(matrice m, size_t n, double p) {
size_t i = 0, j = 0;
assert(n <= N);
srand((unsigned) time(NULL));
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) { m[i][j] = rand() < p * RAND_MAX ? 1 : 0; }
}
}
void stampa_matrice(matrice m, size_t n) {
size_t i = 0, j = 0;
assert(n <= N);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) { printf("%d ", m[i][j]); }
printf("\n");
}
}
void degrees(matrice m, size_t n, int *indegrees, int *outdegrees)
{
size_t i = 0, j = 0;
/* inizializza arrays.. */
for (i = 0; i < n; ++i) { indegrees[i] = outdegrees[i] = 0; }
/* calcola gradi.. */
for (i = 0; i < n; ++i) {
for(j = 0; j < n; ++j) {
/* ricordandosi che m[i][j] è 0 o 1 si può semplicemente usare la somma ed evitare un inutile selezione. */
indegrees[j] += m[i][j];
outdegrees[i] += m[i][j];
}
}
}
int main(void)
{ int i;
double p = 0.5;
size_t n = 5;
matrice m;
int indegrees[N], outdegrees[N];
genera_matrice(m, n, p);
stampa_matrice(m, n);
degrees(m, n, indegrees, outdegrees);
for ( i = 0; i < n; ++i) {
printf("\nvertice : %d\tIndegree :%d\tOut degree:%d\tDegree Totale:%d", i,indegrees[i], outdegrees[i], indegrees[i] + outdegrees[i]);
}
return 0;
}
apatriarca cosa ne pensi? riesci ad aiutarmi
Il problema è che continua a non essermi del tutto chiaro cosa tu stia cercando di fare. Che cosa sono v e vi? Che cosa significa scegliere un vertice? Per farne che cosa? In cosa consiste esattamente la condizione di minimalità? È rispetto a tutto il grafo? Per cui vuoi sapere se il vertice preso in considerazione è quello che ha meno archi entranti o uscenti tra tutti gli altri vertici?
Apatriarca cerco di descriverti passo passo quello che mi ha detto il prof.Nel programma sugli in/out-degree data una scelta di vertici al primo livello, si deve fare un vettore di scelte successive con tutti i possibili ammissibili oppure tutti gli ammissibili adiacenti. es data la tabella
|vertici|in-deg|out-deg|
| 1 |1 |2 |
|2 |2 |2 |
|3 |2 |2 |
|4 |1 |2 |
|5 |2 |3 |
bisogna scegliere nel caso simmetrico se questi due gradi coincidono l'idea e quella di scegliere quel vertice che ha il grado minore.Se la scelta adiacente in base all'out-degree tra tutti gli adiacenti scegliere quello con minore out.degree.nel caso della tabella scarto il vertice 5,se si sceglie in base a l'out-degree minimale scelgo i vertici 1,2,3,4; se scelgo in base al in-degree e out-degree minimale il tutto si riduce alla scelta dei vertici 1 e 4
Codice da modificare:
|vertici|in-deg|out-deg|
| 1 |1 |2 |
|2 |2 |2 |
|3 |2 |2 |
|4 |1 |2 |
|5 |2 |3 |
bisogna scegliere nel caso simmetrico se questi due gradi coincidono l'idea e quella di scegliere quel vertice che ha il grado minore.Se la scelta adiacente in base all'out-degree tra tutti gli adiacenti scegliere quello con minore out.degree.nel caso della tabella scarto il vertice 5,se si sceglie in base a l'out-degree minimale scelgo i vertici 1,2,3,4; se scelgo in base al in-degree e out-degree minimale il tutto si riduce alla scelta dei vertici 1 e 4
Codice da modificare:
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
/* Definisco un nuovo tipo per le matrici.. */
#define N 10
typedef int matrice[N][N];
void degrees();
void genera_matrice(matrice m, size_t n, double p) {
size_t i = 0, j = 0;
assert(n <= N);
srand((unsigned) time(NULL));
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) { m[i][j] = rand() < p * RAND_MAX ? 1 : 0; }
}
}
void stampa_matrice(matrice m, size_t n) {
size_t i = 0, j = 0;
assert(n <= N);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) { printf("%d ", m[i][j]); }
printf("\n");
}
}
void degrees(matrice m, size_t n, int *indegrees, int *outdegrees)
{
size_t i = 0, j = 0;
/* inizializza arrays.. */
for (i = 0; i < n; ++i) { indegrees[i] = outdegrees[i] = 0; }
/* calcola gradi.. */
for (i = 0; i < n; ++i) {
for(j = 0; j < n; ++j) {
/* ricordandosi che m[i][j] è 0 o 1 si può semplicemente usare la somma ed evitare un inutile selezione. */
indegrees[j] += m[i][j];
outdegrees[i] += m[i][j];
}
}
}
int main(void)
{ int i;
double p = 0.5;
size_t n = 5;
matrice m;
int indegrees[N], outdegrees[N];
genera_matrice(m, n, p);
stampa_matrice(m, n);
degrees(m, n, indegrees, outdegrees);
for ( i = 0; i < n; ++i) {
printf("\nvertice : %d\tIndegree :%d\tOut degree:%d\tDegree Totale:%d", i,indegrees[i], outdegrees[i], indegrees[i] + outdegrees[i]);
}
return 0;
}
apatriarca ti è più chairo cosi??
In realtà no.. Proviamo a vedere un esempio. Supponi di aver generato il seguente grafo di 4 nodi:
\[ \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix} \]
Cosa dovrebbe fare a sto punto il tuo programma?
\[ \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix} \]
Cosa dovrebbe fare a sto punto il tuo programma?
scegliere tra tutti i vertici adiacenti quello con il minore out-degree. poi se si riesce a perfezionarlo scegliere il vertice che presenta sia l'in-degree e out degree minore rispetto gli atri vertici. questo è quello che mi hanno spiegato.aspetto un tuo aiuto,grazie.
Ti ho allegato un esempio.Utilizzando la matrice dell'esempio il programma dovrebbe scegliere il minimo out degree,quindi il vertice 0 con out-degree 1, ed il vertice 2 con out-degree 1.
Passo 2) nel caso riusciamo a tenere in considerazione sia l'in/out-degree minore il tutto si riduce al vertice 2 perchè ha in-degree=1 ed out-degree=1.
come Passo 3) devo modificare la procedura sulle permutazioni andando a considerare soltanto i vertici adiacenti
Passo 2) nel caso riusciamo a tenere in considerazione sia l'in/out-degree minore il tutto si riduce al vertice 2 perchè ha in-degree=1 ed out-degree=1.
come Passo 3) devo modificare la procedura sulle permutazioni andando a considerare soltanto i vertici adiacenti
/*
VARIABILI GLOBALI:
n
nChr = numero di permutazioni alcolate (inizialmente 0)
Chr = permutazione
Chr1 = permutazione inversa (Chr1[i] = n equivale ad elemento di permutazione non definito
(se Chr[i]=j, allora Chr1[i]=j)
Succ = risposta della procedura genTPerm (inizialmente 1)
*/
int Chr[100]; /* vettore soluzione (permutazione) */
int Chr1[100]; /* soluzione inversa */
int nChr=0; /* numero soluzioni costruite dalla procedura esaustiva */
int Succ=1; /* flag che indica il successo della procedura esaustiva */
int n=3; /* numero vertici digrafi */
/* procedura di inizializzazione dei vettori soluzione (Chr[] e Chr1[]) */
void initChr()
{
int i=0;
for(i=0;i<n;i++)
{
Chr[i]=n;
Chr1[i]=n;
}
}
/* procedura di stampa di Chr[] */
void stampaVett()
{
int i=0;
for(i=0;i<n;i++)
printf ("%d ",Chr[i]);
printf("\n");
}
/* procedura esaustiva di calcolo soluzioni */
/* metto 0 nella prima posizione e generola permutazione su 1 2,
poi metto 1 nella prima posizione e genero la permutazione su 0 2,
ed infine metto 2 nella prima posizione e genero la permutazione su 0 1 , */
void genTPerm(int k)
{
int i=0;
if(k>(n-1))
{
stampaVett();
/* verifica se la soluzione trovata è un ciclo: se si succ=1 e termina genTPerm */
nChr++;
if(nChr>n)
{
Succ=0;
return ;
}
}
else
for(i=0;i<n;i++)
{if(Chr1[i]==n)
{Chr[k]=i;
Chr1[i]=k;
genTPerm(k+1);
Chr1[i]=n;
Chr[k]=n;
}
}
}
/* programma principale */
int main(void)
{
int i=0, k=0;
/* inizializza variabili, vettori e strutture dati */
nChr = 0;
initChr(); /* procedura che inizializza Chr e Chr1 */
genTPerm(0); /* procedura esaustiva per il calcolo di soluzioni */
}
Non ho capito se ti ha caricato l' immagine ti scrivo la matrice:
0 0 0 0 1
1 1 0 1 1
0 1 0 0 0
1 0 0 1 1
0 1 1 0 0
vertice0: indegree=2; Outdegree=1;
vertice1: indegree=3; Outdegree=4;
vertice2: indegree=1; Outdegree=1;
vertice3: indegree=2; Outdegree=3;
vertice4: indegree=3; Outdegree=2;
0 0 0 0 1
1 1 0 1 1
0 1 0 0 0
1 0 0 1 1
0 1 1 0 0
vertice0: indegree=2; Outdegree=1;
vertice1: indegree=3; Outdegree=4;
vertice2: indegree=1; Outdegree=1;
vertice3: indegree=2; Outdegree=3;
vertice4: indegree=3; Outdegree=2;
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo