MIT CS Graduate student in MIT Visualization Group.
Previously undergraduate member of @uwplse and @uwsampl.
Public
Edited
Oct 30, 2023
g = {
// Create a new directed graph
var g = new Graph();
// Set an object for the graph label
g.setGraph({});
// Default to assigning a new object as a label for each new edge.
g.setDefaultEdgeLabel(function() { return {}; });
// Add nodes to the graph. The first argument is the node id. The second is
// metadata about the node. In this case we're going to add labels to each of
// our nodes.
g.setNode("kspacey", { label: "Kevin Spacey", width: 144, height: 100 });
g.setNode("swilliams", { label: "Saul Williams", width: 160, height: 100 });
g.setNode("bpitt", { label: "Brad Pitt", width: 108, height: 100 });
g.setNode("hford", { label: "Harrison Ford", width: 168, height: 100 });
g.setNode("lwilson", { label: "Luke Wilson", width: 144, height: 100 });
g.setNode("kbacon", { label: "Kevin Bacon", width: 121, height: 100 });
// Add edges to the graph.
g.setEdge("kspacey", "swilliams", { minlen: 1, weight: 1 });
g.setEdge("swilliams", "kbacon", { minlen: 1, weight: 1 });
g.setEdge("bpitt", "kbacon", { minlen: 1, weight: 1 });
g.setEdge("hford", "lwilson", { minlen: 1, weight: 1 });
g.setEdge("lwilson", "kbacon", { minlen: 1, weight: 1 });
// specify rank distances between nodes
g.setEdge("kbacon", "swilliams", {minlen: -1, weight: 0});
g.setEdge("bpitt", "kbacon", {minlen: -1, weight: 0});
// g = simplify(g);
// const ranks = initRank(g);
networkSimplex(g);
return { g };
}
g.g.node("bpitt");
g.ranks
function networkSimplex(g) {
g = simplify(g);
// initialization
initRank(g);
var t = feasibleTree(g); // tree assignment
initLowLimValues(t);
initCutValues(t, g);
// find negative cuts
var e, f;
while ((e = leaveEdge(t))) {
f = enterEdge(t, g, e);
exchangeEdges(t, g, e, f);
}
}
initRank = longestPath
/*
* Initializes ranks for the input graph using the longest path algorithm. This
* algorithm scales well and is fast in practice, it yields rather poor
* solutions. Nodes are pushed to the lowest layer possible, leaving the bottom
* ranks wide and leaving edges longer than necessary. However, due to its
* speed, this algorithm is good for getting an initial ranking that can be fed
* into other algorithms.
*
* This algorithm does not normalize layers because it will be used by other
* algorithms in most cases. If using this algorithm directly, be sure to
* run normalize at the end.
*
* Pre-conditions:
*
* 1. Input graph is a DAG.
* 2. Input graph node labels can be assigned properties.
*
* Post-conditions:
*
* 1. Each node will be assign an (unnormalized) "rank" property.
*/
function longestPath(g) {
const ranks=[];
var visited = {};
function dfs(v) {
var label = g.node(v);
console.log(g.node(v));
if (visited.hasOwnProperty(v)) {
console.log('visited', g.node(v).label, visited);
ranks.push(v);
return label.rank;
}
visited[v] = true;
var rank = Math.min(...g.outEdges(v).map(e => {
if (e == null) {
return Number.POSITIVE_INFINITY;
}
/* IMPORTANT!!!! WE HAD TO MODIFY THIS TO ACCOUNT FOR CASES WHEN WE HAVE A CYCLE. IF WE EVER HIT A CYCLE, THEN WE SHOULD JUST SKIP THE RANK ASSIGNMENT. ALTERNATIVELY, WE COULD DELAY ADDING THE EXTRA EDGES UNTIL AFTER THIS FUNCTION HAS RUN AND LEAVE THE CODE UNCHANGED */
const dfs_rank = dfs(e.w);
if (dfs_rank === undefined) {
return Number.POSITIVE_INFINITY;
}
return dfs_rank - g.edge(e).minlen;
}));
if (rank === Number.POSITIVE_INFINITY) {
rank = 0;
}
ranks.push(rank);
console.log('assigning rank', rank);
return (label.rank = rank);
}
g.sources().forEach(dfs);
return ranks;
}
/*
* Constructs a spanning tree with tight edges and adjusted the input node's
* ranks to achieve this. A tight edge is one that is has a length that matches
* its "minlen" attribute.
*
* The basic structure for this function is derived from Gansner, et al., "A
* Technique for Drawing Directed Graphs."
*
* Pre-conditions:
*
* 1. Graph must be a DAG.
* 2. Graph must be connected.
* 3. Graph must have at least one node.
* 5. Graph nodes must have been previously assigned a "rank" property that
* respects the "minlen" property of incident edges.
* 6. Graph edges must have a "minlen" property.
*
* Post-conditions:
*
* - Graph nodes will have their rank adjusted to ensure that all edges are
* tight.
*
* Returns a tree (undirected graph) that is constructed using only "tight"
* edges.
*/
function feasibleTree(g) {
var t = new Graph({ directed: false });
// Choose arbitrary node from which to start our tree
var start = g.nodes()[0];
var size = g.nodeCount();
t.setNode(start, {});
var edge, delta;
while (tightTree(t, g) < size) {
edge = findMinSlackEdge(t, g);
delta = t.hasNode(edge.v) ? slack(g, edge) : -slack(g, edge);
shiftRanks(t, g, delta);
}
return t;
}
/*
* Finds a maximal tree of tight edges and returns the number of nodes in the
* tree.
*/
function tightTree(t, g) {
function dfs(v) {
g.nodeEdges(v).forEach(e => {
var edgeV = e.v,
w = (v === edgeV) ? e.w : edgeV;
if (!t.hasNode(w) && !slack(g, e)) {
t.setNode(w, {});
t.setEdge(v, w, {});
dfs(w);
}
});
}
t.nodes().forEach(dfs);
return t.nodeCount();
}
/*
* Finds the edge with the smallest slack that is incident on tree and returns
* it.
*/
function findMinSlackEdge(t, g) {
const edges = g.edges();
return edges.reduce((acc, edge) => {
let edgeSlack = Number.POSITIVE_INFINITY;
if (t.hasNode(edge.v) !== t.hasNode(edge.w)) {
edgeSlack = slack(g, edge);
}
if (edgeSlack < acc[0]) {
return [edgeSlack, edge];
}
return acc;
}, [Number.POSITIVE_INFINITY, null])[1];
}
function shiftRanks(t, g, delta) {
t.nodes().forEach(v => g.node(v).rank += delta);
}
Graph = graphlib.Graph
/*
* Returns a new graph with only simple edges. Handles aggregation of data
* associated with multi-edges.
*/
function simplify(g) {
let simplified = new Graph().setGraph(g.graph());
g.nodes().forEach(v => simplified.setNode(v, g.node(v)));
g.edges().forEach(e => {
let simpleLabel = simplified.edge(e.v, e.w) || { weight: 0, minlen: 1 };
let label = g.edge(e);
console.log(simpleLabel.minlen, label.minlen, Math.max(simpleLabel.minlen, label.minlen));
simplified.setEdge(e.v, e.w, {
weight: simpleLabel.weight + label.weight,
minlen: Math.max(simpleLabel.minlen, label.minlen)
});
});
return simplified;
}
/*
* Initializes cut values for all edges in the tree.
*/
function initCutValues(t, g) {
var vs = postorder(t, t.nodes());
vs = vs.slice(0, vs.length - 1);
vs.forEach(v => assignCutValue(t, g, v));
}
function assignCutValue(t, g, child) {
var childLab = t.node(child);
var parent = childLab.parent;
t.edge(child, parent).cutvalue = calcCutValue(t, g, child);
}
/*
* Given the tight tree, its graph, and a child in the graph calculate and
* return the cut value for the edge between the child and its parent.
*/
function calcCutValue(t, g, child) {
var childLab = t.node(child);
var parent = childLab.parent;
// True if the child is on the tail end of the edge in the directed graph
var childIsTail = true;
// The graph's view of the tree edge we're inspecting
var graphEdge = g.edge(child, parent);
// The accumulated cut value for the edge between this node and its parent
var cutValue = 0;
if (!graphEdge) {
childIsTail = false;
graphEdge = g.edge(parent, child);
}
cutValue = graphEdge.weight;
g.nodeEdges(child).forEach(e => {
var isOutEdge = e.v === child,
other = isOutEdge ? e.w : e.v;
if (other !== parent) {
var pointsToHead = isOutEdge === childIsTail,
otherWeight = g.edge(e).weight;
cutValue += pointsToHead ? otherWeight : -otherWeight;
if (isTreeEdge(t, child, other)) {
var otherCutValue = t.edge(child, other).cutvalue;
cutValue += pointsToHead ? -otherCutValue : otherCutValue;
}
}
});
return cutValue;
}
function initLowLimValues(tree, root) {
if (arguments.length < 2) {
root = tree.nodes()[0];
}
dfsAssignLowLim(tree, {}, 1, root);
}
function dfsAssignLowLim(tree, visited, nextLim, v, parent) {
var low = nextLim;
var label = tree.node(v);
visited[v] = true;
tree.neighbors(v).forEach(w => {
if (!visited.hasOwnProperty(w)) {
nextLim = dfsAssignLowLim(tree, visited, nextLim, w, v);
}
});
label.low = low;
label.lim = nextLim++;
if (parent) {
label.parent = parent;
} else {
// TODO should be able to remove this when we incrementally update low lim
delete label.parent;
}
return nextLim;
}
function leaveEdge(tree) {
return tree.edges().find(e => tree.edge(e).cutvalue < 0);
}
function enterEdge(t, g, edge) {
var v = edge.v;
var w = edge.w;
// For the rest of this function we assume that v is the tail and w is the
// head, so if we don't have this edge in the graph we should flip it to
// match the correct orientation.
if (!g.hasEdge(v, w)) {
v = edge.w;
w = edge.v;
}
var vLabel = t.node(v);
var wLabel = t.node(w);
var tailLabel = vLabel;
var flip = false;
// If the root is in the tail of the edge then we need to flip the logic that
// checks for the head and tail nodes in the candidates function below.
if (vLabel.lim > wLabel.lim) {
tailLabel = wLabel;
flip = true;
}
var candidates = g.edges().filter(edge => {
return flip === isDescendant(t, t.node(edge.v), tailLabel) &&
flip !== isDescendant(t, t.node(edge.w), tailLabel);
});
return candidates.reduce((acc, edge) => {
if (slack(g, edge) < slack(g, acc)) {
return edge;
}
return acc;
});
}
/*
* Returns the amount of slack for the given edge. The slack is defined as the
* difference between the length of the edge and its minimum length.
*/
function slack(g, e) {
return g.node(e.w).rank - g.node(e.v).rank - g.edge(e).minlen;
}
function exchangeEdges(t, g, e, f) {
var v = e.v;
var w = e.w;
t.removeEdge(v, w);
t.setEdge(f.v, f.w, {});
initLowLimValues(t);
initCutValues(t, g);
updateRanks(t, g);
}
function updateRanks(t, g) {
var root = t.nodes().find(v => !g.node(v).parent);
var vs = preorder(t, root);
vs = vs.slice(1);
vs.forEach(v => {
var parent = t.node(v).parent,
edge = g.edge(v, parent),
flipped = false;
if (!edge) {
edge = g.edge(parent, v);
flipped = true;
}
g.node(v).rank = g.node(parent).rank + (flipped ? edge.minlen : -edge.minlen);
});
}
graphlib = import("https://cdn.jsdelivr.net/npm/@dagrejs/graphlib/+esm");
preorder = graphlib.alg.preorder
postorder = graphlib.alg.postorder
/*
* Returns true if the edge is in the tree.
*/
function isTreeEdge(tree, u, v) {
return tree.hasEdge(u, v);
}
/*
* Returns true if the specified node is descendant of the root node per the
* assigned low and lim attributes in the tree.
*/
function isDescendant(tree, vLabel, rootLabel) {
return rootLabel.low <= vLabel.lim && vLabel.lim <= rootLabel.lim;
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
