Hello, I have this java code which draws to me 100 nodes(with the sink node)(like the figure) that are connected by links, at the end I will get a tree , now I need to redraw the tree in(shortest path tree using prim algorithm )I have the nods in ( x,y) coordinate, and the number of hops from any node to the sink node and the parent for each node(these result I got them from my c++ prim algorithm code )
I’m really confused and I don’t know how to improve the code to redraw the shortest path tree
Any suggestions or comments will be appreciated

package heuristic;
import javax.swing.*;
import java.awt.Color;
import java.io.*;
import java.util.*;
import java.awt.Graphics;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.BufferedInputStream;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;


public class multitreeplot extends JFrame {
    public void paint(Graphics paint){
        super.paint(paint);
        int[][] data;
        int NMax = 500; // number of nodes in the topology
        int dx = 100, dy = 100 , rectSize = 500;
        data = new int[NMax][2];
        int Ovalsize = 6;
        int Plus = 1;
        double radiorange =50;
     try{
//nodes

    FileReader fG = new FileReader("OriginalTopoPos.txt");
        BufferedReader bufReadG = new BufferedReader(fG);
//sink
        FileReader fSinks = new FileReader("SinksFile.txt");
        BufferedReader bufReadSinks = new BufferedReader(fSinks);

             setTitle("MultiTree Drawer");


            // The whole background
            paint.setColor (Color.white);
            paint.fillRect (0,0,700,700);

             // Determine the size of the area.
             paint.setColor (Color.black);
             paint.drawRect (dx-1,dy-1,rectSize+1,rectSize+1);
             paint.drawRect (dx-2,dy-2,rectSize+1,rectSize+1);
             paint.setColor (Color.white);
             paint.fillRect (dx+1,dy+1,rectSize-2,rectSize-2);

             //Plot the original topology.
            NMax = 0;
            String lineG =new String( bufReadG.readLine());
            while (lineG != null){
                int index= lineG.indexOf("-");
                double x= (new Double(lineG.substring(0, index))).doubleValue();
                double y= (new Double(lineG.substring(index+1, lineG.length()))).doubleValue();

                // ** Reflect the image
                      // Aseel, in your experiment do not divide y, x by 10///
                y=rectSize-y/10;                                                    
                x = (int)(x/10.0) + 100;
                y = (int)(y) + 100;                 
                data[NMax][0] = (int)(x);
                data[NMax][1] = (int)(y);

                System.out.println((int)x+","+(int)y);

                String s = String.valueOf(NMax);
                paint.setColor (Color.gray);
                paint.drawString(s, (int)x+4,(int)y-1);

                paint.setColor (Color.blue);
                paint.drawOval((int)x-4,(int)y-4, Ovalsize+Plus, Ovalsize+Plus);

                paint.setColor (Color.blue);
                paint.fillOval((int)x-3,(int)y-3, Ovalsize, Ovalsize);
                lineG = bufReadG.readLine();
                NMax++;
            }



            //Plot the links in original Topology.
            // *********************************
        //  
             for (int i =0 ; i < NMax; i++)
                for (int j =i ; j < NMax; j++){
                    double distance = Math.pow(data[i][0]-data[j][0],2)+ Math.pow(data[i][1]-data[j][1],2);
                    distance = Math.sqrt(distance);
                    paint.setColor (Color.gray);
                    if (distance <= radiorange)
                        {
                            //gradient
                            //pink
                            //magenta
                            //cyan
            paint.setColor (Color.magenta);
                        paint.drawLine( data[i][0], data[i][1], data[j][0],data[j][1] );
                        }


                }
    //    */


            //Plot Sink Nodes.
            int Sinks = 0;
            String lineSinks =new String( bufReadSinks.readLine());
            while(lineSinks != null){
                int index= lineSinks.indexOf("-");
                double x= (new Double(lineSinks.substring(0, index))).doubleValue();
                double y= (new Double(lineSinks.substring(index+1, lineSinks.length()))).doubleValue();

                //Reflect the image
                y=rectSize-y/10;                                                    
                x = (int)(x/10.0) + 100;
                y = (int)(y) + 100;   

                paint.setColor (Color.blue);
                paint.drawRect((int)x-5,(int)y-4, Ovalsize+Plus, Ovalsize+Plus);

                paint.setColor (Color.green);
                paint.fillRect((int)x-4,(int)y-3, Ovalsize, Ovalsize);  

                //String s = String.valueOf(NMax);
                String s = "Sink";
                paint.setColor (Color.gray);
                paint.setColor (Color.black);
                paint.drawString(s, (int)x+12,(int)y-5);        

                lineSinks = bufReadSinks.readLine();
                Sinks++;
            }
            //System.out.println(Sinks);


     }catch(Exception e){
        System.out.println(e);
        System.exit(-1);
     }

   }

    public multitreeplot(){
        super("");
        int WSize = 700;
        setSize(WSize,WSize);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        }
public static void main(String [] args) throws Exception{
    JFrame win= new JFrame();
    multitreeplot drawing= new multitreeplot();
    drawing.setVisible(true);
}
}
//System.out.println((int)x+","+(int)y);
Attachments
coordinate:  I =  0   41-67
coordinate:  I =  1   34-0
coordinate:  I =  2   69-24
coordinate:  I =  3   78-58
coordinate:  I =  4   162-64
coordinate:  I =  5   105-45
coordinate:  I =  6   181-27
coordinate:  I =  7   161-91
coordinate:  I =  8   295-42
coordinate:  I =  9   227-36
coordinate:  I =  10   291-4
coordinate:  I =  11   202-53
coordinate:  I =  12   392-82
coordinate:  I =  13   321-16
coordinate:  I =  14   318-95
coordinate:  I =  15   347-26
coordinate:  I =  16   471-38
coordinate:  I =  17   469-12
coordinate:  I =  18   467-99
coordinate:  I =  19   435-94
coordinate:  I =  20   3-111
coordinate:  I =  21   22-133
coordinate:  I =  22   73-164
coordinate:  I =  23   41-111
coordinate:  I =  24   153-168
coordinate:  I =  25   147-144
coordinate:  I =  26   162-157
coordinate:  I =  27   137-159
coordinate:  I =  28   223-141
coordinate:  I =  29   229-178
coordinate:  I =  30   216-135
coordinate:  I =  31   290-142
coordinate:  I =  32   388-106
coordinate:  I =  33   340-142
coordinate:  I =  34   364-148
coordinate:  I =  35   346-105
coordinate:  I =  36   490-129
coordinate:  I =  37   470-150
coordinate:  I =  38   406-101
coordinate:  I =  39   493-148
coordinate:  I =  40   29-223
coordinate:  I =  41   84-254
coordinate:  I =  42   56-240
coordinate:  I =  43   66-276
coordinate:  I =  44   131-208
coordinate:  I =  45   144-239
coordinate:  I =  46   126-223
coordinate:  I =  47   137-238
coordinate:  I =  48   218-282
coordinate:  I =  49   229-241
coordinate:  I =  50   233-215
coordinate:  I =  51   239-258
coordinate:  I =  52   304-230
coordinate:  I =  53   377-206
coordinate:  I =  54   373-286
coordinate:  I =  55   321-245
coordinate:  I =  56   424-272
coordinate:  I =  57   470-229
coordinate:  I =  58   477-273
coordinate:  I =  59   497-212
coordinate:  I =  60   86-390
coordinate:  I =  61   61-336
coordinate:  I =  62   55-367
coordinate:  I =  63   55-374
coordinate:  I =  64   131-352
coordinate:  I =  65   150-350
coordinate:  I =  66   141-324
coordinate:  I =  67   166-330
coordinate:  I =  68   207-391
coordinate:  I =  69   207-337
coordinate:  I =  70   257-387
coordinate:  I =  71   253-383
coordinate:  I =  72   345-309
coordinate:  I =  73   309-358
coordinate:  I =  74   321-388
coordinate:  I =  75   322-346
coordinate:  I =  76   406-330
coordinate:  I =  77   413-368
coordinate:  I =  78   400-391
coordinate:  I =  79   462-355
coordinate:  I =  80   10-459
coordinate:  I =  81   24-437
coordinate:  I =  82   48-483
coordinate:  I =  83   95-441
coordinate:  I =  84   102-450
coordinate:  I =  85   191-436
coordinate:  I =  86   174-420
coordinate:  I =  87   196-421
coordinate:  I =  88   248-499
coordinate:  I =  89   268-484
coordinate:  I =  90   281-434
coordinate:  I =  91   253-499
coordinate:  I =  92   318-438
coordinate:  I =  93   300-488
coordinate:  I =  94   327-467
coordinate:  I =  95   328-493
coordinate:  I =  96   448-483
coordinate:  I =  97   407-421
coordinate:  I =  98   410-417
coordinate:  I =  99   413-414


 I = 0 Parent = 0 Hops =  0


 I = 1 Parent = 0 Hops =  1


 I = 2 Parent = 0 Hops =  1


 I = 3 Parent = 0 Hops =  1


 I = 4 Parent = 0 Hops =  0


 I = 5 Parent = 4 Hops =  1


 I = 6 Parent = 4 Hops =  1


 I = 7 Parent = 4 Hops =  1


 I = 8 Parent = 0 Hops =  0


 I = 9 Parent = 8 Hops =  1


 I = 10 Parent = 8 Hops =  1


 I = 11 Parent = 4 Hops =  1


 I = 12 Parent = 0 Hops =  0


 I = 13 Parent = 8 Hops =  1


 I = 14 Parent = 8 Hops =  1


 I = 15 Parent = 8 Hops =  1


 I = 16 Parent = 0 Hops =  0


 I = 17 Parent = 16 Hops =  1


 I = 18 Parent = 16 Hops =  1


 I = 19 Parent = 12 Hops =  1


 I = 20 Parent = 0 Hops =  0


 I = 21 Parent = 0 Hops =  0


 I = 22 Parent = 0 Hops =  0


 I = 23 Parent = 21 Hops =  1


 I = 24 Parent = 0 Hops =  0


 I = 25 Parent = 24 Hops =  1


 I = 26 Parent = 7 Hops =  2


 I = 27 Parent = 25 Hops =  2


 I = 28 Parent = 25 Hops =  2


 I = 29 Parent = 28 Hops =  3


 I = 30 Parent = 25 Hops =  2


 I = 31 Parent = 28 Hops =  3


 I = 32 Parent = 0 Hops =  0


 I = 33 Parent = 14 Hops =  2


 I = 34 Parent = 31 Hops =  4


 I = 35 Parent = 32 Hops =  1


 I = 36 Parent = 18 Hops =  2


 I = 37 Parent = 18 Hops =  2


 I = 38 Parent = 35 Hops =  2


 I = 39 Parent = 18 Hops =  2


 I = 40 Parent = 0 Hops =  0


 I = 41 Parent = 0 Hops =  0


 I = 42 Parent = 41 Hops =  1


 I = 43 Parent = 41 Hops =  1


 I = 44 Parent = 25 Hops =  2


 I = 45 Parent = 41 Hops =  1


 I = 46 Parent = 27 Hops =  3


 I = 47 Parent = 27 Hops =  3


 I = 48 Parent = 0 Hops =  0


 I = 49 Parent = 48 Hops =  1


 I = 50 Parent = 29 Hops =  4


 I = 51 Parent = 49 Hops =  2


 I = 52 Parent = 0 Hops =  0


 I = 53 Parent = 34 Hops =  5


 I = 54 Parent = 0 Hops =  0


 I = 55 Parent = 0 Hops =  0


 I = 56 Parent = 54 Hops =  1


 I = 57 Parent = 37 Hops =  3


 I = 58 Parent = 57 Hops =  4


 I = 59 Parent = 39 Hops =  3


 I = 60 Parent = 0 Hops =  0


 I = 61 Parent = 60 Hops =  1


 I = 62 Parent = 61 Hops =  2


 I = 63 Parent = 61 Hops =  2


 I = 64 Parent = 0 Hops =  0


 I = 65 Parent = 64 Hops =  1


 I = 66 Parent = 0 Hops =  0


 I = 67 Parent = 0 Hops =  0


 I = 68 Parent = 0 Hops =  0


 I = 69 Parent = 68 Hops =  1


 I = 70 Parent = 68 Hops =  1


 I = 71 Parent = 68 Hops =  1


 I = 72 Parent = 0 Hops =  0


 I = 73 Parent = 0 Hops =  0


 I = 74 Parent = 73 Hops =  1


 I = 75 Parent = 74 Hops =  2


 I = 76 Parent = 56 Hops =  2


 I = 77 Parent = 76 Hops =  3


 I = 78 Parent = 76 Hops =  3


 I = 79 Parent = 77 Hops =  4


 I = 80 Parent = 0 Hops =  0


 I = 81 Parent = 80 Hops =  1


 I = 82 Parent = 81 Hops =  2


 I = 83 Parent = 81 Hops =  2


 I = 84 Parent = 60 Hops =  1


 I = 85 Parent = 68 Hops =  1


 I = 86 Parent = 68 Hops =  1


 I = 87 Parent = 68 Hops =  1


 I = 88 Parent = 0 Hops =  0


 I = 89 Parent = 88 Hops =  1


 I = 90 Parent = 89 Hops =  2


 I = 91 Parent = 89 Hops =  2


 I = 92 Parent = 74 Hops =  2


 I = 93 Parent = 90 Hops =  3


 I = 94 Parent = 90 Hops =  3


 I = 95 Parent = 92 Hops =  3


 I = 96 Parent = 0 Hops =  0


 I = 97 Parent = 77 Hops =  4


 I = 98 Parent = 77 Hops =  4


 I = 99 Parent = 0 Hops =  0
RADDIO90.JPG 139.47 KB

Do you want each path from each node to the sink node to be different color? If so, you will need to reconstruct the path to get back to the sink node. If not, you imply ignore the hop value and draw only the line from itself to its parent node. That way, it will display all paths of the shortest spanning tree.

To draw a spanning tree, you don't need to know the path from each node to the sink node because those paths away from each node (the one which is the 2nd, 3rd, etc hop) are already covered (the same) by itself to its parent node.

/*
i.e.

  2---------1------------Sink node
            |
            3
           / \
          /   \
         4     5

So your result would be...
Node  Parent  Hop#
  1      S     1
  2      1     2
  3      1     2
  4      3     3
  5      3     3

That's why the hop number doesn't mean anything. The path from node 2 to 1 is enough for the drawing because the path from node 1 to the sink node is a part of it.
*/

Edited 3 Years Ago by Taywin

This article has been dead for over six months. Start a new discussion instead.