**Mail Archives: geda-user/2012/12/13/22:12:30**
On Thu, 13 Dec 2012, Peter Clifton wrote:
> I'll write the graph extractor for the PCB connectivity, but I probably
> won't get a chance now until later next week.
Sounds great!
While extracting, please keep in mind:
- You are free to choose the API of the extractor; at the end I need to
build an adjacency matrix, and I need to know:
- how many nodes we have,
- which node is a member of a net,
- connections between nodes (there may be multiple between the same two)
Maybe we could implement a C function to start the operation, then C
functions for adding nodes or an edges.
- We need as many details as possible, each line segment should be a
separate edge; unfortunately this means we need to split a line segment
if another line/via/poly touches it in the middle.
- We can handle weights for free, if we want, so a generic 'size'
parameter should be extracted. If we don't use it, and there are
multiple minimum cuts available, the algorithm selects one randomly.
- The output currently is the edges to cut. This means if a cut needs to
be done on a long train of serial connected line segments without
junction, it will pick a segment randomly in that (directed by edge
weights). It may be more useful to highlight the whole thread.
Takes like +20 lines to mark them all. If we want weights on edges, this
needs to be done after the solver, but in unweighted case can be done
before the solver on the whole graph, reducing it in size, speeding up
the solver.
- Polys could be handled as nodes, as you suggested earlier, with
thermals being edges. This won't help splitting up a poly to
resolve the short, but at least would display all the thermals the
user needs to remove and then route, which is still an improvement.
- Minimal cut separates the short into two nets; in case there are more
nets participating, we need to go pair by pair. I can do that in the
solver.
Best regards,
Tibor

*- Raw text -*