🔍 Code Extractor

Validates whether a directed graph represents a one-to-one mapping by checking if each node maps to exactly one unique edge and vice versa.

Purpose

This function determines if a directed graph contains only bijective (one-to-one) mappings between nodes. It verifies that the graph structure represents a perfect matching where each node has exactly one outgoing edge and each node is the target of exactly one edge. This is useful for validating data transformations, checking mapping consistency, or ensuring proper graph structure in data processing pipelines.

Source Code

def one_to_one(graph, nodes):
    """
    Return True if graph contains only one to one mappings. The
    directed graph should be represented as a dictionary mapping of
    edges for each node. Nodes should be passed a simple list.
    """
    edges = itertools.chain.from_iterable(graph.values())
    return len(graph) == len(nodes) and len(set(edges)) == len(nodes)

Parameters

Parameter Details

graph: A dictionary representing a directed graph where keys are source nodes and values are iterables (lists, tuples, etc.) of target nodes/edges. Each key-value pair represents the outgoing edges from a node. Example: {'A': ['B'], 'C': ['D']}

nodes: A simple list or iterable containing all nodes that should be present in the graph. This should include both source and target nodes. The function checks if the number of unique edges equals the number of nodes provided.

Return Value

Returns a boolean value: True if the graph represents a one-to-one mapping (bijection) where the number of graph entries equals the number of nodes AND the number of unique edges equals the number of nodes; False otherwise. This ensures each node appears exactly once as a source and once as a target.

Dependencies

• itertools

Required Imports

import itertools

Usage Example

import itertools

def one_to_one(graph, nodes):
    edges = itertools.chain.from_iterable(graph.values())
    return len(graph) == len(nodes) and len(set(edges)) == len(nodes)

# Example 1: Valid one-to-one mapping
graph1 = {'A': ['B'], 'C': ['D']}
nodes1 = ['A', 'B', 'C', 'D']
result1 = one_to_one(graph1, nodes1)
print(f"Graph1 is one-to-one: {result1}")  # True

# Example 2: Invalid - multiple edges to same node
graph2 = {'A': ['B'], 'C': ['B']}
nodes2 = ['A', 'B', 'C']
result2 = one_to_one(graph2, nodes2)
print(f"Graph2 is one-to-one: {result2}")  # False

# Example 3: Invalid - node count mismatch
graph3 = {'A': ['B']}
nodes3 = ['A', 'B', 'C']
result3 = one_to_one(graph3, nodes3)
print(f"Graph3 is one-to-one: {result3}")  # False

Best Practices

• Ensure the 'nodes' parameter includes all nodes in the graph, both sources and targets
• The graph dictionary values should be iterables (lists, tuples, sets) even for single edges
• This function assumes the graph is directed; undirected graphs should be converted first
• The function does not validate that all nodes in the list are actually present in the graph structure
• For large graphs, consider that itertools.chain.from_iterable creates an iterator that is consumed when converted to a set, so the function has O(n) space complexity
• Empty graphs and empty node lists will return True (vacuous truth), so validate inputs if this is not desired behavior

Tags

Similar Components

AI-powered semantic similarity - components with related functionality:

• function is_cyclic 49.8% similar

  Detects whether a directed graph contains a cycle using depth-first search with path tracking.

  From: /tf/active/vicechatdev/patches/util.py

• function node_exists 43.4% similar

  Checks if a node with a specific UID exists in a Neo4j graph database by querying for the node and returning a boolean result.

  From: /tf/active/vicechatdev/CDocs/db/db_operations.py

• function check_node_exists 40.6% similar

  Checks if a node with a specified label and matching properties exists in a Neo4j graph database.

  From: /tf/active/vicechatdev/CDocs/db/db_operations.py

• function get_unique_keys 40.5% similar

  Extracts unique key values from an ndmapping object for specified dimensions, returning an iterator of unique tuples.

  From: /tf/active/vicechatdev/patches/util.py

• function validate_schema 40.5% similar

  Validates that a Neo4j database schema contains all required constraints and node labels for a controlled document management system.

  From: /tf/active/vicechatdev/CDocs/db/schema_manager.py