iisp-ts-common/src/graph.utils.ts

import { Dijkstra } from './dijkstra.utils';
export class GraphUtils {
	/**
	 * 把节点集和边集转换成图矩阵
	 * @param nodes 节点集
	 * @param edges 边集
	 * @param directed 是否有向，缺省是无向图
	 * @param distanceProp 边上的距离属性名，缺省为distance
	 * @return 图矩阵
	 */
	static toGraphMatrix(nodes: NodeBase<any>[], edges: EdgeBase<any>[], directed = false, distanceProp = "distance"): number[][] {
		let m = GraphUtils.getMatrix(nodes.length);
		let nodeMap = new Object();
		let idx = 0;
		for (let vertex of nodes) {
			nodeMap[vertex.id] = idx;
			idx++;
		}
		for (let edge of edges) {
			let distance = edge[distanceProp];
			if (!distance) {
				distance = 1;
			}
			m[nodeMap[edge.source.id]][nodeMap[edge.target.id]] = distance;
			if (!directed) {
				m[nodeMap[edge.target.id]][nodeMap[edge.source.id]] = distance;
			}
		}
		return m;
	}
	private static getMatrix(length: number): number[][] {
		let m = new Array<number[]>(length);
		for (let idx = 0; idx < m.length; idx++) {
			m[idx] = new Array<number>(length);
		}
		return m;
	}
	/** 从某一源点出发，找到到所有结点的最短路径
	 * 
	 * @param nodes 节点集合
	 * @param edges 边集合
	 * @param start 起点
	 * @param directed 是否有向图，缺省为无向
	 */
	static getShortedPathAll(nodes: NodeBase<any>[], edges: EdgeBase<any>[], start: NodeBase<any>, directed = false): NodeBase<any>[][] {
		let graph = GraphUtils.toGraphMatrix(nodes, edges, directed);
		let pos: number = GraphUtils.getNodePosition(nodes, start);
		let paths = GraphUtils.getMatrix(nodes.length);
		let dists = Dijkstra.getShortedPathAll(graph, pos, paths);
		let pathNodeMatrix = new Array();
		for (let path of paths) {
			let pathNodes = new Array<NodeBase<any>>();
			for (let n of path) {
				if (n == undefined) {
					break;
				}
				pathNodes.push(nodes[n]);
			}
			pathNodeMatrix.push(pathNodes);
		}
		return pathNodeMatrix;
	}
	/** 从某一源点出发，找到到某一结点的最短路径
	 * 
	 * @param nodes 节点集合
	 * @param edges 边集合
	 * @param start 起点
	 * @param end 终点
	 * @param directed 是否有向图，缺省为无向
	 */
	static getShortedPath(nodes: NodeBase<any>[], edges: EdgeBase<any>[], start: NodeBase<any>, end: NodeBase<any>, directed = false): NodeBase<any>[] {
		let graph = GraphUtils.toGraphMatrix(nodes, edges, directed);
		let startPos: number = GraphUtils.getNodePosition(nodes, start);
		let endPos: number = GraphUtils.getNodePosition(nodes, end);
		let path = new Array<number>(nodes.length);
		let dist = Dijkstra.getShortedPath(graph, startPos, endPos, path);
		let pathNodes = new Array<NodeBase<any>>();
		for (let n of path) {
			if (!n) {
				break;
			}
			pathNodes.push(nodes[n]);
		}
		return pathNodes;
	}

	/**
	 * 找到与指定节点相连的节点
	 * @param nodes 节点集
	 * @param edges 边集
	 * @param start 指定节点
	 * @param directed 是否有向图，缺省是无向图
	 */
	static getConnectedNodes(nodes: NodeBase<any>[], edges: EdgeBase<any>[], start: NodeBase<any>, directed = false): NodeBase<any>[] {
		let graph = GraphUtils.toGraphMatrix(nodes, edges, directed);
		let pos: number = GraphUtils.getNodePosition(nodes, start);
		let m = GraphUtils.getMatrix(nodes.length);
		let nodeIdxs = GraphUtils.getConectedbyBfs(graph, pos);
		let cverts = [];
		for (let i of nodeIdxs) {
			cverts.push(nodes[i]);
		}
		graph = null;
		m = null;
		nodeIdxs = null;
		return cverts;
	}
	/**
	 * 找到指定节点在节点集合中的位置
	 * @param nodes 节点集合
	 * @param v0 指定节点
	 * @return 位置，0-based. 如果没找到就返回 undefined;
	 */
	static getNodePosition(nodes: NodeBase<any>[], v0: NodeBase<any>): number {
		for (let i = 0; i < nodes.length; i++) {
			if (nodes[i].id == v0.id) {
				return i;
			}
		}
		return undefined;
	}
	/**
	 * 判断从一个节点出发，到另一个节点是否连通
	 * @param nodes 所有点集
	 * @param edges 所有边集
	 * @param start 起点
	 * @param end 终点
	 * @param directed 是否有向图
	 * @return 是否连通
	 */
	public static isConnected(nodes: NodeBase<any>[], edges: EdgeBase<any>[], start: NodeBase<any>, end: NodeBase<any>, directed: boolean): boolean {
		let graph = GraphUtils.toGraphMatrix(nodes, edges, directed);
		let startPos: number = GraphUtils.getNodePosition(nodes, start);
		let endPos = GraphUtils.getNodePosition(nodes, end);
		return GraphUtils.isConectedbyBfs(graph, startPos, endPos);

	}
	static getConectedbyBfs(graph: number[][], start: number): number[] {
		let row = graph.length
		let queue = []
		let i = start
		let visited = {}//记录遍历顺序
		let order = [] //记录顺序，给自己看的
		queue.push(i) //先把根节点加入
		while (queue.length) { //如果队列没有被清空，也就是还没遍历完毕
			for (let j = 0; j < row; j++) {
				if (graph[i][j]) { //如果是1
					if (!visited[j]) {
						queue.push(j)//队列加入未访问
					}
				}
			}
			queue.shift()//取出队列第一个
			visited[i] = true//记录已经访问
			while (visited[queue[0]]) {
				queue.shift()
			}
			order.push(i)//记录顺序
			i = queue[0]
		}
		queue = null;
		visited = null;
		return order;
	}
	static isConectedbyBfs(arr: number[][], start: number, end: number): boolean {
		let row = arr.length;
		let queue = [];
		let i = start;
		let visited = {};//记录遍历顺序
		let order = []; //记录顺序，给自己看的
		queue.push(i); //先把根节点加入
		while (queue.length) { //如果队列没有被清空，也就是还没遍历完毕
			for (let j = 0; j < row; j++) {
				if (arr[i][j]) { //如果是1
					if (!visited[j]) {
						queue.push(j);//队列加入未访问
					}
				}
			}
			queue.shift();//取出队列第一个
			visited[i] = true;//记录已经访问
			console.log("visit node:" + i);
			if (i == end) {
				return true;
			}
			while (visited[queue[0]]) {
				queue.shift();
			}
			order.push(i);//记录顺序
			i = queue[0];
		}
		queue = null;
		visited = null;
		order = null;
		return false;
	}

	/**
	 * 把业务点和关联数据转换为图的点和关联数据
	 * @param nodes 业务节点集合，如客户集合
	 * @param edges 业务关联集合，如客户关系集合
	 * @param idProp 可选参数，业务节点ID的属性名，如客户代码“code”，缺省为"id"
	 * @param sourceIdProp 可选参数，业务关联的源ID属性名，如如客户关联关系中的“sourceCustCode”，缺省为"sourceId"
	 * @param targetIdProp 可选参数，业务关联的目标ID属性名，如如客户关联关系中的“targetCustCode”，缺省为"targetId"
	 * @return 位置，0-based. 如果没找到就返回 undefined;
	 */
	static toGraphData<N, E>(nodes: Array<N>, edges: Array<E>, idProp = "id", sourceIdProp = "sourceId", targetIdProp = "targetId"): GraphData<N, E> {
		let nodeMap = {};
		let graphData = new GraphData<N, E>();
		graphData.nodes = new Array<NodeBase<N>>(nodes.length);
		graphData.edges = new Array<EdgeBase<E>>(edges.length);

		for (let i = 0; i < nodes.length; i++) {
			let nd = nodes[i];
			let node = new NodeBase<any>();
			node.id = nd[idProp];
			node.data = nd;
			nodeMap[node.id] = node;
			graphData.nodes[i] = node;
		}
		for (let i = 0; i < edges.length; i++) {
			let ed = edges[i];
			let edge: EdgeBase<E> = new EdgeBase<E>();
			edge.source = nodeMap[ed[sourceIdProp]];
			edge.target = nodeMap[ed[targetIdProp]];
			edge.data = ed;
			graphData.edges[i] = edge;
		}
		nodeMap = null;
		return graphData;
	}
}
/**
 * 图相关数据模型，节点基类。
 */
export class NodeBase<N> {
	/**
	 * 节点的ID
	 */
	id: string;
	/**
	 * 节点的业务数据，如Customer
	 */
	data: N;
}
/**
 * 图相关数据模型，连接节点的边基类
 */
export class EdgeBase<E> {
	/**
	 * 源节点的ID
	 */
	source: NodeBase<any>;
	/**
	 * 目标节点的ID
	 */
	target: NodeBase<any>;
	/**
	 * 源节点到目标节点的距离，用于计算最短路径
	 */
	distance = 1;
	/**
	 * 边相关的业务数据，如CustomerRelation
	 */
	data: E;
}
export class GraphData<N, E> {
	nodes: NodeBase<N>[];
	edges: EdgeBase<E>[];
}