rsmt100.ps

生成直角Steiner树的程序包

%!PS-Adobe-3.0
%%Creator: Steiner Tree Version 3.1
%%Copyright: Copyright (c) 1998, 2001 by David M. Warme
%%LanguageLevel: 1
%%DocumentNeededResources: font Times-Roman
%%DocumentSuppliedResources: procset SteinerTreeProcs 2.0 0
%%EndComments
%%BeginProlog
%%BeginProcSet: SteinerTreeProcs 2.0 0
/LabelTerminals	0		def	% set non-zero to label terminals
/inch { 72 mul } def
/PaperWidth	8.5 inch	def
/PaperHeight	11 inch		def
/BigBoxSize	7 inch		def
/SmallBoxSize	2 inch		def
/SmallBoxHeight	SmallBoxSize	def
/SmallBoxWidth	SmallBoxSize	def
/BoxHeight	BigBoxSize	def
/BoxWidth	BigBoxSize	def
/MinX		0		def
/MaxX		1		def
/MinY		0		def
/MaxY		1		def
/BoxMode	0		def	% (0 ==> big plot, 1 ==> small plots)
/SmallBoxCount	0		def
/TermRadius	1 32 div inch	def
/LineWidth	currentlinewidth	def

% Define the clipping region to be the inside edge of the box.

/ClipHeight	BigBoxSize LineWidth sub def
/ClipWidth	ClipHeight def

% Define the plotting region so that points plotted at the extremes will
% exactly meet the edge of the clipping region.  (Reduce by the terminal
% radius on each side.)

/PlotHeight	ClipHeight TermRadius 2 mul sub def
/PlotWidth	ClipWidth  TermRadius 2 mul sub	def
/XlateX { MinX sub MaxX MinX sub div PlotWidth mul } def
/XlateY { MinY sub MaxY MinY sub div PlotHeight mul } def
/XlateXY { exch XlateX exch XlateY } def
/Dup2 { dup 3 -1 roll dup 4 1 roll exch } def
/Swap2 { 4 2 roll } def
% define the two fonts we will use:
%	- one for numbering the terminals
%	- one for printing the plot's title
/TermNumPointsize	8	def
/TitlePointsize		15	def
/TermNumFont
	/Times-Roman findfont TermNumPointsize scalefont
def
/UseTermNumFont { TermNumFont setfont } def
/TitleFont
	/Times-Roman findfont TitlePointsize scalefont
def
/UseTitleFont { TitleFont setfont } def
/DefineTerminals {
	/NumTerms exch def
	/TermX NumTerms array def
	/TermY NumTerms array def
	/TermIndex 0 def
} def
/DT {
	TermY TermIndex 3 -1 roll put
	TermX TermIndex 3 -1 roll put
	/TermIndex TermIndex 1 add def
} def
/SetAxes {	% minx maxx miny maxy
	/MaxY exch def
	/MinY exch def
	/MaxX exch def
	/MinX exch def
} def
/PTString	12 string	def
/Plot_Terminals {
	LabelTerminals 0 eq {
		% Display terminals, no labels
		0 1 NumTerms 1 sub {			% i
			dup				% i i
			TermX exch get exch		% x i
			TermY exch get
			newpath
			XlateXY
			TermRadius 0 360 arc fill
		} for
	}
	{	% Display terminals, with labels
		0 1 NumTerms 1 sub {			% i
			dup				% i i
			PTString cvs exch dup		% str i i
			TermX exch get exch		% str x i
			TermY exch get			% str x y
			newpath
			XlateXY
			Dup2
			TermRadius 0 360 arc fill
			moveto TermRadius 3 mul dup neg rmoveto
			UseTermNumFont
			show
		} for
	} ifelse
} def
% n T ==> Xn Yn, get coordinates of terminal n.
/T {
	dup
	TermX exch get exch
	TermY exch get
} def
% Draw a line segment.
/S {
	newpath
	XlateXY
	moveto
	XlateXY
	lineto
	stroke
} def
% Draw a corner.  First point is incident to vertical segment.
% Second point is incident to horizontal segment.
/C {	% x1 y1 x2 y2
	newpath
	% x1 y1 x2 y2 -> x1 y1 x1 y2 x2 y2
	4 -1 roll dup 5 1 roll exch dup 4 -1 roll exch
	XlateXY
	moveto
	XlateXY
	lineto
	XlateXY
	lineto
	stroke
} def
/BeginPlot {
	FlushSmallPlot
	gsave
	PaperWidth BoxWidth sub 2 div
	 PaperHeight BoxHeight sub 2 div
	  translate
	newpath
	0 0 moveto
	BoxWidth 0 lineto
	BoxWidth BoxHeight lineto
	0 BoxHeight lineto
	closepath
	stroke
	gsave
	% establish a clipping region at the inside edge of the box
	LineWidth 2 div dup moveto
	ClipWidth 0 rlineto
	0 ClipHeight rlineto
	ClipWidth neg 0 rlineto
	closepath
	clip
	% establish the origin for the plotting region
	LineWidth 2 div TermRadius add
	 dup
	  translate
} def
/EndPlot {
	grestore
	newpath
	UseTitleFont
	0 0 moveto
		dup stringwidth pop BigBoxSize exch sub 2 div
		TitlePointsize -2 mul
	rmoveto
	show
	grestore
	showpage
} def
/BeginSmallPlot {
	gsave
	.75 inch SmallBoxCount 3 mod SmallBoxWidth .5 inch add mul add
	  .75 inch 3 SmallBoxCount 3 idiv sub SmallBoxHeight .5 inch add mul add
	    translate
	SmallBoxWidth BoxWidth div
	 SmallBoxHeight BoxHeight div
	  scale
	newpath
	0 0 moveto
	BoxWidth 0 lineto
	BoxWidth BoxHeight lineto
	0 BoxHeight lineto
	closepath
	stroke
	gsave
	% establish a clipping region at the inside edge of the box
	LineWidth 2 div dup moveto
	ClipWidth 0 rlineto
	0 ClipHeight rlineto
	ClipWidth neg 0 rlineto
	closepath
	clip
	% establish the origin for the plotting region
	LineWidth 2 div TermRadius add
	 dup
	  translate
} def
/EndSmallPlot2 {
	grestore
	newpath
	UseTitleFont
	0 0 moveto
		dup stringwidth pop BigBoxSize exch sub 2 div
		TitlePointsize -2 mul
	rmoveto
	show
	grestore
	/SmallBoxCount SmallBoxCount 1 add def
	SmallBoxCount 12 ge {
		FlushSmallPlot
	} if
} def
/FlushSmallPlot {
	SmallBoxCount 0 gt {
		showpage
		/SmallBoxCount	0 def
	} if
} def
/PT {
	dup				% i i
	TermX exch get exch		% x i
	TermY exch get
	newpath
	XlateXY
	TermRadius 0 360 arc fill
} def
%%EndProcSet
%%EndProlog

 % ./bb
 % Args:
 % Phase 1: 0.00 seconds

%%BeginSetup

0 10000 0 10000 SetAxes

100 DefineTerminals
	1857	2738	DT
	2894	8773	DT
	1463	5183	DT
	6905	8268	DT
	3221	2457	DT
	3473	730	DT
	2983	4045	DT
	5486	5208	DT
	815	6755	DT
	1875	934	DT
	606	7576	DT
	6045	4078	DT
	9323	8669	DT
	7952	2547	DT
	303	8201	DT
	6131	4811	DT
	7871	9452	DT
	854	1630	DT
	5468	655	DT
	7539	7194	DT
	2588	3671	DT
	5319	3872	DT
	4004	3636	DT
	8823	9370	DT
	2183	4813	DT
	4853	437	DT
	8935	5346	DT
	8461	2389	DT
	2920	9868	DT
	4339	473	DT
	8222	1895	DT
	9336	5659	DT
	5826	447	DT
	8995	3322	DT
	3337	1432	DT
	7140	4825	DT
	7970	3168	DT
	1959	6377	DT
	8240	6048	DT
	953	5905	DT
	5779	7114	DT
	7741	883	DT
	5927	7473	DT
	3088	4641	DT
	8609	9286	DT
	4558	9381	DT
	7577	1956	DT
	8888	4529	DT
	3717	7332	DT
	7074	9300	DT
	1880	753	DT
	8823	4604	DT
	255	6767	DT
	3610	8398	DT
	9728	2393	DT
	2860	8228	DT
	2032	5977	DT
	9534	3627	DT
	8144	172	DT
	1896	1532	DT
	6615	4909	DT
	3587	126	DT
	2628	2673	DT
	9761	9724	DT
	1941	1952	DT
	5552	6945	DT
	3436	3149	DT
	4392	4101	DT
	6746	2567	DT
	9328	6317	DT
	4146	9128	DT
	695	2216	DT
	6337	8418	DT
	8455	6114	DT
	2684	3094	DT
	713	9431	DT
	5066	5653	DT
	8216	6620	DT
	7158	6191	DT
	636	4345	DT
	676	6403	DT
	8073	876	DT
	7813	1209	DT
	6832	3156	DT
	1595	9219	DT
	2050	607	DT
	4780	2726	DT
	3303	2675	DT
	2177	523	DT
	4923	2899	DT
	5349	7686	DT
	2269	8907	DT
	784	3975	DT
	3825	1158	DT
	7260	142	DT
	9046	110	DT
	2894	8707	DT
	1994	6722	DT
	4565	6538	DT
	6363	3724	DT

%%EndSetup

 % initialize_constraint_pool: 0.00 seconds.
 % Constraint pool initialized with:
 %	1	Total degree rows	293	coeffs.
 %	100	Cutset rows		922	coeffs.
 %	0	Incompatibility rows	0	coeffs.
 %	250	2-terminal SEC rows	1112	coeffs.
 %	331	Total rows in pool	101	in LP
 % @PMEM 331 rows, 1 blocks, 6704 nzfree, 0 nzwasted, 9308 nztotal
 % build_initial_formulation: 0.00 seconds.
% Resuming node 0
  % @PAP adding 101 rows, 1215 nz to LP
  % @PL 101 rows, 293 cols, 1508 nonzeros, 37 slack, 64 tight.
  % @PAP adding 25 rows, 109 nz to LP
  % @PL 126 rows, 293 cols, 1617 nonzeros, 29 slack, 97 tight.
  % @PAP adding 22 rows, 130 nz to LP
  % @PL 148 rows, 293 cols, 1747 nonzeros, 37 slack, 111 tight.
  % @PAP adding 15 rows, 75 nz to LP
  % @PL 163 rows, 293 cols, 1822 nonzeros, 47 slack, 116 tight.
  % @PAP adding 11 rows, 65 nz to LP
  % @PL 174 rows, 293 cols, 1887 nonzeros, 47 slack, 127 tight.
  % @PAP adding 12 rows, 54 nz to LP
  % @PL 186 rows, 293 cols, 1941 nonzeros, 61 slack, 125 tight.
  % @PAP adding 6 rows, 61 nz to LP
  % @PL 192 rows, 293 cols, 2002 nonzeros, 64 slack, 128 tight.
  % @PAP adding 4 rows, 18 nz to LP
  % @PL 196 rows, 293 cols, 2020 nonzeros, 64 slack, 132 tight.
  % Node 0 LP 1 Solution, length = 69697.000000, 0.01 0
 % 7 fractional variables
 % @LO 0.02 69697.00000000000000000000 99.9000000000
 % @LN 0.02 69697.00000000000000000000 99.9000000000
 % @UO 0.02 74958.00000000000000000000 7.0185970810
 % @UN 0.02 74958.00000000000000000000 7.0185970810
 % @cutset: 9 connected components.
 % initially 33 congested vertices:
 % find_congested_components found 7 components:
 %	component 0:	3 verts,	4 edges
 %	component 1:	5 verts,	4 edges
 %	component 2:	6 verts,	6 edges
 %	component 3:	3 verts,	3 edges
 %	component 4:	3 verts,	3 edges
 %	component 5:	5 verts,	4 edges
 %	component 6:	3 verts,	3 edges
 % @D deleting 64 slack rows
  % @PAP adding 45 rows, 669 nz to LP
 % @PMEM 376 rows, 1 blocks, 5990 nzfree, 0 nzwasted, 9308 nztotal
  % @PL 177 rows, 293 cols, 2086 nonzeros, 29 slack, 148 tight.
  % @PAP adding 3 rows, 10 nz to LP
  % @PL 180 rows, 293 cols, 2096 nonzeros, 24 slack, 156 tight.
  % Node 0 LP 2 Solution, length = 72023.000000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 45
 % 0 fractional variables
 % @LO 0.02 69697.00000000000000000000 7.0185970810
 % @LN 0.02 72023.00000000000000000000 3.9155260279
 % @UO 0.02 74958.00000000000000000000 3.9155260279
 % @UN 0.02 73559.00000000000000000000 2.0881197406
 % @cutset: 5 connected components.
 % initially 20 congested vertices:
 % find_congested_components found 4 components:
 %	component 0:	3 verts,	3 edges
 %	component 1:	3 verts,	3 edges
 %	component 2:	3 verts,	3 edges
 %	component 3:	3 verts,	3 edges
 % @D deleting 24 slack rows
  % @PAP adding 11 rows, 158 nz to LP
 % @PMEM 387 rows, 1 blocks, 5821 nzfree, 0 nzwasted, 9308 nztotal
  % @PL 167 rows, 293 cols, 1983 nonzeros, 13 slack, 154 tight.
  % Node 0 LP 3 Solution, length = 72734.000000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 11
 % 0 fractional variables
 % @LO 0.02 72023.00000000000000000000 2.0881197406
 % @LN 0.02 72734.00000000000000000000 1.1215486888
 % @UO 0.03 73559.00000000000000000000 1.1215486888
 % @UN 0.03 73267.00000000000000000000 0.7274762171
 % Fixed 8 vars to 0 and 3 vars to 1.
 % @cutset: 2 connected components.
 % initially 4 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	3 verts,	3 edges
 % @D deleting 13 slack rows
  % @PAP adding 2 rows, 37 nz to LP
 % @PMEM 389 rows, 1 blocks, 5782 nzfree, 0 nzwasted, 9308 nztotal
  % @PL 156 rows, 293 cols, 1880 nonzeros, 3 slack, 153 tight.
  % Node 0 LP 4 Solution, length = 72979.000000, 0.01/0.00/0.00/0.00/0.00/0.00/0.00 2
 % 0 fractional variables
 % @UO 0.03 73267.00000000000000000000 0.7274762171
 % @UN 0.03 72979.00000000000000000000 0.3357130133
  % *     0     0    72979.0000    72979.0000
 % @LO 0.03 72734.00000000000000000000 0.3357130133
 % @LN 0.03 72979.00000000000000000000 0.0000000000

 % Certificate of solution:
 % @C	1941	2673
 % @C	3303	2457
 % @C	3587	473
 % @C	6045	4811
 % @C	1880	934
 % @C	8222	2389
 % @C	606	8201
 % @C	713	9219
 % @C	6615	4825
 % @C	1896	1630
 % @C	2684	3636
 % @C	2983	3636
 % @C	3436	3636
 % @C	6045	3872
 % @C	4392	3872
 % @C	4923	3872
 % @C	9323	9370
 % @C	2983	4641
 % @C	8995	2393
 % @C	4853	447
 % @C	5468	447
 % @C	3473	1158
 % @C	1463	5905
 % @C	1959	5977
 % @C	7813	883
 % @C	7813	1895
 % @C	8995	3627
 % @C	7871	9370
 % @C	8609	9370
 % @C	8888	4604
 % @C	606	6767
 % @C	676	6755
 % @C	3717	8398
 % @C	2894	8398
 % @C	6905	8418
 % @C	8240	6114
 % @C	7539	6620
 % @C	784	4345
 % @C	1463	4813
 % @C	7952	3156
 % @C	5927	7686
 % @C	2894	8907
 % @C	8073	172
 % @C	5066	6538
 % @C	6746	3156
 % @C	8935	5659
 % @C	8935	6114
%%Page: 1 1
BeginPlot
	Plot_Terminals
 % fs1: 0 64 62
	0 T	1941	2673	C
	1941	2673	64 T	S
	1941	2673	62 T	S
 % fs11: 4 87 34
	4 T	3303	2457	S
	3303	2457	87 T	S
	3303	2457	34 T	C
 % fs12: 5 61 29
	5 T	3587	473	C
	3587	473	61 T	S
	3587	473	29 T	S
 % fs24: 7 11 15
	7 T	6045	4811	C
	6045	4811	11 T	S
	6045	4811	15 T	S
 % fs26: 9 50 59
	9 T	1880	934	S
	1880	934	50 T	S
	1880	934	59 T	C
 % fs33: 13 30 27
	13 T	8222	2389	C
	8222	2389	30 T	S
	8222	2389	27 T	S
 % fs36: 14 10 75 84
	14 T	606	8201	S
	606	8201	10 T	S
	606	8201	713	9219	C
	713	9219	75 T	S
	713	9219	84 T	S
 % fs39: 15 60 35
	15 T	6615	4825	C
	6615	4825	60 T	S
	6615	4825	35 T	S
 % fs42: 17 59 64
	17 T	1896	1630	S
	1896	1630	59 T	S
	1896	1630	64 T	C
 % fs45: 20 74 6 66 22
	20 T	2684	3636	C
	2684	3636	74 T	S
	2684	3636	2983	3636	S
	2983	3636	6 T	S
	2983	3636	3436	3636	S
	3436	3636	66 T	S
	3436	3636	22 T	S
 % fs51: 21 11 99
	21 T	6045	3872	S
	6045	3872	11 T	S
	6045	3872	99 T	C
 % fs55: 22 67 89 21
	22 T	4392	3872	C
	4392	3872	67 T	S
	4392	3872	4923	3872	S
	4923	3872	89 T	S
	4923	3872	21 T	S
 % fs57: 23 12 63
	23 T	9323	9370	S
	9323	9370	12 T	S
	9323	9370	63 T	C
 % fs58: 24 6 43
	24 T	2983	4641	C
	2983	4641	6 T	S
	2983	4641	43 T	S
 % fs61: 27 33 54
	27 T	8995	2393	C
	8995	2393	33 T	S
	8995	2393	54 T	S
 % fs63: 29 25 18 32
	29 T	4853	447	C
	4853	447	25 T	S
	4853	447	5468	447	S
	5468	447	18 T	S
	5468	447	32 T	S
 % fs65: 34 5 93
	34 T	3473	1158	C
	3473	1158	5 T	S
	3473	1158	93 T	S
 % fs72: 39 2 37 56
	39 T	1463	5905	S
	1463	5905	2 T	S
	1463	5905	1959	5977	C
	1959	5977	37 T	S
	1959	5977	56 T	S
 % fs76: 41 82 81
	41 T	7813	883	S
	7813	883	82 T	S
	7813	883	81 T	C
 % fs82: 46 82 30
	46 T	7813	1895	C
	7813	1895	82 T	S
	7813	1895	30 T	S
 % fs90: 47 33 57
	47 T	8995	3627	C
	8995	3627	33 T	S
	8995	3627	57 T	S
 % fs100: 49 16 44 23
	49 T	7871	9370	C
	7871	9370	16 T	S
	7871	9370	8609	9370	S
	8609	9370	44 T	S
	8609	9370	23 T	S
 % fs101: 51 47 26
	51 T	8888	4604	S
	8888	4604	47 T	S
	8888	4604	26 T	C
 % fs103: 52 10 80 8
	52 T	606	6767	S
	606	6767	10 T	S
	606	6767	676	6755	C
	676	6755	80 T	S
	676	6755	8 T	S
 % fs108: 53 48 70
	53 T	3717	8398	S
	3717	8398	48 T	S
	3717	8398	70 T	C
 % fs113: 55 96 53
	55 T	2894	8398	C
	2894	8398	96 T	S
	2894	8398	53 T	S
 % fs136: 72 3 49
	72 T	6905	8418	S
	6905	8418	3 T	S
	6905	8418	49 T	C
 % fs141: 77 38 73
	77 T	8240	6114	C
	8240	6114	38 T	S
	8240	6114	73 T	S
 % fs143: 78 19 77
	78 T	7539	6620	C
	7539	6620	19 T	S
	7539	6620	77 T	S
 % fs150: 79 92 2 24
	79 T	784	4345	S
	784	4345	92 T	S
	784	4345	1463	4813	C
	1463	4813	2 T	S
	1463	4813	24 T	S
 % fs160: 83 13 36
	83 T	7952	3156	S
	7952	3156	13 T	S
	7952	3156	36 T	C
 % fs165: 90 42 72
	90 T	5927	7686	S
	5927	7686	42 T	S
	5927	7686	72 T	C
 % fs167: 91 1 28
	91 T	2894	8907	S
	2894	8907	1 T	S
	2894	8907	28 T	C
 % fs172: 94 81 58
	94 T	8073	172	C
	8073	172	81 T	S
	8073	172	58 T	S
 % fs176: 98 76 65
	98 T	5066	6538	S
	5066	6538	76 T	S
	5066	6538	65 T	C
 % fs178: 99 68 83
	99 T	6746	3156	C
	6746	3156	68 T	S
	6746	3156	83 T	S
 % fs181: 26 31 73 69
	26 T	8935	5659	S
	8935	5659	31 T	S
	8935	5659	8935	6114	S
	8935	6114	73 T	S
	8935	6114	69 T	C
 % fs194: 1 96
	1 T	96 T	S
 % fs197: 85 88
	85 T	88 T	C
 % fs201: 50 85
	50 T	85 T	C
 % fs202: 86 89
	86 T	89 T	C
 % fs204: 37 97
	37 T	97 T	C
 % fs205: 40 65
	65 T	40 T	C
 % fs209: 62 74
	62 T	74 T	C
 % fs211: 40 42
	40 T	42 T	C
 % fs219: 66 87
	87 T	66 T	C
 % fs223: 45 70
	70 T	45 T	C
 % fs236: 17 71
	71 T	17 T	C
 % fs241: 39 80
	80 T	39 T	C
 % fs250: 7 76
	76 T	7 T	C
 % fs258: 58 95
	58 T	95 T	C
 % fs260: 84 91
	84 T	91 T	C
  (Steiner Minimal Tree:  100 points,  length = 72979,  0.03 seconds)
EndPlot

% @0 
% N M Nodes LPs P1CPU P2CPU TotCPU
% @1 100 293 1 4 0.00 0.03 0.03
% Z RootZ %Gap RootLPs RootCPU RedMST
% @2 72979 72979.000000 0.00000 4 0.03 10.6515
% InitPRows InitPNZ InitLPRows InitLPNZ
% @3 331 2273 101 1508
% RootPRows RootPNZ RootLPRows RootLPNZ
% @4 389 3137 156 1880
% FinalPRows FinalPNZ FinalLPRows FinalLPNZ
% @5 389 3137 156 1880
% SMTFSTs SMTAvgFSTSz SMTMaxFSTSz #2FSTs #3FSTs ... #10FSTS #>10FSTs
% @6 52 2.903846 5 15 28 8 1 0 0 0 0 0 0