utils/it.unibo.tuprolog.utils.graphs/MutableGraph

MutableGraph

interface MutableGraph<T, W> : Graph<T, W>

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:

val g = MutableGraph.build<String, Int> {
    this += nodeOf("a")
    connect(nodeOf("a"), nodeOf("b"), weight = 1, 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

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

add

abstract fun add(edge: Edge<T, W>)

Adds edge to this graph, in place (implicitly adding its endpoints, if missing), merging it with any other outgoing edge edge.source already has (unlike the immutable Graph.plus, which currently discards them).

abstract fun add(node: Node<T>)

Adds node to this graph, in place. Does nothing if node already belongs to this graph.

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.

clone

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

Returns an independent, mutable copy of this graph (further changes to either do not affect the other).

connect

abstract fun connect(node1: Node<T>, node2: Node<T>, weight: W? = null, bidirectional: Boolean = false)

Adds, in place, an edge from node1 to node2 with the given weight (null by default); if bidirectional is true (false by default), an edge from node2 back to node1, with the same weight, is added as well.

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 override fun minus(edge: Edge<T, W>): MutableGraph<T, W>

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

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

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

minusAssign

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

Operator alias for remove(edge).

abstract operator fun minusAssign(node: Node<T>)

Operator alias for remove(node).

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 override fun plus(edge: Edge<T, W>): MutableGraph<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 override fun plus(node: Node<T>): MutableGraph<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.

plusAssign