/**
* Creates an instance of a SoupGraph
*
* @constructor
*/
function SoupGraph() {
// Always working reference to this
var self = this;
// Make the graph an event emitter, if possible
if (SoupGraph.eventsAvailable)
SoupEvents.makeEventEmitter(this);
else
console.warn("SoupEvents is not available. The graph will be unable to register event listeners and dispatch events");
// Collection of nodes
var nodes = {};
Object.defineProperties(this, {
/**
* An array of all node handles in the graph. This is not static, even though the documentation says so
*
* @return {Array}
* @memberof SoupGraph
* @instance
*/
nodes: {
get: function() {
var ids = [];
for (var id in nodes) {
ids.push(id);
}
return ids;
}
}
});
/**
* Adds a node to the graph
*
* @param {string} id The handle to use for the node
* @param [data] Any data to store in the node
*
* @return {string} The handle of the node. Same as the "id" parameter
*/
this.addNode = function(id, data) {
// Check if the ID is already taken
if (typeof nodes[id] != "undefined")
throw "Node " + id + " already exists";
// Add the node
nodes[id] = new SoupGraphNode(data);
// Emit the "nodeadded" event
dispatchEvent("nodeadded", id);
// Return the identifier
return id;
};
/**
* Removes a node from the graph. All edges to and from the node are removed along with it
*
* @param {string} node Handle for the node to remove
*/
this.removeNode = function(node) {
var id = getValidNode(node).id;
// Check if the node exists
if (typeof nodes[id] == "undefined")
throw "Node " + id + " does not exist in this graph";
// Remove all edges to and from the node
nodes[id].clear(this);
// Remove the node
delete nodes[id];
// Emit the "noderemoved" event
dispatchEvent("noderemoved", id);
}
/**
* Adds an edge between two nodes in the graph
*
* @param {object} properties Properties for the edge to add
* @param {string} properties.fromNode Handle for the node the edge is going from
* @param {string} properties.toNode Handle for the node the edge is going to
* @param {string} properties.name Name of the edge
* @param {number} properties.length Length of the edge
*/
this.addEdge = function(properties) {
// Default properties
var props = {
fromNode: null,
toNode: null,
length: null,
name: null
};
// Merge the default props with the given props
for (var prop in properties) {
props[prop] = properties[prop];
}
// Make the edge
var edge = new SoupGraphEdge(props.fromNode, props.toNode, props.name, props.length);
// Add the edge
nodes[edge.fromNode].addEdge(edge);
// Emit the "edgeadded" event
dispatchEvent("edgeadded", edge);
};
/**
* Removes an edge from the graph
*
* @param {SoupGraphEdge} edge The edge to remove
*/
this.removeEdge = function(edge) {
// Check if the edge is valid
if (!(edge instanceof SoupGraphEdge))
throw "Given edge is not an edge";
// Remove the edge
nodes[edge.fromNode].removeEdge(edge);
// Emit the "edgeremoved" event
dispatchEvent("edgeremoved", edge);
};
/**
* Gets an array of all edges going from a node. Edges are read-only
*
* @param {string} node Handle for the node to get edges from
*
* @return {Array} An array containing all current edges from the given node
*/
this.getEdgesFrom = function(node) {
node = getValidNode(node);
return node.edgesOut;
};
/**
* Gets an array of all edges going to a node. Edges are read-only
*
* @param {string} node Handle for the node to get edges to
*
* @return {Array} An array containing all current edges to the given node
*/
this.getEdgesTo = function(node) {
node = getValidNode(node);
return node.edgesIn;
};
/**
* Gets an edge with a given name from a node
*
* @param {string} node Handle for the node to get the edge from
* @param {string} name Name of the edge to get
*/
this.getNamedEdgeFrom = function(node, name) {
var edges = this.getEdgesFrom(node);
for (var i = 0; i < edges.length; i++) {
if (edges[i].name == name)
return edges[i];
}
throw "No such edge " + name + " from node " + node;
};
/**
* Gets an edge with a given name to a node
*
* @param {string} node Handle for the node to get the edge to
* @param {string} name Name of the edge to get
*/
this.getNamedEdgeTo = function(node, name) {
var edges = this.getEdgesTo(node);
for (var i = 0; i < edges.length; i++) {
if (edges[i].name == name)
return edges[i];
}
throw "No such edge " + name + " to node " + node;
};
/**
* Gets an array of all edges going from a node to another node
*
* @param {string} from Handle for the node to get edges from
* @param {string} to Handle for the node to get edges to
*
* @return {Array} Array containing all edges currently going between the nodes in the direction specified
*/
this.getEdges = function(from, to) {
from = getValidNode(from);
getValidNode(to);
var unprocessedEdges = from.edgesOut;
var edges = [];
unprocessedEdges.forEach(function(edge, i) {
if (edge.toNode == to)
edges.push(edge);
});
return edges;
};
/**
* Get the data held by a node
*
* @param {string} node Handle for the node to get data from
*
* @return The data held by the node
*/
this.getData = function(node) {
node = getValidNode(node);
return node.data;
};
/**
* Set the data held by a node
*
* @param {string} node Handle for the node to set data to
* @param data The data to store in the node
*/
this.setData = function(node, data) {
var id = node;
node = getValidNode(node);
node.data = data;
// Emit the "datachanged" event
dispatchEvent("datachanged", {newData: data, node: id});
};
/**
* Checks if a handle's node is in the graph
*
* @param {string} node The node handle to check
*
* @return {boolean} True if the node is in the graph, false otherwise
*/
this.isValidNode = function(node) {
try {
getValidNode(node);
return true;
} catch (e) {
return false;
}
};
// Function to dispatch events if events are available
function dispatchEvent(type, data) {
if (typeof self.dispatchEvent == "function")
self.dispatchEvent(new CustomEvent(type, {detail: data}));
};
// Get the node with the ID and throw an exception if it does not exist
function getValidNode(node) {
if (typeof nodes[node] == "undefined")
throw "Invalid node: " + node;
return nodes[node];
};
// Constructor for a node
function SoupGraphNode(data) {
// Edges to and from this node
var incomingEdges = [];
var outgoingEdges = [];
Object.defineProperties(this, {
edgesIn: {
get: function() {
var copy = [];
incomingEdges.forEach(function(edge) {
copy.push(edge);
});
return copy;
}
},
edgesOut: {
get: function() {
var copy = [];
outgoingEdges.forEach(function(edge) {
copy.push(edge);
});
return copy;
}
}
});
// Object held by the node
var data = data;
Object.defineProperties(this, {
data: {
get: function() {return data;},
set: function(newData) {data = newData;}
}
});
// Add an incoming edge
this._addIncomingEdge = function(edge) {
// Check if the edge is valid
if (!(edge instanceof SoupGraphEdge))
throw "Given edge is not a SoupGraphEdge";
// Check if the edge is already registered
if (incomingEdges.indexOf(edge) >= 0)
throw "The given edge is already coming in to this node";
// Check if the edge actually goes to this node
if (nodes[edge.toNode] != this)
throw "The edge is not going to this node";
// Add the edge
incomingEdges.push(edge);
};
// Remove an incoming edge
this._removeIncomingEdge = function(edge) {
// Find the edge in the node
var i = incomingEdges.indexOf(edge);
if (i < 0)
throw "The given edge is not connected to this node";
// Remove the edge
incomingEdges.splice(i, 1);
};
// Add an outgoing edge
this.addEdge = function(edge) {
// Check if the edge is valid
if (!(edge instanceof SoupGraphEdge))
throw "Given edge is not a SoupGraphEdge";
// Check if the edge is already registered
if (outgoingEdges.indexOf(edge) >= 0)
throw "The given edge is already going out of this node";
// Check if the edge actually goes to this node
if (nodes[edge.fromNode] != this)
throw "The edge is not coming from this node";
// Check if this node already has an outgoing edge with the name, if the name is set
if (edge.name != null) {
for (var i = 0; i < outgoingEdges.length; i++) {
if (outgoingEdges.name == edge.name)
throw "An edge with the name " + edge.name + " already goes from node " + edge.fromNode;
}
}
// Add the edge
outgoingEdges.push(edge);
// Add the edge as incoming to the target node
nodes[edge.toNode]._addIncomingEdge(edge);
};
// Remove an incoming edge
this.removeEdge = function(edge) {
// Find the edge in the node
var i = outgoingEdges.indexOf(edge);
if (i < 0)
throw "The given edge is not connected to this node";
// Remove the edge
outgoingEdges.splice(i, 1);
// Remove the edge from the target node
nodes[edge.toNode]._removeIncomingEdge(edge);
};
// Clear all edges to and from the node
this.clear = function(parent) {
incomingEdges.forEach(function(edge) {
parent.removeEdge(edge);
});
outgoingEdges.forEach(function(edge) {
parent.removeEdge(edge);
});
};
};
// Constructor for a SoupGraphEdge
function SoupGraphEdge(fromNode, toNode, name, length) {
// Validate the data
getValidNode(fromNode);
getValidNode(toNode);
if (typeof length != "undefined" && isNaN(length))
throw "Length must be a number!";
length = parseFloat(length);
// Handle for the node the edge is going from
this.fromNode = fromNode;
// Handle for the node the edge is going from
this.toNode = toNode;
// Name of the edge
this.name = name == null ? undefined : name.toString();
// Length of the edge
this.length = parseFloat(length);
// Freeze the object so changes can't be made
Object.freeze(this);
};
};
/**
* Automatic graph builders for often used topologies
*
* @memberof SoupGraph
*/
SoupGraph.graphBuilders = {
/**
* Creates a 2D grid graph where all nodes are connected bidirectionally with all four neighbour nodes.
* The nodes will have handles on the format "x,y"
*
* @param {number} width Width of the grid. This-1 is the max "x" coordinate
* @param {number} height Height of the grid. This-1 is the maz "y" coordinate
* @param {SoupGraph} [graph] A SoupGraph to make a grid of. If not provided, a new one will be made
*
* @return {SoupGraph} Either the provided graph, or a new one
*
* @memberof SoupGraph.graphBuilders
*/
Grid2D: function(width, height, graph) {
// Check if width and height are valid numbers
if (isNaN(width) || width < 1)
throw "Width must be a number greater than 0";
if (isNaN(height) || height < 1)
throw "Height must be a number greater than 0";
// Make the graph if one was not provided
if (!(graph instanceof SoupGraph))
graph = new SoupGraph();
// Make all nodes
for (var y = 0; y < height; y++) {
for (var x = 0; x < width; x++) {
graph.addNode(x + "," + y);
}
}
// Connect all nodes
for (var y = 0; y < height; y++) {
for (var x = 0; x < width; x++) {
var edges = [
{fromNode: x + "," + y, toNode: x + "," + (y-1), name: SoupGraph.N, length: 1},
{fromNode: x + "," + y, toNode: (x+1) + "," + y, name: SoupGraph.E, length: 1},
{fromNode: x + "," + y, toNode: x + "," + (y+1), name: SoupGraph.S, length: 1},
{fromNode: x + "," + y, toNode: (x-1) + "," + y, name: SoupGraph.W, length: 1}
];
for (var i = 0; i < edges.length; i++) {
try {
graph.addEdge(edges[i]);
} catch (e) {}
}
}
}
// Return the graph
return graph;
},
/**
* Creates a 3D grid graph where all nodes are connected bidirectionally with all six neighbour nodes.
* The nodes will have handles on the format "x,y,z"
*
* @param {number} width Width of the grid. This-1 is the max "x" coordinate
* @param {number} height Height of the grid. This-1 is the max "y" coordinate
* @param {number} length Height of the grid. This-1 is the max "z" coordinate
* @param {SoupGraph} [graph] A SoupGraph to make a grid of. If not provided, a new one will be made
*
* @return {SoupGraph} Either the provided graph, or a new one
*
* @memberof SoupGraph.graphBuilders
*/
Grid3D: function(width, height, length, graph) {
// Check if width and height are valid numbers
if (isNaN(width) || width < 1)
throw "Width must be a number greater than 0";
if (isNaN(height) || height < 1)
throw "Height must be a number greater than 0";
if (isNaN(length) || length < 1)
throw "Length must be a number greater than 0";
// Make the graph if one was not provided
if (!(graph instanceof SoupGraph))
graph = new SoupGraph();
// Make all nodes
for (var z = 0; z < length; z++) {
for (var y = 0; y < height; y++) {
for (var x = 0; x < width; x++) {
graph.addNode(x + "," + y + "," + z);
}
}
}
// Connect all nodes
for (var z = 0; z < length; z++) {
for (var y = 0; y < height; y++) {
for (var x = 0; x < width; x++) {
var edges = [
{fromNode: x + "," + y + "," + z, toNode: x + "," + (y-1) + "," + z, name: SoupGraph.N, length: 1},
{fromNode: x + "," + y + "," + z, toNode: (x+1) + "," + y + "," + z, name: SoupGraph.E, length: 1},
{fromNode: x + "," + y + "," + z, toNode: x + "," + (y+1) + "," + z, name: SoupGraph.S, length: 1},
{fromNode: x + "," + y + "," + z, toNode: (x-1) + "," + y + "," + z, name: SoupGraph.W, length: 1},
{fromNode: x + "," + y + "," + z, toNode: x + "," + y + "," + (z-1), name: SoupGraph.U, length: 1},
{fromNode: x + "," + y + "," + z, toNode: x + "," + y + "," + (z+1), name: SoupGraph.D, length: 1}
];
for (var i = 0; i < edges.length; i++) {
try {
graph.addEdge(edges[i]);
} catch (e) {}
}
}
}
}
// Return the graph
return graph;
},
/**
* Builds a graph from a previously {@link SoupGraph#save}d graph
*
* @param {string} json JSON representation of a previously {@link SoupGraph#save}d graph
*
* @return {SoupGraph} A SoupGraph made from the JSON.
* @see {@link SoupGraph#load}
*/
fromJSON: function(json) {
var graph = new SoupGraph();
graph.load(json);
return graph;
}
};
Object.defineProperties(SoupGraph, {
/**
* Constant "North"
*
* @memberof SoupGraph
* @readonly
*/
N: {get: function() {return "N";}},
/**
* Constant "East"
*
* @memberof SoupGraph
* @readonly
*/
E: {get: function() {return "E";}},
/**
* Constant "South"
*
* @memberof SoupGraph
* @readonly
*/
S: {get: function() {return "S";}},
/**
* Constant "West"
*
* @memberof SoupGraph
* @readonly
*/
W: {get: function() {return "W";}},
/**
* Constant "Up"
*
* @memberof SoupGraph
* @readonly
*/
U: {get: function() {return "U";}},
/**
* Constant "Down"
*
* @memberof SoupGraph
* @readonly
*/
D: {get: function() {return "D";}},
/**
* Checks if SoupGraphs are able to register event listeners and dispatch events
*
* @memberof SoupGraph
* @readonly
*/
eventsAvailable: {get: function() {return typeof SoupEvents != "undefined" }}
});
/**
* Saves a graph as JSON
*
* @return {string} JSON-representation of the graph
*/
SoupGraph.prototype.save = function() {
// The object which will eventually be turned to JSON
var graph = {};
// Get all nodes
var nodes = this.nodes;
// Iterate over all nodes
for (var i = 0; i < nodes.length; i++) {
var node = nodes[i];
graph[node] = {
edges: [],
data: this.getData(node)
};
// Get all edges from the node
var edges = this.getEdgesFrom(node);
// Iterate over all the edges
for (var j = 0; j < edges.length; j++) {
graph[node].edges.push(edges[j]);
};
}
// Return the JSON
return JSON.stringify(graph);
};
/**
* Loads a graph from JSON. May be used to add one graph to another, but will fail if this graph and the graph loaded contain nodes with the same IDs
*
* @param {string} json JSON-representaion of a graph made with {@link SoupGraph#save}
* @see {@link SoupGraph.graphBuilders#fromJSON}
*/
SoupGraph.prototype.load = function(json) {
// Parse the JSON
var graph = JSON.parse(json);
// Iterate over all the nodes in order to create them
for (var node in graph) {
var data = graph[node].data;
// Add the node to the graph
this.addNode(node, data);
}
// Iterate over all the nodes again in order to add the edges
for (var node in graph) {
var edges = graph[node].edges;
// Add the edges
for (var i = 0; i < edges.length; i++) {
this.addEdge(edges[i]);
}
}
};