QuikGraph Documentation

repository·master·Indexed 19 days ago

https://github.com/kernelith/quikgraph

A high-performance, generic library for directed and undirected graph data structures and algorithms in .NET. A modernized fork of QuickGraph/YC.QuickGraph optimized for .NET Core, supporting algorithms such as DFS, BFS, A* Search, Shortest Path, Maximum Flow, and Minimum Spanning Tree. Compatible with .NET Standard >= 1.3, .NET Core >= 1.0, .NET Framework >= 3.5, and Unity 3D.

Tokens
6K
Snippets
14
Records
25
Agent score
67%

What's inside QuikGraph

  1. What is QuikGraph?

    master

    QuikGraph is a library providing generic directed and undirected graph data structures and algorithms for .NET. It is a cleaned and improved fork of YC.QuickGraph, modernized for .NET Core and available as clean NuGet packages.

    Key features include algorithms for:

    • Depth First Search (DFS)
    • Breadth First Search (BFS)
    • A* Search
    • Shortest Path
    • K-Shortest Path
    • Maximum Flow
    • Minimum Spanning Tree
  2. Overview of QuikGraph namespaces and capabilities

    master

    QuikGraph is a library providing graph data structures and a variety of graph algorithms.

    To use the library, you will primarily interact with two namespaces:

    • QuikGraph: Contains the core graph data structures.
    • QuikGraph.Algorithms: Contains the implementation of various algorithms such as shortest path finders, topological sorts, and Hamiltonian/Eulerian checks.
  3. Apply SOLID principles to design

    master

    Ensure your architecture adheres to the five SOLID principles:

    1. Single Responsibility Principle: A class should have only one reason to change. Use abstractions if a class is doing too much.
    2. Open/Closed Principle: Systems should be open for extension (via new implementations of interfaces) but closed to modification.
    3. Liskov Substitution Principle: Derived classes must be substitutable for their base classes without changing the fundamental nature of the abstraction.
    4. Interface Segregation Principle: Keep interfaces highly focused. If you find yourself implementing methods with NotImplementedException, decompose the interface.
    5. Dependency Inversion Principle: Inject external dependencies into classes, preferably via constructors.
  4. Use the Provider and Creational patterns

    master

    Provider (Strategy) Pattern

    Used heavily for defining contracts. Use specific suffixes to clarify intent:

    • Provider suffix: Use when the contract primarily allows the caller to get something.
    • Reader and Writer interfaces: If a contract allows both getting and setting, split it into two interfaces to clarify intent.

    Creational Patterns

    Use patterns when object creation involves significant logic:

    • Factory Pattern: When logic doesn't fit in a constructor.
    • Create semantics: For items built in a single step.
    • Build semantics: For items built up over multiple steps.

    Null Object Pattern

    When providing an implementation of an interface that does nothing, use the Null Object Pattern instead of returning null.

    // Decomposing a Provider into Reader/Writer
    public interface ICacheReader
    {
        bool TryGetObject(string key, out object value);
    }
    
    public interface ICacheWriter
    {
        void RemoveObjects(string keys);
        void RemoveObject(string key);
        void SetObject(string key, object obj);
        void InsertObject(string key, object value, DateTime absoluteExpiration, TimeSpan slidingExpiration);
    }
    
    // Null Object Pattern
    public interface ISomething
    {
        DateTime GetDateTime(string parameter);
    }
    
    public class NullSomething : ISomething
    {
        public DateTime GetDateTime(string parameter) => default(DateTime);
    }
  5. Configure Source Link for Debugging

    master

    QuikGraph supports Source Link, allowing you to debug directly into the source code. To enable this in your development environment, follow these steps:

    1. Uncheck the option "Enable Just My Code" in your IDE settings.
    2. Add the NuGet symbol server: https://symbols.nuget.org/download/symbols
    3. Check the option "Enable Source Link support".
  6. Initialize Arrays and Objects

    master

    Use concise syntax for initialization:

    • Arrays: Use the { ... } syntax for declaration-line initialization. If specifying a size, you must initialize elements individually.
    • Object Initializers: Use object initializers to simplify the creation of complex objects like List<T> or Dictionary<K, V>.
    // Array initialization
    string[] vowels1 = { "a", "e", "i", "o", "u" };
    var vowels2 = new string[] { "a", "e", "i", "o", "u" };
    
    // Object initializers
    var myObjects = new List<SomeObject>
    {
        new SomeObject("value1"),
        new SomeObject("value2"),
    };
    
    var studentById = new Dictionary<int, Student>
    {
        [123456] = new Student { Name = "John Doe", Age = 17 }
    };
  7. General C# coding rules and patterns

    master

    Follow these general guidelines to maintain code quality within the project:

    • Explicit Visibility: Always use explicit scope/visibility modifiers (e.g., public, private). Avoid relying on default access levels.
    • File Structure: Aim for one class per file, except for inner classes.
    • String Handling: Use string.Empty instead of empty quotes ("") where possible.
    • Method Length: Keep methods short (ideally 20-30 lines). Refactor into smaller, well-named methods if they exceed this.
    • Local Functions: Limit the use of captured variables from the enclosing method and keep local functions short.
    • Fail Fast / Exit Fast: Perform validation and early returns/exceptions at the top of the method to avoid deep nesting or unnecessary else clauses.
    • Avoid dynamic: Avoid the dynamic keyword, especially in performance-critical code, due to the high cost of dynamic dispatch.
    • KeyValuePair Naming: If you must pass values via KeyValuePair<TKey, TValue>, use a naming format like {keyName}And{valueName} (e.g., studentIdAndName).
    • Anonymous Type Formatting: Use explicit property names on anonymous types and place each property on a separate line.
    // Fail Fast pattern
    public void SomeMethod(ISomething something)
    {
        if (something is null)
            throw new ArgumentNullException(nameof(something));
    
        var things = _somethingElse.GetThoseThings();
        // ... logic continues without an else block
    }
    
    // Anonymous type formatting
    var anonymousObj = new
    {
        Property1 = sourceA.Property1,
        Property2 = sourceB.Property2
    };
  8. Manage static structures and dependencies

    master

    Static Member Access

    Call static members using the class name: ClassName.StaticMember. Do not qualify a static member defined in a base class with the name of a derived class.

    Testing Non-Idempotent Static Classes

    Avoid direct dependencies on static .NET classes that require infrastructure or are not idempotent (e.g., System.DateTime, System.IO.File). Instead, wrap them in a facade to enable controlled testing:

    1. Define an interface named I{StaticClassName}.
    2. Create a wrapper class named {StaticClassName}Wrapper that implements the interface and calls the static method.
    public interface IFile
    {
        bool Exists(string path);
    }
    
    public class FileWrapper : IFile
    {
        public bool Exists(string path)
        {
            return File.Exists(path);
        }
    }
  9. Best practices for LINQ queries

    master

    When writing LINQ queries in QuikGraph, follow these patterns to ensure readability and performance:

    • Prefer Method Syntax: Use method syntax (e.g., .Where(), .Select()) over query syntax.
    • Meaningful Naming: Use descriptive names for query variables (e.g., tolkienBooks instead of list).
    • Anonymous Type Aliasing: Use aliases in anonymous types to ensure property names follow Pascal casing.
    • Resolve Ambiguity: Rename properties in anonymous types if the resulting names (like Name or Id) are ambiguous.
    • Filter Early: Place Where clauses before other operations like OrderBy or Select to ensure subsequent operations work on a reduced dataset.
    • Explicit Typing: Prefer explicit typing for query and range variables unless the expression is excessively long.
    // Filter early and use meaningful names
    var tolkienBooks = books.Where(x => x.Author == "Tolkien")
                            .OrderBy(x => x.PublicationYear)
                            .Select(x => x.Name);
    
    // Use aliases to avoid ambiguity in anonymous types
    var booksInfo = books.Join(
        authors,
        book => book.Author,
        author => author.Name,
        (book, author) => new
        {
            BookName = book.Name,
            AuthorId = author.Id
        });
  10. Follow C# naming conventions

    master

    Use clear, descriptive names for all identifiers. Avoid double negatives in method names (e.g., avoid IsNotConnected if the method actually performs a connection attempt; use TryConnect instead).

    Generic Types:

    • Single generic type: Use T (e.g., ISomething<T>) unless a more precise name like TEdge is appropriate.
    • Multiple generic types: Use a capital T followed by a descriptive name (e.g., IService<TRequest, TResponse>).

    Suffixes and Enumerations:

    • Custom attributes must use the Attribute suffix.
    • Custom exceptions must use the Exception suffix.
    • Enumerations should be singular (e.g., FileMode) unless they represent bit flags using the [Flags] attribute (e.g., FileAttributes).
    // Bad: Double negative and misleading behavior
    private static bool IsNotConnected(SocketWrapper socket, string serverName) { ... }
    
    // Good: Clear intent
    private static bool TryConnect(SocketWrapper socket, string serverName) { ... }
    
    // Generics
    public interface ISomething<T>
    public interface IService<TRequest, TResponse>