Skip to content

edge-orientation.md

Latest commit

 

History

History
108 lines (77 loc) · 3.47 KB

edge-orientation.md

File metadata and controls

108 lines (77 loc) · 3.47 KB

Static Edge Orientation (HeiOrient)

Original Repository: https://github.com/HeiOrient/HeiOrient

Overview

HeiOrient orients the edges of an undirected graph to minimize the maximum out-degree of any vertex. The optimal maximum out-degree equals the arboricity of the graph, defined as:

arboricity(G) = max over all subgraphs H of ceil(|E(H)| / (|V(H)| - 1))

Low out-degree orientations enable:

  • Space-efficient adjacency queries (each vertex stores only its out-neighbors)
  • Fast triangle enumeration (enumerate triangles in O(m * arboricity) time)
  • Compact graph representations for streaming and distributed settings

Three algorithms are available:

Algorithm Guarantee Speed Description
"two_approx" 2-approximation Fast Greedy orientation
"dfs" Heuristic Medium DFS-based local search improvement
"combined" Best quality Slower Combines greedy + DFS refinement

Orientation.orient_edges()

Signature

Orientation.orient_edges(
    g: Graph,
    algorithm: str = "combined",
    seed: int = 0,
    eager_size: int = 100,
) -> EdgeOrientationResult

Parameters

Parameter Type Default Description
g Graph required Input undirected graph.
algorithm str "combined" Algorithm: "two_approx", "dfs", or "combined".
seed int 0 Random seed for reproducibility.
eager_size int 100 Maximum path length for the eager path search heuristic (used by "combined").

Returns

EdgeOrientationResult

Field Type Description
max_out_degree int Maximum out-degree achieved across all vertices.
out_degrees np.ndarray (int32) Out-degree of each vertex.
edge_heads np.ndarray (int32) Head (target) of each oriented edge (same length as g.adjncy).

Exceptions

Exception Condition
InvalidModeError algorithm is not one of the valid choices.

Example

from chszlablib import Graph, Orientation

g = Graph.from_metis("graph.graph")

# Best quality orientation
result = Orientation.orient_edges(g, algorithm="combined")
print(f"Max out-degree: {result.max_out_degree}")
print(f"Out-degrees: {result.out_degrees}")

# Fast 2-approximation
fast = Orientation.orient_edges(g, algorithm="two_approx")
print(f"Fast max out-degree: {fast.max_out_degree}")

Performance Disclaimer

This Python interface wraps the HeiOrient C++ library via pybind11. While convenient for prototyping and integration into Python workflows, there is inherent overhead from the Python/C++ boundary and data conversion. For maximum performance on large-scale instances, use the original C++ implementation directly from the HeiOrient repository.

References

@inproceedings{DBLP:conf/esa/Reinstadtler0U24,
  author    = {Henrik Reinst{\"{a}}dtler and Christian Schulz and Bora U{\c{c}}ar},
  title     = {Engineering Edge Orientation Algorithms},
  booktitle = {32nd Annual European Symposium on Algorithms, {ESA} 2024},
  series    = {LIPIcs},
  volume    = {308},
  pages     = {97:1--97:18},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2024},
  doi       = {10.4230/LIPIcs.ESA.2024.97}
}