defaultmap.java

最短路径和哈密顿通路

import java.awt.*;
import java.awt.event.*;
import java.awt.geom.Line2D;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.*;
import java.util.StringTokenizer;
import java.net.*;

import javax.swing.*;
public class DefaultMap extends JPanel implements ActionListener{
	int index1=0,index2=0,index3=0;
	String []path=new String[100];
	String lastdrawstr="";
	
	JOptionPane jop=new JOptionPane();
	Font font1=new Font("仿宋_GB2312",Font.BOLD,15);
	JLabel jlb5=new JLabel("要求选择不同的景点，请重试！");
	
	JOptionPane jop1=new JOptionPane();
	Font font2=new Font("仿宋_GB2312",Font.BOLD,15);
	JLabel jlb6=new JLabel("该两结点间没有哈密顿通路，请重试！");
	
	JOptionPane jop2=new JOptionPane();
	Font font3=new Font("仿宋_GB2312",Font.BOLD,15);
	JLabel jlb7=new JLabel("请选择要画的路径，请重试！");
	
	JLabel jlb1=new JLabel("现在地：");
	JLabel jlb2=new JLabel("目的地：");
	JLabel jlb3=new JLabel("要求：");
	JLabel jlb4=new JLabel("路线：");
	JComboBox jbox1=new JComboBox();
	JComboBox jbox2=new JComboBox();
	JComboBox jbox3=new JComboBox();
	JButton jb1=new JButton("OK");
	JButton jb2=new JButton("Clear");
	JButton jb3=new JButton("Draw");
	JListPane jlt=new JListPane();
	public DefaultMap()
	{
		this.setLayout(null);
		this.add(jlb1);
		jlb1.setBounds(30,10,100,100);
		
		this.add(jbox1);
		jbox1.addItem("入口处");
		jbox1.addItem("景点1");
		jbox1.addItem("景点2");
		jbox1.addItem("景点3");
		jbox1.addItem("景点4");
		jbox1.addItem("景点5");
		jbox1.addItem("景点6");
		jbox1.addItem("景点7");
		jbox1.addItem("景点8");
		jbox1.addItem("景点9");
		jbox1.addItem("出口处");
		jbox1.setBounds(110,45,100,30);
		jbox1.addActionListener(this);
		
		this.add(jlb2);
		jlb2.setBounds(250,10,100,100);
		
		this.add(jbox2);
		jbox2.addItem("入口处");
		jbox2.addItem("景点1");
		jbox2.addItem("景点2");
		jbox2.addItem("景点3");
		jbox2.addItem("景点4");
		jbox2.addItem("景点5");
		jbox2.addItem("景点6");
		jbox2.addItem("景点7");
		jbox2.addItem("景点8");
		jbox2.addItem("景点9");
		jbox2.addItem("出口处");
		jbox2.setBounds(330,45,100,30);
		jbox2.addActionListener(this);
		
		this.add(jlb3);
		jlb3.setBounds(460,10,100,100);
		
		this.add(jbox3);
		jbox3.addItem("最短路径");
		jbox3.addItem("哈密顿通路");
		jbox3.addItem("所有路径");
		jbox3.setBounds(520,45,100,30);
		jbox3.addActionListener(this);
		
		this.add(jb1);
		jb1.setBounds(670,45,80,30);
		jb1.addActionListener(this);
		
		this.add(jlb4);
		jlb4.setBounds(30,90,100,100);
		
		this.add(jlt);
		jlt.setBounds(110,120,450,40);
	//	jlt.jlist.setListData(path);
		
		this.add(jb2);
		jb2.setBounds(680,125,80,30);
		jb2.addActionListener(this);
		
		this.add(jb3);
		jb3.setBounds(580,125,80,30);
		jb3.addActionListener(this);
		
		
	}
	
	public void paintComponent(Graphics g)
	{
		super.paintComponent(g);
		g.setColor(Color.DARK_GRAY);
		g.fillOval(100,200,10,10);
		
		g.fillOval(200,200,10,10);
		
		g.fillOval(400,200,10,10);
		
		g.fillOval(650,200,10,10);
		
		g.fillOval(100,300,10,10);
		
		g.fillOval(300,300,10,10);
		
		g.fillOval(100,450,10,10);
		
		g.fillOval(200,350,10,10);
		
		g.fillOval(500,350,10,10);
		
		g.fillOval(200,450,10,10);
		
		g.fillOval(650,450,10,10);
		
		
		g.drawLine(105,205,205,205);
		g.drawLine(205,205,405,205);
		g.drawLine(405,205,655,205);
		g.drawLine(105,205,105,305);
		g.drawLine(205,205,105,305);
		g.drawLine(205,205,305,305);
		g.drawLine(305,305,655,205);
		g.drawLine(105,305,105,455);
		g.drawLine(305,305,205,355);
		g.drawLine(205,355,505,355);
		g.drawLine(505,355,655,205);
		g.drawLine(205,355,205,455);
		g.drawLine(105,455,205,455);
		g.drawLine(205,455,655,455);
		g.drawLine(505,355,655,455);
		
		
		g.setColor(Color.MAGENTA);
		g.drawString("结点0(入口)",100,200);
		g.drawString("结点1",220,200);
		g.drawString("结点2",420,200);
		g.drawString("结点4",670,200);
		g.drawString("结点5",120,300);
		g.drawString("结点3",320,300);
		g.drawString("结点7",220,350);
		g.drawString("结点9",520,350);
		g.drawString("结点6",120,450);
		g.drawString("结点8",220,450);
		g.drawString("结点10(出口)",670,450);
		
		g.setColor(Color.blue);
		g.drawString("3",150,220);
		g.drawString("6",300,200);
		g.drawString("7",525,200);
		g.drawString("4",110,250);
		g.drawString("6",110,375);
		g.drawString("2",150,470);
		g.drawString("14",425,470);
		g.drawString("5",190,400);
		g.drawString("10",350,350);
		g.drawString("7",150,250);
		g.drawString("5",250,250);
		g.drawString("12",450,250);
		g.drawString("9",550,300);
		g.drawString("3",250,325);
		g.drawString("7",550,400);
		
	}

	public void actionPerformed(ActionEvent e) {
		// TODO Auto-generated method stub
		Object source=e.getSource();
		if(source==jbox1)
		{
			index1=jbox1.getSelectedIndex();
		}
		if(source==jbox2)
		{
			index2=jbox2.getSelectedIndex();
		}
		if(source==jbox3)
		{
			index3=jbox3.getSelectedIndex();
		}
		if(source==jb1)
		{
			if(index1==index2)
			{
				jlb5.setFont(font1);
				jop.showMessageDialog(null,jlb5,"程序警告",JOptionPane.ERROR_MESSAGE);
			}
			else
			{
				WeightedGraph graph=new WeightedGraph(11);
				try {
					graph.createWeightedGraph();
				} catch (NumberFormatException e1) {
					// TODO Auto-generated catch block
					e1.printStackTrace();
				} catch (IOException e1) {
					// TODO Auto-generated catch block
					e1.printStackTrace();
				}
				switch(index3)
				{
				case 0:
					graph.findShortestPath(index1,index2);
					for (int i=0; i<100; i++)
					{
						path[i]="";
					}
					int k=0;
					for(int i=0; i<100; i++)
					{
						if(graph.shortestpath[i][0]!=-1)
						{
							String str="";
							for(int j=0; j<graph.gSize; j++)
							{
								if(graph.shortestpath[i][j]!=-1 && graph.shortestpath[i][j]!=index2)
								{
									str+=graph.shortestpath[i][j];
									str+="->";
								}
								if(graph.shortestpath[i][j]!=-1 && graph.shortestpath[i][j]==index2)
								{
									str+=graph.shortestpath[i][j];
								}
							}
							path[k]=str;
							k++;
						}
					}
					jlt.jlist.setListData(path);
					break;
				case 1:
					graph.findHamPath(index1,index2);
					int k1=0;
					for (int i=0; i<100; i++)
					{
						path[i]="";
					}
					for(int i=0; i<100; i++)
					{
						if(graph.hampath[i][0]!=-1)
						{
							String str="";
							for(int j=0; j<graph.gSize; j++)
							{
								if(graph.hampath[i][j]!=-1 && graph.hampath[i][j]!=index2)
								{
									str+=graph.hampath[i][j];
									str+="->";
								}
								if(graph.hampath[i][j]!=-1 && graph.hampath[i][j]==index2)
								{
									str+=graph.hampath[i][j];
								}
							}
							path[k1]=str;
							k1++;
						}
					}
					if(path[0].equals(""))
					{
						jlt.jlist.setListData(path);
						jlb6.setFont(font2);
						jop1.showMessageDialog(null,jlb6,"程序警告",JOptionPane.ERROR_MESSAGE);
					}
					jlt.jlist.setListData(path);
					break;
				case 2:
					graph.findAllPath(index1,index2);
					int k3=0;
					for (int i=0; i<100; i++)
					{
						path[i]="";
					}
					for(int i=0; i<100; i++)
					{
						if(graph.shortpath[i][0]!=-1)
						{
							String str="";
							for(int j=0; j<graph.gSize; j++)
							{
								if(graph.shortpath[i][j]!=-1 && graph.shortpath[i][j]!=index2)
								{
									str+=graph.shortpath[i][j];
									str+="->";
								}
								if(graph.shortpath[i][j]!=-1 && graph.shortpath[i][j]==index2)
								{
									str+=graph.shortpath[i][j];
								}
							}
							path[k3]=str;
							k3++;
						}
					}
					jlt.jlist.setListData(path);
					break;
				}
			}
		}
		if(source==jb2)
		{
			
			for(int i=0; i<100; i++)
			{
				path[i]="";
			}
			jlt.jlist.setListData(path);
			this.repaint();
		}
		if(source==jb3)
		{
			
			String itemStr1;
			int []itempath=new int[11];
			for(int i=0; i<itempath.length; i++)
			{
				itempath[i]=-1;
			}
			itemStr1=(String)jlt.jlist.getSelectedValue();
			if(lastdrawstr!=itemStr1)
			{
			//	this.repaint();
				Graphics g=this.getGraphics();
				g.setColor(Color.DARK_GRAY);
				g.drawLine(105,205,205,205);
				g.drawLine(205,205,405,205);
				g.drawLine(405,205,655,205);
				g.drawLine(105,205,105,305);
				g.drawLine(205,205,105,305);
				g.drawLine(205,205,305,305);
				g.drawLine(305,305,655,205);
				g.drawLine(105,305,105,455);
				g.drawLine(305,305,205,355);
				g.drawLine(205,355,505,355);
				g.drawLine(505,355,655,205);
				g.drawLine(205,355,205,455);
				g.drawLine(105,455,205,455);
				g.drawLine(205,455,655,455);
				g.drawLine(505,355,655,455);
			}
			lastdrawstr=itemStr1;
			if(itemStr1==null)
			{
				jlb6.setFont(font2);
				jop1.showMessageDialog(null,jlb7,"程序警告",JOptionPane.ERROR_MESSAGE);
			}
			else
			{
				StringTokenizer strtoken=new StringTokenizer(itemStr1,"->");
				int k=0;
				while(strtoken.hasMoreTokens())
				{
					itempath[k]=Integer.parseInt(strtoken.nextToken());
					k++;
				}
				System.out.println();
				for(int i=0; i<itempath.length; i++)
					System.out.print(itempath[i]+"  ");
			}
			
			
			try {
				URL url=DefaultMap.class.getResource("coordinate.txt");
				InputStream in=url.openStream();
				BufferedReader infile=new BufferedReader(new InputStreamReader(in));
				int fx=0,fy=0,tx=0,ty=0;
				int [][]coordinate=new int[11][3];
				int m,node;
				StringTokenizer tokenizer;
				int length=Integer.parseInt(infile.readLine());
				for(m=0; m<length; m++)
				{
					tokenizer=new StringTokenizer(infile.readLine());
					node=Integer.parseInt(tokenizer.nextToken());

					coordinate[node][0]=node;
					
					coordinate[node][1]=Integer.parseInt(tokenizer.nextToken());
					coordinate[node][2]=Integer.parseInt(tokenizer.nextToken());
					
				}
				System.out.println();
				for(int i=0; i<11; i++)
				{
					for(int j=0; j<3; j++)
						System.out.print(coordinate[i][j]+"  ");
					System.out.println();
				}
				for(int i=0; i<itempath.length-1; i++)
				{
					if(itempath[i]!=-1 && itempath[i+1]!=-1)
					{
						for(int j=0; j<11; j++)
						{
							if(itempath[i]==coordinate[j][0])
							{
								fx=coordinate[j][1];
								fy=coordinate[j][2];
							}
						}
						for(int j=0; j<11; j++)
						{
							if(itempath[i+1]==coordinate[j][0])
							{
								tx=coordinate[j][1];
								ty=coordinate[j][2];
							}
						}
				//		System.out.println("fx:"+fx+"fy:"+fy+"   "+"tx:"+tx+"ty:"+ty);
				//		this.repaint();
						Graphics g=this.getGraphics();
						if(i==0)
						{
							g.setColor(Color.GREEN);
							g.fillOval(fx,fy,10,10);
						}
						g.setColor(Color.RED);
						g.drawLine(fx+5,fy+5,tx+5,ty+5);
				/*		Graphics2D g2D=(Graphics2D)g;
						g2D.setColor(Color.RED);
						BasicStroke pen=new BasicStroke(5.0f);
						Line2D.Double line=new Line2D.Double(fx+5,fy+5,tx+5,ty+5);
						g2D.setStroke(pen);
						g2D.draw(line);*/
					}
				}
				
			} catch (FileNotFoundException e1) {
				// TODO Auto-generated catch block
				e1.printStackTrace();
			} catch (NumberFormatException e2) {
				// TODO Auto-generated catch block
				e2.printStackTrace();
			} catch (IOException e3) {
				// TODO Auto-generated catch block
				e3.printStackTrace();
			}
		}
	}
}
class JListPane extends JScrollPane implements ActionListener{
	JList jlist=new JList();
	JListPane(){
		this.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_AS_NEEDED);
		this.getViewport().setView(jlist);
	}
	public void actionPerformed(ActionEvent arg0) {
		// TODO Auto-generated method stub
		
	}
}