Graph Types

Graphizy supports multiple graph construction algorithms, each optimized for different use cases. This section provides comprehensive coverage of all available graph types, their properties, and when to use them.

Overview

Graph Types Comparison

Graph Type	Connectivity	Edge Count	Use Case	Memory Compatible
Delaunay	Always	~3n	Natural triangulation	✅
Proximity	Variable	~distance²	Local neighborhoods	✅
K-NN	Variable	k×n	Fixed degree networks	✅
MST	Always	n-1	Minimal connectivity	✅
Gabriel	Variable	Subset of Delaunay	Geometric proximity	✅
Memory	Variable	Historical	Temporal analysis	N/A (is the modifier)

Delaunay Triangulation

Delaunay triangulation creates an optimal triangular mesh where no point lies inside the circumcircle of any triangle. This produces the “most equilateral” triangulation possible.

Mathematical Properties:

• Connectivity: Always produces a connected graph

• Planarity: Edges never cross

• Optimality: Maximizes minimum angle of all triangles

• Edge Count: Typically ~3n edges for n vertices

Algorithm:

1. Create OpenCV Subdiv2D structure

2. Insert all points into subdivision

3. Extract triangle list

4. Convert triangles to graph edges

5. Map OpenCV indices back to original IDs

# Create Delaunay triangulation
delaunay_graph = grapher.make_delaunay(data)

# Properties
info = grapher.get_graph_info(delaunay_graph)
print(f"Delaunay: {info['vertex_count']} vertices, {info['edge_count']} edges")
print(f"Always connected: {info['is_connected']}")  # True
print(f"Planar embedding: edges never cross")

Use Cases:

• Mesh generation for finite element analysis

• Natural neighbor interpolation

• Spatial analysis where triangle quality matters

• Geographic information systems (GIS)

• Computer graphics mesh generation

Proximity Graphs

Proximity graphs connect points within a specified distance threshold. This creates local neighborhood structures based on spatial proximity.

# Create proximity graph
proximity_graph = grapher.make_proximity(
    data,
    proximity_thresh=50.0,    # Distance threshold
    metric="euclidean"        # Distance metric
)

# Analyze connectivity
components = grapher.call_method_raw(proximity_graph, 'connected_components')
print(f"Proximity graph has {len(components)} connected components")

Distance Metrics:

• Euclidean: √((x₁-x₂)² + (y₁-y₂)²) - Standard Cartesian distance

• Manhattan: |x₁-x₂| + |y₁-y₂| - City block distance

• Chebyshev: max(|x₁-x₂|, |y₁-y₂|) - Chessboard distance

K-Nearest Neighbors (KNN)

K-Nearest Neighbors graphs connect each point to its k closest neighbors, creating a directed graph that can be made undirected by including reverse edges.

# Create KNN graph (requires scipy)
knn_graph = grapher.make_knn(data, k=4)

# Analyze degree distribution
degrees = grapher.call_method(knn_graph, 'degree')
degree_values = list(degrees.values())
print(f"Average degree: {np.mean(degree_values):.2f}")

Minimum Spanning Tree (MST)

Minimum Spanning Tree creates the minimal connected graph by selecting the shortest edges that connect all vertices without creating cycles.

# Create minimum spanning tree
mst_graph = grapher.make_mst(data, metric="euclidean")

# Verify MST properties
info = grapher.get_graph_info(mst_graph)
n_vertices = info['vertex_count']
n_edges = info['edge_count']

print(f"Tree property: {n_edges == n_vertices - 1}")  # Should be True
print(f"Connected: {info['is_connected']}")           # Always True

Gabriel Graph

Gabriel graph connects two points if no other point lies within the circle having the two points as diameter endpoints. It’s a subset of the Delaunay triangulation with interesting geometric properties.

Mathematical Properties:

• Connectivity: May be disconnected for sparse point sets

• Subset Relationship: Always a subset of the Delaunay triangulation

• Local Property: Connections based on local geometric criteria

• Edge Count: Generally fewer edges than Delaunay triangulation

Algorithm:

1. For each pair of points, create a circle with the pair as diameter

2. Check if any other point lies strictly inside this circle

3. If no point is inside, the pair forms a Gabriel edge

4. Add all valid Gabriel edges to the graph

# Create Gabriel graph
gabriel_graph = grapher.make_gabriel(data)

# Properties
info = grapher.get_graph_info(gabriel_graph)
print(f"Gabriel: {info['vertex_count']} vertices, {info['edge_count']} edges")
print(f"Subset of Delaunay: edges ≤ Delaunay edges")
print(f"Connected: {info['is_connected']}")  # May be False

Use Cases:

• Wireless sensor networks with interference-free communication

• Geographic analysis where direct line-of-sight matters

• Computational geometry applications requiring local proximity

• Pattern recognition in point cloud analysis

• Network topology design with geometric constraints

Comparison with Other Graph Types:

# Compare Gabriel with related graph types
gabriel_graph = grapher.make_gabriel(data)
delaunay_graph = grapher.make_delaunay(data)
proximity_graph = grapher.make_proximity(data, 50.0)

gabriel_info = grapher.get_graph_info(gabriel_graph)
delaunay_info = grapher.get_graph_info(delaunay_graph)
proximity_info = grapher.get_graph_info(proximity_graph)

print(f"Gabriel edges: {gabriel_info['edge_count']}")
print(f"Delaunay edges: {delaunay_info['edge_count']}")
print(f"Proximity edges: {proximity_info['edge_count']}")

# Gabriel is always a subset of Delaunay
assert gabriel_info['edge_count'] <= delaunay_info['edge_count']

Memory-Enhanced Graphs

Memory graphs are not a separate graph type but a modifier that can be applied to any base graph type. They track connections over time, creating temporal analysis capabilities.

# Initialize memory system
grapher.init_memory_manager(
    max_memory_size=50,      # Max connections per object
    max_iterations=None,     # Keep all history (or set limit)
    track_edge_ages=True     # Enable age-based visualization
)

# Evolution simulation
for iteration in range(100):
    # Update positions (simulate movement)
    data[:, 1:3] += np.random.normal(0, 2, (len(data), 2))

    # Create current graph (any type)
    current_graph = grapher.make_proximity(data, proximity_thresh=60.0)

    # Update memory with current connections
    grapher.update_memory_with_graph(current_graph)

    # Create memory-enhanced graph
    memory_graph = grapher.make_memory_graph(data)

Graph Type Selection Guide

Choosing the right graph type depends on your specific requirements:

For Spatial Analysis:

• Dense regular patterns → Delaunay Triangulation

• Sparse irregular patterns → Proximity Graphs

• Fixed connectivity needs → K-Nearest Neighbors

• Minimal connectivity → Minimum Spanning Tree

For Network Properties:

• Always connected → Delaunay or MST

• Local neighborhoods → Proximity or KNN

• Minimal edges → MST

• Regular degree → KNN

For Dynamic Analysis:

• Any of the above + Memory modifier

• Temporal patterns → Memory-enhanced graphs

• Evolution tracking → Memory with age visualization