Package it.unimi.dsi.sux4j.mph.solve
Class Modulo2SparseSystem
java.lang.Object
it.unimi.dsi.sux4j.mph.solve.Modulo2SparseSystem
-
Nested Class Summary
Nested Classes -
Constructor Summary
ConstructorsModifierConstructorDescriptionModulo2SparseSystem
(int numVars) protected
Modulo2SparseSystem
(int numVars, ArrayList<Modulo2SparseSystem.Modulo2Equation> system) -
Method Summary
Modifier and TypeMethodDescriptionvoid
add
(Modulo2SparseSystem.Modulo2Equation equation) boolean
check
(long[] solution) 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 Details
-
Modulo2SparseSystem
public Modulo2SparseSystem(int numVars) -
Modulo2SparseSystem
-
-
Method Details
-
print
public void print() -
add
-
solve
public boolean solve(int[] solution) -
size
public int size() -
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)
-