Kinematic Graph

The KinematicGraph provides formal graph-theory logic for validating and traversing the link-joint structure of a robot. It is used internally by RobotValidator and RobotBuilder, but is also available for advanced users who need custom traversal or analysis logic.

KinematicGraph

class linkforge.core.KinematicGraph(links, joints)

Bases: object

Robot connectivity model for cycle detection and topological sorting.

This class decouples the graph-theoretical concerns (islands, cycles, roots) from the main Robot data model, enabling efficient structural validation.

Parameters:

• links (Iterable[Link])

• joints (Iterable[Joint])

__init__(links, joints)

Initialize the kinematic graph.

Parameters:

• links (Iterable[Link]) – Collection of Link objects forming the nodes of the graph.

• joints (Iterable[Joint]) – Collection of Joint objects forming the edges of the graph.

Raises:

RobotValidationError – If a joint references a link not present in the links collection.

has_cycle()

Detect kinematic loops using iterative DFS with WHITE/GREY/BLACK colouring.

Kinematic cycles are generally illegal in URDF and many physics solvers unless explicitly handled by parallel linkage plugins.

Uses three-colour marking to identify back-edges in the directed graph: - WHITE (0): not yet visited - GREY (1): currently in the DFS recursion stack - BLACK (2): fully processed, all descendants explored

A back-edge (node pointing to a GREY ancestor) indicates a cycle. The iterative stack avoids Python’s default recursion limit.

Return type:

bool

get_root_links()

Identify all potential root links in the robot structure.

A root link is defined as a link that has outgoing joint edges (is a parent) but no incoming joint edges (is never a child).

Return type:

list[str]

Returns:

Alphabetically sorted list of root link names.

find_islands()

Identify disconnected components (islands) in the robot structure.

Uses BFS traversal to find all linked components. Returns isolated links as single-node islands.

Return type:

list[set[str]]

get_topological_link_names()

Return links in topological order (parents before children).

Return type:

list[str]

Returns:

List of link names

Raises:

RobotValidationError – If a cycle is detected

get_topological_joints()

Return joints in topological order (parents before children).

This ensures that when building a hierarchy, the parent structure always exists before the child is attached.

Return type:

list[Joint]

Returns:

Sorted list of Joint models

Raises:

RobotValidationError – If a cycle is detected

---

Usage Examples

Detect cycles in a robot

from linkforge.core import KinematicGraph, URDFParser
from pathlib import Path

robot = URDFParser().parse(Path("my_robot.urdf"))
graph = KinematicGraph(robot.links, robot.joints)

try:
    roots = graph.get_root_links()
    print(f"Root links found: {len(roots)}")
    print("No cycles detected.")
except Exception as e:
    print(f"Topology error: {e}")

Topological traversal

from linkforge.core import KinematicGraph

graph = KinematicGraph(robot.links, robot.joints)

# 1. Get ordered link names (Strings)
for link_name in graph.get_topological_link_names():
    print(f"Processing link: {link_name}")

# 2. Get ordered joint objects (Models)
for joint in graph.get_topological_joints():
    print(f"Configuring joint: {joint.name} ({joint.type.name})")

Note

KinematicGraph is stateless and can be re-created at any time from a Robot model. It does not hold a reference to the original robot, making it safe to use in parallel or in tests without side effects.