The aim is to develop a function that quickly traces sub-graphs for a list of nodes, given an existing adjacency list implementation, and returns a list of connected ID's in addition to the original list
I am finding it hard to understand what to return, and how/where to add the found ID's to the original list. The real issue is deciding:
I have a skeleton code, but am starting at it not sure how to finish it off. Can you help please?
//------------------------------------------
// Adjaceny List Class
//-------------------------------------------
class Graph {
constructor(){
this.adjacencyList = new Map();
}
addNode(node){
this.adjacencyList.set(node, new Set());
}
addEdge(node1, node2){
this.adjacencyList.get(node1).set(node2);
}
getNeighboors(node){
return this.adjacencyList.get(node);
}
hasEdge(node1, node2){
return this.adjacencyList.get(node1).has(node2);
}
}
can anyone show me what to do with this please so it returns just the list of nodes in the sub-graphs, including the original ID's? Thanks
function traceSubGraph(ID_list, adjacency) {
let layer_IDs = []
for (let ID in ID_list) {
layer_IDs = adjacency.getNeighboors(ID);
if (layer_IDs.length) {
// add new valid nodes to original list of nodes
ID_list.concat(layer_IDs);
// keep recursing, but how to add the new values?
return traceSubGraph(layer_IDs, adjacency)
}
else {
// stop recursing, what to do here?
}
}
// what to return? ID_list, but where to add the new found nodes?
}
function processGraph(graph) {
// 1. Setup variables and define promotable types
const prom_types = [
'incident',
'task',
'impact',
'event',
'sighting',
];
var returnGraph = {};
var nodes = graph.nodes;
var edges = graph.edges;
var scratch_nodes = [];
var scratch_edges = [];
var promotable_nodes = [];
var prom_IDs = [];
var collect_IDs = [];
var promotable_edges = [];
var adjacency = new Graph();
// 2. Fill adjacency list with nodes, and get any top level promotables
for (let node in nodes) {
adjacency.addNode(node['id']);
if (node['type'] in prom_types) {
prom_IDs.push(node.id);
}
}
// 3. Fill adjacency list with edges
for (let edge in edges) {
adjacency.addEdge(edge['source'], edge['target']);
}
// 4. Now trace out the promotable
collect_IDs = traceSubGraph(prom_IDs, adjacency);
}
I had worked out that peering through the nodes and edges array was not fast, and then just manually using if/else to go down 3 or 4 layers was not good either. I then found this adjacency list class online. I have managed to fill it relatively easily, but it is using it to trace the subgraph that has me bedevilled.
Particularly the fact that we are iterating through a list, when we decide whether to recurse or not, makes it seem difficult for me as a noob.
I have tried looking at it for hours, and searching the web for tutorials on recursing, but i am still unsure as to the best approach.
fix Graph
The nested Map should be a Set because there is no value being associated with the keys. addEdge would break under certain conditions. getNeighboors would return undefined in some cases. addNode wasn't needed for the purposes of this answer -
class Graph {
constructor() {
this.t = new Map()
}
addEdge(node1, node2) {
const s = this.t.get(node1)
if (s == null)
this.t.set(node1, new Set([node2])) // Set, not Map
else
s.add(node2) // .add, not .set
}
getAdjacencies(node) {
return this.t.get(node) ?? new Set()
}
}
Let's construct a concrete graph to use for the rest of our answer. Next time you will provide this in your question -
const g = new Graph()
g.addEdge("A", "B")
g.addEdge("B", "C")
g.addEdge("B", "D")
g.addEdge("D", "E")
g.addEdge("P", "Q")
g.addEdge("Q", "P")
g.addEdge("W", "X")
g.addEdge("W", "Y")
g.addEdge("X", "Z")
g.addEdge("Y", "Z")
g.addEdge("Z", "W")
single entry point
First we will write dir to traverse a single node entry point of our graph. I'm calling it dir because it generates paths to our nodes, much like listing the contents of a directory in a file system -
class Graph {
//...
*dir(node, path = Array(), visited = new Set()) {
yield [...path, node]
path.push(node)
visited.add(node)
for (const adj of this.getAdjacencies(node)) {
if (!visited.has(adj)) {
yield* this.dir(adj, path, visited)
}
}
path.pop()
}
}
Each path is a sequence of nodes, we can visualize them as familiar string paths by joining the segments with a separator, / -
for (const path of g.dir("A")) {
console.log(path.join("/"))
}
A
A/B
A/B/C
A/B/D
A/B/D/E
But more importantly we can manipulate these paths to extract the data we care about for a particular traversal. In this example, we find all unique nodes in the subgraph of A by selecting the basename of each path -
for (const path of g.dir("A")) {
console.log(path.at(-1)) // basename
}
A
B
C
D
E
multiple entry points
Currently dir only accepts a single node entry point. To complete the rest of your problem, we can write dirs that accepts an array of nodes representing multiple entry points to the graph -
class Graph {
//...
*dirs(nodes) {
for (const node of nodes) {
yield* this.dir(node)
}
}
}
Now we call dirs with an array of entry points -
for (const path of g.dirs(["B", "W"])) {
console.log(path.join("/"))
}
B
B/C
B/D
B/D/E
W
W/X
W/X/Z
W/Y
Or again using path manipulation to collect all nodes reachable from B and W -
console.log(Array.from(g.dirs(["B", "W"]), path => path.at(-1)))
[ "B", "C", "D", "E", "W", "X", "Z", "Y" ]
remarks
Hopefully you can see writing dir in this way means we offload the hard choices to users of our program. Instead of trying to predict the needs of the traversal consumer, dir produces a path to each reachable node. Now each program that needs to traverse the graph can make distinct choices based on that program's unique context.
And maybe you noticed in the dirs example that we only produced one path to Z even though multiple paths existed. This is a concern I will address in my next answer to this question.
demo
class Graph {
constructor() {
this.t = new Map()
}
addEdge(node1, node2) {
const s = this.t.get(node1)
if (s == null) this.t.set(node1, new Set([node2]))
else s.add(node2)
}
getAdjacencies(node) {
return this.t.get(node) ?? new Set()
}
*dir(node, path = Array(), visited = new Set()) {
yield [...path, node]
path.push(node)
visited.add(node)
for (const adj of this.getAdjacencies(node)) {
if (!visited.has(adj)) {
yield* this.dir(adj, path, visited)
}
}
path.pop()
}
*dirs(nodes) {
for (const node of nodes) {
yield* this.dir(node)
}
}
}
const g = new Graph()
g.addEdge("A", "B"); g.addEdge("B", "C"); g.addEdge("B", "D"); g.addEdge("D", "E"); g.addEdge("P", "Q"); g.addEdge("Q", "P"); g.addEdge("W", "X"); g.addEdge("W", "Y"); g.addEdge("X", "Z"); g.addEdge("Y", "Z"); g.addEdge("Z", "W")
for (const path of g.dir("A")) {
console.log(path.join("/"))
}
for (const path of g.dir("A")) {
console.log(path.at(-1))
}
for (const path of g.dirs(["B", "W"])) {
console.log(path.join("/"))
}
console.log(Array.from(g.dirs(["B", "W"]), path => path.at(-1))).as-console-wrapper { min-height: 100%; top: 0 }typescript
type Node = string
class Graph {
t: Map<Node, Set<Node>>
constructor() {
this.t = new Map()
}
addEdge(node1: Node, node2: Node): void {
const s = this.t.get(node1)
if (s == null) this.t.set(node1, new Set([node2]))
else s.add(node2)
}
getAdjacencies(node: Node): Set<Node> {
return this.t.get(node) ?? new Set()
}
*dir(
node: Node,
path = Array<Node>(),
visited = new Set<Node>(),
): Generator<Node[]> {
yield [...path, node]
path.push(node)
visited.add(node)
for (const adj of this.getAdjacencies(node)) {
if (!visited.has(adj)) {
yield* this.dir(adj, path, visited)
}
}
path.pop()
}
*dirs(nodes: Node[]): Generator<Node[]> {
for (const node of nodes) {
yield* this.dir(node)
}
}
}