Does the algorithm choose centers?

No. The centers are inputs to the cell construction.

Can a vertex be equally close to two centers?

Yes. A partition needs a rule for assigning such ties.

Why reverse a directed graph?

Reversing edges converts a center-to-vertex calculation into the corresponding vertex-to-center distance calculation.

AI Glossary / Graphs and symbolic AI / Intermediate

Voronoi cells

Definition

Voronoi cells divide a space among selected centers according to which center is nearest. In a graph, distance is measured along graph paths rather than necessarily by straight-line geometry. Each center's cell contains the vertices assigned to it under the chosen shortest-path distance and tie policy. This entry focuses on the graph-based meaning used by NetworkX.

What it means

The centers are supplied in advance. Computing their cells answers which center is nearest to each vertex; it does not choose the best locations for the centers.
The result depends on edge weights and direction. A geographically nearby center can be far away through the available connections. On a directed graph, distance from a center to a vertex can differ from distance from that vertex to the center. Equal distances also require attention: a mathematical description may retain a shared boundary, while a software partition assigns a tied vertex to one center.

How it works

Choose a nonempty set of center vertices and define what edge distance means. Compute shortest-path distances from the centers, commonly with a multi-source shortest-path procedure for nonnegative weights. Associate each reachable vertex with a nearest center.
Specify the treatment of ties and vertices unreachable from every center. NetworkX's documented function computes outward cells on directed graphs, meaning center-to-vertex distance. Reversing edges supports the corresponding inward interpretation. Its implementation groups vertices by the source of a selected shortest path and places unreachable vertices under a separate key. These implementation details matter when converting the result into an operational assignment.

Three practical examples

A service-network model can assign locations to the nearest predefined hub by travel cost along network edges.
A graph-analysis exercise can partition vertices around selected representative nodes.
A directed-network simulation can compare outward reach from centers with inward access to centers, revealing assignments that change with travel direction.

Think of it this way

Think of assigning neighborhoods to their nearest library using actual walkable routes. A river or missing bridge can matter more than a short straight-line distance. The analogy is limited because a nearest-center assignment ignores library capacity, opening hours, and preferences unless the model explicitly includes them.

Worked example

Consider an original undirected path with vertices 0, 1, 2, 3, 4, 5, and 6 in that order. Each adjacent edge has weight one. Choose centers 0 and 6.
Distances from center 0 are 0, 1, 2, 3, 4, 5, and 6. Distances from center 6 are the reverse: 6, 5, 4, 3, 2, 1, and 0. Vertices 0, 1, and 2 are strictly nearer to center 0. Vertices 4, 5, and 6 are strictly nearer to center 6. Vertex 3 is tied at distance three.
For this teaching example, explicitly assign ties to the numerically smaller center. The cells are then {0,1,2,3} and {4,5,6}. This declared policy makes the example deterministic; it is not a claim that NetworkX universally promises that tie order.
Now increase the weight of edge 2-3 from one to four. Distances from center 0 become 0, 1, 2, 6, 7, 8, and 9. Distances from center 6 become 9, 8, 7, 3, 2, 1, and 0. Vertex 3 is now strictly nearer to center 6. The cells become {0,1,2} and {3,4,5,6}. No vertex moved geometrically; changing the network cost changed the assignment.
Return to unit weights, but direct every edge from the smaller number toward the larger. For outward distances, center 0 reaches every vertex, while center 6 reaches only itself. Thus 0 through 5 belong to center 0 and 6 belongs to center 6. For inward distances, vertex 0 can reach its own center immediately, while vertices 1 through 6 can reach center 6 but not center 0. The inward cells therefore differ.
Finally, add an isolated vertex Z with no center in its component. It is unreachable from both centers. Treating it as assigned to an arbitrary center would conceal a missing route; it needs separate handling. The inspected NetworkX implementation exposes such vertices in its unreachable group.

Illustrative case study

In a fictional distribution-planning prototype, analysts use existing depot vertices as centers in a directed road graph. An initial analysis measures depot-to-customer distance, but the intended task concerns customer returns to depots.
The team corrects the direction of the distance calculation and reviews locations with no available route. It also checks capacity separately because nearest-distance cells do not balance depot workloads. This fictional case illustrates interpretation and model review, not a claimed operational saving.

Common misconceptions and mistakes

Graph Voronoi cells are not necessarily ordinary polygons on a map. They are sets of vertices defined by the graph's distance structure. They do not automatically have equal sizes or balanced demand.
Do not ignore edge direction, substitute geographic distance for network distance, or assume tied assignments are uniquely determined. Do not treat an unreachable vertex as merely very far away without defining the intended behavior. Finally, changing centers or weights can alter many assignments, so an old partition may no longer represent the updated network.

Business use

The concept supports explainable nearest-center assignments when the distance model fits the task. It can clarify which hub serves a vertex under the current network and why a seemingly close alternative loses.
Document centers, cost units, edge direction, tie handling, and unreachable cases. Compare cell assignments with capacity and service constraints before treating them as final allocations. If the goal is to choose center locations or balance workloads, formulate that additional optimization explicitly rather than expecting a Voronoi partition alone to solve it.

Check your understanding

Why does vertex 3 move to center 6's cell after edge 2-3 becomes more expensive?

Answer: Its distance from center 0 increases to six, while its distance from center 6 remains three.

Related terms

Shortest Paths
Directed graph
Graph distance
Shortest path
Multi-source Dijkstra
Voronoi diagram
Center node
Reachability
Facility location

Learn next

Next, add center 3 to the original unit-weight path. Compute distances to all three centers and form the cells using the same explicit tie policy. Then explain why adding a center can reduce nearest-center distances without guaranteeing a better capacity allocation.

Sources

Primary sources: NetworkX Voronoi-cells reference: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.voronoi.voronoi_cells.html ; implementation: https://networkx.org/documentation/stable/_modules/networkx/algorithms/voronoi.html . The weighted-path and direction examples are original.

Previous: Von Mises-Fisher distribution Next: Voronoi graph