graph-ds

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();
});