Método ShowMemory()

Esse método tem a finalidade de calcular e imprimir a quantidade de memória gastapela classe de grafos quando utiliza a tecnica de matrizes de adjacência e delistas de adjacências.Julgo que o calculo de memória utilizada para matrizes seja mais simples do quelistas, portanto é por ela (Matriz adjacênte) que começaremos.
Bom, na matriz guardamos valores inteiros que ocupa 4Bytes de espaço de memória.Se já sabemos quanto cada espaço alocado de memória tem separadamente, entãoprecisamos descobrir quantos espaços reservamos para contruir a matriz.
Mas como descobrir isso?
Isso é simples, pois o usuário entra com a quantidade de nós que ele deseja, e amatriz adjacênte, é uma matriz quadrada do valor total de nós, ou seja tem aquantidade de nós de linha e coluna.Por exemplo:
O usuário diz que o objeto de grafos instanciado por ele terá cinco nóslogo nossa matriz tem cinco linhas e cinco colunas.
Sendo assim, elevamos a quantidade de nós ao quadrado para saber a quantidade deíndices da matriz. Após isso pegamos o resultado adquirido e multiplicamos por 4que é a quantidade de bytes ocupados por uma variável do tipo inteiro.

4: Múltipicla 4 (valor de Bytes reservados da memória para uma variável do tipo inteiro) pela quantidades de nós do grafo elevado ao quadrado.

5-8: Impressão da informação calculada.

Método SetAresta()

Esse método tem como objetivo criar a aresta entre dois pontos que são definidos pelo usuário via parâmetros.
Nesse método conseguimos incluir também o valor de peso da aresta e dizer se ela é uma aresta dirigida ou não.
Existem três variações de possibilidade de entrada de parâmetros nesse método. A imagem mostrada a baixo é o método com quantidade máxima de parâmetros que se pode passar.
As outras duas variações serão mostradas logo após a explicação de cada linha do método.

Vale ressaltar que, se o valor do parâmetro de direção for 0, então a aresta é não dirigida e se o valor do parâmetro for 1 então a aresta é dirigida.






58: Condição para verificar se os parâmetros passados pelo usuário de nó de origem e nó de destino são valores menores que o tamanho do atributo Nos.
Essa verificação tem de ser feita, porque se, por exemplo, tentarmos acessar o índice 5 de um vetor que só tem 3 posições o programa irá dar erro por tentar acessar um índice que não existe.
60: Caso os valores dos pontos de inicio e fim forem menor que o atributo Nos, então é verificado se o parâmetro direcao (que verifica se a aresta é ou não dirigida) recebeu o valor 0 ou 1.
61: Caso a condição for verdadeira então a Matriz recebe o peso da aresta passado por parâmetro na posição (também passada por parâmetro) do ptoOrigem e ptoDestino.
62: Caso a condição da linha 11 for falsa então é verificado se o valor passado por parâmetro para direção é igual a 0
64-65: Se essa condição for verdadeira então a Matriz recebe o peso nos dois sentidos.

Agora muitos devem estar se perguntando o que é esses dois sentidos mencionados acima.
Bom, vamos tentar explicar:
Vamos supor que uma aresta de peso 5 irá ser criada. É passado como parâmetro também o ponto inicial (definido pelo parâmetro ptoOrigem) 7 e ponto de destino (definido pelo parâmetro ptoDestino) 10.
Se o grafo não for dirigido (direcao = 0) então o grafo não tem direção, ou seja, não tem ponto inicial ou final.
Sendo assim, o ponto definido como ponto de origem é na verdade o ponto inicial e também o final, ou seja, essa aresta pode ir do ponto 7 até 10 ou do ponto 10 até 7.


67: Caso as condições das linhas 60 e 62 forem falsas então uma mensagem de erro é enviada ao usuário.


Agora serão mostradas as outras formas de chamar o método SetAresta que só varia pelo número de parâmetros passados.





No primeiro método que vai da linha 78 até a linha 81 o parâmetro de peso da aresta não é passado, portanto, por padronização chamamos o método apresentado anteriormente do SetAresta passando o valor do peso como 1.

Já no segundo método apresentado que vai da linha 85 até a linha 88, os valores de peso da aresta e direcao não são setados. Portanto, por padronização passamos os valores, tanto de peso, quanto de direção da aresta, valendo 1.

Método GerarGrafo()

Esse método tem por objetivo dimensionar os valores para o grafo que será gerado.
Esse método recebe o tamanho passado como parâmetro e a partir disso gera o vetor de peso dos nós, a matriz de adjacência.
Vale ressaltar que esse método não é acessível aos usuários.
O usuário, quando instancia o objeto grafo, passa o valor do tamanho o grafo e então o construtor do objeto chama essa função para realizar todos os dimensionamentos.



36: Condição que verifica se o tamanho passado como parâmetro para o método é maior que zero.
38: Se o valor de tam for maior que zero então o atributo Nos receberá o valor passado por parâmetro.
39: É criado o vetor para peso de acordo com o tamanho do grafo passado por parâmetro.
40: É criado o vetor inicial da matriz de acordo com o tamanho passado por parâmetro.

Tanto no caso da Matriz quanto o Peso, o tamanho passado por parâmetro refere-se à quantidade de posições que eles terão.
Por exemplo, se o tamanho passado for 3, então peso será um vetor com três posições (vai de 0 a 2).
No caso da matriz esse primeiro vetor serve como um local onde guarda o endereço de memória das linhas que serão guardados os registros.
42-43: Laço que cria a quantidade de linhas da matriz de acordo com o valor entrado.
47-49: Se a condição da linha 3 for falsa então os atributos Nos, Peso e Matriz receberão NULL como valor.

Classe de Grafos

Inicialmente apresentaremos a estrutura que a classe grafo está tomando nesse começo de desenvolvimento.
Por problemas de entendimento de como a classe seria desenvolvida, tivemos de mudar muitas coisas nela, mas agora ela está corrigida.

Abaixo serão apresentados os atributos iniciais da classe e os protótipos dos métodos criados até então.





8: Private (Área Privada) - Todos os métodos, variáveis e objetos que são criados nessa área só podem ser acessados, ou ter seus valores alterados dentro da própria classe.
9: Declaração do atributo que define a quantidade de nós que o grafo irá ter.
10: Declaração do atributo (em forma de vetor) que define o peso dos nós.
11: Declaração do atributo (em forma de matriz) que define as arestas do grafo.
13: Protótipo do método GerarGrafo.
14: Public (Área Pública) - Todos os métodos, variáveis e objetos que são criados nessa área podem ser acessados, ou ter seus valores alterados de qualquer outra classe que faça referência a essa.
15: Construtor da classe onde não é necessário que passe parâmetro.
17: Chama o método GerarGrafo, passando o valor 0 como parâmetro. No próximo post esse método (e outros) serão explicados.
19: Construtor da classe onde o usuário entra com o valor de parâmetro.
21: Chama o método GerarGrafo, passando o valor que o usuário passou como parâmetro. No próximo post esse método (e outros) serão explicados.
24-30: Protótipo dos métodos da classe.

GRAFOS

Consideramos informalmente, grafo como um conjunto não vazio de pontos V (vértices, nós, nodos) podendo ou não haver ligações entre eles através de linhas (arcos, arestas). A cada aresta do grafo podemos associar um par de nós do grafo.


Alguns exemplos de aplicações dos grafos:
1. Modelagem de circuitos digitais
2. Representação de processos em sistemas paralelos ou distribuídos.
3. Simulação e avaliação de desempenho

· Um grafo G é constituído por um conjunto N de elementos e por uma relação binária A entre estes elementos.

Escreve-se: G = (N, A).
· N são denominados nós (ou vértices).
· A são denominados arcos (ou arestas).

Ex:

N={1, 2, 3, 4}
A={(1, 2), (1, 4), (2, 1), (3, 1), (3, 2), (3, 4), (4, 2)}

· Nós ligados por arcos são ditos adjacentes (do ex. 3 é adjacente de 1, 2 e 4).
· Arcos são incidentes de um nó (partem dele) ou incidentes a um nó (chegam nele)
- incidentes do nó 2 – (partem dele) - (2, 1), (3, 2) e (3, 4)
- incidente no nó 1 - (1, 2)
· O grau de um nó é igual ao número de arcos que incidem a ele.
· Um caminho é a seqüência de arcos e nós percorridos com o objetivo de ligar dois nós não adjacentes.
(Ex: (1,2) e (2,3) é o caminho que liga o nó 1 ao nó 3. )
· Um circuito é um caminho que pode ser percorrido infinitamente dentro do grafo. Ex: (1,2), (2,4), (4,1); ou (3,3).
· Ramo Incidente num vértice v, é qualquer ramo para o qual v é vértice destino. No caso de ramo não orientado é incidente nos dois vértices que o ramo liga.
· Anel é um ramo de um grafo que liga um vértice a si próprio
· Ramos Paralelos são ramos que ligam os mesmos nós
· Multigrafo é um grafo que contem ramos paralelos, caso contrário será Grafo Simples
· Multiplicidade (peso) de um ramo valor que indica o número de ramos, com o mesmo sentido, que ligam 2 nós. Pode generalizar-se este conceito de peso e associar-se a cada ramo um valor inteiro que representará um atributo do ramo. Por exemplo, no caso de representação de um mapa das rua de uma cidade, poder-se-ia considerar em cada ramo um número (peso) que poderia ser a densidade de tráfego.
· Vértice Isolado é um vértice que não é origem nem destino de nenhum ramo.
Grafo Nulo é um grafo constituído só por vértices isolados.
· Um grafo conexo é aquele que possui um nó a partir do qual existem caminhos para todos os demais nós.
· Um subgrafo é aquele onde é considerado apenas um subconjunto dos nós do grafo original.
· Um grafo parcial, considera-se um subconjunto dos arcos do grafo original, permanecendo todos os nós.Ex:

· Um grafo é acíclico quando não possui circuitos.

· Uma rede é um tipo especial de grafo que possui um nó fonte, a partir do qual todos os demais nós são atingidos e um nó sorvedouro, do qual não parte nenhum nó.

· Os grafos vistos até agora são dígrafos, ou grafos dirigidos, nos quais a relação binária não é simétrica, ou seja, não implica em retorno.

· Grafos valorados (weighted graphs): Um número pode ser associado aos nós ou arcos de um grafo (dirigido ou não).

Ex:

· Existem maneiras diferentes dese representar um grafo, como por exemplo, matrizes de adjacência e listas de adjacência

MATRIZ DE ADJACÊNCIA

- Usar uma matriz para representar um grafo permite:obter caminhos, ciclos e outras características dos grafos.
- Preferível em grafos pequenos.
- Requer apenas um bit por entrada.

Este grafo é representado por uma matriz quadrada M (n x n) cujos elementos são mij em que:
- As linhas correspondem aos vértices origem e as colunas aos vértices destino.

- mij=1 se (vi,vj) Î E (existe ligação entre i e j)

- mij=0 não existe ligação entre i e j.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Abaixo está a 1ª classe Grafos que a gente fez e alguns metodos.....

Estão com alguns erros, pois são apenas as ideias iniciais, mas estes já foram corrigidos nas postagens acima.

----------------------- Classe Grafos

----------------------- Método Gerar grafos

----------------------- Metodo Set Aresta

----------------------- Metodo Imprime Peso

Metodo parentAninhados

O método parentAninhados tem a função de representar graficamente uma arvore binária através de parênteses como mostra a imagem a seguir:

1 – 4: Método que faz interface entre o usuário e a programação para mostrar uma árvore representada graficamente através dos parentes aninhados.
7: Verifica se o nó raiz passado é ou não nulo.
9: Imprimi na tela o “(” mais o valor do nó.
10: Chama recursivamente o método passando o valor do nó filho da esquerda.
11: Chama recursivamente o método passando o valor do nó filho da direita.
12: Imprimi na tela o “)”.

Metodo arvoreHierarquicaII

O método arvoreHierarquicaII tem a função de representar graficamente uma arvore binária através de uma arvore de hereditária como mostra a imagem a seguir:

1 – 4: Método que faz interface entre o usuário e a programação para mostrar uma árvore representada graficamente através dos arvore hierárquica II.
7: Verifica se o nó raiz passado é ou não nulo.
9: Imprimi a variável space que guarda os espaços em branco dados para a identação da árvore e o valor do nó atual.
10: Acrescenta espaços em branco à variável space.
11: Chama recursivamente o método passando o valor do nó filho da esquerda e os espaços em branco guardados em space.
12: Chama recursivamente o método passando o valor do nó filho da direita e os espaços em branco guardados em space.