utils/it.unibo.tuprolog.utils.graphs/Graph

Graph

interface Graph<T, W> : Iterable<Edge<T, W>>

An immutable, directed, optionally-weighted graph over nodes carrying a payload of type T, with edges carrying an optional weight of type W. Iterating a Graph (it implements Iterable) yields its edges.

Being immutable, every structural change (see plus/minus) returns a new Graph rather than mutating the receiver; use toMutable (or build directly via MutableGraph.build) when many changes need to be applied in a row, then MutableGraph.toImmutable the result back. Construct a Graph via Graph.build, Graph.of, or the various node/edge-adding operators on a MutableGraph:

val g = Graph.build<String, Int> {
    this += edgeOf(nodeOf("a"), nodeOf("b"), 1)
    connect(nodeOf("a"), nodeOf("c"), weight = 2, bidirectional = true)
}

Type Parameters

is the type of the payload carried by this graph's nodes

is the type of this graph's edge weights

Inheritors

MutableGraph

Types

Companion

object Companion

Properties

edges

abstract val edges: Set<Edge<T, W>>

The set of all edges belonging to this graph.

edgesCount

abstract val edgesCount: Int

The number of edges in this graph.

isAcyclic

val <T, W> Graph<T, W>.isAcyclic: Boolean

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.

isTree

val <T, W> Graph<T, W>.isTree: Boolean

Whether this graph is a tree/forest, i.e. every node has at most one incoming edge. Note that this alone does not rule out cycles (see isAcyclic for that); e.g. a single node with a self-loop satisfies this check.

nodes

abstract val nodes: Set<Node<T>>

The set of all nodes belonging to this graph.

size

abstract val size: Int

The number of nodes in this graph.

Functions

asIterable

abstract fun <S> asIterable(searchStrategy: SearchStrategy<T, W, S>, initialNode: Node<T>): Iterable<Visit<T, S>>

Traverses this graph starting from initialNode, according to searchStrategy, as an Iterable of Visits (one per traversed node); each traversal of the returned Iterable restarts from scratch.

asSequence

abstract fun <S> asSequence(searchStrategy: SearchStrategy<T, W, S>, initialNode: Node<T>): Sequence<Visit<T, S>>

Same as asIterable, but as a lazy Sequence of Visits.

assertItemsAreNotNull

fun <T> Iterable<T?>.assertItemsAreNotNull(): Iterable<T>

Same as Sequence.assertItemsAreNotNull, starting from an Iterable rather than a Sequence.

contains

abstract operator fun contains(edge: Edge<T, W>): Boolean

Whether edge (matched by source, destination, and weight) belongs to this graph.

abstract operator fun contains(node: Node<T>): Boolean

Whether node belongs to this graph.

containsEdgeAmong

abstract fun containsEdgeAmong(node1: Node<T>, node2: Node<T>): Boolean

Whether this graph has an edge going from node1 to node2, regardless of its weight.

copy

fun <T, W> Graph<T, W>.copy(f: MutableGraph<T, W>.() -> Unit): Graph<T, W>

Returns a new, immutable Graph, obtained by applying the in-place changes performed by f to a mutable copy of this graph. Handy to apply several changes to an (otherwise immutable) Graph at once, without paying the cost of a defensive copy for each individual change.

cursor

fun <T> Iterable<T>.cursor(): Cursor<out T>

Returns a lazy Cursor traversing the elements of this Iterable, in iteration order.

filter

fun <T, W> Graph<T, W>.filter(p: (Edge<T, W>) -> Boolean): Graph<T, W>

Returns a new Graph, keeping only the edges of this graph that satisfy p.

get

abstract operator fun get(edge: Pair<Node<T>, Node<T>>): W?

Returns the weight of the edge going from edge.first to edge.second, or null if there is none.

indegree

abstract fun indegree(to: Node<T>): Int

The number of edges of this graph pointing to to, i.e. ingoingEdges(to).count().

ingoingEdges

abstract fun ingoingEdges(to: Node<T>): Iterable<Edge<T, W>>

Returns all the edges of this graph pointing to to.

isLeaf

fun <T, W> Graph<T, W>.isLeaf(node: Node<T>): Boolean

Whether node has no outgoing edges in this graph, i.e. outdegree(node) == 0.

iterator

abstract operator fun iterator(): Iterator<Edge<T, W>>

map

fun <T1, W1, T2, W2> Graph<T1, W1>.map(f: (Edge<T1, W1>) -> Edge<T2, W2>): Graph<T2, W2>

Returns a new Graph, obtained by transforming every edge of this graph via f (which may change the type of the payload/weight, or entirely rewire an edge's endpoints).

minus

abstract operator fun minus(edge: Edge<T, W>): Graph<T, W>

Returns a new Graph, with edge removed from it (its endpoints are kept).

abstract operator fun minus(node: Node<T>): Graph<T, W>

Returns a new Graph, with node (and every edge incident to it) removed from it.

outdegree

abstract fun outdegree(from: Node<T>): Int

The number of edges of this graph originating from from, i.e. outgoingEdges(from).count().

outgoingEdges

abstract fun outgoingEdges(from: Node<T>): Iterable<Edge<T, W>>

Returns all the edges of this graph originating from from.

permutations

fun <T> Iterable<T>.permutations(): Sequence<List<T>>

Same as List.permutations, starting from an Iterable rather than a List.

plus

abstract operator fun plus(edge: Edge<T, W>): Graph<T, W>

Returns a new Graph, with edge added to it (implicitly adding its endpoints, if missing). Note: as currently implemented, any other outgoing edge that edge.source already had in this graph is discarded in the result, rather than kept alongside edge (unlike MutableGraph.add, which merges the new edge in without discarding existing ones).

abstract operator fun plus(node: Node<T>): Graph<T, W>

Returns a new Graph, with node added to it. Note: as currently implemented, if node already belongs to this graph, its existing outgoing edges are discarded in the result rather than preserved.

subsequences

fun <T> Iterable<T>.subsequences(): Sequence<Sequence<T>>

Same as Sequence.subsequences, but starting from an Iterable.

toMutable

abstract fun toMutable(): MutableGraph<T, W>

Returns a MutableGraph copy of this graph, which can be modified in place.