-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.js
97 lines (72 loc) · 1.9 KB
/
index.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
const arccore = require("@encapsule/arccore");
// create a digraph object
let digraph = arccore.graph.directed.create().result;
/**
Example 1. Depth first traversal to obtain topological sort.
**/
// add some vertices
digraph.addVertex("a");
digraph.addVertex("b");
digraph.addVertex("c");
digraph.addVertex("d");
/**
connect with edges so we have a directed graph that looks like:
a
/ \
b c
\
d
**/
digraph.addEdge({e: {u: "a", v: "b"}});
digraph.addEdge({e: {u: "a", v: "c"}});
digraph.addEdge({e: {u: "c", v: "d"}});
/**
Do a depth-first traversal on the graph, and create a list
of the vertices in topographical order
**/
// an array to store the ordered vertex list
const inOrder = [];
// a callback function that will be called on the dft as each vertex is visited.
const discoverVertex = ({u, g}) => {
inOrder.push(u);
return true;
}
let dftResponse = arccore.graph.directed.depthFirstTraverse({
digraph,
visitor: {discoverVertex}
});
console.log(inOrder);
//[ 'a', 'b', 'c', 'd' ]
/**
Example 2. Find a cycle in a graph.
**/
digraph = arccore.graph.directed.create().result;
digraph.addVertex("a");
digraph.addVertex("b");
digraph.addVertex("c");
digraph.addVertex("d");
/**
Add some edges so the directed graph looks like:
a
|
b
/ \
c |
| |
d/
There will be a cycle caused by the edge from d -> b
**/
digraph.addEdge({e: {u: "a", v: "b"}});
digraph.addEdge({e: {u: "b", v: "c"}});
digraph.addEdge({e: {u: "c", v: "d"}});
digraph.addEdge({e: {u: "d", v: "b"}});
// To find a cycle we need to use the backEdge call back when doing the traversal.
const backEdge = ({e, g}) => {
console.log("Back edge found: " + JSON.stringify(e));
}
// run the traversal
dftResponse = arccore.graph.directed.depthFirstTraverse({
digraph,
visitor: {backEdge}
});
// output: Back edge found: {"u":"d","v":"b"}