2
$\begingroup$

If I store a directed graph $G$ in adjacency list format, one can find all the out-neighbors $j$ of a given vertex $i$ in $\mathcal O(d)$ time, where $d$ is the max degree of the graph. These are all the vertices $j$ such that $(i,j)$ is an edge of $G$. On the other hand, if I want to find all the in-neighbors of $i$, i.e. the set of all vertices $j$: $(j,i)$ is an edge, then this takes $\mathcal O(n)$.

If I want to answer both in- and out-neighbor queries fast, I could just store the graph $G'$ obtained from $G$ by reversing all the edges, but that doubles memory usage. Is there a graph storage scheme for which both in- and out-neighbor queries take $\mathcal O(d)$ time, but doesn't require double the memory?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ if I want to find all the in-neighbors of i, i.e. the set of all vertices $j: (j,i)$ is an edge, then this takes $O(n)$. Are you sure? I don't think this is correct in adjacency list format. It must be $O(nd)$ $\endgroup$
    – orezvani
    May 30, 2014 at 3:08

2 Answers 2

Reset to default
2
$\begingroup$

If you care about constant factors, then big-Oh notation is not a useful tool to help you compare or measure possible data structures. If you want to minimize storage as much as possible, you need to think about the layout of the bits -- and then it would help to know concrete parameters and information, like roughly how big $n$ is, a rough estimate of the average degree (averaged over all vertices), a rough estimate of the largest degree and the distribution of degrees, etc.

For instance, one scheme is to represent the list of out-neighbors using something more efficient than a plain linked list (e.g., a linked list of buckets, where each bucket contains $c$ elements, and where you choose an optimal value of $c$ to minimize expected space usage). Or, you can pack these lists of out-neighbors and in-neighbors into a single big array, with each vertex having a pointer to the first index in that array where the sequence of out-neighbors or in-neighbors exist. You can also arrange that each entry needs only $\lceil \lg n \rceil$ bits, where $n$ is the number of vertices.

Another scheme is to use a multi-linked list as Patrick suggests, but with a slight twist. Instead of storing a pair of vertices $(a,b)$ in each linked-list node, store $a \oplus b$ (the xor of the identifier for vertex $a$ and the identifier for vertex $b$). This will be present in two linked lists: the out-neighbors of $a$, and the in-neighbors of $b$. Each linked-list node will have two next pointers. Notice that, when traversing the list of out-neighbors of $a$, all of the nodes will have $a$ as one of the two vertices, so if the value $x$ is stored in the node, we know it represents an edge to $a \oplus x$ (since $a \oplus (a \oplus b) = b$). Similarly, when traversing the list of in-neighbors of $b$, the value $x$ in a node represents an edge from the vertex $x \oplus b$. This doesn't reduce the number of pointers compared to a naive scheme, but it halves the amount of space for storing the data (the vertex identifiers) in each linked-list.

There are many more such bit-packing tricks and considerations that can be tried when you care about constant factors.

Improve this answer
$\endgroup$
0
$\begingroup$

I believe the best you can do without completely recreating the graph is a multi-linked list:

Assuming adjacency lists are the only structure that'll get you neighbors in $\mathcal{O}(d)$ time, you'll need one each for out- and in-neighbors. The same elements can be used by each list, so $(a,b)$ is both in the list of out-neighbors of $a$ and in-neighbors of $b$, but there will still be twice as many pointers as there are edges in the original graph.

Memory being a linear function of the number of edges, it's going to be of use mostly in sparse graphs.

EDIT: As D.W. shows below, this doesn't actually save any space.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I thought about this, but I don't think this helps. If you have a simple adjacency list for the out-neighbors of each vertex, then each list element needs space for one vertex and one next-pointer. (e.g., the list for vertex $v$ will contain $[w_1,w_2,\dots]$ if $w_1,w_2,\dots$ are $v$'s neighbors). That's space for exactly $|E|$ vertices and $|E|$ next-pointers in total across the graph, for the out-neighbors, or $2|E|$ vertices and $2|E|$ next-pointers in total for both in- and out-neighbors. $\endgroup$
    – D.W. ♦
    May 30, 2014 at 16:11
  • 1
    $\begingroup$ Your scheme is no better. Now each entry needs space for two vertices (both endpoints of the edge) and two next-pointers, so entries are double-sized; the total space usage is $2|E|$ vertices and $2|E|$ next-pointers across the entire graph, which is the same as the naive scheme. The reason is that, in your scheme, the list for the out-neighbors of $v$ now looks like $[(v,w_1),(v,w_2),\dots]$, so each element needs to hold both endpoint of the edge, even though one of them is already obvious from the fact that we're talking about out-neighbors of $v$. $\endgroup$
    – D.W. ♦
    May 30, 2014 at 16:12
  • $\begingroup$ OK, I've updated my answer with a scheme inspired by your idea, but tweaked so that it does actually save some space. Thank you for the idea. $\endgroup$
    – D.W. ♦
    Jun 2, 2014 at 7:33

Your Answer

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

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