graphgenerator.java

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

package twf.weightedgraph.common;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

import twf.weightedgraph.Edge;
import twf.weightedgraph.Graph;

public class GraphGenerator {
	public static void randE(Graph G, int E) {
		Random ran = new Random();
		for (int i = 0; i < E; i++) {
			int v = ran.nextInt(G.V());
			int w = ran.nextInt(G.V());
			if (v != w && G.edge(v, w) == null) {
				G.insert(new Edge(v, w, Math.random()));
			}
		}
	}
	
	public static void randG(Graph G , int E) {
		double p = 1.0*E/G.V()/(G.V() - 1);
		for (int v = 0; v < G.V(); v++) {
			for (int w = 0; w < G.V(); w++) {
				if (v != w && Math.random() < p) {
					G.insert(new Edge(v, w, Math.random()));
				}
			}
		}
	}
	
	public static void randP(Graph G, double r) {
		int n = G.V();
		Point[] point = new Point[n];
		for (int i = 0; i < n; i++) {
			point[i] = new Point(Math.random(), Math.random());
		}
		Arrays.sort(point, new Comparator(){
			public int compare(Object arg0, Object arg1) {
				// TODO Auto-generated method stub
				Point p1 = (Point) arg0, p2 = (Point) arg1;
				if (p1.x > p2.x) return -1;
				if (p1.x < p2.x) return 1;
				return 0;
			}
			
		});
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j) continue;
				double dist;
				if ((dist = point[i].dist(point[j])) < r) {
					G.insert(new Edge (i, j, dist));
				}
			}
		}		
	}
	static class Point {
		double x, y;
		Point(double x, double y) {
			this.x = x;
			this.y = y;			
		}
		double dist(Point p) {
			double xx = x - p.x;
			double yy = y - p.y;
			return Math.sqrt(xx*xx + yy*yy);
		}
	}
}