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

Improve this question
$\endgroup$
8
  • $\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, 2019 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, 2019 at 15:10
  • $\begingroup$ @DavidRicherby - Thanks for your comment. I fixed the question $\endgroup$
    – Avi Tal
    Aug 9, 2019 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, 2019 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, 2019 at 19:56

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
7
  • $\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, 2019 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, 2019 at 20:19
  • $\begingroup$ I updated the question according to your comments. Thanks $\endgroup$
    – Avi Tal
    Aug 9, 2019 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, 2019 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, 2019 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...

Improve this answer
$\endgroup$

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.