Deutsch

petgraph_ext

Downloads

285

GitHub-Sterne

4

Erweiterungs-Repository auf GitHub

Graphalgorithmen für DuckDB — PageRank, kürzester Pfad, SCC, MST und mehr über petgraph

Maintainer: alitrack

Installation und Laden

INSTALL petgraph_ext FROM community;
LOAD petgraph_ext;

Beispiel

INSTALL petgraph_ext FROM community;
LOAD petgraph_ext;
SELECT * FROM petgraph_shortest_path('[(0,1,2.5),(1,2,1.0),(0,2,5.0)]', 0, 2);
-- → [0,1,2]  3.5

Über petgraph_ext

duckdb_petgraph

Eine DuckDB-Erweiterung, die Graphalgorithmen nach SQL bringt, angetrieben von der Rust-Crate petgraph. Führen Sie PageRank, Betweenness Centrality, Closeness Centrality, Eigenvector Centrality, SCC, Louvain-Community-Detection, topologische Sortierung, Zyklenerkennung, kürzesten Pfad, Zusammenhangskomponenten und MST aus — ohne externe Graphdatenbank.

Funktionen

  • 17 Tabellenfunktionen: build_graph, list_graphs, drop_graph, edges, neighbors, shortest_path, connected_components, pagerank, betweenness_centrality, closeness_centrality, eigenvector_centrality, scc, mst, louvain, toposort, is_cyclic
  • Benannter Graph-Cache: einmal mit petgraph_build_graph('name', ...) aufbauen und mit @name referenzieren für wiederholte Abfragen ohne erneutes Parsen
  • Multi-Batch-Streaming: alle mehrzeiligen Funktionen streamen Ergebnisse über Scan- Aufrufe — keine künstliche 2048-Zeilen-Obergrenze
  • Kantenformat: String-Syntax [(src,dst,weight),...], inline verwendbar oder aus DuckDB-Tabellen über string_agg aufgebaut

Algorithmen

Function Description
petgraph_shortest_path A*-kürzester Pfad mit Pfadrekonstruktion
petgraph_connected_components DFS-Komponentenbeschriftung (ungerichtet)
petgraph_pagerank PageRank mit konfigurierbarem Alpha/Iterationen
petgraph_betweenness_centrality Brandes-Algorithmus (ungerichtet)
petgraph_closeness_centrality BFS-basierte Closeness (gerichtet)
petgraph_eigenvector_centrality Power-Iteration-Eigenvektor
petgraph_scc Tarjans stark zusammenhängende Komponenten
petgraph_louvain Louvain-Community-Detection
petgraph_toposort Kahns topologische Sortierung
petgraph_is_cyclic Gerichtete Zyklenerkennung
petgraph_mst Kruskals minimaler Spannbaum

Einschränkungen

  • Graphen müssen in den Speicher passen (kein festplattenbasiertes Speichern)
  • Louvain ist ein vereinfachter Greedy-Durchlauf mit 20 Iterationen — nützlich für schnelle Community-Detection, aber keine vollständige Implementierung
  • Kantengewichte sind nur f64
  • Knoten-IDs sind i32

Hinzugefügte Funktionen

function_name function_type description comment examples
petgraph_betweenness_centrality table NULL NULL
petgraph_build_graph table NULL NULL
petgraph_build_graph_list table NULL NULL
petgraph_closeness_centrality table NULL NULL
petgraph_connected_components table NULL NULL
petgraph_drop_graph table NULL NULL
petgraph_edges table NULL NULL
petgraph_eigenvector_centrality table NULL NULL
petgraph_is_cyclic table NULL NULL
petgraph_list_graphs table NULL NULL
petgraph_louvain table NULL NULL
petgraph_mst table NULL NULL
petgraph_neighbors table NULL NULL
petgraph_pagerank table NULL NULL
petgraph_scc table NULL NULL
petgraph_shortest_path table NULL NULL
petgraph_toposort table NULL NULL

Überladene Funktionen

Diese Erweiterung fügt keine Funktionsüberladungen hinzu.

Hinzugefügte Typen

Diese Erweiterung fügt keine Typen hinzu.

Hinzugefügte Einstellungen

Diese Erweiterung fügt keine Einstellungen hinzu.