Graph Node

A GraphNode provides a simple node-based representation for basic graph structures. Each node contains a value and maintains a list of neighboring nodes, making it ideal for simple graph operations and learning graph concepts.

Overview

GraphNode is a lightweight implementation for representing individual nodes in a graph. Unlike the full Graph implementations, it focuses on simple node-to-node relationships without advanced graph operations. This makes it ideal for basic graph structures, learning purposes, or as building blocks for custom graph implementations.

Features

• Simple design - minimal overhead with just value and neighbors
• Direct connections - neighbors stored as a simple list for easy access
• Flexible values - can store any type of data as the node value
• Basic operations - add and remove neighbors with automatic duplicate prevention
• Memory efficient - no overhead from graph-wide data structures
• Educational - perfect for learning graph concepts and algorithms
• Building blocks - can be used to construct custom graph implementations
• Type agnostic - works with any hashable value type

Time Complexities

Operation	Time Complexity	Description
Create Node	O(1)	Instantiate with value
Add Neighbor	O(n)	Check for duplicates in neighbor list
Remove Neighbor	O(n)	Search and remove from neighbor list
Check Neighbor	O(n)	Linear search through neighbor list
Get Neighbors	O(1)	Direct access to neighbor list
Get Value	O(1)	Direct access to node value

Space Complexity: O(n) where n is the number of neighbors

Basic Usage

Creating and Initializing

from algo.data_structs.graphs import GraphNode

# Create nodes with different value types
person_node = GraphNode("Alice")
number_node = GraphNode(42)
data_node = GraphNode({"id": 1, "name": "Server"})

print(f"Person node: {person_node}")     # GraphNode(Alice)
print(f"Value: {person_node.value}")     # Alice
print(f"Neighbors: {person_node.neighbors}")  # []

# Node values can be any type
boolean_node = GraphNode(True)
tuple_node = GraphNode((1, 2, 3))
list_node = GraphNode([1, 2, 3])

print(f"Boolean node value: {boolean_node.value}")  # True
print(f"Tuple node value: {tuple_node.value}")      # (1, 2, 3)

Understanding Node Relationships

# Nodes start with no connections
node_a = GraphNode('A')
node_b = GraphNode('B')

print(f"A's neighbors: {len(node_a.neighbors)}")  # 0
print(f"B's neighbors: {len(node_b.neighbors)}")  # 0

# Connections are directional by default
node_a.add_neighbor(node_b)
print(f"A's neighbors: {len(node_a.neighbors)}")  # 1
print(f"B's neighbors: {len(node_b.neighbors)}")  # 0

# For bidirectional connections, add both directions
node_b.add_neighbor(node_a)
print(f"A's neighbors: {len(node_a.neighbors)}")  # 1
print(f"B's neighbors: {len(node_b.neighbors)}")  # 1

Adding and Managing Neighbors

# Create a small network
alice = GraphNode("Alice")
bob = GraphNode("Bob")
carol = GraphNode("Carol")
david = GraphNode("David")

# Add neighbors (connections)
alice.add_neighbor(bob)
alice.add_neighbor(carol)
bob.add_neighbor(david)

print(f"Alice's friends: {len(alice.neighbors)}")  # 2
print(f"Bob's friends: {len(bob.neighbors)}")      # 1

# Adding same neighbor again doesn't create duplicate
alice.add_neighbor(bob)
print(f"Alice's friends after duplicate: {len(alice.neighbors)}")  # Still 2

# Access neighbor nodes
print("Alice's connections:")
for neighbor in alice.neighbors:
    print(f"  → {neighbor.value}")

# Check if a specific node is a neighbor
is_neighbor = bob in alice.neighbors
print(f"Bob is Alice's neighbor: {is_neighbor}")  # True

Removing Neighbors

# Remove connections
alice.add_neighbor(david)  # Add David as Alice's friend
print(f"Alice's friends: {len(alice.neighbors)}")  # 3

alice.remove_neighbor(david)
print(f"Alice's friends after removing David: {len(alice.neighbors)}")  # 2

# Removing non-existent neighbor is safe (no error)
alice.remove_neighbor(david)  # Safe to call again
print(f"Alice's friends after safe removal: {len(alice.neighbors)}")  # Still 2

# Check remaining connections
remaining_friends = [neighbor.value for neighbor in alice.neighbors]
print(f"Alice's remaining friends: {remaining_friends}")

Basic Node Operations

from algo.data_structs.graphs import GraphNode

# Create nodes with different value types
person_node = GraphNode("Alice")
number_node = GraphNode(42)
data_node = GraphNode({"id": 1, "name": "Server"})

print(f"Person node: {person_node}")  # GraphNode(Alice)
print(f"Value: {person_node.value}")  # Alice
print(f"Neighbors: {person_node.neighbors}")  # []

Building a Simple Network

# Create a small social network
alice = GraphNode("Alice")
bob = GraphNode("Bob")
carol = GraphNode("Carol")
david = GraphNode("David")

# Add friendships (bidirectional)
alice.add_neighbor(bob)
bob.add_neighbor(alice)

alice.add_neighbor(carol)
carol.add_neighbor(alice)

bob.add_neighbor(david)
david.add_neighbor(bob)

carol.add_neighbor(david)
david.add_neighbor(carol)

# Explore the network
print(f"Alice's friends: {[str(friend) for friend in alice.neighbors]}")
print(f"David's friends: {[str(friend) for friend in david.neighbors]}")

# Check mutual connections
mutual_friends = set(alice.neighbors) & set(david.neighbors)
print(f"Alice and David's mutual friends: {[str(friend) for friend in mutual_friends]}")

Tree-like Structure

# Build a simple organizational hierarchy
ceo = GraphNode("CEO")
cto = GraphNode("CTO")
cfo = GraphNode("CFO")
dev_manager = GraphNode("Dev Manager")
qa_manager = GraphNode("QA Manager")

# Build hierarchy (directed relationships)
ceo.add_neighbor(cto)
ceo.add_neighbor(cfo)
cto.add_neighbor(dev_manager)
cto.add_neighbor(qa_manager)

# Traverse the hierarchy
def print_hierarchy(node, level=0):
    indent = "  " * level
    print(f"{indent}{node.value}")
    for subordinate in node.neighbors:
        print_hierarchy(subordinate, level + 1)

print("Organizational Structure:")
print_hierarchy(ceo)

Node Manipulation

# Create a dynamic network
hub = GraphNode("Hub")
node1 = GraphNode("Node1")
node2 = GraphNode("Node2")
node3 = GraphNode("Node3")

# Add connections
hub.add_neighbor(node1)
hub.add_neighbor(node2)
hub.add_neighbor(node3)

print(f"Hub connections: {len(hub.neighbors)}")

# Adding same neighbor again doesn't create duplicate
hub.add_neighbor(node1)
print(f"Hub connections after duplicate add: {len(hub.neighbors)}")

# Remove a connection
hub.remove_neighbor(node2)
print(f"Hub connections after removal: {len(hub.neighbors)}")
print(f"Remaining connections: {[str(n) for n in hub.neighbors]}")

# Safe removal of non-existent neighbor
hub.remove_neighbor(node2)  # No error
print(f"Connections after safe removal: {len(hub.neighbors)}")

Custom Node Data

# Nodes with complex data
class Location:
    def __init__(self, name, lat, lon):
        self.name = name
        self.lat = lat
        self.lon = lon

    def __str__(self):
        return f"{self.name} ({self.lat}, {self.lon})"

# Create location nodes
new_york = GraphNode(Location("New York", 40.7128, -74.0060))
chicago = GraphNode(Location("Chicago", 41.8781, -87.6298))
la = GraphNode(Location("Los Angeles", 34.0522, -118.2437))

# Connect cities
new_york.add_neighbor(chicago)
chicago.add_neighbor(la)
new_york.add_neighbor(la)

# Access location data
for neighbor in new_york.neighbors:
    location = neighbor.value
    print(f"From {new_york.value.name} to {location.name}")
    print(f"  Coordinates: {location.lat}, {location.lon}")

Simple Graph Traversal

# Manual graph traversal using nodes
def dfs_nodes(start_node, visited=None):
    """Simple DFS traversal using GraphNodes."""
    if visited is None:
        visited = set()

    result = []
    stack = [start_node]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            result.append(node.value)

            # Add neighbors to stack
            for neighbor in reversed(node.neighbors):
                if neighbor not in visited:
                    stack.append(neighbor)

    return result

# Create a small graph
a = GraphNode('A')
b = GraphNode('B')
c = GraphNode('C')
d = GraphNode('D')

a.add_neighbor(b)
a.add_neighbor(c)
b.add_neighbor(d)
c.add_neighbor(d)

# Traverse the graph
traversal = dfs_nodes(a)
print(f"DFS traversal: {traversal}")

When to Use GraphNode

Ideal Use Cases

• Simple graphs - when you need basic node-to-node relationships
• Learning and education - when studying graph concepts or teaching algorithms
• Prototyping - quick graph prototypes without full implementation overhead
• Building blocks - as components for more complex graph structures
• Tree structures - when working with hierarchical data
• Small networks - when the graph size is small and manageable
• Custom implementations - when building specialized graph algorithms

Consider Full Graph Implementations When

• Complex operations - need algorithms like cycle detection, topological sort
• Large graphs - working with many vertices and edges
• Performance critical - need optimized traversal and analysis operations
• Weighted edges - need edge weights or complex edge properties
• Graph algorithms - using algorithms like Dijkstra, Floyd-Warshall
• Memory efficiency - need optimized storage for large graphs

Limitations

No Built-in Algorithms

GraphNode doesn't provide:

• Graph traversal algorithms (DFS, BFS)
• Cycle detection
• Connectivity checking
• Shortest path algorithms
• Topological sorting

No Edge Weights

• Cannot associate weights or costs with connections
• All relationships are treated equally
• No support for weighted graph algorithms

No Graph-level Operations

• No centralized vertex/edge management
• No graph-wide statistics or analysis
• Manual memory management of node relationships
• No global graph properties (connectivity, etc.)

Performance Considerations

• O(n) neighbor operations - list-based storage requires linear search
• No optimization for large numbers of connections
• Memory management - potential issues with circular references
• No indexing - cannot quickly find nodes by value

Performance and Memory Tips

Efficient Neighbor Management

# For better performance with many neighbors, consider using sets
class OptimizedGraphNode:
    def __init__(self, value):
        self.value = value
        self._neighbors_set = set()  # For O(1) lookups
        self.neighbors = []  # Maintain list interface

    def add_neighbor(self, neighbor):
        if neighbor not in self._neighbors_set:
            self._neighbors_set.add(neighbor)
            self.neighbors.append(neighbor)

    def remove_neighbor(self, neighbor):
        if neighbor in self._neighbors_set:
            self._neighbors_set.remove(neighbor)
            self.neighbors.remove(neighbor)

    def has_neighbor(self, neighbor):
        return neighbor in self._neighbors_set  # O(1) instead of O(n)

Memory Management for Large Networks

# Use weak references to avoid circular reference issues
import weakref

class WeakGraphNode:
    def __init__(self, value):
        self.value = value
        self._neighbors = []  # Store weak references

    def add_neighbor(self, neighbor):
        weak_ref = weakref.ref(neighbor)
        if weak_ref not in self._neighbors:
            self._neighbors.append(weak_ref)

    @property
    def neighbors(self):
        # Return live neighbors (filter out dead references)
        return [ref() for ref in self._neighbors if ref() is not None]

Batch Operations

# When building large networks, batch operations for efficiency
def build_network_efficiently(nodes, connections):
    """Build network with batch operations."""
    node_map = {node.value: node for node in nodes}

    # Add all connections in batch
    for from_val, to_val in connections:
        from_node = node_map[from_val]
        to_node = node_map[to_val]
        from_node.add_neighbor(to_node)

    return nodes

# Usage
nodes = [GraphNode(f"Node{i}") for i in range(100)]
connections = [(f"Node{i}", f"Node{(i+1)%100}") for i in range(100)]
network = build_network_efficiently(nodes, connections)

Migration to Full Graph Implementations

When your needs outgrow GraphNode, you can migrate to full implementations:

# Convert GraphNode structure to AdjacencyListGraph
from algo.data_structs.graphs import AdjacencyListGraph

def convert_nodes_to_graph(start_node, directed=False):
    """Convert a GraphNode structure to AdjacencyListGraph."""
    graph = AdjacencyListGraph(directed=directed)
    visited = set()

    def traverse_and_add(node):
        if node in visited:
            return

        visited.add(node)
        graph.add_vertex(node.value)

        for neighbor in node.neighbors:
            graph.add_edge(node.value, neighbor.value)
            traverse_and_add(neighbor)

    traverse_and_add(start_node)
    return graph

# Example migration
node_a = GraphNode('A')
node_b = GraphNode('B')
node_c = GraphNode('C')
node_a.add_neighbor(node_b)
node_b.add_neighbor(node_c)

# Convert to full graph implementation
full_graph = convert_nodes_to_graph(node_a)
print(f"Converted graph vertices: {full_graph.get_vertices()}")
print(f"Converted graph edges: {full_graph.get_edges()}")

# Now you can use advanced operations
print(f"Is connected: {full_graph.is_connected()}")
print(f"BFS traversal: {full_graph.bfs('A')}")

Best Practices

Design Patterns

# 1. Use factory pattern for creating connected nodes
class NodeFactory:
    @staticmethod
    def create_chain(values):
        """Create a chain of connected nodes."""
        nodes = [GraphNode(val) for val in values]
        for i in range(len(nodes) - 1):
            nodes[i].add_neighbor(nodes[i + 1])
        return nodes

    @staticmethod
    def create_star(center_val, satellite_vals):
        """Create a star topology with center node."""
        center = GraphNode(center_val)
        satellites = [GraphNode(val) for val in satellite_vals]

        for satellite in satellites:
            center.add_neighbor(satellite)
            satellite.add_neighbor(center)  # Bidirectional

        return center, satellites

# Usage
chain = NodeFactory.create_chain(['A', 'B', 'C', 'D'])
center, satellites = NodeFactory.create_star('Hub', ['Node1', 'Node2', 'Node3'])

Error Handling

# Robust node operations with error handling
class SafeGraphNode(GraphNode):
    def safe_add_neighbor(self, neighbor):
        """Add neighbor with validation."""
        if not isinstance(neighbor, GraphNode):
            raise TypeError("Neighbor must be a GraphNode instance")

        if neighbor is self:
            raise ValueError("Cannot add self as neighbor")

        self.add_neighbor(neighbor)

    def safe_remove_neighbor(self, neighbor):
        """Remove neighbor with error handling."""
        try:
            self.remove_neighbor(neighbor)
            return True
        except ValueError:
            return False  # Neighbor not found

Testing and Validation

# Utility functions for testing node networks
def validate_network(nodes):
    """Validate network structure and relationships."""
    issues = []

    for node in nodes:
        # Check for self-loops
        if node in node.neighbors:
            issues.append(f"Self-loop detected in {node.value}")

        # Check for bidirectional consistency
        for neighbor in node.neighbors:
            if node not in neighbor.neighbors:
                issues.append(f"Unidirectional link: {node.value} -> {neighbor.value}")

    return issues

def network_statistics(nodes):
    """Calculate basic network statistics."""
    if not nodes:
        return {}

    total_connections = sum(len(node.neighbors) for node in nodes)
    max_connections = max(len(node.neighbors) for node in nodes)
    min_connections = min(len(node.neighbors) for node in nodes)
    avg_connections = total_connections / len(nodes)

    return {
        'total_nodes': len(nodes),
        'total_connections': total_connections // 2,  # Bidirectional
        'average_connections': avg_connections,
        'max_connections': max_connections,
        'min_connections': min_connections
    }

# Example usage
nodes = [node_a, node_b, node_c]
issues = validate_network(nodes)
stats = network_statistics(nodes)

print(f"Network issues: {issues}")
print(f"Network stats: {stats}")

API Reference

Graph data structure implementations.

This module provides core graph components like GraphNode and imports from specialized graph implementation modules.

GraphNode(value)

A node in a graph.

add_neighbor(neighbor)

Add a neighbor to this node.

remove_neighbor(neighbor)

Remove a neighbor from this node.