Index: trunk/doc-rnd/TODO
===================================================================
--- trunk/doc-rnd/TODO	(revision 1061)
+++ trunk/doc-rnd/TODO	(revision 1062)
@@ -3,7 +3,6 @@
 		- toporouter
 		- dbus
 		- gpmi
-		- mincut (through stubs?)
 	- move src/3rd/ one level up
 	- remove libstroke or move it in a plugin?
 	- warnings in util/
Index: trunk/scconfig/hooks.c
===================================================================
--- trunk/scconfig/hooks.c	(revision 1061)
+++ trunk/scconfig/hooks.c	(revision 1062)
@@ -65,6 +65,10 @@
 	{"buildin-djopt",  "/local/pcb/djopt/buildin",  arg_true,      "$static link the djopt plugin into the executable"},
 	{"plugin-djopt",   "/local/pcb/djopt/buildin",  arg_false,     "$the djopt plugin is dynamic loadable"},
 
+	{"disable-mincut",  "/local/pcb/mincut/enable",   arg_false,     "$do not compile the mincut"},
+	{"buildin-mincut",  "/local/pcb/mincut/buildin",  arg_true,      "$static link the mincut plugin into the executable"},
+	{"plugin-mincut",   "/local/pcb/mincut/buildin",  arg_false,     "$the mincut plugin is dynamic loadable"},
+
 	{NULL, NULL, NULL, NULL}
 };
 
@@ -151,6 +155,10 @@
 	put("/local/pcb/djopt/enable", strue);
 	put("/local/pcb/djopt/buildin", strue);
 
+	db_mkdir("/local/pcb/mincut");
+	put("/local/pcb/mincut/enable", strue);
+	put("/local/pcb/mincut/buildin", strue);
+
 	return 0;
 }
 
@@ -376,6 +384,7 @@
 	plugin_stat("Puller: ",                "/local/pcb/puller");
 	plugin_stat("Edif: ",                  "/local/pcb/edif");
 	plugin_stat("djopt: ",                 "/local/pcb/djopt");
+	plugin_stat("Mincut: ",                "/local/pcb/mincut");
 
 	if (manual_config)
 		printf("\n\n * NOTE: you may want to edit config.manual.h (user preferences) *\n");
Index: trunk/src/pcb-mincut/proposals.txt
===================================================================
--- trunk/src/pcb-mincut/proposals.txt	(revision 1061)
+++ trunk/src/pcb-mincut/proposals.txt	(nonexistent)
@@ -1,99 +0,0 @@
-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.
-    With further improvments by John Doty and Levente Kovacs with detailed
-    method described by Chris Smith.
-
- 3. separate connection/netlist history (saved with the PCB). No details
-    yet. Might be the same as I/2.
-
- 4. Markus Hitter's proposal of pinning down rat lines later converted to
-    to copper. (This is not strictly about keeping track of object
-    history, unless we consider pinned down rats as history of a later copper
-    trace)
-
-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.
-
- 6. pick a random path from a random pin/pad of net1 to another random
-    pin/pad of net2 and let the user resolve this short. Once this is done,
-    the process can be repeated until all shorts are eliminated. Proposed
-    by Russell Dill.
-
-III. manual net tagging
-
- 1. 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.
-
- 2. I/2 combined with III/1; by default it follows I/2 but the user can
-    chose to manually edit tags as in III/1.
-
-
-
Index: trunk/src/pcb-mincut/load.c
===================================================================
--- trunk/src/pcb-mincut/load.c	(revision 1061)
+++ trunk/src/pcb-mincut/load.c	(nonexistent)
@@ -1,271 +0,0 @@
-/*    pcb-mincut, a prototype project demonstrating how to highlight shorts
- *    Copyright (C) 2012 Tibor 'Igor2' Palinkas
- *
- *   This program is free software; you can redistribute it and/or modify
- *   it under the terms of the GNU General Public License as published by
- *   the Free Software Foundation; either version 2 of the License, or
- *   (at your option) any later version.
- *
- *   This program is distributed in the hope that it will be useful,
- *   but WITHOUT ANY WARRANTY; without even the implied warranty of
- *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *   GNU General Public License for more details.
- *
- *   You should have received a copy of the GNU General Public License along
- *   with this program; if not, write to the Free Software Foundation, Inc.,
- *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
-*/
-
-#include <stdlib.h>
-#include <stdio.h>
-#include <string.h>
-#include <assert.h>
-#include "genht/htsi.h"
-#include "graph.h"
-
-/*#define DEBUG_GR*/
-
-/* maximum number of nodes */
-#define MAXNODES 1024
-
-/* maximum length of a name */
-#define NAMELEN 128
-
-/* how many edges net nodes are connected with - this would balance
-   mincut to avoid cutting such connections */
-#define NET_EDGES 8
-
-#define isspc(c) (((c) == ' ') || ((c) == '\t'))
-#define isid(c) ((((c) >= 'a') && ((c) <= 'z')) || (((c) >= 'A') && ((c) <= 'Z')) || (((c) >= '0') && ((c) <= '9')) || ((c) == '_'))
-
-htsi_t *name2node = NULL;              /* hash for looking up known node name -> node id pairs */
-char *node2name[MAXNODES] = {NULL};
-int num_nodes;
-
-static unsigned int keyhash(char *key) {
-	unsigned char *p = (unsigned char *)key;
-	unsigned int hash = 0;
-
-	while (*p)
-		hash += (hash << 2) + *p++;
-	return hash;
-}
-
-static int keyeq(char *a, char *b) {
-	char *pa = (char *)a;
-	char *pb = (char *)b;
-
-	for (; *pa == *pb; pa++, pb++)
-		if (*pa == '\0')
-			return 1;
-	return 0;
-}
-
-
-gr_t *load(FILE *f)
-{
-	int lineno;
-	int nets[2][MAXNODES];  /* nodes in nets */
-	int neut[MAXNODES];     /* neutral nodes */
-	int nn_net[2];          /* number of nodes in nets */
-	int nn_neut;            /* number of nodes in nets */
-	int nodes_fin;          /* 1 after reading the first conn line */
-	gr_t *g = NULL;
-
-/* peek at next char and return if it is a newline */
-#define return_at_eol \
-	do { \
-		char c; \
-		c = fgetc(f); \
-		if ((c == '\r') || (c == '\n')) \
-			return; \
-		ungetc(c, f); \
-	} while(0)
-
-
-	/* eat up space and tabs */
-	void eat_space(void)
-	{
-		int c;
-		do {
-			c = fgetc(f);
-		} while(isspc(c));
-		ungetc(c, f);
-	}
-
-	/* load next token of type id */
-	const char *token_id(void)
-	{
-		static char id[NAMELEN];
-		char *s;
-		int n;
-
-		n = sizeof(id) - 1;
-		s = id-1;
-		do {
-			s++;
-			*s = fgetc(f);
-			n--;
-			if (n <= 0) {
-				*s = '\0';
-				fprintf(stderr, "Error: name too long: %s...\n", id);
-			}
-		} while(isid(*s));
-		ungetc(*s, f);
-		*s = '\0';
-		return id;
-	}
-
-	/* read next id token and look it up as a node name; if it does not
-	   exist and alloc is 1, allocate it; if it does not exist and
-	   alloc is 0, abort with error */
-	int token_node(int alloc)
-	{
-		const char *id = token_id();
-		if (htsi_has(name2node, (char *)id))
-			return htsi_get(name2node, (char *)id);
-		if (alloc) {
-			node2name[num_nodes] = strdup(id);
-			htsi_set(name2node, node2name[num_nodes], num_nodes);
-			return num_nodes++;
-		}
-		fprintf(stderr, "Error: unknown node %s\n", id);
-		abort();
-	}
-
-	/* load a net1 or net2 statement */
-	void load_net(int net)
-	{
-		int node;
-		if (nodes_fin) {
-			fprintf(stderr, "Error: net%d after conn\n", net);
-			abort();
-		}
-		/* load each node and append */
-		while(1) {
-			eat_space();
-			return_at_eol;
-			node = token_node(1);
-			nets[net][nn_net[net]] = node;
-			nn_net[net]++;
-		}
-	}
-
-	/* load a neut statement */
-	void load_neut(void)
-	{
-		int node;
-		if (nodes_fin) {
-			fprintf(stderr, "Error: neut after conn\n");
-			abort();
-		}
-		/* load each node and append */
-		while(1) {
-			eat_space();
-			return_at_eol;
-			node = token_node(1);
-			neut[nn_neut] = node;
-			nn_neut++;
-		}
-	}
-
-	/* load a list of connections */
-	void load_conn(void)
-	{
-		int n1, n2;
-		char c;
-
-		/* if this is the first conn, create the graph */
-		if (!nodes_fin) {
-			g = gr_alloc(num_nodes);
-			g->node2name = node2name;
-		}
-		nodes_fin = 1;
-
-		/* load each n1-n2 pair */
-		while(1) {
-			eat_space();
-			return_at_eol;
-			n1 = token_node(0);
-			c = fgetc(f);
-			if (c != '-') {
-				fprintf(stderr, "Error: expected '-' between nodes in conn list (got '%c' instead)\n", c);
-				abort();
-			}
-			n2 = token_node(0);
-			gr_add_(g, n1, n2, 1);
-		}
-	}
-
-	name2node = htsi_alloc(keyhash, keyeq);
-	node2name[0] = strdup("(S)"); htsi_set(name2node, node2name[0], 0);
-	node2name[1] = strdup("(T)"); htsi_set(name2node, node2name[1], 1);
-	num_nodes = 2;
-	nn_net[0] = 0;
-	nn_net[1] = 0;
-	nn_neut = 0;
-
-	nodes_fin = 0;
-	lineno = 0;
-	while(!(feof(f))) {
-		char cmd[6];
-		lineno++;
-		eat_space();
-		*cmd = '\0';
-		fgets(cmd, 5, f);
-		if (*cmd == '#') {
-			char s[1024]; /* will break for comment lines longer than 1k */
-			fgets(s, sizeof(s), f);
-			continue;
-		}
-		if ((*cmd == '\n') || (*cmd == '\t') || (*cmd == '\0'))
-			continue;
-		if (strcmp(cmd, "net1") == 0)
-			load_net(0);
-		else if (strcmp(cmd, "net2") == 0)
-			load_net(1);
-		else if (strcmp(cmd, "neut") == 0)
-			load_neut();
-		else if (strcmp(cmd, "conn") == 0)
-			load_conn();
-	}
-
-
-#ifdef DEBUG_GR
-	gr_print(g, stdout, "(input0) ");
-	gr_draw(g, "input0", "png");
-#endif
-
-	/* preprocessing nets */
-	{
-		int net, node;
-
-#if 0
-/* this optimization looked like a good idea but fails for O.in because
-   it's always cheaper to cut T-> and S-> bounding than anything else */
-		/* merge net nodes into (S) and (T) */
-		for(net = 0; net < 2; net++)
-			for(node = 0; node < nn_net[net]; node++)
-				gr_merge_nodes(g, net, nets[net][node]);
-
-		/* make sure (S) and (T) connections are heavy */
-		for(net = 0; net < 2; net++)
-			for(node = 0; node < g->n; node++)
-				if (gr_get_(g, net, node))
-					gr_add_(g, net, node, NET_EDGES);
-#endif
-
-		/* make sure (S) and (T) connections are heavy */
-		for(net = 0; net < 2; net++)
-			for(node = 0; node < nn_net[net]; node++)
-				gr_add_(g, net, nets[net][node], NET_EDGES);
-	}
-
-#ifdef DEBUG_GR
-	gr_print(g, stdout, "(input1) ");
-	gr_draw(g, "input1", "png");
-#endif
-
-	return g;
-}
-
Index: trunk/src/pcb-mincut/graph.c
===================================================================
--- trunk/src/pcb-mincut/graph.c	(revision 1061)
+++ trunk/src/pcb-mincut/graph.c	(nonexistent)
@@ -1,136 +0,0 @@
-/*    pcb-mincut, a prototype project demonstrating how to highlight shorts
- *    Copyright (C) 2012 Tibor 'Igor2' Palinkas
- *
- *   This program is free software; you can redistribute it and/or modify
- *   it under the terms of the GNU General Public License as published by
- *   the Free Software Foundation; either version 2 of the License, or
- *   (at your option) any later version.
- *
- *   This program is distributed in the hope that it will be useful,
- *   but WITHOUT ANY WARRANTY; without even the implied warranty of
- *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *   GNU General Public License for more details.
- *
- *   You should have received a copy of the GNU General Public License along
- *   with this program; if not, write to the Free Software Foundation, Inc.,
- *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
-*/
-
-#include <stdlib.h>
-#include <string.h>
-#include "graph.h"
-
-/* allocate a new graph of n nodes with no edges */
-gr_t *gr_alloc(int n)
-{
-	gr_t *g = malloc(sizeof(gr_t));
-	g->n = n;
-	g->adj = calloc(n * n, sizeof(int));
-	return g;
-}
-
-/* create a new graph by cloning graph g */
-gr_t *gr_clone(gr_t *g)
-{
-	int size = g->n * g->n * sizeof(int);
-	gr_t *o = malloc(sizeof(gr_t));
-
-	o->n = g->n;
-	o->adj = malloc(size);
-	memcpy(o->adj, g->adj, size);
-	o->node2name = g->node2name;
-	return o;
-}
-
-/* free all resouces used by the graph */
-void gr_free(gr_t *g)
-{
-	free(g->adj);
-	free(g);
-}
-
-void gr_merge_nodes(gr_t *g, int n1, int n2)
-{
-	int n;
-	gr_bound_chk(g, n1, n2);
-
-	for(n = 0; n < g->n; n++) {
-		if (n != n2)
-			gr_add_(g, n, n1, gr_set_(g, n, n2, 0));
-		else
-			gr_add_(g, n1, n1, gr_set_(g, n2, n2, 0)/2);
-	}
-}
-
-void gr_print(gr_t *g, FILE *f, const char *prefix)
-{
-	int x, y;
-
-	fprintf(f, "%s      ", prefix);
-	for(x = 0; x < g->n; x++)
-		fprintf(f, "% 4d ", x);
-	fprintf(f, "\n");
-
-	for(y = 0; y < g->n; y++) {
-		fprintf(f, "%s % 4d ", prefix, y);
-		for(x = 0; x < g->n; x++)
-			fprintf(f, "% 4d ", gr_get_(g, x, y));
-		fprintf(f, "\n");
-	}
-	fprintf(f, "%s\n", prefix);
-	if (g->node2name != NULL) {
-	fprintf(f, "%snames:\n", prefix);
-		for(x = 0; x < g->n; x++)
-			fprintf(f, "%s % 4d=%s\n", prefix, x, g->node2name[x]);
-	}
-}
-
-int gr_draw(gr_t *g, const char *name, const char *type)
-{
-	char *cmd;
-	FILE *f;
-	int x, y;
-
-	if (type == NULL)
-		type = "png";
-
-	cmd = malloc(strlen(type)*2 + strlen(name) + 64);
-	sprintf(cmd, "dot -T%s -o %s.%s", type, name, type);
-	f = popen(cmd, "w");
-	if (f == NULL)
-		return -1;
-
-	fprintf(f, "graph %s {\n", name);
-
-	if (g->node2name != NULL)
-		for(x = 0; x < g->n; x++)
-			fprintf(f, "\t% 4d[label=\"%d\\n%s\"]\n", x, x, g->node2name[x] == NULL ? "NULL" : g->node2name[x]);
-
-	for(y = 0; y < g->n; y++) {
-		for(x = y; x < g->n; x++) {
-
-#ifdef MULTI_EDGE
-			int n;
-			for(n = gr_get_(g, x, y); n > 0; n--)
-				fprintf(f, "\t% 4d -- % 4d\n", x, y);
-#else
-			if (gr_get_(g, x, y) > 0)
-				fprintf(f, "\t% 4d -- % 4d [label=\"*%d\"]\n", x, y, gr_get_(g, x, y));
-#endif
-		}
-	}
-
-	fprintf(f, "}\n");
-	pclose(f);
-	return 0;
-}
-
-int gr_node_edges(gr_t *g, int node)
-{
-	int n, sum;
-	sum = 0;
-	gr_bound_chk(g, 0, node);
-	for(n = 0; n < g->n; n++)
-		sum += gr_get_(g, n, node);
-	return sum;
-}
Index: trunk/src/pcb-mincut/load.h
===================================================================
--- trunk/src/pcb-mincut/load.h	(revision 1061)
+++ trunk/src/pcb-mincut/load.h	(nonexistent)
@@ -1,5 +0,0 @@
-#include <stdio.h>
-#include "graph.h"
-
-/* load example input from FILE f and return the preprocessed graph */
-gr_t *load(FILE *f);
Index: trunk/src/pcb-mincut/main.c
===================================================================
--- trunk/src/pcb-mincut/main.c	(revision 1061)
+++ trunk/src/pcb-mincut/main.c	(nonexistent)
@@ -1,28 +0,0 @@
-#include <stdlib.h>
-#include <stdio.h>
-#include "graph.h"
-#include "load.h"
-#include "solve.h"
-
-#define strempty(s) ((s) == NULL ? "" : (s))
-
-int main()
-{
-	int *best;
-	gr_t *g;
-	int n;
-
-	g = load(stdin);
-	if (g == NULL) {
-		fprintf(stderr, "Failed to load input, exiting\n");
-		exit(1);
-	}
-	best = solve(g);
-	for(n = 0; best[n*2] != -1; n++)
-		printf("%s-%s\n", strempty(g->node2name[best[n*2+0]]), strempty(g->node2name[best[n*2+1]]));
-
-	gr_free(g);
-	free(best);
-
-	return 0;
-}
Index: trunk/src/pcb-mincut/graph.h
===================================================================
--- trunk/src/pcb-mincut/graph.h	(revision 1061)
+++ trunk/src/pcb-mincut/graph.h	(nonexistent)
@@ -1,97 +0,0 @@
-/*    pcb-mincut, a prototype project demonstrating how to highlight shorts
- *    Copyright (C) 2012 Tibor 'Igor2' Palinkas
- *
- *   This program is free software; you can redistribute it and/or modify
- *   it under the terms of the GNU General Public License as published by
- *   the Free Software Foundation; either version 2 of the License, or
- *   (at your option) any later version.
- *
- *   This program is distributed in the hope that it will be useful,
- *   but WITHOUT ANY WARRANTY; without even the implied warranty of
- *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *   GNU General Public License for more details.
- *
- *   You should have received a copy of the GNU General Public License along
- *   with this program; if not, write to the Free Software Foundation, Inc.,
- *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
-*/
-
-#ifndef GRAPH_H
-#define GRAPH_H
-#include <stdio.h>
-#include <assert.h>
-
-typedef struct gr_s {
-	int n;     /* number of nodes */
-	int *adj;  /* adjacency matrix of n*n ints */
-	char **node2name; /* optional node names */
-} gr_t;
-
-/* allocate a new graph of n nodes with no edges */
-gr_t *gr_alloc(int n);
-
-/* create a new graph by cloning graph g */
-gr_t *gr_clone(gr_t *g);
-
-/* free all resouces used by the graph */
-void gr_free(gr_t *g);
-
-
-static inline void gr_bound_chk(gr_t *g, int n1, int n2)
-{
-	assert((n1 >= 0) && (n1 < g->n));
-	assert((n2 >= 0) && (n2 < g->n));
-}
-
-/* return number of edges between nodes n1 and n2 - without checks */
-static inline int gr_get_(gr_t *g, int n1, int n2)
-{
-	return g->adj[n1 * g->n + n2];
-}
-
-/* return number of edges between nodes n1 and n2 - with checks */
-static inline int gr_get(gr_t *g, int n1, int n2)
-{
-	gr_bound_chk(g, n1, n2);
-	return gr_get_(g, n1, n2);
-}
-
-/* return old number of edges between nodes n1 and n2 and change it to newnum - no check*/
-static inline int gr_set_(gr_t *g, int n1, int n2, int newnum)
-{
-	int old;
-	old = g->adj[n1 * g->n + n2];
-	g->adj[n1 * g->n + n2] = newnum;
-	g->adj[n2 * g->n + n1] = newnum;
-	return old;
-}
-
-/* return old number of edges between nodes n1 and n2 and increase it by newnum - no check*/
-static inline int gr_add_(gr_t *g, int n1, int n2, int newnum)
-{
-	int old;
-	old = g->adj[n1 * g->n + n2];
-	g->adj[n1 * g->n + n2] += newnum;
-	g->adj[n2 * g->n + n1] += newnum;
-	return old;
-}
-
-/* return old number of edges between nodes n1 and n2 and change it to newnum - check*/
-static inline int gr_set(gr_t *g, int n1, int n2, int newnum)
-{
-	gr_bound_chk(g, n1, n2);
-	return gr_set_(g, n1, n2, newnum);
-}
-
-/* merge two nodes n1 and n2 (contraction) */
-void gr_merge_nodes(gr_t *g, int n1, int n2);
-
-/* print the connection matrix */
-void gr_print(gr_t *g, FILE *f, const char *prefix);
-
-/* draw graph using graphviz/dot */
-int gr_draw(gr_t *g, const char *name, const char *type);
-
-/* return total number of edges of a node */
-int gr_node_edges(gr_t *g, int node);
-#endif
Index: trunk/src/pcb-mincut/COPYING
===================================================================
--- trunk/src/pcb-mincut/COPYING	(revision 1061)
+++ trunk/src/pcb-mincut/COPYING	(nonexistent)
@@ -1,339 +0,0 @@
-                    GNU GENERAL PUBLIC LICENSE
-                       Version 2, June 1991
-
- Copyright (C) 1989, 1991 Free Software Foundation, Inc.,
- 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
- Everyone is permitted to copy and distribute verbatim copies
- of this license document, but changing it is not allowed.
-
-                            Preamble
-
-  The licenses for most software are designed to take away your
-freedom to share and change it.  By contrast, the GNU General Public
-License is intended to guarantee your freedom to share and change free
-software--to make sure the software is free for all its users.  This
-General Public License applies to most of the Free Software
-Foundation's software and to any other program whose authors commit to
-using it.  (Some other Free Software Foundation software is covered by
-the GNU Lesser General Public License instead.)  You can apply it to
-your programs, too.
-
-  When we speak of free software, we are referring to freedom, not
-price.  Our General Public Licenses are designed to make sure that you
-have the freedom to distribute copies of free software (and charge for
-this service if you wish), that you receive source code or can get it
-if you want it, that you can change the software or use pieces of it
-in new free programs; and that you know you can do these things.
-
-  To protect your rights, we need to make restrictions that forbid
-anyone to deny you these rights or to ask you to surrender the rights.
-These restrictions translate to certain responsibilities for you if you
-distribute copies of the software, or if you modify it.
-
-  For example, if you distribute copies of such a program, whether
-gratis or for a fee, you must give the recipients all the rights that
-you have.  You must make sure that they, too, receive or can get the
-source code.  And you must show them these terms so they know their
-rights.
-
-  We protect your rights with two steps: (1) copyright the software, and
-(2) offer you this license which gives you legal permission to copy,
-distribute and/or modify the software.
-
-  Also, for each author's protection and ours, we want to make certain
-that everyone understands that there is no warranty for this free
-software.  If the software is modified by someone else and passed on, we
-want its recipients to know that what they have is not the original, so
-that any problems introduced by others will not reflect on the original
-authors' reputations.
-
-  Finally, any free program is threatened constantly by software
-patents.  We wish to avoid the danger that redistributors of a free
-program will individually obtain patent licenses, in effect making the
-program proprietary.  To prevent this, we have made it clear that any
-patent must be licensed for everyone's free use or not licensed at all.
-
-  The precise terms and conditions for copying, distribution and
-modification follow.
-
-                    GNU GENERAL PUBLIC LICENSE
-   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
-
-  0. This License applies to any program or other work which contains
-a notice placed by the copyright holder saying it may be distributed
-under the terms of this General Public License.  The "Program", below,
-refers to any such program or work, and a "work based on the Program"
-means either the Program or any derivative work under copyright law:
-that is to say, a work containing the Program or a portion of it,
-either verbatim or with modifications and/or translated into another
-language.  (Hereinafter, translation is included without limitation in
-the term "modification".)  Each licensee is addressed as "you".
-
-Activities other than copying, distribution and modification are not
-covered by this License; they are outside its scope.  The act of
-running the Program is not restricted, and the output from the Program
-is covered only if its contents constitute a work based on the
-Program (independent of having been made by running the Program).
-Whether that is true depends on what the Program does.
-
-  1. You may copy and distribute verbatim copies of the Program's
-source code as you receive it, in any medium, provided that you
-conspicuously and appropriately publish on each copy an appropriate
-copyright notice and disclaimer of warranty; keep intact all the
-notices that refer to this License and to the absence of any warranty;
-and give any other recipients of the Program a copy of this License
-along with the Program.
-
-You may charge a fee for the physical act of transferring a copy, and
-you may at your option offer warranty protection in exchange for a fee.
-
-  2. You may modify your copy or copies of the Program or any portion
-of it, thus forming a work based on the Program, and copy and
-distribute such modifications or work under the terms of Section 1
-above, provided that you also meet all of these conditions:
-
-    a) You must cause the modified files to carry prominent notices
-    stating that you changed the files and the date of any change.
-
-    b) You must cause any work that you distribute or publish, that in
-    whole or in part contains or is derived from the Program or any
-    part thereof, to be licensed as a whole at no charge to all third
-    parties under the terms of this License.
-
-    c) If the modified program normally reads commands interactively
-    when run, you must cause it, when started running for such
-    interactive use in the most ordinary way, to print or display an
-    announcement including an appropriate copyright notice and a
-    notice that there is no warranty (or else, saying that you provide
-    a warranty) and that users may redistribute the program under
-    these conditions, and telling the user how to view a copy of this
-    License.  (Exception: if the Program itself is interactive but
-    does not normally print such an announcement, your work based on
-    the Program is not required to print an announcement.)
-
-These requirements apply to the modified work as a whole.  If
-identifiable sections of that work are not derived from the Program,
-and can be reasonably considered independent and separate works in
-themselves, then this License, and its terms, do not apply to those
-sections when you distribute them as separate works.  But when you
-distribute the same sections as part of a whole which is a work based
-on the Program, the distribution of the whole must be on the terms of
-this License, whose permissions for other licensees extend to the
-entire whole, and thus to each and every part regardless of who wrote it.
-
-Thus, it is not the intent of this section to claim rights or contest
-your rights to work written entirely by you; rather, the intent is to
-exercise the right to control the distribution of derivative or
-collective works based on the Program.
-
-In addition, mere aggregation of another work not based on the Program
-with the Program (or with a work based on the Program) on a volume of
-a storage or distribution medium does not bring the other work under
-the scope of this License.
-
-  3. You may copy and distribute the Program (or a work based on it,
-under Section 2) in object code or executable form under the terms of
-Sections 1 and 2 above provided that you also do one of the following:
-
-    a) Accompany it with the complete corresponding machine-readable
-    source code, which must be distributed under the terms of Sections
-    1 and 2 above on a medium customarily used for software interchange; or,
-
-    b) Accompany it with a written offer, valid for at least three
-    years, to give any third party, for a charge no more than your
-    cost of physically performing source distribution, a complete
-    machine-readable copy of the corresponding source code, to be
-    distributed under the terms of Sections 1 and 2 above on a medium
-    customarily used for software interchange; or,
-
-    c) Accompany it with the information you received as to the offer
-    to distribute corresponding source code.  (This alternative is
-    allowed only for noncommercial distribution and only if you
-    received the program in object code or executable form with such
-    an offer, in accord with Subsection b above.)
-
-The source code for a work means the preferred form of the work for
-making modifications to it.  For an executable work, complete source
-code means all the source code for all modules it contains, plus any
-associated interface definition files, plus the scripts used to
-control compilation and installation of the executable.  However, as a
-special exception, the source code distributed need not include
-anything that is normally distributed (in either source or binary
-form) with the major components (compiler, kernel, and so on) of the
-operating system on which the executable runs, unless that component
-itself accompanies the executable.
-
-If distribution of executable or object code is made by offering
-access to copy from a designated place, then offering equivalent
-access to copy the source code from the same place counts as
-distribution of the source code, even though third parties are not
-compelled to copy the source along with the object code.
-
-  4. You may not copy, modify, sublicense, or distribute the Program
-except as expressly provided under this License.  Any attempt
-otherwise to copy, modify, sublicense or distribute the Program is
-void, and will automatically terminate your rights under this License.
-However, parties who have received copies, or rights, from you under
-this License will not have their licenses terminated so long as such
-parties remain in full compliance.
-
-  5. You are not required to accept this License, since you have not
-signed it.  However, nothing else grants you permission to modify or
-distribute the Program or its derivative works.  These actions are
-prohibited by law if you do not accept this License.  Therefore, by
-modifying or distributing the Program (or any work based on the
-Program), you indicate your acceptance of this License to do so, and
-all its terms and conditions for copying, distributing or modifying
-the Program or works based on it.
-
-  6. Each time you redistribute the Program (or any work based on the
-Program), the recipient automatically receives a license from the
-original licensor to copy, distribute or modify the Program subject to
-these terms and conditions.  You may not impose any further
-restrictions on the recipients' exercise of the rights granted herein.
-You are not responsible for enforcing compliance by third parties to
-this License.
-
-  7. If, as a consequence of a court judgment or allegation of patent
-infringement or for any other reason (not limited to patent issues),
-conditions are imposed on you (whether by court order, agreement or
-otherwise) that contradict the conditions of this License, they do not
-excuse you from the conditions of this License.  If you cannot
-distribute so as to satisfy simultaneously your obligations under this
-License and any other pertinent obligations, then as a consequence you
-may not distribute the Program at all.  For example, if a patent
-license would not permit royalty-free redistribution of the Program by
-all those who receive copies directly or indirectly through you, then
-the only way you could satisfy both it and this License would be to
-refrain entirely from distribution of the Program.
-
-If any portion of this section is held invalid or unenforceable under
-any particular circumstance, the balance of the section is intended to
-apply and the section as a whole is intended to apply in other
-circumstances.
-
-It is not the purpose of this section to induce you to infringe any
-patents or other property right claims or to contest validity of any
-such claims; this section has the sole purpose of protecting the
-integrity of the free software distribution system, which is
-implemented by public license practices.  Many people have made
-generous contributions to the wide range of software distributed
-through that system in reliance on consistent application of that
-system; it is up to the author/donor to decide if he or she is willing
-to distribute software through any other system and a licensee cannot
-impose that choice.
-
-This section is intended to make thoroughly clear what is believed to
-be a consequence of the rest of this License.
-
-  8. If the distribution and/or use of the Program is restricted in
-certain countries either by patents or by copyrighted interfaces, the
-original copyright holder who places the Program under this License
-may add an explicit geographical distribution limitation excluding
-those countries, so that distribution is permitted only in or among
-countries not thus excluded.  In such case, this License incorporates
-the limitation as if written in the body of this License.
-
-  9. The Free Software Foundation may publish revised and/or new versions
-of the General Public License from time to time.  Such new versions will
-be similar in spirit to the present version, but may differ in detail to
-address new problems or concerns.
-
-Each version is given a distinguishing version number.  If the Program
-specifies a version number of this License which applies to it and "any
-later version", you have the option of following the terms and conditions
-either of that version or of any later version published by the Free
-Software Foundation.  If the Program does not specify a version number of
-this License, you may choose any version ever published by the Free Software
-Foundation.
-
-  10. If you wish to incorporate parts of the Program into other free
-programs whose distribution conditions are different, write to the author
-to ask for permission.  For software which is copyrighted by the Free
-Software Foundation, write to the Free Software Foundation; we sometimes
-make exceptions for this.  Our decision will be guided by the two goals
-of preserving the free status of all derivatives of our free software and
-of promoting the sharing and reuse of software generally.
-
-                            NO WARRANTY
-
-  11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
-FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.  EXCEPT WHEN
-OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
-PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
-OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
-MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS
-TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE
-PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
-REPAIR OR CORRECTION.
-
-  12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
-WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
-REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
-INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
-OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
-TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
-YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
-PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
-POSSIBILITY OF SUCH DAMAGES.
-
-                     END OF TERMS AND CONDITIONS
-
-            How to Apply These Terms to Your New Programs
-
-  If you develop a new program, and you want it to be of the greatest
-possible use to the public, the best way to achieve this is to make it
-free software which everyone can redistribute and change under these terms.
-
-  To do so, attach the following notices to the program.  It is safest
-to attach them to the start of each source file to most effectively
-convey the exclusion of warranty; and each file should have at least
-the "copyright" line and a pointer to where the full notice is found.
-
-    <one line to give the program's name and a brief idea of what it does.>
-    Copyright (C) <year>  <name of author>
-
-    This program is free software; you can redistribute it and/or modify
-    it under the terms of the GNU General Public License as published by
-    the Free Software Foundation; either version 2 of the License, or
-    (at your option) any later version.
-
-    This program is distributed in the hope that it will be useful,
-    but WITHOUT ANY WARRANTY; without even the implied warranty of
-    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-    GNU General Public License for more details.
-
-    You should have received a copy of the GNU General Public License along
-    with this program; if not, write to the Free Software Foundation, Inc.,
-    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
-
-Also add information on how to contact you by electronic and paper mail.
-
-If the program is interactive, make it output a short notice like this
-when it starts in an interactive mode:
-
-    Gnomovision version 69, Copyright (C) year name of author
-    Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
-    This is free software, and you are welcome to redistribute it
-    under certain conditions; type `show c' for details.
-
-The hypothetical commands `show w' and `show c' should show the appropriate
-parts of the General Public License.  Of course, the commands you use may
-be called something other than `show w' and `show c'; they could even be
-mouse-clicks or menu items--whatever suits your program.
-
-You should also get your employer (if you work as a programmer) or your
-school, if any, to sign a "copyright disclaimer" for the program, if
-necessary.  Here is a sample; alter the names:
-
-  Yoyodyne, Inc., hereby disclaims all copyright interest in the program
-  `Gnomovision' (which makes passes at compilers) written by James Hacker.
-
-  <signature of Ty Coon>, 1 April 1989
-  Ty Coon, President of Vice
-
-This General Public License does not permit incorporating your program into
-proprietary programs.  If your program is a subroutine library, you may
-consider it more useful to permit linking proprietary applications with the
-library.  If this is what you want to do, use the GNU Lesser General
-Public License instead of this License.
Index: trunk/src/pcb-mincut/solve.c
===================================================================
--- trunk/src/pcb-mincut/solve.c	(revision 1061)
+++ trunk/src/pcb-mincut/solve.c	(nonexistent)
@@ -1,253 +0,0 @@
-/*    pcb-mincut, a prototype project demonstrating how to highlight shorts
- *    Copyright (C) 2012 Tibor 'Igor2' Palinkas
- *
- *   This program is free software; you can redistribute it and/or modify
- *   it under the terms of the GNU General Public License as published by
- *   the Free Software Foundation; either version 2 of the License, or
- *   (at your option) any later version.
- *
- *   This program is distributed in the hope that it will be useful,
- *   but WITHOUT ANY WARRANTY; without even the implied warranty of
- *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *   GNU General Public License for more details.
- *
- *   You should have received a copy of the GNU General Public License along
- *   with this program; if not, write to the Free Software Foundation, Inc.,
- *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
-*/
-
-#include <stdlib.h>
-#include <string.h>
-#include <math.h>
-#include "solve.h"
-
-/* Karger's algorithm as described in the wikipedia article
-   http://en.wikipedia.org/wiki/Karger%27s_algorithm
-*/
-
-#define BAD 1000000
-
-/*#define DEBUG_MERGES*/
-/*#define DEBUG_TAGS*/
-/*#define DEBUG_SOLVE*/
-
-typedef struct {
-	gr_t *g;
-	int *avail;    /* nodes IDs still avaialble for merging */
-	int *neigh;    /* neighbor list */
-	int *tag;
-	int num_avail; /* number of nodes still avaialble for merging */
-} sstate_t;
-
-static int pick_del(sstate_t *st)
-{
-	int idx, ret, size;
-	idx = rand() % st->num_avail;
-	ret = st->avail[idx];
-	size = (st->num_avail-idx-1) * sizeof(int);
-	if (size > 0)
-		memmove(&st->avail[idx], &st->avail[idx+1], size);
-	st->num_avail--;
-	return ret;
-}
-
-static int pick_neigh(sstate_t *st, int node)
-{
-	int n, num_neigh;
-
-	num_neigh = 0;
-	for(n = 0; n < st->g->n; n++) {
-		if ((n != node) && (gr_get_(st->g, n, node) > 0)) {
-			st->neigh[num_neigh] = n;
-			num_neigh++;
-		}
-	}
-	return st->neigh[rand() % num_neigh];
-}
-
-static void retag(sstate_t *st, int from, int to)
-{
-	int n;
-	for(n = 0; n < st->g->n; n++)
-		if (st->tag[n] == from)
-			st->tag[n] = to;
-}
-
-
-/* clone graph and do a randon contraction */
-int solve_(gr_t *g_, int *cuts)
-{
-	sstate_t st;
-	int n, result, tags;
-	static int solution = -1;
-#ifdef DEBUG_MERGES
-	int cnt = 0;
-	char fn[512];
-#endif
-
-	solution++;
-	st.g = gr_clone(g_);
-	st.avail = malloc(sizeof(int) * st.g->n);
-	st.neigh = malloc(sizeof(int) * st.g->n);
-	st.tag = malloc(sizeof(int) * st.g->n);
-
-#define FREE_ALL() \
-	gr_free(st.g); \
-	free(st.avail); \
-	free(st.neigh); \
-	free(st.tag);
-
-	for(n = 2; n < st.g->n; n++)
-		st.tag[n] = -1;
-	st.tag[0] = 0;
-	st.tag[1] = 1;
-	tags = 2;
-
-	st.num_avail = 0;
-	for(n = 0; n < st.g->n; n++) {
-		if (gr_node_edges(st.g, n) > 0) {
-			st.avail[st.num_avail] = n;
-			st.num_avail++;
-		}
-	}
-
-	while(st.num_avail > 2) {
-		int n1, n2;
-		n2 = pick_del(&st);
-		n1 = pick_neigh(&st, n2);
-#ifndef DEBUG_MERGES
-#ifdef DEBUG_SOLVE
-			printf("Merge %d (%s) into %d (%s)\n", n2, st.g->node2name[n2], n1, st.g->node2name[n1]);
-#endif
-#endif
-		assert(n2 != n1);
-
-		/* propagate tags */
-		if ((st.tag[n1] != -1) && (st.tag[n2] == -1))
-			st.tag[n2] = st.tag[n1];
-		else if ((st.tag[n1] == -1) && (st.tag[n2] != -1))
-			st.tag[n1] = st.tag[n2];
-		else if ((st.tag[n1] == -1) && (st.tag[n2] == -1))
-			st.tag[n1] = st.tag[n2] = tags++;
-		else if ((st.tag[n1] != -1) && (st.tag[n2] != -1)) {
-			if ((st.tag[n1] > 1) && (st.tag[n2] <= 1))
-				retag(&st, st.tag[n1], st.tag[n2]);
-			else if ((st.tag[n2] > 1) && (st.tag[n1] <= 1))
-				retag(&st, st.tag[n2], st.tag[n1]);
-			else {
-				/* tag collision means we won't be able to distinguish between our
-				   two groups and our cut won't resolve the short anyway */
-#ifdef DEBUG_TAGS
-				printf("Tag collision!\n");
-#endif
-				FREE_ALL();
-				return BAD;
-			}
-		}
-
-		gr_merge_nodes(st.g, n1, n2);
-
-#ifdef DEBUG_MERGES
-			sprintf(fn, "contraction_%02d_%02d", solution, cnt);
-			cnt++;
-			gr_draw(st.g, fn, "png");
-			printf("Merge %d into %d, result in %s leaving %d available nodes\n", n2, n1, fn, st.num_avail);
-#endif
-	}
-
-#ifdef DEBUG_SOLVE
-	{
-		char fn[128];
-		sprintf(fn, "contraction_%02d", solution);
-		gr_draw(st.g, fn, "png");
-	}
-#endif
-
-	result = gr_get(st.g, st.avail[0], st.avail[1]);
-
-#ifdef DEBUG_TAGS
-	{
-		int t, n;
-		printf("Groups:\n");
-		for(t = 0; t < 2; t++) {
-			printf("  [%d] is", t);
-			for(n = 0; n < st.g->n; n++) {
-				if (st.tag[n] == t)
-					printf(" %s", st.g->node2name[n]);
-			}
-			printf("\n");
-		}
-	}
-#endif
-	{
-		int x, y, num_cuts = 0;
-		for(y = 0; y < st.g->n; y++)
-			for(x = y+1; x < st.g->n; x++)
-				if ((gr_get_(g_, x, y) > 0) && (st.tag[x] != st.tag[y])) {
-#ifdef DEBUG_TAGS
-					printf("CUT %s-%s\n", st.g->node2name[x], st.g->node2name[y]);
-#endif
-					cuts[num_cuts*2+0] = x;
-					cuts[num_cuts*2+1] = y;
-					num_cuts++;
-				}
-		cuts[num_cuts*2+0] = -1;
-		cuts[num_cuts*2+1] = -1;
-	}
-	FREE_ALL();
-	return result;
-}
-
-#define strempty(s) ((s) == NULL ? "" : (s))
-int *solve(gr_t *g)
-{
-	int n, best, res, till, cuts_size;
-	double nd;
-	int *cuts, *best_cuts;
-
-	/* count how many nodes we really have - the ones not cut down from the graph by the preprocessor */
-	nd = 0;
-	for(n = 0; n < g->n; n++)
-		if (gr_node_edges(g, n) > 0)
-			nd++;
-
-	till = (int)(nd * (nd-1.0) / 2.0 * log(nd))+1;
-#ifdef DEBUG_SOLVE
-	printf("Running solver at most %d times for %d relevant nodes\n", till, (int)nd);
-#endif
-
-	cuts_size = ((nd * nd) + 1) * sizeof(int);
-	cuts = malloc(cuts_size);
-	best_cuts = malloc(cuts_size);
-
-	best = BAD;
-	for(n = 0; n < till; n++) {
-		res = solve_(g, cuts);
-#ifdef DEBUG_SOLVE
-		printf("solution %d=%d\n", n, res);
-#endif
-		if (res < best) {
-			best = res;
-			memcpy(best_cuts, cuts, cuts_size);
-		}
-		if (best == 1) /* we won't find a better solution ever */
-			break;
-	}
-
-#ifdef DEBUG_SOLVE
-	printf("Best solution cuts %d edge%s:", best, best == 1 ? "" : "s");
-	for(n = 0; best_cuts[n*2] != -1; n++) {
-		printf(" %d:%s-%d:%s", best_cuts[n*2+0], strempty(g->node2name[best_cuts[n*2+0]]), best_cuts[n*2+1], strempty(g->node2name[best_cuts[n*2+1]]));
-	}
-	printf("\n");
-#endif
-	if (best == BAD) {
-		free(best_cuts);
-		free(cuts);
-		return NULL;
-	}
-	free(cuts);
-	return best_cuts;
-}
-
-
Index: trunk/src/pcb-mincut/H.in
===================================================================
--- trunk/src/pcb-mincut/H.in	(revision 1061)
+++ trunk/src/pcb-mincut/H.in	(nonexistent)
@@ -1,8 +0,0 @@
-# a-1-b
-#   |
-# C-2-D
-
-net1 a b
-net2 C D
-neut 1 2
-conn C-2 D-2 a-1 b-1 1-2
Index: trunk/src/pcb-mincut/README
===================================================================
--- trunk/src/pcb-mincut/README	(revision 1061)
+++ trunk/src/pcb-mincut/README	(nonexistent)
@@ -1,21 +0,0 @@
-This mini-project demonstrates a minimal cut implementation tailored
-to solve geda/pcb "how to highlight shorts" problem.
-
-It should compile out of the box on GNU/Linux using make. Running
-a test case:
-
-./main < test_cases/H3.in
-
-If graphviz is installed, input graphs are drawn. Changing the
-#defines in solve.c causes more debug messages printed and/or
-debug graphs drawn.
-
-The code is not portable at all, since it is a proof-of-concept
-prototype.
-
-load.c is for easier testing; if the code ever gets merge in PCB it
-would use something native and load.c would be omitted. genht is a
-dependency of load.c.
-
-
-
Index: trunk/src/pcb-mincut/test_cases/H3.in
===================================================================
--- trunk/src/pcb-mincut/test_cases/H3.in	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/H3.in	(nonexistent)
@@ -1,18 +0,0 @@
-# a-1-2-3-4-5-b
-#       |
-#       6-+
-#       | |
-#       7-+
-#       |/
-# C-8-9-10-11-D
-
-net1 a b
-net2 C D
-neut 1 2 3 4 5 6 7 8 9 10 11
-conn a-1 1-2 2-3 3-4 4-5 5-b
-conn C-8 8-9 9-10 10-11 11-D
-conn 3-6 6-7 7-10
-
-#redundancy - cut 3-6 is the best:
-conn 6-7 7-10
-
Index: trunk/src/pcb-mincut/test_cases/H4.in
===================================================================
--- trunk/src/pcb-mincut/test_cases/H4.in	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/H4.in	(nonexistent)
@@ -1,12 +0,0 @@
-# a   b
-# |   |
-# 1---2
-# |   |
-# C   D
-
-net1 a b
-net2 C D
-neut 1 2
-conn a-1 b-2
-conn C-1 D-2
-conn 1-2
Index: trunk/src/pcb-mincut/test_cases/H2.ref
===================================================================
--- trunk/src/pcb-mincut/test_cases/H2.ref	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/H2.ref	(nonexistent)
@@ -1 +0,0 @@
-7-6
Index: trunk/src/pcb-mincut/test_cases/H3.ref
===================================================================
--- trunk/src/pcb-mincut/test_cases/H3.ref	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/H3.ref	(nonexistent)
@@ -1 +0,0 @@
-6-3
Index: trunk/src/pcb-mincut/test_cases/H4.ref
===================================================================
--- trunk/src/pcb-mincut/test_cases/H4.ref	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/H4.ref	(nonexistent)
@@ -1,2 +0,0 @@
-1-C
-2-D
Index: trunk/src/pcb-mincut/test_cases/C.in
===================================================================
--- trunk/src/pcb-mincut/test_cases/C.in	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/C.in	(nonexistent)
@@ -1,9 +0,0 @@
-# a---b
-# |
-# C---D
-
-net1 a b
-net2 C D
-conn a-b C-D
-conn a-C
-
Index: trunk/src/pcb-mincut/test_cases/redundant.in
===================================================================
--- trunk/src/pcb-mincut/test_cases/redundant.in	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/redundant.in	(nonexistent)
@@ -1,20 +0,0 @@
-# 12----13---14
-# |           |
-# a-1-2-3-4-5-b
-#       |
-#       6-+
-#       | |
-#       7-+
-#       |
-# C-8-9-10-11-D
-
-net1 a b
-net2 C D
-neut 1 2 3 4 5 6 7 8 9 10 11 12 13 14
-conn a-1 1-2 2-3 3-4 4-5 5-b
-conn C-8 8-9 9-10 10-11 11-D
-conn 3-6 6-7 7-10
-conn a-12 12-13 13-14 14-b
-conn 6-7
-
-
Index: trunk/src/pcb-mincut/test_cases/H.in
===================================================================
--- trunk/src/pcb-mincut/test_cases/H.in	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/H.in	(nonexistent)
@@ -1,8 +0,0 @@
-# a-1-b
-#   |
-# C-2-D
-
-net1 a b
-net2 C D
-neut 1 2
-conn C-2 D-2 a-1 b-1 1-2
Index: trunk/src/pcb-mincut/test_cases/C.ref
===================================================================
--- trunk/src/pcb-mincut/test_cases/C.ref	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/C.ref	(nonexistent)
@@ -1 +0,0 @@
-C-a
Index: trunk/src/pcb-mincut/test_cases/rats1.in
===================================================================
--- trunk/src/pcb-mincut/test_cases/rats1.in	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/rats1.in	(nonexistent)
@@ -1,12 +0,0 @@
-# a   b
-# |   |
-# 1   2
-# |   |
-# C   D
-
-net1 a b
-net2 C D
-neut 1 2
-conn a-1 b-2
-conn C-1 D-2
-
Index: trunk/src/pcb-mincut/test_cases/rats2.in
===================================================================
--- trunk/src/pcb-mincut/test_cases/rats2.in	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/rats2.in	(nonexistent)
@@ -1,8 +0,0 @@
-# a---C---b---D
-
-net1 a b
-net2 C D
-conn a-C C-b b-D
-
-
-
Index: trunk/src/pcb-mincut/test_cases/rats3.in
===================================================================
--- trunk/src/pcb-mincut/test_cases/rats3.in	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/rats3.in	(nonexistent)
@@ -1,9 +0,0 @@
-# C---a---b---D
-
-net1 a b
-net2 C D
-conn C-a a-b b-D
-
-
-
-
Index: trunk/src/pcb-mincut/test_cases/H.ref
===================================================================
--- trunk/src/pcb-mincut/test_cases/H.ref	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/H.ref	(nonexistent)
@@ -1 +0,0 @@
-2-1
Index: trunk/src/pcb-mincut/test_cases/O.in
===================================================================
--- trunk/src/pcb-mincut/test_cases/O.in	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/O.in	(nonexistent)
@@ -1,9 +0,0 @@
-# a---b
-# |   |
-# C---D
-
-net1 a b
-net2 C D
-conn a-b C-D
-conn a-C b-D
-
Index: trunk/src/pcb-mincut/test_cases/rats1.ref
===================================================================
--- trunk/src/pcb-mincut/test_cases/rats1.ref	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/rats1.ref	(nonexistent)
@@ -1,2 +0,0 @@
-1-C
-2-D
Index: trunk/src/pcb-mincut/test_cases/rats2.ref
===================================================================
--- trunk/src/pcb-mincut/test_cases/rats2.ref	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/rats2.ref	(nonexistent)
@@ -1,3 +0,0 @@
-C-a
-C-b
-D-b
Index: trunk/src/pcb-mincut/test_cases/rats3.ref
===================================================================
--- trunk/src/pcb-mincut/test_cases/rats3.ref	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/rats3.ref	(nonexistent)
@@ -1,2 +0,0 @@
-C-a
-D-b
Index: trunk/src/pcb-mincut/test_cases/O.ref
===================================================================
--- trunk/src/pcb-mincut/test_cases/O.ref	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/O.ref	(nonexistent)
@@ -1,2 +0,0 @@
-C-a
-D-b
Index: trunk/src/pcb-mincut/test_cases/Makefile
===================================================================
--- trunk/src/pcb-mincut/test_cases/Makefile	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/Makefile	(nonexistent)
@@ -1,12 +0,0 @@
-TESTS = C.diff H.diff H2.diff H3.diff H4.diff O.diff \
-        rats1.diff rats2.diff rats3.diff
-
-all: $(TESTS)
-
-.SUFFIXES: .in .out .diff .ref
-
-.out.diff:
-	@diff -u $*.out $*.ref
-
-.in.out:
-	@../main < $*.in >$*.out
Index: trunk/src/pcb-mincut/test_cases/H2.in
===================================================================
--- trunk/src/pcb-mincut/test_cases/H2.in	(revision 1061)
+++ trunk/src/pcb-mincut/test_cases/H2.in	(nonexistent)
@@ -1,16 +0,0 @@
-# a-1-2-3-4-5-b
-#       |
-#       6
-#       |
-#       7
-#       |
-# C-8-9-10-11-D
-
-net1 a b
-net2 C D
-neut 1 2 3 4 5 6 7 8 9 10 11
-conn a-1 1-2 2-3 3-4 4-5 5-b
-conn C-8 8-9 9-10 10-11 11-D
-conn 3-6 6-7 7-10
-
-
Index: trunk/src/pcb-mincut/Makefile
===================================================================
--- trunk/src/pcb-mincut/Makefile	(revision 1061)
+++ trunk/src/pcb-mincut/Makefile	(nonexistent)
@@ -1,14 +0,0 @@
-CFLAGS = -g -Wall
-LDFLAGS = -lm
-OBJS = main.o solve.o load.o graph.o ../3rd/genht/htsi.o
-
-all: main
-
-main: $(OBJS)
-
-test:
-	cd test_cases && make
-
-
-clean:
-	rm $(OBJS) 2>/dev/null ; true
Index: trunk/src/pcb-mincut/solve.h
===================================================================
--- trunk/src/pcb-mincut/solve.h	(revision 1061)
+++ trunk/src/pcb-mincut/solve.h	(nonexistent)
@@ -1,5 +0,0 @@
-#include "graph.h"
-
-/* returns a list of object ID pairs (each nth and n+1th element) terminated
-   by a -1;-1. Cutting these vertices would separate g. */
-int *solve(gr_t *g);
Index: trunk/src/rats_mincut.c
===================================================================
--- trunk/src/rats_mincut.c	(revision 1061)
+++ trunk/src/rats_mincut.c	(nonexistent)
@@ -1,411 +0,0 @@
-/* $Id$ */
-
-/*
- *                            COPYRIGHT
- *
- *  PCB, interactive printed circuit board design
- *  Copyright (C) 2013..2015 Tibor 'Igor2' Palinkas
- * 
- *  This module, rats.c, was written and is Copyright (C) 1997 by harry eaton
- *  this module is also subject to the GNU GPL as described below
- *
- *  This program is free software; you can redistribute it and/or modify
- *  it under the terms of the GNU General Public License as published by
- *  the Free Software Foundation; either version 2 of the License, or
- *  (at your option) any later version.
- *
- *  This program is distributed in the hope that it will be useful,
- *  but WITHOUT ANY WARRANTY; without even the implied warranty of
- *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *  GNU General Public License for more details.
- *
- *  You should have received a copy of the GNU General Public License
- *  along with this program; if not, write to the Free Software
- *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- *
- */
-
-/* Change History:
- * Started 6/10/97
- * Added support for minimum length rat lines 6/13/97
- * rat lines to nearest line/via 8/29/98
- * support for netlist window 10/24/98
- */
-
-
-#include "config.h"
-
-#include <math.h>
-#include <stdio.h>
-#include <assert.h>
-
-#include "global.h"
-
-#include "create.h"
-#include "data.h"
-#include "draw.h"
-#include "error.h"
-#include "file.h"
-#include "find.h"
-#include "misc.h"
-#include "mymem.h"
-#include "polygon.h"
-#include "rats.h"
-#include "search.h"
-#include "set.h"
-#include "undo.h"
-
-
-#include "rats.h"
-#include "pcb-mincut/graph.h"
-#include "pcb-mincut/solve.h"
-
-#define debprintf(x...)
-
-typedef struct short_conn_s short_conn_t;
-struct short_conn_s {
-	int gid;											/* id in the graph */
-	int from_type;
-/*	AnyObjectType *from;*/
-	int from_id;
-	int to_type;
-	int edges;										/* number of edges */
-	AnyObjectType *to;
-	found_conn_type_t type;
-	short_conn_t *next;
-};
-
-static short_conn_t *short_conns = NULL;
-static int num_short_conns = 0;
-static int short_conns_maxid = 0;
-
-static void proc_short_cb(int current_type, void *current_obj, int from_type, void *from_obj, found_conn_type_t type)
-{
-	AnyObjectType *curr = current_obj, *from = from_obj;
-	short_conn_t *s;
-
-	s = malloc(sizeof(short_conn_t));
-	if (from != NULL) {
-		s->from_type = from_type;
-		s->from_id = from->ID;
-	}
-	else {
-		s->from_type = 0;
-		s->from_id = -1;
-	}
-	s->to_type = current_type;
-	s->to = curr;
-	s->type = type;
-	s->edges = 0;
-	s->next = short_conns;
-	short_conns = s;
-	if (curr->ID > short_conns_maxid)
-		short_conns_maxid = curr->ID;
-	num_short_conns++;
-
-	debprintf(" found %d %d/%p type %d from %d\n", current_type, curr->ID, current_obj, type, from == NULL ? -1 : from->ID);
-}
-
-/* returns 0 on succes */
-static int proc_short(PinType * pin, PadType * pad, int ignore)
-{
-	find_callback_t old_cb;
-	Coord x, y;
-	short_conn_t *n, **lut_by_oid, **lut_by_gid, *next;
-	int gids;
-	gr_t *g;
-	void *S, *T;
-	int *solution;
-	int i, maxedges;
-	int bad_gr = 0;
-
-	if (!TEST_FLAG(ENABLEMINCUTFLAG, PCB))
-		return bad_gr;
-
-	if (!Settings.EnableMincut)
-		return bad_gr;
-
-	/* only one should be set, but one must be set */
-	assert((pin != NULL) || (pad != NULL));
-	assert((pin == NULL) || (pad == NULL));
-
-	if (pin != NULL) {
-		debprintf("short on pin!\n");
-		SET_FLAG(WARNFLAG, pin);
-		x = pin->X;
-		y = pin->Y;
-	}
-	else if (pad != NULL) {
-		debprintf("short on pad!\n");
-		SET_FLAG(WARNFLAG, pad);
-		if (TEST_FLAG(EDGE2FLAG, pad)) {
-			x = pad->Point2.X;
-			y = pad->Point2.Y;
-		}
-		else {
-			x = pad->Point1.X;
-			y = pad->Point1.Y;
-		}
-	}
-
-	/* run only if net is not ignored */
-	if (ignore)
-		return 0;
-
-	short_conns = NULL;
-	num_short_conns = 0;
-	short_conns_maxid = 0;
-
-	/* perform a search using MINCUTFLAG, calling back proc_short_cb() with the connections */
-	old_cb = find_callback;
-	find_callback = proc_short_cb;
-	SaveFindFlag(MINCUTFLAG);
-	LookupConnection(x, y, false, 1, MINCUTFLAG);
-
-	debprintf("- alloced for %d\n", (short_conns_maxid + 1));
-	lut_by_oid = calloc(sizeof(short_conn_t *), (short_conns_maxid + 1));
-	lut_by_gid = calloc(sizeof(short_conn_t *), (num_short_conns + 3));
-
-	g = gr_alloc(num_short_conns + 2);
-
-	g->node2name = calloc(sizeof(char *), (num_short_conns + 2));
-
-	/* conn 0 is S and conn 1 is T and set up lookup arrays */
-	for (n = short_conns, gids = 2; n != NULL; n = n->next, gids++) {
-		char *s, *typ;
-		ElementType *parent;
-		n->gid = gids;
-		debprintf(" {%d} found %d %d/%p type %d from %d\n", n->gid, n->to_type, n->to->ID, n->to, n->type, n->from_id);
-		lut_by_oid[n->to->ID] = n;
-		lut_by_gid[n->gid] = n;
-
-		s = malloc(256);
-		parent = NULL;
-		switch (n->to_type) {
-		case PIN_TYPE:
-			typ = "pin";
-			parent = ((PinType *) (n->to))->Element;
-			break;
-		case VIA_TYPE:
-			typ = "via";
-			parent = ((PinType *) (n->to))->Element;
-			break;
-		case PAD_TYPE:
-			typ = "pad";
-			parent = ((PadType *) (n->to))->Element;
-			break;
-		case LINE_TYPE:
-			typ = "line";
-			break;
-		default:
-			typ = "other";
-			break;
-		}
-		if (parent != NULL) {
-			TextType *name;
-			name = &parent->Name[1];
-			if ((name->TextString == NULL) || (*name->TextString == '\0'))
-				sprintf(s, "%s #%d \\nof #%d", typ, n->to->ID, parent->ID);
-			else
-				sprintf(s, "%s #%d \\nof %s", typ, n->to->ID, name->TextString);
-		}
-		else
-			sprintf(s, "%s #%d", typ, n->to->ID);
-		g->node2name[n->gid] = s;
-	}
-	g->node2name[0] = strdup("S");
-	g->node2name[1] = strdup("T");
-
-	/* calculate how many edges each node has and the max edge count */
-	maxedges = 0;
-	for (n = short_conns; n != NULL; n = n->next) {
-		short_conn_t *from;
-
-		n->edges++;
-		if (n->edges > maxedges)
-			maxedges = n->edges;
-
-		if (n->from_id >= 0) {
-			from = lut_by_oid[n->from_id];
-			if (from == NULL) {
-				/* no from means broken graph (multiple components) */
-				if (n->from_id >= 2) {	/* ID 0 and 1 are start/stop, there won't be from for them */
-					fprintf(stderr, "rats_mincut.c error: graph has multiple components, bug in find.c (n->from_id=%d)!\n", n->from_id);
-					bad_gr = 1;
-				}
-				continue;
-			}
-			from->edges++;
-			if (from->edges > maxedges)
-				maxedges = from->edges;
-		}
-	}
-
-
-	S = NULL;
-	T = NULL;
-	for (n = short_conns; n != NULL; n = n->next) {
-		short_conn_t *from;
-		void *spare;
-
-		spare = NULL;
-		if (n->to_type == PIN_TYPE)
-			spare = ((PinType *) n->to)->Spare;
-		if (n->to_type == PAD_TYPE)
-			spare = ((PadType *) n->to)->Spare;
-		if (spare != NULL) {
-			void *net = &(((LibraryMenuTypePtr) spare)->Name[2]);
-			debprintf(" net=%s\n", net);
-			if (S == NULL) {
-				debprintf(" -> became S\n");
-				S = net;
-			}
-			else if ((T == NULL) && (net != S)) {
-				debprintf(" -> became T\n");
-				T = net;
-			}
-
-			if (net == S)
-				gr_add_(g, n->gid, 0, 100000);
-			else if (net == T)
-				gr_add_(g, n->gid, 1, 100000);
-		}
-		/* if we have a from object, look it up and make a connection between the two gids */
-		if (n->from_id >= 0) {
-			int weight;
-			short_conn_t *from = lut_by_oid[n->from_id];
-
-			from = lut_by_oid[n->from_id];
-			/* weight: 1 for connections we can break, large value for connections we shall not break */
-			if ((n->type == FCT_COPPER) || (n->type == FCT_START)) {
-				/* connection to a pin/pad is slightly stronger than the
-				   strongest obj-obj conn; obj-obj conns are weaker at junctions where many
-				   objects connect */
-				if ((n->from_type == PIN_TYPE) || (n->from_type == PAD_TYPE) || (n->to_type == PIN_TYPE) || (n->to_type == PAD_TYPE))
-					weight = maxedges * 2 + 2;
-				else
-					weight = maxedges * 2 - n->edges - from->edges + 1;
-			}
-			else
-				weight = 10000;
-			if (from != NULL) {
-				gr_add_(g, n->gid, from->gid, weight);
-				debprintf(" CONN %d %d\n", n->gid, from->gid);
-			}
-		}
-	}
-
-/*#define MINCUT_DRAW*/
-#ifdef MINCUT_DRAW
-	{
-		static int drw = 0;
-		char gfn[256];
-		drw++;
-		sprintf(gfn, "A_%d_a", drw);
-		debprintf("gfn=%s\n", gfn);
-		gr_draw(g, gfn, "png");
-	}
-#endif
-
-	if (!bad_gr) {
-		solution = solve(g);
-
-		if (solution != NULL) {
-			debprintf("Would cut:\n");
-			for (i = 0; solution[i] != -1; i++) {
-				short_conn_t *s;
-				debprintf("%d:", i);
-				s = lut_by_gid[solution[i]];
-				debprintf("%d %p", solution[i], s);
-				if (s != NULL) {
-					SET_FLAG(WARNFLAG, s->to);
-					debprintf("  -> %d", s->to->ID);
-				}
-				debprintf("\n");
-			}
-
-			free(solution);
-		}
-		else {
-			fprintf(stderr, "mincut didn't find a solution, falling back to the old warn\n");
-			bad_gr = 1;
-		}
-	}
-	free(lut_by_oid);
-	free(lut_by_gid);
-
-	for (n = short_conns; n != NULL; n = next) {
-		next = n->next;
-		free(n);
-	}
-
-
-	ResetFoundLinesAndPolygons(false);
-	ResetFoundPinsViasAndPads(false);
-	RestoreFindFlag();
-
-	find_callback = old_cb;
-	return bad_gr;
-}
-
-typedef struct pinpad_s pinpad_t;
-struct pinpad_s {
-	int ignore;										/* if 1, changed our mind, do not check */
-	PinType *pin;
-	PadType *pad;
-	const char *with_net;					/* the name of the net this pin/pad is in short with */
-	pinpad_t *next;
-};
-
-static pinpad_t *shorts = NULL;
-
-void rat_found_short(PinType * pin, PadType * pad, const char *with_net)
-{
-	pinpad_t *pp;
-	pp = malloc(sizeof(pinpad_t));
-	pp->ignore = 0;
-	pp->pin = pin;
-	pp->pad = pad;
-	pp->with_net = with_net;
-	pp->next = shorts;
-	shorts = pp;
-}
-
-void rat_proc_shorts(void)
-{
-	pinpad_t *n, *i, *next;
-	int bad_gr = 0;
-	for (n = shorts; n != NULL; n = next) {
-		next = n->next;
-
-		if (n->pin != NULL)
-			SET_FLAG(WARNFLAG, n->pin);
-		if (n->pad != NULL)
-			SET_FLAG(WARNFLAG, n->pad);
-
-
-		/* run only if net is not ignored */
-		if ((!bad_gr) && (proc_short(n->pin, n->pad, n->ignore) != 0)) {
-			fprintf(stderr, "Can't run mincut :(\n");
-			bad_gr = 1;
-		}
-
-		if (!bad_gr) {
-			/* check if the rest of the shorts affect the same nets - ignore them if so */
-			for (i = n->next; i != NULL; i = i->next) {
-				LibraryMenuType *spn, *spi;
-				spn = (n->pin != NULL) ? n->pin->Spare : n->pad->Spare;
-				spi = (i->pin != NULL) ? i->pin->Spare : i->pad->Spare;
-
-				if ((spn == NULL) || (spi == NULL))
-					continue;
-
-				/* can compare by pointer - names are never strdup()'d */
-				if ((&spn->Name[2] == i->with_net) || (&spi->Name[2] == n->with_net))
-					i->ignore = 1;
-			}
-		}
-		free(n);
-	}
-	shorts = NULL;
-}
Index: trunk/src/rats_mincut.h
===================================================================
--- trunk/src/rats_mincut.h	(revision 1061)
+++ trunk/src/rats_mincut.h	(nonexistent)
@@ -1,36 +0,0 @@
-/* $Id$ */
-
-/*
- *                            COPYRIGHT
- *
- *  PCB, interactive printed circuit board design
- *  Copyright (C) 2013..2015 Tibor 'Igor2' Palinkas
- * 
- *  This module, rats.c, was written and is Copyright (C) 1997 by harry eaton
- *  this module is also subject to the GNU GPL as described below
- *
- *  This program is free software; you can redistribute it and/or modify
- *  it under the terms of the GNU General Public License as published by
- *  the Free Software Foundation; either version 2 of the License, or
- *  (at your option) any later version.
- *
- *  This program is distributed in the hope that it will be useful,
- *  but WITHOUT ANY WARRANTY; without even the implied warranty of
- *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *  GNU General Public License for more details.
- *
- *  You should have received a copy of the GNU General Public License
- *  along with this program; if not, write to the Free Software
- *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- *
- */
-
-/* Change History:
- * Started 6/10/97
- * Added support for minimum length rat lines 6/13/97
- * rat lines to nearest line/via 8/29/98
- * support for netlist window 10/24/98
- */
-
-void rat_found_short(PinType * pin, PadType * pad, const char *with_net);
-void rat_proc_shorts(void);
Index: trunk/src/Makefile.dep
===================================================================
--- trunk/src/Makefile.dep	(revision 1061)
+++ trunk/src/Makefile.dep	(revision 1062)
@@ -148,7 +148,7 @@
 rats.o: rats.c ../config.h ../config.manual.h ../config.auto.h global.h \
  const.h ../globalconst.h ../config.h macro.h hid.h polyarea.h \
  libpcb_fp.h create.h data.h draw.h error.h file.h find.h misc.h ds.h \
- mymem.h polygon.h rats.h search.h set.h undo.h rats_mincut.h
+ mymem.h polygon.h rats.h search.h set.h undo.h
 rats_mincut.o: rats_mincut.c ../config.h ../config.manual.h \
  ../config.auto.h global.h const.h ../globalconst.h ../config.h macro.h \
  hid.h polyarea.h libpcb_fp.h create.h data.h draw.h error.h file.h \
Index: trunk/src/Makefile.in
===================================================================
--- trunk/src/Makefile.in	(revision 1061)
+++ trunk/src/Makefile.in	(revision 1062)
@@ -48,7 +48,6 @@
 	polygon1.o
 	print.o
 	rats.o
-	rats_mincut.o
 	rats_patch.o
 	remove.o
 	report.o
@@ -60,6 +59,7 @@
 	set.o
 	strflags.o
 	stub_edif.o
+	stub_mincut.o
 	stub_vendor.o
 	thermal.o
 	undo.o
@@ -71,8 +71,6 @@
 	hid/common/extents.o
 	hid/common/draw_helpers.o
 	hid/common/hid_resource.o
-	pcb-mincut/graph.o
-	pcb-mincut/solve.o
 	res_parse.o
 	res_lex.o
 	portability.o
@@ -128,7 +126,9 @@
 include {../src_plugins/puller/Makefile.mod}
 include {../src_plugins/edif/Makefile.mod}
 include {../src_plugins/djopt/Makefile.mod}
+include {../src_plugins/mincut/Makefile.mod}
 
+
 if /target/libs/script/gpmi/presents then
 include {Makefile.in.mod/gpmi_plugin}
 end
Index: trunk/src/rats.c
===================================================================
--- trunk/src/rats.c	(revision 1061)
+++ trunk/src/rats.c	(revision 1062)
@@ -55,7 +55,7 @@
 #include "search.h"
 #include "set.h"
 #include "undo.h"
-#include "rats_mincut.h"
+#include "stub_mincut.h"
 
 
 RCSID("$Id$");
@@ -343,7 +343,7 @@
 			if (!pin->Spare) {
 				Message(_("Warning! Net \"%s\" is shorted to %s pin %s\n"),
 								&theNet->Name[2], UNKNOWN(NAMEONPCB_NAME(element)), UNKNOWN(pin->Number));
-				rat_found_short(pin, NULL, &theNet->Name[2]);
+				stub_rat_found_short(pin, NULL, &theNet->Name[2]);
 				continue;
 			}
 			newone = true;
@@ -360,7 +360,7 @@
 				*menu = pin->Spare;
 				Message(_("Warning! Net \"%s\" is shorted to net \"%s\"\n"),
 								&theNet->Name[2], &((LibraryMenuTypePtr) (pin->Spare))->Name[2]);
-				rat_found_short(pin, NULL, &theNet->Name[2]);
+				stub_rat_found_short(pin, NULL, &theNet->Name[2]);
 			}
 		}
 	}
@@ -374,7 +374,7 @@
 			if (!pad->Spare) {
 				Message(_("Warning! Net \"%s\" is shorted  to %s pad %s\n"),
 								&theNet->Name[2], UNKNOWN(NAMEONPCB_NAME(element)), UNKNOWN(pad->Number));
-				rat_found_short(NULL, pad, &theNet->Name[2]);
+				stub_rat_found_short(NULL, pad, &theNet->Name[2]);
 				continue;
 			}
 			newone = true;
@@ -391,7 +391,7 @@
 				*menu = pad->Spare;
 				Message(_("Warning! Net \"%s\" is shorted to net \"%s\"\n"),
 								&theNet->Name[2], &((LibraryMenuTypePtr) (pad->Spare))->Name[2]);
-				rat_found_short(NULL, pad, &theNet->Name[2]);
+				stub_rat_found_short(NULL, pad, &theNet->Name[2]);
 			}
 		}
 	}
@@ -719,7 +719,7 @@
 		return (true);
 
 	if (Warned || changed) {
-		rat_proc_shorts();
+		stub_rat_proc_shorts();
 		Draw();
 	}
 
Index: trunk/src/stub_mincut.c
===================================================================
--- trunk/src/stub_mincut.c	(nonexistent)
+++ trunk/src/stub_mincut.c	(revision 1062)
@@ -0,0 +1,49 @@
+/*
+ *                            COPYRIGHT
+ *
+ *  PCB, interactive printed circuit board design
+ *  Copyright (C) 2016 Tibor 'Igor2' Palinkas
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+#include "config.h"
+#include "global.h"
+#include "error.h"
+#include "data.h"
+#include "stub_mincut.h"
+
+static void stub_rat_proc_shorts_dummy(void)
+{
+
+	if (TEST_FLAG(ENABLEMINCUTFLAG, PCB))
+		Message(_("Can not run mincut: the mincut plugin/buildin is not present.\n"));
+	return 0;
+}
+
+static void stub_rat_found_short_dummy(PinType * pin, PadType * pad, const char *with_net)
+{
+	/* original behavior: just warn at random pins/pads */
+	if (pin != NULL)
+		SET_FLAG(WARNFLAG, pin);
+	if (pad != NULL)
+		SET_FLAG(WARNFLAG, pad);
+
+	stub_rat_proc_shorts_dummy();
+}
+
+void (*stub_rat_found_short)(PinType * pin, PadType * pad, const char *with_net) = stub_rat_found_short_dummy;
+void (*stub_rat_proc_shorts)(void) = stub_rat_proc_shorts_dummy;
Index: trunk/src/stub_mincut.h
===================================================================
--- trunk/src/stub_mincut.h	(nonexistent)
+++ trunk/src/stub_mincut.h	(revision 1062)
@@ -0,0 +1,25 @@
+/*
+ *                            COPYRIGHT
+ *
+ *  PCB, interactive printed circuit board design
+ *  Copyright (C) 2016 Tibor 'Igor2' Palinkas
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+void (*stub_rat_found_short)(PinType * pin, PadType * pad, const char *with_net);
+void (*stub_rat_proc_shorts)(void);
+
Index: trunk/src_plugins/mincut/Makefile
===================================================================
--- trunk/src_plugins/mincut/Makefile	(nonexistent)
+++ trunk/src_plugins/mincut/Makefile	(revision 1062)
@@ -0,0 +1,4 @@
+all:
+	cd ../../src && make mod_mincut
+
+
Index: trunk/src_plugins/mincut/Makefile.mod
===================================================================
--- trunk/src_plugins/mincut/Makefile.mod	(nonexistent)
+++ trunk/src_plugins/mincut/Makefile.mod	(revision 1062)
@@ -0,0 +1,27 @@
+append /local/pcb/mincut/enable {}
+append /local/pcb/mincut/buildin {}
+
+append /local/pcb/mincut/OBJS [@ ${PLUGDIR}/mincut/rats_mincut.o ${PLUGDIR}/mincut/pcb-mincut/graph.o ${PLUGDIR}/mincut/pcb-mincut/solve.o @]
+
+if /local/pcb/mincut/enable then
+	if /local/pcb/mincut/buildin then
+		append /local/pcb/buildin_init    { extern void hid_mincut_init(); hid_mincut_init(); plugin_register("mincut", "<mincut>", NULL, 0); }
+		append /local/pcb/OBJS            /local/pcb/mincut/OBJS
+		append /local/pcb/RULES [@
+
+mod_mincut: all
+
+@]
+
+	else
+		append /local/pcb/all   [@ ${PLUGDIR}/mincut/mincut.so @]
+		append /local/pcb/RULES [@
+
+${PLUGDIR}/mincut/mincut.so: @/local/pcb/mincut/OBJS@
+	$(CC) $(LDFLAGS) -shared @cc/rdynamic@ -o ${PLUGDIR}/mincut/mincut.so @/local/pcb/mincut/OBJS@
+
+mod_mincut: ${PLUGDIR}/mincut/mincut.so
+
+@]
+	end
+end
Index: trunk/src_plugins/mincut/pcb-mincut/COPYING
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/COPYING	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/COPYING	(revision 1062)
@@ -0,0 +1,339 @@
+                    GNU GENERAL PUBLIC LICENSE
+                       Version 2, June 1991
+
+ Copyright (C) 1989, 1991 Free Software Foundation, Inc.,
+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ Everyone is permitted to copy and distribute verbatim copies
+ of this license document, but changing it is not allowed.
+
+                            Preamble
+
+  The licenses for most software are designed to take away your
+freedom to share and change it.  By contrast, the GNU General Public
+License is intended to guarantee your freedom to share and change free
+software--to make sure the software is free for all its users.  This
+General Public License applies to most of the Free Software
+Foundation's software and to any other program whose authors commit to
+using it.  (Some other Free Software Foundation software is covered by
+the GNU Lesser General Public License instead.)  You can apply it to
+your programs, too.
+
+  When we speak of free software, we are referring to freedom, not
+price.  Our General Public Licenses are designed to make sure that you
+have the freedom to distribute copies of free software (and charge for
+this service if you wish), that you receive source code or can get it
+if you want it, that you can change the software or use pieces of it
+in new free programs; and that you know you can do these things.
+
+  To protect your rights, we need to make restrictions that forbid
+anyone to deny you these rights or to ask you to surrender the rights.
+These restrictions translate to certain responsibilities for you if you
+distribute copies of the software, or if you modify it.
+
+  For example, if you distribute copies of such a program, whether
+gratis or for a fee, you must give the recipients all the rights that
+you have.  You must make sure that they, too, receive or can get the
+source code.  And you must show them these terms so they know their
+rights.
+
+  We protect your rights with two steps: (1) copyright the software, and
+(2) offer you this license which gives you legal permission to copy,
+distribute and/or modify the software.
+
+  Also, for each author's protection and ours, we want to make certain
+that everyone understands that there is no warranty for this free
+software.  If the software is modified by someone else and passed on, we
+want its recipients to know that what they have is not the original, so
+that any problems introduced by others will not reflect on the original
+authors' reputations.
+
+  Finally, any free program is threatened constantly by software
+patents.  We wish to avoid the danger that redistributors of a free
+program will individually obtain patent licenses, in effect making the
+program proprietary.  To prevent this, we have made it clear that any
+patent must be licensed for everyone's free use or not licensed at all.
+
+  The precise terms and conditions for copying, distribution and
+modification follow.
+
+                    GNU GENERAL PUBLIC LICENSE
+   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+
+  0. This License applies to any program or other work which contains
+a notice placed by the copyright holder saying it may be distributed
+under the terms of this General Public License.  The "Program", below,
+refers to any such program or work, and a "work based on the Program"
+means either the Program or any derivative work under copyright law:
+that is to say, a work containing the Program or a portion of it,
+either verbatim or with modifications and/or translated into another
+language.  (Hereinafter, translation is included without limitation in
+the term "modification".)  Each licensee is addressed as "you".
+
+Activities other than copying, distribution and modification are not
+covered by this License; they are outside its scope.  The act of
+running the Program is not restricted, and the output from the Program
+is covered only if its contents constitute a work based on the
+Program (independent of having been made by running the Program).
+Whether that is true depends on what the Program does.
+
+  1. You may copy and distribute verbatim copies of the Program's
+source code as you receive it, in any medium, provided that you
+conspicuously and appropriately publish on each copy an appropriate
+copyright notice and disclaimer of warranty; keep intact all the
+notices that refer to this License and to the absence of any warranty;
+and give any other recipients of the Program a copy of this License
+along with the Program.
+
+You may charge a fee for the physical act of transferring a copy, and
+you may at your option offer warranty protection in exchange for a fee.
+
+  2. You may modify your copy or copies of the Program or any portion
+of it, thus forming a work based on the Program, and copy and
+distribute such modifications or work under the terms of Section 1
+above, provided that you also meet all of these conditions:
+
+    a) You must cause the modified files to carry prominent notices
+    stating that you changed the files and the date of any change.
+
+    b) You must cause any work that you distribute or publish, that in
+    whole or in part contains or is derived from the Program or any
+    part thereof, to be licensed as a whole at no charge to all third
+    parties under the terms of this License.
+
+    c) If the modified program normally reads commands interactively
+    when run, you must cause it, when started running for such
+    interactive use in the most ordinary way, to print or display an
+    announcement including an appropriate copyright notice and a
+    notice that there is no warranty (or else, saying that you provide
+    a warranty) and that users may redistribute the program under
+    these conditions, and telling the user how to view a copy of this
+    License.  (Exception: if the Program itself is interactive but
+    does not normally print such an announcement, your work based on
+    the Program is not required to print an announcement.)
+
+These requirements apply to the modified work as a whole.  If
+identifiable sections of that work are not derived from the Program,
+and can be reasonably considered independent and separate works in
+themselves, then this License, and its terms, do not apply to those
+sections when you distribute them as separate works.  But when you
+distribute the same sections as part of a whole which is a work based
+on the Program, the distribution of the whole must be on the terms of
+this License, whose permissions for other licensees extend to the
+entire whole, and thus to each and every part regardless of who wrote it.
+
+Thus, it is not the intent of this section to claim rights or contest
+your rights to work written entirely by you; rather, the intent is to
+exercise the right to control the distribution of derivative or
+collective works based on the Program.
+
+In addition, mere aggregation of another work not based on the Program
+with the Program (or with a work based on the Program) on a volume of
+a storage or distribution medium does not bring the other work under
+the scope of this License.
+
+  3. You may copy and distribute the Program (or a work based on it,
+under Section 2) in object code or executable form under the terms of
+Sections 1 and 2 above provided that you also do one of the following:
+
+    a) Accompany it with the complete corresponding machine-readable
+    source code, which must be distributed under the terms of Sections
+    1 and 2 above on a medium customarily used for software interchange; or,
+
+    b) Accompany it with a written offer, valid for at least three
+    years, to give any third party, for a charge no more than your
+    cost of physically performing source distribution, a complete
+    machine-readable copy of the corresponding source code, to be
+    distributed under the terms of Sections 1 and 2 above on a medium
+    customarily used for software interchange; or,
+
+    c) Accompany it with the information you received as to the offer
+    to distribute corresponding source code.  (This alternative is
+    allowed only for noncommercial distribution and only if you
+    received the program in object code or executable form with such
+    an offer, in accord with Subsection b above.)
+
+The source code for a work means the preferred form of the work for
+making modifications to it.  For an executable work, complete source
+code means all the source code for all modules it contains, plus any
+associated interface definition files, plus the scripts used to
+control compilation and installation of the executable.  However, as a
+special exception, the source code distributed need not include
+anything that is normally distributed (in either source or binary
+form) with the major components (compiler, kernel, and so on) of the
+operating system on which the executable runs, unless that component
+itself accompanies the executable.
+
+If distribution of executable or object code is made by offering
+access to copy from a designated place, then offering equivalent
+access to copy the source code from the same place counts as
+distribution of the source code, even though third parties are not
+compelled to copy the source along with the object code.
+
+  4. You may not copy, modify, sublicense, or distribute the Program
+except as expressly provided under this License.  Any attempt
+otherwise to copy, modify, sublicense or distribute the Program is
+void, and will automatically terminate your rights under this License.
+However, parties who have received copies, or rights, from you under
+this License will not have their licenses terminated so long as such
+parties remain in full compliance.
+
+  5. You are not required to accept this License, since you have not
+signed it.  However, nothing else grants you permission to modify or
+distribute the Program or its derivative works.  These actions are
+prohibited by law if you do not accept this License.  Therefore, by
+modifying or distributing the Program (or any work based on the
+Program), you indicate your acceptance of this License to do so, and
+all its terms and conditions for copying, distributing or modifying
+the Program or works based on it.
+
+  6. Each time you redistribute the Program (or any work based on the
+Program), the recipient automatically receives a license from the
+original licensor to copy, distribute or modify the Program subject to
+these terms and conditions.  You may not impose any further
+restrictions on the recipients' exercise of the rights granted herein.
+You are not responsible for enforcing compliance by third parties to
+this License.
+
+  7. If, as a consequence of a court judgment or allegation of patent
+infringement or for any other reason (not limited to patent issues),
+conditions are imposed on you (whether by court order, agreement or
+otherwise) that contradict the conditions of this License, they do not
+excuse you from the conditions of this License.  If you cannot
+distribute so as to satisfy simultaneously your obligations under this
+License and any other pertinent obligations, then as a consequence you
+may not distribute the Program at all.  For example, if a patent
+license would not permit royalty-free redistribution of the Program by
+all those who receive copies directly or indirectly through you, then
+the only way you could satisfy both it and this License would be to
+refrain entirely from distribution of the Program.
+
+If any portion of this section is held invalid or unenforceable under
+any particular circumstance, the balance of the section is intended to
+apply and the section as a whole is intended to apply in other
+circumstances.
+
+It is not the purpose of this section to induce you to infringe any
+patents or other property right claims or to contest validity of any
+such claims; this section has the sole purpose of protecting the
+integrity of the free software distribution system, which is
+implemented by public license practices.  Many people have made
+generous contributions to the wide range of software distributed
+through that system in reliance on consistent application of that
+system; it is up to the author/donor to decide if he or she is willing
+to distribute software through any other system and a licensee cannot
+impose that choice.
+
+This section is intended to make thoroughly clear what is believed to
+be a consequence of the rest of this License.
+
+  8. If the distribution and/or use of the Program is restricted in
+certain countries either by patents or by copyrighted interfaces, the
+original copyright holder who places the Program under this License
+may add an explicit geographical distribution limitation excluding
+those countries, so that distribution is permitted only in or among
+countries not thus excluded.  In such case, this License incorporates
+the limitation as if written in the body of this License.
+
+  9. The Free Software Foundation may publish revised and/or new versions
+of the General Public License from time to time.  Such new versions will
+be similar in spirit to the present version, but may differ in detail to
+address new problems or concerns.
+
+Each version is given a distinguishing version number.  If the Program
+specifies a version number of this License which applies to it and "any
+later version", you have the option of following the terms and conditions
+either of that version or of any later version published by the Free
+Software Foundation.  If the Program does not specify a version number of
+this License, you may choose any version ever published by the Free Software
+Foundation.
+
+  10. If you wish to incorporate parts of the Program into other free
+programs whose distribution conditions are different, write to the author
+to ask for permission.  For software which is copyrighted by the Free
+Software Foundation, write to the Free Software Foundation; we sometimes
+make exceptions for this.  Our decision will be guided by the two goals
+of preserving the free status of all derivatives of our free software and
+of promoting the sharing and reuse of software generally.
+
+                            NO WARRANTY
+
+  11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
+FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.  EXCEPT WHEN
+OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
+PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
+OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS
+TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE
+PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
+REPAIR OR CORRECTION.
+
+  12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
+WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
+REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
+INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
+OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
+TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
+YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
+PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGES.
+
+                     END OF TERMS AND CONDITIONS
+
+            How to Apply These Terms to Your New Programs
+
+  If you develop a new program, and you want it to be of the greatest
+possible use to the public, the best way to achieve this is to make it
+free software which everyone can redistribute and change under these terms.
+
+  To do so, attach the following notices to the program.  It is safest
+to attach them to the start of each source file to most effectively
+convey the exclusion of warranty; and each file should have at least
+the "copyright" line and a pointer to where the full notice is found.
+
+    <one line to give the program's name and a brief idea of what it does.>
+    Copyright (C) <year>  <name of author>
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+
+Also add information on how to contact you by electronic and paper mail.
+
+If the program is interactive, make it output a short notice like this
+when it starts in an interactive mode:
+
+    Gnomovision version 69, Copyright (C) year name of author
+    Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
+    This is free software, and you are welcome to redistribute it
+    under certain conditions; type `show c' for details.
+
+The hypothetical commands `show w' and `show c' should show the appropriate
+parts of the General Public License.  Of course, the commands you use may
+be called something other than `show w' and `show c'; they could even be
+mouse-clicks or menu items--whatever suits your program.
+
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the program, if
+necessary.  Here is a sample; alter the names:
+
+  Yoyodyne, Inc., hereby disclaims all copyright interest in the program
+  `Gnomovision' (which makes passes at compilers) written by James Hacker.
+
+  <signature of Ty Coon>, 1 April 1989
+  Ty Coon, President of Vice
+
+This General Public License does not permit incorporating your program into
+proprietary programs.  If your program is a subroutine library, you may
+consider it more useful to permit linking proprietary applications with the
+library.  If this is what you want to do, use the GNU Lesser General
+Public License instead of this License.
Index: trunk/src_plugins/mincut/pcb-mincut/H.in
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/H.in	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/H.in	(revision 1062)
@@ -0,0 +1,8 @@
+# a-1-b
+#   |
+# C-2-D
+
+net1 a b
+net2 C D
+neut 1 2
+conn C-2 D-2 a-1 b-1 1-2
Index: trunk/src_plugins/mincut/pcb-mincut/Makefile
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/Makefile	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/Makefile	(revision 1062)
@@ -0,0 +1,14 @@
+CFLAGS = -g -Wall
+LDFLAGS = -lm
+OBJS = main.o solve.o load.o graph.o ../3rd/genht/htsi.o
+
+all: main
+
+main: $(OBJS)
+
+test:
+	cd test_cases && make
+
+
+clean:
+	rm $(OBJS) 2>/dev/null ; true
Index: trunk/src_plugins/mincut/pcb-mincut/README
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/README	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/README	(revision 1062)
@@ -0,0 +1,21 @@
+This mini-project demonstrates a minimal cut implementation tailored
+to solve geda/pcb "how to highlight shorts" problem.
+
+It should compile out of the box on GNU/Linux using make. Running
+a test case:
+
+./main < test_cases/H3.in
+
+If graphviz is installed, input graphs are drawn. Changing the
+#defines in solve.c causes more debug messages printed and/or
+debug graphs drawn.
+
+The code is not portable at all, since it is a proof-of-concept
+prototype.
+
+load.c is for easier testing; if the code ever gets merge in PCB it
+would use something native and load.c would be omitted. genht is a
+dependency of load.c.
+
+
+
Index: trunk/src_plugins/mincut/pcb-mincut/graph.c
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/graph.c	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/graph.c	(revision 1062)
@@ -0,0 +1,136 @@
+/*    pcb-mincut, a prototype project demonstrating how to highlight shorts
+ *    Copyright (C) 2012 Tibor 'Igor2' Palinkas
+ *
+ *   This program is free software; you can redistribute it and/or modify
+ *   it under the terms of the GNU General Public License as published by
+ *   the Free Software Foundation; either version 2 of the License, or
+ *   (at your option) any later version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License along
+ *   with this program; if not, write to the Free Software Foundation, Inc.,
+ *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+
+#include <stdlib.h>
+#include <string.h>
+#include "graph.h"
+
+/* allocate a new graph of n nodes with no edges */
+gr_t *gr_alloc(int n)
+{
+	gr_t *g = malloc(sizeof(gr_t));
+	g->n = n;
+	g->adj = calloc(n * n, sizeof(int));
+	return g;
+}
+
+/* create a new graph by cloning graph g */
+gr_t *gr_clone(gr_t *g)
+{
+	int size = g->n * g->n * sizeof(int);
+	gr_t *o = malloc(sizeof(gr_t));
+
+	o->n = g->n;
+	o->adj = malloc(size);
+	memcpy(o->adj, g->adj, size);
+	o->node2name = g->node2name;
+	return o;
+}
+
+/* free all resouces used by the graph */
+void gr_free(gr_t *g)
+{
+	free(g->adj);
+	free(g);
+}
+
+void gr_merge_nodes(gr_t *g, int n1, int n2)
+{
+	int n;
+	gr_bound_chk(g, n1, n2);
+
+	for(n = 0; n < g->n; n++) {
+		if (n != n2)
+			gr_add_(g, n, n1, gr_set_(g, n, n2, 0));
+		else
+			gr_add_(g, n1, n1, gr_set_(g, n2, n2, 0)/2);
+	}
+}
+
+void gr_print(gr_t *g, FILE *f, const char *prefix)
+{
+	int x, y;
+
+	fprintf(f, "%s      ", prefix);
+	for(x = 0; x < g->n; x++)
+		fprintf(f, "% 4d ", x);
+	fprintf(f, "\n");
+
+	for(y = 0; y < g->n; y++) {
+		fprintf(f, "%s % 4d ", prefix, y);
+		for(x = 0; x < g->n; x++)
+			fprintf(f, "% 4d ", gr_get_(g, x, y));
+		fprintf(f, "\n");
+	}
+	fprintf(f, "%s\n", prefix);
+	if (g->node2name != NULL) {
+	fprintf(f, "%snames:\n", prefix);
+		for(x = 0; x < g->n; x++)
+			fprintf(f, "%s % 4d=%s\n", prefix, x, g->node2name[x]);
+	}
+}
+
+int gr_draw(gr_t *g, const char *name, const char *type)
+{
+	char *cmd;
+	FILE *f;
+	int x, y;
+
+	if (type == NULL)
+		type = "png";
+
+	cmd = malloc(strlen(type)*2 + strlen(name) + 64);
+	sprintf(cmd, "dot -T%s -o %s.%s", type, name, type);
+	f = popen(cmd, "w");
+	if (f == NULL)
+		return -1;
+
+	fprintf(f, "graph %s {\n", name);
+
+	if (g->node2name != NULL)
+		for(x = 0; x < g->n; x++)
+			fprintf(f, "\t% 4d[label=\"%d\\n%s\"]\n", x, x, g->node2name[x] == NULL ? "NULL" : g->node2name[x]);
+
+	for(y = 0; y < g->n; y++) {
+		for(x = y; x < g->n; x++) {
+
+#ifdef MULTI_EDGE
+			int n;
+			for(n = gr_get_(g, x, y); n > 0; n--)
+				fprintf(f, "\t% 4d -- % 4d\n", x, y);
+#else
+			if (gr_get_(g, x, y) > 0)
+				fprintf(f, "\t% 4d -- % 4d [label=\"*%d\"]\n", x, y, gr_get_(g, x, y));
+#endif
+		}
+	}
+
+	fprintf(f, "}\n");
+	pclose(f);
+	return 0;
+}
+
+int gr_node_edges(gr_t *g, int node)
+{
+	int n, sum;
+	sum = 0;
+	gr_bound_chk(g, 0, node);
+	for(n = 0; n < g->n; n++)
+		sum += gr_get_(g, n, node);
+	return sum;
+}
Index: trunk/src_plugins/mincut/pcb-mincut/graph.h
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/graph.h	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/graph.h	(revision 1062)
@@ -0,0 +1,97 @@
+/*    pcb-mincut, a prototype project demonstrating how to highlight shorts
+ *    Copyright (C) 2012 Tibor 'Igor2' Palinkas
+ *
+ *   This program is free software; you can redistribute it and/or modify
+ *   it under the terms of the GNU General Public License as published by
+ *   the Free Software Foundation; either version 2 of the License, or
+ *   (at your option) any later version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License along
+ *   with this program; if not, write to the Free Software Foundation, Inc.,
+ *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+
+#ifndef GRAPH_H
+#define GRAPH_H
+#include <stdio.h>
+#include <assert.h>
+
+typedef struct gr_s {
+	int n;     /* number of nodes */
+	int *adj;  /* adjacency matrix of n*n ints */
+	char **node2name; /* optional node names */
+} gr_t;
+
+/* allocate a new graph of n nodes with no edges */
+gr_t *gr_alloc(int n);
+
+/* create a new graph by cloning graph g */
+gr_t *gr_clone(gr_t *g);
+
+/* free all resouces used by the graph */
+void gr_free(gr_t *g);
+
+
+static inline void gr_bound_chk(gr_t *g, int n1, int n2)
+{
+	assert((n1 >= 0) && (n1 < g->n));
+	assert((n2 >= 0) && (n2 < g->n));
+}
+
+/* return number of edges between nodes n1 and n2 - without checks */
+static inline int gr_get_(gr_t *g, int n1, int n2)
+{
+	return g->adj[n1 * g->n + n2];
+}
+
+/* return number of edges between nodes n1 and n2 - with checks */
+static inline int gr_get(gr_t *g, int n1, int n2)
+{
+	gr_bound_chk(g, n1, n2);
+	return gr_get_(g, n1, n2);
+}
+
+/* return old number of edges between nodes n1 and n2 and change it to newnum - no check*/
+static inline int gr_set_(gr_t *g, int n1, int n2, int newnum)
+{
+	int old;
+	old = g->adj[n1 * g->n + n2];
+	g->adj[n1 * g->n + n2] = newnum;
+	g->adj[n2 * g->n + n1] = newnum;
+	return old;
+}
+
+/* return old number of edges between nodes n1 and n2 and increase it by newnum - no check*/
+static inline int gr_add_(gr_t *g, int n1, int n2, int newnum)
+{
+	int old;
+	old = g->adj[n1 * g->n + n2];
+	g->adj[n1 * g->n + n2] += newnum;
+	g->adj[n2 * g->n + n1] += newnum;
+	return old;
+}
+
+/* return old number of edges between nodes n1 and n2 and change it to newnum - check*/
+static inline int gr_set(gr_t *g, int n1, int n2, int newnum)
+{
+	gr_bound_chk(g, n1, n2);
+	return gr_set_(g, n1, n2, newnum);
+}
+
+/* merge two nodes n1 and n2 (contraction) */
+void gr_merge_nodes(gr_t *g, int n1, int n2);
+
+/* print the connection matrix */
+void gr_print(gr_t *g, FILE *f, const char *prefix);
+
+/* draw graph using graphviz/dot */
+int gr_draw(gr_t *g, const char *name, const char *type);
+
+/* return total number of edges of a node */
+int gr_node_edges(gr_t *g, int node);
+#endif
Index: trunk/src_plugins/mincut/pcb-mincut/load.c
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/load.c	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/load.c	(revision 1062)
@@ -0,0 +1,271 @@
+/*    pcb-mincut, a prototype project demonstrating how to highlight shorts
+ *    Copyright (C) 2012 Tibor 'Igor2' Palinkas
+ *
+ *   This program is free software; you can redistribute it and/or modify
+ *   it under the terms of the GNU General Public License as published by
+ *   the Free Software Foundation; either version 2 of the License, or
+ *   (at your option) any later version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License along
+ *   with this program; if not, write to the Free Software Foundation, Inc.,
+ *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+#include "genht/htsi.h"
+#include "graph.h"
+
+/*#define DEBUG_GR*/
+
+/* maximum number of nodes */
+#define MAXNODES 1024
+
+/* maximum length of a name */
+#define NAMELEN 128
+
+/* how many edges net nodes are connected with - this would balance
+   mincut to avoid cutting such connections */
+#define NET_EDGES 8
+
+#define isspc(c) (((c) == ' ') || ((c) == '\t'))
+#define isid(c) ((((c) >= 'a') && ((c) <= 'z')) || (((c) >= 'A') && ((c) <= 'Z')) || (((c) >= '0') && ((c) <= '9')) || ((c) == '_'))
+
+htsi_t *name2node = NULL;              /* hash for looking up known node name -> node id pairs */
+char *node2name[MAXNODES] = {NULL};
+int num_nodes;
+
+static unsigned int keyhash(char *key) {
+	unsigned char *p = (unsigned char *)key;
+	unsigned int hash = 0;
+
+	while (*p)
+		hash += (hash << 2) + *p++;
+	return hash;
+}
+
+static int keyeq(char *a, char *b) {
+	char *pa = (char *)a;
+	char *pb = (char *)b;
+
+	for (; *pa == *pb; pa++, pb++)
+		if (*pa == '\0')
+			return 1;
+	return 0;
+}
+
+
+gr_t *load(FILE *f)
+{
+	int lineno;
+	int nets[2][MAXNODES];  /* nodes in nets */
+	int neut[MAXNODES];     /* neutral nodes */
+	int nn_net[2];          /* number of nodes in nets */
+	int nn_neut;            /* number of nodes in nets */
+	int nodes_fin;          /* 1 after reading the first conn line */
+	gr_t *g = NULL;
+
+/* peek at next char and return if it is a newline */
+#define return_at_eol \
+	do { \
+		char c; \
+		c = fgetc(f); \
+		if ((c == '\r') || (c == '\n')) \
+			return; \
+		ungetc(c, f); \
+	} while(0)
+
+
+	/* eat up space and tabs */
+	void eat_space(void)
+	{
+		int c;
+		do {
+			c = fgetc(f);
+		} while(isspc(c));
+		ungetc(c, f);
+	}
+
+	/* load next token of type id */
+	const char *token_id(void)
+	{
+		static char id[NAMELEN];
+		char *s;
+		int n;
+
+		n = sizeof(id) - 1;
+		s = id-1;
+		do {
+			s++;
+			*s = fgetc(f);
+			n--;
+			if (n <= 0) {
+				*s = '\0';
+				fprintf(stderr, "Error: name too long: %s...\n", id);
+			}
+		} while(isid(*s));
+		ungetc(*s, f);
+		*s = '\0';
+		return id;
+	}
+
+	/* read next id token and look it up as a node name; if it does not
+	   exist and alloc is 1, allocate it; if it does not exist and
+	   alloc is 0, abort with error */
+	int token_node(int alloc)
+	{
+		const char *id = token_id();
+		if (htsi_has(name2node, (char *)id))
+			return htsi_get(name2node, (char *)id);
+		if (alloc) {
+			node2name[num_nodes] = strdup(id);
+			htsi_set(name2node, node2name[num_nodes], num_nodes);
+			return num_nodes++;
+		}
+		fprintf(stderr, "Error: unknown node %s\n", id);
+		abort();
+	}
+
+	/* load a net1 or net2 statement */
+	void load_net(int net)
+	{
+		int node;
+		if (nodes_fin) {
+			fprintf(stderr, "Error: net%d after conn\n", net);
+			abort();
+		}
+		/* load each node and append */
+		while(1) {
+			eat_space();
+			return_at_eol;
+			node = token_node(1);
+			nets[net][nn_net[net]] = node;
+			nn_net[net]++;
+		}
+	}
+
+	/* load a neut statement */
+	void load_neut(void)
+	{
+		int node;
+		if (nodes_fin) {
+			fprintf(stderr, "Error: neut after conn\n");
+			abort();
+		}
+		/* load each node and append */
+		while(1) {
+			eat_space();
+			return_at_eol;
+			node = token_node(1);
+			neut[nn_neut] = node;
+			nn_neut++;
+		}
+	}
+
+	/* load a list of connections */
+	void load_conn(void)
+	{
+		int n1, n2;
+		char c;
+
+		/* if this is the first conn, create the graph */
+		if (!nodes_fin) {
+			g = gr_alloc(num_nodes);
+			g->node2name = node2name;
+		}
+		nodes_fin = 1;
+
+		/* load each n1-n2 pair */
+		while(1) {
+			eat_space();
+			return_at_eol;
+			n1 = token_node(0);
+			c = fgetc(f);
+			if (c != '-') {
+				fprintf(stderr, "Error: expected '-' between nodes in conn list (got '%c' instead)\n", c);
+				abort();
+			}
+			n2 = token_node(0);
+			gr_add_(g, n1, n2, 1);
+		}
+	}
+
+	name2node = htsi_alloc(keyhash, keyeq);
+	node2name[0] = strdup("(S)"); htsi_set(name2node, node2name[0], 0);
+	node2name[1] = strdup("(T)"); htsi_set(name2node, node2name[1], 1);
+	num_nodes = 2;
+	nn_net[0] = 0;
+	nn_net[1] = 0;
+	nn_neut = 0;
+
+	nodes_fin = 0;
+	lineno = 0;
+	while(!(feof(f))) {
+		char cmd[6];
+		lineno++;
+		eat_space();
+		*cmd = '\0';
+		fgets(cmd, 5, f);
+		if (*cmd == '#') {
+			char s[1024]; /* will break for comment lines longer than 1k */
+			fgets(s, sizeof(s), f);
+			continue;
+		}
+		if ((*cmd == '\n') || (*cmd == '\t') || (*cmd == '\0'))
+			continue;
+		if (strcmp(cmd, "net1") == 0)
+			load_net(0);
+		else if (strcmp(cmd, "net2") == 0)
+			load_net(1);
+		else if (strcmp(cmd, "neut") == 0)
+			load_neut();
+		else if (strcmp(cmd, "conn") == 0)
+			load_conn();
+	}
+
+
+#ifdef DEBUG_GR
+	gr_print(g, stdout, "(input0) ");
+	gr_draw(g, "input0", "png");
+#endif
+
+	/* preprocessing nets */
+	{
+		int net, node;
+
+#if 0
+/* this optimization looked like a good idea but fails for O.in because
+   it's always cheaper to cut T-> and S-> bounding than anything else */
+		/* merge net nodes into (S) and (T) */
+		for(net = 0; net < 2; net++)
+			for(node = 0; node < nn_net[net]; node++)
+				gr_merge_nodes(g, net, nets[net][node]);
+
+		/* make sure (S) and (T) connections are heavy */
+		for(net = 0; net < 2; net++)
+			for(node = 0; node < g->n; node++)
+				if (gr_get_(g, net, node))
+					gr_add_(g, net, node, NET_EDGES);
+#endif
+
+		/* make sure (S) and (T) connections are heavy */
+		for(net = 0; net < 2; net++)
+			for(node = 0; node < nn_net[net]; node++)
+				gr_add_(g, net, nets[net][node], NET_EDGES);
+	}
+
+#ifdef DEBUG_GR
+	gr_print(g, stdout, "(input1) ");
+	gr_draw(g, "input1", "png");
+#endif
+
+	return g;
+}
+
Index: trunk/src_plugins/mincut/pcb-mincut/load.h
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/load.h	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/load.h	(revision 1062)
@@ -0,0 +1,5 @@
+#include <stdio.h>
+#include "graph.h"
+
+/* load example input from FILE f and return the preprocessed graph */
+gr_t *load(FILE *f);
Index: trunk/src_plugins/mincut/pcb-mincut/main.c
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/main.c	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/main.c	(revision 1062)
@@ -0,0 +1,28 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "graph.h"
+#include "load.h"
+#include "solve.h"
+
+#define strempty(s) ((s) == NULL ? "" : (s))
+
+int main()
+{
+	int *best;
+	gr_t *g;
+	int n;
+
+	g = load(stdin);
+	if (g == NULL) {
+		fprintf(stderr, "Failed to load input, exiting\n");
+		exit(1);
+	}
+	best = solve(g);
+	for(n = 0; best[n*2] != -1; n++)
+		printf("%s-%s\n", strempty(g->node2name[best[n*2+0]]), strempty(g->node2name[best[n*2+1]]));
+
+	gr_free(g);
+	free(best);
+
+	return 0;
+}
Index: trunk/src_plugins/mincut/pcb-mincut/proposals.txt
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/proposals.txt	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/proposals.txt	(revision 1062)
@@ -0,0 +1,99 @@
+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.
+    With further improvments by John Doty and Levente Kovacs with detailed
+    method described by Chris Smith.
+
+ 3. separate connection/netlist history (saved with the PCB). No details
+    yet. Might be the same as I/2.
+
+ 4. Markus Hitter's proposal of pinning down rat lines later converted to
+    to copper. (This is not strictly about keeping track of object
+    history, unless we consider pinned down rats as history of a later copper
+    trace)
+
+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.
+
+ 6. pick a random path from a random pin/pad of net1 to another random
+    pin/pad of net2 and let the user resolve this short. Once this is done,
+    the process can be repeated until all shorts are eliminated. Proposed
+    by Russell Dill.
+
+III. manual net tagging
+
+ 1. 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.
+
+ 2. I/2 combined with III/1; by default it follows I/2 but the user can
+    chose to manually edit tags as in III/1.
+
+
+
Index: trunk/src_plugins/mincut/pcb-mincut/solve.c
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/solve.c	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/solve.c	(revision 1062)
@@ -0,0 +1,253 @@
+/*    pcb-mincut, a prototype project demonstrating how to highlight shorts
+ *    Copyright (C) 2012 Tibor 'Igor2' Palinkas
+ *
+ *   This program is free software; you can redistribute it and/or modify
+ *   it under the terms of the GNU General Public License as published by
+ *   the Free Software Foundation; either version 2 of the License, or
+ *   (at your option) any later version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License along
+ *   with this program; if not, write to the Free Software Foundation, Inc.,
+ *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+
+#include <stdlib.h>
+#include <string.h>
+#include <math.h>
+#include "solve.h"
+
+/* Karger's algorithm as described in the wikipedia article
+   http://en.wikipedia.org/wiki/Karger%27s_algorithm
+*/
+
+#define BAD 1000000
+
+/*#define DEBUG_MERGES*/
+/*#define DEBUG_TAGS*/
+/*#define DEBUG_SOLVE*/
+
+typedef struct {
+	gr_t *g;
+	int *avail;    /* nodes IDs still avaialble for merging */
+	int *neigh;    /* neighbor list */
+	int *tag;
+	int num_avail; /* number of nodes still avaialble for merging */
+} sstate_t;
+
+static int pick_del(sstate_t *st)
+{
+	int idx, ret, size;
+	idx = rand() % st->num_avail;
+	ret = st->avail[idx];
+	size = (st->num_avail-idx-1) * sizeof(int);
+	if (size > 0)
+		memmove(&st->avail[idx], &st->avail[idx+1], size);
+	st->num_avail--;
+	return ret;
+}
+
+static int pick_neigh(sstate_t *st, int node)
+{
+	int n, num_neigh;
+
+	num_neigh = 0;
+	for(n = 0; n < st->g->n; n++) {
+		if ((n != node) && (gr_get_(st->g, n, node) > 0)) {
+			st->neigh[num_neigh] = n;
+			num_neigh++;
+		}
+	}
+	return st->neigh[rand() % num_neigh];
+}
+
+static void retag(sstate_t *st, int from, int to)
+{
+	int n;
+	for(n = 0; n < st->g->n; n++)
+		if (st->tag[n] == from)
+			st->tag[n] = to;
+}
+
+
+/* clone graph and do a randon contraction */
+int solve_(gr_t *g_, int *cuts)
+{
+	sstate_t st;
+	int n, result, tags;
+	static int solution = -1;
+#ifdef DEBUG_MERGES
+	int cnt = 0;
+	char fn[512];
+#endif
+
+	solution++;
+	st.g = gr_clone(g_);
+	st.avail = malloc(sizeof(int) * st.g->n);
+	st.neigh = malloc(sizeof(int) * st.g->n);
+	st.tag = malloc(sizeof(int) * st.g->n);
+
+#define FREE_ALL() \
+	gr_free(st.g); \
+	free(st.avail); \
+	free(st.neigh); \
+	free(st.tag);
+
+	for(n = 2; n < st.g->n; n++)
+		st.tag[n] = -1;
+	st.tag[0] = 0;
+	st.tag[1] = 1;
+	tags = 2;
+
+	st.num_avail = 0;
+	for(n = 0; n < st.g->n; n++) {
+		if (gr_node_edges(st.g, n) > 0) {
+			st.avail[st.num_avail] = n;
+			st.num_avail++;
+		}
+	}
+
+	while(st.num_avail > 2) {
+		int n1, n2;
+		n2 = pick_del(&st);
+		n1 = pick_neigh(&st, n2);
+#ifndef DEBUG_MERGES
+#ifdef DEBUG_SOLVE
+			printf("Merge %d (%s) into %d (%s)\n", n2, st.g->node2name[n2], n1, st.g->node2name[n1]);
+#endif
+#endif
+		assert(n2 != n1);
+
+		/* propagate tags */
+		if ((st.tag[n1] != -1) && (st.tag[n2] == -1))
+			st.tag[n2] = st.tag[n1];
+		else if ((st.tag[n1] == -1) && (st.tag[n2] != -1))
+			st.tag[n1] = st.tag[n2];
+		else if ((st.tag[n1] == -1) && (st.tag[n2] == -1))
+			st.tag[n1] = st.tag[n2] = tags++;
+		else if ((st.tag[n1] != -1) && (st.tag[n2] != -1)) {
+			if ((st.tag[n1] > 1) && (st.tag[n2] <= 1))
+				retag(&st, st.tag[n1], st.tag[n2]);
+			else if ((st.tag[n2] > 1) && (st.tag[n1] <= 1))
+				retag(&st, st.tag[n2], st.tag[n1]);
+			else {
+				/* tag collision means we won't be able to distinguish between our
+				   two groups and our cut won't resolve the short anyway */
+#ifdef DEBUG_TAGS
+				printf("Tag collision!\n");
+#endif
+				FREE_ALL();
+				return BAD;
+			}
+		}
+
+		gr_merge_nodes(st.g, n1, n2);
+
+#ifdef DEBUG_MERGES
+			sprintf(fn, "contraction_%02d_%02d", solution, cnt);
+			cnt++;
+			gr_draw(st.g, fn, "png");
+			printf("Merge %d into %d, result in %s leaving %d available nodes\n", n2, n1, fn, st.num_avail);
+#endif
+	}
+
+#ifdef DEBUG_SOLVE
+	{
+		char fn[128];
+		sprintf(fn, "contraction_%02d", solution);
+		gr_draw(st.g, fn, "png");
+	}
+#endif
+
+	result = gr_get(st.g, st.avail[0], st.avail[1]);
+
+#ifdef DEBUG_TAGS
+	{
+		int t, n;
+		printf("Groups:\n");
+		for(t = 0; t < 2; t++) {
+			printf("  [%d] is", t);
+			for(n = 0; n < st.g->n; n++) {
+				if (st.tag[n] == t)
+					printf(" %s", st.g->node2name[n]);
+			}
+			printf("\n");
+		}
+	}
+#endif
+	{
+		int x, y, num_cuts = 0;
+		for(y = 0; y < st.g->n; y++)
+			for(x = y+1; x < st.g->n; x++)
+				if ((gr_get_(g_, x, y) > 0) && (st.tag[x] != st.tag[y])) {
+#ifdef DEBUG_TAGS
+					printf("CUT %s-%s\n", st.g->node2name[x], st.g->node2name[y]);
+#endif
+					cuts[num_cuts*2+0] = x;
+					cuts[num_cuts*2+1] = y;
+					num_cuts++;
+				}
+		cuts[num_cuts*2+0] = -1;
+		cuts[num_cuts*2+1] = -1;
+	}
+	FREE_ALL();
+	return result;
+}
+
+#define strempty(s) ((s) == NULL ? "" : (s))
+int *solve(gr_t *g)
+{
+	int n, best, res, till, cuts_size;
+	double nd;
+	int *cuts, *best_cuts;
+
+	/* count how many nodes we really have - the ones not cut down from the graph by the preprocessor */
+	nd = 0;
+	for(n = 0; n < g->n; n++)
+		if (gr_node_edges(g, n) > 0)
+			nd++;
+
+	till = (int)(nd * (nd-1.0) / 2.0 * log(nd))+1;
+#ifdef DEBUG_SOLVE
+	printf("Running solver at most %d times for %d relevant nodes\n", till, (int)nd);
+#endif
+
+	cuts_size = ((nd * nd) + 1) * sizeof(int);
+	cuts = malloc(cuts_size);
+	best_cuts = malloc(cuts_size);
+
+	best = BAD;
+	for(n = 0; n < till; n++) {
+		res = solve_(g, cuts);
+#ifdef DEBUG_SOLVE
+		printf("solution %d=%d\n", n, res);
+#endif
+		if (res < best) {
+			best = res;
+			memcpy(best_cuts, cuts, cuts_size);
+		}
+		if (best == 1) /* we won't find a better solution ever */
+			break;
+	}
+
+#ifdef DEBUG_SOLVE
+	printf("Best solution cuts %d edge%s:", best, best == 1 ? "" : "s");
+	for(n = 0; best_cuts[n*2] != -1; n++) {
+		printf(" %d:%s-%d:%s", best_cuts[n*2+0], strempty(g->node2name[best_cuts[n*2+0]]), best_cuts[n*2+1], strempty(g->node2name[best_cuts[n*2+1]]));
+	}
+	printf("\n");
+#endif
+	if (best == BAD) {
+		free(best_cuts);
+		free(cuts);
+		return NULL;
+	}
+	free(cuts);
+	return best_cuts;
+}
+
+
Index: trunk/src_plugins/mincut/pcb-mincut/solve.h
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/solve.h	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/solve.h	(revision 1062)
@@ -0,0 +1,5 @@
+#include "graph.h"
+
+/* returns a list of object ID pairs (each nth and n+1th element) terminated
+   by a -1;-1. Cutting these vertices would separate g. */
+int *solve(gr_t *g);
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/C.in
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/C.in	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/C.in	(revision 1062)
@@ -0,0 +1,9 @@
+# a---b
+# |
+# C---D
+
+net1 a b
+net2 C D
+conn a-b C-D
+conn a-C
+
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/C.ref
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/C.ref	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/C.ref	(revision 1062)
@@ -0,0 +1 @@
+C-a
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/H.in
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/H.in	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/H.in	(revision 1062)
@@ -0,0 +1,8 @@
+# a-1-b
+#   |
+# C-2-D
+
+net1 a b
+net2 C D
+neut 1 2
+conn C-2 D-2 a-1 b-1 1-2
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/H.ref
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/H.ref	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/H.ref	(revision 1062)
@@ -0,0 +1 @@
+2-1
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/H2.in
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/H2.in	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/H2.in	(revision 1062)
@@ -0,0 +1,16 @@
+# a-1-2-3-4-5-b
+#       |
+#       6
+#       |
+#       7
+#       |
+# C-8-9-10-11-D
+
+net1 a b
+net2 C D
+neut 1 2 3 4 5 6 7 8 9 10 11
+conn a-1 1-2 2-3 3-4 4-5 5-b
+conn C-8 8-9 9-10 10-11 11-D
+conn 3-6 6-7 7-10
+
+
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/H2.ref
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/H2.ref	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/H2.ref	(revision 1062)
@@ -0,0 +1 @@
+7-6
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/H3.in
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/H3.in	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/H3.in	(revision 1062)
@@ -0,0 +1,18 @@
+# a-1-2-3-4-5-b
+#       |
+#       6-+
+#       | |
+#       7-+
+#       |/
+# C-8-9-10-11-D
+
+net1 a b
+net2 C D
+neut 1 2 3 4 5 6 7 8 9 10 11
+conn a-1 1-2 2-3 3-4 4-5 5-b
+conn C-8 8-9 9-10 10-11 11-D
+conn 3-6 6-7 7-10
+
+#redundancy - cut 3-6 is the best:
+conn 6-7 7-10
+
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/H3.ref
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/H3.ref	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/H3.ref	(revision 1062)
@@ -0,0 +1 @@
+6-3
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/H4.in
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/H4.in	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/H4.in	(revision 1062)
@@ -0,0 +1,12 @@
+# a   b
+# |   |
+# 1---2
+# |   |
+# C   D
+
+net1 a b
+net2 C D
+neut 1 2
+conn a-1 b-2
+conn C-1 D-2
+conn 1-2
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/H4.ref
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/H4.ref	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/H4.ref	(revision 1062)
@@ -0,0 +1,2 @@
+1-C
+2-D
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/Makefile
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/Makefile	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/Makefile	(revision 1062)
@@ -0,0 +1,12 @@
+TESTS = C.diff H.diff H2.diff H3.diff H4.diff O.diff \
+        rats1.diff rats2.diff rats3.diff
+
+all: $(TESTS)
+
+.SUFFIXES: .in .out .diff .ref
+
+.out.diff:
+	@diff -u $*.out $*.ref
+
+.in.out:
+	@../main < $*.in >$*.out
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/O.in
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/O.in	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/O.in	(revision 1062)
@@ -0,0 +1,9 @@
+# a---b
+# |   |
+# C---D
+
+net1 a b
+net2 C D
+conn a-b C-D
+conn a-C b-D
+
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/O.ref
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/O.ref	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/O.ref	(revision 1062)
@@ -0,0 +1,2 @@
+C-a
+D-b
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/rats1.in
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/rats1.in	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/rats1.in	(revision 1062)
@@ -0,0 +1,12 @@
+# a   b
+# |   |
+# 1   2
+# |   |
+# C   D
+
+net1 a b
+net2 C D
+neut 1 2
+conn a-1 b-2
+conn C-1 D-2
+
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/rats1.ref
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/rats1.ref	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/rats1.ref	(revision 1062)
@@ -0,0 +1,2 @@
+1-C
+2-D
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/rats2.in
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/rats2.in	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/rats2.in	(revision 1062)
@@ -0,0 +1,8 @@
+# a---C---b---D
+
+net1 a b
+net2 C D
+conn a-C C-b b-D
+
+
+
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/rats2.ref
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/rats2.ref	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/rats2.ref	(revision 1062)
@@ -0,0 +1,3 @@
+C-a
+C-b
+D-b
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/rats3.in
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/rats3.in	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/rats3.in	(revision 1062)
@@ -0,0 +1,9 @@
+# C---a---b---D
+
+net1 a b
+net2 C D
+conn C-a a-b b-D
+
+
+
+
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/rats3.ref
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/rats3.ref	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/rats3.ref	(revision 1062)
@@ -0,0 +1,2 @@
+C-a
+D-b
Index: trunk/src_plugins/mincut/pcb-mincut/test_cases/redundant.in
===================================================================
--- trunk/src_plugins/mincut/pcb-mincut/test_cases/redundant.in	(nonexistent)
+++ trunk/src_plugins/mincut/pcb-mincut/test_cases/redundant.in	(revision 1062)
@@ -0,0 +1,20 @@
+# 12----13---14
+# |           |
+# a-1-2-3-4-5-b
+#       |
+#       6-+
+#       | |
+#       7-+
+#       |
+# C-8-9-10-11-D
+
+net1 a b
+net2 C D
+neut 1 2 3 4 5 6 7 8 9 10 11 12 13 14
+conn a-1 1-2 2-3 3-4 4-5 5-b
+conn C-8 8-9 9-10 10-11 11-D
+conn 3-6 6-7 7-10
+conn a-12 12-13 13-14 14-b
+conn 6-7
+
+
Index: trunk/src_plugins/mincut/rats_mincut.c
===================================================================
--- trunk/src_plugins/mincut/rats_mincut.c	(nonexistent)
+++ trunk/src_plugins/mincut/rats_mincut.c	(revision 1062)
@@ -0,0 +1,412 @@
+/* $Id$ */
+
+/*
+ *                            COPYRIGHT
+ *
+ *  PCB, interactive printed circuit board design
+ *  Copyright (C) 2013..2015 Tibor 'Igor2' Palinkas
+ * 
+ *  This module, rats.c, was written and is Copyright (C) 1997 by harry eaton
+ *  this module is also subject to the GNU GPL as described below
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+#include "config.h"
+
+#include <math.h>
+#include <stdio.h>
+#include <assert.h>
+
+#include "global.h"
+
+#include "create.h"
+#include "data.h"
+#include "draw.h"
+#include "error.h"
+#include "file.h"
+#include "find.h"
+#include "misc.h"
+#include "mymem.h"
+#include "polygon.h"
+#include "rats.h"
+#include "search.h"
+#include "set.h"
+#include "undo.h"
+
+
+#include "rats.h"
+#include "pcb-mincut/graph.h"
+#include "pcb-mincut/solve.h"
+
+#define debprintf(x...)
+
+typedef struct short_conn_s short_conn_t;
+struct short_conn_s {
+	int gid;											/* id in the graph */
+	int from_type;
+/*	AnyObjectType *from;*/
+	int from_id;
+	int to_type;
+	int edges;										/* number of edges */
+	AnyObjectType *to;
+	found_conn_type_t type;
+	short_conn_t *next;
+};
+
+static short_conn_t *short_conns = NULL;
+static int num_short_conns = 0;
+static int short_conns_maxid = 0;
+
+static void proc_short_cb(int current_type, void *current_obj, int from_type, void *from_obj, found_conn_type_t type)
+{
+	AnyObjectType *curr = current_obj, *from = from_obj;
+	short_conn_t *s;
+
+	s = malloc(sizeof(short_conn_t));
+	if (from != NULL) {
+		s->from_type = from_type;
+		s->from_id = from->ID;
+	}
+	else {
+		s->from_type = 0;
+		s->from_id = -1;
+	}
+	s->to_type = current_type;
+	s->to = curr;
+	s->type = type;
+	s->edges = 0;
+	s->next = short_conns;
+	short_conns = s;
+	if (curr->ID > short_conns_maxid)
+		short_conns_maxid = curr->ID;
+	num_short_conns++;
+
+	debprintf(" found %d %d/%p type %d from %d\n", current_type, curr->ID, current_obj, type, from == NULL ? -1 : from->ID);
+}
+
+/* returns 0 on succes */
+static int proc_short(PinType * pin, PadType * pad, int ignore)
+{
+	find_callback_t old_cb;
+	Coord x, y;
+	short_conn_t *n, **lut_by_oid, **lut_by_gid, *next;
+	int gids;
+	gr_t *g;
+	void *S, *T;
+	int *solution;
+	int i, maxedges;
+	int bad_gr = 0;
+
+	if (!TEST_FLAG(ENABLEMINCUTFLAG, PCB))
+		return bad_gr;
+
+	if (!Settings.EnableMincut)
+		return bad_gr;
+
+	/* only one should be set, but one must be set */
+	assert((pin != NULL) || (pad != NULL));
+	assert((pin == NULL) || (pad == NULL));
+
+	if (pin != NULL) {
+		debprintf("short on pin!\n");
+		SET_FLAG(WARNFLAG, pin);
+		x = pin->X;
+		y = pin->Y;
+	}
+	else if (pad != NULL) {
+		debprintf("short on pad!\n");
+		SET_FLAG(WARNFLAG, pad);
+		if (TEST_FLAG(EDGE2FLAG, pad)) {
+			x = pad->Point2.X;
+			y = pad->Point2.Y;
+		}
+		else {
+			x = pad->Point1.X;
+			y = pad->Point1.Y;
+		}
+	}
+
+	/* run only if net is not ignored */
+	if (ignore)
+		return 0;
+
+	short_conns = NULL;
+	num_short_conns = 0;
+	short_conns_maxid = 0;
+
+	/* perform a search using MINCUTFLAG, calling back proc_short_cb() with the connections */
+	old_cb = find_callback;
+	find_callback = proc_short_cb;
+	SaveFindFlag(MINCUTFLAG);
+	LookupConnection(x, y, false, 1, MINCUTFLAG);
+
+	debprintf("- alloced for %d\n", (short_conns_maxid + 1));
+	lut_by_oid = calloc(sizeof(short_conn_t *), (short_conns_maxid + 1));
+	lut_by_gid = calloc(sizeof(short_conn_t *), (num_short_conns + 3));
+
+	g = gr_alloc(num_short_conns + 2);
+
+	g->node2name = calloc(sizeof(char *), (num_short_conns + 2));
+
+	/* conn 0 is S and conn 1 is T and set up lookup arrays */
+	for (n = short_conns, gids = 2; n != NULL; n = n->next, gids++) {
+		char *s, *typ;
+		ElementType *parent;
+		n->gid = gids;
+		debprintf(" {%d} found %d %d/%p type %d from %d\n", n->gid, n->to_type, n->to->ID, n->to, n->type, n->from_id);
+		lut_by_oid[n->to->ID] = n;
+		lut_by_gid[n->gid] = n;
+
+		s = malloc(256);
+		parent = NULL;
+		switch (n->to_type) {
+		case PIN_TYPE:
+			typ = "pin";
+			parent = ((PinType *) (n->to))->Element;
+			break;
+		case VIA_TYPE:
+			typ = "via";
+			parent = ((PinType *) (n->to))->Element;
+			break;
+		case PAD_TYPE:
+			typ = "pad";
+			parent = ((PadType *) (n->to))->Element;
+			break;
+		case LINE_TYPE:
+			typ = "line";
+			break;
+		default:
+			typ = "other";
+			break;
+		}
+		if (parent != NULL) {
+			TextType *name;
+			name = &parent->Name[1];
+			if ((name->TextString == NULL) || (*name->TextString == '\0'))
+				sprintf(s, "%s #%d \\nof #%d", typ, n->to->ID, parent->ID);
+			else
+				sprintf(s, "%s #%d \\nof %s", typ, n->to->ID, name->TextString);
+		}
+		else
+			sprintf(s, "%s #%d", typ, n->to->ID);
+		g->node2name[n->gid] = s;
+	}
+	g->node2name[0] = strdup("S");
+	g->node2name[1] = strdup("T");
+
+	/* calculate how many edges each node has and the max edge count */
+	maxedges = 0;
+	for (n = short_conns; n != NULL; n = n->next) {
+		short_conn_t *from;
+
+		n->edges++;
+		if (n->edges > maxedges)
+			maxedges = n->edges;
+
+		if (n->from_id >= 0) {
+			from = lut_by_oid[n->from_id];
+			if (from == NULL) {
+				/* no from means broken graph (multiple components) */
+				if (n->from_id >= 2) {	/* ID 0 and 1 are start/stop, there won't be from for them */
+					fprintf(stderr, "rats_mincut.c error: graph has multiple components, bug in find.c (n->from_id=%d)!\n", n->from_id);
+					bad_gr = 1;
+				}
+				continue;
+			}
+			from->edges++;
+			if (from->edges > maxedges)
+				maxedges = from->edges;
+		}
+	}
+
+
+	S = NULL;
+	T = NULL;
+	for (n = short_conns; n != NULL; n = n->next) {
+		short_conn_t *from;
+		void *spare;
+
+		spare = NULL;
+		if (n->to_type == PIN_TYPE)
+			spare = ((PinType *) n->to)->Spare;
+		if (n->to_type == PAD_TYPE)
+			spare = ((PadType *) n->to)->Spare;
+		if (spare != NULL) {
+			void *net = &(((LibraryMenuTypePtr) spare)->Name[2]);
+			debprintf(" net=%s\n", net);
+			if (S == NULL) {
+				debprintf(" -> became S\n");
+				S = net;
+			}
+			else if ((T == NULL) && (net != S)) {
+				debprintf(" -> became T\n");
+				T = net;
+			}
+
+			if (net == S)
+				gr_add_(g, n->gid, 0, 100000);
+			else if (net == T)
+				gr_add_(g, n->gid, 1, 100000);
+		}
+		/* if we have a from object, look it up and make a connection between the two gids */
+		if (n->from_id >= 0) {
+			int weight;
+			short_conn_t *from = lut_by_oid[n->from_id];
+
+			from = lut_by_oid[n->from_id];
+			/* weight: 1 for connections we can break, large value for connections we shall not break */
+			if ((n->type == FCT_COPPER) || (n->type == FCT_START)) {
+				/* connection to a pin/pad is slightly stronger than the
+				   strongest obj-obj conn; obj-obj conns are weaker at junctions where many
+				   objects connect */
+				if ((n->from_type == PIN_TYPE) || (n->from_type == PAD_TYPE) || (n->to_type == PIN_TYPE) || (n->to_type == PAD_TYPE))
+					weight = maxedges * 2 + 2;
+				else
+					weight = maxedges * 2 - n->edges - from->edges + 1;
+			}
+			else
+				weight = 10000;
+			if (from != NULL) {
+				gr_add_(g, n->gid, from->gid, weight);
+				debprintf(" CONN %d %d\n", n->gid, from->gid);
+			}
+		}
+	}
+
+/*#define MINCUT_DRAW*/
+#ifdef MINCUT_DRAW
+	{
+		static int drw = 0;
+		char gfn[256];
+		drw++;
+		sprintf(gfn, "A_%d_a", drw);
+		debprintf("gfn=%s\n", gfn);
+		gr_draw(g, gfn, "png");
+	}
+#endif
+
+	if (!bad_gr) {
+		solution = solve(g);
+
+		if (solution != NULL) {
+			debprintf("Would cut:\n");
+			for (i = 0; solution[i] != -1; i++) {
+				short_conn_t *s;
+				debprintf("%d:", i);
+				s = lut_by_gid[solution[i]];
+				debprintf("%d %p", solution[i], s);
+				if (s != NULL) {
+					SET_FLAG(WARNFLAG, s->to);
+					debprintf("  -> %d", s->to->ID);
+				}
+				debprintf("\n");
+			}
+
+			free(solution);
+		}
+		else {
+			fprintf(stderr, "mincut didn't find a solution, falling back to the old warn\n");
+			bad_gr = 1;
+		}
+	}
+	free(lut_by_oid);
+	free(lut_by_gid);
+
+	for (n = short_conns; n != NULL; n = next) {
+		next = n->next;
+		free(n);
+	}
+
+
+	ResetFoundLinesAndPolygons(false);
+	ResetFoundPinsViasAndPads(false);
+	RestoreFindFlag();
+
+	find_callback = old_cb;
+	return bad_gr;
+}
+
+typedef struct pinpad_s pinpad_t;
+struct pinpad_s {
+	int ignore;										/* if 1, changed our mind, do not check */
+	PinType *pin;
+	PadType *pad;
+	const char *with_net;					/* the name of the net this pin/pad is in short with */
+	pinpad_t *next;
+};
+
+static pinpad_t *shorts = NULL;
+
+void rat_found_short(PinType * pin, PadType * pad, const char *with_net)
+{
+	pinpad_t *pp;
+	pp = malloc(sizeof(pinpad_t));
+	pp->ignore = 0;
+	pp->pin = pin;
+	pp->pad = pad;
+	pp->with_net = with_net;
+	pp->next = shorts;
+	shorts = pp;
+}
+
+void rat_proc_shorts(void)
+{
+	pinpad_t *n, *i, *next;
+	int bad_gr = 0;
+	for (n = shorts; n != NULL; n = next) {
+		next = n->next;
+
+		if (n->pin != NULL)
+			SET_FLAG(WARNFLAG, n->pin);
+		if (n->pad != NULL)
+			SET_FLAG(WARNFLAG, n->pad);
+
+
+		/* run only if net is not ignored */
+		if ((!bad_gr) && (proc_short(n->pin, n->pad, n->ignore) != 0)) {
+			fprintf(stderr, "Can't run mincut :(\n");
+			bad_gr = 1;
+		}
+
+		if (!bad_gr) {
+			/* check if the rest of the shorts affect the same nets - ignore them if so */
+			for (i = n->next; i != NULL; i = i->next) {
+				LibraryMenuType *spn, *spi;
+				spn = (n->pin != NULL) ? n->pin->Spare : n->pad->Spare;
+				spi = (i->pin != NULL) ? i->pin->Spare : i->pad->Spare;
+
+				if ((spn == NULL) || (spi == NULL))
+					continue;
+
+				/* can compare by pointer - names are never strdup()'d */
+				if ((&spn->Name[2] == i->with_net) || (&spi->Name[2] == n->with_net))
+					i->ignore = 1;
+			}
+		}
+		free(n);
+	}
+	shorts = NULL;
+}
+
+
+#include "stub_mincut.h"
+void hid_mincut_init(void)
+{
+	stub_rat_found_short = rat_found_short;
+	stub_rat_proc_shorts = rat_proc_shorts;
+}
+
Index: trunk/src_plugins/mincut/rats_mincut.h
===================================================================
--- trunk/src_plugins/mincut/rats_mincut.h	(nonexistent)
+++ trunk/src_plugins/mincut/rats_mincut.h	(revision 1062)
@@ -0,0 +1,29 @@
+/* $Id$ */
+
+/*
+ *                            COPYRIGHT
+ *
+ *  PCB, interactive printed circuit board design
+ *  Copyright (C) 2013..2015 Tibor 'Igor2' Palinkas
+ * 
+ *  This module, rats.c, was written and is Copyright (C) 1997 by harry eaton
+ *  this module is also subject to the GNU GPL as described below
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+void rat_found_short(PinType * pin, PadType * pad, const char *with_net);
+void rat_proc_shorts(void);