0
$\begingroup$

This question appeared in an undergrad data structures final. The details are sound.

I need help to design a data structure for a directed graph with the following properties:

  1. Initialization should be done in O(1) time.
  2. AddVertex(id1,id2,...idK) - Add a new vertex to the graph. The new vertex is added with id=N+1 where N is the number of existing vertices. id1...idK are the neighbors of the new vertex, such that there is an outgoing edge from the new added vertex to each of the vertices id1 .. idK. This should be done in O(K) time.
  3. GetNumberOfNeighbors(id) - Return the number of outgoing edges for a vertex with a given id (id is in 1..N). This should be done in O(1) time.

All O(1) times are for worse case.

I know that the idea is to allocate a new array of K*constant length during the AddVertex method, and to copy K vertices to it in O(K) total, but I don't know how to do this exactly.

Thanks a lot

$\endgroup$
  • $\begingroup$ Seems like a big ask. Is $K$ constant? If not, there's no hope, as the $n$th vertex could have $n$ neighbours. Even if $K$ is constant, $O(1)$ worst-case access basically requires an array but even dynamic arrays are only amortized $O(1)$ for adding a new element, not $O(1)$ worst-case. $\endgroup$ – David Richerby Aug 9 at 14:37
  • $\begingroup$ Number of outgoing edges for each vertex is defined during its addition and never changes after that? Then, I think, it's trivial $\endgroup$ – HEKTO Aug 9 at 15:10
  • $\begingroup$ @DavidRicherby - Thanks for your comment. I fixed the question $\endgroup$ – Avi Tal Aug 9 at 19:18
  • $\begingroup$ @HEKTO - Yes. The number of outgoing edges never changes. Please share your solution if you can (as an answer perhaps). Thanks allot $\endgroup$ – Avi Tal Aug 9 at 19:39
  • $\begingroup$ Your problem formulation doesn't say anything about what you need to do with your graph, besides the request to return a vertex outdegree. So, you don't even need to store edges! Store the outdegree for each vertex, that's all. I think, you need to extend your question to include everything you need to do with your graph $\endgroup$ – HEKTO Aug 9 at 19:56
1
$\begingroup$

Make a Node class whose objects hold and an array of references to the other nodes they connects to. Make a Graph class whose objects store a dictionary mapping node IDs to nodes, and implement your 3 methods.

$\endgroup$
  • $\begingroup$ Can you please elaborate on how you can have a dictionary mapping in O(1) worse case access time without knowing the number of vertices in advance? Thanks $\endgroup$ – Avi Tal Aug 9 at 20:14
  • $\begingroup$ @AviTal Ah, so amortized O(1) isn't sufficient? What if you had a background process that does the expansions, preallocating extra space preemptively to ensure additions stay O(1)? $\endgroup$ – Alexander Aug 9 at 20:19
  • $\begingroup$ I updated the question according to your comments. Thanks $\endgroup$ – Avi Tal Aug 9 at 20:38
  • $\begingroup$ @AviTal I'm not sure if implementation details are on-topic on this site. It's meant for more general algorithm questions. May I ask why exactly O(1) worst case is so important? With large growth factors, array/hashmap resizes usually aren't a big deal. $\endgroup$ – Alexander Aug 9 at 21:41
  • $\begingroup$ The O(1) worse case is the requirement. I think that it is because a smart dictionary manipulation scheme is needed... If you can point me to the right forum to ask this, than I will ask it there. Thanks $\endgroup$ – Avi Tal Aug 9 at 21:51
0
$\begingroup$

So here is the solution (a little tricky):

Init()

Define a constant M=5. Initialize n - the number of vertices to be zero. Initialize 2 arrays A1 and A2 of length M and 2M using the known O(1) triple array "initialization" scheme.

AddVertex()

In each addition, if n < M, do A1[n] = K, and then n++. If n==M then do A2[n] = K, and copy A1[n-M] to A2[n-M] (one element), then do n++. After 2M additions, n==2M and all A1 elements were copied to the beginning of A2. Then do M = 2*M, allocate a new array of size 2*M and point array A1 to it. Keep alternating between A1 and A2 when n==2M again.

In the GetNumberOfNeighbors(id), test the relation between id and M, and choose the correct array (A1 or A2) accordingly.

Maybe someone will find this helpful some day...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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