程式扎記: [ Data Structures with Java ] Section 24.2 : Creating and Using Graphs - Example 24.1

標籤

2011年4月27日 星期三

[ Data Structures with Java ] Section 24.2 : Creating and Using Graphs - Example 24.1


The example creates an empty graph and uses readGraph() with the file samplegraph.dat to load the vertices, edges and weights. An output statement uses toString() to display the graph. The following is a listing of the file with an accompanying picture of the graph :

- File samplegraph.dat :
// data for the vertices
A B C D E
// data for the edges
A B 3
A C 2
B C 6
C B 4
C D 1
E B 5

Here we create a class JGraph which implements Graph interface to carry out the example here :
- JGraph.java :
  1. package DSwJ.S24;  
  2.   
  3. import java.io.BufferedReader;  
  4. import java.io.File;  
  5. import java.io.FileReader;  
  6. import java.util.ArrayList;  
  7. import java.util.HashSet;  
  8. import java.util.Iterator;  
  9. import java.util.List;  
  10. import java.util.Set;  
  11. import java.util.TreeMap;  
  12.   
  13. import DSwJ.S24.sub.Edge;  
  14.   
  15. public class JGraph implements Graph{  
  16.     private TreeMap>> vertexTable;  
  17.       
  18.     public JGraph(){vertexTable = new TreeMap>>();}  
  19.       
  20.     public static JGraph readGraph(String fn) {  
  21.         JGraph graph = new JGraph();  
  22.         File graphFile = new File(fn);  
  23.         int vertexCnt = 0;  
  24.         int edgeCnt = 0;  
  25.         if(graphFile.exists()) {  
  26.             try{  
  27.                 BufferedReader br = new BufferedReader(new FileReader(graphFile));  
  28.                 String line;  
  29.                 if((line=br.readLine())!=null) { //Read vertex count                      
  30.                     vertexCnt = Integer.valueOf(line.trim());  
  31.                     //System.out.println("Vertex Cnt="+vertexCnt+"...");  
  32.                 } else return null;  
  33.                 if((line=br.readLine())!=null) { //Read vertex set  
  34.                     String[] vertexSet = line.split(" ");  
  35.                     vertexCnt = vertexCnt>vertexSet.length?vertexSet.length:vertexCnt;  
  36.                     for(int i=0; i
  37.                         //System.out.println("Add Vertex("+vertexSet[i]+")");  
  38.                         graph.addVertex(vertexSet[i].trim());                     
  39.                     }                     
  40.                 } else return null;  
  41.                 if((line=br.readLine())!=null) { //Read edge count  
  42.                     edgeCnt = Integer.valueOf(line);      
  43.                 } else return null;  
  44.                 while((line=br.readLine())!=null && edgeCnt>0) {  
  45.                     String[] edgeSet = line.split(" ");  
  46.                     if(edgeSet.length==3) {  
  47.                         graph.addEdge(edgeSet[0].trim(), edgeSet[1].trim(), Integer.valueOf(edgeSet[2]));  
  48.                     }  
  49.                     edgeCnt--;  
  50.                 }  
  51.                 br.close();  
  52.             }catch(Exception e){e.printStackTrace(); return null;}  
  53.         }  
  54.         return graph;  
  55.     }  
  56.   
  57.     @Override  
  58.     public boolean addEdge(Object v1, Object v2, int w) {  
  59.         if(vertexTable.containsKey(v1) && vertexTable.containsKey(v2)) {  
  60.             return vertexTable.get(v1).add(new Edge((T)v1, (T)v2, w));  
  61.         }  
  62.         throw new java.lang.IllegalArgumentException("JGraph(addEdge): Vertices "+v1+" or "+v2+" doesn't exist");  
  63.     }  
  64.   
  65.     @Override  
  66.     public boolean addVertex(Object v) {  
  67.         if(!vertexTable.containsKey(v)){  
  68.             vertexTable.put((T)v, new ArrayList>());  
  69.             return true;  
  70.         }  
  71.         return false;  
  72.     }  
  73.   
  74.     @Override  
  75.     public void clear() {  
  76.         vertexTable.clear();  
  77.     }  
  78.   
  79.     @Override  
  80.     public boolean containsEdge(Object v1, Object v2) {  
  81.         if(vertexTable.containsKey(v1) && vertexTable.containsKey(v2)) {  
  82.             ArrayList> list = vertexTable.get(v1);  
  83.             if(list!=null) {  
  84.                 Iterator> iter = list.iterator();  
  85.                 while(iter.hasNext()) {  
  86.                     Edge e = iter.next();  
  87.                     if(e.dest.equals(v2)) return true;  
  88.                 }  
  89.             }  
  90.             return false;  
  91.         }  
  92.         throw new java.lang.IllegalArgumentException("JGraph(containsEdge): Vertices "+v1+" or "+v2+" doesn't exist");  
  93.     }  
  94.   
  95.     @Override  
  96.     public boolean containsVertex(Object v) {  
  97.         return vertexTable.containsKey(v);  
  98.     }  
  99.   
  100.     @Override  
  101.     public Set getNeighbors(Object v) {  
  102.         if(vertexTable.containsKey(v)) {  
  103.             HashSet neighborSet = new HashSet();    
  104.             return neighborSet;  
  105.         }         
  106.         throw new java.lang.IllegalArgumentException("JGraph(containsEdge): Vertex "+v+" doesn't exist");  
  107.     }  
  108.   
  109.     @Override  
  110.     public int getWeight(Object v1, Object v2) {  
  111.         if(vertexTable.containsKey(v1) && vertexTable.containsKey(v2)) {  
  112.             List> list = vertexTable.get(v1);  
  113.             if(list!=null) {  
  114.                 Iterator> iter = list.iterator();  
  115.                 while(iter.hasNext()) {  
  116.                     Edge e = iter.next();  
  117.                     if(e.dest.equals(v2)) return e.weight;  
  118.                 }  
  119.             }  
  120.             return -1;  
  121.         }  
  122.         throw new java.lang.IllegalArgumentException("JGraph(getWeight): Vertices "+v1+" or "+v2+" doesn't exist");  
  123.     }  
  124.   
  125.     @Override  
  126.     public boolean isEmpty() {  
  127.         return vertexTable.isEmpty();  
  128.     }  
  129.   
  130.     @Override  
  131.     public int numberOfEdges() {  
  132.         int total=0;  
  133.         Set keySet = vertexTable.keySet();  
  134.         Iterator iter = keySet.iterator();  
  135.         while(iter.hasNext()) {  
  136.             total+=vertexTable.get(iter.next()).size();  
  137.         }  
  138.         return total;  
  139.     }  
  140.   
  141.     @Override  
  142.     public int numberOfVertices() {  
  143.         return vertexTable.size();  
  144.     }  
  145.   
  146.     @Override  
  147.     public boolean removeEdge(Object v1, Object v2) {  
  148.         if(vertexTable.containsKey(v1) && vertexTable.containsKey(v2)) {  
  149.             List> list = vertexTable.get(v1);  
  150.             if(list!=null) {  
  151.                 Iterator> iter = list.iterator();  
  152.                 while(iter.hasNext()) {  
  153.                     Edge e = iter.next();  
  154.                     if(e.dest.equals(v2)){  
  155.                         return list.remove(e);  
  156.                     }  
  157.                 }  
  158.             }  
  159.             return false;  
  160.         }  
  161.         throw new java.lang.IllegalArgumentException("JGraph(removeEdge): Vertices "+v1+" or "+v2+" doesn't exist");  
  162.     }  
  163.   
  164.     @Override  
  165.     public boolean removeVertex(Object v) {  
  166.         if(vertexTable.remove(v)!=nullreturn true;  
  167.         return false;  
  168.     }  
  169.   
  170.     @Override  
  171.     public int setWeight(Object v1, Object v2, int w) {  
  172.         if(vertexTable.containsKey(v1) && vertexTable.containsKey(v2)) {  
  173.             List> list = vertexTable.get(v1);  
  174.             if(list!=null) {  
  175.                 Iterator> iter = list.iterator();  
  176.                 while(iter.hasNext()) {  
  177.                     Edge e = iter.next();  
  178.                     if(e.dest.equals(v2)){  
  179.                         int prevW =  e.weight;  
  180.                         e.weight = w;  
  181.                         return prevW;  
  182.                     }  
  183.                 }  
  184.             }  
  185.             return -1;  
  186.         }  
  187.         throw new java.lang.IllegalArgumentException("JGraph(setWeight): Vertices "+v1+" or "+v2+" doesn't exist");  
  188.     }  
  189.   
  190.     @Override  
  191.     public Set vertexSet() {          
  192.         return vertexTable.keySet();  
  193.     }  
  194.       
  195.     public int outDegree(T vertex) {  
  196.         if(vertexTable.containsKey(vertex)) {  
  197.             return vertexTable.get(vertex).size();            
  198.         }  
  199.         throw new java.lang.IllegalArgumentException("JGraph(outDegree): Vertex "+vertex+" doesn't exist");  
  200.     }  
  201.       
  202.     public int inDegree(T vertex){  
  203.         int cnt = 0;  
  204.         if(vertexTable.containsKey(vertex)) {  
  205.             Set keySet = vertexTable.keySet();  
  206.             Iterator iter = keySet.iterator();  
  207.             while(iter.hasNext()) {  
  208.                 T v = iter.next();  
  209.                 if(!v.equals(vertex)) {  
  210.                     List> edges = vertexTable.get(v);  
  211.                     Iterator> eIter = edges.iterator();  
  212.                     while(eIter.hasNext()) if(eIter.next().dest.equals(vertex)) cnt++;  
  213.                 }  
  214.             }  
  215.             return cnt;  
  216.         }  
  217.         throw new java.lang.IllegalArgumentException("JGraph(inDegree): Vertex "+vertex+" doesn't exist");        
  218.     }  
  219.       
  220.     public int size(){return vertexTable.size();}  
  221.       
  222.     @Override  
  223.     public String toString(){  
  224.         StringBuffer buffer = new StringBuffer("");  
  225.         Set keySet = vertexTable.keySet();  
  226.         Iterator iter = keySet.iterator();  
  227.         while(iter.hasNext()) {  
  228.             T vertex = iter.next();  
  229.             buffer.append(vertex+":\tin-degree "+inDegree(vertex)+" out-degree "+outDegree(vertex)+"\n");  
  230.             buffer.append("\tEdges: ");  
  231.             List> edges = vertexTable.get(vertex);  
  232.             Iterator> eIter = edges.iterator();  
  233.             while(eIter.hasNext()) {  
  234.                 Edge edge = eIter.next();  
  235.                 buffer.append(edge.dest+"("+edge.weight+") ");  
  236.             }  
  237.             buffer.append("\n");  
  238.         }  
  239.         return buffer.toString();  
  240.     }  
  241.       
  242.     public static void main(String args[]) {  
  243.         JGraph graph = JGraph.readGraph("samplegraph.dat");  
  244.         System.out.println(graph);  
  245.     }  
  246. }  

Output :
A: in-degree 0 out-degree 2
Edges: B(3) C(2)
B: in-degree 3 out-degree 1
Edges: C(6)
C: in-degree 2 out-degree 2
Edges: B(4) D(1)
D: in-degree 1 out-degree 0
Edges:
E: in-degree 0 out-degree 1
Edges: B(5)
This message was edited 3 times. Last update was at 08/11/2010 16:20:12

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!