johnsdilon

SINK

 

  1 /**
  2  * @file FindSINK.java
  3  * @author zhanqingfeng
  4  * @date 2007-09-02
  5  * @description 尋找SINK
  6  *     SINK：
  7  *         由一些顶点和有向边组成的一个图，如果两个顶点x,y之间有一条路连通，则称x到y是连通的。
  8  *         对于所有顶点集合的一个子集，如果任意两点之间是连通的，则称为一个“强连通子集”。
  9  *         一个强连通子集，如果没有任何指向其他顶点的边（各个顶点有且只有一个输出方向），则称为一个“SINK”。
 10  */
 11 
 12 package src;
 13 
 14 import java.util.ArrayList;
 15 import java.util.LinkedList;
 16 
 17 public class FindSINK {
 18     
 19     /** 数据 */
 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     };
 31     
 32     /** 所有出现的点集 */
 33     private ArrayList allNodeS = new ArrayList();
 34     
 35     /** 待匹配的线集
 36      * waitLineS.* 为 LinkedList
 37      */
 38     private ArrayList waitLineS = new ArrayList();
 39     
 40     /** 匹配成功的环集
 41      * okLapS.* 为 ArrayList
 42      */
 43     private ArrayList okLapS = new ArrayList();
 44     
 45     /** 坏点集（不可能形成SINK的点集） */
 46     private ArrayList badNodeS = new ArrayList();
 47     
 48     /** 读取边数据 */
 49     private void readLine(int lineHead, int lineTail){
 50         
 51         // 获取首点
 52         Integer headInteger = new Integer(lineHead);
 53         // 获取尾点
 54         Integer tailInteger = new Integer(lineTail);
 55 
 56         // 若首点是第一次出现
 57         if (false == allNodeS.contains(headInteger)){
 58             // 添加首點至點集中
 59             allNodeS.add(headInteger);
 60         }
 61         // 若尾点是第一次出现
 62         if (false == allNodeS.contains(tailInteger)){
 63             // 添加尾點至點集中
 64             allNodeS.add(tailInteger);
 65         }        
 66         // 若首点、尾点均为第一次出现
 67         if ( (false == allNodeS.contains(headInteger))
 68                 && (false == allNodeS.contains(tailInteger)) ){
 69             // 构造一个新的线
 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;
 81             
 82             // 若坏点集不包含首点，及尾点
 83         }
 84         else{
 85             // 遍历环集中的环
 86             // 若环集中的环同时存在首点及尾点，或者存在首点，作相应处理
 87             for (int i=0; i<okLapS.size(); i++){
 88                 ArrayList okLap = (ArrayList)okLapS.get(i);
 89                  // 若环中已经存在首点，及尾点
 90                  if ( (okLap.contains(headInteger)) && (okLap.contains(tailInteger)) ){
 91                      // 若环中已经存在该边
 92                      if (okLap.indexOf(headInteger) == okLap.indexOf(tailInteger)-1){
 93                          return;
 94                          
 95                          // 若环中不存在该边
 96                      }
 97                      else{
 98                          // 置环中的点为坏点
 99                          badNodeS.addAll(okLap);
100                          // 从环中删除该环
101                          okLapS.remove(i);
102                          return;
103                      }
104                      
105                      // 若环中不同时包含首点，及尾点
106                  }
107                  else{
108                      // 若环中存在首点
109                      if (true == okLap.contains(headInteger)){
110                          // 置环中的点为坏点
111                          badNodeS.addAll(okLap);
112                          // 从环集中删除该环
113                          okLapS.remove(i);
114                          return;
115                          
116                          // 若环中不存在首点
117                      }
118                      else{
119                          continue;
120                      }
121                  }
122             }
123             // 遍历线集中的线
124             // 若线集中的线同时存在首点及尾点，或者存在二者之一，作相应处理
125             for (int i=0; i<waitLineS.size(); i++){
126                 LinkedList waitLine = (LinkedList)waitLineS.get(i);
127                 // 若线中已经存在这两点
128                 if ( (waitLine.contains(headInteger)) && (waitLine.contains(tailInteger)) ){
129                     // 若在线中，tailInteger 是 headInteger 的后续
130                     if (waitLine.indexOf(headInteger)<waitLine.indexOf(tailInteger)){
131                         // 若线中已经存在该边
132                         if (waitLine.indexOf(headInteger) == waitLine.indexOf(tailInteger)-1){
133                             return;
134                             
135                             // 若线中不存在该边
136                         }
137                         else{
138                             // 置线中 tailInteger 及其前续点为坏点，同时从线中删除这些点
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 的后续
145                     }
146                     else{
147                         // 若线的末结点是 headInteger
148                         if (headInteger.equals(waitLine.getLast())){
149                             // 置线中 tailInteger 的前续点为坏点
150                             badNodeS.addAll(waitLine.subList(0, waitLine.indexOf(tailInteger)));
151                             // 取出线中尾点（包含）至首点（包含）的线上的点，构成一个成功匹配的环
152                             ArrayList okLapNew = new ArrayList();
153                             okLapNew.addAll(waitLine.subList
154                                                     (waitLine.indexOf(tailInteger), 
155                                                             waitLine.size()));
156                             // 添加该环至环集中
157                             okLapS.add(okLapNew);
158                             // 从线集中删除该线
159                             waitLineS.remove(i);
160                             return;
161                             
162                             // 若线的末结点不是 headInteger
163                         }
164                         else{
165                             // 置线中 headInteger 及其前续点为坏点，同时从该线中删除这些点
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                         // 若首点等于该线的末结点
178                         if (headInteger.equals(waitLine.getLast())){
179                             waitLine.addLast(tailInteger);
180                             return;
181                             
182                             // 若首点不等于该线的末结点
183                         }
184                         else{
185                             // 置线中 headInteger 及其前续点为坏点，同时从该线中删除这些点
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                         // 若尾点等于该线的首结点
195                         if (tailInteger.equals(waitLine.getFirst())){
196                             waitLine.addFirst(headInteger);
197                             return;
198                             
199                             // 若尾点不等于该线的首结点
200                         }
201                         else{
202                             // 取出线中尾点及其后续的点，构成一个待匹配的线
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             // 若线集、坏点集、环集均不包含首点及尾点，或者二者之一
222             // 构造一个新的线
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     /** 读取所有的边数据 */
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     /** 输出所有的边数据 */
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      * 构造函数
265      * 读取并输出所有边数据，并输出所有的SINK
266      */
267     public FindSINK(){
268         this.readAllLine(nodeArr);
269         this.showLine(nodeArr);
270         this.showLap();
271     }
272     
273     /*
274      * 主函数
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 阅读(125) 评论(0)  编辑  收藏 所属分类: java


只有注册用户登录后才能发表评论。
网站导航:
 

导航

留言簿

文章分类

最新评论