Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jun 11th, 2012  |  syntax: None  |  size: 4.41 KB  |  hits: 18  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. package ads1ss12.pa;
  2.  
  3. import java.util.*;
  4.  
  5. /**
  6.  * Klasse zum Berechnen eines k-MST mittels Branch-and-Bound. Hier sollen Sie
  7.  * Ihre Lösung implementieren.
  8.  */
  9. public class KMST extends AbstractKMST {
  10.  
  11.         int numNodes, numEdges, k;
  12.         TreeSet<Edge> ts_edges;
  13.         TreeSet<Edge> kmst_tree;
  14.         /**
  15.          * Der Konstruktor. Hier ist die richtige Stelle f&uuml;r die
  16.          * Initialisierung Ihrer Datenstrukturen.
  17.          *
  18.          * @param numNodes
  19.          *            Die Anzahl der Knoten
  20.          * @param numEdges
  21.          *            Die Anzahl der Kanten
  22.          * @param edges
  23.          *            Die Menge der Kanten
  24.          * @param k
  25.          *            Die Anzahl der Knoten, die Ihr MST haben soll
  26.          */
  27.         public KMST(Integer numNodes, Integer numEdges, HashSet<Edge> edges, int k) {
  28.                 // TODO: Hier ist der richtige Platz fuer Initialisierungen
  29.                 this.numNodes=numNodes;
  30.                 this.numEdges=numEdges;
  31.                 this.ts_edges = new TreeSet<Edge>(edges);
  32.                 this.k=k;
  33.         }
  34.  
  35.         /**
  36.          * Diese Methode bekommt vom Framework maximal 30 Sekunden Zeit zur
  37.          * Verf&uuml;gung gestellt um einen g&uuml;ltigen k-MST zu finden.
  38.          *
  39.          * <p>
  40.          * F&uuml;gen Sie hier Ihre Implementierung des Branch-and-Bound Algorithmus
  41.          * ein.
  42.          * </p>
  43.          */
  44.         @Override
  45.         public void run() {
  46.                 // TODO: Diese Methode ist von Ihnen zu implementieren
  47.                 kmstSolution(ts_edges);
  48.  
  49.                 ts_edges=removeLastEdges(ts_edges, this.getSolution().getUpperBound());
  50.  
  51.                 doBnB(ts_edges, new TreeSet<Edge>(),0,0);
  52.  
  53.         }
  54.  
  55.         public TreeSet<Edge> removeLastEdges(TreeSet<Edge> edges, int upper){
  56.                 int sum=0, count=0;
  57.                 TreeSet<Edge> result = new TreeSet<Edge>(edges);
  58.                 /*for(Edge e : result){
  59.                         sum+=e.weight;
  60.                         if(++count==(k-2)){
  61.                                 break;
  62.                         }
  63.                 }
  64.                 upper-=sum;*/
  65.                 while(result.last().weight>upper){
  66.                         result.pollLast();
  67.                 }
  68.  
  69.                 return result;
  70.         }
  71.  
  72.         public void doBnB(TreeSet<Edge> edges, TreeSet<Edge> removed, int numWith, int depth){
  73.  
  74.                 TreeSet<Edge> kmst, tree;
  75.  
  76.                 if(numWith>k-1) return;
  77.  
  78.                 tree = new TreeSet<Edge>(edges);
  79.                 tree.removeAll(removed);
  80.  
  81.                 int count = 0;
  82.                 int lowerBound = 0;
  83.                 for(Edge e: tree){
  84.                         lowerBound += e.weight;
  85.                         if(++count==this.k-1)
  86.                                 break;
  87.                 }
  88.  
  89.                 if(lowerBound>=getSolution().getUpperBound() || count != this.k-1)
  90.                         return;
  91.  
  92.                 if((kmst = doPrim(tree, 0)) != null){
  93.                         int sum = 0;
  94.                         for(Edge e : kmst){
  95.                                 sum += e.weight;
  96.                         }
  97.  
  98.                         if(setSolution(sum,kmst)){
  99.                                 ts_edges = removeLastEdges(ts_edges,sum);
  100.                                 TreeSet<Edge> tmp = new TreeSet<Edge>(edges);
  101.                                 tmp.removeAll(ts_edges);
  102.                                 removed.addAll(tmp);
  103.                         }
  104.  
  105.                         doBnB(new TreeSet<Edge>(edges), new TreeSet<Edge>(removed), numWith+1, depth+1);
  106.  
  107.                         Edge edge = new Edge(0,0,0);
  108.                         count = 0;
  109.                         for(Edge e : edges){
  110.                                 edge = e;
  111.                                 if(count++== depth)
  112.                                         break;
  113.                         }
  114.                         removed.add(edge);
  115.                         doBnB(new TreeSet<Edge>(edges), new TreeSet<Edge>(removed), numWith, depth+1);
  116.  
  117.                 }
  118.         }
  119.  
  120.         public void kmstSolution(TreeSet<Edge> edges){
  121.                 TreeSet<Edge> final_ts = new TreeSet<Edge>();
  122.                 int begin=0, sum=0;
  123.  
  124.                
  125.                 for(int j=0;j<edges.size()/2;j++){
  126.  
  127.                         final_ts=doPrim(edges, begin);
  128.  
  129.                         if(final_ts!=null){
  130.                                 for(Edge e: final_ts){
  131.                                         sum += e.weight;
  132.                                 }
  133.                                 if(begin>0){
  134.                                         if(sum<=this.getSolution().getUpperBound()){
  135.                                                 this.setSolution(sum, new TreeSet<Edge>(final_ts));
  136.                                                 kmst_tree=new TreeSet<Edge>(final_ts);
  137.                                         }
  138.                                 }
  139.                                 else{
  140.                                         this.setSolution(sum, new TreeSet<Edge>(final_ts));
  141.                                         kmst_tree=new TreeSet<Edge>(final_ts);
  142.                                 }
  143.                         }
  144.                                                
  145.                         begin++;
  146.                         sum=0;
  147.                 }
  148.         }
  149.  
  150.         public TreeSet<Edge> doPrim(TreeSet<Edge> tree, int edgeNr){
  151.  
  152.                 TreeSet<Edge> result = new TreeSet<Edge>();
  153.                 HashSet<Integer> intSet = new HashSet<Integer>();
  154.  
  155.  
  156.                 Edge edge = new Edge(0,0,0);
  157.                 if(edgeNr==0){ 
  158.                         edge = tree.first();
  159.  
  160.                         intSet.add(edge.node1);
  161.                         intSet.add(edge.node2);
  162.                 }
  163.                 else{
  164.                         int count = 0;
  165.                         for(Edge e : tree){
  166.                                 edge = e;
  167.                                 if(count++ == edgeNr)  break;
  168.                         }
  169.                         intSet.add(edge.node1);
  170.                         intSet.add(edge.node2);
  171.                 }
  172.  
  173.                 result.add(edge);
  174.  
  175.                 while(this.k-1 > result.size()){
  176.  
  177.                         boolean found = false;
  178.                         for(Edge e: tree){
  179.  
  180.                                 boolean a = (intSet.contains(e.node1));
  181.                                 boolean b = (intSet.contains(e.node2));
  182.                                 if((a||b) && !(a&&b)){
  183.                                         result.add(e);
  184.                                         intSet.add(e.node1);
  185.                                         intSet.add(e.node2);
  186.                                         found = true;
  187.                                         break;
  188.                                 }
  189.                         }
  190.                         if(!found){
  191.                                 return null;
  192.                         }
  193.  
  194.                 }              
  195.  
  196.                 if(result.size()!=this.k-1 || intSet.size()!=this.k ){
  197.                         return null;
  198.                 }
  199.  
  200.                 return result;         
  201.         }
  202.  
  203.  
  204.  
  205. }
create a new version of this paste RAW Paste Data