0.0.1 • Published 3 years ago
graph-ds v0.0.1
graph-ds
Common operations of data structure graph
Function
| 原始类型 | 目标类型 | 方法 |
|---|---|---|
| 边数组 | 邻接矩阵 | edgesetArray_adjacencyMatrix(vertices, edges, keyMap) => { vertices, matrix } |
| 邻接矩阵 | 边数组 | adjacencyMatrix_edgesetArray(vertices, matrix, keyMap) => { vertices, edges } |
| 边数组 | 十字链表 | edgesetArray_orthogonalList(vertices, edges, keyMap) => verticesMap |
| 邻接矩阵 | 十字链表 | adjacencyMatrix_orthogonalList(vertices, matrix, keyMap) => verticesMap |
API
| 参数 | 说明 | 类型 | 默认值 | 版本 |
|---|---|---|---|---|
| vertices | 顶点 | array{} | - | |
| edges | 边 | array{} | - | |
| matrix | 矩阵 | array[] | - | |
| keyMap | vertices的键值映射 | object | { id: 'id', beginId: 'beginId', endId: 'endId', weight: 'weight' } |
Usage
const nodes = [{
idnum: 'v0', name: 0,
}, {
idnum: 'v1', name: 1,
}, {
idnum: 'v2', name: 2,
}, {
idnum: 'v3', name: 3,
}, {
idnum: 'v4', name: 4,
}];
const relationsId = [{
beginId: 'v0', endId: 'v3', weight: 1,
}, {
beginId: 'v1', endId: 'v0', weight: 1,
}, {
beginId: 'v1', endId: 'v2', weight: 2,
}, {
beginId: 'v2', endId: 'v0', weight: 3,
}, {
beginId: 'v2', endId: 'v1', weight: 4,
}];
const relationsIndex = [{
beginIndex: 0, endIndex: 3, weight: 1,
}, {
beginIndex: 1, endIndex: 0, weight: 1,
}, {
beginIndex: 1, endIndex: 2, weight: 2,
}, {
beginIndex: 2, endIndex: 0, weight: 3,
}, {
beginIndex: 2, endIndex: 1, weight: 4,
}];
const matrixMin = [
[0, Infinity, Infinity, 1],
[1, 0, 2],
[3, 4, 0],
];
const resultRelationsIndex = [{
beginId: 0, endId: 3, weight: 1,
}, {
beginId: 1, endId: 0, weight: 1,
}, {
beginId: 1, endId: 2, weight: 2,
}, {
beginId: 2, endId: 0, weight: 3,
}, {
beginId: 2, endId: 1, weight: 4,
}];
const resultMatrix = [
[0, Infinity, Infinity, 1, Infinity],
[1, 0, 2, Infinity, Infinity],
[3, 4, 0, Infinity, Infinity],
[Infinity, Infinity, Infinity, 0, Infinity],
[Infinity, Infinity, Infinity, Infinity, 0],
];
import {
edgesetArray_adjacencyMatrix, adjacencyMatrix_edgesetArray, edgesetArray_orthogonalList, adjacencyMatrix_orthogonalList,
} from '../src/index';
test('edgesetArray_adjacencyMatrix id', () => {
const { matrix: value } = edgesetArray_adjacencyMatrix(nodes, relationsId, { id: 'idnum' });
expect(value).toEqual(resultMatrix);
});
test('edgesetArray_adjacencyMatrix index', () => {
const { matrix: value } = edgesetArray_adjacencyMatrix(nodes, relationsIndex, { beginId: 'beginIndex', endId: 'endIndex' });
expect(value).toEqual(resultMatrix);
});
test('adjacencyMatrix_edgesetArray id', () => {
const { edges: value } = adjacencyMatrix_edgesetArray(nodes, matrixMin, { id: 'idnum' });
expect(value).toEqual(relationsId);
});
test('adjacencyMatrix_edgesetArray index', () => {
const { edges: value } = adjacencyMatrix_edgesetArray(nodes, matrixMin);
expect(value).toEqual(resultRelationsIndex);
});
test('edgesetArray_orthogonalList id', () => {
const value = edgesetArray_orthogonalList(nodes, relationsId, { id: 'idnum' });
expect(value).not.toBeUndefined();
expect(value).not.toBeUndefined();
});
test('edgesetArray_orthogonalList index', () => {
const value = edgesetArray_orthogonalList(nodes, relationsIndex, { beginId: 'beginIndex', endId: 'endIndex' });
expect(value).not.toBeUndefined();
expect(value).not.toBeUndefined();
});
test('adjacencyMatrix_orthogonalList id', () => {
const value = adjacencyMatrix_orthogonalList(nodes, matrixMin, { id: 'idnum' });
expect(value).not.toBeUndefined();
expect(value).not.toBeUndefined();
});
test('adjacencyMatrix_orthogonalList index', () => {
const value = adjacencyMatrix_orthogonalList(nodes, matrixMin);
expect(value).not.toBeUndefined();
expect(value).not.toBeUndefined();
});