QuickGraph.NETStandard 4.0.0

QuickGraph.NETStandard Examples

A comprehensive collection of examples demonstrating the capabilities of the QuickGraph.NETStandard library.

Overview

QuickGraph.NETStandard is a powerful graph data structure and algorithm library for .NET. These examples showcase various graph types, algorithms, visualization techniques, and real-world applications.

Prerequisites

• .NET 10 or later (for Examples project)
• .NET Standard 2.1 (for QuickGraph.NETStandard library)
• Optional: Graphviz for graph visualization

Installing Graphviz

To use the visualization features, install Graphviz:

Windows:

1. Download from https://graphviz.org/download/
2. Run installer and add to PATH
3. Restart your IDE

Linux:

sudo apt-get install graphviz  # Ubuntu/Debian
sudo yum install graphviz      # Fedora/RHEL

macOS:

brew install graphviz

Running the Examples

cd Examples
dotnet run

A menu-driven interface will guide you through all available examples.

Example Categories

1. Basic Graphs (Examples 1-4)

Learn fundamental graph data structures:

Example 1: Simple Directed Graph

• Concepts: Directed edges, vertex/edge addition, adjacency queries
• Use Case: One-way relationships (web links, citations, task dependencies)
• Key Methods: AddVertex(), AddEdge(), OutEdges(), InDegree()

Example 2: Undirected Graph

• Concepts: Bidirectional edges, symmetric relationships
• Use Case: Friendships, road networks, physical connections
• Key Methods: AdjacentEdges(), AdjacentDegree(), connectivity checks

Example 3: Bidirectional Graph

• Concepts: Directed graph with efficient reverse edge lookup
• Use Case: Web page navigation, dependency analysis
• Key Methods: OutEdges(), InEdges(), degree centrality

Example 4: Custom Edge Types

• Concepts: Edges with properties (weight, cost, capacity, labels)
• Use Case: Weighted graphs, cost optimization, flow networks
• Features: Custom edge classes with domain-specific data

2. Graph Algorithms (Examples 5-12)

Master essential graph algorithms:

Example 5: Shortest Path (Dijkstra)

• Algorithm: Dijkstra's shortest path
• Complexity: O((V + E) log V)
• Use Case: GPS navigation, network routing, delivery optimization
• Features: Weighted edges, path reconstruction, distance calculation

Example 6: Breadth-First Search (BFS)

• Algorithm: Level-order traversal
• Complexity: O(V + E)
• Use Case: Shortest path in unweighted graphs, level detection, web crawling
• Features: Discovery order, tree edges, level-by-level exploration

Example 7: Depth-First Search (DFS)

• Algorithm: Deep-first traversal with backtracking
• Complexity: O(V + E)
• Use Case: Cycle detection, pathfinding, maze solving
• Features: Discovery/finish times, tree/back edges, parenthesis theorem

Example 8: Topological Sort

• Algorithm: Dependency-ordered traversal
• Complexity: O(V + E)
• Use Case: Build systems, task scheduling, course prerequisites
• Features: DAG validation, parallel execution levels, cycle detection
• Note: Only works on Directed Acyclic Graphs (DAGs)

Example 9: Strongly Connected Components

• Algorithm: Tarjan's or Kosaraju's algorithm
• Complexity: O(V + E)
• Use Case: Community detection, circuit analysis, web page clustering
• Features: Component identification, reachability analysis

Example 10: Minimum Spanning Tree (Kruskal)

• Algorithm: Kruskal's MST with Union-Find
• Complexity: O(E log V)
• Use Case: Network design, cable routing, cost minimization
• Features: Minimum cost connectivity, forest to tree conversion

Example 11: Maximum Flow (Edmonds-Karp)

• Algorithm: Ford-Fulkerson with BFS
• Complexity: O(V � E�)
• Use Case: Network capacity, supply chain, bandwidth allocation
• Features: Flow distribution, bottleneck identification, residual networks

Example 12: Cycle Detection

• Algorithm: DFS-based back edge detection
• Complexity: O(V + E)
• Use Case: Deadlock detection, circular dependency resolution
• Features: Directed/undirected cycle detection, cycle path reconstruction

3. Visualization (Examples 13-15)

Create professional graph visualizations:

Example 13: Basic Visualization

• Format: DOT language (Graphviz)
• Outputs: PNG, SVG, PDF, etc.
• Features: Automatic layout, DOT file generation
• Tools: Integrates with Graphviz

Example 14: Styled Visualization

• Customization: Colors, shapes, labels, styles
• Features: Vertex formatting, edge styling, conditional formatting
• Use Case: State machines, workflow diagrams, network maps

Example 15: Hierarchical Layout

• Layouts: Top-to-bottom, left-to-right, etc.
• Use Case: Organizational charts, tree structures, class hierarchies
• Features: Rank direction, level-based coloring, shape differentiation

4. Real-World Scenarios (Examples 16-19)

Apply graph theory to practical problems:

Example 16: Social Network Analysis

• Features:
  • Influencer identification (degree centrality)
  • Community detection
  • Mutual friend discovery
  • Connection recommendations
• Algorithms: Degree centrality, path analysis
• Metrics: Network density, clustering coefficient

Example 17: Route Planning (GPS/Maps)

• Features:
  • Multi-criteria optimization (distance, time, cost)
  • Alternative route suggestions
  • Road type preferences
  • Real-time routing
• Algorithms: Dijkstra with custom cost functions
• Use Case: Navigation apps, delivery routing, trip planning

Example 18: Task Dependency Management

• Features:
  • Critical path analysis
  • Project duration calculation
  • Resource allocation
  • Parallel execution detection
• Algorithms: Topological sort, forward/backward pass
• Use Case: Project management, build systems, CI/CD pipelines

Example 19: Network Topology Analysis

• Features:
  • Redundancy checking
  • Single point of failure detection
  • Bandwidth capacity analysis
  • Failover simulation
• Algorithms: Multiple path finding, connectivity testing
• Use Case: Infrastructure planning, disaster recovery, network design

Code Structure

Examples/
??? Program.cs                          # Main menu application
??? BasicGraphs/
?   ??? SimpleDirectedGraphExample.cs
?   ??? UndirectedGraphExample.cs
?   ??? BidirectionalGraphExample.cs
?   ??? CustomEdgeTypesExample.cs
??? Algorithms/
?   ??? ShortestPathExample.cs
?   ??? BreadthFirstSearchExample.cs
?   ??? DepthFirstSearchExample.cs
?   ??? TopologicalSortExample.cs
?   ??? StronglyConnectedComponentsExample.cs
?   ??? MinimumSpanningTreeExample.cs
?   ??? MaximumFlowExample.cs
?   ??? CycleDetectionExample.cs
??? Visualization/
?   ??? BasicVisualizationExample.cs
?   ??? StyledVisualizationExample.cs
?   ??? HierarchicalLayoutExample.cs
??? RealWorldScenarios/
    ??? SocialNetworkExample.cs
    ??? RoutePlanningExample.cs
    ??? TaskDependencyExample.cs
    ??? NetworkTopologyExample.cs

Key Concepts

Graph Types

Common Operations

// Create graph
var graph = new AdjacencyGraph<string, Edge<string>>();

// Add vertices
graph.AddVertex("A");
graph.AddVertexRange(new[] { "B", "C", "D" });

// Add edges
graph.AddEdge(new Edge<string>("A", "B"));
graph.AddVerticesAndEdge(new Edge<string>("B", "C")); // Adds vertices if needed

// Query
int vertexCount = graph.VertexCount;
int edgeCount = graph.EdgeCount;
bool hasEdge = graph.ContainsEdge("A", "B");
int outDegree = graph.OutDegree("A");
IEnumerable<Edge<string>> edges = graph.OutEdges("A");

// Algorithms
var shortestPath = graph.ShortestPathsDijkstra(costFunc, "start");
var topologicalOrder = graph.TopologicalSort();
var components = graph.StronglyConnectedComponents(out var componentMap);

Custom Edge Types

public class WeightedEdge : Edge<string>
{
    public double Weight { get; set; }
    
    public WeightedEdge(string source, string target, double weight)
        : base(source, target)
    {
        Weight = weight;
    }
}

var graph = new AdjacencyGraph<string, WeightedEdge>();
graph.AddVerticesAndEdge(new WeightedEdge("A", "B", 5.0));

Performance Characteristics

Visualization Output

All visualization examples create two files:

1. .dot file - Text format that can be edited or processed
2. .png file - Visual representation (requires Graphviz)

Without Graphviz: Copy the DOT content to https://dreampuf.github.io/GraphvizOnline/

Common Patterns

Pattern 1: Weighted Shortest Path

var graph = new AdjacencyGraph<string, Edge<string>>();
var weights = new Dictionary<Edge<string>, double>();

// Add weighted edges
void AddWeightedEdge(string from, string to, double weight) {
    var edge = new Edge<string>(from, to);
    graph.AddVerticesAndEdge(edge);
    weights[edge] = weight;
}

// Find shortest path
Func<Edge<string>, double> costFunc = e => weights[e];
var tryGetPath = graph.ShortestPathsDijkstra(costFunc, "start");

if (tryGetPath("end", out var path)) {
    // Process path
}

Pattern 2: Graph Traversal with State

var visited = new HashSet<string>();
var dfs = new DepthFirstSearchAlgorithm<string, Edge<string>>(graph);

dfs.DiscoverVertex += vertex => {
    visited.Add(vertex);
    Console.WriteLine($"Discovered: {vertex}");
};

dfs.FinishVertex += vertex => {
    Console.WriteLine($"Finished: {vertex}");
};

dfs.Compute("start");

Pattern 3: Custom Visualization

var viz = new GraphvizAlgorithm<string, Edge<string>>(graph);

viz.FormatVertex += (sender, args) => {
    args.VertexFormatter.Label = args.Vertex;
    args.VertexFormatter.Shape = GraphvizVertexShape.Box;
    args.VertexFormatter.FillColor = GraphvizColor.LightBlue;
    args.VertexFormatter.Style = GraphvizVertexStyle.Filled;
};

viz.Generate(new FileDotEngine(), "output_file");

Additional Resources

• QuickGraph GitHub: https://github.com/deepakkumar1984/QuickGraph.NETStandard
• Graphviz Documentation: https://graphviz.org/documentation/
• Graph Theory: https://en.wikipedia.org/wiki/Graph_theory
• Algorithm Visualization: https://visualgo.net/en/graphds

Tips and Best Practices

1. Choose the Right Graph Type

   • Use AdjacencyGraph for directed relationships
   • Use UndirectedGraph for symmetric relationships
   • Use BidirectionalGraph when you need efficient reverse lookups

2. Memory Considerations

   • Large graphs can consume significant memory
   • Consider using value types for vertices when possible
   • Reuse edge instances when appropriate

3. Performance

   • Check graph properties before running expensive algorithms
   • Cache frequently accessed results
   • Use appropriate algorithms for your use case

4. Visualization

   • Keep graphs under 100 nodes for readable visualizations
   • Use colors and shapes to convey meaning
   • Consider hierarchical layouts for trees

5. Error Handling

   • Always check for cycles before topological sort
   • Verify graph connectivity when required
   • Handle cases where paths don't exist

Contributing

Feel free to add more examples or improve existing ones! Common additions might include:

• A* pathfinding
• Bellman-Ford algorithm
• Graph coloring
• Matching algorithms
• Planar graph testing

License

These examples are part of the QuickGraph.NETStandard project.