Demo entry 5863126

DIGRAPH

   

Submitted by Thomas on Aug 11, 2016 at 21:39
Language: C. Code size: 6.1 kB.

/* DECLARO QUE SOU O UNICO AUTOR E RESPONSAVEL POR ESTE PROGRAMA.
// TODAS AS PARTES DO PROGRAMA, EXCETO AS QUE FORAM FORNECIDAS
// PELO PROFESSOR OU COPIADAS DO LIVRO OU DAS BIBLIOTECAS DE
// SEDGEWICK OU ROBERTS, FORAM DESENVOLVIDAS POR MIM.  DECLARO
// TAMBEM QUE SOU RESPONSAVEL POR TODAS AS COPIAS DESTE PROGRAMA
// E QUE NAO DISTRIBUI NEM FACILITEI A DISTRIBUICAO DE COPIAS.
// 
// Autor:      Thomas Sameshima
// Numero USP: 4776862
// Sigla:      THOMASRY
// Data:       2016-08-07
// 
// Este arquivo faz parte da tarefa B
// da disciplina MAC0328.
// 
////////////////////////////////////////////////////////////// */


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

 /* A função NEWnode() recebe um vértice w e o endereço next de um nó 
 e devolve o endereço a de um novo nó tal que a->w == w e a->next == next. */

static link NEWnode(Vertex w, link next) { 
   link a = malloc(sizeof (struct node));
   a->w = w; 
   a->next = next;     
   return a;                         
}

/* A função randV() devolve um vértice aleatório do digrafo G. 
Ela é apenas um invólucro para a função rand() da biblioteca stdlib, que produz 
um número inteiro (pseudo)aleatório no intervalo fechado 0..RAND_MAX. */

static Vertex randV(Digraph G) { 
    double r;
    r = rand( ) / (RAND_MAX + 1.0);
    return r * G->V;
}

/* A função DIGRAPHinit() constrói um digrafo com vértices 0 1 .. V-1 e nenhum arco. */

Digraph DIGRAPHinit(int V) { 
    Vertex v;
    Digraph G = malloc(sizeof *G);
    G->V = V; 
    G->A = 0;
    G->adj = malloc(V * sizeof (link));
    for (v = 0; v < V; v++) 
        G->adj[v] = NULL;
    return G;
}

/* A função DIGRAPHrand1() constrói um digrafo aleatório com vértices 0..V-1 e exatamente A arcos.
A função supõe que A <= V*(V-1). Se A for próximo de V*(V-1), a função pode consumir muito tempo. 
(Código inspirado no Programa 17.7 de Sedgewick.) */

Digraph DIGRAPHrand1(int V, int A) { 
    Vertex v, w;
    Digraph G = DIGRAPHinit(V);
    while (G->A < A) {
        v = randV(G);
        w = randV(G);
        if (v != w) 
            DIGRAPHinsertA(G, v, w);
    }
    return G;
}

/* A função GRAPHrand2() constrói um digrafo aleatório com vértices 0..V-1. Cada um dos V*(V-1) 
possíveis arcos é criado com probabilidade p, sendo p calculado 
de modo que o número esperado de arcos seja A. A função supõe que V >= 2 e A <= V*(V-1). 
(Código inspirado no Program 17.8 de Sedgewick.) */

Digraph DIGRAPHrand2(int V, int A) { 
    Vertex v, w;
    double p = (double) A / (V * (V-1));
    Digraph G = DIGRAPHinit(V);
    for (v = 0; v < V; v++)
        for (w = 0; w < V; w++)
            if (v != w && rand( ) < p*(RAND_MAX + 1.0))
                DIGRAPHinsertA(G, v, w);
    return G;
}

/* A função GRAPHrand1() constrói um grafo aleatório com vértices 0..V-1 e exatamente E arestas.
A função supõe que E <= V*(V-1)/2. (Código inspirado no Programa 17.7 de Sedgewick.) */

Digraph GRAPHrand1(int V, int E) { 
    Vertex v, w;
    Digraph G = DIGRAPHinit(V);
    while (G->A < 2*E) {
        v = randV(G);
        w = randV(G);
        if (v != w) { 
            DIGRAPHinsertA(G, v, w);
            DIGRAPHinsertA(G, w, v);
        }
    }
    return G;
}

/* A função GRAPHinit2() constrói um grafo aleatório com vértices 0..V-1. Cada uma das V*(V-1)/2 
possíveis arestas é criada com probabilidade p, sendo p calculado 
de modo que o número esperado de arestas seja E. A função supõe que V >= 2 e E <= V*(V-1)/2. 
(Código inspirado no Program 17.8 de Sedgewick.) */

Digraph GRAPHrand2(int V, int E) { 
    Vertex v, w;
    double p = (double) 2*E / (V * (V-1));
    Digraph G = DIGRAPHinit(V);
    for (v = 0; v < V; v++)
        for (w = 0; w < V; w++)
            if (v != w && rand( ) < p*(RAND_MAX + 1.0)) {
                DIGRAPHinsertA(G, v, w);
                DIGRAPHinsertA(G, w, v);
            }
    return G;
}

/* A função DIGRAPHdestroy() libera o espaço que a representação ocupa na memória. */

void DIGRAPHdestroy(Digraph G) {
	link a, b;
	int i;
	for (i = 0; i < G->V; i++) {
		a = G->adj[i];
		while(a) {
			b = a;
			a = a->next;
			free(b);
		}
	}
	free(G->adj);
	free(G);
}

/* A função DIGRAPHinsertA() insere um arco v-w no digrafo G. A função supõe que v e w são distintos, 
positivos e menores que G->V. Se o digrafo já tem um arco v-w, a função não faz nada. */

void DIGRAPHinsertA(Digraph G, Vertex v, Vertex w) { 
    link a;
    for (a = G->adj[v]; a != NULL; a = a->next) 
        if (a->w == w) return;
    G->adj[v] = NEWnode(w, G->adj[v]);
    G->A++;
}

/* A função DIGRAPHremoveA() remove um arco v-w do digrafo G. A função supõe que v e w são distintos, 
positivos e menores que G->V. Se não existe arco v-w, a função não faz nada. */

void DIGRAPHremoveA(Digraph G, Vertex v, Vertex w) {
	link prev, curr;
	prev = NULL;
	for (curr = G->adj[v]; curr != NULL; prev = curr, curr = curr->next)
		if (curr->w == w) {
			if (prev == NULL) G->adj[v] = curr->next;
			else prev->next = curr->next;
			free(curr);
			return;
		}
}

/* A função DIGRAPHindeg() calcula e retorna o grau de entrada de um vértice v de um grafo G. */

int DIGRAPHindeg(Digraph G, Vertex v) {
	link a;
	int i, d;
	for (i = 0, d = 0; i < G->V; i++)
		for (a = G->adj[i]; a != NULL; a = a->next)
			if (a->w == v) d++;
	return d;
}

/* A função DIGRAPHoutdeg() calcula e retorna o grau de saída de um vértice v de um grafo G. */

int DIGRAPHoutdeg(Digraph G, Vertex v) {
	link a;
	int d = 0;
	for (a = G->adj[v]; a != NULL; a = a->next) d++;
	return d;	
}

/* A função DIGRAPHshow() imprime, para cada vértice v do digrafo G, em uma linha, 
todos os vértices adjacentes a v. */

void DIGRAPHshow(Digraph G) { 
    Vertex v;
    link a; 
    for (v = 0; v < G->V; v++) {
        printf("%2d:", v);
        for (a = G->adj[v]; a != NULL; a = a->next)
            printf(" %2d", a->w);
        printf("\n");
    }
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).