implement route optimizer

[joamatab]

How can we improve routing functions?

• [ ] support global router
• [ ] support auto-routing with arbitrary directions, at the moment groups of routes need to have the same angle.

See gdsfactory/fixme/router.py and gdsfactory/fixme/router2.py

we could also leverage some of the routing algorithms from VLSI or PCB routing

• https://github.com/gdsfactory/kfactory/blob/auto-router/src/kfactory/routing/auto_router.py
• https://codeberg.org/LibrEDA/mycelium-router/src/branch/main/src/maze_router
• https://github.com/vygr/Python-PCB
• https://github.com/freerouting/freerouting
• https://github.com/jrialland/python-astar
• https://github.com/jamesbowman/cuflow
• https://codeberg.org/tok/librecell/src/branch/master/librecell-layout/lclayout/router.py
• https://codeberg.org/tok/librecell/src/branch/master/librecell-layout/lclayout/graphrouter/pathfinder.py
• https://github.com/hgroller/KlayoutNetworkX
• https://github.com/gsteixeira/python-astar/blob/main/examples/basic.py
• https://github.com/zhm-real/PathPlanning

@jaspreetj

[joamatab]

This looks promising

https://github.com/zhm-real/PathPlanning

the router from openRoad also looks great

https://github.com/The-OpenROAD-Project/OpenLane

[joamatab]

ideas to get started:

• single route
• bundles of routes
• different bundles competing for space

@tvt173 @SkandanC @thomasdorch

[SkandanC]

@joamatab Are we planning on adding this as an extension to Manhattan routing, etc. or as its own separate thing?

[joamatab]

I think we need a separate function for this

[joamatab]

for routing a group of routes, the following routers seem more promising

• https://codeberg.org/LibrEDA/mycelium-router/src/branch/main/src
• https://codeberg.org/tok/librecell/src/branch/master/librecell-layout/lclayout/graphrouter
• https://github.com/The-OpenROAD-Project/TritonRoute/
• https://github.com/The-OpenROAD-Project/OpenROAD/blob/master/src/grt/README.md

[joamatab]

Troy,

I think you were going to send a PR with a non-Manhattan router

@Hsuan-Tung @nikosavola @95-martin-orion

[joamatab]

https://github.com/instadeepai/jumanji

[SkandanC]

KFactory has a draft auto router writte using jumanji. See here: https://github.com/gdsfactory/kfactory/blob/auto-router/src/kfactory/routing/auto_router.py

@joamatab

[SkandanC]

I've added a draft auto-router for gdsfactory in the auto-router branch. If you want you can take a look, if anyone would like to collborate and work out how we can get this working better, that'd be great :)

[github-actions[bot]]

This issue is stale because it has been inactive for 60 days. Remove stale label or comment or this will be closed in 7 days.

[95-martin-orion]

Bumping this issue to brush off the dust:

• 2259 was motivated by issues using get_bundle_all_angle with manually-defined steps

• Other auto-routing tools would also benefit from better documentation. My team reports that wiring constitutes a significant fraction of their time spent laying out a device; if auto-routing works well, it could greatly reduce that time (and we should advertise that to users)

[joamatab]

yes, I looked at some PCB routing packages

• https://github.com/freerouting/freerouting/issues/132#issuecomment-1210868519 (java)

as well as CMOS routers

• https://github.com/The-OpenROAD-Project/TritonRoute/ (C++)
• https://codeberg.org/LibrEDA/mycelium-router (rust)

Skandan had a demo with

• https://github.com/instadeepai/jumanji

PRs are welcome

@basnijholt

[github-actions[bot]]

This issue is stale because it has been inactive for 60 days. Remove stale label or comment or this will be closed in 7 days.

[juanferv]

Just in case it helps development, we have tried jumaji's auto-router, but it takes a few minutes to do many iterations. This code is scanning the networkX library to do the grid and pathfinding. Actually, with a grid 5 times denser than the Astar example included in gdsfactory, it takes a couple of seconds compared to several minutes with the get_rout_astar function. Problems I have detected with the code:

• it fails me when I try to put bends in the routing (I am not an expert and it will be some waypoints nonsense).
• the issue of the orientation of the ports, it would be necessary to “correct” at the beginning or at the end so that “it doesn't matter the orientation” but that it connects well. For metal routing, it is ok, but for optical routing it can be a problem.
• To make multiport, with networkX from what I have seen is quite possible, and handles large grids with ease, so multiport, could be very interesting.
• We have put some loops that search the whole grid to make distance calculations that maybe could be changed by direct algorithms and speed up.
• It occurred to us that we could launch this type of automatic routing in parallel using multithreading or multicore.

from __future__ import annotations

import warnings

import numpy as np

import gdsfactory as gf
from gdsfactory import Port
from gdsfactory.component import Component
from gdsfactory.typings import CrossSectionSpec, LayerSpec, Route
import networkx as nx
from shapely.geometry import LineString

class Node:
    def __init__(self, parent=None, position: tuple = ()) -> None:
        """Initializes a node. A node is a point on the grid."""
        self.parent = parent  # parent node of current node
        self.position = position  # position of current node

        self.g = 0  # distance between current node and start node
        self.h = 0  # distance between current node and end node
        self.f = self.g + self.h  # cost of the node (sum of g and h)

def _extract_all_bbox(c: Component, avoid_layers: list[LayerSpec] | None = None):
    """Extract all polygons whose layer is in `avoid_layers`."""
    return [c.get_polygons(layer) for layer in avoid_layers]

def _generate_grid(
    c: Component,
    resolution: float = 0.5,
    avoid_layers: list[LayerSpec] | None = None,
    distance: float = 1,
) -> np.ndarray:
    """Generate discretization grid that the algorithm will step through."""
    bbox = c.bbox
    x, y = np.meshgrid(
        np.linspace(
            bbox[0][0]-resolution,
            bbox[1][0]+resolution,
            int((bbox[1][0] - bbox[0][0]+2*resolution) / resolution),
            endpoint=True,
        ),
        np.linspace(
            bbox[0][1]-resolution,
            bbox[1][1]+resolution,
            int((bbox[1][1] - bbox[0][1]+2*resolution) / resolution),
            endpoint=True,
        ),
    )  # discretize component space
    x, y = x[0], y[:, 0]  # weed out copies
    grid = np.zeros(
        (len(x), len(y))
    )  # mapping from gdsfactory's x-, y- coordinate to grid vertex

    # assign 1 for obstacles
    if avoid_layers is None:
        for ref in c.references:
            bbox = ref.bbox
            xmin = np.abs(x - bbox[0][0] + distance).argmin()
            xmax = np.abs(x - bbox[1][0] - distance).argmin()
            ymin = np.abs(y - bbox[0][1] + distance).argmin()
            ymax = np.abs(y - bbox[1][1] - distance).argmin()

            grid[xmin:xmax, ymin:ymax] = 1
    else:
        all_refs = _extract_all_bbox(c, avoid_layers)
        for layer in all_refs:
            for bbox in layer:
                xmin = np.abs(x - bbox[0][0] + distance).argmin()
                xmax = np.abs(x - bbox[2][0] - distance).argmin()
                ymin = np.abs(y - bbox[0][1] + distance).argmin()
                ymax = np.abs(y - bbox[2][1] - distance).argmin()
                grid[xmin:xmax, ymin:ymax] = 1

    return np.ndarray.round(grid, 3), np.ndarray.round(x, 3), np.ndarray.round(y, 3)

def simplify_path(waypoints, tolerance):
    """
    Simplifica una lista de waypoints utilizando el algoritmo de Douglas-Peucker.

    Args:
        waypoints: Lista de waypoints como pares de coordenadas (x, y).
        tolerance: Tolerancia de simplificación.

    Returns:
        Lista de waypoints simplificados.
    """
    # Crear una línea a partir de los waypoints
    line = LineString(waypoints)

    # Simplificar la línea utilizando el algoritmo de Douglas-Peucker
    simplified_line = line.simplify(tolerance, preserve_topology=False)

    # Convertir la línea simplificada de nuevo a una lista de waypoints
    simplified_waypoints = list(simplified_line.coords)

    return simplified_waypoints
def get_route_networkx2(
    component: Component,
    port1: Port,
    port2: Port,
    resolution: float = 1,
    avoid_layers: list[LayerSpec] | None = None,
    distance: float = 8,
    cross_section: CrossSectionSpec = "xs_sc",
    radius: float = 10.0,  # Radius of curvature
    smooth_factor: int = 3,  # Smoothing factor
    **kwargs,
) -> Route:
    """Bidirectional routing function using NetworkX. Finds a route between two ports avoiding obstacles.

    Args:
        component: Component the route, and ports belong to.
        port1: input.
        port2: output.
        resolution: discretization resolution in um.
        avoid_layers: list of layers to avoid.
        distance: distance from obstacles in um.
        cross_section: spec.
        radius: radius of curvature for smoothing (default: 10.0)
        smooth_factor: smoothing factor for route (default: 3)
        kwargs: cross_section settings.
    """
    cross_section = gf.get_cross_section(cross_section, **kwargs)

    grid, x, y = _generate_grid(component, resolution, avoid_layers, distance)

    # Create graph
    G = nx.grid_2d_graph(len(x), len(y))

    # Remove nodes representing obstacles
    for i in range(len(x)):
        for j in range(len(y)):
            if grid[i, j] == 1:
                G.remove_node((i, j))

    # Define start and end nodes
    start_node = (int(round((port1.x - x.min()) / resolution)), int(round((port1.y - y.min()) / resolution)))
    end_node = (int(round((port2.x - x.min()) / resolution)), int(round((port2.y - y.min()) / resolution)))
    # find the closet one
    for i in G:            
        node = i
        distance1_lim = 15*resolution
        distance2_lim = 15*resolution
        distance1 = np.sqrt(pow(start_node[0]-node[0],2)+pow(start_node[1]-node[1],2))
        distance2 = np.sqrt( pow(end_node[0]-node[0],2)+pow(end_node[1]-node[1],2))
        if distance1 < distance1_lim:
            start_node_auxi = node
            distance1_lim = distance1
        if distance2 < distance2_lim:
            end_node_auxi = node
            distance2_lim = distance2
    # Find shortest path
    start_node = start_node_auxi
    end_node = end_node_auxi
    try:
        path = nx.astar_path(G, start_node, end_node)
    except nx.NetworkXNoPath:
        warnings.warn("No path found.")
        return None

    # Convert path to waypoints
    waypoints = [(x[i] + resolution/2 , y[j] + resolution/2 ) for i, j in path]

    # # Smooth the route
    simplified_path = simplify_path(waypoints, tolerance=5)
        # Convert path to steps
    steps = []
    paths=[]
    my_waypoints = []
    # print(waypoints)
    my_waypoints.append(list([port1.x,port1.y]))
    paths.append(list([port1.x,port1.y]))
    for i in range(len(simplified_path) ):
        paths.append(np.round(simplified_path[i],1))
        x1, y1 = simplified_path[i]
        steps.append({"x": x1,"y":y1})
    for i in range(len(waypoints) ):
        my_waypoints.append(waypoints[i])
    # print(steps)
    paths.append(list([port2.x,port2.y]))   
    my_waypoints.append(list([port2.x,port2.y])) 
    my_waypoints[1] = [my_waypoints[1][0],my_waypoints[0][1]]
    my_waypoints[len(my_waypoints)-2] = [my_waypoints[len(my_waypoints)-2][0],my_waypoints[len(my_waypoints)-1][1]]
    routes =[]
    for i in range (len(steps)):
        position1 = []
        position2 = []
        if i==0:
            position1.append(port1.x)
            position1.append(port1.y)
            position2.append(steps[0]['x'])
            position2.append(steps[0]['y'])
        elif i == len(steps):
            position1.append(steps[len(steps)]['x'])
            position1.append(steps[len(steps)]['y'])
            position2.append(port2.x)
            position2.append(port2.y)
        else:
            position1.append(steps[i-1]['x'])
            position1.append(steps[i-1]['y'])
            position2.append(steps[i]['x'])
            position2.append(steps[i]['y'])

        port1 = gf.Port(
            name="aux1",
            center=(position1[0]-5, position1[1]),
            orientation=port1.orientation,
            cross_section=cross_section,
            width=port1.width,
            layer=port1.layer
        )
        port2 = gf.Port(
            name="aux2",
            center=(position2[0]+10, position2[1]),
            orientation=port1.orientation,
            cross_section=cross_section,
            width=port1.width,
            layer=port1.layer
        )
        routes.append(gf.routing.get_route(input_port=port1, output_port=port2, cross_section=cross_section,with_sbend=True,end_straight_length=0.5, radius=5))
    # Retornar la ruta simplificada
    # return routes

    return gf.routing.get_route_from_waypoints( waypoints=my_waypoints, cross_section=cross_section, bend=gf.components.wire_corner)
    # return gf.routing.get_route_from_steps(port1=port1, port2=port2,steps=steps)

c = gf.Component("get_route_astar_avoid_layers")
# cross_section = "xs_metal_routing"
cross_section = gf.get_cross_section("xs_metal_routing", width=5)
w = gf.components.straight(cross_section=cross_section)
left = c << w
right = c << w
right.rotate(90.0)
right.move((168, 63.2))

obstacle = gf.components.rectangle(size=(250, 3), layer="M2")
obstacle1 = c << obstacle
obstacle2 = c << obstacle
obstacle3 = c << obstacle
obstacle4 = c << obstacle
obstacle5 = c << obstacle
obstacle4.rotate(90)
obstacle5.rotate(90)
obstacle1.ymin = 50
obstacle1.xmin = -10
obstacle2.xmin = 35
obstacle3.ymin = 42
obstacle3.xmin = 72.23
obstacle4.xmin = 200
obstacle4.ymin = 55
obstacle5.xmin = 600
obstacle5.ymin = 200
port1 = left.ports["e2"]
port2 = right.ports["e2"]

routes = get_route_networkx2(
    component=c,
    port1=port1,
    port2=port2,
    cross_section=cross_section,
    resolution=1,
    distance=12,
    avoid_layers=("M2",),
)

# for route in routes:
#     c.add(route.references)
c.add(routes.references)
c.show()

[joamatab]

Thank you for sharing Juan, this works great for metal

i was able to make some cases with optical routes using your code

the trick is to have radius smaller than the resolution of the grid