import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import javax.swing.*;

// スプリングモデル (「マグネティック・スプリング・モデルによるグラフ描画法について　三末　和男・杉山　公造　（株）富士通研究所　情報社会科学研究所）
class SpringModel {
  private Vector<String> nodes = new Vector<String>();
  private Vector<Rectangle> node_pos = new Vector<Rectangle>();
  private Vector<Boolean> node_fixed = new Vector<Boolean>();
  private Vector<int[]> edges = new Vector<int[]>();
  private Point scr = new Point();
  private int length0 = 200;
  private int dragging_node = -1;
  private Point dragging_node_ofset = new Point();
  private boolean dragging_node_fixed;
  private int popupmenu_node = -1;
  private boolean popupmenu_node_fixed;
  private Container parent;
  
  public SpringModel(int screen_w,int screen_h,Container parent){
    this.parent = parent;
    scr.x = screen_w;
    scr.y = screen_h;
  }
  public SpringModel(int screen_w,int screen_h){
    this(screen_w,screen_h,null);
  }
  public synchronized boolean save(String filename){
    String[] strs = new String[edges.size()];
    for(int cnt=0;cnt<strs.length;cnt++){
      int[] e = edges.get(cnt);
      strs[cnt] = nodes.get(e[0])+","+nodes.get(e[1])+","+e[2];
    }
    saveStrings(filename,strs);
    return true;
  }
  public synchronized boolean load(String filename){
    String[] strs = loadStrings(filename);
    if(strs==null){
      return false;
    }
    clear();
    for(int cnt=0;cnt<strs.length;cnt++){
      String[] parts = strs[cnt].split(",");
      if(parts.length==3){
        addEdge(parts[0],parts[1],parts[2].equals("1"));
      }
    }
    return true;
  }
  public void clear(){
    nodes.clear();
    node_pos.clear();
    node_fixed.clear();
    edges.clear();
  }
  public synchronized void draw(){
    stroke(200);
    fill(230);
    for(int cnt=0;cnt<edges.size();cnt++){
      int[] e = edges.get(cnt);
      double[] p0 = {node_pos.get(e[0]).getCenterX(),node_pos.get(e[0]).getCenterY()};
      double[] p1 = {node_pos.get(e[1]).getCenterX(),node_pos.get(e[1]).getCenterY()};
      if(e[2]==0){
        strokeWeight(2);
        line((float)p0[0],(float)p0[1],(float)p1[0],(float)p1[1]);
      }else{
        strokeWeight(1);
        double r = Math.atan2(p0[1]-p1[1],p0[0]-p1[0]);
        double len = 3;
        beginShape();
        vertex((float)(p0[0]+len*Math.cos(r+Math.PI/2)),(float)(p0[1]+len*Math.sin(r+Math.PI/2)));
        vertex((float)(p0[0]+len*Math.cos(r-Math.PI/2)),(float)(p0[1]+len*Math.sin(r-Math.PI/2)));
        vertex((float)p1[0],(float)p1[1]);
        endShape();
      }
    }
    stroke(255);
    strokeWeight(2);
    for(int cnt=0;cnt<nodes.size();cnt++){
      Rectangle rc = node_pos.get(cnt);
      fill(node_fixed.get(cnt)?100:0);
      rect(rc.x,rc.y,rc.width,rc.height);
      fill(255);
      text(nodes.get(cnt),rc.x+5,rc.y+rc.height-6);
    }
  }
  private Rectangle getTextRect(String text,int x,int y){
    Graphics g = parent.getGraphics();
    Rectangle2D bounds = g.getFontMetrics().getStringBounds(text,g);
    int w = (int)bounds.getWidth()+10;
    int h = (int)bounds.getHeight()+6;
    return new Rectangle(x-w/2,y-h/2,w,h);
  }
  public int getNodeCount(){
    return nodes.size();
  }
  public int getEdgeCount(){
    return edges.size();
  }
  public synchronized void relax(){
    Vector<Point> dv = new Vector<Point>();
    for(int cnt=0;cnt<nodes.size();cnt++){
      dv.add(new Point(0,0));
    }
    // spring
    for(int cnt=0;cnt<edges.size();cnt++){
      int[] e = edges.get(cnt);
      double x0 = node_pos.get(e[0]).getCenterX();
      double y0 = node_pos.get(e[0]).getCenterY();
      double x1 = node_pos.get(e[1]).getCenterX();
      double y1 = node_pos.get(e[1]).getCenterY();
      double len = Math.sqrt(Math.pow(x0-x1,2)+Math.pow(y0-y1,2));
      double ddv = (len-length0)/2;
      double effect = 1.0-(1.0/(1.0+Math.exp(-1*(Math.abs(ddv)-5.0)/2)));
      if(effect < 0.1){
        effect = 0.1;
      }
      ddv *= effect;
      double rad = getRad(x0,y0,x1,y1);
      double ddv_x = ddv*Math.cos(rad);
      double ddv_y = ddv*Math.sin(rad);
      dv.get(e[0]).x += ddv_x;
      dv.get(e[0]).y += ddv_y;
      dv.get(e[1]).x -= ddv_x;
      dv.get(e[1]).y -= ddv_y;
    }
    // repulsion
    /*
    double effect = 5000;
    for(int cnt1=0;cnt1<nodes.size()-1;cnt1++){
      if(node_fixed.get(cnt1).booleanValue()==false){
        for(int cnt2=cnt1+1;cnt2<nodes.size();cnt2++){
          if(cnt1!=cnt2 && false==isConnected(cnt1,cnt2)){
            double x0 = node_pos.get(cnt1).getCenterX();
            double y0 = node_pos.get(cnt1).getCenterY();
            double x1 = node_pos.get(cnt2).getCenterX();
            double y1 = node_pos.get(cnt2).getCenterY();
            double len = Math.sqrt(Math.pow(x0-x1,2)+Math.pow(y0-y1,2));
            double f = effect/Math.pow(len,2);
            double ddv_x = (x0-x1)*f/len/2;
            double ddv_y = (y0-y1)*f/len/2;
            dv.get(cnt1).x += ddv_x;
            dv.get(cnt1).y += ddv_y;
            dv.get(cnt2).x -= ddv_x;
            dv.get(cnt2).y -= ddv_y;
          }
        }
      }
    }
    /**/
    
    for(int cnt=0;cnt<nodes.size();cnt++){
      if(node_fixed.get(cnt).booleanValue()==false){
        node_pos.get(cnt).x += dv.get(cnt).x;
        if(node_pos.get(cnt).x < 0){
          node_pos.get(cnt).x = 0;
        }else if(node_pos.get(cnt).x+node_pos.get(cnt).width>scr.x){
          node_pos.get(cnt).x = scr.x-node_pos.get(cnt).width;
        }
        node_pos.get(cnt).y += dv.get(cnt).y;
        if(node_pos.get(cnt).y < 0){
          node_pos.get(cnt).y = 0;
        }else if(node_pos.get(cnt).y+node_pos.get(cnt).height>scr.y){
          node_pos.get(cnt).y = scr.y-node_pos.get(cnt).height;
        }
      }
    }
  }
  public boolean isConnected(String n1,String n2){
    return isConnected(indexOf(n1),indexOf(n2));
  }
  private int indexOf(int x,int y){
    for(int cnt=node_pos.size()-1;cnt>=0;cnt--){
      Rectangle rc = node_pos.get(cnt);
      if(rc.contains(mouseX,mouseY)){
        return cnt;
      }
    }
    return -1;
  }
  private int indexOf(String nodeName){
    for(int cnt=0;cnt<nodes.size();cnt++){
      if(nodes.get(cnt).equals(nodeName)){
        return cnt;
      }
    }
    return -1;
  }
  private boolean isConnected(int n1,int n2){
    for(int[] e : edges){
      if(e[0]==n1&&e[1]==n2 || e[0]==n2&&e[1]==n1){
        return true;
      }
    }
    return false;
  }
  public boolean setFixed(String nodeString,boolean fixed){
    int idx = indexOf(nodeString);
    if(idx == -1){
      return false;
    }
    node_fixed.set(idx,fixed);
    return true;
  }
  public boolean getFixed(String nodeString){
    return node_fixed.get(indexOf(nodeString));
  }
  private double getRad(double x0,double y0,double x1,double y1){
    double x = x1-x0;
    double y = y1-y0;
    if(y == 0){
      if(x >= 0){
        return 0;
      }else{
        return Math.PI;
      }
    }else if(x == 0){
      if(y >= 0){
        return Math.PI/2;
      }else{
        return 3*Math.PI/2;
      }
    }
    double rad = Math.acos(x/Math.sqrt(Math.pow(x,2)+Math.pow(y,2)));
    if(y<0){
      rad = (2*Math.PI)-rad;
    }
    return rad;
  }
  
  public boolean addEdge(String fnode,String tnode){
    return addEdge(fnode,tnode,true);
  }
  public boolean addEdge(String fnode,String tnode,boolean directed){
    int findex = addNode(fnode);
    int tindex = addNode(tnode);
    for(int cnt=0;cnt<edges.size();cnt++){
      int[] e = edges.get(cnt);
      if(e[0]==findex && e[1]==tindex){
        e[2] = Math.min(e[2],directed?1:0);
        return true;
      }else if(e[0]==tindex && e[1]==findex){
        e[2] = 0;
        return true;
      }
    }
    edges.add(new int[]{findex,tindex,directed?1:0});
    return true;
  }
  public int addNode(String node){
    int index = nodes.indexOf(node);
    if(index != -1){
      return index;
    }
    nodes.add(node);
    node_pos.add(getTextRect(node,(int)random(0,scr.x),(int)random(0,scr.y)));
    node_fixed.add(new Boolean(false));
    return nodes.size()-1;
  }
  public void toCirclePosition(){
    if(nodes.size()==0){
      return;
    }
    int margin = 50;
    int r = Math.min(scr.x/2-2*margin,scr.y/2-2*margin);
    double r1 = Math.PI*2/nodes.size();
    for(int cnt=0;cnt<nodes.size();cnt++){
      double rn = r1*cnt;
      Rectangle rc = node_pos.get(cnt);
      rc.setLocation(
        (int)(r*Math.cos(rn)+scr.x/2)-rc.width/2,
        (int)(r*Math.sin(rn)+scr.y/2)-rc.height/2);
    }
  }
  void mousePressed()
  {
    if(mouseButton==RIGHT){
      if(popupmenu_node!=-1){
        node_fixed.set(popupmenu_node,popupmenu_node_fixed);
        popupmenu_node=-1;
      }
      final int idx = indexOf(mouseX,mouseY);
      JPopupMenu popup = new JPopupMenu();
      if(idx == -1){
        JMenuItem i1 = new JMenuItem("load file");
        i1.addActionListener(new ActionListener(){
          public void actionPerformed(ActionEvent e){
            JFileChooser dlg = new JFileChooser();
            if(JFileChooser.APPROVE_OPTION==dlg.showOpenDialog(parent)){
              load(dlg.getSelectedFile().getAbsolutePath());
            }
          }
        });
        popup.add(i1);
        JMenuItem i2 = new JMenuItem("save file");
        i2.addActionListener(new ActionListener(){
          public void actionPerformed(ActionEvent e){
            JFileChooser dlg = new JFileChooser();
            if(JFileChooser.APPROVE_OPTION==dlg.showSaveDialog(parent)){
              save(dlg.getSelectedFile().getAbsolutePath());
            }
          }
        });
        popup.add(i2);
      }else{
        popupmenu_node = idx;
        popupmenu_node_fixed = node_fixed.get(idx);
        node_fixed.set(idx,true);
//println("fixed "+nodes.get(idx));
        JMenuItem i = new JMenuItem(popupmenu_node_fixed?"free":"fixed");
        i.addActionListener(new ActionListener(){
          public void actionPerformed(ActionEvent e){
            popupmenu_node = -1;
            node_fixed.set(idx,!popupmenu_node_fixed);
          }
        });
        popup.add(i);
      }
      popup.show(parent,mouseX,mouseY);
    }else if(mouseButton==LEFT){
//println("dragging_node "+dragging_node);
      if(popupmenu_node!=-1){
        node_fixed.set(popupmenu_node,popupmenu_node_fixed);
        popupmenu_node=-1;
      }
      if(dragging_node==-1){
        int idx = indexOf(mouseX,mouseY);
        if(idx!=-1){
          dragging_node = idx;
          dragging_node_ofset.x = mouseX-node_pos.get(idx).x;
          dragging_node_ofset.y = mouseY-node_pos.get(idx).y;
          dragging_node_fixed = node_fixed.get(idx);
          node_fixed.set(idx,true);
        }
      }
    }
  }
  void mouseReleased()
  {
    if(dragging_node != -1){
//println("change "+nodes.get(dragging_node)+" -> "+dragging_node_fixed);
      node_fixed.set(dragging_node,dragging_node_fixed);
      dragging_node = -1;
    }
  }
  void mouseDragged()
  {
    if(dragging_node!=-1){
      node_pos.get(dragging_node).setLocation(mouseX-dragging_node_ofset.x,mouseY-dragging_node_ofset.y);
    }
  }
}