class Vector
{
public boolean transpose;
public int[] V;
/**
* @param int[] V Vektor (Größe > 0).
*/
public Vector(int[] V)
{
this.V = V;
this.transpose = false;
}
/**
* @param int[] V Vektor (Größe > 0).
* @param boolean transpose
*/
public Vector(int[] V, boolean transpose)
{
this.V = V;
this.transpose = transpose;
}
/**
* Gibt ein Teilstück des Vektors zurück.
* @param int from >= 0
* @param int to Vektorlänge > to >= from
* @return Vector
*/
public Vector slice(int from, int to)
{
int[] a = new int[to - from + 1];
System.out.println(a.length);
System.out.println(from);
System.out.println(to);
for
(
int i = 0, j = from;
j <= to;
)
{
a[i++] = V[j++];
}
return new Vector(a, transpose);
}
/**
* @param Vector other
* Dessen V muss gleich groß dieser Instanz sein.
* Entweder müssen beide transpose oder beide nicht transpose sein.
* @return Vector
*/
public Vector add(Vector other)
{
int size = V.length;
int[] a = new int[size];
for(int i = 0; i < size; ++i)
{
a[i] = V[i] + other.V[i];
}
return new Vector(a, transpose);
}
/**
* @return String
*/
public String toString()
{
int size = V.length;
if(transpose)
{
String s = "";
for(int i = 1; i < size; ++i)
{
s += ", " + V[i];
}
return "{" + V[0] + s + "}";
}
String s = "{\n";
for(int i = 0; i < size - 1; ++i)
{
s += " " + V[i] + ",\n";
}
return s + " " + V[size - 1] + "\n}";
}
}
class Matrix
{
public int[][] M;
/**
* @param int[][] M Quadratische Matrix (Größe > 0).
*/
public Matrix(int[][] M)
{
this.M = M;
}
/**
* Gibt ein quadratisches Teilstück der Matrix zurück.
* @param int from >= 0
* @param int to Matrixgröße > to >= from
* @return Matrix
*/
public Matrix slice(int from, int to)
{
int length = to - from + 1;
int[][] a = new int[length][length];
for
(
int i = 0, j = from;
j <= to;
++i, ++j
)
{
for
(
int k = 0, l = from;
l <= to;
)
{
a[i][k++] = M[j][l++];
}
}
return new Matrix(a);
}
public Matrix add(Matrix other)
{
int size = M.length;
int[][] A = new int[size][size];
for(int i = 0; i < size; ++i) // Zeilen
{
for(int j = 0; j < size; ++j) // Spalten
{
A[i][j] = M[i][j] + other.M[i][j];
}
}
return new Matrix(A);
}
/**
* @param Matrix other Dessen M muss gleich groß dieser Instanz sein.
* @return Matrix
*/
public Matrix mul(Matrix other)
{
int size = M.length;
int[][] A = new int[size][size];
for(int i = 0; i < size; ++i) // Zeilen
{
for(int j = 0; j < size; ++j) // Spalten
{
A[i][j] = 0;
for(int k = 0; k < size; ++k)
{
A[i][j] += M[i][k] * other.M[k][j];
}
}
}
return new Matrix(A);
}
/**
* @param Vector v Dessen V muss gleich groß dieser Matrix M sein (nur 1-dim.).
* @return Vector
*/
public Vector mul(Vector v)
{
int size = M.length;
int[] a = new int[size];
if(v.transpose)
{
for(int j = 0; j < size; ++j) // Spalten
{
a[j] = 0;
for(int k = 0; k < size; ++k)
{
a[j] += v.V[k] * M[k][j];
}
}
}
else
{
for(int i = 0; i < size; ++i) // Zeilen
{
a[i] = 0;
for(int k = 0; k < size; ++k)
{
a[i] += M[i][k] * v.V[k];
}
}
}
return new Vector(a, v.transpose);
}
/**
* @return String
*/
public String toString()
{
int size = M.length;
String s = "{\n";
// alle Zeilen bis auf die letzte:
for(int i = 0; i < size - 1; ++i) // Zeilen
{
s += " {";
for(int j = 0; j < size - 1; ++j) // Spalten
{
s += M[i][j] + ", ";
}
s += M[i][size - 1] + "},\n";
}
// letzte Zeile:
s += " {";
for(int j = 0; j < size - 1; ++j) // Spalten
{
s += M[size - 1][j] + ", ";
}
s += M[size - 1][size - 1] + "}\n";
return s + "}";
}
}
class Main
{
/**
* Kontrolle, ob alle Knoten vom Startknoten (erster Knoten) direkt oder indirekt erreichbar sind.
* @param Matrix m Adjazenzmatrix (welche Knoten von welchen anderen Knoten eingehende Kanten haben)
* @return boolean
*/
private static boolean allNodesReachable(Matrix m)
{
// Alle Knoten erreichbar, wenn es nur max. 1 Knoten gibt:
int end = m.M.length - 1;
if(end < 1)
{
return true;
}
// Erste Matrix-Zeile als transponierten Vector (exkl. erstes Element):
Vector v = new Vector(m.M[0], true).slice(1, end);
// Matrix ohne erste Spalte und erste Zeile:
m = m.slice(1, end);
// n - 1 Durchläufe:
Vector mulV;
for(int i = 1; i < end; ++i) // ist das korrekt, dass hier ab 1 begonnen werden darf????????????
{
mulV = m.mul(v);
v = v.add(mulV);
System.out.println("mulV: " + mulV);
System.out.println("v : " + v);
}
// Kontrolle ob alle Vektorelement 1 sind:
for(int i = 0; i < end; ++i)
{
if(v.V[i] == 0)
{
return false;
}
}
return true;
}
public static void main(String[] args)
{
int[][] x = // 0 -> 1 -> 3 -> 2
{
{0, 1, 0, 0},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 1, 0}
};
Matrix m = new Matrix(x);
System.out.println(allNodesReachable(m) ? "ok" : "nok");
// Zum Vergleich mit Matrix-Potenzen:
Matrix m0 = new Matrix(x);
Matrix mulM;
for(int i = 0; i < 4; ++i)
{
mulM = m0.mul(m0);
m0 = m0.add(mulM);
}
System.out.println(m0);
}
}
