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=message-id:subject:from:reply-to:to:date:in-reply-to:references :content-type:x-mailer:mime-version; bh=2qXImOJFqGDgBQ+gLZCMCUCKK66fJ0CXX5MUdD1dVUY=; b=KLTVo5/cnviM2tduWYCIiDT78Z5qksxfzRYOQy5VmgQpXPOBX3M0Lh9GMrU1gN+YVm sCLlR3PB9kJe2aGq0xklo9K2E1wlexrJgyaGQ2anmcchvxS8g0MX8GF544ZyJ78YnznM yLDEBJUUPT5XrxooG9qBaEcGW/0AjFiYYuYW1QMBMibGgwA8PYtdGUekuJjjEbDVAwLr w+bkSSAPjdjJIRriJxHmb1KLu+ZHz6oZVUFFCi1kKGNJGFR8tTaqePaZt3hK/u09R4sR vCk0cK7ZwRDl/jNokl7Wrlsv4ppWlUAiyWm4R8nqkeW4jDURqH8YMc0dqC9H+9qTL9s1 YZVQ== Message-ID: <1355587723.7067.40.camel@monster> Subject: Re: [geda-user] Find rat lines - summary From: Felipe De la Puente Christen To: geda-user AT delorie DOT com Date: Sat, 15 Dec 2012 13:08:43 -0300 In-Reply-To: <1355585479.7067.26.camel@monster> 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> <1355585479 DOT 7067 DOT 26 DOT camel AT monster> Content-Type: multipart/alternative; boundary="=-B5swmuNAyjQE56dAdGEt" X-Mailer: Evolution 3.2.3-0ubuntu6 Mime-Version: 1.0 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 Precedence: bulk --=-B5swmuNAyjQE56dAdGEt Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit Hi, On Sat, 2012-12-15 at 12:31 -0300, Felipe De la Puente Christen wrote: > On Fri, 2012-12-14 at 11:47 +0100, gedau AT igor2 DOT repo DOT hu wrote: > > > > > On Wed, 12 Dec 2012, gedau AT igor2 DOT repo DOT hu wrote: > > > > > > > > > > > On Wed, 12 Dec 2012, gedau AT igor2 DOT repo DOT hu wrote: > > > > > >> Hi all, > > >> > > >> I start to lose track of all the diverse ideas. This post is an effort to > > >> structure the major directions. May it be incomplete, feel free to complete > > >> it. > > >> > > >> In case there is a short... > > >> > > >> I. check whether we have history, since this way the qeustion is "what > > >> user modification introduced the short" which might be more useful > > >> than answer "which object(s) cause(s) the short at the moment". > > >> > > >> 1. bisect using the undo buffer (as Kai-Martin Knaak does manually) - > > >> does not work accross sessions (restart/load) and as Markus > > >> Hitter pointed it out, fails when new netlist is loaded > > >> > > >> 2. tag objects according to their first connection as suggested by Peter > > >> Clifton. This info could be easily saved, making it immune to reload. > > >> Needs more thoughts on some corner cases (new netlist, user moving and > > >> object from one net to another) > > >> > > >> 3. separate connection/netlist history (saved with the PCB). No details > > >> yet. > > >> > > >> II. no history available, try to highlight objects that are most likely to > > >> help the user resolving the short. Nodes of the graph include > > >> junctions, thermals, etc., much more verbose then the netlist. > > >> > > >> 1. propagate nets from all nodes as suggested by Peter Clifton. Doing > > >> this in parallel may cause a collision close to the "real place > > >> of the short" > > >> > > >> 2. find a minimal cut in a way the resulting graphs will reflect the > > >> netlist and highlight only those cutting edge. To the end user this > > >> means we find the smallest modification (deletion) that would fix the > > >> problem (with or without leaving new rat lines). Sounds like an NP > > >> hard problem, no working solution has been proposed in the thread yet. > > >> > > >> 3. Peter Clifton's remove-edges-and-see-how-that-improves-the-situation. > > >> A good metric is needed to make sure we can measure small improvements > > >> in cases where multiple edges must be removed to resolve the short. > > >> Likely to select more edges than the minimum. > > >> > > >> 4. > > >> stage 1 > > >> classify nodes/edges: each belongs to one of the affected nets or is > > >> neutral (could be in multiple nets or could be removed without > > >> breaking only short, not legal redundant connection in a net). Assume > > >> only neutral nodes/edges may participate in the short. Question is how > > >> to do the classification properly: > > >> > > >> a. A modified version of Peter Clifton's propagation idea might work, > > >> needs more thoughts. > > >> b. A similar problem may be known in graph theory; Finding Steiner > > >> tree for a net and trying to fit our nodes/edges on it would keep > > >> the minimal amount (or length) of objects to form the net properly, > > >> and take the rest as neutral. This Breaks badly with redundant > > >> connections in a net. Needs more work. > > >> > > >> stage 2 > > >> from stage 1 we already have sections with multiple nodes/edges that > > >> are neutral and can be blamed for the short. If the user breaks each > > >> such section, the short is resolved. > > >> > > >> a. highlight these sections and let the user break each wherever > > >> (s)he wants (need a way to differentiate between sections) > > >> b. try to find the best place to cut each section > > >> A. middle of the section > > >> B. smallest modification (however we measure that) > > >> C. heat up the section with the modified verison of Joshua Lansford > > >> idea; this may be used to highlight the shortest/smallest > > >> object > > >> > > >> > > > 5. minimal cut (proposed by Britton Kerin_ with the S->T modified > > > connection graph; creating the modified graph is trival and there > > > should be pseudo code and/or libraries available for calculating > > > minimal cut. With uniformly wieghted edges it could reliably find the > > > smallest amount of cuts resolving the short. > > > > > > > > > > > > > III. manual net tagging > > Do not use I. or II., require(?) the user to manually select a net > > for each object placed and highlight shorts, as proposed by John Doty > > and Levente Kovacs. > > > > Hi, > > Am I missing something about III? > > I see all copper objects being floating (i.e. no net attribute set) by > default unless you are explicitly routing already netlisted objects, > in which case the copper will automatically adopt the net attribute of > the startpoint. > > What happens when a tagged copper object touches a floating copper > object? > > Possible Handling Procedure: > > 1. Keep register(hash table?) of floating copper objects, and its > possible single associate (a tagged copper object). The concept evolved while I wrote the message. Remove the word "single" in above statement. > > 2. if the tool finds itself adding a new tagged cooper associate to > the floating copper object: > > 2.1 if the new associate has the same net attribute of the others, > you can add it to the associates list. > > 2.2. if the new associate has a different net attribute than the > others, stop right there and throw the user a dialog exposing the > situation (a floating copper object is shorting different nets), > letting him take actions accordingly. You have enough information here > to describe the situation clearly. > > 3. If the tool finds itself adding a new floating object associate, > merge them as a single floating copper object group. > Well, we have the concept of copper groups here. There can be multiple copper groups with the same net attribute. They can even be connected through floating copper groups, BUT if you directly connect two different groups with the same net attribute, then they get merged. What happens when you disconnect a piece (or group) of copper from an already tagged copper group? You create a new floating copper group, UNLESS the detached copper group still has netlist nodes giving it a net attribute, in which case we have a new copper group with the same net attribute. Now... we can discuss if we really need to keep track of floating groups at all, because we can also automatically merge a floating copper group with the first tagged coper group it touches (but I have the felling that's not a good idea, I'm not sure why yet... may be the origin of each copper group is relevant information). > > That way you avoid annoying (and unneeded) warnings and manual net > attribute settings. > > I don't see the user having to manually select a net for each object > so far... > > Does it make any sense? > > Thanks, Felipe. > --=-B5swmuNAyjQE56dAdGEt Content-Type: text/html; charset="utf-8" Content-Transfer-Encoding: 7bit Hi,

On Sat, 2012-12-15 at 12:31 -0300, Felipe De la Puente Christen wrote:
On Fri, 2012-12-14 at 11:47 +0100, gedau AT igor2 DOT repo DOT hu wrote: 

On Wed, 12 Dec 2012, gedau AT igor2 DOT repo DOT hu wrote:

>
>
> On Wed, 12 Dec 2012, gedau AT igor2 DOT repo DOT hu wrote:
>
>> Hi all,
>> 
>> I start to lose track of all the diverse ideas. This post is an effort to 
>> structure the major directions. May it be incomplete, feel free to complete 
>> it.
>> 
>> In case there is a short...
>> 
>> I. check whether we have history, since this way the qeustion is "what
>>   user modification introduced the short" which might be more useful
>>   than answer "which object(s) cause(s) the short at the moment".
>> 
>> 1. bisect using the undo buffer (as Kai-Martin Knaak does manually) -
>>    does not work accross sessions (restart/load) and as Markus
>>    Hitter pointed it out, fails when new netlist is loaded
>> 
>> 2. tag objects according to their first connection as suggested by Peter
>>    Clifton. This info could be easily saved, making it immune to reload.
>>    Needs more thoughts on some corner cases (new netlist, user moving and
>>    object from one net to another)
>> 
>> 3. separate connection/netlist history (saved with the PCB). No details
>>    yet.
>> 
>> II. no history available, try to highlight objects that are most likely to
>>    help the user resolving the short. Nodes of the graph include
>>    junctions, thermals, etc., much more verbose then the netlist.
>> 
>> 1. propagate nets from all nodes as suggested by Peter Clifton. Doing
>>    this in parallel may cause a collision close to the "real place
>>    of the short"
>> 
>> 2. find a minimal cut in a way the resulting graphs will reflect the
>>    netlist and highlight only those cutting edge. To the end user this
>>    means we find the smallest modification (deletion) that would fix the
>>    problem (with or without leaving new rat lines). Sounds like an NP
>>    hard problem, no working solution has been proposed in the thread yet.
>> 
>> 3. Peter Clifton's remove-edges-and-see-how-that-improves-the-situation.
>>    A good metric is needed to make sure we can measure small improvements
>>    in cases where multiple edges must be removed to resolve the short.
>>    Likely to select more edges than the minimum.
>> 
>> 4.
>>   stage 1
>>    classify nodes/edges: each belongs to one of the affected nets or is
>>    neutral (could be in multiple nets or could be removed without
>>    breaking only short, not legal redundant connection in a net). Assume
>>    only neutral nodes/edges may participate in the short. Question is how
>>    to do the classification properly:
>>
>>    a. A modified version of Peter Clifton's propagation idea might work,
>>       needs more thoughts.
>>    b. A similar problem may be known in graph theory; Finding Steiner
>>       tree for a net and trying to fit our nodes/edges on it would keep
>>       the minimal amount (or length) of objects to form the net properly,
>>       and take the rest as neutral. This Breaks badly with redundant
>>       connections in a net. Needs more work.
>>
>>   stage 2
>>    from stage 1 we already have sections with multiple nodes/edges that
>>    are neutral and can be blamed for the short. If the user breaks each
>>    such section, the short is resolved.
>>
>>    a. highlight these sections and let the user break each wherever
>>       (s)he wants (need a way to differentiate between sections)
>>    b. try to find the best place to cut each section
>>       A. middle of the section
>>       B. smallest modification (however we measure that)
>>       C. heat up the section with the modified verison of Joshua Lansford
>>          idea; this may be used to highlight the shortest/smallest
>>          object
>> 
>> 
> 5. minimal cut (proposed by Britton Kerin_ with the S->T modified
>    connection graph; creating the modified graph is trival and there
>    should be pseudo code and/or libraries available for calculating
>    minimal cut. With uniformly wieghted edges it could reliably find the
>    smallest amount of cuts resolving the short.
>
>
>

III. manual net tagging
      Do not use I. or II., require(?) the user to manually select a net
      for each object placed and highlight shorts, as proposed by John Doty
      and Levente Kovacs.
Hi,

Am I missing something about III?  

I see all copper objects being floating (i.e. no net attribute set) by default unless you are explicitly routing already netlisted objects, in which case the copper will automatically adopt the net attribute of the startpoint.

What happens when a tagged copper object touches a floating copper object?

Possible Handling Procedure:

1. Keep register(hash table?) of floating copper objects, and its possible single associate (a tagged copper object).

The concept evolved while I wrote the message. Remove the word "single" in above statement.


2. if the tool finds itself adding a new tagged cooper associate to the floating copper object:

2.1 if the new  associate has the same net attribute of the others, you can add it to the associates list.

2.2. if the new associate has a different net attribute than the others, stop right there and throw the user a dialog exposing the situation (a floating copper object is shorting different nets), letting him take actions accordingly. You have enough information here to describe the situation clearly.

3. If the tool finds itself adding a new floating object associate, merge them as a single floating copper object group.


Well, we have the concept of copper groups here. There can be multiple copper groups with the same net attribute. They can even be connected through floating copper groups, BUT if you directly connect two different groups with the same net attribute, then they get merged.

What happens when you disconnect a piece (or group) of copper from an already tagged copper group?

You create a new floating copper group, UNLESS the detached copper group still has netlist nodes giving it a net attribute, in which case we have a new copper group with the same net attribute.

Now... we can discuss if we really need to keep track of floating groups at all, because we can also automatically merge a floating copper group with the first tagged coper group it touches (but I have the felling that's not a good idea, I'm not sure why yet... may be the origin of each copper group is relevant information).


That way you avoid annoying (and unneeded) warnings and manual net attribute settings.

I don't see the user having to manually select a net for each object so far...

Does it make any sense?

Thanks, Felipe.


--=-B5swmuNAyjQE56dAdGEt--