Doubly Connected Graph Interface Desgin

I have a directed graph (DAG) with nodes of several types.
Each type has its own implementation of Ensure Outgoing Link, which adds another node to the list of outgoing nodes.

This graph is doubly connected, so Ensure Outgoing Link also calls Ensure Incoming Link which adds the reverse link so that the graph can be traversed in either direction.

Ensure Incoming Link does not call Ensure Outgoing Link, as that would create a circle. So the problem is trying to stop consumers of the nodes from calling Ensure Incoming Link (as that would create an incomplete graph), while still allowing the implementation of the Node to call it.

Solutions I see are to either:

1. Have the graph data structure itself do all the link management
2. Or to have the node cast itself from the interface to the actual class.
3. Or to comment or name the Ensure Incoming Link so no one else uses it.

The only issue with having the graph object do it is that each type of node has their own slightly different version of adding an outgoing node, so it still needs to have a method which could be called externally if I'm not careful.

What would be a good design here?