X-Authentication-Warning:	delorie.com: mail set sender to geda-user-bounces using -f
X-Recipient:	geda-user AT delorie DOT com
DKIM-Signature:	v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=gmail.com; s=20120113;
	h=mime-version:in-reply-to:references:date:message-id:subject:from:to
	:content-type;
	bh=mfMDQuwXTR43yDt8Baq8P4Bk1c3pIrtbfIK3ZvXDEmc=;
	b=uZ2iqc0fINJw+Xis42xW2Sas2s0TFe90aykttbGlp9J+KhKrvcffOAa8jtdqCx103e
	eLLpfCFDSrCNCo94Us6WvNb3tfrEPHZiVlqMuf+dXgE1zcQyKFlUmFs+zmykoj+L4+tI
	AO/OQcqHp6Se/hppNTfdjNV2O7QztHjEh8t3SO9xhk4zfvusU7tZO80nx6kNzQNsnFdX
	J6aPhQ/Skgj0+03gHfAMCZpeya00T5O2PvY/6VCSnxa4fXyELTlRgpWLHL86NJfZ00JJ
	nJNVEK5f/udOxB5gmukvYCSdPfOGUDUXOBtFDhmVwQSBeBozTmwR9m3PLbw/Xq4NLs7q
	Fgag==
MIME-Version:	1.0
In-Reply-To:	<alpine.DEB.2.00.1212111935190.26605@igor2priv>
References:	<20121204183305 DOT 6b04c0dc AT jive DOT levalinux DOT org>
	<20121208112649 DOT 388a9d22 AT jive DOT levalinux DOT org>
	<1355011808 DOT 19390 DOT 8 DOT camel AT localhost>
	<alpine DOT DEB DOT 2 DOT 00 DOT 1212090407031 DOT 26605 AT igor2priv>
	<1355188647 DOT 12937 DOT 14 DOT camel AT localhost>
	<alpine DOT DEB DOT 2 DOT 00 DOT 1212110530020 DOT 26605 AT igor2priv>
	<alpine DOT DEB DOT 2 DOT 00 DOT 1212111935190 DOT 26605 AT igor2priv>
Date:	Tue, 11 Dec 2012 13:18:46 -0900
Message-ID:	<CAC4O8c__Yhb8ZijkVeZzELtNMAO8-=V3aDiEdiCC=BPMPy67Xw@mail.gmail.com>
Subject:	Re: [geda-user] Find rat lines
From:	Britton Kerin <britton DOT kerin AT gmail DOT com>
To:	geda-user AT delorie DOT com
Reply-To:	geda-user AT delorie DOT com
Errors-To:	nobody AT delorie DOT com
X-Mailing-List:	geda-user AT delorie DOT com
X-Unsubscribes-To:	listserv AT delorie DOT com

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.)

Britton

- Raw text -