bpc-graph

A box pin color (BPC) graph is a specialized graph structure where:

• Boxes contain pins
• Pins belong to a network
• Pins are coloured to describe signal type

Boxes can be fixed (they know their position) or floating (no position yet). Each pin stores an offset relative to its box. When all pins on a network are visualised, a schematic like connection graph is produced.

This repository provides utilities for manipulating and comparing BPC graphs.

Contents

• bpc-graph
  • Contents
  • Where BPC graphs are used
  • Installation
  • Quick Example
  • Library
    • getGraphBounds(graph)
    • getPinDirection(graph, boxId, pinId)
    • assignFloatingBoxPositions(graph)
    • netAdaptBpcGraph(source, target)
    • renetworkWithCondition(graph, predicate)
    • getBpcGraphWlDistance(a, b)
    • ForceDirectedLayoutSolver
    • getBoxSideSubgraph({ bpcGraph, boxId, side })
    • mergeBoxSideSubgraphs(graphs)
    • convertToFlatBpcGraph(graph)
    • convertFromFlatBpcGraph(flatBpcGraph)

Where BPC graphs are used

When automatically laying out schematics the tools in this repo convert an initial "floating" design into a fixed layout. Networks can be split, boxes can be adapted to a template and the resulting graph can be rendered with a force directed solver.

Installation

bun add bpc-graph

Quick Example

import { getGraphicsForBpcGraph } from "bpc-graph"
import { getSvgFromGraphicsObject } from "graphics-debug"

const graph = {
  boxes: [
    { boxId: "A", kind: "fixed", center: { x: 0, y: 0 } },
    { boxId: "B", kind: "fixed", center: { x: 2, y: 0 } },
  ],
  pins: [
    {
      boxId: "A",
      pinId: "P1",
      offset: { x: 0.5, y: 0 },
      color: "red",
      networkId: "N1",
    },
    {
      boxId: "A",
      pinId: "P2",
      offset: { x: 0.5, y: -0.5 },
      color: "blue",
      networkId: "N1",
    },
    {
      boxId: "B",
      pinId: "P1",
      offset: { x: -0.5, y: 0 },
      color: "red",
      networkId: "N1",
    },
    {
      boxId: "B",
      pinId: "CENTER",
      offset: { x: 0, y: 0 },
      color: "gray",
      networkId: "N2",
    },
  ],
}

const svg = getSvgFromGraphicsObject(getGraphicsForBpcGraph(graph), {
  backgroundColor: "white",
  includeTextLabels: true,
})

Library

getGraphBounds(graph)

getGraphBounds(g)
// { minX, minY, maxX, maxY }

getPinDirection(graph, boxId, pinId)

Determines which direction a pin is facing (and which side of the box it is on) by examining its offset relative to the bounds of the box.

getPinDirection(g, "A", "P1")
// x-" | "x+" | "y-" | "y+" | null

assignFloatingBoxPositions(graph)

Infers positions for floating boxes based on the positions of any connected pins

Starting with floating boxes (no fixed positions), the layout solver can automatically assign positions:

import { assignFloatingBoxPositions } from "bpc-graph"

const floatingGraph = {
  boxes: [
    { boxId: "A", kind: "floating" },
    { boxId: "B", kind: "floating" },
  ],
  pins: [
    /* ... */
  ],
}

// Convert floating boxes to fixed positions
const fixedGraph = assignFloatingBoxPositions(floatingGraph)

The image shows floating boxes (left) being automatically positioned into a fixed layout (right):

netAdaptBpcGraph(source, target)

Adapt the source graph so that on a network, connection and pin count level it matches the target graph. This function will insert or remove pins and boxes or change network ids until there is a 1:1 matching for boxes and pins between the source and target.

After net adapt, the graph will have floating boxes- we use assignFloatingBoxPositions to infer positions for these boxes below.

renetworkWithCondition(graph, predicate)

Change the networks of a graph based on a predicate.

const { renetworkedGraph } = renetworkWithCondition(
  ogGraph,
  (from, to, networkId) => {
    if (!from.box.center || !to.box.center) return true
    const fromSide =
      from.box.center.x + from.pin.offset.x < component0Center.x
        ? "left"
        : "right"
    const toSide =
      to.box.center.x + to.pin.offset.x < component0Center.x ? "left" : "right"
    return fromSide === toSide
  }
)

getBpcGraphWlDistance(a, b)

Compute graph distance based on the "bag of colors" from a Weisfeiler-Leman algorithm. This algorithm runs several iterations of "color hashes" to create a "bag of colors" for each graph, a Jaccard index is then computed between the bags of colors.

ForceDirectedLayoutSolver

Physics based solver for positioning boxes

All type definitions can be imported from bpc-graph as well and are located in lib/types.ts.

getBoxSideSubgraph({ bpcGraph, boxId, side })

Get the subgraph of one side of a box with all connections

mergeBoxSideSubgraphs(graphs)

Merge two subgraphs into a single graph

import { mergeBoxSideSubgraphs } from "bpc-graph"

const mergedGraph = mergeBoxSideSubgraphs([leftSubgraph, rightSubgraph])

convertToFlatBpcGraph(graph)

Flatten a BPC graph into nodes and undirected edges. This is performed prior to constructing adjacency matrices. This changes the representation of the graph from a 2 layer hierarchy to a flat list of nodes and edges.

convertFromFlatBpcGraph(flatBpcGraph)

Rebuild a BPC graph from the flat representation