import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.net.*;
import javax.swing.*;
import javax.swing.text.*;
import javax.swing.plaf.basic.*;
import java.lang.reflect.*;
import java.io.*;

/** スプリングモデルによる描画を行うクラス */
public class SpringModel extends JPanel {
	/** Node一覧 contents are class Node */
	private Vector m_nodes = new Vector();
	/** Edge一覧 contents are class Edge */
	private Vector m_edges = new Vector();

	/** relax thread */
	private Thread m_relax = null;

	/** ノードの追加時にLabelを作成する場合，true
	 * falseにすると始めて描画されるときにLabelを作成する．
	 * 画面表示せずグラフ構造のデータとして利用するときは，
	 * falseにすると良い．
	 */
	private boolean m_createLabel = false;

	/**
	 * 画面の有効領域
	 */
	private double m_availableArea = 0.85;

	/**
	 * ネットワーク密度の計算
	 */
	public double getDensity(){
		int max = countNodes()*(countNodes()-1);
		int count = 0;
		for(int ecnt=0;ecnt<m_edges.size();ecnt++){
			Edge e = (Edge)m_edges.get(ecnt);
			if(e.getFrom().equals(e.getTo())==false){
				if(e.getDirection()==true)
					count += 2;
				else
					count += 1;
			}
		}
		return (double)count/max;
	}
	/**
	 * ノード数の取得
	 */
	public int countNodes(){
		return m_nodes.size();
	}
	/**
	 * エッジ数の取得
	 */
	public int countEdges(){
		return m_edges.size();
	}


	/** class Matrix形式のデータを，ノード，エッジとして登録する
	 */
	public boolean setMatrix(Object m){
		try{
			Class c = Class.forName("Matrix");
			Method getRowName = c.getDeclaredMethod("getRowName",new Class[]{Integer.TYPE});
			Method getColName = c.getDeclaredMethod("getColName",new Class[]{Integer.TYPE});
			Method getAsInteger = c.getDeclaredMethod("getAsInteger",new Class[]{Integer.TYPE,Integer.TYPE});
			Method countRows = c.getDeclaredMethod("countRows",new Class[]{});
			Method countCols = c.getDeclaredMethod("countCols",new Class[]{});

			int max_rows = ((Integer)countRows.invoke(m,new Object[]{})).intValue();
			int max_cols = ((Integer)countCols.invoke(m,new Object[]{})).intValue();

			for(int row=0;row<max_rows;row++){
				String name = (String)getRowName.invoke(m,new Object[]{new Integer(row)});
				addNode(name);
			}

			for(int row=0;row<max_rows;row++){
				String r_name = (String)getRowName.invoke(m,new Object[]{new Integer(row)});
				for(int col=0;col<max_cols;col++){
					String c_name = (String)getColName.invoke(m,new Object[]{new Integer(col)});
					int value = ((Integer)getAsInteger.invoke(m,new Object[]{new Integer(row),new Integer(col)})).intValue();
					if(r_name.equals(c_name)==false && value!=0){
						addEdge(r_name,c_name,true);
					}
				}
			}

		}catch(Exception e){
			e.printStackTrace();
			System.out.println("If you want to use \"setMatrix\" function, you should locate Matrix.class in your CLASSPATH");
			return false;
		}
		return true;
	}

	/** class Matrix 形式でNode，接続一覧を取得する
	  */
	public Object getMatrix(){
		return getMatrix(false);
	}
	/** class Matrix 形式でNode，接続一覧を取得する
		* @param useUserData Matrixの行名称，列名称にユーザデータをセットする
	  */
	public Object getMatrix(boolean useUserData){
		try{
			Class c = Class.forName("Matrix");
			Object o = c.getConstructor(new Class[]{
				Integer.TYPE,Integer.TYPE}).
				newInstance(new Object[]{new Integer(m_nodes.size()),new Integer(m_nodes.size())});
			Method set = c.getDeclaredMethod("set",new Class[]{
				Integer.TYPE,Integer.TYPE,Integer.TYPE});
			Method setAll = c.getDeclaredMethod("setAll",new Class[]{
				Integer.TYPE});
			Method setRowName = c.getDeclaredMethod("setRowName",new Class[]{
				Integer.TYPE,Class.forName("java.lang.String")});
			Method setColName = c.getDeclaredMethod("setColName",new Class[]{
				Integer.TYPE,Class.forName("java.lang.String")});
			Method printMatrixForm = c.getDeclaredMethod("printMatrixForm",new Class[]{});

			setAll.invoke(o,new Object[]{new Integer(0)});
			for(int cnt=0;cnt<m_nodes.size();cnt++){
				Node n = (Node)m_nodes.get(cnt);
				if(useUserData){
					setRowName.invoke(o,new Object[]{new Integer(cnt),n.getUserData().toString()});
					setColName.invoke(o,new Object[]{new Integer(cnt),n.getUserData().toString()});
				}else{
					setRowName.invoke(o,new Object[]{new Integer(cnt),n.getName()});
					setColName.invoke(o,new Object[]{new Integer(cnt),n.getName()});
				}
			}
			for(int cnt=0;cnt<m_edges.size();cnt++){
				Edge e = (Edge)m_edges.get(cnt);
				int i_from=-1,i_to=-1;
				for(int ncnt=0;ncnt<m_nodes.size();ncnt++){
					Node n = (Node)m_nodes.get(ncnt);
					if(n.equals(e.m_from))
						i_from = ncnt;
					if(n.equals(e.m_to))
						i_to = ncnt;
				}
				if(i_from!=-1 && i_to!=-1){
					set.invoke(o,new Object[]{new Integer(i_from),new Integer(i_to),new Integer(1)});
					if(e.m_direction==false)
						set.invoke(o,new Object[]{new Integer(i_to),new Integer(i_from),new Integer(1)});
				}
			}
			return o;
		}catch(Exception e){
			System.out.println(e);
			System.out.println("If you want to use \"getMatrix\" function, you should locate Matrix.class in your CLASSPATH");
			return null;
		}
	}


	/** <pre>
		* ノード間を接続するパス一覧を取得する．
		* 引数には，パス一覧を取得したいノード一覧を取得する．そのノード一覧
		* の全ての組み合わせについて調査する．
		*
		* 戻り値のHashMap(1)の構造は，
	  * HashMap(1)
	  *  key,              value
	  *  -----------------+----------------------------
	  *  node name,        検索対象Node一覧(HashMap(2))
	  *  SpringModel.Node
	  *
	  * HashMap(2)
	  *  key,             value
	  *  ----------------+---------------------------------
	  * 対象Node名,       接続ルート(Vector whose contents
	  * SpringModel.Node  are SpringModel.Edge)
	  *
	  * 検索は，Edgeの方向を無視する．また，同じエッジ数のパスが複数あっても，最初に見つけた最もエッジ数の少ないパスのみを出力する．
		* </pre>
	  */
	public HashMap findPaths(String[] snodes){
		HashMap map = new HashMap();
		Vector nodestemp = new Vector();
		for(int cnt=0;cnt<snodes.length;cnt++){
			Node n = findNode(snodes[cnt]);
			if(n != null){
				map.put(n,new HashMap());
				nodestemp.add(n);
			}
		}
		Node[] nodes = new Node[nodestemp.size()];
		for(int cnt=0;cnt<nodes.length;cnt++)
			nodes[cnt] = (Node)nodestemp.get(cnt);

		for(int cnt=0;cnt<nodes.length;cnt++){
			Vector alreadyChecked = new Vector();
			alreadyChecked.add(nodes[cnt]);
			Vector path = new Vector();
			path.add(new Edge(null,nodes[cnt],true));
			Vector paths = new Vector();
			paths.add(path);
			HashMap tmap = (HashMap)map.get(nodes[cnt]);

			while(paths.size()!=0){
				findPathsIn(nodes,alreadyChecked,paths,tmap);
				// 終了チェック
				if(tmap.size() == nodes.length-1){
					break;
				}
			}
		}
		return map;
	}
	private void findPathsIn(Node[] nodes,Vector alreadyChecked,Vector paths,HashMap tmap){
		Vector npaths = new Vector();
		for(int pcnt=0;pcnt<paths.size();pcnt++){
			Vector path = (Vector)paths.get(pcnt);
			Node source = ((Edge)path.lastElement()).m_to;
			for(int ecnt=0;ecnt<m_edges.size();ecnt++){
				Edge e = (Edge)m_edges.get(ecnt);

				Edge candidateEdge = null;
				if(e.m_direction==false && e.m_to.equals(source)){
					candidateEdge = new Edge(e.m_to,e.m_from,e.m_direction);
				}else if(e.m_from.equals(source)){
					candidateEdge = new Edge(e.m_from,e.m_to,e.m_direction);
				}

				if(candidateEdge!=null && alreadyChecked.contains(candidateEdge.m_to)==false){
					alreadyChecked.add(candidateEdge.m_to);
					Vector npath = new Vector(path);
					npath.add(candidateEdge);
					for(int cnt=0;cnt<nodes.length;cnt++){
						if(nodes[cnt].equals(source)==false && nodes[cnt].equals(candidateEdge.m_to)){
							// 発見
							tmap.put(candidateEdge.m_to,npath);
						}
					}
					// 終了チェック
					if(tmap.size() == nodes.length-1){
						return;
					}
					npaths.add(npath);
				}
			}
		}
		paths.clear();
		paths.addAll(npaths);
		return;
	}

	/** ノード間を接続する最短パスを取得する．最短パスは複数存在する可能性がある．
	 *  よって，1つのパスをVector（要素はノード名(String)）で表して，その配列を戻り値とする．
	 *  この関数は，エッジの向きを考慮する．
	 */
	public Vector[] getShortestPaths(String from,String to){
		return getShortestPaths(from,to,true);
	}
	/** ノード間を接続する最短パスを取得する．最短パスは複数存在する可能性がある．
	 *  よって，1つのパスをVector（要素はノード名(String)）で表して，その配列を戻り値とする．
	 *  この関数は，エッジの向きを無視する．
	 */
	public Vector[] getShortestPathsIgnoreDirection(String from,String to){
		return getShortestPaths(from,to,false);
	}
	/** ノード間を接続する最短パスを取得する．最短パスは複数存在する可能性がある．
	 *  よって，1つのパスをVector（要素はノード名(String)）で表して，その配列を戻り値とする．
	 *  エッジの向きを考慮するか，無視するかを引数で与える．
	 */
	public Vector[] getShortestPaths(String fromStr,String toStr,boolean direction){
		Node from = findNode(fromStr);
		Node to = findNode(toStr);
		if(from==null || to==null){
			System.out.println("could not find the node \""+fromStr+"\"=("+from+"), \""+toStr+"\"=("+to+")");
			return new Vector[0];
		}

		Vector paths = new Vector();
		Vector firstPath = new Vector();
		firstPath.add(from);
		paths.add(firstPath);

		Vector already = new Vector();
		already.add(from);
		Vector retPaths = null;

		do{
			Vector npaths = new Vector();
			for(int pcnt=0;pcnt<paths.size();pcnt++){
				Vector path = (Vector)paths.get(pcnt);
				Node last = (Node)path.lastElement();
				for(int ecnt=0;ecnt<m_edges.size();ecnt++){
					Edge e = (Edge)m_edges.get(ecnt);
					Node next = null;
					if(e.getFrom().equals(last))
						next = e.getTo();
					else if(e.getTo().equals(last) && (direction==false || e.getDirection()==false))
						next = e.getFrom();

					if(next != null){
						Vector npath = new Vector(path);
						npath.add(next);
						if(next.equals(to)){
							if(retPaths == null)
								retPaths = new Vector();
							retPaths.add(npath);
						}else if(already.contains(next)==false){
							already.add(next);
							npaths.add(npath);
						}
					}
				}
			}
			paths.clear();
			paths.addAll(npaths);
		}while(retPaths==null && paths.size()!=0);
		if(retPaths==null)
			return new Vector[0];
		Vector[] nretPaths = new Vector[retPaths.size()];
		for(int cnt=0;cnt<nretPaths.length;cnt++){
			Vector npath = new Vector();
			Vector path = (Vector)retPaths.get(cnt);
			for(int ncnt=0;ncnt<path.size();ncnt++){
				npath.add(((Node)path.get(ncnt)).getName());
			}
			nretPaths[cnt] = npath;
		}
		return nretPaths;
	}

	/** <pre>
		* ノード間を接続するパス一覧を取得する．エッジの向きは無視する．
		* 引数には，パス一覧を取得したいノード一覧を取得する．そのノード一覧
		* の全ての組み合わせについて調査する．
		*
		* 戻り値のHashMap(1)の構造は，
	  * HashMap(1)
	  *  key,              value
	  *  -----------------+----------------------------
	  *  node name,        検索対象Node一覧(HashMap(2))
	  *  SpringModel.Node
	  *
	  * HashMap(2)
	  *  key,             value
	  *  ----------------+---------------------------------
	  * 対象Node名,       接続ルート(Vector whose contents
	  * SpringModel.Node  are SpringModel.Node)
	  *
	  * 検索は，Edgeの方向を無視する．また，同じエッジ数のパスが複数あっても，最初に見つけた最もエッジ数の少ないパスのみを出力する．
		* </pre>
	  */
	public HashMap findPathsIgnoreDirection(String[] snodes){
		HashMap map = new HashMap();
		Vector nodestemp = new Vector();
		for(int cnt=0;cnt<snodes.length;cnt++){
			Node n = findNode(snodes[cnt]);
			if(n != null){
				map.put(n,new HashMap());
				nodestemp.add(n);
			}
		}
		Node[] nodes = new Node[nodestemp.size()];
		for(int cnt=0;cnt<nodes.length;cnt++)
			nodes[cnt] = (Node)nodestemp.get(cnt);

		for(int cnt=0;cnt<nodes.length;cnt++){
			Vector alreadyChecked = new Vector();
			alreadyChecked.add(nodes[cnt]);
			Vector path = new Vector();
			path.add(nodes[cnt]);
			Vector paths = new Vector();
			paths.add(path);
			HashMap tmap = (HashMap)map.get(nodes[cnt]);

			while(paths.size()!=0){
				findPathsIgnoreDirectionIn(nodes,alreadyChecked,paths,tmap);
				// 終了チェック
				if(tmap.size() == nodes.length-1){
					break;
				}
			}
		}
		return map;
	}
	private void findPathsIgnoreDirectionIn(Node[] nodes,
		Vector alreadyChecked,Vector paths,HashMap tmap){

		Vector npaths = new Vector();
		for(int pcnt=0;pcnt<paths.size();pcnt++){
			Vector path = (Vector)paths.get(pcnt);
			Node source = (Node)path.lastElement();
			for(int ecnt=0;ecnt<m_edges.size();ecnt++){
				Edge e = (Edge)m_edges.get(ecnt);
				Node cmp = null;
				if(e.m_from.equals(source))
					cmp = e.m_to;
				else if(e.m_to.equals(source))
					cmp = e.m_from;

				if(cmp != null && alreadyChecked.contains(cmp)==false){
					alreadyChecked.add(cmp);
					Vector npath = new Vector(path);
					npath.add(cmp);
					for(int cnt=0;cnt<nodes.length;cnt++){
						if(nodes[cnt].equals(source)==false && nodes[cnt].equals(cmp)){
							// 発見
							Object old = tmap.put(cmp,npath);
						}
					}
					// 終了チェック
					if(tmap.size() == nodes.length-1){
						return;
					}
					npaths.add(npath);
				}
			}
		}
		paths.clear();
		paths.addAll(npaths);
		return;
	}

	/** vector class */
	class CVector {
		/** メンバ変数 */
		double m_x;
		/** メンバ変数 */
		double m_y;
		/** コンストラクタ
		 * @param x x軸値
		 * @param y y軸値
		 */
		CVector(double x,double y){
			m_x = x;
			m_y = y;
		}
		/** ベクトルのプラス <BR>
		 *  JAVAでの演算子のオーバーロード方法が分かれば、そちらに変更する。
		 */
		CVector plus(CVector cmp){
			m_x += cmp.m_x;
			m_y += cmp.m_y;
			return this;
		}
		/** ベクトルの始点を中心に回転したベクトルを求める */
		CVector rotate(double rad){
			/* 回転行列は
			   | c -s ||x|
			   | s  c ||y|
			*/
			double c = Math.cos(rad);
			double s = Math.sin(rad);
			return new CVector(m_x*c-m_y*s,m_x*s+m_y*c);
		}
		/** 長さを返す。
		 */
		double getLength(){
			return Math.sqrt(Math.pow(m_x,2)+Math.pow(m_y,2));
		}
		/** 現在のx,yの値を使用して、角度(radians)を返す
		 * @return 角度(radians)
		 */
		double getRad(){
			// 返す角度の範囲は 0 <= rad < 2*Math.PI
			if(m_y == 0){
				if(m_x >= 0)
					return 0;
				else
					return Math.PI;
			}else if(m_x == 0){
				if(m_y >= 0)
					return Math.PI/2;
				else
					return 3*Math.PI/2;
			}
			double rad = Math.acos(m_x/Math.sqrt(Math.pow(m_x,2)+Math.pow(m_y,2)));
			if(m_y < 0)
				rad = (2*Math.PI)-rad;
			return rad;
		}
		/** 引数として与えられたベクトルに対して自分のベクトルをプラス方向
		 * に回転すれば角度が近づくか、マイナス方向に回転すれば近づくかを返
		 * す。<br>
		 * 例えば、引数ベクトルが(1,1) 自分のベクトルが(1,-1)の場合、自分の
		 * ベクトルをマイナス方向に回転させると、引数ベクトルに近づくのでこ
		 * の関数はマイナス方向を示す -1 を返す。
		 * @param vec 対象となるベクトル
		 * @return 1の場合はプラス方向、2の場合はマイナス方向。
		 */
		int towordPlusMinus(CVector vec){
			if((m_x == 0 && m_y == 0) ||
				(vec.m_x == 0 && vec.m_y == 0)){
				return 0;
			}
			int nDiff;
			switch(nDiff = diffWorld(vec)){
			case 0:
			case 2:
				double x = ((double)vec.m_y/vec.m_x)-((double)m_y/m_x);
				if(x == 0)
					return 0;
				else{
					if(nDiff==0)
						return x>0?1:-1;
					else
						return x>0?-1:1;
				}
			case -1:
				return -1;
			case 1:
				return 1;
			}
			return 0;	// bug
		}
		/** {@link #getWorld()}により求められる象現の差分を求める。同じ象現
		 * の場合、差分は０。隣の象現に互いがある場合、１。対角線上に互いの
		 * 象現が存在する場合、２となる。
		 * @param vec 比較対象のベクトル
		 * @return 差分値(0-2)
		 */
		int diffWorld(CVector vec){
			int w = getWorld();
			int w2 = vec.getWorld();
			if(w == w2)
				return 0;
			else if(Math.abs(w-w2)==2)
				return 2;
			else if(Math.max(w,w2)-Math.min(w,w2)==1)
				return 1;
			else
				return -1;
		}
		/**
		 * m_x,m_yを以下の4つの象現に分ける<br>
		 * <pre>
		 * 1.  ○      2.   ●    3.  |      4.  |
		 *     | |        | |         |          |
		 *     +-●      ○-+-     ●-+-        -+-○
		 *     |            |       | |          | |
		 *                            ○         ●
		 * </pre>
		 * @return 象現の番号(1-4)
		 */
		int getWorld(){
			if(m_x > 0 && m_y >= 0){
				return 1;
			}else if(m_x <= 0 && m_y > 0){
				return 2;
			}else if(m_x < 0 && m_y <= 0){
				return 3;
			}else if(m_x >= 0 && m_y < 0){
				return 4;
			}
			return 0;// bug
		}
		public double radToDeg(double rad){
			return rad*180/Math.PI;
		}
		public double degToRad(double deg){
			return deg*Math.PI/180;
		}
	}

	/** relax */
	public void relax(){
		final SpringModel own = this;
		m_relax = new Thread(){
			public void run(){
				while(m_relax!=null){
					// initialize
					for(int ncnt=0;ncnt<own.m_nodes.size();ncnt++){
						Node n = (Node)own.m_nodes.get(ncnt);
						n.clearDxy();
					}

					// spring
					for(int ecnt=0;ecnt<own.m_edges.size();ecnt++){
						Edge e = (Edge)own.m_edges.get(ecnt);
						if(e.m_from.m_label!=null && e.m_to.m_label!=null && 
							(e.m_from.getFixed()==false || e.m_to.getFixed()==false)){
							Point p_from = e.m_from.m_label.getLocation();
							Point p_to = e.m_to.m_label.getLocation();
							CVector vec = new CVector(p_from.x-p_to.x,p_from.y-p_to.y);

							double div = (vec.getLength()-e.getLength0())/2;

							double effect = 1.0-(1.0/(1.0+Math.exp(-1*(Math.abs(div)-5.0)/2)));
							if(effect < 0.1)	effect = 0.1;
							div *= effect;
							double dx = div*Math.cos(vec.getRad());
							double dy = div*Math.sin(vec.getRad());

							e.m_to.addDxy(dx,dy);
							e.m_from.addDxy(-dx,-dy);
						}
					}

					// repulsion
					double effect = 5000;
					for(int ncnt1=0;ncnt1<own.m_nodes.size()-1;ncnt1++){
						Node n1 = (Node)own.m_nodes.get(ncnt1);
						if(n1.getFixed()==false && n1.m_label!=null){
							for(int ncnt2=ncnt1+1;ncnt2<own.m_nodes.size();ncnt2++){
								Node n2 = (Node)own.m_nodes.get(ncnt2);
								if(own.isLinkedIgnoreDirection(n1,n2)==false && n2.m_label!=null){
									Point p1 = n1.m_label.getLocation();
									Point p2 = n2.m_label.getLocation();
									CVector vec = new CVector((double)p1.x-p2.x,(double)p1.y-p2.y);
									double len = vec.getLength();
									double f = effect/Math.pow(len,2);

									n1.addDxy(vec.m_x*f/len/2,vec.m_y*f/len/2);
									if(n2.getFixed() == false){
										n2.addDxy(-vec.m_x*f/len/2,-vec.m_y*f/len/2);
									}
								}
							}
						}
					}

					// dx,dyの適用
					Dimension d = own.getSize();
					int noarea_w = (int)(d.width*(1.0-m_availableArea)/2+0.5);
					int noarea_h = (int)(d.height*(1.0-m_availableArea)/2+0.5);
					double all = 0;
					for(int ncnt=0;ncnt<own.m_nodes.size();ncnt++){
						Node n = (Node)own.m_nodes.get(ncnt);
						if(n.m_label != null && n.getFixed()==false){
							Point p = n.m_label.getLocation();
							int newx = (int)(p.x+n.m_dx+0.5);
							if(newx < noarea_w)
								newx = noarea_w;
							if(newx > d.width-noarea_w)
								newx = d.width-noarea_w;
							int newy = (int)(p.y+n.m_dy+0.5);
							if(newy < noarea_h)
								newy = noarea_h;
							if(newy > d.height-noarea_h)
								newy = d.height-noarea_h;
							all += Math.abs(newx-p.x)+Math.abs(newy-p.y);
							n.m_label.setLocation(newx,newy);
						}
					}

					// repaint
					own.repaint();
					if(m_nodes.size()==0 || all/m_nodes.size()<1.4)
						try{sleep(500);}catch(InterruptedException e){}
					else
						try{sleep(50);}catch(InterruptedException e){}
				}
			}
		};
		m_relax.setPriority(Thread.MIN_PRIORITY);
		m_relax.start();
	}
	/** stop relax */
	public void stopRelax(){
		m_relax = null;
	}
	public boolean getRelax(){
		return m_relax!=null;
	}

	/** Nodeを表示するためのラベル */
	class NodeLabel extends JLabel{
		private Node m_parent;
		private Image m_image = null;

		public NodeLabel(String n,Node parent,Image image){
			super(n);
			m_parent = parent;
			m_image = image;
		}
		public void paint(Graphics graphics){
			Dimension d = getSize();
			Color b = graphics.getColor();
			if(m_parent.getFixed())
				graphics.setColor(Color.pink);
			else
				graphics.setColor(Color.white);
			Point p = getLocation();
			graphics.fillRect(p.x,p.y,d.width,d.height);

			graphics.setColor(Color.black);
			FontMetrics fm = graphics.getFontMetrics();
			graphics.drawString(getText(),p.x+1,p.y+fm.getHeight()-4);

			if(m_image != null){
				int imageWidth = 41;
				int imageHeigth = 60;
				graphics.drawImage(m_image,(int)(p.x+d.width/2-imageWidth/2+0.5),p.y+fm.getHeight()+2,
					imageWidth,imageHeigth,null);
			}
			graphics.setColor(b);
		}
	}
	/** Nodeをあらわすクラス */
	class Node implements Comparable{
		private String m_name;
		private HashMap m_userData = new HashMap();
		private Image m_image = null;
		private JLabel m_label = null;
		private Point m_backupPosition = null;
		private boolean m_fixed = false;
		private boolean m_temporaryFixed = false;
		private double m_dx=0;
		private double m_dy=0;
		private boolean m_visible = true;

		public boolean getVisible(){
			return m_visible;
		}
		public void setVisible(boolean v){
			m_visible = v;
		}
		public void setLocation(int x,int y){
			m_label.setLocation(x,y);
		}
		public void addDxy(double dx,double dy){
			m_dx += dx;
			m_dy += dy;
		}
		public void clearDxy(){
			m_dx = m_dy = 0;
		}

		public boolean getFixed(){
			return m_fixed || m_temporaryFixed;
		}
		public boolean getFixedIgnoreTemporary(){
			return m_fixed;
		}
		public void setFixed(boolean data){
			m_fixed = data;
		}
		public void setTemporaryFixed(boolean data){
			m_temporaryFixed = data;
		}

		public void backupPosition(){
			if(m_label != null){
				m_backupPosition = m_label.getLocation(null);
			}else{
				m_backupPosition = null;
			}
		}
		public void restorePosition(){
			if(m_backupPosition!=null&&m_label!=null){
				m_label.setLocation(m_backupPosition.x,m_backupPosition.y);
			}
			m_backupPosition = null;
		}
		public Node(String name){
			this(name,null);
		}
		public Node(String name,Object userData){
			setName(name);
			setUserData(userData);
		}
		public Node(String name,Object userData,Image image){
			setName(name);
			setUserData(userData);
			setImage(image);
		}
		public Node(Node node){
			setName(node.getName());
			setUserData(node.getUserData());
		}
		public String toString(){
			return m_name;
		}
		public String getName(){
			return m_name;
		}
		public void setName(String data){
			m_name = data;
		}
		public Object getUserData(){
			return getUserData(0);
		}
		public Object getUserData(int index){
			return m_userData.get(new Integer(index));
		}
		public void setUserData(Object data){
			setUserData(0,data);
		}
		public void setUserData(int index,Object data){
			m_userData.put(new Integer(index),data);
		}
		public Image getImage(){
			return m_image;
		}
		public void setImage(Image data){
			m_image = data;
		}
		public boolean equals(Object obj){
			if(obj instanceof Node){
				return ((Node)obj).m_name.equals(m_name) &&
					((Node)obj).m_userData.equals(m_userData);
			}
			return false;
		}
		public int compareTo(Object o){
			return toString().compareTo(o.toString());
		}
	}
	/** エッジをあらわすクラス */
	class Edge {
		private int m_length0 = 200;
		private Node m_from;
		private Node m_to;
		private boolean m_direction;

		public Node getTo(){
			return m_to;
		}
		public Node getFrom(){
			return m_from;
		}
		public boolean getDirection(){
			return m_direction;
		}
		public boolean equals(Object obj){
			if(obj instanceof Edge){
				Edge e = (Edge)obj;
				if(e.m_direction!=m_direction)
					return false;
				if(m_direction){
					return e.m_from.equals(m_from) && e.m_to.equals(m_to);
				}else{
					return (e.m_from.equals(m_from) && e.m_to.equals(m_to)) ||
						(e.m_from.equals(m_to) && e.m_to.equals(m_from));
				}
			}
			return false;
		}
/*
		public Edge(Node from,Node to){
			this(from,to,true);
		}
*/
		public Edge(Node from,Node to,boolean direction){
			m_from = from;
			m_to = to;
			m_direction = direction;
		}
		public int getLength0(){
			return m_length0;
		}
		public String toString(){
			if(m_direction)
				return ""+m_from+"->"+m_to;
			else
				return ""+m_from+"--"+m_to;
		}
	}
	/** constructor */
	public SpringModel(boolean createLabel){
		this();
		m_createLabel = createLabel;
	}
	/** constructor */
	public SpringModel(){
		final SpringModel own = this;
		setLayout(new FlowLayout(){
			public void layoutContainer(Container target){
				for(int cnt=0;cnt<own.m_nodes.size();cnt++){
					((Node)(own.m_nodes.get(cnt))).backupPosition();
//System.out.println(((Node)(own.m_nodes.get(cnt))).m_label.getLocation());
				}
				super.layoutContainer(target);
				for(int cnt=0;cnt<own.m_nodes.size();cnt++){
					((Node)(own.m_nodes.get(cnt))).restorePosition();
//System.out.println(((Node)(own.m_nodes.get(cnt))).m_label.getLocation());
				}
			}
		});
		addMouseListener(new MouseAdapter(){
			public void mouseReleased(MouseEvent e){
				if(e.isPopupTrigger()){
					JPopupMenu popup = new JPopupMenu();
					JMenuItem i = new JMenuItem(own.getRelax()?"stop relax":"relax");
					i.addActionListener(new ActionListener(){
						public void actionPerformed(ActionEvent e){
							if(own.getRelax())
								own.stopRelax();
							else
								own.relax();
						}
					});
					popup.add(i);
					JMenuItem i2 = new JMenuItem("find node");
					i2.addActionListener(new ActionListener(){
						public void actionPerformed(ActionEvent e){
							String target = JOptionPane.showInputDialog(
								own,"Please input node name");
							if(target != null){
								Node[] nodes = own.findNodes(target);
								for(int ncnt=0;ncnt<nodes.length;ncnt++)
									nodes[ncnt].setFixed(true);
							}
						}
					});
					popup.add(i2);
					JMenuItem i3 = new JMenuItem("circle");
					i3.addActionListener(new ActionListener(){
						public void actionPerformed(ActionEvent e){
							own.stopRelax();
							Dimension d = own.getSize();
							int area_w = (int)(d.width*m_availableArea/2+0.5);
							int area_h = (int)(d.height*m_availableArea/2+0.5);
							int r = Math.min(area_w,area_h);
							int center_x = d.width/2-(d.width/2-area_w)/2;
							int center_y = d.height/2-(d.height/2-area_h)/2;

							Object[] nodes = own.getNodes();
							double addrad = 2*Math.PI/nodes.length;

							double rad = 0;
							for(int n=0;n<nodes.length;n++){
								double x = center_x+r*Math.cos(rad);
								double y = center_y+r*Math.sin(rad);

								((SpringModel.Node)nodes[n]).setLocation((int)x,(int)y);
								rad += addrad;
							}
							own.repaint();
						}
					});
					popup.add(i3);
					popup.show(e.getComponent(),e.getX(),e.getY());
				}
			}
		});
	}

	/** 2つのNodeが接続しているかどうかを確認する */
	public boolean isLinked(String fromStr,String toStr){
		return isLinked(findNode(fromStr),findNode(toStr));
	}
	/** 2つのNodeが接続しているかどうかを確認する */
	public boolean isLinked(Node from,Node to){
		for(int ecnt=0;ecnt<m_edges.size();ecnt++){
			Edge e = (Edge)m_edges.get(ecnt);
			if((e.m_from.equals(from) && e.m_to.equals(to)) ||
				 (e.getDirection()==false && e.m_from.equals(to) && e.m_to.equals(from))){
				return true;
			}
		}
		return false;
	}
	/** 2つのNodeが直接接続しているかどうかを確認する(方向は関係する) */
	public boolean isLinkedIgnoreDirection(String fromStr,String toStr){
		return isLinkedIgnoreDirection(findNode(fromStr),findNode(toStr));
	}
	/** 2つのNodeが直接接続しているかどうかを確認する(方向は関係する) */
	public boolean isLinkedIgnoreDirection(Node from,Node to){
		for(int ecnt=0;ecnt<m_edges.size();ecnt++){
			Edge e = (Edge)m_edges.get(ecnt);
			if((e.m_from.equals(from) && e.m_to.equals(to)) ||
				(e.m_from.equals(to) && e.m_to.equals(from)))
				return true;
		}
		return false;
	}


	/** 新しいNodeのラベルを作成する */
	private void addNewLabel(final Node n){
		final Point p_initial = new Point();
		final SpringModel parentPanel = this;
		Dimension d = getSize(null);
		n.m_label = new NodeLabel(n.getName(),n,n.getImage());
		Object userData = n.getUserData();
		if(userData != null)
			n.m_label.setToolTipText(userData.toString());
		n.m_label.addMouseListener(new MouseAdapter(){
			public void mousePressed(MouseEvent e){
				p_initial.x = e.getX();
				p_initial.y = e.getY();
			}
			public void mouseReleased(MouseEvent e){
				n.setTemporaryFixed(false);
				parentPanel.repaint();
				if(e.isPopupTrigger()){
					n.setTemporaryFixed(true);
					JPopupMenu popup = new JPopupMenu(){
						protected void firePopupMenuCanceled(){
							super.firePopupMenuCanceled();
							n.setTemporaryFixed(false);
						}
					};
					JMenuItem i = new JMenuItem(n.getFixedIgnoreTemporary()?"free":"fixed");
					i.addActionListener(new ActionListener(){
						public void actionPerformed(ActionEvent e){
							n.setTemporaryFixed(false);
							n.setFixed(!n.getFixed());
						}
					});
					popup.add(i);
					JMenuItem i2= new JMenuItem("find path");
					i2.addActionListener(new ActionListener(){
						public void actionPerformed(ActionEvent e){
							n.setTemporaryFixed(false);
							String target = JOptionPane.showInputDialog(
								parentPanel,"Please input target node name from \""+n.getName()+"\"");
							if(target != null){
								Vector[] paths = parentPanel.getShortestPaths(n.getName(),target);
								String ret = paths.length==0?"no path":"";
								for(int cnt=0;cnt<paths.length;cnt++){
									ret += "path "+(cnt+1)+"\r\n";
									for(int pcnt=0;pcnt<paths[cnt].size();pcnt++){
										if(pcnt!=0)
											ret += " -> ";
										ret += paths[cnt].get(pcnt);
									}
									ret += "\r\n";
								}
								JOptionPane.showMessageDialog(parentPanel,ret);
/*
								HashMap map = parentPanel.findPathsIgnoreDirection(
									new String[]{n.getName(),target});
//System.out.println(map.size());
								HashMap tmap = (HashMap)map.get(findNode(n.getName()));
//System.out.println(tmap);
								Vector path = (Vector)tmap.get(findNode(target));
								if(path == null){
									System.out.println("could not find path");
								}else{
									for(int pcnt=0;pcnt<path.size();pcnt++){
										System.out.println(path.get(pcnt));
									}
								}
*/
							}
						}
					});
					popup.add(i2);
					popup.show(e.getComponent(),e.getX(),e.getY());
				}
			}
		});
		n.m_label.addMouseMotionListener(new MouseMotionAdapter(){
			public void mouseDragged(MouseEvent e){
//System.out.println(e);
				n.setTemporaryFixed(true);
				Point p = n.m_label.getLocation();
				n.m_label.setLocation(p.x+e.getX()-p_initial.x,p.y+e.getY()-p_initial.y);
				parentPanel.repaint();
			}
		});
		this.add(n.m_label);
		for(int cnt=0;cnt<m_nodes.size();cnt++)
			((Node)(m_nodes.get(cnt))).backupPosition();
		this.validate();
		for(int cnt=0;cnt<m_nodes.size();cnt++)
			((Node)(m_nodes.get(cnt))).restorePosition();
		n.m_label.setLocation((int)(d.width*m_availableArea*Math.random()+0.5),
			(int)(d.height*0.65*Math.random()+0.5));
	}
	/** 表示処理 */
	public void paint(Graphics graphics){
//		super.paint(graphics);
		Color b = graphics.getColor();
		graphics.setColor(getBackground());
		Dimension d = getSize();
		graphics.fillRect(0,0,d.width,d.height);

		// initialize node
		for(int cnt=0;cnt<m_nodes.size();cnt++){
			Node n = (Node)m_nodes.get(cnt);
			if(n.m_label==null){
				addNewLabel(n);
			}
		}

		// paint edges
		graphics.setColor(Color.black);
		for(int cnt=0;cnt<m_edges.size();cnt++){
			Edge e = (Edge)m_edges.get(cnt);
			if(e.m_from.getVisible() && e.m_to.getVisible()){
				Point from = e.m_from.m_label.getLocation();
				Dimension sfrom = e.m_from.m_label.getSize();
				Point to = e.m_to.m_label.getLocation();
				Dimension sto = e.m_to.m_label.getSize();

				int xLow = from.x+sfrom.width/2;
				int yLow = from.y+sfrom.height/2;
				int xHigh = to.x+sto.width/2;
				int yHigh = to.y+sto.height/2;
				if(e.m_direction){
					if(Math.abs(xHigh-xLow)>Math.abs(yHigh-yLow))
						graphics.fillPolygon(new int[]{xLow,xLow,xHigh},new int[]{yLow-2,yLow+2,yHigh},3);
					else
						graphics.fillPolygon(new int[]{xLow-2,xLow+2,xHigh},new int[]{yLow,yLow,yHigh},3);
				}else{
					graphics.drawLine(xLow,yLow,xHigh,yHigh);
				}
			}
		}

		// repaint node (first paint is done in super.paint(..))
		for(int cnt=0;cnt<m_nodes.size();cnt++){
			Node n = (Node)m_nodes.get(cnt);
			if(n!=null && n.m_label!=null && n.getVisible())
				n.m_label.paint(graphics);
		}

		graphics.setColor(b);
	}
	/** Node, Edgeのクリア */
	public void clear(){
		clearNodes();
		clearEdges();
		this.removeAll();
	}
	public void clearNodes(){
		m_nodes.clear();
	}
	public void clearEdges(){
		m_edges.clear();
	}
	/** Nodeの追加 */
	public Node addNode(String name){
		return addNode(name,null);
	}
	/** Nodeの追加（ユーザデータ付） */
	public Node addNode(String name,Object userData){
		return addNode(name,userData,(Image)null);
	}
	/** Nodeの追加（ユーザデータ，イメージファイル名 付） */
	public Node addNode(String name,Object userData,String imageURL){
		Image image = null;
		if(imageURL != null){
			try{
				image = Toolkit.getDefaultToolkit().getImage(new URL(imageURL));
			}catch(MalformedURLException e){
				e.printStackTrace();
			}
		}
		return addNode(name,userData,image);
	}
	/** Nodeの追加（ユーザデータ，イメージファイル名 付） */
	public Node addNode(String name,Object userData,Image image){
		return addNode(new Node(name,userData,image));
	}
	/** Nodeの追加（class Node形式） */
	public Node addNode(Node n){
		m_nodes.add(n);
		if(m_createLabel)
			addNewLabel(n);
		repaint();
		return n;
	}
	/** エッジの追加 */
	public Edge addEdge(Node from,Node to){
		return addEdge(from,to,true);
	}
	/** エッジの追加（方向が有効か，無効かを指定） */
	public Edge addEdge(Node from,Node to,boolean direction){
		return addEdge(new Edge(from,to,direction));
	}
	/** エッジの追加（ノード名称による指定） */
	public Edge addEdge(String from,String to){
		return addEdge(from,to,true);
	}
	/** エッジの追加：方向付き（ノード名称による指定） */
	public Edge addEdge(String from,String to,boolean direction){
		Node f_node = findNode(from);
		Node t_node = findNode(to);
		if(f_node!=null && t_node!=null)
			return addEdge(f_node,t_node,direction);
		return null;
	}
	/** エッジの追加 */
	public Edge addEdge(Edge e){
		boolean added = false;
		for(int cnt=0;cnt<m_edges.size();cnt++){
			Edge ecmp = (Edge)m_edges.get(cnt);
			if(e.m_direction==false){
				// 追加するEdgeに方向がない場合，既に方向のある
				// Edgeを削除して新しく追加する．
				if((e.m_to==ecmp.m_to && e.m_from==ecmp.m_from) ||
					(e.m_to==ecmp.m_from && e.m_from==ecmp.m_to)){
					if(ecmp.m_direction){
//System.out.println(" addEdge remove "+ecmp);
//System.out.println(" addEdge "+e);
						m_edges.remove(ecmp);
						m_edges.add(e);
					}
					added = true;
				}
			}else{
				// 追加するEdgeに方向がある場合，既に方向のある
				// Edgeと合わせて双方向になる場合は，方向なしEdgeを
				// 追加する
				if(ecmp.m_direction){
					if(e.m_to==ecmp.m_from && e.m_from==ecmp.m_to){
//System.out.println(" addEdge remove "+ecmp);
//System.out.println(" addEdge "+new Edge(e.m_from,e.m_to,false));
						m_edges.remove(ecmp);
						m_edges.add(new Edge(e.m_from,e.m_to,false));
						added = true;
					}else if(e.m_to==ecmp.m_to && e.m_from==ecmp.m_from){
						added = true;
					}
				}else{
				if((e.m_to==ecmp.m_to && e.m_from==ecmp.m_from) ||
					(e.m_to==ecmp.m_from && e.m_from==ecmp.m_to)){
						added = true;
					}
				}
			}
		}
		if(added==false){
//System.out.println(" addEdge "+e);
			m_edges.add(e);
		}
		return e;
	}
	/** ノード一覧の取得 */
	public Object[] getNodes(){
		return m_nodes.toArray();
	}
	/** エッジ一覧の取得 */
	public Object[] getEdges(){
		return m_edges.toArray();
	}
	/** ノードの検索（ユーザデータ） */
	public Node findNode(int index,Object userData){
		for(int cnt=0;cnt<m_nodes.size();cnt++){
			Node n = (Node)m_nodes.get(cnt);
			Object cmp = n.m_userData.get(new Integer(index));
			if(cmp!=null && cmp.equals(userData))
				return n;
		}
		return null;
	}
	/** ノードの検索（名前の完全一致） */
	public Node findNode(String name){
		for(int cnt=0;cnt<m_nodes.size();cnt++){
			Node n = (Node)m_nodes.get(cnt);
			if(n.getName().equals(name))
				return n;
		}
		return null;
	}
	/** ノードの検索（名前の前方一致） */
	public Node[] findNodes(String name){
		Vector res = new Vector();
		for(int cnt=0;cnt<m_nodes.size();cnt++){
			Node n = (Node)m_nodes.get(cnt);
			if(n.getName().startsWith(name))
				res.add(n);
		}
		Node[] resnodes = new Node[res.size()];
		for(int cnt=0;cnt<resnodes.length;cnt++)
			resnodes[cnt] = (Node)res.get(cnt);
		return resnodes;
	}
	/** エッジの検索（方向を意識する） */
	public Edge findEdge(String from,String to){
		for(int cnt=0;cnt<m_edges.size();cnt++){
			Edge e = (Edge)m_edges.get(cnt);
			if(e.m_from.getName().equals(from) && e.m_to.getName().equals(to))
				return e;
		}
		return null;
	}
	/** エッジの検索（方向を無視） */
	public Edge findEdgeIgnoreDirection(String from,String to){
		for(int cnt=0;cnt<m_edges.size();cnt++){
			Edge e = (Edge)m_edges.get(cnt);
			if((e.m_from.getName().equals(from) && e.m_to.getName().equals(to)) ||
				e.m_from.getName().equals(to) && e.m_to.getName().equals(from))
				return e;
		}
		return null;
	}

	/** フレームを自ら生成して，表示する．フレームを消去すると，プログラムが終了する． */
	public void show(){
		JFrame frame = new JFrame("SpringModel");
		frame.addWindowListener(new WindowAdapter(){
			public void windowClosing(WindowEvent e){System.exit(0);}
		});
		frame.setContentPane(this);
		frame.pack();
		frame.setSize(new Dimension(400,300));
		frame.show();

		relax();
	}

	/** ネットワーク密度100%の部分グラフを抽出する． */
	SpringModel[] subGroups(){
		Vector candidates = new Vector();
		for(int cnt=0;cnt<m_nodes.size();cnt++){
			candidates.add(new Node[]{(Node)m_nodes.get(cnt)});
		}

		Vector fixed = new Vector();
		do{
/*
System.out.println("candidates :");
for(int cnt=0;cnt<candidates.size();cnt++){
Node[] member = (Node[])candidates.get(cnt);
for(int mcnt=0;mcnt<member.length;mcnt++)
System.out.print(member[mcnt]+",");
System.out.println();
}
System.out.println(": candidates");
*/
			Node[] member = (Node[])candidates.get(0);
			boolean baddednewcandidate = false;
			for(int ncnt=0;ncnt<m_nodes.size();ncnt++){
				Node node = (Node)m_nodes.get(ncnt);
				boolean bmember = false;
				for(int mcnt=0;mcnt<member.length;mcnt++){
					if(member[mcnt].equals(node)){
						bmember = true;
						break;
					}
				}

				if(bmember==false){
					boolean balllinked = true;
					for(int mcnt=0;mcnt<member.length;mcnt++){
						if(isLinked(member[mcnt],node)==false || isLinked(node,member[mcnt])==false){
/*
System.out.println(":: "+member[mcnt]+","+node+" "+isLinked(member[mcnt],node)+","+isLinked(node,member[mcnt]));
*/
							balllinked = false;
							break;
						}
					}
/*
System.out.println("balllinked ("+node+"):"+balllinked);
*/

					if(balllinked==true){
						Node[] nmember = new Node[member.length+1];
						System.arraycopy(member,0,nmember,0,member.length);
						nmember[nmember.length-1] = node;
						Arrays.sort(nmember);
/*
System.out.print("new candidate:");
for(int cnt=0;cnt<nmember.length;cnt++)
System.out.print(nmember[cnt]+",");
System.out.println();
*/

						for(int ccnt=1;ccnt<candidates.size();ccnt++){
							Node[] cmember = (Node[])candidates.get(ccnt);

							boolean ballcontents = true;
							for(int cmcnt=0;cmcnt<cmember.length;cmcnt++){
								if(Arrays.binarySearch(nmember,cmember[cmcnt])<0){
									ballcontents = false;
									break;
								}
							}
							if(ballcontents==true){
/*
System.out.print("remove candidate:");
for(int cnt=0;cnt<cmember.length;cnt++)
System.out.print(cmember[cnt]+",");
System.out.println();
*/
								candidates.remove(ccnt);
								ccnt--;
							}
						}
						candidates.add(nmember);
						baddednewcandidate = true;
					}
				}
			}
			if(baddednewcandidate==false){
				fixed.add(member);
			}
			candidates.remove(0);
		}while(candidates.size()!=0);
		SpringModel[] nets = new SpringModel[fixed.size()];
		for(int cnt=0;cnt<nets.length;cnt++){
			nets[cnt] = new SpringModel();
			Node[] nodes = (Node[])fixed.get(cnt);
			for(int ncnt=0;ncnt<nodes.length;ncnt++){
				nodes[ncnt] = nets[cnt].addNode(new Node(nodes[ncnt]));
			}
			for(int ncnt1=0;ncnt1<nodes.length-1;ncnt1++){
				for(int ncnt2=ncnt1;ncnt2<nodes.length;ncnt2++){
					nets[cnt].addEdge(nodes[ncnt1],nodes[ncnt2],false);
				}
			}
		}
		return nets;
	}

	/** debug main */
	public static void main(String[] args){
		SpringModel sp = new SpringModel();
		// set data
		sp.addNode("node1");
		sp.addNode("node2");
		sp.addNode("node3");
		sp.addEdge("node1","node2",false);
		sp.addEdge("node1","node3",false);
		sp.addEdge("node2","node3",false);

		sp.addNode("node4");
		sp.addEdge("node4","node1",false);
		sp.addEdge("node4","node2",false);
		sp.addEdge("node4","node3",true);
		sp.show();

/*
		System.out.println(sp.isLinked("node2","node1"));
		SpringModel[] subs = sp.subGroups();
		for(int cnt=0;cnt<subs.length;cnt++){
			subs[cnt].show();
		}
*/
	}
}