main.java

用图形用户界面表示的图

package hartech.kids.grapher;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.event.*;
import hartech.ui.*;
import hartech.ds.*;

/**
 * <p>Title: 图的应用演示 </p>
 *
 * <p>Description: </p>
 *
 * <p>Website: www.hartech.cn </p>
 * <p>Page: http://www.hartech.cn/blog/blogview.asp?logID=88 </p>
 *
 * <p>Date: 2006-09-07 </p>
 */
public class Main {

  // 图标
  static JLabel[] icon;

  // 图标数量
  static final int icon_num = 25;

  // 图存储结构
  static int arcs[][];

  // 图的存储结构二
  // 专门做为最短路径的参数
  // 因如用上面的arcs[][]则为完全图，点与点间最短距离当然就是两点用直线相连，没什么意思
  // 该结构继承上面的arcs[][]，但仅是相邻距离最小的四个节点可通，到其它节点不通
  static int arcs_last4[][];

  // 设置仅连相邻距离最小的 LAST_NUM 个节点可通
  static final int LAST_NUM = 2;

  // 图标移动范围
  static final int panel_width = 715, panel_height = 290;

  // 四个队列，图运算结果保存于该四队列，第五个为路径图
  // panel根据这些队列画线、箭头
  static Queue Q_DFS = new Queue();
  static Queue Q_BFS = new Queue();
  static Queue Q_tree = new Queue();
  static Queue Q_shortest = new Queue();
  static Queue Q_route = new Queue();
  // 记录各种遍历的路径总长度，用于在右下角显示
  static int length_DFS = 0, length_BFS = 0, length_tree = 0, length_short = 0,
  length_route = 0;

  // 预设25个图标的坐标
  static final int[] location_x = {
      203, 180, 40, 458, 99, 118, 230, 409, 27, 519, 259, 496, 695, 292, 415,
      295, 320, 504, 342, 181, 575, 562, 621, 419, 694};
  static final int[] location_y = {
      134, 181, 0, 112, 188, 73, 242, 169, 271, 56, 72, 287, 10, 210, 247, 129,
      0, 178, 54, 35, 219, 140, 77, 30, 196};

  // 初始化
  static {
    // arcs[][]
    arcs = new int[icon_num][icon_num];
    arcs_last4 = new int[icon_num][icon_num];
    // 自己到自己为不联通，-1
    for (int i = 0; i < icon_num; i++) {
      arcs[i][i] = -1;
    }

    // icon[]
    icon = new JLabel[icon_num];
    for (int i = 0; i < icon_num; i++) {
      icon[i] = new JLabel(ComboBoxRenderer.createImageIcon("images/smiles/" +
          i + ".gif"));
      icon[i].setBounds(location_x[i], location_y[i], 22, 22);
      icon[i].addMouseMotionListener(new MouseMotionListener_drag_icon());
    }

    updateArcs();
    //printLocations();
  }

  // 更新各图标距离到图存储结构 arcs[][]
  // 全联通，自己到自己为不联通：-1
  static void updateArcs() {
    int temp = 0;
    // 因无向图，仅计算矩阵上三角
    for (int i = 0; i < icon_num; i++) {
      for (int j = i + 1; j < icon_num; j++) {
        temp = (icon[i].getX() - icon[j].getX()) *
            (icon[i].getX() - icon[j].getX()) +
            (icon[i].getY() - icon[j].getY()) * (icon[i].getY() - icon[j].getY());
        arcs[i][j] = (int) Math.pow(temp, 0.5);
      }
    }
    // 复制到下三角
    for (int i = 0; i < icon_num; i++) {
      for (int j = 0; j < i; j++) {
        arcs[i][j] = arcs[j][i];
      }
    }
  }

  // 用updateArcs()计算出所有距离，再把非最小四的节点设为 -1
  // 先求出有向图，再转成无向图
  static void updateArcs_last4() {
    updateArcs();

    int min, p = 0;
    Q_route.clean();
    length_route = 0;
    boolean[] isLast4 = new boolean[icon_num];
    for (int i = 0; i < icon_num; i++) {
      for (int n = 0; n < icon_num; n++) {
        isLast4[n] = false;
      }
      // 找出四个最短的
      for (int n = 0; n < LAST_NUM; n++) {
        min = Integer.MAX_VALUE;
        for (int j = 0; j < icon_num; j++) {
          if (arcs[i][j] != -1 && arcs[i][j] < min && !isLast4[j]) {
            min = arcs[i][j];
            p = j;
          }
        }
        if (min == Integer.MAX_VALUE) {
          break;
        }
        else {
          isLast4[p] = true;
        }
      }
      // 输入到arcs_last4[][]
      for (int n = 0; n < icon_num; n++) {
        if (isLast4[n]) {
          arcs_last4[i][n] = arcs[i][n];
        }
        else {
          arcs_last4[i][n] = -1;
        }
      }
    }

    // 把上面的有向图变成无向图
    for (int i = 0; i < icon_num; i++) {
      for (int j = 0; j < icon_num; j++) {
        if (arcs_last4[i][j] != -1 && arcs_last4[j][i] == -1) {
          arcs_last4[j][i] = arcs_last4[i][j];
        }
      }
    }

    // 遍历上三角，把上面所得的无向图中所有路径入队列和统计总长度
    for (int i = 0; i < icon_num; i++) {
      for (int j = i + 1; j < icon_num; j++) {
        if (arcs_last4[i][j] != -1) {
          // 输出到 Main.Q_route 队列，用于画路径图
          Q_route.enQueue(new Dimension(i, j));
          length_route += arcs_last4[i][j];
        }
      }
    }
    UI.jTextField_route.setText(String.valueOf(length_route));
  }

  // 打印出当前所有图标的坐标
  static void printLocations() {
    StringBuffer out_x = new StringBuffer("{");
    StringBuffer out_y = new StringBuffer("{");
    Point d;
    for (int i = 0; i < icon_num; i++) {
      d = icon[i].getLocation();
      out_x.append( (int) d.getX() + ",");
      out_y.append( (int) d.getY() + ",");
    }
    System.out.println(out_x + "}");
    System.out.println(out_y + "}");
  }

  public static void main(String[] args) {
    javax.swing.SwingUtilities.invokeLater(new Runnable() {
      public void run() {
        J.setLookAndFeel("Metal");
        new UI();
      }
    });
  }
}

// 图标拖动事件
class MouseMotionListener_drag_icon
    implements MouseMotionListener {
  static JLabel temp;
  static int x, y;
  public void mouseMoved(MouseEvent e) {
  }

  public void mouseDragged(MouseEvent e) {
    temp = ( (JLabel) e.getSource());
    x = temp.getX() + e.getX() - 10;
    y = temp.getY() + e.getY() - 10;
    if (x > ( (Dimension) UI.drawPanel.getSize()).width - 25) {
      x = ( (Dimension) UI.drawPanel.getSize()).width - 25;
    }
    if (x < 5) {
      x = 5;
    }
    if (y > ( (Dimension) UI.drawPanel.getSize()).height - 25) {
      y = ( (Dimension) UI.drawPanel.getSize()).height - 25;
    }
    if (y < 5) {
      y = 5;
    }
    temp.setLocation(x, y);
    UI.drawPanel.repaint();
  }
}

class ActionListener_buttons
    implements ActionListener {
  public void actionPerformed(ActionEvent e) {

    //
    if (e.getActionCommand().equals("DFS_begin")) {
      Main.Q_DFS.clean();
      Main.length_DFS = 0;
      if (UI.jCheckBox_show_route.isSelected()) {
        Main.updateArcs_last4();
        Graph.traverse_DFS(Main.arcs_last4,
                           UI.jComboBox_DFS_begin.getSelectedIndex());
      }
      else {
        Main.updateArcs();
        Graph.traverse_DFS(Main.arcs,
                           UI.jComboBox_DFS_begin.getSelectedIndex());
      }
      UI.jTextField_DFS.setText(String.valueOf(Main.length_DFS));
      UI.drawPanel.repaint();
    }
    else if (e.getActionCommand().equals("DFS_clean")) {
      Main.Q_DFS.clean();
      Main.length_DFS = 0;
      UI.jTextField_DFS.setText(String.valueOf(Main.length_DFS));
      UI.drawPanel.repaint();
    }

    //
    else if (e.getActionCommand().equals("BFS_begin")) {
      Main.Q_BFS.clean();
      Main.length_BFS = 0;
      if (UI.jCheckBox_show_route.isSelected()) {
        Main.updateArcs_last4();
        Graph.traverse_BFS(Main.arcs_last4,
                           UI.jComboBox_BFS_begin.getSelectedIndex());
      }
      else {
        Main.updateArcs();
        Graph.traverse_BFS(Main.arcs,
                           UI.jComboBox_BFS_begin.getSelectedIndex());
      }
      UI.jTextField_BFS.setText(String.valueOf(Main.length_BFS));
      UI.drawPanel.repaint();
    }
    else if (e.getActionCommand().equals("BFS_clean")) {
      Main.Q_BFS.clean();
      Main.length_BFS = 0;
      UI.jTextField_BFS.setText(String.valueOf(Main.length_BFS));
      UI.drawPanel.repaint();
    }

    //
    else if (e.getActionCommand().equals("tree_begin")) {
      Main.Q_tree.clean();
      Main.length_tree = 0;
      if (UI.jCheckBox_show_route.isSelected()) {
        Main.updateArcs_last4();
        Graph.miniSpanTree(Main.arcs_last4);
      }
      else {
        Main.updateArcs();
        Graph.miniSpanTree(Main.arcs);
      }
      UI.jTextField_tree.setText(String.valueOf(Main.length_tree));
      UI.drawPanel.repaint();
    }
    else if (e.getActionCommand().equals("tree_clean")) {
      Main.Q_tree.clean();
      Main.length_tree = 0;
      UI.jTextField_tree.setText(String.valueOf(Main.length_tree));
      UI.drawPanel.repaint();
    }

    //
    else if (e.getActionCommand().equals("shortest_begin")) {
      Main.Q_shortest.clean();
      Main.length_short = 0;
      if (UI.jCheckBox_show_route.isSelected()) {
        Main.updateArcs_last4();
        Graph.shortestPath_DIJ(Main.arcs_last4,
                               UI.jComboBox_shortest_begin.getSelectedIndex()
                               , UI.jComboBox_shortest_end.getSelectedIndex());
      }
      else {
        Main.updateArcs();
        Graph.shortestPath_DIJ(Main.arcs,
                               UI.jComboBox_shortest_begin.getSelectedIndex()
                               , UI.jComboBox_shortest_end.getSelectedIndex());
      }
      UI.jTextField_short.setText(String.valueOf(Main.length_short));
      UI.drawPanel.repaint();
    }
    else if (e.getActionCommand().equals("shortest_clean")) {
      Main.Q_shortest.clean();
      Main.length_short = 0;
      UI.jTextField_short.setText(String.valueOf(Main.length_short));
      UI.drawPanel.repaint();
    }
    else if (e.getActionCommand().equals("show_route")) {
      if (UI.jCheckBox_show_route.isSelected()) {
        Main.updateArcs_last4();
        UI.drawPanel.repaint();
      }
      else {
        Main.Q_route.clean();
        Main.length_route = 0;
        UI.jTextField_route.setText(String.valueOf(Main.length_route));
        UI.drawPanel.repaint();
      }
    }
    else if (e.getActionCommand().equals("show_number")) {
      UI.drawPanel.repaint();
    }
  }
}