C Maneira correta de implementar grafos

Reberth Siqueira · 30 de setembro de 2020

Fala galera! Boa noite!

Inicie meus estudos em grafos e estou perdido em relação a como criar um (minha aula a distância dessa semana foi um lixo e os videos no youtube estão me confundindo). Criei com base no conceito de matriz esparsa. Gostaria de saber se estou setando corretamente os ponteiros (função insertInRoot()).

pastebin: https://pastebin.com/BZex2nqH

abraços

arfneto · 1 de outubro de 2020

typedef struct FORK *PFork;
typedef struct FORK **PPFork;
struct FORK {
    int value;
    PFork next;
};

Acho que esse tipo de construção é mais difícil. Em geral eu diria que se NUNCA usar um tipo ponteiro NUNCA vai ter dúvidas ou depender de prefixos . Ou ficar indo e voltando nos headers para saber o que é o que. Compare:

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

typedef struct      st_fork
{
    int             value;
    struct st_fork* next;

}   Fork;

Fork**      clearRoot(Fork**,int,int);
Fork**      createRoot(int,int);
Fork*       getNode();
int         insertInRoot(Fork**, int, int);
Fork*       insertNode(int);

Esse header serviria para seu programa. Qual a diferença? Simples: só existe Fork. O dado é Fork. Fork* e Fork** e Fork**** todos só existem a partir de Fork. Então ao ler o código você e outros economizam transições tipo começa com PP ou PP ou chama pont_struct...

Os asteriscos estão lá para contar a história. E é muito mais fácil achar um erro assim do que um prefixo faltando, porque * é algo operante em C

E main() deve ser a primeira função de seu programa, se possível em um arquivo separado.

Porque? porque é onde alguém começa a ler o código. Todo alguém. E nem sempre você precisa compilar tudo... Por isso existe CMake, Make e projetos.

E como você insere as funções uma a uma, use ordem. Alfabética por exemplo. Aí pode fazer busca binária no próprio IDE. Veja, com o seu código:

O próprio IDE lista as funções que estão no arquivo aberto, na ordem em que elas estão no arquivo. Um único click e o cursor vai direto para a função. Então se estiverem em ordem alfabética seu trabalho é mínimo.

Sobre o código

Era o caso de ter uma descrição do algoritmo para entender o que quer fazer.

Fork** createRoot(int nodes, int maxConnections) {
    int i;
    Fork** root = (Fork**)malloc(sizeof(Fork) * nodes);
    for (i = 0; i < nodes; i++) {
        root[i] = NULL;
    }
    return root;
}

Isso está errado.

O que se quer aqui em geral é um array de Fork*. Não de Fork. Trata-se do mesmo paradigma de main(). cujo protótipo é

int main ( int argc, char** argv);

Você quer que createRoot() devolva o endereço de um vetor de ponteiros para estruturas, para poder iterar no vetor, como em argv[0], argv[1], argv[argc-1] em C.

Pense nisso

        createRoot(30, maxConnections);

deve retornar um ponteiro para uma área onde tem o que? 30 Fork? Não, Não, Não.

30 Fork* ! É muito importante entender isso se programa para sistemas ou estruturas de dados. E nunca se vê isso bem descrito na literatura. Ao menos eu nunca tive a sorte de ler algo assim.

Então

Fork**    grafo = createRoot( 30, 45 ); // 30 vertices

Grafo é Fork**

Então *Grafo é Fork*

E **Grafo é Fork.

Assim é. Se definiu tipos apenas para as variáveis já entendeu como fica mais transparente a expressão do algoritmo e a leitura do programa. Os asteriscos mostram CLARAMENTE o nível de redirecionamento

Então existe Grafo[0], Grafo[1], Grafo[2], e todos são Fork*, um ponteiro para Fork. É isso que você quer, e por isso Dennis e Bryan escreveram C : para escrever sistemas operacionais. E um game na verdade

Claro que em geral se escreve *Grafo, *(Grafo + 1), *(Grafo + 2). Raramente se usa essa notação de [ ] colchetes.

Então

    Fork** grafo = (Fork**)malloc(nodes * sizeof(Fork*));

Isso é mais expressivo inclusive na ordem. Pense numa nota fiscal: você instintivamente espera ler primeiro a quantidade, depois o produto e depois o preço.

Usar o cast (Fork**) antes de malloc() é opcional e muitos autores condenam e muita gente replica sem qualquer explicação. Eu recomendo usar como um seguro contra você mesmo, para deixar claro que está alocando o que pretende. Nesse caso por exemplo mostra que você está usando um ponteiro para um ponteiro para Fork, mas na verdade serão vários ponteiros. O código é autoexplicativo ou vai ser logo mais na sua carreira em C porque essa construção é muito frequente. Todo programa em C começa por uma, na verdade.

Só que aí você reservou a área apenas. Não tem nada lá. Precisa montar isso com cuidado.

    for (i = 0; i < nodes; i++)
        *(root + i) = NULL;

Essa construção que usou

    int i;
    Fork** root = (Fork**)malloc(sizeof(Fork) * nodes);
    for (i = 0; i < nodes; i++)
    {

É perigosa. Evite a todo custo.

Em geral você quer o menor escopo, a menor vida para todas as variáveis. Em especial uma chamada i ou aux...

Eis o que acontece: essa variável só é usada como controle do loop mas se você declara fora ela continua viva depois do loop e pode gerar um erro do 1nf3rn0 para char depois. Por isso desde 1989 é possível em C declarar essas variáveis como eu mostrei acima. Faça isso. Em C++ você pode declarar variáveis num switch ou while também, de tanta pressão para que isso fosse implementado para diminuir o scope de variáveis. Esse exemplo abaixo é perfeitamente legal:

	char opt = 2;
	switch (int i = 0, j = 12, char c = 'x'; opt)
	{
	default:
		std::cout << i << j << c << endl;
	};

Reberth Siqueira · 1 de outubro de 2020

Com esse programa eu queria que fosse possível criar, adicionar uma aresta e depois liberar o grafo. Ontem peguei novamente para estudar e identifiquei alguns erros no método em que eu determinei para criação das arestas. Começando pela struct:

Mudei de:

struct FORK {
    int value;
    PFork next;
};

Para:

struct FORK {
    int col;
    PFork next;
};

Onde int value eu queria armazenar um valor qualquer e no int col eu desejo armazenar o indice de refêrencia ao node desejado.

A partir dai utilizei os métodos para matrizes esparsas e acho que deu certo...

AGORA REFERENTE A SUAS OBSERVAÇÕES

11 horas atrás, arfneto disse:

Fork** createRoot(int nodes, int maxConnections) { int i; Fork** root = (Fork**)malloc(sizeof(Fork) * nodes); for (i = 0; i < nodes; i++) { root[i] = NULL; } return root; }

invés de fazer igual acima eu posso fazer que nem abaixo?

Fork** createRoot(int nodes) {
   return (PPFork) malloc(sizeof(Fork *)*nodes);
}

arfneto · 1 de outubro de 2020

Eu te expliquei a razão de não 3 tipos para a mesma coisa. E te mostrei um exemplo.

O único dado é Fork, a estrutura. Pode chamar o ponteiro de Azul e o ponteiro para o ponteiro de PAzul. Só não é esperto. Apenas Fork existe. Se a estrutura é Grafo o ponteiro é Grafo* e o ponteiro para ele é Grafo**.

Se tiver 12 estruturas vai andar com uma tabela de prefixos par ler o código? Sem necessidade? E se errar em um typedef vai arrastar isso pelo programa a toa...

Reberth Siqueira · 1 de outubro de 2020

Opa. Eu errei na parte do cast. onde estava PPFork tinha que ser Fork**

arfneto · 1 de outubro de 2020

Sim. E na versão inicial o quie estaa errado era a falta do asterisco: estava alocando unidades de Fork e não de Fork*. Eu te mostrei um exemplo. E Em geral ao ler algo assim você espera as unidades primeiro. Te expliquei isso também. Veja uma nota fiscal...

Escreva o simples.

E declarar uma variável solta com esse nome i fora do loop e só para controlar o loop é bem tosco. Sua professora por certo não vota no comitê ISO que mantem essas linguagens.

Como te disse, em java e C++ por exemplo você pode colocar { } em qualquer bloco no meio do programa apenas para reduzir o escopo e sumir com essas possíveis coisas. E em C++ se pode declarar variáveis no switch() no do() e no while() com o mesmo propósito

Reberth Siqueira · 1 de outubro de 2020

Certo. Muito interessante essa declaração de escopo dentro dos métodos switch, while e for... Vou começar a utilizar, sempre que possível.

Só pra confirmar... Após criar o vetor de Fork*:

Fork** root = (Fork**)malloc(sizeof(Fork) * nodes);

Todas posições no vetor já são NULL?

*(root+1) == NULL
*(root+2) == NULL
    .
    .
    .
*(root+n) == NULL

Ou tenho que setar como NULL?

for (int i = 0 ; i < nodes ; i++) {
  *(root+i) = NULL;
}

arfneto · 1 de outubro de 2020

35 minutos atrás, Reberth Siqueira disse:

Fork** root = (Fork**)malloc(sizeof(Fork) * nodes);

Mas eu te expliquei, no modo texto, linha a linha.

E postei o código corrigido. E a razão do erro.

Vou postar um exemplo completo mais tarde. Entenda que

você não vai alocar nodes mas sim ponteiros para nodes
escreva a quantia antes. É o natural. Todo mundo faz isso porque é mais fácil de ler. Ou o contrário.
os ponteiros devem ser inicializados

Isso foi o que eu escrevi... E entenda que é mais transparente assim: vai alocar nodes ponteiros para Fork e colocar o endereço inicial do bloco em grafo, que é Fork**

Reberth Siqueira · 1 de outubro de 2020

Novamente peço desculpa pela minha falta de atenção... Esqueci de adicionar o asterisco no sizeof(Fork)

Eu quis dizer assim:

Fork** root = (Fork**)malloc(sizeof(Fork*) * nodes);

adicionado 6 minutos depois

1 hora atrás, arfneto disse:

os ponteiros devem ser inicializados

Show. Era isso que eu imaginava. valeu

arfneto · 1 de outubro de 2020

Como escreveu está certo.

Mas não vou desistir:

entenda que malloc() só vê um número: bytes

    void*    malloc(size_t size)

E nem devia ser um int o parâmetro: assim nunca iria se preocupar com o fato de int ter sinal e um erro levar a um valor negativo na chamada. Se deve usar unsigned ou size_t que foi criado para isso.

Então o argumento é uma quantidade. Como você está alocando em unidades de Fork e não em unidades de bytes usa o operador sizeof() para converter a quantidade para bytes. E quantidade vai ser o número de nodes multiplicado pelo tamanho de cada um, e o natural é escrever como eu te disse e não o contrário como você insiste em escrever.

Algo assim ilustra o caso

Fork** createRoot(int nodes, int maxConnections)
{
    size_t quantidade = nodes * sizeof(Fork*);
    Fork** root = (Fork**) malloc(quantidade);
    for (int i = 0; i < nodes; i++)
        *(root + i) = NULL;
    return root;
};

Claro que não precisa da variável quantidade. É só um exemplo

Mas usando essa versão aí esse é o resultado

root0] =  0
root1] =  10
root2] =  20
root3] =  30
root4] =  40
root5] =  50
root6] =  60
root7] =  70
root8] =  80
root9] =  90

desse programa

#include "rb.h"

int main(void)
{
    const int amostra = 10;
    Fork** root = createRoot((int) amostra, 5);
    for (int i = 0; i < amostra; i++)
    {
        root[i] = (Fork*)malloc(sizeof(Fork));
        root[i]->value = amostra * i;
    };  // for

    for (int i = 0; i < amostra; i++)
        printf("root%d] =  %i\n", i,  root[i]->value);

    return 0;
}

De volta ao código

Acho que não precisa de uma função getNode(). Redundante
pergunte a sua professora qual seria a razão de declarar uma variável i fora do loop e que só é usada como índice do loop. Fiquei curioso. Genial a ideia dela
o seu problema de mostrar uma matriz de adjacência vai direto a dois casos: um vetor de vetores com os vértices, ou uma lista de listas com os vértices. Pense num mapa de 30 x 30 destinos e só com um caminho, de mão única: de 0 para 1 e de 1 para 2 e de 2 para 3. Seu mapa continua tendo 900 pontos, mas só vai ter 3 vértices. Essa é a definição de "esparso".
- então se você usa vetores vai ter 30 vetores apontando para os 30 possíveis vértices iniciais. No fundo mesmo isso poderia ser dinâmico, com uma lista dos vértices presentes, certo? Afinal se fossem 3000 iria criar 3000 ponteiros já de início e não parece assim bom
- e em cada vértice teria um novo vetor ou lista com os caminhos partindo desse vértice. O simples
- na hora de montar a matriz você percorre todos os caminhos possíveis e vai preenchendo o mapa. Como se fosse uma árvore. Não por acaso alguns dos algoritmos de percurso são os mesmos para grafos e árvores.
- Considerando cada início como raiz de uma árvore, nas folhas estão os possíveis finais de caminho a partir do vértice original e é só isso que você quer: a lista de folhas da árvore é a lista de 1 na tal matriz esparsa de adjacência.
- Percorre os possíveis inícios e marca os possíveis finais. Só isso.

adicionado 6 minutos depois

estruturalmente é como um arquivo csv. é algo do tipo FORK ** ** e usando o mesmo paradigma de

    int main(int argc, char** argv);

você precisaria de mais uns int para percorrer: o argc seria o contador de vértices existentes. E cada vértice teria seu próprio argc com a lista de vértices com origem nele.