Hyperlinkv0.8.0-beta.28

← Graph

Graph.externalsconsteffect/Graph.ts:4850
(config?: ExternalsConfig): <N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>
) => NodeWalker<N>
<N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>,
  config?: ExternalsConfig
): NodeWalker<N>

Creates an iterator over external nodes (nodes without edges in the specified direction).

Details

External nodes have no outgoing edges (direction: "outgoing") or no incoming edges (direction: "incoming"). These are useful for finding sources, sinks, or isolated nodes.

Example (Iterating external nodes)

import { Graph } from "effect"

const graph = Graph.directed<string, number>((mutable) => {
  const source = Graph.addNode(mutable, "source") // 0 - no incoming
  const middle = Graph.addNode(mutable, "middle") // 1 - has both
  const sink = Graph.addNode(mutable, "sink") // 2 - no outgoing
  const isolated = Graph.addNode(mutable, "isolated") // 3 - no edges

  Graph.addEdge(mutable, source, middle, 1)
  Graph.addEdge(mutable, middle, sink, 2)
})

// Nodes with no outgoing edges (sinks + isolated)
const sinks = Array.from(
  Graph.indices(Graph.externals(graph, { direction: "outgoing" }))
)
console.log(sinks) // [2, 3]

// Nodes with no incoming edges (sources + isolated)
const sources = Array.from(
  Graph.indices(Graph.externals(graph, { direction: "incoming" }))
)
console.log(sources) // [0, 3]
iterators
Source effect/Graph.ts:485043 lines
export const externals: {
  (
    config?: ExternalsConfig
  ): <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => NodeWalker<N>
  <N, E, T extends Kind = "directed">(
    graph: Graph<N, E, T> | MutableGraph<N, E, T>,
    config?: ExternalsConfig
  ): NodeWalker<N>
} = dual((args) => isGraph(args[0]), <N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>,
  config: ExternalsConfig = {}
): NodeWalker<N> => {
  const direction = config.direction ?? "outgoing"

  return new Walker((f) => ({
    [Symbol.iterator]: () => {
      const nodeMap = graph.nodes
      const adjacencyMap = direction === "incoming"
        ? graph.reverseAdjacency
        : graph.adjacency

      const nodeIterator = nodeMap.entries()

      const nextMapped = () => {
        let current = nodeIterator.next()
        while (!current.done) {
          const [nodeIndex, nodeData] = current.value
          const adjacencyList = adjacencyMap.get(nodeIndex)

          // Node is external if it has no edges in the specified direction
          if (adjacencyList === undefined || adjacencyList.length === 0) {
            return { done: false, value: f(nodeIndex, nodeData) }
          }
          current = nodeIterator.next()
        }

        return { done: true, value: undefined } as const
      }

      return { next: nextMapped }
    }
  }))
})