What structure to represent Directed Acyclic Graph in .NET?

Question

I'm considering representing a DAG as Dictionary(Of Integer, List(Of Integer)) Where the key will be a vertex ID and the List will contain all target vertices along edges.

I will use this structure later to:

derive lists of possible ascendant and descendant paths

derive lists of possible next paths and possible source paths

derive a list of leaf nodes

validate proposed edges between vertices

Topologically sort vertices

Is there some problem with my approach? How have you done it in the past? Thanks

EDIT
One issue with my approach is that finding source paths to vertices is an expensive operation, as it requires iteration over the entire dictionary. Perhaps it's in my interest to make a DAGVertex object exposing Targets and Sources

Answer 1

You can represent the graph as two dictionaries – one for incoming edges and one for outgoing ones. This will double the time to modify the graph and memory consumption, but lowers the time complexity of getting a list of edges coming to a certain vertex from O(V + E) to O(1).

Getting a list of leaf nodes could be done similarly – just have a list of current leaf nodes (or Dictionary(Of Integer, Boolean)). Add a node to it whenever it becomes a leaf node, and remove it if it stops being one.