Package it.unimi.dsi.sux4j.mph.solve
Class Modulo2SparseSystem
- java.lang.Object
-
- it.unimi.dsi.sux4j.mph.solve.Modulo2SparseSystem
-
public class Modulo2SparseSystem extends java.lang.Object
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
Modulo2SparseSystem.Modulo2Equation
-
Constructor Summary
Constructors Modifier Constructor Description Modulo2SparseSystem(int numVars)
protected
Modulo2SparseSystem(int numVars, java.util.ArrayList<Modulo2SparseSystem.Modulo2Equation> system)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
add(Modulo2SparseSystem.Modulo2Equation equation)
boolean
check(long[] solution)
Modulo2SparseSystem
copy()
static boolean
gaussianElimination(int[][] var2Eq, long[] c, int[] variable, long[] solution)
boolean
gaussianElimination(long[] solution)
static boolean
lazyGaussianElimination(int[][] var2Eq, long[] c, int[] variable, long[] solution)
Solves a system using lazy Gaussian elimination.boolean
lazyGaussianElimination(long[] solution)
Solves the system using lazy Gaussian elimination.static boolean
lazyGaussianElimination(Modulo2SparseSystem system, int[][] var2Eq, long[] c, int[] variable, long[] solution)
Solves a system using lazy Gaussian elimination.void
print()
int
size()
boolean
solve(int[] solution)
-
-
-
Constructor Detail
-
Modulo2SparseSystem
public Modulo2SparseSystem(int numVars)
-
Modulo2SparseSystem
protected Modulo2SparseSystem(int numVars, java.util.ArrayList<Modulo2SparseSystem.Modulo2Equation> system)
-
-
Method Detail
-
print
public void print()
-
add
public void add(Modulo2SparseSystem.Modulo2Equation equation)
-
solve
public boolean solve(int[] solution)
-
size
public int size()
-
copy
public Modulo2SparseSystem copy()
-
check
public boolean check(long[] solution)
-
gaussianElimination
public boolean gaussianElimination(long[] solution)
-
lazyGaussianElimination
public boolean lazyGaussianElimination(long[] solution)
Solves the system using lazy Gaussian elimination.Warning: this method is very inefficient, as it scans linearly the equations, builds from scratch the
var2Eq
parameter oflazyGaussianElimination(Modulo2SparseSystem, int[][], long[], int[], long[])
, and finally calls it. It should be used mainly to write unit tests.- Parameters:
solution
- an array where the solution will be written.- Returns:
- true if the system is solvable.
-
lazyGaussianElimination
public static boolean lazyGaussianElimination(int[][] var2Eq, long[] c, int[] variable, long[] solution)
Solves a system using lazy Gaussian elimination.- Parameters:
var2Eq
- an array of arrays describing, for each variable, in which equation it appears; equation indices must appear in nondecreasing order; an equation may appear several times for a given variable, in which case the final coefficient of the variable in the equation is given by the number of appearances modulo 3 (this weird format is useful when calling this method from aLinear3SystemSolver
). Note that this array will be altered if some equation appears multiple time associated with a variable.c
- the array of known terms, one for each equation.variable
- the variables with respect to which the system should be solved (variables not appearing in this array will be simply assigned zero).solution
- an array where the solution will be written.- Returns:
- true if the system is solvable.
-
lazyGaussianElimination
public static boolean lazyGaussianElimination(Modulo2SparseSystem system, int[][] var2Eq, long[] c, int[] variable, long[] solution)
Solves a system using lazy Gaussian elimination.- Parameters:
system
- a modulo-3 system.var2Eq
- an array of arrays describing, for each variable, in which equation it appears; equation indices must appear in nondecreasing order; an equation may appear several times for a given variable, in which case the final coefficient of the variable in the equation is given by the number of appearances modulo 3 (this weird format is useful when calling this method from aLinear3SystemSolver
). The resulting system must be identical tosystem
. Note that this array will be altered if some equation appears multiple time associated with a variable.c
- the array of known terms, one for each equation.variable
- the variables with respect to which the system should be solved (variables not appearing in this array will be simply assigned zero).solution
- an array where the solution will be written.- Returns:
- true if the system is solvable.
-
gaussianElimination
public static boolean gaussianElimination(int[][] var2Eq, long[] c, int[] variable, long[] solution)
-
-