Package-level declarations
Types
A base SearchStrategy taking care of the common bookkeeping of a graph traversal (the "fringe" of edges still to explore, and driving search as a lazy Sequence), so that concrete strategies (see BreadthFirst and DepthFirst) only need to implement selectNextVisit, deciding, at each step, which edge in the fringe to visit next and how to grow the fringe from there.
A SearchStrategy visiting a Graph breadth-first, i.e. level by level: all nodes at depth 0 (the source), then all nodes at depth 1, and so on. Each yielded Visit.state is the depth (an Int, starting at 0) at which the corresponding node was reached.
A SearchStrategy visiting a Graph depth-first: from the source, it follows one outgoing edge as deep as possible before backtracking to explore the next one. Each yielded Visit.state is the depth (an Int, starting at 0) at which the corresponding node was reached.
A directed, optionally-weighted edge of a Graph, going from source to destination; an unweighted edge (as used e.g. by Graph.build<T, Nothing> { ... }) simply carries a null weight. Build one via Edge.of, or the edgeOf top-level shorthand. Two Edges connecting the same source and destination with the same weight are ==-equal, since the default implementation returned by Edge.of is a data class; a bidirectional connection is modelled as two separate Edges (see MutableGraph.connect).
A mutable variant of Graph: add/remove (and their operator aliases plusAssign/minusAssign) change this instance in place, unlike the copy-on-write Graph.plus/Graph.minus. This is the type to reach for when building up a graph incrementally, or when applying many changes in a row without paying the cost of a defensive copy for each of them (as Graph.plus/Graph.minus would); see Graph.build and MutableGraph.build to construct one via a builder block:
A node of a Graph, wrapping a payload value of type T. A Node is a distinct, identity-less wrapper around value (two Nodes built from ==-equal values are themselves ==-equal, since the default implementation returned by Node.of is a data class), so that the same graph can, e.g., use plain Strings or numbers as node payloads without those values having to implement any graph-specific interface. Build one via Node.of, or the nodeOf top-level shorthand.
A pluggable graph-traversal algorithm, generic over the kind of state it threads through the traversal (e.g. the current depth, for BreadthFirst/DepthFirst). Rather than Graph baking in a fixed set of traversal orders, it delegates to a SearchStrategy via Graph.asSequence/Graph.asIterable, so new orders (e.g. a custom best-first search) can be added without touching Graph itself. See AbstractSearchStrategy for a base class handling the traversal's bookkeeping (the fringe of edges still to explore), leaving concrete strategies to only decide which edge to explore next.
One step of a graph traversal, as produced by a SearchStrategy: the node reached by the traversal, paired with the traversal's state at the time it was reached (e.g. the current depth for it.unibo.tuprolog.utils.graphs.BreadthFirst/it.unibo.tuprolog.utils.graphs.DepthFirst, both of which use an Int state). Graph.asSequence (and Graph.asIterable) yield a stream of Visits, one per traversed node. Build one via Visit.of, or the visitOf top-level shorthand.
Properties
Whether this graph contains no directed cycles, checked by repeatedly stripping away leaf nodes (nodes with no outgoing edges) from a working copy until either no nodes are left (the original graph is acyclic) or no leaf remains despite nodes still being present (there is a cycle among them). This makes a mutable copy of the whole graph and is therefore O(nodes + edges), not free to call repeatedly on a large graph.