21
COS242 – Teoria dos Grafos Trabalho Prático – Parte 2 Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Embed Size (px)

Citation preview

Page 1: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

COS242 – Teoria dos GrafosTrabalho Prático – Parte 2

Alunos:Bruno Tourinho Tomas

Jonathan Augusto da Silva

Page 2: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Sumário

Objetivo

Destaques sobre implementação

Resultados dos Estudos de Caso

Page 3: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Introdução

Page 4: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

ObjetivoExpandir a biblioteca desenvolvida na parte 1, incluindo as seguintes funcionalidades:Grafos com pesos;Distância e caminho mínimo;Árvore geradora mínima (MST); Distribuição empírica da distância; eDistância média.

Page 5: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Destaques sobre a implementação

Page 6: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Orientação a objetoNa parte 1 do trabalho, a estrutura orientada a

objeto foi usada apenas como “intermediária” para criação de matriz e lista de adjacência

Agora, ela segue como uma “terceira via” no projeto, sendo mais uma opção para representação

Relativamente baixo consumo de memória (como na lista de adjacência):

Grafo 4 (50000 vértices)OO: ~40MBLista: ~25MBMatriz: >1.5GB (travou!)

Page 7: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Programação concorrentePara o cálculo da distribuição empírica das

distâncias e da distância média, era preciso executar o algoritmo de Dijkstra diversas vezes

No caso do grafo 5 (o maior, com 100000 vértices):

1 Dijkstra a cada 40 minutos (em média) = 36 por dia100000 vértices -- 2778 dias = ~7,7 anosSolução?

Threads to the rescue!

Page 8: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Programação concorrenteUso da biblioteca Boost

Possui bibliotecas de suporte a diversas áreas, como gerenciamento de memória, matemática, análise sintática, programação concorrente, entre outras.

www.boost.org

Page 9: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Programação concorrente#include <boost/thread/thread.hpp>using namespace std;

void ola_mundo(){

cout << "Ola mundo, sou uma thread!" << endl;}

int main(int argc, char* argv[]){ // inicia uma nova thread que chama a função ola_mundo boost::thread minha_thread( &ola_mundo ); // espera a thread finalizar minha_thread.join();

return 0;}

Page 10: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Resultados - 1Caminho mínimoDistância mínima

(a partir do vértice 1)

Page 11: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Resultados – Grafo 1

Vért.

finalDistância Caminho

10 19 1-100-17-8-67-10

100 12 1-100

Page 12: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Resultados – Grafo 2

Vért.

final

Distânci

aCaminho

10 2 1-52-10

100 2 1-144-100

1000 2 1-874-1000

Page 13: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Resultados – Grafo 3 Vért.

final

Distânci

aCaminho

10 261-2-3-7739-3782-8405-7014-

10

100 29 1-2-3-7739-3782-3259-100

1000 331-2-3-7739-3782-83-2265-

1995-8244-1541-1001-1000

10000 12 1-10000

Page 14: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Vért.

final

Distânci

aCaminho

10 27

1-2-40954-6638-24142-5438-5437-30631-18082-9-

10

100 19

1-2-30823-31610-13545-49238-35624-39086-21397-

99-100

1000 36

1-2-40954-9187-46430-48174-42945-43820-36655-

19057-1002-1001-1000

10000 171-2-40954-9187-44780-

30421-15094-28332-10000

Resultados – Grafo 4

Page 15: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Resultados – Grafo 5 Vért.

finalDistância Caminho

10 56

1-100000-99999-99998-92827-24681-49217-86633-23787-19564-82822-24916-79294-79095-35948-30951-30952-30953-

70778-10

100 481-100000-99999-99998-5098-15254-

70965-45051-13678-79705-85645-12152-12151-94349-100

1000 491-100000-99999-99998-5098-15254-

23575-7300-96904-96903-56757-17388-17389-57543-95359-999-1000

10000 94

1-100000-99999-99998-5098-15254-23575-7300-91801-72212-72213-24567-

78009-78010-16066-9993-9994-9995-9996-9997-9998-9999-10000

Page 16: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Resultados - 2Distribuição empíricaDistância média

Page 17: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Resultados

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 951000

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

Distribuição empírica da distância

grafo_1grafo_2grafo_3

Distância

Fre

qu

ên

cia

rela

tiva

da d

istâ

ncia

Page 18: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Resultados Distâncias médias

Grafo Distância média

1 13,01922 2,08593 6,91714 ind.

5 ind.

Page 19: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Resultados - 3Árvore geradora mínima (MST)

Page 20: Alunos: Bruno Tourinho Tomas Jonathan Augusto da Silva

Resultados Árvore geradora mínima

Grafo Custo da MST

1 3362 9993 319474 2162365 608677