1import * as Equal from "../Equal.ts"
2import type * as Graph from "../Graph.ts"
3import * as Hash from "../Hash.ts"
4import { NodeInspectSymbol } from "../Inspectable.ts"
5import * as Option from "../Option.ts"
6import { pipeArguments } from "../Pipeable.ts"
7import { hasProperty } from "../Predicate.ts"
8
9/** @internal */
10export const TypeId = "~effect/Graph"
11
12/** @internal */
13export const isGraph = <N = unknown, E = unknown, T extends Graph.Kind = Graph.Kind, U = never>(
14 u: U | Graph.Graph<N, E, T> | Graph.MutableGraph<N, E, T>
15): u is Graph.Graph<N, E, T> | Graph.MutableGraph<N, E, T> => hasProperty(u, TypeId)
16
17/** @internal */
18export interface GraphImpl<in out N, in out E, T extends Graph.Kind>
19 extends Iterable<readonly [Graph.NodeIndex, N]>, Equal.Equal
20{
21 readonly [TypeId]: unknown
22 type: T
23 mutable: boolean
24 transforming: boolean
25 nodes: Map<Graph.NodeIndex, N>
26 edges: Map<Graph.EdgeIndex, Graph.Edge<E>>
27 adjacency: Map<Graph.NodeIndex, Array<Graph.EdgeIndex>>
28 reverseAdjacency: Map<Graph.NodeIndex, Array<Graph.EdgeIndex>>
29 nextNodeIndex: Graph.NodeIndex
30 nextEdgeIndex: Graph.EdgeIndex
31 acyclic: Option.Option<boolean>
32 toJSON(): unknown
33}
34
35/** @internal */
36export const toImpl = <N, E, T extends Graph.Kind>(
37 graph: Graph.Graph<N, E, T> | Graph.MutableGraph<N, E, T>
38): GraphImpl<N, E, T> => graph as unknown as GraphImpl<N, E, T>
39
40/** @internal */
41export const isTransforming = <N, E, T extends Graph.Kind>(
42 graph: Graph.Graph<N, E, T> | Graph.MutableGraph<N, E, T>
43): boolean => toImpl(graph).transforming
44
45/** @internal */
46export const withTransformation = <N, E, T extends Graph.Kind, A>(
47 graph: Graph.MutableGraph<N, E, T>,
48 evaluate: () => A
49): A => {
50 const impl = toImpl(graph)
51 const transforming = impl.transforming
52 impl.transforming = true
53 try {
54 return evaluate()
55 } finally {
56 impl.transforming = transforming
57 }
58}
59
60const edgeEquals = (type: Graph.Kind, self: Graph.Edge<any>, that: Graph.Edge<any>): boolean =>
61 (type === "directed"
62 ? self.source === that.source && self.target === that.target
63 : (self.source === that.source && self.target === that.target) ||
64 (self.source === that.target && self.target === that.source)) &&
65 Equal.equals(self.data, that.data)
66
67const edgeHash = (type: Graph.Kind, edge: Graph.Edge<any>): number =>
68 type === "directed"
69 ? Hash.hash(edge)
70 : Hash.optimize(Hash.combine(Hash.hash(edge.data), endpointsHash(edge.source, edge.target)))
71
72/**
73 * Addition is commutative and does not cancel self-loops.
74 *
75 * @internal
76 */
77export const endpointsHash = (source: unknown, target: unknown): number =>
78 Hash.combine(0, Hash.hash(source)) + Hash.combine(0, Hash.hash(target))
79
80const graphSeed = Hash.string("Graph")
81
82const ProtoGraph = {
83 [TypeId]: {
84 _N: (_: never) => _,
85 _E: (_: never) => _
86 },
87 [Symbol.iterator](this: GraphImpl<any, any, any>) {
88 return this.nodes[Symbol.iterator]()
89 },
90 [NodeInspectSymbol](this: GraphImpl<any, any, any>) {
91 return this.toJSON()
92 },
93 [Equal.symbol](this: GraphImpl<any, any, any>, that: Equal.Equal): boolean {
94 if (hasProperty(that, TypeId)) {
95 const thatImpl = toImpl(that as Graph.Graph<any, any, any>)
96 if (
97 this.nodes.size !== thatImpl.nodes.size ||
98 this.edges.size !== thatImpl.edges.size ||
99 this.type !== thatImpl.type
100 ) {
101 return false
102 }
103 for (const [nodeIndex, nodeData] of this.nodes) {
104 if (!thatImpl.nodes.has(nodeIndex) || !Equal.equals(nodeData, thatImpl.nodes.get(nodeIndex))) {
105 return false
106 }
107 }
108 for (const [edgeIndex, edgeData] of this.edges) {
109 const otherEdge = thatImpl.edges.get(edgeIndex)
110 if (otherEdge === undefined || !edgeEquals(this.type, edgeData, otherEdge)) {
111 return false
112 }
113 }
114 return true
115 }
116 return false
117 },
118 [Hash.symbol](this: GraphImpl<any, any, any>): number {
119 let hash = graphSeed
120 hash = hash ^ Hash.string(this.type)
121 hash = hash ^ Hash.number(this.nodes.size)
122 hash = hash ^ Hash.number(this.edges.size)
123 for (const [nodeIndex, nodeData] of this.nodes) {
124 hash ^= Hash.combine(Hash.hash(nodeIndex), Hash.hash(nodeData))
125 }
126 for (const [edgeIndex, edgeData] of this.edges) {
127 hash ^= Hash.combine(Hash.hash(edgeIndex), edgeHash(this.type, edgeData))
128 }
129 return Hash.optimize(hash)
130 },
131 toJSON(this: GraphImpl<any, any, any>) {
132 return {
133 _id: "Graph",
134 nodeCount: this.nodes.size,
135 edgeCount: this.edges.size,
136 type: this.type
137 }
138 },
139 toString(this: GraphImpl<any, any, any>) {
140 return `Graph(${this.type}, ${this.nodes.size}, ${this.edges.size})`
141 },
142 pipe() {
143 return pipeArguments(this, arguments)
144 }
145}
146
147/** @internal */
148export const make = <N, E, T extends Graph.Kind>(type: T, mutable: boolean): GraphImpl<N, E, T> => {
149 const graph: GraphImpl<N, E, T> = Object.create(ProtoGraph)
150 graph.type = type
151 graph.mutable = mutable
152 graph.transforming = false
153 graph.nodes = new Map()
154 graph.edges = new Map()
155 graph.adjacency = new Map()
156 graph.reverseAdjacency = new Map()
157 graph.nextNodeIndex = 0
158 graph.nextEdgeIndex = 0
159 graph.acyclic = Option.some(true)
160 return graph
161}
162
163const cloneAdjacency = (
164 adjacency: Map<Graph.NodeIndex, Array<Graph.EdgeIndex>>
165): Map<Graph.NodeIndex, Array<Graph.EdgeIndex>> => {
166 const cloned = new Map<Graph.NodeIndex, Array<Graph.EdgeIndex>>()
167 for (const [nodeIndex, edges] of adjacency) {
168 cloned.set(nodeIndex, [...edges])
169 }
170 return cloned
171}
172
173/** @internal */
174export const clone = <N, E, T extends Graph.Kind>(
175 source: GraphImpl<N, E, T>,
176 mutable: boolean
177): GraphImpl<N, E, T> => {
178 const graph = make<N, E, T>(source.type, mutable)
179 graph.nodes = new Map(source.nodes)
180 graph.edges = new Map(source.edges)
181 graph.adjacency = cloneAdjacency(source.adjacency)
182 graph.reverseAdjacency = cloneAdjacency(source.reverseAdjacency)
183 graph.nextNodeIndex = source.nextNodeIndex
184 graph.nextEdgeIndex = source.nextEdgeIndex
185 graph.acyclic = source.acyclic
186 return graph
187}
188
189/** @internal */
190export const finalize = <N, E, T extends Graph.Kind>(source: GraphImpl<N, E, T>): GraphImpl<N, E, T> => {
191 const graph: GraphImpl<N, E, T> = Object.create(ProtoGraph)
192 graph.type = source.type
193 graph.mutable = false
194 graph.transforming = false
195 graph.nodes = source.nodes
196 graph.edges = source.edges
197 graph.adjacency = source.adjacency
198 graph.reverseAdjacency = source.reverseAdjacency
199 graph.nextNodeIndex = source.nextNodeIndex
200 graph.nextEdgeIndex = source.nextEdgeIndex
201 graph.acyclic = source.acyclic
202 return graph
203}
204
205/** @internal */
206export const snapshot = <N, E, T extends Graph.Kind>(graph: Graph.Graph<N, E, T>): Graph.Snapshot<N, E, T> => {
207 const impl = toImpl(graph)
208 return {
209 type: graph.type,
210 nodes: Array.from(impl.nodes, ([index, data]) => ({ index, data })).sort((a, b) => a.index - b.index),
211 edges: Array.from(impl.edges, ([index, edge]) => ({
212 index,
213 source: edge.source,
214 target: edge.target,
215 data: edge.data
216 })).sort((a, b) => a.index - b.index)
217 }
218}
219
220/** @internal */
221export const hydrate = <N, E, T extends Graph.Kind>(
222 snapshot: Graph.Snapshot<N, E, T>
223): Graph.Graph<N, E, T> => {
224 const graph = make<N, E, T>(snapshot.type, false)
225 for (const node of snapshot.nodes) {
226 graph.nodes.set(node.index, node.data)
227 graph.adjacency.set(node.index, [])
228 graph.reverseAdjacency.set(node.index, [])
229 }
230 for (const edge of snapshot.edges) {
231 graph.edges.set(edge.index, {
232 source: edge.source,
233 target: edge.target,
234 data: edge.data
235 })
236 graph.adjacency.get(edge.source)!.push(edge.index)
237 graph.reverseAdjacency.get(edge.target)!.push(edge.index)
238 if (snapshot.type === "undirected") {
239 graph.adjacency.get(edge.target)!.push(edge.index)
240 graph.reverseAdjacency.get(edge.source)!.push(edge.index)
241 }
242 }
243 graph.nextNodeIndex = snapshot.nodes.length === 0 ? 0 : snapshot.nodes[snapshot.nodes.length - 1].index + 1
244 graph.nextEdgeIndex = snapshot.edges.length === 0 ? 0 : snapshot.edges[snapshot.edges.length - 1].index + 1
245 graph.acyclic = Option.none()
246 return graph as unknown as Graph.Graph<N, E, T>
247}