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

8 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

%%EndSetup

 % initialize_constraint_pool: 0.00 seconds.
 % Constraint pool initialized with:
 %	1	Total degree rows	16	coeffs.
 %	8	Cutset rows		42	coeffs.
 %	0	Incompatibility rows	0	coeffs.
 %	11	2-terminal SEC rows	34	coeffs.
 %	20	Total rows in pool	9	in LP
 % @PMEM 20 rows, 1 blocks, 256 nzfree, 0 nzwasted, 368 nztotal
 % build_initial_formulation: 0.00 seconds.
% Resuming node 0
  % @PAP adding 9 rows, 58 nz to LP
  % @PL 9 rows, 16 cols, 74 nonzeros, 3 slack, 6 tight.
  % @PAP adding 1 rows, 2 nz to LP
  % @PL 10 rows, 16 cols, 76 nonzeros, 2 slack, 8 tight.
  % @PAP adding 1 rows, 3 nz to LP
  % @PL 11 rows, 16 cols, 79 nonzeros, 3 slack, 8 tight.
  % @PAP adding 1 rows, 2 nz to LP
  % @PL 12 rows, 16 cols, 81 nonzeros, 4 slack, 8 tight.
  % @PAP adding 1 rows, 5 nz to LP
  % @PL 13 rows, 16 cols, 86 nonzeros, 3 slack, 10 tight.
  % Node 0 LP 1 Solution, length = 16991.000000, 0.00 0
 % 0 fractional variables
 % @LO 0.00 16991.00000000000000000000 99.9000000000
 % @LN 0.00 16991.00000000000000000000 99.9000000000
 % @UO 0.00 17693.00000000000000000000 3.9676708303
 % @UN 0.00 17693.00000000000000000000 3.9676708303
 % Fixed 1 vars to 0 and 0 vars to 1.
 % @cutset: 2 connected components.
 % initially 3 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	3 verts,	3 edges
 % @D deleting 3 slack rows
  % @PAP adding 2 rows, 12 nz to LP
 % @PMEM 22 rows, 1 blocks, 242 nzfree, 0 nzwasted, 368 nztotal
  % @PL 12 rows, 16 cols, 80 nonzeros, 1 slack, 11 tight.
  % Node 0 LP 2 Solution, length = 17693.000000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 2
  %       0     0        cutoff    17693.0000
 % @LO 0.00 16991.00000000000000000000 3.9676708303
 % @LN 0.00 17693.00000000000000000000 0.0000000000

 % Certificate of solution:
 % @C	2983	2738
 % @C	5486	8268
 % @C	2983	5183
%%Page: 1 1
BeginPlot
	Plot_Terminals
 % fs0: 0 6 4
	0 T	2983	2738	S
	2983	2738	6 T	S
	2983	2738	4 T	C
 % fs2: 1 7 3
	1 T	5486	8268	C
	5486	8268	7 T	S
	5486	8268	3 T	S
 % fs7: 2 6 7
	2 T	2983	5183	S
	2983	5183	6 T	S
	2983	5183	7 T	C
 % fs11: 4 5
	4 T	5 T	C
  (Steiner Minimal Tree:  8 points,  length = 17693,  0.00 seconds)
EndPlot

% @0 
% N M Nodes LPs P1CPU P2CPU TotCPU
% @1 8 16 1 2 0.00 0.00 0.00
% Z RootZ %Gap RootLPs RootCPU RedMST
% @2 17693 (17693.000000) 0.00000 2 0.00 14.8105
% InitPRows InitPNZ InitLPRows InitLPNZ
% @3 20 92 9 74
% RootPRows RootPNZ RootLPRows RootLPNZ
% @4 22 104 12 80
% FinalPRows FinalPNZ FinalLPRows FinalLPNZ
% @5 22 104 12 80
% SMTFSTs SMTAvgFSTSz SMTMaxFSTSz #2FSTs #3FSTs ... #10FSTS #>10FSTs
% @6 4 2.750000 3 1 3 0 0 0 0 0 0 0 0