Roman domination number in the tree
I have been trying to implement a linear roman dominance number algorithm in trees from page 61-66 in this article . it almost works, but for the bottom graph it returns 6 instead of 8
1 1 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 1 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 1 0 0
0 0 1 0 0 0 1 1 1 0
0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 1 1
can someone help me in this case.
import java.util.Arrays;
/**
*
* @author karo
*/
public class LinearTreeDomination {
int n;
int[][] Class;
int[] Parent;
private static final int INFINITY = Integer.MAX_VALUE/100;
public LinearTreeDomination(int[][] graph,int vertex) {
Class = new int[vertex+1][5];
Parent = new int[vertex+1];
n = vertex;
for (int i = 1; i <= n; i++) {
Class[i][1] = 1;
Class[i][2] = 2;
Class[i][3] = INFINITY;
Class[i][4] = 0;
}
Parent[0] = -1;
boolean[] bool = new boolean[vertex];
Arrays.fill(bool, false);
bool[0] = true;
dfs(graph,bool,0);
for (int i = n; i > 0; i--) {
Parent[i] = Parent[i-1] + 1;
}
}
private void dfs(int[][] graph,boolean[] visited,int index) {
for(int i = 0 ; i < n ; i++){
if(graph[i][index] == 1 && index != i){
if(visited[i] == false){
Parent[i] = index;
visited[i] = true;
dfs(graph,visited,i);
}
}
}
}
public int doIt(){
for (int j = 0; j <= n-2; j++) {
int k = Parent[n-j];
combine(k,n-j);
}
return min(Class[1][1],Class[1][2],Class[1][3]);
}
private void combine(int a, int b) {
int[] ClassPrim = new int[5];
ClassPrim[1] = min(Class[a][1]+Class[b][1],Class[a][1]+Class[b][2]
,Class[a][1]+Class[b][3]);
ClassPrim[2] = min(Class[a][2] + Class[b][1],Class[a][2] + Class[b][2]
,Class[a][2] + Class[b][3],Class[a][2] + Class[b][4]
,Class[a][1] + Class[b][4] + 1,Class[a][3] + Class[b][4] + 2
,Class[a][4] + Class[b][4] + 2);
ClassPrim[3] = min(Class[a][3] + Class[b][1],Class[a][3] + Class[b][2]
,Class[a][3] + Class[b][3],Class[a][4] + Class[b][2]);
ClassPrim[4] = min(Class[a][4] + Class[b][1],Class[a][4] + Class[b][3]);
for (int i = 1; i <= 4; i++) {
Class[a][i] = ClassPrim[i];
}
}
private int min(int... values){
int k = INFINITY;
for (int val : values) {
k = Math.min(k, val);
}
return k;
}
}
Correction
Like Richard Snape, the problem was with the dfs method, dfs was for marking the vertex, and I didn't initialize the vertex marks. After that, we have to set the parent array. the code is a little messy and unreadable I was just trying to find an answer.
import java.util.Arrays;
/**
*
* @author karo
*/
public class LinearTreeDomination {
int n;
int[][] Class;
int[] Parent;
int[] Label;
int Y;
private static final int INFINITY = Integer.MAX_VALUE / 100;
public LinearTreeDomination(int[][] graph, int vertex, int from) {
Y = 0;
Class = new int[vertex + 1][5];
Parent = new int[vertex + 1];
Label = new int[vertex + 1];
n = vertex;
for (int i = 1; i <= n; i++) {
Class[i][1] = 1;
Class[i][2] = 2;
Class[i][3] = INFINITY;
Class[i][4] = 0;
}
Label[0] = 0;
boolean[] bool = new boolean[vertex];
Arrays.fill(bool, false);
bool[from] = true;
dfs(graph, bool, from);
for (int i = n; i > 0; i--) {
Label[i] = Label[i - 1] + 1;
}
Parent[1] = 0;
for (int i = 2; i <= n; i++) {
int counter = 0;
for (int k = Label[i] - 1; k > 0; k--) {
if (graph[i - 1][getIt(k) - 1] == 1) {
counter++;
Parent[Label[i]] = k;
break;
}
}
}
}
private void dfs(int[][] graph, boolean[] visited, int index) {
for (int i = 0; i < n; i++) {
if (graph[i][index] == 1 && index != i) {
if (visited[i] == false) {
Y++;
Label[i] = Y;
visited[i] = true;
dfs(graph, visited, i);
}
}
}
}
public int doIt() {
for (int j = 0; j <= n - 2; j++) {
int k = Parent[n - j];
combine(k, n - j);
}
return min(Class[1][1], Class[1][2], Class[1][3]);
}
private void combine(int a, int b) {
int[] ClassPrim = new int[5];
ClassPrim[1] = min(Class[a][1] + Class[b][1], Class[a][1] + Class[b][2], Class[a][1] + Class[b][3]);
ClassPrim[2] = min(Class[a][2] + Class[b][1], Class[a][2] + Class[b][2], Class[a][2] + Class[b][3], Class[a][2] + Class[b][4], Class[a][1] + Class[b][4] + 1, Class[a][3] + Class[b][4] + 2, Class[a][4] + Class[b][4] + 2);
ClassPrim[3] = min(Class[a][3] + Class[b][1], Class[a][3] + Class[b][2], Class[a][3] + Class[b][3], Class[a][4] + Class[b][2]);
ClassPrim[4] = min(Class[a][4] + Class[b][1], Class[a][4] + Class[b][3]);
for (int i = 1; i <= 4; i++) {
Class[a][i] = ClassPrim[i];
}
}
private int min(int... values) {
int k = INFINITY;
for (int val : values) {
k = Math.min(k, val);
}
return k;
}
private int getIt(int k) {
for (int i = 1; i <= n; i++) {
if (Label[i] == k) {
return i;
}
}
return -1;
}
}
source to share
TL; DR
I suppose the labeling dfs()
for your graph is not working as expected and this is causing your problem. I think your vector Parent
should be [-1, 0, 1, 2, 3, 4, 3, 6, 7, 6, 9]
- your program computes [-1, 0, 1, 2, 3, 4, 3, 6, 7, 6, 9]
- which is the same tree structure, but with nodes marked as non-DFS.
You can work it out either
- makes your method
dfs()
pretty clever so that it can detect erroneously numbered nodes connected together in an adjacency matrix, or -
The adjacency matrix change looks like this: same tree shape and same format, but with correctly numbered nodes linked
1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1
Detail
It is very difficult, based on your question, to see how your matrix input relates to the algorithm in the document you are linking. In particular, in this article, the tree structure is completely defined by a vector Parent
, but you introduced a new parameter called Graph
.
I'm going to assume that your input is an adjacency matrix . If this is not correct - what follows will be nonsense - please report in the comments. I also assume that I don't need to check for loops or whatever - so don't consider how that might affect what you do (if you need to do these checks programmatically - there are examples on the web ). Note that - since you have the diagonal of all 1s in an adjacency matrix - this really denotes a graph with a loop at each node.
Your adjacency matrix gives a graph that looks like this:
This should be noted as follows:
Which would give Parent
values [-1,0,1,2,3,4,3,6,7,6,9]
using your indexing. However (if you output Parent
to your constructor) you get this before the loop to make the index of indices 1 based on:
[-1, 0, 1, 2, 3, 6, 7, 2, 7, 8, 0]
and this is after:
[-1, 0, 1, 2, 3, 4, 7, 8, 3, 8, 9]
This is the correct tree “shape”, but the nodes are not labeled in the correct order for DFS (in particular, the middle “leg” is numbered from bottom to top).
If you mock the correct value of the parent simply by inserting
Parent = new int[]{-1, 0, 1, 2, 3, 4, 3, 6, 7, 6, 9};
at the end of the constructor, you will get the answer you expect (roman dominance number == 8). This may hint that we are on the right track. Note that this is mostly just debugging ...
A comment
I see that you have kept the 1-based indexing for paper matching. I think this is a bad idea - it makes Java very difficult to read. I suggest you replace the 0-based indexing, and if I get some time, I'll post a solution with your code, but with 0-based indexing and dfs()
.
source to share