Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Resolver problema de Minimum Spanning Tree de um grafo

0 votos
229 visitas
perguntada Dez 7, 2020 em Ciência da Computação por leonardocarvalho (21 pontos)  

Como proposto no livro "Dynamic programming - A computational tool", no capítulo 2 exercício 2.29, o problema de minimum weight spanning tree consiste em achar um subgrafo que contenha todos os nós do grafo original, dado que a soma dos pesos de suas conexões seja a mínima possível.

Compartilhe

1 Resposta

0 votos
respondida Dez 7, 2020 por leonardocarvalho (21 pontos)  
editado Dez 17, 2020 por leonardocarvalho

Para começar a responder essa pergunta, precisamos primeiro definir o que é um grafo.
Um grafo é uma estrutura de dado que consiste em nós e arestas. Cada nó pode se conectar com outro por meio de uma aresta, que terá um respectivo peso P para ser possível caminhar de um ponto até o outro (podemos considerar isso o custo ou a distância entre esses dois nós).
Todo nó pode se conectar com qualquer outro, mas não é possível que um nó tenha dois caminhos diferentes para outro. Uma imagem abaixo ilustra a situação:

A imagem será apresentada aqui.

Um subgrafo é um conjunto de nós que pertence a um outro grafo do qual esse foi gerado. Ele tem as mesmas propriedades de um grafo normal.
O problema de minimum weight spanning tree define que devemos achar o menor caminho possível para que podemos conectar todos os nós. Um algoritmo útil para esse tipo de problema é o algoritmo de Prim.

Ele consiste em começar em um nó qualquer, e, a partir dele, escolher a aresta com menor peso que está conectado. Supondo que o nó inicial é o ponto A da imagem acima, a aresta com menor peso é D (peso = 5), então nos movemos para esse nó. A partir de agora, temos como nós visitados [A, D]. Agora podemos analisar entre os nós visitados, qual o menor caminho que podemos seguir. Como D se conecta com F por meio de um caminho com peso igual a 6 e A se conecta a B com um caminho de peso igual a 7, seguimos para o nó F. Agora, os nós visitados são [A, D, F].

Como F tem caminhos com pesos 8 e 11, D com um caminho possível igual a 15 e A com um caminho de peso igual a 7, podemos seguir do nó A para B. A lista de nós visitados é atualizada para [A, D, F, B]. E seguimos com o algoritmo até ele encontrar o minimum spanning tree desse grafo, ou seja, o menor caminho que liga todos os nós, que está sinalizado em verde. (O código foi feito em JavaScript, mas se necessário posso colocá-lo em Python.

 class Graph{
     constructor(){
         this.paths = {};
         this.visitedNodes = [];
 }
    addNode(key, conections, weights){
    this.paths[key] = new Map();
    for (let i = 0; i < conections.length; i++){
        this.paths[key].set(conections[i], weights[i]);
    }
    return this;
}

Primeiro criamos o objeto Grafo, que contém em seu construtor os caminhos, sendo os nós as chaves desse objeto. visitedNodes são os nós já visitados no grafo para encontrar o Minimum Spanning Tree.
addNode é um método desse objeto que permite criar um novo nó e seus respectivos caminhos. O primeiro argumento é o nome do nó (chave da propriedade this.paths), e em seu valor está um Map() que irá mapear cada nó ao seu respectivo peso. Usando um loop, podemos criar esse nó e seus respectivos caminhos.

getNodes(){
    return Object.keys(this.paths);
}
getPath(key){
    return this.paths[key].keys();
}
getNode(key){
    let minorWeight = Infinity;
    for (let node of this.paths[key].entries()){
        if (minorWeight > node[1]
            && this.visitedNodes.indexOf(node[0]) == -1){
                minorWeight = node[1];
                var nodeName = node[0];
            }
    }
    return [minorWeight, nodeName];
}
minimumSpanningTree(start){
    let subGraph = new SubGraph(this);
    subGraph.minimum.path.push(start);
    let graphLength = this.getNodes().length;
    this.visitedNodes.push(start);
    while (subGraph.length !== graphLength){
        subGraph.findMinorWeight(this.visitedNodes);
    }
    subGraph.sumWeights();
    this.visitedNodes = [];
    return subGraph;
}

Os outros métodos desse objeto são:
getNodes(), que retorna todos os nós desse grafo.
getPath(key), retorna os nós que estão conectados com o nó escolhido (key).
getNode(key), escolhe o menor caminho possível dentro de um nó (key), que consiste em
passar por todos os nós conectados por meio de um loop e, caso o nó escolhido seja menor do que o último e, esse nó escolhido não exista em this.visitedNodes, consideramos ele o que tem o menor caminho possível.

O método minimumSpanningTree é o que cria o subgrafo. Primiero, um objeto subGraph é criado. Após isso, criamos no caminho escolhido no subgrafo para adicionar o nó inicial (start). Criamos uma variável que armazena o tamanho do nó em graphLength. Adicionamos o nó visitado do grafo em this.visitedNodes, e, então, iniciamos um while loop para que, enquanto os nós do subgrafo forem diferentes dos nós do grafo, o algoritmo continue procurando o minimum spanning tree.

O método findMinorWeight do objeto subgrafo faz a procura dentro dos nós já visitados. Após o subgrafo estar pronto, somamos os pesos de seus caminhos com o método sumWeights, reiniciamos o vetor de visitedNodes e retornamos o subGrafo resultante.

class SubGraph {
    constructor(graph){
        this.minimum = {"path": [], "weights": [], "Total Weight": 0};
        this.graph = graph;
        this.length = 1;
}
    findMinorWeight(visitedNodes){
        let minorWeight = Infinity;
        for (let node of visitedNodes){
            let [nodeWeight, nodeName] = this.graph.getNode(node);
            if (minorWeight > nodeWeight){
                minorWeight = nodeWeight;
                var chosenNode = nodeName;
            }
        }
        visitedNodes.push(chosenNode);
        this.updateMinimumPath(chosenNode, minorWeight);
        this.length++; // aumenta o tamanho do subgrafo
}

O objeto subGrafo tem como propriedades o minimum, que é o caminho feito para criar achar o minimum spanning tree, graph, que é o grafo que gera esse MST e o tamanho do subGrafo, que começa com 1, o nó inicial.

O método findMinorWeight procura, entre todos os nós já visitados, qual deles tem o caminho com o menor peso. Ele passa por todos esses nós, coleta o menor peso de cada um e depois o compara com o menor valor antes registrado (no caso, compara minorWeight, o menor anterior com o nodeWeight, o maior agora). Caso verdadeiro, coleta o nome desse nó com chosenNode e depois o coloca em visitedNodes.

updateMinimumPath(node, weight){
    this.minimum.path.push(node);
    this.minimum.weights.push(weight);
}
sumWeights(){
    this.minimum["Total Weight"] = this.minimum["weights"].reduce(
        (value, sum) => {
            return value+sum; // calcula a soma dos pesos do subgrafo
        }
    );
}
print(allInfo){ // imprime o subgrafo
    let [path, weights, totalWeight] = [this.minimum.path, this.minimum.weights, this.minimum["Total Weight"]];
    if (allInfo == undefined){ // forma simples
        console.log(`${path}\n${weights}\n${totalWeight}`)
    } else if (allInfo == true) { // forma mostrando como foram feitos os caminhos, mais completa
        console.log(`Nó: ${path[0]}, Peso para chegar: Nó Inicial`);
        for (let i = 0; i < weights.length; i++){
            console.log(`Nó: ${path[i+1]}, Peso para chegar: ${weights[i]}`)
        }
        console.log(`Total Weight: ${totalWeight}`);
    }
}

Já o método updateMinimumPath atualiza o caminho feito até agora no subgrafo adicionando o novo nó com menor peso e aumentando em 1 o tamanho do subgrafo.
O método print serve para imprimir o subGrafo com seus caminhos e pesos, pode ser escolhido tanto uma impressão mais simples (somente os nós e depois o peso de cada nó, com o total embaixo) ou uma mais completa, mostrando de onde veio o nó atual e qual foi o peso desse caminho.

No final, podemos testar se funciona utilizando o método print do subGrafo criado. Um exemplo abaixo:

myGraph = new Graph();
testGraph = new Graph();

myGraph.addNode("a", ["b", "h"], [4, 8]);
myGraph.addNode("b", ["a", "c", "h"], [4, 8, 11]);
myGraph.addNode("c", ["d", "f", "i", "b"], [7, 4, 2, 8]);
myGraph.addNode("d", ["c", "e", "f"], [7, 9, 14]);
myGraph.addNode("e", ["d", "f"], [9, 10]);
myGraph.addNode("f", ["c", "d", "g", "e"], [4, 14, 2, 10]);
myGraph.addNode("g", ["f", "i", "h"], [2, 6, 1]);
myGraph.addNode("h", ["a", "b", "i", "g"], [8, 11, 7, 1]);
myGraph.addNode("i", ["c", "g", "h"], [2, 6, 7]);

testGraph.addNode("a", ["b", "c", "d"], [4, 6, 5]);
testGraph.addNode("b", ["e", "c", "a"], [7, 1, 4]);
testGraph.addNode("c", ["a", "b", "d", "e", "f"], [6, 1, 2, 5, 4]);
testGraph.addNode("d", ["a", "c", "f"], [5, 2, 5]);
testGraph.addNode("e", ["b", "c", "f", "g"], [7, 5, 1, 6]);
testGraph.addNode("f", ["c", "d", "e", "g"], [4, 5, 1, 8]);
testGraph.addNode("g", ["e", "f"], [6, 8]);

São criados dois grafos: myGraph e testGraph. O primeiro argumento do método é o nó em que será feito as ligações. O segundo é o nome dos nós que representarão as ligações, e por fim, o terceiro é o peso de cada ligação, respectivamente.

const newGraph = myGraph.minimumSpanningTree("i");
const otherGraph = myGraph.minimumSpanningTree("a");
const test = testGraph.minimumSpanningTree("b");
newGraph.print(true);
otherGraph.print(true);
test.print(true);

Depois, criamos os subgrafos gerados a partir deles usando o método minimumSpanningTree, com um argumento de onde irá começar a procura. Usando o método print, com o seu único argumento sendo true para que imprima o caminho realizado de uma forma mais compreensível. Dessa forma, o output será o caminho feito para criar o subgrafo, com o peso de cada nó escolhido e, no final, o peso total desse subgrafo. No caso do primeiro teste, é retornado:

Nó: i, Peso para chegar: Nó Inicial
Nó: c, Peso para chegar: 2
Nó: f, Peso para chegar: 4
Nó: g, Peso para chegar: 2
Nó: h, Peso para chegar: 1
Nó: d, Peso para chegar: 7
Nó: b, Peso para chegar: 8
Nó: a, Peso para chegar: 4
Nó: e, Peso para chegar: 9
Total Weight: 37

No segundo, temos:

Nó: a, Peso para chegar: Nó Inicial
Nó: b, Peso para chegar: 4
Nó: h, Peso para chegar: 8
Nó: g, Peso para chegar: 1
Nó: f, Peso para chegar: 2
Nó: c, Peso para chegar: 4
Nó: i, Peso para chegar: 2
Nó: d, Peso para chegar: 7
Nó: e, Peso para chegar: 9
Total Weight: 37

E o terceiro:

Nó: b, Peso para chegar: Nó Inicial
Nó: c, Peso para chegar: 1
Nó: d, Peso para chegar: 2
Nó: a, Peso para chegar: 4
Nó: f, Peso para chegar: 4
Nó: e, Peso para chegar: 1
Nó: g, Peso para chegar: 6
Total Weight: 18
comentou Dez 17, 2020 por danielcajueiro (5,501 pontos)  
Acho que seria interessante colocar um exemplo especifico com a entrada e a saida.
comentou Dez 17, 2020 por leonardocarvalho (21 pontos)  
Foram adicionados três exemplos, dois com um mesmo grafo mas iniciando em nós diferentes e um outro grafo diferente
comentou Dez 17, 2020 por Luiz Filippe (21 pontos)  
Leonardo, muito interessante sua resposta. Tanto a explicação do problema (o que é grafo e toda a questão dos pesos) quanto a explicação detalhada de cada passo do código. Mesmo não sendo familiarizado com JavaScript, consegui entender. Não vejo onde acrescentar à sua resposta.
...