11
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ When "iterating through this subset", which information about each path do you need? Length? Visited nodes? Intersections with other paths? ... There can be $2^d$ many, so you have to be prepared for "not really fast" if you need to store whole paths. $\endgroup$
    – Raphael
    Commented Mar 29, 2014 at 11:57
  • $\begingroup$ I don't know if you are just given the paths by some unknown process or not, but perhaps you can do some bookkeeping while you are computing the paths of interest. Quick idea: let $G$ be the host graph, and set the weight of each edge to zero. When you find a path of interest $P$, increment the weight of each edge in $G$ that is in $P$. At the end, the edge weight tells in how many paths does that edge appear. Maybe you could now compute a minimum spanning tree of $G$, and drop all the edges with weight zero, or something like that. $\endgroup$
    – Juho
    Commented Mar 29, 2014 at 12:04
  • $\begingroup$ Well, even the union of two edge-disjoint simple paths can create a cycle, so computing the MST would make you lose one of the paths I guess. But the above might give you some ideas. $\endgroup$
    – Juho
    Commented Mar 29, 2014 at 12:10
  • 2
    $\begingroup$ You might want to check out Eppstein's paper on $k$ shortest paths, and the related literature. They deal with compact representations as well. $\endgroup$
    – Juho
    Commented Mar 29, 2014 at 12:13
  • $\begingroup$ there is some possibility of using FSMs to represent paths and then one can do basic operations like unions, intersections, subtractions, etc... and also the "compression" operation of minimizing FSMs is well understood/optimal and efficient. havent seen this done in a paper but proposed it on another somewhat similar problem... $\endgroup$
    – vzn
    Commented Mar 29, 2014 at 15:51

3 Answers 3

Reset to default
4
$\begingroup$

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.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Interesting. A trie however comes with a much larger set of specifications that I don't really care about (quick lookup, association with a key, etc.) so I wonder if something better is possible... $\endgroup$
    – Opt
    Commented Mar 31, 2014 at 3:30
2
$\begingroup$

Perhaps you should have a look at succinct data structures. They are data structures that attempt to store information in space close to the information-theoretic lower bound while still preserving the ability to perform operations on them.

There are such structures for trees, dictionaries, etc. I don't recall any that would do exactly what you want but perhaps some combination or modification of them would help you.

Improve this answer
$\endgroup$
1
$\begingroup$

Depending on the complexity and the pre/post processing required for your algorithm, perhaps the simplest option is the way. You could trivially represent them as arrays, and save them compressed in a HDF5. This library is equipped with some fast compression algorithms, so that reading and writing compressed data may be even faster than uncompressed.

Here are some plots:

Sequential access time per element for a 15 GB EArray and different chunksizes: http://pytables.github.io/_images/seq-chunksize-15GB.png

Decompression speed using Blosc on PyTables: enter image description here

And, if they are bounded in lenght, you could store them in a table, and thus probably gaining a bit more space. And when retrieving them from memory, you have them already in a very convenient form to apply your algorithm.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.