graphdrawer.java

个人学习图算法时写的源码 包括最小生成树, 最大网络流, DSF遍历, BSF遍历,

package twf.weightedgraph.common;

import java.awt.Color;
import java.awt.Graphics;
import java.text.DecimalFormat;

import javax.swing.JFrame;
import javax.swing.JPanel;

import twf.weightedgraph.AdjList;
import twf.weightedgraph.Edge;
import twf.weightedgraph.Graph;
import twf.weightedgraph.Path;

public class GraphDrawer extends JFrame {

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	private GPanel panel;   
    public GraphDrawer(Graph G, int width, int height) {
    	panel = new GPanel(G, 200, 18, 240, 230);    	
    	this.getContentPane().add(panel);
    	this.setTitle("-图形显示-");    	
    	setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    	setSize(width, height);
    	setVisible(true);
    }
    public void highlightPath(Path path) {
    	panel.highLightPath(path);
    }
    public void highLightEdges(Edge[] es) {
    	panel.htEdges(es);
    }
    private class GPanel extends JPanel {
    	/**
		 * 
		 */
		private static final long serialVersionUID = 1L;
		private Graph G;
    	private Node[] nodes;
    	private int R;
    	private int r;
    	private int centerX;
    	private int centerY;
    	private boolean showPath, htEdges, digraph;
    	private Path path;
    	private Edge[] es;
    	GPanel(Graph G, int R, int r, int centerX, int centerY) {
    		this.G = G;
    		this.r = r;
    		this.R = R;
    		this.centerX = centerX;
    		this.centerY = centerY;
    		this.digraph = G.directed();
    		initNodes();
    	}
    	private void initNodes() {
    		int n = G.V();
    		double thta = Math.PI*2/n;
    		nodes = new Node[n];
    		for (int i = 0; i < n; i++) {
    			nodes[i] = new Node((int) (R*Math.cos(i*thta)) + centerX, 
    					centerY + (int) (R*Math.sin(i*thta)));
    		}
    	}
    	public void paintComponent(Graphics g) {
    		super.paintComponent(g);
    		int n = G.V();
    		for (int i = 0; i < n; i++) {
    			drawNode(g, i);
    			
    		    AdjList A = G.getAdjList(i);
    			for (Edge e = A.beg(); !A.end(); e = A.nxt()) {
    				drawEdge(g, e);
    			}
    		}
    		if (showPath) {
    			showPath(g);
    		}
    		if (htEdges) {
    			Color old = g.getColor();
				g.setColor(Color.red);
    			for (int i = 0; i < es.length; i++) {
    				if (es[i] != null)
    			    drawEdge(g, es[i]);
    			}
    			g.setColor(old);
    		}
    	}
    	private void htEdges(Edge[] es) {
    		this.es = es;
    		htEdges = true;
    		repaint();
    	}
    	private void drawEdge(Graphics g, Edge e) {
    		int v = e.v(), w = e.w();
    		int x1 = nodes[v].x, x2 = nodes[w].x;
    		int y1 = nodes[v].y, y2 = nodes[w].y;
    		g.drawLine(x1, y1, x2, y2);
    		//draw weight here
    		DecimalFormat format = new DecimalFormat("#.##");    		
    		g.drawString(format.format(e.wt()), (x1 + x2)/2, (y1 + y2)/2);
    		
    		//draw arrow    		
    		if (digraph) {
    			double theta;
    			if (x1 != x2) {
    				double tan = (y2 - y1) / (double) (x2 - x1);
    				theta = Math.atan(tan);
    				if (x2 < x1) theta += Math.PI;
    			} else {
    				if (y2 > y1) {
    					theta = Math.PI/2.0;
    				} else {
    					theta = 3*Math.PI/2.0;
    				}
    			}
    			x2 -= r*Math.cos(theta);
    			y2 -= r*Math.sin(theta);
    			int x3 = x2 - (int) (10*Math.cos(theta - Math.PI/12.0));
    			int y3 = y2 - (int) (10*Math.sin(theta - Math.PI/12.0));
    			int x4 = x2 - (int) (10*Math.cos(theta + Math.PI/12.0));
    			int y4 = y2 - (int) (10*Math.sin(theta + Math.PI/12.0));
    			g.drawLine(x3, y3, x2, y2);
    			g.drawLine(x4, y4, x2, y2);
    		}
    	}
    	private void drawNode(Graphics g, int v) {     		
    		g.fillOval(nodes[v].x - r/2, nodes[v].y - r/2, r, r); 
    		Color old = g.getColor();
    		g.setColor(Color.white);
    		//draw label here.
    		g.drawString(Integer.toString(v), nodes[v].x - r/3 , nodes[v].y + r/3);
    		g.setColor(old);
    	}
    	private void showPath(Graphics g) {
    		Color old = g.getColor();
    		g.setColor(Color.red);
    		
    		for (Edge e = path.beg(); !path.end(); e = path.nxt()) {
    			if (e != null) {
    			  drawNode(g, e.v());
    			  drawEdge(g, e);
    			}
    		}
    		g.setColor(old);
    	}
    	public void highLightPath(Path path) {
    		this.path = path;
    		showPath = true;
    		this.repaint();
    	}
    }
    private class Node {
    	int x, y;
    	Node(int x, int y) {    		
    		this.x = x;
    		this.y = y;
    	}
    }
}