亚洲区欧美区,3dmax动漫人物在线看,91系列在线观看

SINK

1 /**

2 * @file FindSINK.java

3 * @author zhanqingfeng

4 * @date 2007-09-02

5 * @description 尋找SINK

6 * SINK：

7 * 由一些頂點和有向邊組成的一個圖，如果兩個頂點x,y之間有一條路連通，則稱x到y(tǒng)是連通的。

8 * 對于所有頂點集合的一個子集，如果任意兩點之間是連通的，則稱為一個“強連通子集”。

9 * 一個強連通子集，如果沒有任何指向其他頂點的邊（各個頂點有且只有一個輸出方向），則稱為一個“SINK”。

10 */

12 package src;

14 import java.util.ArrayList;

15 import java.util.LinkedList;

17 public class FindSINK {

19 /** 數(shù)據(jù) */

20 private final int[][] nodeArr = {

21 { 1, 2 },

22 { 2, 6 },

23 { 6, 1 },

24 { 3, 5 },

25 { 5, 4 },

26 { 4, 1 },

27 { 7, 8 },

28 { 8, 7 },

29 { 8, 6 }

30 };

32 /** 所有出現(xiàn)的點集 */

33 private ArrayList allNodeS = new ArrayList();

35 /** 待匹配的線集

36 * waitLineS.* 為 LinkedList

37 */

38 private ArrayList waitLineS = new ArrayList();

40 /** 匹配成功的環(huán)集

41 * okLapS.* 為 ArrayList

42 */

43 private ArrayList okLapS = new ArrayList();

45 /** 壞點集（不可能形成SINK的點集） */

46 private ArrayList badNodeS = new ArrayList();

48 /** 讀取邊數(shù)據(jù) */

49 private void readLine(int lineHead, int lineTail){

51 // 獲取首點

52 Integer headInteger = new Integer(lineHead);

53 // 獲取尾點

54 Integer tailInteger = new Integer(lineTail);

56 // 若首點是第一次出現(xiàn)

57 if (false == allNodeS.contains(headInteger)){

58 // 添加首點至點集中

59 allNodeS.add(headInteger);

60 }

61 // 若尾點是第一次出現(xiàn)

62 if (false == allNodeS.contains(tailInteger)){

63 // 添加尾點至點集中

64 allNodeS.add(tailInteger);

65 }

66 // 若首點、尾點均為第一次出現(xiàn)

67 if ( (false == allNodeS.contains(headInteger))

68 && (false == allNodeS.contains(tailInteger)) ){

69 // 構(gòu)造一個新的線

70 LinkedList waitLineNew = new LinkedList();

71 waitLineNew.add(headInteger);

72 waitLineNew.add(tailInteger);

73 // 添加該新線至線集中

74 this.waitLineS.add(waitLineNew);

75 return;

76 }

77 // 若壞點集包含首點，或者尾點

78 if ( (badNodeS.contains(headInteger))

79 || (badNodeS.contains(tailInteger)) ){

80 return;

82 // 若壞點集不包含首點，及尾點

83 }

84 else{

85 // 遍歷環(huán)集中的環(huán)

86 // 若環(huán)集中的環(huán)同時存在首點及尾點，或者存在首點，作相應(yīng)處理

87 for (int i=0; i<okLapS.size(); i++){

88 ArrayList okLap = (ArrayList)okLapS.get(i);

89 // 若環(huán)中已經(jīng)存在首點，及尾點

90 if ( (okLap.contains(headInteger)) && (okLap.contains(tailInteger)) ){

91 // 若環(huán)中已經(jīng)存在該邊

92 if (okLap.indexOf(headInteger) == okLap.indexOf(tailInteger)-1){

93 return;

95 // 若環(huán)中不存在該邊

96 }

97 else{

98 // 置環(huán)中的點為壞點

99 badNodeS.addAll(okLap);

100 // 從環(huán)中刪除該環(huán)

101 okLapS.remove(i);

102 return;

103 }

104

105 // 若環(huán)中不同時包含首點，及尾點

106 }

107 else{

108 // 若環(huán)中存在首點

109 if (true == okLap.contains(headInteger)){

110 // 置環(huán)中的點為壞點

111 badNodeS.addAll(okLap);

112 // 從環(huán)集中刪除該環(huán)

113 okLapS.remove(i);

114 return;

115

116 // 若環(huán)中不存在首點

117 }

118 else{

119 continue;

120 }

121 }

122 }

123 // 遍歷線集中的線

124 // 若線集中的線同時存在首點及尾點，或者存在二者之一，作相應(yīng)處理

125 for (int i=0; i<waitLineS.size(); i++){

126 LinkedList waitLine = (LinkedList)waitLineS.get(i);

127 // 若線中已經(jīng)存在這兩點

128 if ( (waitLine.contains(headInteger)) && (waitLine.contains(tailInteger)) ){

129 // 若在線中，tailInteger 是 headInteger 的后續(xù)

130 if (waitLine.indexOf(headInteger)<waitLine.indexOf(tailInteger)){

131 // 若線中已經(jīng)存在該邊

132 if (waitLine.indexOf(headInteger) == waitLine.indexOf(tailInteger)-1){

133 return;

134

135 // 若線中不存在該邊

136 }

137 else{

138 // 置線中 tailInteger 及其前續(xù)點為壞點，同時從線中刪除這些點

139 badNodeS.addAll(waitLine.subList(0, waitLine.indexOf(tailInteger)+1));

140 waitLine.removeAll(waitLine.subList(0, waitLine.indexOf(tailInteger)+1));

141 return;

142 }

143

144 // 若在線中， tailInteger 不是 headInteger 的后續(xù)

145 }

146 else{

147 // 若線的末結(jié)點是 headInteger

148 if (headInteger.equals(waitLine.getLast())){

149 // 置線中 tailInteger 的前續(xù)點為壞點

150 badNodeS.addAll(waitLine.subList(0, waitLine.indexOf(tailInteger)));

151 // 取出線中尾點（包含）至首點（包含）的線上的點，構(gòu)成一個成功匹配的環(huán)

152 ArrayList okLapNew = new ArrayList();

153 okLapNew.addAll(waitLine.subList

154 (waitLine.indexOf(tailInteger),

155 waitLine.size()));

156 // 添加該環(huán)至環(huán)集中

157 okLapS.add(okLapNew);

158 // 從線集中刪除該線

159 waitLineS.remove(i);

160 return;

161

162 // 若線的末結(jié)點不是 headInteger

163 }

164 else{

165 // 置線中 headInteger 及其前續(xù)點為壞點，同時從該線中刪除這些點

166 badNodeS.addAll(waitLine.subList(0, waitLine.indexOf(headInteger)+1));

167 waitLine.removeAll(waitLine.subList(0, waitLine.indexOf(headInteger)+1));

168 return;

169 }

170 }

171

172 // 若線中不同時包含首點，及尾點

173 }

174 else{

175 // 若線中存在首點

176 if (waitLine.contains(headInteger)){

177 // 若首點等于該線的末結(jié)點

178 if (headInteger.equals(waitLine.getLast())){

179 waitLine.addLast(tailInteger);

180 return;

181

182 // 若首點不等于該線的末結(jié)點

183 }

184 else{

185 // 置線中 headInteger 及其前續(xù)點為壞點，同時從該線中刪除這些點

186 badNodeS.add(waitLine.subList(0, waitLine.indexOf(headInteger)+1));

187 waitLine.removeAll(waitLine.subList(0, waitLine.indexOf(headInteger)+1));

188 return;

189 }

190

191 // 若線中存在尾點

192 }

193 else if (waitLine.contains(tailInteger)){

194 // 若尾點等于該線的首結(jié)點

195 if (tailInteger.equals(waitLine.getFirst())){

196 waitLine.addFirst(headInteger);

197 return;

198

199 // 若尾點不等于該線的首結(jié)點

200 }

201 else{

202 // 取出線中尾點及其后續(xù)的點，構(gòu)成一個待匹配的線

203 LinkedList waitLineNew = new LinkedList();

204 waitLineNew.addAll(waitLine.subList

205 (waitLine.indexOf(tailInteger),

206 waitLine.size()));

207 // 將首點插入該新線的開始

208 waitLineNew.addFirst(headInteger);

209 // 將該新線添加至線集中

210 waitLineS.add(waitLineNew);

211 return;

212 }

213

214 // 若線中不存在首點，及尾點

215 }

216 else{

217 continue;

218 }

219 }

220 }

221 // 若線集、壞點集、環(huán)集均不包含首點及尾點，或者二者之一

222 // 構(gòu)造一個新的線

223 LinkedList waitLineNew = new LinkedList();

224 waitLineNew.add(headInteger);

225 waitLineNew.add(tailInteger);

226 // 添加該新線至線集中

227 this.waitLineS.add(waitLineNew);

228 return;

229 }

230 }

231

232 /** 讀取所有的邊數(shù)據(jù) */

233 private void readAllLine(int[][] arr){

234 for (int i=0; i<arr.length; i++){

235 this.readLine(arr[i][0], arr[i][1]);

236 }

237 }

238

239 /** 輸出所有的邊數(shù)據(jù) */

240 private void showLine(int[][] arr){

241 System.out.println("All the lines input:");

242 for (int i=0; i<arr.length; i++){

243 System.out.println(arr[i][0] + " , " + arr[i][1]);

244 }

245 }

246

247 /** 輸出所有的SINK */

248 private void showLap(){

249 System.out.println();

250 System.out.println("All the SINK:");

251 for (int i=0; i<okLapS.size(); i++){

252 ArrayList okLapOut = (ArrayList)okLapS.get(i);

253 for (int j=0; j<okLapOut.size(); j++){

254 System.out.print(okLapOut.get(j).toString());

255 if (okLapOut.size()-1 > j){

256 System.out.print(" , ");

257 }

258 }

259 System.out.println();

260 }

261 }

262

263 /**

264 * 構(gòu)造函數(shù)

265 * 讀取并輸出所有邊數(shù)據(jù)，并輸出所有的SINK

266 */

267 public FindSINK(){

268 this.readAllLine(nodeArr);

269 this.showLine(nodeArr);

270 this.showLap();

271 }

272

273 /*

274 * 主函數(shù)

275 */

276 public static void main(String[] args){

277 FindSINK obj = new FindSINK();

278 }

279

280 }

281

282

posted on 2007-12-22 22:20 johnsdilon 閱讀(132) 評論(0) 編輯收藏所屬分類: java

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理

johnsdilon

SINK

導(dǎo)航

留言簿

文章分類

最新評論