patternMinor
Compact representation of paths in a graph
Viewed 0 times
representationpathsgraphcompact
Problem
I've a subset of the simple paths in a graph. The length of the paths is bounded by $d$.
What's the most compact way (memory-wise) I can represent the paths such that no other paths apart from the selected ones are represented?
Note that I want to use this representation in an algorithm that will iterate through this subset of paths over and over again and that I want to be fairly fast, so for instance, I can't use any standard compression algorithms.
One representation that came to my mind was representing them as a set of trees. I'm guessing though that getting it down to an optimal number of trees is NP-hard? What other representations would be good?
What's the most compact way (memory-wise) I can represent the paths such that no other paths apart from the selected ones are represented?
Note that I want to use this representation in an algorithm that will iterate through this subset of paths over and over again and that I want to be fairly fast, so for instance, I can't use any standard compression algorithms.
One representation that came to my mind was representing them as a set of trees. I'm guessing though that getting it down to an optimal number of trees is NP-hard? What other representations would be good?
Solution
A Trie might do the trick: http://en.wikipedia.org/wiki/Trie
Label each edge of your graph with a letter. Then add the strings which represent paths through your graph to the trie. To fulfill the requirement that "no other paths apart from the selected ones are represented" you could leave all vertices of the trie blank, and label the edges, except when the edges leading from the root to the vertex represent one of your paths, then label the vertex with something. A bool, the number of the path under some ordering, etc.
Once you have your trie built, there are algorithms for compressing it down to an optimal (or near optimal) representation. (see the linked Wikipedia article.)
Label each edge of your graph with a letter. Then add the strings which represent paths through your graph to the trie. To fulfill the requirement that "no other paths apart from the selected ones are represented" you could leave all vertices of the trie blank, and label the edges, except when the edges leading from the root to the vertex represent one of your paths, then label the vertex with something. A bool, the number of the path under some ordering, etc.
Once you have your trie built, there are algorithms for compressing it down to an optimal (or near optimal) representation. (see the linked Wikipedia article.)
Context
StackExchange Computer Science Q#23213, answer score: 4
Revisions (0)
No revisions yet.