Function

Static Public Summary
public	adj(edges: Iterable): Map Constructs the adjacency list for an undirected unweighted connected loopless multigraph G given as a list of edges.
public	maxback(edges: Iterable): Iterable Convenience wrapper around Nagamochi-Ibaraki poly-time algorithm.
public	mb(G: Map): Array Nagamochi-Ibaraki poly-time algorithm.
public	* outgoingedges(G: Map, U: Set): Iterable Yields all edges of an undirected unweighted connected loopless multigraph G that have one endpoint inside some vertex subset U and that have the other endpoint inside of V = V(G) \ U.

Static Private Summary
private	_contract(G: Map, ordering: Array): Map Given G and some ordering, computes the graph H obtained from G by contracting all edges between the last two vertices of the ordering.
private	* _order(G: Map): Iterable Lists the vertices of an undirected unweighted connected loopless multigraph G in max-back order.
private	* _smallcuts(G: Map): Iterable Yields the small cuts of undirected unweighted connected loopless multigraph G.

Static Public

public adj(edges: Iterable): Map source

import adj from '@graph-algorithm/minimum-cut/src/adj.js'

Constructs the adjacency list for an undirected unweighted connected loopless multigraph G given as a list of edges.

Params:

Name	Type	Attribute	Description
edges	Iterable		The edges of G.

Return:

Map	The adjacency list G.

public maxback(edges: Iterable): Iterable source

import maxback from '@graph-algorithm/minimum-cut/src/maxback/maxback.js'

Convenience wrapper around Nagamochi-Ibaraki poly-time algorithm.

Params:

Name	Type	Attribute	Description
edges	Iterable		List of edges of an undirected unweighted connected loopless multigraph G.

Return:

Iterable

An iterable over the edges of a minimum cut of G.

public mb(G: Map): Array source

import mb from '@graph-algorithm/minimum-cut/src/maxback/mb.js'

Nagamochi-Ibaraki poly-time algorithm.

Params:

Name	Type	Attribute	Description
G	Map		The adjacency list of an undirected unweighted connected loopless multigraph G.

Return:

Array

A pair [U,cutsize] reprensenting a minimum cut of G.

public * outgoingedges(G: Map, U: Set): Iterable source

import outgoingedges from '@graph-algorithm/minimum-cut/src/outgoingedges.js'

Yields all edges of an undirected unweighted connected loopless multigraph G that have one endpoint inside some vertex subset U and that have the other endpoint inside of V = V(G) \ U.

Params:

Name	Type	Attribute	Description
G	Map		The input undirected unweighted connected loopless multigraph.
U	Set		The subset of edges.

Return:

Iterable

The edges of G going from U to V(G) \ U.

Static Private

private _contract(G: Map, ordering: Array): Map source

import _contract from '@graph-algorithm/minimum-cut/src/maxback/_contract.js'

Given G and some ordering, computes the graph H obtained from G by contracting all edges between the last two vertices of the ordering.

Params:

Name	Type	Attribute	Description
G	Map
ordering	Array

Return:

Map

private * _order(G: Map): Iterable source

import _order from '@graph-algorithm/minimum-cut/src/maxback/_order.js'

Lists the vertices of an undirected unweighted connected loopless multigraph G in max-back order.

Params:

Name	Type	Attribute	Description
G	Map		The adjacency list of G.

Return:

Iterable

The vertices of G in max-back order.

private * _smallcuts(G: Map): Iterable source

import _smallcuts from '@graph-algorithm/minimum-cut/src/maxback/_smallcuts.js'

Yields the small cuts of undirected unweighted connected loopless multigraph G. At least one of them must be a minimum cut.

Params:

Name	Type	Attribute	Description
G	Map		The adjacency list of G.

Return:

Iterable

The small cuts of G.