nxbench.validation package

Submodules

nxbench.validation.base module

Validation functions for graph algorithm benchmarking results.

exception nxbench.validation.base.ValidationError

Bases: Exception

Custom exception for validation failures.

nxbench.validation.base.validate_communities(result, graph, allow_overlap=False, min_community_size=None, check_connectivity=True)

Validate community detection results.

Parameters:

• result (list of sets) – List of node sets representing communities

• graph (nx.Graph or nx.DiGraph) – Original graph

• allow_overlap (bool, default=False) – Whether communities can overlap

• min_community_size (int, optional) – Minimum allowed community size

• check_connectivity (bool, default=True) – Whether to verify that communities are internally connected

Raises:

ValidationError – If validation fails

Return type:

None

nxbench.validation.base.validate_edge_scores(edge_scores, graph, score_range=(0.0, 1.0))

Validate edge scores for a given graph.

Parameters:

• edge_scores (dict) – Dictionary of edge scores where keys are tuples representing edges (u, v) and values are the scores associated with those edges.

• graph (networkx.Graph or networkx.DiGraph) – The graph for which the edge scores are being validated.

• score_range (tuple, default=(0.0, 1.0)) – The range (min, max) within which the edge scores should lie.

Raises:

ValidationError – If edge scores do not satisfy the expected conditions.

Return type:

None

nxbench.validation.base.validate_flow(result, graph, check_conservation=True, tolerance=1e-06)

Validate maximum flow results.

Parameters:

• result (tuple) – (flow_value, flow_dict) tuple from max flow algorithm

• graph (nx.Graph or nx.DiGraph) – Original graph

• check_conservation (bool, default=True) – Whether to verify flow conservation at all nodes

• tolerance (float, default=1e-6) – Numerical tolerance for flow conservation checks

Raises:

ValidationError – If validation fails

Return type:

None

nxbench.validation.base.validate_graph_result(result)

Validate graph algorithm results.

Return type:

None

Parameters:

result (Any)

nxbench.validation.base.validate_node_scores(result, graph, score_range=(0.0, 1.0), require_normalized=True, tolerance=1e-06, normalization_factor=None, scale_by_n=False)

Validate node-based scoring algorithms (e.g. centrality measures).

Parameters:

• result (dict) – Dictionary mapping nodes to scores

• graph (nx.Graph or nx.DiGraph) – Original graph

• score_range (tuple of float, default=(0.0, 1.0)) – Expected range for scores (min, max)

• require_normalized (bool, default=True) – Whether scores should be normalized

• tolerance (float, default=1e-6) – Numerical tolerance for floating point comparisons

• normalization_factor (float, optional) – Custom normalization factor to divide summed scores by. If provided, this takes precedence over scale_by_n.

• scale_by_n (bool, default=False) – Whether to scale expected sum by number of nodes. Some measures like betweenness centrality scale differently based on graph size.

Raises:

ValidationError – If validation fails

Return type:

None

Notes

The validation handles different normalization schemes:

1. Basic normalization (sum to 1.0)

2. Node count scaling (sum to n)

3. Custom normalization factor

4. No normalization

nxbench.validation.base.validate_path_lengths(result, graph, check_symmetry=False, allow_infinity=True)

Validate all-pairs shortest path lengths.

Parameters:

• result (dict of dict) – Dictionary mapping source nodes to dictionaries mapping target nodes to distances

• graph (nx.Graph or nx.DiGraph) – Original graph

• check_symmetry (bool, default=False) – Whether to verify that distances are symmetric (for undirected graphs)

• allow_infinity (bool, default=True) – Whether infinite distances are allowed for disconnected nodes

Raises:

ValidationError – If validation fails

Return type:

None

nxbench.validation.base.validate_scalar_result(result, graph, min_value=None, max_value=None)

Validate scalar result (e.g., float, int).

Return type:

None

Parameters:

• result (Any)

• graph (Graph | DiGraph)

• min_value (float | None)

• max_value (float | None)

nxbench.validation.base.validate_similarity_scores(result, graph, score_range=(0.0, 1.0), require_symmetric=True, tolerance=1e-06)

Validate link prediction similarity scores.

Parameters:

• result (iterable of tuples) – (node_u, node_v, score) tuples from similarity measure

• graph (nx.Graph or nx.DiGraph) – Original graph

• score_range (tuple of float, default=(0.0, 1.0)) – Expected range for similarity scores

• require_symmetric (bool, default=True) – Whether similarity scores should be symmetric

• tolerance (float, default=1e-6) – Numerical tolerance for comparisons

Raises:

ValidationError – If validation fails

Return type:

None

nxbench.validation.registry module

Integration of validation system with benchmark framework.

class nxbench.validation.registry.BenchmarkValidator(registry=None)

Bases: object

Handles validation for benchmark results.

Parameters:

registry (ValidationRegistry | None)

__init__(registry=None)

Initialize validator with optional registry.

Parameters:

registry (ValidationRegistry | None)

create_validator(algorithm_name, *, raise_errors=True)

Create a validator function for use with pytest.mark.benchmark.

Return type:

Callable[[Any, Graph | DiGraph], bool]

Parameters:

• algorithm_name (str)

• raise_errors (bool)

validate_result(result, algorithm_name, graph, *, raise_errors=True)

Validate algorithm result.

Return type:

bool

Parameters:

• result (Any)

• algorithm_name (str)

• graph (Graph | DiGraph)

• raise_errors (bool)

class nxbench.validation.registry.ValidationConfig(validator, params=<factory>, expected_type=None, required=True, extra_checks=<factory>)

Bases: object

Configuration for algorithm result validation.

Parameters:

• validator (Callable)

• params (dict[str, Any])

• expected_type (type | None)

• required (bool)

• extra_checks (set[str])

__init__(validator, params=<factory>, expected_type=None, required=True, extra_checks=<factory>)

Parameters:

• validator (Callable)

• params (dict[str, Any])

• expected_type (type | None)

• required (bool)

• extra_checks (set[str])

Return type:

None

expected_type: type | None = None

extra_checks: set[str]

params: dict[str, Any]

required: bool = True

validator: Callable

class nxbench.validation.registry.ValidationRegistry

Bases: object

Registry of validation configurations for algorithms.

DEFAULT_VALIDATORS: ClassVar[dict] = {'all_pairs_all_shortest_paths': ValidationConfig(validator=<function validate_path_lengths>, params={'check_symmetry': False, 'allow_infinity': True}, expected_type=<class 'dict'>, required=True, extra_checks=set()), 'all_pairs_bellman_ford_path': ValidationConfig(validator=<function validate_path_lengths>, params={'check_symmetry': False, 'allow_infinity': True}, expected_type=<class 'dict'>, required=True, extra_checks=set()), 'all_pairs_bellman_ford_path_length': ValidationConfig(validator=<function validate_path_lengths>, params={'check_symmetry': False, 'allow_infinity': True}, expected_type=<class 'dict'>, required=True, extra_checks=set()), 'all_pairs_dijkstra': ValidationConfig(validator=<function validate_path_lengths>, params={'check_symmetry': False, 'allow_infinity': True}, expected_type=<class 'dict'>, required=True, extra_checks=set()), 'all_pairs_dijkstra_path_length': ValidationConfig(validator=<function validate_path_lengths>, params={'check_symmetry': False, 'allow_infinity': True}, expected_type=<class 'dict'>, required=True, extra_checks=set()), 'all_pairs_shortest_path_length': ValidationConfig(validator=<function validate_path_lengths>, params={'check_symmetry': False, 'allow_infinity': True}, expected_type=<class 'dict'>, required=True, extra_checks=set()), 'average_clustering': ValidationConfig(validator=<function validate_scalar_result>, params={'min_value': 0.0, 'max_value': 1.0}, expected_type=<class 'float'>, required=True, extra_checks=set()), 'betweenness_centrality': ValidationConfig(validator=<function validate_node_scores>, params={'score_range': (0.0, 1.0), 'require_normalized': False}, expected_type=<class 'dict'>, required=True, extra_checks=set()), 'closeness_vitality': ValidationConfig(validator=<function validate_node_scores>, params={'score_range': (0.0, 1.0), 'require_normalized': False}, expected_type=<class 'dict'>, required=True, extra_checks=set()), 'edge_betweenness_centrality': ValidationConfig(validator=<function validate_edge_scores>, params={'score_range': (0.0, 1.0)}, expected_type=<class 'dict'>, required=True, extra_checks=set()), 'eigenvector_centrality': ValidationConfig(validator=<function validate_node_scores>, params={'score_range': (0.0, 1.0), 'require_normalized': False}, expected_type=<class 'dict'>, required=True, extra_checks=set()), 'jaccard_coefficient': ValidationConfig(validator=<function validate_similarity_scores>, params={'score_range': (0.0, 1.0), 'require_symmetric': True}, expected_type=<class 'list'>, required=True, extra_checks=set()), 'johnson': ValidationConfig(validator=<function validate_path_lengths>, params={'check_symmetry': False, 'allow_infinity': True}, expected_type=<class 'dict'>, required=True, extra_checks=set()), 'label_propagation_communities': ValidationConfig(validator=<function validate_communities>, params={'allow_overlap': False, 'check_connectivity': False}, expected_type=<class 'list'>, required=True, extra_checks=set()), 'local_efficiency': ValidationConfig(validator=<function validate_scalar_result>, params={'min_value': 0.0, 'max_value': 1.0}, expected_type=<class 'float'>, required=True, extra_checks=set()), 'louvain_communities': ValidationConfig(validator=<function validate_communities>, params={'allow_overlap': False, 'check_connectivity': True}, expected_type=<class 'list'>, required=True, extra_checks=set()), 'maximum_flow': ValidationConfig(validator=<function validate_flow>, params={'check_conservation': True}, expected_type=<class 'tuple'>, required=True, extra_checks=set()), 'number_of_isolates': ValidationConfig(validator=<function validate_scalar_result>, params={'min_value': 0}, expected_type=<class 'int'>, required=True, extra_checks=set()), 'pagerank': ValidationConfig(validator=<function validate_node_scores>, params={'score_range': (0.0, 1.0), 'require_normalized': False, 'tolerance': 1e-06}, expected_type=<class 'dict'>, required=True, extra_checks=set()), 'shortest_path': ValidationConfig(validator=<function validate_path_lengths>, params={'check_symmetry': False, 'allow_infinity': True}, expected_type=<class 'dict'>, required=True, extra_checks=set())}

__init__()

Initialize the registry with default validators.

get_validator(algorithm_name, *, required=True)

Get validator configuration for an algorithm.

Parameters:

• algorithm_name (str) – Name of algorithm

• required (bool, default=True) – Whether to raise error if no validator found

Returns:

Validator configuration if found

Return type:

ValidationConfig or None

Raises:

ValueError – If required=True and no validator found

load_config(path)

Load validator configurations from YAML file.

Parameters:

path (str or Path) – Path to YAML configuration file

Return type:

None

register_validator(algorithm_name, validator, **kwargs)

Register a new validator for an algorithm.

Parameters:

• algorithm_name (str) – Name of algorithm to validate

• validator (callable or ValidationConfig) – Validation function or config

• **kwargs (dict) – Additional parameters for ValidationConfig if validator is a callable

Raises:

ValueError – If validator configuration is invalid

Return type:

None

Module contents