/ktrees

Computer Science undergraduate thesis on uniform generation of k-trees for learning the structure of Bayesian networks (USP 2016)

Primary LanguageGo

Este repositório contém os códigos desenvolvidos para o meu trabalho de conclusão de curso, juntamente à sua documentação.

Tema: geração uniforme de k-trees para aprendizado de redes bayesianas
Supervisor: Prof. Dr. Denis Deratani Mauá
Mais informações:

GoDoc Build Status Coverage Status

Instalação e testes

As implementações foram realizadas em Go e é necessário instalá-lo. Recomenda-se utilizar o próprio go para clonar este repositório.

Para baixar o código e rodar os testes, use:

$ export ${GOPATH:=$HOME/go}
$ mkdir -p $GOPATH
$ go get github.com/tmadeira/tcc/...
$ go test -v github.com/tmadeira/tcc/...

As três primeiras linhas criarão o diretório $HOME/go e o usarão como $GOPATH caso essa variável de ambiente não esteja configurada na sua estação de trabalho.

Caso você não esteja acostumado com esse workflow (que é o padrão da linguagem Go), recomenda-se a leitura de How to Write Go Code.

Exemplos

Após baixar o código no seu $GOPATH, você pode usar alguns utilitários disponíveis na pasta examples/. Eles permitem codificar/decodificar k-trees e gerar k-trees aleatórias.

code-ktree

Para codificar uma k-tree, use:

$ go install github.com/tmadeira/tcc/examples/code-ktree
$ $GOPATH/bin/code-ktree

A entrada desse utilitário deve ser dada no formato:

k
m
x_1 y_1
...
x_m y_m

Onde:

  • n é o número de vértices
  • k é o parâmetro k da k-tree
  • m é o número de arestas
  • x_i y_i corresponde à i-ésima aresta (0 <= x_i, y_i < n)

Um exemplo de entrada pode ser encontrado em examples/code-ktree/fig1a.txt.

A saída será um par (Q, S) no formato de entrada esperado pelo utilitário decode-ktree.

decode-ktree

Para decodificar um código (Q, S) em uma k-tree, use:

$ go install github.com/tmadeira/tcc/examples/decode-ktree
$ $GOPATH/bin/decode-ktree

A entrada desse utilitário deve ser dada no formato:

Q_1
...
Q_k
s
p_1 l_1
...
p_s l_s

Onde:

  • k é o tamanho de Q
  • Q_i corresponde ao i-ésimo valor em Q
  • s é o tamanho do Generalized Dandelion Code, |S|
  • p_i l_i corresponde ao i-ésimo valor em S

Um exemplo de entrada pode ser encontrado em examples/decode-ktree/code1a.txt.

A saída será uma k-tree no formato de entrada esperado pelo utilitário code-ktree.

generate-ktree

Para gerar uma k-tree aleatória, use:

$ go install github.com/tmadeira/tcc/examples/generate-ktree
$ $GOPATH/bin/generate-ktree

A entrada desse utilitário deve ser dada no formato:

n k

A saída será uma k-tree com n vértices no formato de entrada esperado pelo utilitário code-ktree.