Graph Theory in C#

Graph theory applications in C#

In the realm of C# programming, many tasks revolve around flat collections such as filtering, sorting, and looking up items by key. These operations are efficiently handled by LINQ and dictionaries. However, some problems involve relationships among entities, which flat collections struggle to address effectively.

Consider scenarios like determining inherited permissions through nested role groups, identifying build targets that require rebuilding due to changes in a specific file, locating accounts linked directly or indirectly to a flagged account, or determining the shortest chain of referrals between two users. These are all reachability questions that graph search algorithms can solve.

To understand graph search, it's essential to grasp the basic concepts. A graph consists of nodes connected by edges. In an undirected graph, an edge runs in both directions, meaning if Alice and Bob are friends, each considers the other a friend. In a directed graph, edges have a one-way relationship, such as when module A imports module B, which doesn't imply the reverse.

This distinction is crucial, as incorrectly implementing it leads to common bugs in hand-rolled graph code. Traversing the graph means visiting nodes by following edges. Two primary traversal orders exist: Breadth-first search (BFS) and Depth-first search (DFS). BFS expands outward in rings, visiting everything one hop away before moving to the next level, making it suitable for finding the shortest path by hop count.

DFS, on the other hand, explores one branch as far as possible before backtracking, making it ideal for cycle detection, topological sorting, and any scenario requiring knowledge of when a subtree is fully explored.

Dijkstra's algorithm and A* are extensions of these concepts that handle graphs with varying edge costs but are beyond the scope of this discussion. To represent a graph in C#, an adjacency list is commonly used. This data structure maps each node to a set of nodes it connects to, making it memory-efficient for sparse graphs, which are typical in real-world scenarios compared to adjacency matrices.

When implementing a graph in C#, several considerations are worth noting:

- Use `HashSet` for neighbors instead of `List` to avoid storing duplicate edges, which can inflate traversal costs and skew calculations of node degrees.

- Make the `AddEdge` method bidirectional by default, with an option to specify a non-bidirectional graph explicitly. This clarity at the call site prevents overlooking handling of directed graphs.

- Ensure both nodes are registered as keys in the dictionary; otherwise, starting a traversal from one node will yield no results.

- Allow for an optional `IEqualityComparer` to handle nodes as case-insensitive strings, such as treating "Alice" and "alice" as the same person. This flexibility should be managed by the caller rather than the data structure itself.

To implement breadth-first search (BFS), a queue is utilized. Nodes are enqueued and dequeued in a first-in-first-out manner, ensuring each node is visited exactly once by checking a visited set. This approach guarantees the shortest path in terms of the number of edges.

In contrast, depth-first search (DFS) employs a stack, either explicitly or through recursion. While the recursive version offers cleaner code, it poses a risk of a `StackOverflowException` when dealing with long paths, as the call stack grows with the path length. To circumvent this issue, an explicit stack data structure can be used, moving frames to the heap and eliminating stack overflow as a failure mode.