# Constructing a directed graph for O(1) queries

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

• 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. – David Richerby Aug 9 at 14:37
• Number of outgoing edges for each vertex is defined during its addition and never changes after that? Then, I think, it's trivial – HEKTO Aug 9 at 15:10
• @DavidRicherby - Thanks for your comment. I fixed the question – Avi Tal Aug 9 at 19:18
• @HEKTO - Yes. The number of outgoing edges never changes. Please share your solution if you can (as an answer perhaps). Thanks allot – Avi Tal Aug 9 at 19:39
• 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 – HEKTO Aug 9 at 19:56

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.

• 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 – Avi Tal Aug 9 at 20:14
• @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)? – Alexander Aug 9 at 20:19
• I updated the question according to your comments. Thanks – Avi Tal Aug 9 at 20:38
• @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. – Alexander Aug 9 at 21:41
• 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 – Avi Tal Aug 9 at 21:51

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.