# Class PartwiseMinimumBase

java.lang.Object
it.unimi.dsi.law.fibrations.PartwiseMinimumBase

```public final class PartwiseMinimumBase
extends Object```
Static methods to compute the minimum fibration base of a given graph using a partwise algorithm. More precisely, the method `compute(ImmutableGraph, NodeColouringStrategy, ArcColouringStrategy)` starts from a graph (possibly with a colouring on its nodes and/or on its arcs) and returns an array, say `a[]`, with exactly as many elements as there are nodes in the graph, and with the following properties:
• `a[x]==a[y]` iff `x` and `y` are in the same fibre of the minimal (coloured, if the graph is such) fibrations;
• the values contained in `a[]` range from 0 to `k−1` where `k` is the number of nodes in the minimum base;
• the values in `a[]` are assigned canonically, that is, if `b[]` is the array returned by the method on an isomorphic graph (with the same colours, if the graph is coloured) and if `f` represents the isomorphism, then `a[x]=b[f(x)]` for every node `x`.

## Algorithm implementation

The algorithm is a partwise variant of that implemented by `MinimumBase`. The algorithm keeps a list of touched parts, as opposed to a list of touched nodes, resulting in less memory consumption and, in practice, in faster execution and reduced memory usage, even if it is not possible for this implementation to prove the good bounds given for `MinimumBase`. The canonical labels created by the two algorithms, however, are identical.

In the following, by partition of a set we mean a subdivision of the set into a number of nonempty disjoint subsets, called parts.

The algorithm execution happens in rounds; at the end of each round, a certain partition of the nodes is established. The starting partition is the one determined by node colours, if any, or it is simply the trivial partition with just one part. At every round, the old partition is refined (i.e., some of the parts are further subdivided into subparts). The algorithm stops as soon as no part is actually subdivided at the end of a round: the final partition is the desired one (i.e., the nodes are partitioned according to the fibres of the minimum fibration).

### Basic data structures

Current partition: The current partition is stored into two arrays: the first, called `part[]` simply contains a permutation of the nodes with the property that nodes belonging to the same part appear consecutively; the second, called `start[]` contains, for each node, the index of `part[]` where its class belongs to. More formally, suppose that `part[begin]`, `part[begin+1]`, …, `part[end-1]` is one of the parts; then, if `x=part[j]` for some `j` between `begin` and `end` (i.e., if `x` is one of the nodes in the part) we have `start[x]=begin`. In the following, unless otherwise specified, we shall identify a part with its starting index in the array `part`.

Active parts: At the beginning of each round, there is a certain set of active parts; their number is stored in `numActiveParts`, and they are stored in the `startActivePart[]` array, in arbitrary order.

Touched parts: During each round, some of the parts are deemed as touched; their number (at the end of the round) is stored in `touchedListLength`, and they are stored in the `touchedList[]` array; additionally, there is an array of boolean values, called `touched[]` such that `touched[i]` is true iff `i` is the starting index of a touched part.

### First phase: assigning labels to nodes

The final aim of the first phase is to assign to each node `x` a label that is the list of all nodes `y` that have an arc towards `x` and appear in some active parts; such labels (whose length cannot be larger than the indegree of `x`) will be contained in the array `inFrom[x][]`, its length being stored in `inFill[x]`.

To obtain this result, the algorithm scans all the nodes in all the active parts, and for each such node `y` considers all outgoing arcs, writing `y` in all the labels of the target nodes of such arcs.

In this phase, we mark all parts containing at least one target node as touched.

### Second phase: refining touched parts

We consider all touched parts, in the (arbitrary) order in which we find them in the touched list. In this phase (some of) these parts will be partitioned into subparts: this amounts in permuting the portion of the array `part[]` where the part is stored, and changing some of the entries of the array `start[]` (those that are relative to nodes in the part that is being subpartitioned).

Note that at a certain point of this phase we have some parts that have already been subpartitioned (we call them completed), a part that is being considered (we call it current) and some other touched parts that will be considered later on.

Suppose that the current part starts at index `begin` and ends at index `end` (exclusive). First of all, for each node `x` in the part, the label `inFrom[x][0..inFill[x]-1]` is sorted according to the following lexicographic order:

• if the colour of the arc (`y`,`x`) is smaller than the colour of (`y'`,`x`), then `y` must appear before `y'`;
• if the colour of the arc (`y`,`x`) is the same as the colour of (`y'`,`x`), but the part of `y` is smaller than the part of `y'`, then `y` must appear before `y'`.

After sorting, the current part is subdivided according to the equivalence relation induced by the previously described lexicographic order. Some care must be taken, though: when comparing the parts of `y` and `y'` we are considering the new partitioning for the completed parts, but we use the old partitioning for the current part (i.e., nodes in the current part are considered to have partition number `begin`).

• ## Method Summary

Modifier and Type Method Description
`static int[]` ```compute​(ImmutableGraph g, NodeColouringStrategy nodeColouring, ArcColouringStrategy arcColouring)```
Returns a labelling of an immutable graph such that two nodes have the same label iff they are in the same fibre of minimal fibrations.
`static void` `main​(String[] arg)`

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ## Method Details

• ### compute

public static int[] compute​(ImmutableGraph g, NodeColouringStrategy nodeColouring, ArcColouringStrategy arcColouring)
Returns a labelling of an immutable graph such that two nodes have the same label iff they are in the same fibre of minimal fibrations.

Note that the labelling is surjective—if a node has label k, there are nodes with label j, for every 0≤jk.

Parameters:
`g` - an immutable graph.
`nodeColouring` - a colouring for the nodes, or `null`.
`arcColouring` - a colouring for the arcs, or `null`.
Returns:
an array of integers labelling the graph so that two nodes have the same label iff they are in the same fibre of minimal fibrations.
• ### main

public static void main​(String[] arg) throws IOException
Throws:
`IOException`