Lee's PCB routing algorithm. Construct with list of connections between nodes (i.e. topology) and list of coordinates of nodes (can be vector::zero) More...

Collaboration diagram for router:

[legend]

Public Member Functions
	router (const labelListList &connections, const List< point > &coords)
	Construct from connections, route later. More...

const labelList &	weights () const

bool	route (const labelList &path, const label pathValue)
	Find path from first element in path to all other elements. More...

labelList	getRoute (const label pathValue) const
	Extract labels of route with given value. More...

Private Member Functions
label	count (const label weight) const
	Return number of weights. Utility function. More...

void	setWeights (const label weight, const label nodeI)
	Set distance from nodeI. More...

void	fixWeights (const label startNodeI, const label endNodeI, const label nodeI, const label prevNodeI)
	Finds path from nodeI to startNodeI by travelling in direction. More...

bool	shortestPath (const labelList &path, const label pathValue)
	Routes single path. More...

label	getValue (const label) const
	Linear search for element with weight. More...

label	findEndNode (const label startNodeI, const label prevNodeI, const label pathValue) const
	Find node which has no neighbours with pathValue. More...

void	storeRoute (const label startNodeI, const label prevNodeI, const label pathValue, DynamicList< label > &route) const
	Append all pathValue weights to route. More...

	router (const router &)
	Disallow default bitwise copy construct. More...

void	operator= (const router &)
	Disallow default bitwise assignment. More...

Private Attributes
const labelListList	connections_
	Connections. More...

const pointField	coords_
	Coordinates of nodes. More...

labelList	weights_
	Routing table. More...

Detailed Description

Lee's PCB routing algorithm. Construct with list of connections between nodes (i.e. topology) and list of coordinates of nodes (can be vector::zero)

Use e.g.

Enter topology/geometry router cellRouter ( mesh().cellCells(), mesh().cellCentres() );

Try to route connections one by one. Specify unique value (<0) to mark path with. forAll(wantedConnections, i) { bool success = cellRouter.route(wantedConnections[i], -(i+1)); }

The coordinates are only used at the moment for diagonal preference of routing:

So not:

+A | | | | ——+B

But:

+ A |_ |_ |_ |_ | + B

Lee algo: take array with same dimensions as grid of nodes. Initialize to large number. Put 0 at starting point. Now recursively assign neighbours as current value plus one. Stop if you hit node which has smaller number. Phase two is where you search path with lowest value. These are assigned negative number so they for next route are not overwritten.

Source files

Definition at line 99 of file router.H.

Constructor & Destructor Documentation

◆ router() [1/2]

router ( const router & )

private

Disallow default bitwise copy construct.

◆ router() [2/2]

router	(	const labelListList &	connections,
		const List< point > &	coords
	)

Construct from connections, route later.

Definition at line 269 of file router.C.

Member Function Documentation

◆ count()

Foam::label count ( const label weight ) const

private

Return number of weights. Utility function.

Definition at line 32 of file router.C.

References forAll, and router::weights_.

◆ setWeights()

void setWeights	(	const label	weight,
		const label	nodeI
	)

private

Set distance from nodeI.

Definition at line 47 of file router.C.

References forAll.

◆ fixWeights()

void fixWeights	(	const label	startNodeI,
		const label	endNodeI,
		const label	nodeI,
		const label	prevNodeI
	)

private

Finds path from nodeI to startNodeI by travelling in direction.

of lowest weight

Definition at line 75 of file router.C.

References Foam::endl(), forAll, Foam::labelMax, Foam::mag(), n, and WarningInFunction.

Here is the call graph for this function:

◆ shortestPath()

bool shortestPath	(	const labelList &	path,
		const label	pathValue
	)

private

Routes single path.

◆ getValue()

Foam::label getValue ( const label pathValue ) const

private

Linear search for element with weight.

Definition at line 190 of file router.C.

References forAll.

◆ findEndNode()

Foam::label findEndNode	(	const label	startNodeI,
		const label	prevNodeI,
		const label	pathValue
	)		const

private

Find node which has no neighbours with pathValue.

Definition at line 205 of file router.C.

References forAll.

◆ storeRoute()

void storeRoute	(	const label	startNodeI,
		const label	prevNodeI,
		const label	pathValue,
		DynamicList< label > &	route
	)		const

private

Append all pathValue weights to route.

Definition at line 233 of file router.C.

References DynamicList::append(), and forAll.

Here is the call graph for this function:

◆ operator=()

void operator= ( const router & )

private

Disallow default bitwise assignment.

◆ weights()

const labelList& weights ( ) const

inline

Definition at line 184 of file router.H.

References router::weights_.

◆ route()

bool route	(	const labelList &	path,
		const label	pathValue
	)

Find path from first element in path to all other elements.

Mark resulting path in weights with (negative) pathValue. Returns false and does not mark any elements if cannot route.

Definition at line 282 of file router.C.

References Foam::exit(), Foam::FatalError, FatalErrorInFunction, forAll, Foam::labelMax, and path().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getRoute()

Foam::labelList getRoute ( const label pathValue ) const

Extract labels of route with given value.

Definition at line 369 of file router.C.

References DynamicList::append(), Foam::endl(), FatalErrorInFunction, and DynamicList::shrink().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

Field Documentation

◆ connections_

const labelListList connections_

private

Connections.

Definition at line 104 of file router.H.

◆ coords_

const pointField coords_

private

Coordinates of nodes.

Definition at line 107 of file router.H.

◆ weights_

labelList weights_

private

Routing table.

Definition at line 110 of file router.H.

Referenced by router::count(), and router::weights().

The documentation for this class was generated from the following files:

applications/test/router/router.H
applications/test/router/router.C

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ router() [1/2]

◆ router() [2/2]

Member Function Documentation

◆ count()

◆ setWeights()

◆ fixWeights()

◆ shortestPath()

◆ getValue()

◆ findEndNode()

◆ storeRoute()

◆ operator=()

◆ weights()

◆ route()

◆ getRoute()

Field Documentation

◆ connections_

◆ coords_

◆ weights_