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

50 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

%%EndSetup

 % initialize_constraint_pool: 0.00 seconds.
 % Constraint pool initialized with:
 %	1	Total degree rows	140	coeffs.
 %	50	Cutset rows		419	coeffs.
 %	0	Incompatibility rows	0	coeffs.
 %	106	2-terminal SEC rows	446	coeffs.
 %	154	Total rows in pool	51	in LP
 % @PMEM 154 rows, 1 blocks, 2868 nzfree, 0 nzwasted, 4020 nztotal
 % build_initial_formulation: 0.00 seconds.
% Resuming node 0
  % @PAP adding 51 rows, 559 nz to LP
  % @PL 51 rows, 140 cols, 699 nonzeros, 16 slack, 35 tight.
  % @PAP adding 17 rows, 73 nz to LP
  % @PL 68 rows, 140 cols, 772 nonzeros, 24 slack, 44 tight.
  % @PAP adding 9 rows, 46 nz to LP
  % @PL 77 rows, 140 cols, 818 nonzeros, 30 slack, 47 tight.
  % @PAP adding 8 rows, 30 nz to LP
  % @PL 85 rows, 140 cols, 848 nonzeros, 30 slack, 55 tight.
  % @PAP adding 3 rows, 6 nz to LP
  % @PL 88 rows, 140 cols, 854 nonzeros, 29 slack, 59 tight.
  % @PAP adding 2 rows, 6 nz to LP
  % @PL 90 rows, 140 cols, 860 nonzeros, 30 slack, 60 tight.
  % @PAP adding 2 rows, 15 nz to LP
  % @PL 92 rows, 140 cols, 875 nonzeros, 30 slack, 62 tight.
  % @PAP adding 3 rows, 12 nz to LP
  % @PL 95 rows, 140 cols, 887 nonzeros, 31 slack, 64 tight.
  % @PAP adding 3 rows, 16 nz to LP
  % @PL 98 rows, 140 cols, 903 nonzeros, 30 slack, 68 tight.
  % @PAP adding 1 rows, 5 nz to LP
  % @PL 99 rows, 140 cols, 908 nonzeros, 31 slack, 68 tight.
  % @PAP adding 1 rows, 8 nz to LP
  % @PL 100 rows, 140 cols, 916 nonzeros, 33 slack, 67 tight.
  % Node 0 LP 1 Solution, length = 49601.833333, 0.01 0
 % 16 fractional variables
 % @LO 0.01 49601.83333333333575865254 99.9000000000
 % @LN 0.01 49601.83333333333575865254 99.9000000000
 % @UO 0.01 51831.00000000000000000000 4.3008366936
 % @UN 0.01 51831.00000000000000000000 4.3008366936
 % @cutset: 4 connected components.
 % initially 15 congested vertices:
 % find_congested_components found 3 components:
 %	component 0:	4 verts,	5 edges
 %	component 1:	7 verts,	10 edges
 %	component 2:	3 verts,	3 edges
 % @D deleting 33 slack rows
  % @PAP adding 48 rows, 895 nz to LP
 % @PMEM 202 rows, 1 blocks, 1925 nzfree, 0 nzwasted, 4020 nztotal
  % @PL 115 rows, 140 cols, 1558 nonzeros, 21 slack, 94 tight.
  % @PAP adding 2 rows, 6 nz to LP
  % @PL 117 rows, 140 cols, 1564 nonzeros, 5 slack, 112 tight.
  % @PAP adding 1 rows, 4 nz to LP
  % @PL 118 rows, 140 cols, 1568 nonzeros, 7 slack, 111 tight.
  % Node 0 LP 2 Solution, length = 51063.000000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 48
 % 10 fractional variables
 % @LO 0.01 49601.83333333333575865254 4.3008366936
 % @LN 0.01 51063.00000000000000000000 1.4817387278
 % @UO 0.01 51831.00000000000000000000 1.4817387278
 % @UN 0.01 51595.00000000000000000000 1.0311076655
 % Fixed 10 vars to 0 and 3 vars to 1.
 % initially 14 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	3 verts,	4 edges
 %	component 1:	3 verts,	3 edges
 % @D deleting 7 slack rows
  % @PAP adding 2 rows, 14 nz to LP
 % @PMEM 204 rows, 1 blocks, 1909 nzfree, 0 nzwasted, 4020 nztotal
  % @PL 113 rows, 140 cols, 1478 nonzeros, 3 slack, 110 tight.
  % Node 0 LP 3 Solution, length = 51277.000000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 2
 % 6 fractional variables
 % @LO 0.01 51063.00000000000000000000 1.0311076655
 % @LN 0.01 51277.00000000000000000000 0.6163387925
 % Fixed 11 vars to 0 and 1 vars to 1.
 % initially 4 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	4 verts,	5 edges
 % @D deleting 3 slack rows
  % @PAP adding 1 rows, 7 nz to LP
 % @PMEM 205 rows, 1 blocks, 1901 nzfree, 0 nzwasted, 4020 nztotal
  % @PL 111 rows, 140 cols, 1444 nonzeros, 2 slack, 109 tight.
  % @PAP adding 3 rows, 14 nz to LP
  % @PL 114 rows, 140 cols, 1458 nonzeros, 1 slack, 113 tight.
  % Node 0 LP 4 Solution, length = 51294.000000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 1
 % 0 fractional variables
 % @LO 0.01 51277.00000000000000000000 0.6163387925
 % @LN 0.01 51294.00000000000000000000 0.5833898634
 % @cutset: 2 connected components.
 % initially 3 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	3 verts,	3 edges
 % @D deleting 1 slack rows
  % @PAP adding 2 rows, 30 nz to LP
 % @PMEM 207 rows, 1 blocks, 1869 nzfree, 0 nzwasted, 4020 nztotal
  % @PL 115 rows, 140 cols, 1476 nonzeros, 5 slack, 110 tight.
  % @PAP adding 5 rows, 55 nz to LP
  % @PL 120 rows, 140 cols, 1531 nonzeros, 1 slack, 119 tight.
  % Node 0 LP 5 Solution, length = 51595.000000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 2
  %       0     0        cutoff    51595.0000
 % @LO 0.01 51294.00000000000000000000 0.5833898634
 % @LN 0.01 51595.00000000000000000000 0.0000000000

 % Certificate of solution:
 % @C	2920	9381
 % @C	6045	4811
 % @C	7970	2547
 % @C	8222	2389
 % @C	1857	1630
 % @C	1875	1432
 % @C	3221	1432
 % @C	2983	3671
 % @C	3221	3636
 % @C	2983	4641
 % @C	4853	447
 % @C	5468	447
 % @C	7539	6048
 % @C	8888	3322
 % @C	8935	5659
 % @C	1463	5905
 % @C	6905	7473
 % @C	8823	9286
 % @C	7741	1895
 % @C	4558	7473
 % @C	5779	7473
 % @C	7871	9300
%%Page: 1 1
BeginPlot
	Plot_Terminals
 % fs3: 1 28 45
	1 T	2920	9381	C
	2920	9381	28 T	S
	2920	9381	45 T	S
 % fs22: 7 11 15
	7 T	6045	4811	C
	6045	4811	11 T	S
	6045	4811	15 T	S
 % fs28: 13 36 30 27
	13 T	7970	2547	S
	7970	2547	36 T	S
	7970	2547	8222	2389	C
	8222	2389	30 T	S
	8222	2389	27 T	S
 % fs35: 17 0 9 4 34
	17 T	1857	1630	S
	1857	1630	0 T	S
	1857	1630	1875	1432	C
	1875	1432	9 T	S
	1875	1432	3221	1432	S
	3221	1432	4 T	S
	3221	1432	34 T	S
 % fs39: 20 6 4 22
	20 T	2983	3671	S
	2983	3671	6 T	S
	2983	3671	3221	3636	C
	3221	3636	4 T	S
	3221	3636	22 T	S
 % fs44: 24 6 43
	24 T	2983	4641	C
	2983	4641	6 T	S
	2983	4641	43 T	S
 % fs48: 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
 % fs49: 35 19 38
	35 T	7539	6048	C
	7539	6048	19 T	S
	7539	6048	38 T	S
 % fs54: 36 47 33
	36 T	8888	3322	C
	8888	3322	47 T	S
	8888	3322	33 T	S
 % fs57: 38 26 31
	38 T	8935	5659	C
	8935	5659	26 T	S
	8935	5659	31 T	S
 % fs58: 39 2 37
	39 T	1463	5905	S
	1463	5905	2 T	S
	1463	5905	37 T	C
 % fs61: 42 3 19
	42 T	6905	7473	S
	6905	7473	3 T	S
	6905	7473	19 T	C
 % fs62: 44 23 12
	44 T	8823	9286	S
	8823	9286	23 T	S
	8823	9286	12 T	C
 % fs63: 46 41 30
	46 T	7741	1895	C
	7741	1895	41 T	S
	7741	1895	30 T	S
 % fs73: 48 45 40 42
	48 T	4558	7473	C
	4558	7473	45 T	S
	4558	7473	5779	7473	S
	5779	7473	40 T	S
	5779	7473	42 T	S
 % fs79: 49 16 44
	49 T	7871	9300	S
	7871	9300	16 T	S
	7871	9300	44 T	C
 % fs104: 5 34
	34 T	5 T	C
 % fs105: 26 47
	47 T	26 T	C
 % fs107: 10 14
	14 T	10 T	C
 % fs108: 11 21
	21 T	11 T	C
 % fs110: 8 39
	8 T	39 T	C
 % fs111: 15 35
	15 T	35 T	C
 % fs112: 8 10
	10 T	8 T	C
 % fs115: 2 24
	2 T	24 T	C
 % fs117: 5 29
	5 T	29 T	C
 % fs120: 3 49
	3 T	49 T	C
 % fs128: 21 22
	22 T	21 T	C
  (Steiner Minimal Tree:  50 points,  length = 51595,  0.01 seconds)
EndPlot

% @0 
% N M Nodes LPs P1CPU P2CPU TotCPU
% @1 50 140 1 5 0.00 0.01 0.01
% Z RootZ %Gap RootLPs RootCPU RedMST
% @2 51595 (51595.000000) 0.00000 5 0.01 10.4891
% InitPRows InitPNZ InitLPRows InitLPNZ
% @3 154 998 51 699
% RootPRows RootPNZ RootLPRows RootLPNZ
% @4 207 1944 120 1531
% FinalPRows FinalPNZ FinalLPRows FinalLPNZ
% @5 207 1944 120 1531
% SMTFSTs SMTAvgFSTSz SMTMaxFSTSz #2FSTs #3FSTs ... #10FSTS #>10FSTs
% @6 27 2.814815 5 11 11 4 1 0 0 0 0 0 0