mstvisual.java

最小生成树的算法演示

      implements KeyListener {

    public void keyPressed(KeyEvent e) {}

    public void keyTyped(KeyEvent e) {}

    public void keyReleased(KeyEvent e) {
      paintResult = false;
      repaint();
      if (e.getKeyCode() == KeyEvent.VK_DELETE) {
        //当delete键按下时
        if (lineBrighter) {
          //如果当前有线高亮显示，则删除该线
          startNode.remove(currentLineIndex);
          endNode.remove(currentLineIndex);
          weight.remove(currentLineIndex);
          weightBack.remove(currentLineIndex);
          lineBrighter = false;
          repaint();
        }
        if (brighter) {
          //如果当前有结点高亮显示，则删除该结点以及相应的边
          for (int i = 0; i < startNode.size(); i++) {
            int index = ( (Integer) startNode.get(i)).intValue();
            if (index == currentNodeIndex) {
              startNode.remove(i);
              endNode.remove(i);
              weight.remove(i);
              weightBack.remove(i);
              i--;
            }
            if (index > currentNodeIndex) {
              startNode.set(i, new Integer(index - 1));
            }
          }
          for (int i = 0; i < endNode.size(); i++) {
            int index = ( (Integer) endNode.get(i)).intValue();
            if (index == currentNodeIndex) {
              startNode.remove(i);
              endNode.remove(i);
              weight.remove(i);
              weightBack.remove(i);
              i--;
            }
            if (index > currentNodeIndex) {
              endNode.set(i, new Integer(index - 1));
            }
          }

          node.remove(currentNodeIndex);
          nodeName.remove(currentNodeIndex);
          brighter = false;
          repaint();
        }
      }

    };
  }

  //鼠标事件监听类
  class MouseL
      implements MouseListener {

    public void mouseEntered(MouseEvent e) {}

    public void mouseExited(MouseEvent e) {}

    public void mousePressed(MouseEvent e) {
    }

    public void mouseClicked(MouseEvent e) {
      paintResult = false;
      if (e.getClickCount() == 2 && brighter) {
        String str = JOptionPane.showInputDialog(null, "请输入新的结点名:",
                                                 "更改结点名",
                                                 JOptionPane.
                                                 INFORMATION_MESSAGE);
        if (str == null) {
          return;
        }
        else if (str.length() > 0) {
          nodeName.set(currentNodeIndex, str);
        }
        else {
          nodeName.set(currentNodeIndex, String.valueOf(name++));
        }
        repaint();
      }
      if (e.getClickCount() == 2 && lineBrighter) {
        //鼠标经过一条边且双击时，更改权重
        System.out.println("Change weight");
        String str = JOptionPane.showInputDialog(null, "请输入该边的新权重",
                                                 "更改权重",
                                                 JOptionPane.
                                                 INFORMATION_MESSAGE);

        if (str != null && str.length() > 0) {
          weight.set(currentLineIndex, Integer.valueOf(str));
          weightBack.set(currentLineIndex, Integer.valueOf(str));
        }
        else {
          weight.set(currentLineIndex, new Integer(0));
          weightBack.set(currentLineIndex, new Integer(0));
        }
        return;
      }
      if (e.getClickCount() == 2 && !hasPre) {
        //鼠标双击且没有一条边的开始结点时，新建一个结点
        String str = JOptionPane.showInputDialog(null, "请输入结点名:",
                                                 "新建结点",
                                                 JOptionPane.
                                                 INFORMATION_MESSAGE);
        if (str == null) {
          return;
        }
        else if (str.length() > 0) {
          nodeName.add(str);
        }
        else {
          nodeName.add(String.valueOf(name++));
        }
        node.add(new Point(e.getX(), e.getY()));
        drawNode = true;
        repaint();
      }
      if (e.getClickCount() == 2 && hasPre) {
        //鼠标双击且已经有了一条边的开始结点时，取消该边的创建，并将开始结点链表中的最后一个元素删除
        hasPre = false;
        repaint();
        if (startNode.size() > 0) {
          startNode.removeLast();
        }
      }
    }

    public void mouseReleased(MouseEvent e) {
      paintResult = false;
      for (int i = 0; i < node.size(); i++) {
        if (e.getX() >= ( (Point) node.get(i)).x
            && e.getX() <= ( ( (Point) node.get(i)).x + 30)
            && e.getY() >= ( (Point) node.get(i)).y
            && e.getY() <= ( ( (Point) node.get(i)).y + 30)) {
          if (!hasPre) {
            //点击鼠标，而且还不存在一条边的开始结点时，将当前结点加入到开始结点链表中
            if (!move) {
              preNode.x = ( (Point) node.get(i)).x;
              preNode.y = ( (Point) node.get(i)).y;

              startNode.add(new Integer(i));
              hasPre = true;
              drawEdge = true;
            }
            else {
              move = false;
            }
          }
          else {
            //点击鼠标，而且已经存在一条边的开始结点时，将当前结点加入到结束结点链表中
            //创建一条边并输入该边的权重
            currentNode.x = ( (Point) node.get(i)).x;
            currentNode.y = ( (Point) node.get(i)).y;
            if (i == ( (Integer) startNode.getLast()).intValue()) {
              return;
            }
            endNode.add(new Integer(i));
            findEdge = true;
            hasPre = false;
            repaint();

            String str = JOptionPane.showInputDialog(null, "请输入该边的权重",
                "新建边", JOptionPane.INFORMATION_MESSAGE);

            if (str != null && str.length() > 0) {
              weight.add(Integer.valueOf(str));
              weightBack.add(Integer.valueOf(str));
            }
            else {
              weight.add(new Integer(0));
              weightBack.add(new Integer(0));
            }
            drawWeight = true;
            repaint();
          }
        }
      }
    }

  }

  boolean move = false;
  //鼠标运动监听类
  class MouseM
      implements MouseMotionListener {

    public void mouseDragged(MouseEvent e) {
      if (brighter) {
        move = true;
        node.set(currentNodeIndex, new Point(e.getX(), e.getY()));
        repaint();
      }
    }

    public void mouseMoved(MouseEvent e) {

      if (hasPre) {
        //如果已经存在一条边的开始结点，则得到当前鼠标位置，并画出开始结点与鼠标位置之间的直线
        currentMousePoint.x = e.getX();
        currentMousePoint.y = e.getY();
        repaint();
      }
      for (int i = 0; i < startNode.size() && i < endNode.size(); i++) {
        int[] p = getPaintPosition( ( (Point) node.get( ( (Integer) startNode.
            get(i)).intValue())).x,
                                   ( (Point) node.get( ( (Integer) startNode.
            get(i)).intValue())).y,
                                   ( (Point) node.get( ( (Integer) endNode.
            get(i)).intValue())).x,
                                   ( (Point) node.get( ( (Integer) endNode.
            get(i)).intValue())).y);
        float k;
        if ( (p[2] - p[0]) != 0) {
          k = ( (float) (p[3] - p[1])) / ( (float) (p[2] - p[0]));
        }
        else {
          k = Integer.MAX_VALUE;
        }
        float b = p[3] - k * p[2];

        int small;
        int large;

        if (p[2] > p[0]) {
          small = p[0];
          large = p[2];
        }
        else {
          small = p[2];
          large = p[0];
        }
        //如果鼠标经过图中的某一条边，则高亮显示该边及相应权重
        if (k == Integer.MAX_VALUE) {
          if ( (e.getX() >= p[0] - 15) && (e.getX() <= p[0] + 15) &&
              e.getX() >= small && e.getX() <= large) {
            lineBrighter = true;
            paintResult = false;
            currentLineIndex = i;
            repaint();
            break;
          }
        }
        if (e.getY() <= (k * e.getX() + b + 20) &&
            e.getY() >= (k * e.getX() + b - 20) &&
            e.getX() >= small && e.getX() <= large) {
          lineBrighter = true;
          paintResult = false;
          currentLineIndex = i;
          repaint();
          break;
        }
        else {
          lineBrighter = false;
          repaint();
        }
      }
      //如果鼠标经过图中某一个结点，则高亮显示该结点及相应结点名
      for (int i = 0; i < node.size(); i++) {
        if (e.getX() >= ( (Point) node.get(i)).x
            && e.getX() <= ( ( (Point) node.get(i)).x + 30)
            && e.getY() >= ( (Point) node.get(i)).y
            && e.getY() <= ( ( (Point) node.get(i)).y + 30)) {
          currentNodeIndex = i;
          brighter = true;
          paintResult = false;
          repaint();
          break;
        }
        else {
          brighter = false;
          repaint();
        }
      }
    }
  }

  public static void main(String[] args) {
    JFrame fram = new JFrame();
    MSTVisual pan = new MSTVisual();

    JMenuBar menuBar = new JMenuBar();
    JMenu fileMenu = new JMenu("文件");
    JMenu helpMenu = new JMenu("帮助");

    JMenuItem exit = new JMenuItem("退出");
    JMenuItem topic = new JMenuItem("主题");
    JMenuItem about = new JMenuItem("关于");
    exit.addActionListener(
        new ActionListener() {
      public void actionPerformed(ActionEvent event) {
        System.exit(1);
      }
    }
    );

    topic.addActionListener(
        new ActionListener() {
      public void actionPerformed(ActionEvent event) {
        try {
          Process process = Runtime.getRuntime().exec(
              "notepad  help.txt");
        }
        catch (IOException e) {
          System.out.println("Open file error!");
        }
      }
    }
    );

    about.addActionListener(
        new ActionListener() {
      public void actionPerformed(ActionEvent event) {
        JOptionPane.showMessageDialog(null,
            "   最小生成树算法过程演示\n             winpro     ",
            "关于", JOptionPane.INFORMATION_MESSAGE);
      }
    }
    );

    fileMenu.add(exit);
    helpMenu.add(topic);
    helpMenu.add(about);

    menuBar.add(fileMenu);
    menuBar.add(helpMenu);
    fram.setJMenuBar(menuBar);

    Container c = fram.getContentPane();
    c.add(pan);

    fram.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    fram.setSize(800, 600);
    fram.setTitle("最上生成树算法演示");
    fram.setVisible(true);
  }

  private boolean drawEdge = false;
  private boolean drawNode = false;
  private boolean brighter = false;
  private boolean drawWeight = false;
  private boolean hasPre = false;
  private boolean findEdge = false;
  private boolean findMSTEdge = false;
  private boolean paintResult = false;
  private boolean lineBrighter = false;

  private int currentNodeIndex = 0;
  private int currentLineIndex = 0;
  private int sMSTEdge = 0;
  private int eMSTEdge = 0;
  private int iD = -1;
  private int name = 0;

  private Thread main_thread;

  private LinkedList startNode = new LinkedList();
  private LinkedList endNode = new LinkedList();
  private LinkedList weight = new LinkedList();
  private LinkedList weightBack = new LinkedList();
  private LinkedList nodeName = new LinkedList();
  private LinkedList node = new LinkedList();

  private Vector MST = new Vector();
  private Vector sMSTEdgeV = new Vector();
  private Vector eMSTEdgeV = new Vector();
  private Vector isSelect = new Vector();
  private Vector edge = new Vector();

  private Point preNode = new Point();
  private Point currentNode = new Point();
  private Point currentMousePoint = new Point();

  private JButton process = new JButton("演示算法");

  private MouseL mouse = new MouseL();
  private MouseM mouseM = new MouseM();
  private KeyDown key = new KeyDown();

}