Representação compacta de caminhos em um gráfico

Eu tenho um subconjunto dos caminhos simples em um gráfico. O comprimento dos caminhos é delimitado por . $d$

Qual é a maneira mais compacta (em termos de memória) de representar os caminhos de forma que nenhum outro caminho além dos selecionados seja representado?

Observe que eu quero usar essa representação em um algoritmo que irá percorrer esse subconjunto de caminhos repetidamente e que eu quero ser bastante rápido; portanto, por exemplo, não posso usar nenhum algoritmo de compactação padrão.

Uma representação que me veio à cabeça foi representá-las como um conjunto de árvores. No entanto, acho que reduzi-lo a um número ideal de árvores é difícil para o NP? Que outras representações seriam boas?

graphs data-structures Optar
fonte

Ao "percorrer este subconjunto", quais informações sobre cada caminho você precisa? Comprimento? Nós visitados? Interseções com outros caminhos? ... Pode haver

muitos, então você deve estar preparado para "não muito rápido" se precisar armazenar caminhos inteiros.

2^{d}

$2^d$

Raphael

G

$G$

P

$P$

G

$G$

P

$P$

G

$G$

Bem, mesmo a união de dois caminhos simples distintos pode criar um ciclo, de modo que calcular o MST faria você perder um dos caminhos, eu acho. Mas o acima exposto pode lhe dar algumas idéias.

Juho

k

$k$

existe alguma possibilidade de usar FSMs para representar caminhos e, em seguida, é possível realizar operações básicas como uniões, cruzamentos, subtrações, etc ... e também a operação de "compressão" de minimizar FSMs é bem compreendida / ideal e eficiente. não vi este feito em um papel, mas propõe-nos um outro problema um pouco semelhante ...

vzn

Respostas:

Um Trie pode fazer o truque: http://en.wikipedia.org/wiki/Trie

Rotule cada extremidade do seu gráfico com uma letra. Em seguida, adicione as strings que representam os caminhos através do seu gráfico para o teste. Para cumprir o requisito de que "nenhum outro caminho além dos selecionados seja representado", você pode deixar todos os vértices da árvore em branco e rotular as arestas, exceto quando as arestas que vão da raiz ao vértice representam um dos seus caminhos. rotule o vértice com algo. Um bool, o número do caminho sob alguma ordem, etc.

Depois de criar seu teste, existem algoritmos para compactá-lo para uma representação ótima (ou quase ótima). (veja o artigo vinculado da Wikipedia.)

Real John Connor
fonte

Interessante. No entanto, um trie vem com um conjunto muito maior de especificações com as quais eu realmente não me importo (pesquisa rápida, associação com uma chave etc.), por isso, me pergunto se algo melhor é possível ...

Opte

Talvez você deva dar uma olhada em estruturas de dados sucintas . São estruturas de dados que tentam armazenar informações no espaço próximo ao limite inferior da teoria da informação, preservando a capacidade de executar operações nelas.

Existem estruturas para árvores, dicionários etc. Não me lembro de nenhuma que faria exatamente o que você deseja, mas talvez alguma combinação ou modificação delas o ajudasse.

Jakub Kotowski
fonte

Dependendo da complexidade e do processamento pré / pós necessário para o seu algoritmo, talvez a opção mais simples seja essa. Você pode representá-los trivialmente como matrizes e salvá-los compactados em um HDF5. Esta biblioteca está equipada com alguns algoritmos de compactação rápidos, de modo que a leitura e gravação de dados compactados podem ser ainda mais rápidas que as não compactadas.

Aqui estão algumas parcelas:

Tempo de acesso sequencial por elemento para um EArray de 15 GB e tamanhos diferentes:

Velocidade de descompressão usando Blosc no PyTables: insira a descrição da imagem aqui

E, se eles forem delimitados em comprimento, você poderá armazená-los em uma tabela e, portanto, provavelmente ganhar um pouco mais de espaço. E ao recuperá-los da memória, você já os possui de uma forma muito conveniente para aplicar seu algoritmo.

Davidmh
fonte