Keywords: graph engine, multipartite graph, sparse matrix, CSR matrix, graph set algebra, custom DSL parser, recommendation system, fast pathfinding, Python, SciPy, NumPy.
A high-performance discrete graph analysis engine built with Python, NumPy, and SciPy. This project leverages Compressed Sparse Row (CSR) matrix representations to perform rapid set-algebra operations and pathfinding on large-scale multipartite graphs. It includes a built-in domain-specific language (DSL) parser to execute complex graph queries with a SQL-like where filtering layer.
- CSR Matrix Backend: Efficient memory layout and lightning-fast neighbor lookups via SciPy's sparse matrices.
- Vectorized Operations: Node filtering, intersections, and unions are executed using highly optimized NumPy functions (isin, intersect1d, union1d).
- Graph Set-Algebra DSL: A custom query language that supports operations like neig(), adjac(), union(), intersect(), diff(), and count().
- Dynamic Conditional Filtering: Filter runtime graph slices by node type labels and edge weight thresholds directly within the query.
- Optimized Pathfinding: Fast retrieval of intermediate 2-step and 3-step paths between specific entities.
This core class transforms a standard tabular pandas DataFrame into a bidirectional graph inside a single unified CSR matrix. Node types (e.g., Shop, Product, Supplier) are dynamically parsed out of prefixes (e.g., Shop_5) and stored in a specialized partitions array for O(1) mask indexing.
A recursive query interpreter that parses custom string expressions starting with the math prefix. It decouples the core graph mathematics from network overhead, executing logic layers at native C-speeds.
Every query must begin with the math prefix, followed by a set expression and an optional where clause.
| Function | Description | Example |
|---|---|---|
| neig(X) | Returns the immediate (1-hop) neighbors of set X. | math neig(Shop_5) |
| adjac(X) | Returns the 2-hop neighbors (neighbors of neighbors) of set X. | math adjac(Shop_5) |
| intersect(A, B) | Computes the intersection of set A and set B. | math intersect(neig(Shop_5), neig(Shop_6)) |
| union(A, B) | Computes the union of set A and set B. | math union(neig(Shop_5), neig(Shop_6)) |
| diff(A, B) | Computes the set difference (A \ B). Useful for gap analysis. | math diff(neig(Shop_5), neig(Shop_6)) |
| count(X) | Fast server-side aggregation returning the size of the set. | math count(union(neig(Shop_1), neig(Shop_2))) |
| path(A, B) | Finds transition paths up to 3 hops between nodes A and B. | math path(Shop_5, Shop_6) |
You can append conditional statements using the where keyword:
- label = 'PartitionName' — Include only specific node types.
- not label = 'PartitionName' — Exclude specific node types.
- edge_weight > value — Filter graph relationships based on minimal connection weights.
Ensure you have Python 3.8+ installed along with the required scientific computing libraries:
pip install numpy pandas scipy
import pandas as pd
from SetGrahEngine import MultipartiteSetGraphEngine, MathGraphQueryProcessor
data = { 'source': ['Shop_1', 'Shop_1', 'Supplier_1', 'Shop_2'], 'target': ['Product_A', 'Product_B', 'Product_A', 'Product_B'], 'weight': [5000.0, 12000.0, 9500.0, 3000.0]}
df = pd.DataFrame(data)
engine.build_from_df(df, source_col='source', target_col='target', weight_col='weight')
yet.query = "math diff(adjac(neig(Shop_1)), neig(Shop_1)) where label = 'Product'"result = processor.execute(query)
print("Recommended Products for Shop_1:", result)
When tested against a multipartite synthetic dataset containing 1,000,000 edges across various entity types (Shops, Suppliers, Products, Districts, Categories), execution times demonstrate high efficiency:
- Graph Build Time: ~0.70 seconds (1M records into CSR mapping) (p. 8).
- 1-Hop Neighbor Lookup: ~0.70 ms (p. 8).
- Assortment Gap Analysis (diff(adjac(...))): ~30.00 ms (p. 8).
- Set Intersection: ~0.43 ms (p. 8).
- Complex Multi-hop Pathfinding: ~16.28 ms (p. 8).