[C] : Selezionare un vertice di un grafo da collegare casualmente ad un altro

[bad.alex]

Ciao ragazzi.
Ho il seguente problema: sto provando a creare un grafo diretto in C, in cui un vertice scelto dall'utente possa essere collegato casualmente ad un altro vertice (dovrei anche aggiungere con una certa probabilità, ma un passo per volta).
Il codice che ho scritto è il seguente:

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

#define VOL 20

/* Adjacency matrix */

int V, E, visited[VOL], graph[VOL][VOL];
void dfs(int i)
{
    int j;
    visited[i]=1;
    printf("%d",i+1);
    for(j=0;j<V;j++)
    {
        if(graph[i][j]==1&&visited[j]==0)
            dfs(j);
    }
}

int main()
{
    int i, j, vertex1, vertex2;
    int i_trad;
    
    printf("Directed graph\n");
    
    printf("Please, enter the number of vertices:");
    scanf("%d", &V);
    printf("Please, enter the number of edges:");
    scanf("%d", &E);
   
    for(i=0;i<V;i++)
    {
        for(j=0;j<V;j++)
            graph[i][j]=0;
    }
    
    
    /* Creating edges */
    
    for(i=0;i<E;i++)
    {
        printf("Please, select the edges (format: vertex1 vertex2):");
        scanf("%d %d", &vertex1,&vertex2);
        graph[vertex1-1][vertex2-1]=1;
    }
   
    for(i=0;i<V;i++)
    {
        for(j=0;j<V;j++)
        printf("%d",graph[i][j]);
    printf("\n");
        
    
    return 0;
}

Come potete vedere, non sono riuscito a selezionare un vertice! (per quanto assurdo possa sembrare )
Spero possiate aiutarmi con questa parte.
Vi ringrazio.

p.s. se dovessero esserci errori al codice attuale, vi sarei grato se poteste segnalarmeli. Sembra funzionare ad ogni modo.

[apatriarca]

Che cosa intendi dire con selezionare un vertice? Tutto quello che vedo nel tuo codice è un tentativo di inizializzare la matrice di adiacenza di un grafo a partire dall'input dell'utente seguito dalla visualizzazione di tale matrice. Ad una occhiata veloce mi sembra abbastanza corretto, ma non vedo la parentesi graffa che chiude il ciclo esterno per la visualizzazione della matrice.

[bad.alex]

Si, l'ho dimenticata nel ricopiarla. Scusa. Praticamente, ciò che dovrei fare è creare un grafo che sia diretto e connesso, in cui seleziono un vertice (che fisso, ad esempio digitando j=3) e collego casualmente questo ad un altro nuovo vertice.
Al momento il codice funziona per quanto concerne la parte di creazione della matrice delle adiacenze, in cui inserisco da tastiera sia il numero di vertici sia il numero di collegamenti con gli altri vertici (sempre inseriti da tastiera). Questo, però, dovrebbe avvenire casualmente, una volta scelto un vertice
Spero tu possa aiutarmi. Ti ringrazio

[bad.alex]

Sto provando a scrivere questa parte di programma, tuttavia ho problemi con la funzione rand().

int main()
{
    int i, j, graph[VOL][VOL];
    int  value, prob;
    
    srand(unsigned(time(NULL)));
    
    printf("\n Enter a specific vertex?");
    scanf("%d", &j);
    
    for(i=0;i<VOL;i++){
        if(i!=j)
        {
            graph[i][j]=1;  //Creo matrice delle adiacenze
            vicino[i]=j;
            value=;
            if(value>=prob){
                graph[i][j]=0;
                j=;
                graph[i][j];
                vicino[i]=j;
            }
        }
  return 0;

  }

Devo ancora inizializzare il valore di prob (probabilità, che si potrebbe fissare a 1, ad esempio).
Dove ho lasciato vuoto, dovrei utilizzare la famosa funzione rand().
Tuttavia, dai dettagli che ho (tenendo presente che DIM l'ho inizializzata nella parte di codice pubblicata all'inizio), in quella parte dovrei scrivere l'equivalente al seguente codice in Fortran, dove viene utilizzata la funzione ran2:

j=ran2(&idum);
value= ran2(&idum)*DIM;

Potreste dirmi come riscriverlo in C? Grazie mille.

[apatriarca]

Non conosco la funzione ran2 di fortran per cui non mi è chiaro che cosa quel codice stia facendo. Potresti spiegarlo a parole? Nel codice prob non è stato inizializzato, quale dovrebbe essere il suo valore? Non vedo l'inizializzazione di DIM da nessuna parte.. E' la costante VOL? Cosa rappresenta l'array vicino?

E' possibile inizializzare un array statico in modo che tutti i suoi valori siano uguali a zero con il seguente codice:

int graph[VOL][VOL] = { 0 };

Potrebbe semplificare leggermente il codice in quanto hai solo bisogno di scrivere i valori diversi da zero.

P.S. La limitazione che tutto debba essere dichiarato all'inizio del blocco (non c'è mai stata la limitazione che dice di dichiarare tutto all'inizio della funzione) è stata eliminata nello standard del 1999 e sono certo che il compilatore che stai usando supporti standard più recenti.. Oltretutto stai usando i commenti che iniziano con // che sono stati inseriti nello stesso standard..

[apatriarca]

Ti ho scritto un codice che fa più o meno quello che ti interessa per confrontarlo.

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

#define MAX_VERTS 20

int main(void)
{
    puts("Directed graph.");

    unsigned V = 0;
    do {
        fputs("Please enter number of vertices: ", stdout);
        scanf("%u", &V);
    } while (V < 1 || V > MAX_VERTS); 

    double p = -1.0;
    do {
        fputs("Please enter edge probability: ", stdout);
        scanf("%lf", &p);
    } while (p < 0.0 || p > 1.0);

    srand(clock());

    puts("\nGenerated Graph.");

    int graph[MAX_VERTS][MAX_VERTS] = { 0 };
    unsigned E = 0;
    for (unsigned i = 0; i < V; ++i) {
        for (unsigned j = 0; j < V; ++j) {
            double q = rand() / (double)RAND_MAX;
            if (q < p) {
                graph[i][j] = 1;
                ++E;
            }
            printf("%d ", graph[i][j]);
        }
        puts("");
    }

    double Q = E / (double)(V*V);
    printf("Number of generated edges: %u.\nGenerated edges probability: %f\n\n", E, Q);
}

[bad.alex]

Grazie apatriarca. Giusto per essere più chiaro, il meccanismo di collegamento tra nodi avviene secondo il preferential attachment di Albert-Barabasi. Su internet, ho trovato qualche algoritmo in C++, ma non riesco a capirlo per riscriverlo in C.
Questo dovrebbe essere l'algoritmo trovato su internet:

1) Add m0 nodes to G.
2) Connect every node in G to every other node in G, i.e. create a complete graph.
3) Create a new node i.
4) Pick a node j uniformly at random from the graph G. Set P = (k(j)/k_tot)^a.
5) Pick a real number R uniformly at random between 0 and 1.
6) If P > R then add j to i's adjacency list.
7) Repeat steps 4 - 6 until i has m nodes in its adjacency list.
8) Add i to the adjacency list of each node in its adjacency list.
9) Add i to to the graph.
10) Repeat steps 3 - 9 until there are N nodes in the graph.

[EDIT] Ho aggiunto la parte di codice che mi hai suggerito. Tuttavia mi dà un messaggio di errore legato alla chiamata srand() (expected expression):

int main()

{
    
    int i, j, V;
    double value, p=-1.0;
    
    printf("\nDirected graph\n");
    printf("\n");
    
    srand(unsigned(time(NULL)));
    V=0;
    do {
        
        printf("Please, enter the number of vertices:\n");
        scanf("%d", &V);
        
    } while(V<1||V>VOL);
    
    do {
        printf("Please, enter the edge probability:\n");
        scanf("%lf",&p);
    } while (p<0.0||p>1.0);
    
    
    printf("Generated graph\n");
    
    int graph[VOL][VOL]={0};
    int E=0;
  
    for(i=0;i<V;i++) {
        for(j=0;j<V;j++) {
            value=rand()/(double)RAND_MAX;
            if(value<p){
            graph[i][j]=1;
                E++;
    }
    
            printf("%d", graph[i][j]);
        }
    }

    /* Creating edges */
    
        double VAL=E/(double)(V*V);
        printf("Number of generated edges: %d. \n Generaded edges probability: %f\n\n", E, VAL);
        

Sapresti dirmi dove sto sbagliando? Ti ringrazio