Représentation compacte des chemins dans un graphique

J'ai un sous-ensemble des chemins simples dans un graphique. La longueur des chemins est délimitée par . $d$

Quelle est la manière la plus compacte (en termes de mémoire) que je peux représenter les chemins de sorte qu'aucun autre chemin en dehors de ceux sélectionnés ne soit représenté?

Notez que je veux utiliser cette représentation dans un algorithme qui itérera à travers ce sous-ensemble de chemins encore et encore et que je veux être assez rapide, donc par exemple, je ne peux pas utiliser d'algorithme de compression standard.

Une représentation qui m'est venue à l'esprit était de les représenter comme un ensemble d'arbres. Je suppose cependant que la réduction à un nombre optimal d'arbres est difficile à NP? Quelles autres représentations seraient bonnes?

graphs data-structures Opter
la source

Lorsque vous "parcourez ce sous-ensemble", de quelles informations sur chaque chemin avez-vous besoin? Longueur? Nœuds visités? Intersections avec d'autres chemins? ... Il peut y en avoir , vous devez donc être préparé pour "pas vraiment rapide" si vous avez besoin de stocker des chemins entiers.

2^{d}

$2^d$

Raphael

Je ne sais pas si les chemins vous sont simplement fournis par un processus inconnu ou non, mais vous pouvez peut-être faire de la comptabilité pendant que vous calculez les chemins qui vous intéressent. Idée rapide: soit le graphe hôte, et mettez le poids de chaque arête à zéro. Lorsque vous trouvez un chemin d'intérêt , augmenter le poids de chaque bord en qui est en . À la fin, le poids du bord indique combien de chemins ce bord apparaît. Peut-être pourriez-vous maintenant calculer un arbre couvrant minimum de , et supprimer tous les bords avec un poids zéro, ou quelque chose comme ça.

G

$G$

P

$P$

G

$G$

P

$P$

G

$G$

Juho

Eh bien, même l'union de deux chemins simples disjoints peut créer un cycle, donc le calcul du MST vous ferait perdre l'un des chemins je suppose. Mais ce qui précède pourrait vous donner quelques idées.

Juho

Vous pouvez consulter le document de Eppstein sur chemins les plus courts, et la documentation connexe. Ils traitent également de représentations compactes.

k

$k$

Juho

il y a une certaine possibilité d'utiliser des FSM pour représenter des chemins et ensuite on peut faire des opérations de base comme des unions, des intersections, des soustractions, etc ... et aussi l'opération de "compression" de minimisation des FSM est bien comprise / optimale et efficace.

Je n'ai pas

Réponses:

Un Trie pourrait faire l'affaire: http://en.wikipedia.org/wiki/Trie

Étiquetez chaque bord de votre graphique avec une lettre. Ajoutez ensuite les chaînes qui représentent les chemins à travers votre graphique au trie. Pour répondre à l'exigence selon laquelle "aucun autre chemin que ceux sélectionnés n'est représenté", vous pouvez laisser tous les sommets du trie en blanc et étiqueter les bords, sauf lorsque les bords menant de la racine au sommet représentent l'un de vos chemins, puis étiqueter le sommet avec quelque chose. Un booléen, le numéro du chemin sous une certaine commande, etc.

Une fois que vous avez construit votre trie, il existe des algorithmes pour le compresser jusqu'à une représentation optimale (ou presque optimale). (voir l'article Wikipédia lié.)

Real John Connor
la source

Intéressant. Un trie est cependant livré avec un ensemble de spécifications beaucoup plus important dont je ne me soucie pas vraiment (recherche rapide, association avec une clé, etc.), donc je me demande si quelque chose de mieux est possible ...

Opt

Vous devriez peut-être jeter un œil aux structures de données succinctes . Ce sont des structures de données qui tentent de stocker des informations dans un espace proche de la borne inférieure de la théorie de l'information tout en conservant la possibilité d'effectuer des opérations sur elles.

Il existe de telles structures pour les arbres, les dictionnaires, etc. Je ne m'en souviens pas qui feraient exactement ce que vous voulez, mais peut-être qu'une combinaison ou une modification de celles-ci vous aiderait.

Jakub Kotowski
la source

Selon la complexité et le pré / post-traitement requis pour votre algorithme, l'option la plus simple est peut-être le chemin. Vous pouvez les représenter trivialement sous forme de tableaux et les enregistrer compressés dans un HDF5. Cette bibliothèque est équipée de quelques algorithmes de compression rapides, de sorte que la lecture et l'écriture de données compressées peuvent être encore plus rapides que non compressées.

Voici quelques parcelles:

Temps d'accès séquentiel par élément pour une baie EA de 15 Go et différentes tailles de blocs:

Vitesse de décompression à l'aide de Blosc sur PyTables: entrez la description de l'image ici

Et, s'ils sont limités en longueur, vous pouvez les stocker dans une table, et gagner ainsi probablement un peu plus d'espace. Et lorsque vous les récupérez de la mémoire, vous les avez déjà sous une forme très pratique pour appliquer votre algorithme.

Davidmh
la source