1

Given these nodes:

a
b
c
d
e
f
g
h

And given some edges between the nodes like this:

a/b/c
b/c/d
c/e
c/d/e/f
c/g
f/g
e/f/g
a/c/h
h/a/b
c/a
d/b/c
f/g/c
d/a/f
g/f
g/a/b/c
f/a/b
e/a/c

(where a/b/c means one edge from a to b, and another one from b to c), so this describes a directed graph.

Here is another, more compact representation for the same graph:

a(b(c(d, e(f), g)))
f(g)
e(f(g), a(c))

...

using a tree-like representation. But there are still duplicates in there (e.g. a and c are shown twice in the last snippet).

Another way to represent it is like this:

a:b
a:c
b:c
c:d
c:e

But this uses even more letters than the original (first) snippet.

Wondering if there is anything better than these 3 approaches to represent a directed graph.

Maybe there is a way to assign numbers to the letters and do all 3 approaches as one. Or maybe something else.

So what could be a representation using the smallest amount of bytes?

closed as unclear what you're asking by gnat, Useless, Frank Hileman, Deduplicator, Erik Eidt Jun 30 '18 at 0:34

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • You only have 8 nodes, so you can trivially store a complete adjacency matrix in 64 bits. Does it need to be smaller than that? – Useless Jun 29 '18 at 16:31
  • No there would be billions of nodes, sorry this was just an example. – Lance Pollard Jun 29 '18 at 16:32
  • 1
    OK, so what representations have you already looked at? What properties does your graph have? Do you need edge weights or just connections? Do the edges have direction? What's the ratio of edges to vertices? – Useless Jun 29 '18 at 16:35
  • 3
    What does a/b/c, followed by b/c/d mean? Is the repeated b/c redundant or meaningful? – Erik Eidt Jun 29 '18 at 17:52
  • 4
    So you have seen other representations, but you don't like them for ... reasons. I don't know how you expect anyone to answer this question satisfactorily when it all your actual requirements are being drip-fed in comments, and your sample representations are so abstract I can't tell how big they would be. – Useless Jun 29 '18 at 17:59
3

Any directed graph with vertices V={v_1, ..., v_n} can be identified with a subset of

 S = V x V \ {(a,a) | a in V}

where V x V means the cartesian product, and each of these subsets represent a different graph. So this means there are 2^(n * (n-1)) different graphs over V. Thus, a uniform representation where each graph takes the same storage size requires necessarily n * (n-1) bits per graph. Less is not possible because of the pidgeon hole principle.

Of course, one can find a representation where some graphs over V need far less than n * (n-1) bits, but then others will need more. But without any knowledge about which graphs have to be processed or stored in context of a specific use case, or additional constraints (like a limited number of edges), one cannot decide which of these representations will need less or more bytes than another.

For example, one may develop representations where graphs with a smaller number of edges will take less space than graphs with a higher number. For a deeper analysis, you may find this thesis about compact and efficient representations of graphs helpful.

  • 1
    Just for completeness' sake: if instead of an arbitrary graph you have a DAG or a tree, there exist quite effective compression algorithms. – Giorgio Jun 30 '18 at 8:14

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