این صفحه هنوز ترجمه نشده است؛ نسخهٔ انگلیسی نمایش داده میشود.
IRI.Maptor.Core.Graph
Graph data structures and algorithms for the Maptor stack, inspired by the graph chapters of CLRS (Introduction to Algorithms). Supports directed and undirected weighted graphs with the classic traversal, shortest-path, spanning-tree, and connectivity algorithms.
Installation
dotnet add package IRI.Maptor.Core.Graph
Features
- Adjacency-list representation (
AdjacencyList<TNode, TWeight>) with directed and undirected weighted edges, plus aDirectedAcyclicGraphtype; matrix-based algorithm variants accept aMatrixadjacency input - Traversal: breadth-first search (
BreadthFirstSearch) and depth-first search (DepthFirstSearch,FastDepthFirstSearch) with topological sort and cycle detection - Shortest paths: Dijkstra (
DijkstraProblem, adjacency-matrix input), Bellman-Ford (BellmanFordProblem,BellmanFordMatrixProblem; handles negative weights and detects negative cycles), Floyd-Warshall all-pairs (FloydWarshallProblem) - Minimum spanning tree: Kruskal (
MinimumSpanningTree.CalculateByKruskal) and Prim (PrimAlgorithm) - Strongly connected components (
GraphHelper.GetStronglyConnectedComponents) - Minimum cut (
MinimumCut.GetMinCut) and greedy clustering (GreedyClustering)
Usage
Build a graph and run BFS:
using IRI.Maptor.Core.Graph;
var g = new AdjacencyList<string, int>();
g.AddDirectedEdge("A", "B", 1);
g.AddDirectedEdge("A", "C", 1);
g.AddDirectedEdge("B", "D", 1);
g.AddDirectedEdge("C", "D", 1);
var bfs = new BreadthFirstSearch<string, int>(g, startNode: "A");
double level = bfs.GetLevel("D"); // 2
var path = bfs.GetPathTo("D"); // ["A", "B", "D"] or ["A", "C", "D"]
Bellman-Ford with negative weights:
var graph = new AdjacencyList<string, double>();
graph.AddDirectedEdge("A", "B", 4.0);
graph.AddDirectedEdge("B", "C", -3.0); // negative weight allowed
graph.AddDirectedEdge("C", "D", 5.0);
var bellmanFord = new BellmanFordProblem<string, double>(graph, "A");
if (!bellmanFord.HasNegativeCycle)
{
double distance = bellmanFord.GetDistance("D");
var path = bellmanFord.GetShortestPath("D");
}
Minimum spanning tree and strongly connected components:
var ug = new AdjacencyList<string, int>();
ug.AddUndirectedEdge("A", "B", 4);
ug.AddUndirectedEdge("A", "C", 1);
ug.AddUndirectedEdge("B", "C", 3);
var mstKruskal = MinimumSpanningTree.CalculateByKruskal<string, int>(ug);
var mstPrim = new PrimAlgorithm<string, int>(ug).GetMinimumSpanningTree();
// each inner list is one strongly connected component of a directed graph
var components = GraphHelper.GetStronglyConnectedComponents<string, int>(g);