0
# Graph Analysis
1

2
Advanced graph-based analysis functions for extracting connectivity relationships between regions and voxels, including contact surface area calculations, region adjacency graphs, and voxel-level connectivity patterns for network analysis and advanced image processing.
3

4
## Capabilities
5

6
### Contact Analysis
7

8
Calculate contact surface areas and adjacency relationships between connected components with support for anisotropic voxel spacing and different connectivity patterns.
9

10
```python { .api }
11
def contacts(
12
    labels: NDArray[Any],
13
    connectivity: Literal[4, 6, 8, 18, 26] = 26,
14
    surface_area: bool = True,
15
    anisotropy: tuple[Union[int, float], Union[int, float], Union[int, float]] = (1, 1, 1),
16
) -> dict[tuple[int, int], Union[int, float]]:
17
    """
18
    Get the N-connected region adjacency graph and contact area between regions.
19

20
    Parameters:
21
    - labels: 3D numpy array of integer segmentation labels
22
    - connectivity: 6, 18, or 26 (default) for 3D; 4 or 8 for 2D
23
    - surface_area: Return contact surface area (True) or simple voxel count (False)
24
    - anisotropy: Weights for x, y, and z dimensions for computing surface area
25

26
    Returns:
27
    - dict: Mapping {(label_1, label_2): contact_value, ...}
28
            contact_value is surface area (float) or voxel count (int)
29
    """
30
```
31

32
Usage examples:
33

34
```python
35
import cc3d
36
import numpy as np
37

38
# Create test segmentation
39
labels = np.zeros((100, 100, 100), dtype=np.int32)
40
labels[20:40, 20:40, 20:40] = 1  # Component 1
41
labels[35:55, 35:55, 35:55] = 2  # Component 2 (overlapping)
42
labels[60:80, 60:80, 60:80] = 3  # Component 3 (separate)
43

44
# Get contact surface areas between all pairs
45
surface_contacts = cc3d.contacts(labels, connectivity=26, surface_area=True)
46

47
# Print all contacts
48
for (label1, label2), area in surface_contacts.items():
49
    print(f"Contact between regions {label1} and {label2}: {area:.2f} surface area")
50

51
# Get simple voxel contact counts instead of surface area
52
voxel_contacts = cc3d.contacts(labels, connectivity=6, surface_area=False)
53
for (label1, label2), count in voxel_contacts.items():
54
    print(f"Regions {label1} and {label2} share {count} face-adjacent voxels")
55

56
# Handle anisotropic voxel spacing (e.g., microscopy data)
57
# Voxel dimensions: 0.5μm x 0.5μm x 2μm (z is thicker)
58
anisotropic_contacts = cc3d.contacts(
59
    labels, 
60
    connectivity=26,
61
    surface_area=True,
62
    anisotropy=(0.5, 0.5, 2.0)
63
)
64

65
# Different connectivity patterns
66
face_contacts = cc3d.contacts(labels, connectivity=6)   # Face-adjacent only  
67
edge_contacts = cc3d.contacts(labels, connectivity=18)  # Faces + edges
68
corner_contacts = cc3d.contacts(labels, connectivity=26) # Faces + edges + corners
69

70
# Check if specific regions are adjacent
71
if (1, 2) in surface_contacts:
72
    contact_area = surface_contacts[(1, 2)]
73
    print(f"Regions 1 and 2 are adjacent with area {contact_area}")
74
else:
75
    print("Regions 1 and 2 are not adjacent")
76

77
# Find all neighbors of a specific region
78
region_of_interest = 2
79
neighbors = []
80
for (label1, label2) in surface_contacts.keys():
81
    if label1 == region_of_interest:
82
        neighbors.append(label2)
83
    elif label2 == region_of_interest:
84
        neighbors.append(label1)
85
print(f"Region {region_of_interest} neighbors: {neighbors}")
86
```
87

88
### Region Adjacency Graph
89

90
Extract the topological adjacency graph between regions as a set of edges, providing a simplified view of spatial relationships.
91

92
```python { .api }
93
def region_graph(
94
    labels: NDArray[np.integer],
95
    connectivity: Literal[4, 6, 8, 18, 26] = 26,
96
) -> set[tuple[int, int]]:
97
    """
98
    Get the N-connected region adjacency graph of a 3D image.
99

100
    Parameters:
101
    - labels: 3D numpy array of integer segmentation labels
102
    - connectivity: 6, 18, or 26 (default) for 3D; 4 or 8 for 2D
103

104
    Returns:
105
    - set: Set of edges between labels as (label1, label2) tuples
106
    """
107
```
108

109
Usage examples:
110

111
```python
112
import cc3d
113
import numpy as np
114

115
# Create complex segmentation
116
labels = create_complex_segmentation()  # Your segmentation function
117

118
# Get adjacency graph
119
edges = cc3d.region_graph(labels, connectivity=26)
120

121
# Print graph structure
122
print(f"Found {len(edges)} adjacency relationships")
123
for label1, label2 in sorted(edges):
124
    print(f"Regions {label1} and {label2} are adjacent")
125

126
# Convert to other graph representations
127
# NetworkX graph
128
import networkx as nx
129
G = nx.Graph()
130
G.add_edges_from(edges)
131

132
# Adjacency list
133
from collections import defaultdict
134
adjacency_list = defaultdict(list)
135
for label1, label2 in edges:
136
    adjacency_list[label1].append(label2)
137
    adjacency_list[label2].append(label1)
138

139
# Find connected components in the adjacency graph
140
connected_groups = list(nx.connected_components(G))
141
print(f"Found {len(connected_groups)} connected groups of regions")
142

143
# Find regions with most neighbors
144
degree_centrality = nx.degree_centrality(G)
145
most_connected = max(degree_centrality.items(), key=lambda x: x[1])
146
print(f"Most connected region: {most_connected[0]} with {most_connected[1]:.2f} centrality")
147

148
# Compare different connectivity patterns
149
edges_6 = cc3d.region_graph(labels, connectivity=6)
150
edges_26 = cc3d.region_graph(labels, connectivity=26)
151
print(f"6-connected: {len(edges_6)} edges")
152
print(f"26-connected: {len(edges_26)} edges")
153
```
154

155
### Voxel Connectivity Graph
156

157
Generate detailed voxel-level connectivity information as bitfields, enabling fine-grained analysis of spatial relationships and custom connectivity processing.
158

159
```python { .api }
160
def voxel_connectivity_graph(
161
    data: NDArray[IntegerT],
162
    connectivity: Literal[4, 6, 8, 18, 26] = 26,
163
) -> NDArray[IntegerT]:
164
    """
165
    Extracts the voxel connectivity graph from a multi-label image.
166

167
    A voxel is considered connected if the adjacent voxel has the same label.
168
    The output is a bitfield representing allowed directions for transit between voxels.
169

170
    For 2D connectivity (4,8): returns uint8 with bits 1-8 encoding directions
171
    For 3D connectivity (6): returns uint8 with bits 1-6 encoding face directions  
172
    For 3D connectivity (18,26): returns uint32 with bits 1-26 encoding all directions
173

174
    Bit encoding for 3D (26-connected):
175
    Bits 1-6: faces (+x,-x,+y,-y,+z,-z)
176
    Bits 7-18: edges 
177
    Bits 19-26: corners
178
    Bits 27-32: unused (zero)
179

180
    Parameters:
181
    - data: Input labeled array
182
    - connectivity: Connectivity pattern to analyze
183

184
    Returns:
185
    - NDArray: Same shape as input, with connectivity bitfields
186
    """
187
```
188

189
Usage examples:
190

191
```python
192
import cc3d
193
import numpy as np
194

195
# Create test segmentation
196
labels = np.random.randint(0, 5, (50, 50, 50), dtype=np.int32)
197

198
# Generate voxel connectivity graph
199
vcg = cc3d.voxel_connectivity_graph(labels, connectivity=26)
200

201
# Analyze connectivity patterns
202
print(f"VCG dtype: {vcg.dtype}")  # uint32 for 26-connected
203
print(f"VCG shape: {vcg.shape}")  # Same as input
204

205
# Check connectivity at specific voxel
206
x, y, z = 25, 25, 25
207
connectivity_bits = vcg[x, y, z]
208
print(f"Voxel ({x},{y},{z}) connectivity: {connectivity_bits:032b}")
209

210
# Count total connections per voxel
211
total_connections = np.zeros_like(vcg, dtype=np.int32)
212
for bit in range(26):  # For 26-connected
213
    bit_mask = 1 << bit
214
    total_connections += ((vcg & bit_mask) > 0).astype(np.int32)
215

216
# Find highly connected voxels
217
highly_connected = np.where(total_connections > 20)
218
print(f"Found {len(highly_connected[0])} highly connected voxels")
219

220
# Different connectivity patterns
221
vcg_6 = cc3d.voxel_connectivity_graph(labels, connectivity=6)   # uint8
222
vcg_18 = cc3d.voxel_connectivity_graph(labels, connectivity=18) # uint32
223
vcg_26 = cc3d.voxel_connectivity_graph(labels, connectivity=26) # uint32
224

225
# Analyze 2D connectivity (using 2D slice)
226
labels_2d = labels[:, :, 25]
227
vcg_2d_4 = cc3d.voxel_connectivity_graph(labels_2d, connectivity=4)  # uint8
228
vcg_2d_8 = cc3d.voxel_connectivity_graph(labels_2d, connectivity=8)  # uint8
229

230
# Extract specific directional connections
231
# For 3D 26-connected, bit positions:
232
# 1: +x, 2: -x, 3: +y, 4: -y, 5: +z, 6: -z
233
plus_x_connections = (vcg & 1) > 0  # Can move in +x direction
234
minus_z_connections = (vcg & (1 << 5)) > 0  # Can move in -z direction
235

236
print(f"Voxels with +x connectivity: {np.sum(plus_x_connections)}")
237
print(f"Voxels with -z connectivity: {np.sum(minus_z_connections)}")
238
```
239

240
### Connectivity Graph Coloring
241

242
Convert voxel connectivity graphs back to labeled images, useful for reconstructing components from connectivity information or creating alternative labelings.
243

244
```python { .api }
245
def color_connectivity_graph(
246
    vcg: NDArray[VcgT],
247
    connectivity: Literal[4, 6, 8, 18, 26] = 26,
248
    return_N: bool = False,
249
) -> Union[NDArray[VcgT], tuple[NDArray[VcgT], int]]:
250
    """
251
    Color the connectivity graph back into connected components.
252

253
    Given a voxel connectivity graph, this function treats it as an undirected
254
    graph and returns connected components based on the connectivity patterns
255
    encoded in the bitfield.
256

257
    Parameters:
258
    - vcg: Voxel connectivity graph from voxel_connectivity_graph()
259
    - connectivity: Must match the connectivity used to generate vcg
260
    - return_N: If True, also return the number of components
261

262
    Returns:
263
    - NDArray: Labeled image with connected components
264
    - tuple[NDArray, int]: If return_N=True, includes component count
265
    """
266
```
267

268
Usage examples:
269

270
```python
271
import cc3d
272
import numpy as np
273

274
# Start with original labels
275
original_labels = np.random.randint(0, 10, (100, 100, 100), dtype=np.int32)
276

277
# Extract voxel connectivity graph
278
vcg = cc3d.voxel_connectivity_graph(original_labels, connectivity=26)
279

280
# Reconstruct connected components from connectivity graph
281
reconstructed_labels = cc3d.color_connectivity_graph(vcg, connectivity=26)
282

283
# Get component count
284
reconstructed_labels, N = cc3d.color_connectivity_graph(
285
    vcg, connectivity=26, return_N=True
286
)
287
print(f"Reconstructed {N} components")
288

289
# Compare original vs reconstructed
290
print(f"Original max label: {np.max(original_labels)}")
291
print(f"Reconstructed max label: {np.max(reconstructed_labels)}")
292

293
# Note: Labels will be different but connectivity should be preserved
294
# Verify connectivity is preserved by checking region adjacency
295
original_graph = cc3d.region_graph(original_labels, connectivity=26)
296
reconstructed_graph = cc3d.region_graph(reconstructed_labels, connectivity=26)
297

298
print(f"Original graph edges: {len(original_graph)}")
299
print(f"Reconstructed graph edges: {len(reconstructed_graph)}")
300

301
# Modify connectivity graph before reconstruction
302
modified_vcg = vcg.copy()
303

304
# Remove some connections (set bits to 0)
305
# For example, remove all +x connections (bit 0)
306
modified_vcg = modified_vcg & ~1  # Clear bit 0
307

308
# Reconstruct with modified connectivity
309
modified_labels = cc3d.color_connectivity_graph(modified_vcg, connectivity=26)
310

311
# This should result in more components since we removed connections
312
original_N = len(np.unique(reconstructed_labels)) - 1  # Subtract background
313
modified_N = len(np.unique(modified_labels)) - 1
314
print(f"Original: {original_N} components")
315
print(f"After removing +x connections: {modified_N} components")
316

317
# Use with different connectivity patterns
318
vcg_6 = cc3d.voxel_connectivity_graph(original_labels, connectivity=6)
319
labels_6 = cc3d.color_connectivity_graph(vcg_6, connectivity=6)
320

321
# 2D example
322
labels_2d = original_labels[:, :, 50]
323
vcg_2d = cc3d.voxel_connectivity_graph(labels_2d, connectivity=8)
324
reconstructed_2d = cc3d.color_connectivity_graph(vcg_2d, connectivity=8)
325
```
326

327
## Advanced Graph Analysis Patterns
328

329
### Combining Graph Functions
330

331
```python
332
# Complete region analysis pipeline
333
labels = your_segmentation_image()
334

335
# Get adjacency relationships
336
edges = cc3d.region_graph(labels)
337
contacts = cc3d.contacts(labels, surface_area=True)
338

339
# Analyze voxel-level connectivity
340
vcg = cc3d.voxel_connectivity_graph(labels)
341

342
# Create connectivity-based alternative labeling
343
alternative_labels = cc3d.color_connectivity_graph(vcg)
344

345
# Compare region structures
346
print(f"Original regions: {len(np.unique(labels))}")
347
print(f"Alternative regions: {len(np.unique(alternative_labels))}")
348
```
349

350
### Network Analysis Integration
351

352
```python
353
# Convert to NetworkX for advanced analysis
354
import networkx as nx
355

356
contacts = cc3d.contacts(labels, surface_area=True)
357
G = nx.Graph()
358
for (u, v), weight in contacts.items():
359
    G.add_edge(u, v, weight=weight)
360

361
# Network metrics
362
centrality = nx.betweenness_centrality(G, weight='weight')
363
clustering = nx.clustering(G, weight='weight')
364
communities = nx.community.greedy_modularity_communities(G)
365

366
print(f"Found {len(communities)} communities in the region graph")
367
```