X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f
X-Recipient: geda-user AT delorie DOT com
Date: Fri, 14 Dec 2012 04:20:13 +0100 (CET)
X-X-Sender: igor2 AT igor2priv
To: geda-user AT delorie DOT com
X-Debug: to=geda-user AT delorie DOT com from="gedau AT igor2 DOT repo DOT hu"
From: gedau AT igor2 DOT repo DOT hu
Subject: Re: [geda-user] Find rat lines - prototype solver for minimal cut
 short-resolving
In-Reply-To: <1355442108.2993.5.camel@localhost>
Message-ID: <alpine.DEB.2.00.1212140356380.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 1212131517470 DOT 26605 AT igor2priv>  <68345C18-5F26-4781-93A5-A6432883B540 AT jump-ing DOT de>
 <1355442108 DOT 2993 DOT 5 DOT camel AT localhost>
User-Agent: Alpine 2.00 (DEB 1167 2008-08-23)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
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



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