2 Replies - 10997 Views - Last Post: 30 January 2011 - 09:27 PM Rate Topic: -----

#1 pritamg  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 08-March 10

Finding shortest path between two nodes

Posted 08 March 2010 - 08:19 AM

I have to build a gui based application to find shortest path between two nodes.The graph will be input by the user.User will draw the graph using nodes and edges.On mouseclicking node will be created.on dragging mouse from one node to another weighted edge will be created.Then the user will input the start node and end node.Then shortest path will be marked.


Please help me ...I am stuck....

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
import java.lang.*;
import java.util.*;
import javax.swing.JFrame;

class SPfrm extends JFrame 
{
	int radius = 10,i=0,x,y,x1,y1,x2,y2;
	double dis;
	int[] a = new int[100];
	int[] b = new int[100];
	
        	JPanel panel2= new JPanel();
        	JButton B1 = new JButton("Enter Nodes");
        	JButton B2 = new JButton("Draw Edges");
        	JButton B3 = new JButton("Start Node");
        	JButton B4 = new JButton("End Node");
        	JButton B5 = new JButton("Run");
        	JButton B6 = new JButton("Clear");
	JButton button[]=new JButton[100];
	JInternalFrame jInternalFrame1 = new JInternalFrame();

	
	public SPfrm()
    	{
        		setTitle("Shortest Path Finding");
        		setSize(700, 600);
        		addWindowListener(new WindowAdapter() {
		public void windowClosing(WindowEvent e)
            		{
                			System.exit(0);
            		}
	           }	 );
        		Container contentPane = getContentPane();
	        	contentPane.add(jInternalFrame1,"Center");
        		contentPane.add(panel2,"South");
		jInternalFrame1.setVisible(true);
		jInternalFrame1.setBackground(Color.white);
	        	panel2.add(B1);
    	    	panel2.add(B2);
        		panel2.add(B3);
        		panel2.add(B4);
        		panel2.add(B5);
        		panel2.add(B6);
       		B1.addActionListener(new B1Listener());
       		B2.addActionListener(new B2Listener());
        		/*B3.addActionListener(new B3Listener());
        		B4.addActionListener(new B4Listener());
        		B5.addActionListener(new B5Listener());*/
        		B6.addActionListener(new B6Listener());
	}
		

	class drawedge
	{
		public void de(){
  		jInternalFrame1.addMouseListener(new java.awt.event.MouseAdapter() {
            		public void mousePressed(java.awt.event.MouseEvent event) {
                		jInternalFrame1MousePressed(event);}
		public void mouseReleased(java.awt.event.MouseEvent event) {
                		jInternalFrame1MouseReleased(event);}});}

		public void jInternalFrame1MousePressed(MouseEvent e)
  		{
			for(int l=0;l<i;l++){
			if(e.getX()==a[l] && e.getY()==b[l]){
			x1=a[l];
			y1=b[l];
			break;}}
			x1=e.getX();
			y1=e.getY();
		}
  
  		public void jInternalFrame1MouseReleased(MouseEvent e)
  		{
			for(int m=0;m<i;m++){
			if(e.getX()==a[m] && e.getY()==b[m]){
			x2=a[m];
			y2=b[m];
			x2=e.getX();
			y2=e.getY();
			Graphics g = getGraphics();
    			g.drawLine(x1-10, y1+20, x2-10, y2+20);
			dis=((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1))/10;
			if(dis<0)
				dis=dis*(-1);
			dis=Math.floor(Math.sqrt(dis));
			g.drawString(""+ dis, ((x2+x1)/2), ((y2+y1)/2));}
		}
	}}
	class drawnode
	{
		drawnode(){
		jInternalFrame1.setVisible(true);
		jInternalFrame1.getContentPane().setLayout(null);}
		public void dn(){
		jInternalFrame1.addMouseListener(new java.awt.event.MouseAdapter() {
           		public void mouseClicked(java.awt.event.MouseEvent evt) {
                		jInternalFrame1MouseClicked(evt);
          		}
        		});
		}
		private void jInternalFrame1MouseClicked(MouseEvent e)
		{
			x=e.getX();
			y=e.getY();
			button[i] = new JButton();
			 button[i].setBounds(x-7,y-30,50,30);
    			jInternalFrame1.getContentPane ().add (button[i]);
			button[i].setText(Integer.toString(i+1));
			i++;
			a[i]=x-7;
			b[i]=y-30;
		}
	
	}
	class B1Listener implements ActionListener{
		public void actionPerformed(ActionEvent event) {
			drawnode d1=new drawnode();
			d1.dn();

		}
	}
	
	class B2Listener implements ActionListener{
		public void actionPerformed(ActionEvent event) {
			drawedge d=new drawedge();
			d.de();	
		}
	}
	/*class B3Listener implements ActionListener{
		public void actionPerformed(ActionEvent event) {

		}
	}*/
	class B6Listener implements ActionListener{
		public void actionPerformed(ActionEvent event) {
			jInternalFrame1.getContentPane().removeAll();
		}

	}
	 public static void main(String args[])
    	{
        	JFrame frame = new SPfrm();
        	frame.setLocation(150, 50);
        	frame.show();
    	}
}





I can not create the edges.And also do not have idea how to find shortest path using dijkstra algorithm.

This post has been edited by Dogstopper: 08 March 2010 - 04:02 PM
Reason for edit:: [code] Post your code between these tags [/code]


Is This A Good Question/Topic? 0
  • +

Replies To: Finding shortest path between two nodes

#2 Guest_sunny*


Reputation:

Re: Finding shortest path between two nodes

Posted 30 January 2011 - 08:39 PM

import java.awt.Color;
import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.FileOutputStream;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import com.sun.image.codec.jpeg.JPEGCodec;
import com.sun.image.codec.jpeg.JPEGImageEncoder;
/****
 *
 *
 * A program that takes a comma seperated tree values and converts it into an image
 * Ex: root-child1,root-child2,child1-children1,child2-children2...
 *
 *
 * */
public class DrawGraph {

	private Hashtable listparent         = new Hashtable();
	private Hashtable keyerrors 		 = new Hashtable();
	private Hashtable nodetree 			 = new Hashtable();
	private Hashtable connectNodes 		 = new Hashtable();
	private LinkedList rowsLinkedList 	 = new LinkedList();
	private static int start_xaxis 		 = 0;
	private static int start_yaxis 		 = 40;
	private static int xaxis 			 = 800;
	private static int yaxis 			 = 600;
	private static int end_xaxis 		 = 0;
	private static int maxy 			 = 0;
	private static int rectx 			 = 0;
	private static int recty 			 = 0;
	private int 	   rows 			 = 0;
	private static String 		root;
	private static Graphics2D 	g;
	private static  int bigx = 0;
	private  int bigy = 0;



	private Hashtable _listparent         = new Hashtable();
	private Hashtable _keyerrors 		  = new Hashtable();
	private Hashtable _nodetree 			 = new Hashtable();
	private Hashtable _connectNodes 		 = new Hashtable();
	private LinkedList _rowsLinkedList 	 = new LinkedList();
	private static int _start_xaxis 		 = 0;
	private static int _start_yaxis 		 = 40;
	private static int _xaxis 			 = 1000;
	private static int _yaxis 			 = 800;
	private static int _end_xaxis 		 = 0;
	private static int _maxy 			 = 0;
	private static int _rectx 			 = 0;
	private static int _recty 			 = 0;
	private int 	   _rows 			 = 0;
	private static String 		_root;

	private static Graphics2D 	_g;




	public static void main(String args[]) {
		if (args.length == 0) {
			System.out.println("USAGE:  ");
			System.out.println("DrawGraph <queryString> <imagelocation>  ");

		}
		DrawGraph myn = new DrawGraph();
		args[0]= "root(1/2)-child1,root-child2,child1-children1,child2-children2(test1/test2)";
		args[1]="c:/test.jpeg";
		myquery=args[0];
		myoutput = args[1];
		myn.initialize(args[0], args[1]);
	}

	private static String myquery  = new String();
	private static String myoutput = new String();
	public String getErrors(String qstring) {

		StringBuffer sb = new StringBuffer();
		String[] namevalues = qstring.split(",");
		for (int i = 0; i < namevalues.length; i++) {
			String _key 	 = namevalues[i].split("-")[0];
			String _children = namevalues[i].split("-")[1];

			String[] errors 	= _key.split("\\(");
			String[] errorsc 	= _children.split("\\(");

			String mykey 		 = errors[0];
			String mychildrenkey = errorsc[0];

			LinkedList lk 		= new LinkedList();
			if (null != listparent.get(mychildrenkey)) {
				lk = (LinkedList) listparent.get(mychildrenkey);

			}

			lk.add(mykey);
			listparent.put(mychildrenkey, lk);

			if (i == 0)
				root = mykey;
			LinkedList _chil = new LinkedList();

			try {
				_chil = (LinkedList) nodetree.get(mykey);
				if (null == _chil) {
					_chil = new LinkedList();

				}
			} catch (Exception ee) {

			}
			_chil.add(errorsc[0]);
			nodetree.put(mykey, _chil);

			sb.append(mykey + "-" + _children + ",");

			LinkedList l = new LinkedList();
			if (null != keyerrors.get(mykey))
				l = (LinkedList) keyerrors.get(mykey);
			if (errors.length > 1) {
				String[] ers = errors[1].split("/");
				for (int j = 0; j < ers.length; j++)
					l.add(ers[j]);
			}

			keyerrors.put(mykey, l);

			LinkedList lc = new LinkedList();
			if (null != keyerrors.get(mychildrenkey))
				lc = (LinkedList) keyerrors.get(mychildrenkey);
			if (errorsc.length > 1) {

				String[] ersc = errorsc[1].split("/");
				for (int j = 0; j < ersc.length; j++) {
					lc.add(ersc[j]);
				}
			}
			keyerrors.put(mychildrenkey, lc);

		}

		return (sb.toString());

	}

	public void initialize(String queryString, String outputfile) {

		getErrors(queryString);
		rowsLinkedList.add(root);
		String[] str = { root };
		drawTree(str);
		createImage(root, outputfile);


	}

	public void reinitialize(String queryString, String outputfile,int _xaxis,int _yaxis) {
		listparent         = new Hashtable();
		keyerrors 		 = new Hashtable();
		nodetree 			 = new Hashtable();
		connectNodes 		 = new Hashtable();
		rowsLinkedList 	 = new LinkedList();

		System.out.println(_xaxis);
		getErrors(queryString);
		rowsLinkedList.add(root);
		String[] str = { root };
		drawTree(str);
		createImage(_xaxis,_yaxis,root, outputfile);


	}


	public void drawTree(String[] node) {
		String[] a = getGreatChildren(node);
		if (a.length > 0)
			drawTree(a);

	}


	public String[] getGreatChildren(String[] children) {
		StringBuffer sb = new StringBuffer();
		LinkedList ll = new LinkedList();
		for (int i = 0; i < children.length; i++) {

			if (null != getChildren(children[i])) {
				LinkedList temp = getChildren(children[i]);
				Iterator itr = temp.iterator();
				while (itr.hasNext()) {
					String chld = itr.next().toString();
					sb.append(chld);
					sb.append(",");
					ll.add(chld);
				}

			}
		}
		rows++;
		if (sb.toString().length() > 0)
			rowsLinkedList.add(rows, sb.toString());
		return convertLinkedListtoStringArray(ll);
	}

	public LinkedList getChildren(String node) {

		LinkedList l = new LinkedList();
		try {
			l = (LinkedList) nodetree.get(node);
			return l;
		} catch (Exception ee) {
		}

		return null;
	}

	public String[] convertLinkedListtoStringArray(LinkedList l) {

		String[] strnodes = null;
		int size = l.size();
		strnodes = new String[size];
		Object[] objectArray = l.toArray();
		new ArrayList();
		for (int i = 0; i < size; i++) {

			strnodes[i] = objectArray[i].toString();

		}

		return strnodes;
	}

	private String[] removeDuplicates(String[] l) {

		Hashtable h = new Hashtable();

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

			h.put(l[i], l[i]);

		}

		java.util.Enumeration enk = h.keys();
		LinkedList ll = new LinkedList();

		while (enk.hasMoreElements()) {
			String _as = enk.nextElement().toString();
			ll.add(_as);

		}


		return convertLinkedListtoStringArray(ll);

	}


	private void tmpinitialize(){

		_listparent          = new Hashtable(listparent);
		_keyerrors 		     = new Hashtable(keyerrors);
		_nodetree 			 = new Hashtable(nodetree);
		_connectNodes 		 = connectNodes;
		_rowsLinkedList 	 = rowsLinkedList;
		_start_xaxis 		 = start_xaxis;
		_start_yaxis 		 = start_yaxis;
		_xaxis 			 = xaxis;
		_yaxis 			 = yaxis;
		_end_xaxis 		 = end_xaxis;
		_maxy 			 = maxy;
		_rectx 			 = rectx;
		_recty 			 = recty;
		_rows 			 = rows;
		_root			 = root;



	}
	private void reset(){

		_listparent          = listparent;
		_keyerrors 		     = keyerrors;
		_nodetree 			 = nodetree;
		_connectNodes 		 = connectNodes;
		_rowsLinkedList 	 = rowsLinkedList;
		_start_xaxis 		 = start_xaxis;
		_start_yaxis 		 = start_yaxis;
		_xaxis 			 = xaxis;
		_yaxis 			 = yaxis;
		_end_xaxis 		 = end_xaxis;
		_maxy 			 = maxy;
		_rectx 			 = rectx;
		_recty 			 = recty;
		_rows 			 = rows;
		_root			 = root;


	}
	public void calculateXY(){

		tmpinitialize();

		Hashtable _allh = new Hashtable();
		int _noofrows = _rowsLinkedList.size();
		int _mxy = start_yaxis;
		for (int i = 0; i < _noofrows; i++) {


			String[] _tmpnodes = removeDuplicates(((String) _rowsLinkedList
					.get(i)).split(","));

			int _parts = calculateXY(_tmpnodes.length);

			start_yaxis = _mxy + 60;
			end_xaxis = 0;
			int _tmpy = start_yaxis;
			int _tmpx = 0;
			for (int j = 0; j < _tmpnodes.length; j++) {

				try {
					if (j+1 == 1)			{
						start_xaxis = _parts * (j + 1) - 20;
					}
					else {
						start_xaxis = _tmpx+ _parts;// * (j + 1) - 50;

					}


					_tmpx = start_xaxis;

					start_yaxis = _tmpy;

					if (null == _allh.get(_tmpnodes[j]))
						drawNode(_tmpnodes[j]);
					_allh.put(_tmpnodes[j], _tmpnodes[j]);
					if (start_yaxis >= _mxy)
						_mxy = start_yaxis;
				} catch (Exception e) {
					e.printStackTrace();
				}

			}

		}


	}
	public void createImage(String startNode, String outputfile) {

		BufferedImage image = new BufferedImage(xaxis, yaxis,
				BufferedImage.TYPE_INT_RGB);
		g = (Graphics2D) image.createGraphics();
		g.setColor(Color.white);
		g.fillRoundRect(0, 0, xaxis, yaxis, 0, 0);
		g.setColor(Color.white);
		Font f = new Font("SansSerif", Font.BOLD, 20);
		g.setFont(f);

		Hashtable allh = new Hashtable();
		int noofrows = rowsLinkedList.size();
		int mxy = start_yaxis;
		for (int i = 0; i < noofrows; i++) {


			String[] tmpnodes = removeDuplicates(((String) rowsLinkedList
					.get(i)).split(","));

			int parts = calculateXY(tmpnodes.length);

			start_yaxis = mxy + 60;
			end_xaxis = 0;
			int tmpy = start_yaxis;
			int tmpx = 0;
			int stringwidth=0;
			for (int j = 0; j < tmpnodes.length; j++) {

				try {
					if (j+1 == 1)			{
						start_xaxis = parts * (j + 1) - 20;
					}
					else {
						start_xaxis = tmpx+ parts;// * (j + 1) - 50;

					}


					tmpx = start_xaxis;

					start_yaxis = tmpy;

					if (null == allh.get(tmpnodes[j]))
						drawNode(tmpnodes[j]);
					allh.put(tmpnodes[j], tmpnodes[j]);
					if (start_yaxis >= mxy)
						mxy = start_yaxis;
					FontMetrics ff = g.getFontMetrics();
					stringwidth += (start_xaxis+ff.stringWidth(tmpnodes[j]));

				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			if (stringwidth >= bigx)bigx = stringwidth;
			System.out.println("Row "+i+" "+stringwidth);
		}

			xaxis = bigx;
			yaxis = mxy+40;

			System.out.println(xaxis);
			start_xaxis 		 = 0;
			start_yaxis 		 = 40;

			end_xaxis 		 = 0;
			maxy 			 = 0;
			rectx 			 = 0;
			recty 			 = 0;
			rows 			 = 0;

			reinitialize(myquery, myoutput,bigx,mxy+40);

	}

	public void createImage(int _xaxis,int _yaxis,String startNode, String outputfile) {

		BufferedImage image = new BufferedImage(_xaxis, _yaxis,
				BufferedImage.TYPE_INT_RGB);
		g = (Graphics2D) image.createGraphics();
		g.setColor(Color.white);
		g.fillRoundRect(0, 0, xaxis, yaxis, 0, 0);
		g.setColor(Color.white);
		Font f = new Font("SansSerif", Font.BOLD, 20);
		g.setFont(f);

		Hashtable allh = new Hashtable();
		int noofrows = rowsLinkedList.size();
		int mxy      = start_yaxis;

		for (int i = 0; i < noofrows; i++) {


			String[] tmpnodes = removeDuplicates(((String) rowsLinkedList
					.get(i)).split(","));

			int parts = calculateXY(tmpnodes.length);

			start_yaxis = mxy + 60;
			end_xaxis = 0;
			int tmpy = start_yaxis;
			int tmpx = 0;
			for (int j = 0; j < tmpnodes.length; j++) {

				try {
					if (j+1 == 1)			{
						start_xaxis = parts * (j + 1) - 20;
					}
					else {
						start_xaxis = tmpx+ parts;// * (j + 1) - 50;

					}


					tmpx = start_xaxis;

					start_yaxis = tmpy;

					if (null == allh.get(tmpnodes[j]))
						drawNode(tmpnodes[j]);
					allh.put(tmpnodes[j], tmpnodes[j]);
					if (start_yaxis >= mxy)
						mxy = start_yaxis;

				} catch (Exception e) {
					e.printStackTrace();
				}

			}

		}

		try {

			FileOutputStream jpegout = new FileOutputStream(
					new File(outputfile));
			JPEGImageEncoder encoder = JPEGCodec.createJPEGEncoder(jpegout);
			encoder.encode(image);

		} catch (Exception ee) {
			ee.printStackTrace();
		}

	}


	private int getMaxFm(String node){

		int maxfm = 0;
		FontMetrics fm 	= g.getFontMetrics();;
			maxfm 		= fm.stringWidth(node)+10;

		LinkedList errorslist  = (LinkedList)keyerrors.get(node);
		Iterator itr  = errorslist.iterator();
		while (itr.hasNext()){

			String eacherror = itr.next().toString();

			int tmpfm = fm.stringWidth(eacherror)+10;
			if (tmpfm >= maxfm) maxfm = tmpfm;
		}


		return maxfm;
	}
	private int calculateXY(int nodecount) {

		try {

			return xaxis / (nodecount + 1);
		} catch (Exception e) {

			e.printStackTrace();
		}
		return 0;
	}


	public void drawNode(String node) {


		Font f = new Font("SansSerif", Font.BOLD | Font.BOLD, 20);
		g.setFont(f);
		recty = 0;
		maxy = 0;
		FontMetrics fm = g.getFontMetrics();
		int w = fm.stringWidth(node) + 10;
		int h = fm.getHeight() + 4;
		int x = 0;x=start_xaxis;
		int y = 0;y=start_yaxis;


		int startrect_xaxis = x - w / 2;
		if (startrect_xaxis < end_xaxis) {
				x = end_xaxis + w / 2 + 10;
				startrect_xaxis = x - w / 2;

		}
		int startnode_xaxis = x - (w - 10) / 2;
		int startnode_yaxis = (y - (h - 4) / 2) + fm.getAscent();

		int startrect_yaxis = y - h / 2;
		int xrectlength = w - 1;
		int yrectlength = h - 1;

		int end_yaxis = startrect_yaxis + yrectlength + 1;
		end_xaxis = startrect_xaxis + xrectlength + 1;
		g.setColor(Color.white);
		g.fillRect(startrect_xaxis, startrect_yaxis, w, h);
		g.setColor(Color.BLACK);

		g.drawString(node, startnode_xaxis, startnode_yaxis);
		recty = yrectlength;
		if (null != keyerrors.get(node)) {
			rectx = 0;
			f = new Font("SansSerif", Font.PLAIN, 20);
			g.setFont(f);
			drawNodeErrors(node, startnode_xaxis, end_yaxis);
			if (rectx <= xrectlength)
				rectx = xrectlength;
			g.setColor(Color.black);
			calculateEdges(node, startrect_xaxis, startrect_yaxis, rectx,recty + 2);
			g.setColor(Color.GRAY);
			g.drawRoundRect(startrect_xaxis, startrect_yaxis, rectx, recty + 2,15,15);
			start_yaxis = startrect_yaxis + recty;

		} else {
			g.setColor(Color.black);
			calculateEdges(node, startrect_xaxis, startrect_yaxis, xrectlength,	yrectlength);
			g.setColor(Color.GRAY);
			g.drawRoundRect(startrect_xaxis, startrect_yaxis, xrectlength,yrectlength,15,15);


		}

		int bb = startrect_xaxis + xrectlength;
		if (bb >= bigx) {bigx = bb;}

	}

	public void drawNodeErrors(String node, int startnode_xaxis, int end_yaxis) {
		Iterator itr = ((LinkedList) keyerrors.get(node)).iterator();
		while (itr.hasNext()) {
			int startrect_xaxis = 0;
			int x = 0;
			int y = 0;
			int xrectlength = 0;
			node = itr.next().toString().replaceAll("\\)", "");
			FontMetrics fm = g.getFontMetrics();
			int w = fm.stringWidth(node) + 10;
			int h = fm.getHeight() + 4;
			x = start_xaxis;
			start_yaxis = start_yaxis + 20;
			y = start_yaxis;

			startrect_xaxis = x - w / 2;
			if (startrect_xaxis < end_xaxis) {
				x = end_xaxis + w / 2 + 10;
				startrect_xaxis = x - w / 2;

			}
			int startnode_yaxis = (y - (h - 4) / 2) + fm.getAscent();
			xrectlength = w - 1;
			g.setColor(Color.RED);
			g.drawString(node, startnode_xaxis, startnode_yaxis);
			recty += fm.getAscent();

			if (xrectlength >= rectx)
				rectx = xrectlength;
			if (recty >= maxy)
				maxy = recty;

		}
	}
	private void calculateEdges(String node, int startxaxis, int startyaxis,
			int xlength, int ylength) {

		int x1 = startxaxis + xlength / 2;
		int y1 = startyaxis;

		int x2 = x1;
		int y2 = startyaxis + ylength;

		middle m = new middle();
		m.setX1(x1);
		m.setY1(y1);
		m.setX2(x2);
		m.setY2(y2);
		m.setStartxaxis(startxaxis);

		connectNodes.put(node, m);
		try {

			String[] myparent = convertLinkedListtoStringArray((LinkedList) listparent
					.get(node));
			for (int j = 0; j < myparent.length; j++) {
				middle par = (middle) connectNodes.get(myparent[j]);

				int p[] = par.getBottom();
				int c[] = m.getTop();

				g.setColor(Color.black);
				int parentrectlength = p[0] - par.getStartxaxis();
				int parentendxaxis = par.getStartxaxis()
						+ (parentrectlength * 2);
				if (c[0] > par.getStartxaxis() && c[0] < parentendxaxis) {

					drawArrow(g,c[0],p[1],c[0],c[1]);
					drawMArrow(g,c[0],c[1],c[0],p[1]);

				}
				else {
					drawArrow(g,p[0],p[1],c[0],c[1]);
					drawMArrow(g,c[0],c[1],p[0],p[1]);

				}
			}

		}

		catch (Exception ee) {

		}

	}

	private void drawArrow( Graphics2D g, int x, int y, int xx, int yy )
	  {
	    float arrowWidth = 6.0f ;
	    float theta = 0.423f ;
	    int[] xPoints = new int[ 3 ] ;
	    int[] yPoints = new int[ 3 ] ;
	    float[] vecLine = new float[ 2 ] ;
	    float[] vecLeft = new float[ 2 ] ;
	    float fLength;
	    float th;
	    float ta;
	    float baseX, baseY ;

	    xPoints[ 0 ] = xx ;
	    yPoints[ 0 ] = yy ;


	    vecLine[ 0 ] = (float)xPoints[ 0 ] - x ;
	    vecLine[ 1 ] = (float)yPoints[ 0 ] - y ;


	    vecLeft[ 0 ] = -vecLine[ 1 ] ;
	    vecLeft[ 1 ] = vecLine[ 0 ] ;


	    fLength = (float)Math.sqrt( vecLine[0] * vecLine[0] + vecLine[1] * vecLine[1] ) ;
	    th = arrowWidth / ( 2.0f * fLength ) ;
	    ta = arrowWidth / ( 2.0f * ( (float)Math.tan( theta ) / 2.0f ) * fLength ) ;


	    baseX = ( (float)xPoints[ 0 ] - ta * vecLine[0]);
	    baseY = ( (float)yPoints[ 0 ] - ta * vecLine[1]);


	    xPoints[ 1 ] = (int)( baseX + th * vecLeft[0] );
	    yPoints[ 1 ] = (int)( baseY + th * vecLeft[1] );
	    xPoints[ 2 ] = (int)( baseX - th * vecLeft[0] );
	    yPoints[ 2 ] = (int)( baseY - th * vecLeft[1] );

	    g.drawLine( x, y, (int)baseX, (int)baseY ) ;
	    g.fillPolygon( xPoints, yPoints, 3 ) ;

	  }

	private void drawMArrow( Graphics2D g, int x, int y, int xx, int yy )
	  {
	    float arrowWidth = 6.0f ;
	    float theta = 0.423f ;
	    int[] xPoints = new int[ 3 ] ;
	    int[] yPoints = new int[ 3 ] ;
	    float[] vecLine = new float[ 2 ] ;
	    float[] vecLeft = new float[ 2 ] ;
	    float fLength;
	    float th;
	    float ta;
	    float baseX, baseY ;

	    xPoints[ 0 ] = xx ;
	    yPoints[ 0 ] = yy ;

	    vecLine[ 0 ] = (float)xPoints[ 0 ] - x ;
	    vecLine[ 1 ] = (float)yPoints[ 0 ] - y ;


	    vecLeft[ 0 ] = -vecLine[ 1 ] ;
	    vecLeft[ 1 ] = vecLine[ 0 ] ;


	    fLength = (float)Math.sqrt( vecLine[0] * vecLine[0] + vecLine[1] * vecLine[1] ) ;
	    th = arrowWidth / ( 2.0f * fLength ) ;
	    ta = arrowWidth / ( 2.0f * ( (float)Math.tan( theta ) / 2.0f ) * fLength ) ;


	    baseX = ( (float)xPoints[ 0 ] - ta * vecLine[0]);
	    baseY = ( (float)yPoints[ 0 ] - ta * vecLine[1]);


	    xPoints[ 1 ] = (int)( baseX + th * vecLeft[0] );
	    yPoints[ 1 ] = (int)( baseY + th * vecLeft[1] );
	    xPoints[ 2 ] = (int)( baseX - th * vecLeft[0] );
	    yPoints[ 2 ] = (int)( baseY - th * vecLeft[1] );


	    g.fillPolygon( xPoints, yPoints, 3 ) ;

	  }





	class middle {

		int x1;
		int y1;
		int x2;
		int y2;
		int startxaxis;

		public int getStartxaxis() {
			return startxaxis;
		}

		public void setStartxaxis(int startxaxis) {
			this.startxaxis = startxaxis;
		}

		public int getX1() {
			return x1;
		}

		public void setX1(int x1) {
			this.x1 = x1;
		}

		public int getY1() {
			return y1;
		}

		public void setY1(int y1) {
			this.y1 = y1;
		}

		public int getX2() {
			return x2;
		}

		public void setX2(int x2) {
			this.x2 = x2;
		}

		public int getY2() {
			return y2;
		}

		public void setY2(int y2) {
			this.y2 = y2;
		}

		public int[] getTop() {

			int t[] = new int[2];
			t[0] = this.x1;
			t[1] = this.y1;

			return t;
		}

		public int[] getBottom() {

			int t[] = new int[2];
			t[0] = this.x2;
			t[1] = this.y2;

			return t;
		}

	}
}


This post has been edited by macosxnerd101: 30 January 2011 - 09:26 PM
Reason for edit:: Please use code tags

Was This Post Helpful? 0

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,604
  • Joined: 27-December 08

Re: Finding shortest path between two nodes

Posted 30 January 2011 - 09:27 PM

Also as an addendum to the above code, note that Java Collections as of Java 1.5 are generic.

And for what it's worth, I figure I'll throw out my Dijkstra's Algorithm Tutorial.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1