rsmt200.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.02 seconds

%%BeginSetup

0 10000 0 10000 SetAxes

200 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
	2643	6261	DT
	4704	7644	DT
	1363	3820	DT
	3156	4019	DT
	8413	5866	DT
	8040	4713	DT
	6147	7878	DT
	4272	8595	DT
	9058	1440	DT
	6460	1645	DT
	5821	9743	DT
	9182	4040	DT
	3520	9039	DT
	4592	5876	DT
	2535	6181	DT
	6411	7863	DT
	5360	281	DT
	885	3082	DT
	9005	9739	DT
	3077	7573	DT
	8832	6327	DT
	3594	7641	DT
	2370	3125	DT
	6563	4337	DT
	6104	7017	DT
	9571	6887	DT
	2246	4107	DT
	6650	2485	DT
	269	7510	DT
	3584	3889	DT
	4883	87	DT
	419	1878	DT
	8122	2489	DT
	8623	8722	DT
	2071	266	DT
	367	1127	DT
	7749	9472	DT
	7447	654	DT
	178	3414	DT
	9665	3534	DT
	8889	9622	DT
	1103	4661	DT
	508	8482	DT
	731	9452	DT
	9129	598	DT
	2726	8714	DT
	1324	2380	DT
	4862	1267	DT
	4210	8839	DT
	2489	684	DT
	2201	2140	DT
	2379	9488	DT
	7018	3643	DT
	9113	2349	DT
	5310	7647	DT
	5981	8787	DT
	5094	8384	DT
	3497	2095	DT
	7046	1110	DT
	5910	6658	DT
	223	7807	DT
	8583	9828	DT
	7371	1529	DT
	5383	7632	DT
	7943	8383	DT
	8634	6223	DT
	9334	864	DT
	8807	4244	DT
	641	713	DT
	6384	1784	DT
	5952	2973	DT
	8227	172	DT
	461	3812	DT
	6921	5779	DT
	6121	4015	DT
	5754	4492	DT
	939	4135	DT
	9480	6939	DT
	7627	1458	DT
	9464	1350	DT
	2465	6698	DT
	9389	4524	DT
	2830	7903	DT
	8201	5081	DT
	246	126	DT
	5959	188	DT
	5552	7956	DT
	364	6688	DT
	6631	6595	DT
	4831	8043	DT
	9211	4941	DT
	6510	8272	DT
	2162	9596	DT
	3429	666	DT
	9220	1013	DT
	652	1935	DT
	1439	893	DT
	5512	1849	DT
	1318	6163	DT
	7721	2950	DT

%%EndSetup

 % initialize_constraint_pool: 0.01 seconds.
 % Constraint pool initialized with:
 %	1	Total degree rows	807	coeffs.
 %	200	Cutset rows		2897	coeffs.
 %	0	Incompatibility rows	0	coeffs.
 %	761	2-terminal SEC rows	4646	coeffs.
 %	843	Total rows in pool	201	in LP
 % @PMEM 843 rows, 1 blocks, 24733 nzfree, 0 nzwasted, 33400 nztotal
 % build_initial_formulation: 0.00 seconds.
% Resuming node 0
  % @PAP adding 201 rows, 3704 nz to LP
  % @PL 201 rows, 807 cols, 4511 nonzeros, 75 slack, 126 tight.
  % @PAP adding 45 rows, 237 nz to LP
  % @PL 246 rows, 807 cols, 4748 nonzeros, 68 slack, 178 tight.
  % @PAP adding 36 rows, 222 nz to LP
  % @PL 282 rows, 807 cols, 4970 nonzeros, 80 slack, 202 tight.
  % @PAP adding 33 rows, 201 nz to LP
  % @PL 315 rows, 807 cols, 5171 nonzeros, 91 slack, 224 tight.
  % @PAP adding 24 rows, 193 nz to LP
  % @PL 339 rows, 807 cols, 5364 nonzeros, 98 slack, 241 tight.
  % @PAP adding 15 rows, 99 nz to LP
  % @PL 354 rows, 807 cols, 5463 nonzeros, 100 slack, 254 tight.
  % @PAP adding 14 rows, 163 nz to LP
  % @PL 368 rows, 807 cols, 5626 nonzeros, 100 slack, 268 tight.
  % @PAP adding 8 rows, 85 nz to LP
  % @PL 376 rows, 807 cols, 5711 nonzeros, 105 slack, 271 tight.
  % @PAP adding 4 rows, 37 nz to LP
  % @PL 380 rows, 807 cols, 5748 nonzeros, 108 slack, 272 tight.
  % @PAP adding 2 rows, 11 nz to LP
  % @PL 382 rows, 807 cols, 5759 nonzeros, 106 slack, 276 tight.
  % @PAP adding 1 rows, 14 nz to LP
  % @PL 383 rows, 807 cols, 5773 nonzeros, 107 slack, 276 tight.
  % Node 0 LP 1 Solution, length = 96811.833333, 0.07 0
 % 24 fractional variables
 % @LO 0.08 96811.83333333332848269492 99.9000000000
 % @LN 0.08 96811.83333333332848269492 99.9000000000
 % @UO 0.08 107799.00000000000000000000 10.1922714187
 % @UN 0.08 107799.00000000000000000000 10.1922714187
 % @cutset: 24 connected components.
 % initially 71 congested vertices:
 % find_congested_components found 14 components:
 %	component 0:	5 verts,	4 edges
 %	component 1:	4 verts,	4 edges
 %	component 2:	3 verts,	3 edges
 %	component 3:	13 verts,	17 edges
 %	component 4:	3 verts,	3 edges
 %	component 5:	6 verts,	8 edges
 %	component 6:	3 verts,	3 edges
 %	component 7:	5 verts,	5 edges
 %	component 8:	3 verts,	3 edges
 %	component 9:	3 verts,	3 edges
 %	component 10:	5 verts,	5 edges
 %	component 11:	6 verts,	5 edges
 %	component 12:	3 verts,	3 edges
 %	component 13:	3 verts,	3 edges
 % Enumerating 13 congested vertices.
 % @D deleting 107 slack rows
  % @PAP adding 108 rows, 2235 nz to LP
 % @PMEM 951 rows, 1 blocks, 22390 nzfree, 0 nzwasted, 33400 nztotal
  % @PL 384 rows, 807 cols, 6463 nonzeros, 59 slack, 325 tight.
  % @PAP adding 12 rows, 118 nz to LP
  % @PL 396 rows, 807 cols, 6581 nonzeros, 59 slack, 337 tight.
  % @PAP adding 7 rows, 48 nz to LP
  % @PL 403 rows, 807 cols, 6629 nonzeros, 61 slack, 342 tight.
  % @PAP adding 7 rows, 38 nz to LP
  % @PL 410 rows, 807 cols, 6667 nonzeros, 62 slack, 348 tight.
  % @PAP adding 6 rows, 44 nz to LP
  % @PL 416 rows, 807 cols, 6711 nonzeros, 68 slack, 348 tight.
  % @PAP adding 5 rows, 40 nz to LP
  % @PL 421 rows, 807 cols, 6751 nonzeros, 63 slack, 358 tight.
  % @PAP adding 2 rows, 21 nz to LP