**Mail Archives: geda-user/2012/12/12/15:19:28**
On Tue, 11 Dec 2012, Britton Kerin wrote:
> On Tue, Dec 11, 2012 at 9:59 AM, <gedau AT igor2 DOT repo DOT hu> wrote:
>>
>>
>> On Tue, 11 Dec 2012, gedau AT igor2 DOT repo DOT hu wrote:
>>
>>> I can ask a friend today who is good in graph theory.
>>
>>
>> Today we sat together and I demonstrated the problem in PCB and described
>> the details. After modelling the problem (graphs) he evaluated both
>> solutions (propagation nets and finding cutting edges).
>>
>> After decomposing the problem, he concluded that finding the cutting edges
>> may be an NP problem (in case it is important to minimize the number of
>> cuts) and would be impossible to solve on a large board with a complicated
>> situation (multiple traces causing shorts).
>
> Perhaps I don't understand what's being done, but there are some faster
> minimum-cut algorithms:
>
> http://en.wikipedia.org/wiki/Minimum_cut
> http://en.wikipedia.org/wiki/Karger%27s_algorithm
>
> It seems like the difficulty would be keeping the graph up-to-date across
> all existing PCB operations (part move, past, manual wire, etc.)
>
It turned out it was not you who didn't understand what's being done here,
but me who didn't understand how it is being done with minimum cut.
My friend showed me a great approach how to apply this solution on our
problme. Using the original connection graph of the two shorted
net (enchanched netlist with the line segments and object forming new
edges and virtual nodes) wouldn't work because it would find the minimum
cut to split the whole graph in two. We need to modify the graph to get
minimal cut to respect what should stay on one part and what should stay
on the other.
The modification is introducing two new virtual nodes called S and T (this
is some sort of convention, I think). Connect S to each net1 nodes with
edges of infinite weight; connect T to each net2 nodes with edges of
infinite weight. Assign a finite number (1, or the length of the line
segment) to all other edges. If minimal cut is ran on this new graph, it
will never cut an infinite weight edge, thus we keep our nets togheter.
It will cut finite weighted edges minimizing total weight cut, resolving
our short.
If all original edges are assigned weight 1, it will find the minimum
amount of cuts needed for resolving the short.
Regards,
Tibor

*- Raw text -*