/**
|
* represents an undirected graph
|
*/
|
export class Graph {
|
/**
|
* creates a new empty graph.
|
* */
|
constructor( ) {
|
this.adjacent = new Map();
|
this.vertexAttribute = new Map();
|
}
|
|
/**
|
* (vertex:integer) => this
|
* @param vertex {Number} a vertex
|
* @return this graph
|
* */
|
addVertex(vertex) {
|
if (! this.adjacent.has(vertex)) {
|
let [isInteger, i] = toInteger(vertex);
|
if (isInteger) {
|
this.adjacent.set(i, []);
|
} else {
|
throw new TypeError(`Argument ${vertex} is not a valid vertex`)
|
}
|
}
|
return this;
|
}
|
|
/**
|
* (u: integer, v: integer) => undefined
|
* @param u {Number} a vertex of edge
|
* @param v {Number} a vertex of edge
|
* */
|
addEdge(u, v) {
|
this.addVertex(u);
|
this.addVertex(v);
|
const vNeighbor = this.adjacent.get(v);
|
if (!vNeighbor.includes(u) ) {
|
vNeighbor.push(u);
|
}
|
const uNeighbor = this.adjacent.get(u);
|
if(!uNeighbor.includes(v)) {
|
uNeighbor.push(v);
|
}
|
return this;
|
}
|
|
/**
|
* merge a map of attribute to a vertex. Usage example:
|
* ```
|
* let g = new Graph();
|
* g.addVertex(1);
|
* g.mergeAttribute(1, {'color': 0});
|
* ```
|
* @param v {Number} a vertex of graph
|
* @param p {object|Map} attributes of the vertex, an empty object is allowed, but
|
* undefined, empty array is not allow
|
* */
|
mergeAttribute(v, p) {
|
if (!this.adjacent.has(v)) {
|
throw new Error(`Graph does not include vertex ${v}`);
|
}
|
if (!p) {
|
throw new Error(`Bad attribute`)
|
}
|
let newAttribute = (p instanceof Map) ? p : new Map(Object.entries(p));
|
let oldAttribute = this.vertexAttribute.get(v) || new Map();
|
this.vertexAttribute.set(v, new Map([...oldAttribute, ...newAttribute]));
|
return this;
|
}
|
|
getAttribute(vertex) {
|
if (this.adjacent.has(vertex)) {
|
return this.vertexAttribute.get(vertex);
|
} else {
|
throw new Error(`Graph does not include vertex ${v}`);
|
}
|
}
|
|
/**
|
* example usage:
|
* ```
|
* for (let v of g.vertices() ) {
|
* // do something with v
|
* }
|
* ```
|
* @return vertices array of the graph
|
* */
|
vertices() {
|
return this.adjacent.keys();
|
}
|
|
forEachVertices(action) {
|
for(const v of this.vertices() ) {
|
action(v);
|
}
|
}
|
|
/**
|
* @param v {integer} a vertex of graph.
|
* @return neighbor array of v
|
* */
|
adjacentOf(v) {
|
if (!this.adjacent.has(v)) {
|
throw new Error(`Graph does not include vertex ${v}`);
|
}
|
return this.adjacent.get(v);
|
}
|
|
forEachEdges(action) {
|
const visitedEdges = new Map();
|
for(const start of this.vertices() ) {
|
for(const end of this.adjacentOf(start)) {
|
const first = (start > end) ? start : end;
|
const second = (start > end) ? end : start;
|
if(visitedEdges.has(first)) {
|
const visitedAdjacent = visitedEdges.get(first);
|
if( !visitedAdjacent.has(second) ) {
|
visitedAdjacent.add(second);
|
action(start, end);
|
}
|
}else {
|
const adjacent = new Set();
|
visitedEdges.set(first, adjacent);
|
adjacent.add(second);
|
action(start, end);
|
}
|
}
|
}
|
}
|
|
|
toString() {
|
let text = "";
|
let sortedKeys = [...this.adjacent.keys()].sort();
|
let lastKey = sortedKeys.pop();
|
let adjacentFn = (key) => `[${this.adjacent.get(key).join(', ')}]`;
|
for( let key of sortedKeys) {
|
text += `${key} → ${adjacentFn(key)}\n`
|
}
|
text += `${lastKey} → ${adjacentFn(lastKey)}`;
|
return text;
|
}
|
}
|
|
function toInteger(value) {
|
if (isNaN(value)) {
|
return [false, NaN];
|
}
|
let x = parseFloat(value);
|
let i = x | 0;
|
return [i === x, i];
|
}
|
