How to count number of edges between red and white nodes in a graph?

I would like to count how many edges there are that goes between a white and a red node. The red nodes are the ones in the new int[] in the main method.

Provided code for the assignment:

import edu.princeton.cs.algs4.Graph;
public class RedWhite {
public static int count(Graph G, int[] rednodes) {
int rw_count = 0;
// Count how many of the edges in G connect a white node (one that
// isn't in rednodes) with a red node (one that is in rednodes).
return rw_count;
}    
}

and

import edu.princeton.cs.algs4.Graph;
public class TestRW {
public static void main(String[] args) {
Graph G = new Graph(13);
G.addEdge(0, 1);
G.addEdge(3, 2);
G.addEdge(3, 5);
G.addEdge(4, 3);
G.addEdge(4, 2);
G.addEdge(6, 9);
G.addEdge(8, 7);
G.addEdge(8, 9);
G.addEdge(9, 11);
G.addEdge(10, 12);
G.addEdge(11, 12);
G.addEdge(12, 9);
System.out.println(RedWhite.count(G, new int[] { 3 }));                                        // should print 3
System.out.println(RedWhite.count(G, new int[] { 3, 4, 2 }));                                  // should print 1
System.out.println(RedWhite.count(G, new int[] { 3, 4, 2, 11, 12 }));                          // should print 4
System.out.println(RedWhite.count(G, new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 })); // should print 0
System.out.println(RedWhite.count(G, new int[] {  }));                                         // should print 0
}
}

I am having trouble traversing the graph and I don't know how to use rednodes[] to compare to the graph. When running my attempted code below I get errors in the marked and count methods.

Any help is appreciated.

import edu.princeton.cs.algs4.Graph;
public class RedWhite {
private static boolean[] marked;
public RedWhite(Graph G, int s) {
marked = new boolean[G.V()];
dfs(G, s);
}
public static int count(Graph G, int[] rednodes) {
int rw_count = 0;
for (int w : G.adj(rednodes.length))
{
if (marked(w)) {
rw_count++;
}
}
// Count how many of the edges in G connect a white node (one that
// isn't in rednodes) with a red node (one that is in rednodes).
return rw_count;
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
dfs(G, w);
}
}
}
public static boolean marked(int v) {
return marked[v];
}
public static void main(String[] args) {
Graph G = new Graph(13);
G.addEdge(0, 1);
G.addEdge(3, 2);
G.addEdge(3, 5);
G.addEdge(4, 3);
G.addEdge(4, 2);
G.addEdge(6, 9);
G.addEdge(8, 7);
G.addEdge(8, 9);
G.addEdge(9, 11);
G.addEdge(10, 12);
G.addEdge(11, 12);
G.addEdge(12, 9);
System.out.println(RedWhite.count(G, new int[] { 3 }));                                        // should print 3
System.out.println(RedWhite.count(G, new int[] { 3, 4, 2 }));                                  // should print 1
System.out.println(RedWhite.count(G, new int[] { 3, 4, 2, 11, 12 }));                          // should print 4
System.out.println(RedWhite.count(G, new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 })); // should print 0
System.out.println(RedWhite.count(G, new int[] {  }));                                         // should print 0
}
}

• Code issues:

You will get an error because marked is not initialized because count is a static method and it don't need to create a new instance of RedWhite.

What you can do is remove static from count method definition. Also don't declare marked as static.

And in your main method, do : RedWhite rw = new RedWhite(G, s) and rw.count(G, new int[]{}).

• Solution:

Now coming to the solution, I m not sure why you are going for DFS. You have the graph defined, all you need is to look at the adjacency list of each red node and count.

To be more efficient, sort the red nodes and do a binary search for each adjacent node in the sorted rednodes, if it is not found it is a white node. Then increment the count. Do this for all rednodes you will get the final count.

Code is :

    private int countEdges(Graph G, int[] rednodes) {
int count = 0;
Arrays.sort(rednodes);
for ( int rednode : rednodes ) {
for ( int adj : G.adj(rednode) ) {
if ( Arrays.binarySearch(rednodes, adj) < 0 ) {
count++;
}
}
}
return count;
}

To be fair I code in C++, not java, but here's a question: Why does your marked() function return the value of a marked array? Wouldn't it make more sense to use that array directly?

For the time being I can tell you are using a DFS to traverse the graph correctly. I am not sure, however, why you are traversing the graph at all.

I am sorry, but this is going to be one of these "don't do this, do that instead" answers.

If you are looking for a linear solution (for one execution of the count method), you better just create an array which, for each node holds info about whether it is white or red. I'd recommend filling it with zeroes, and then going over the rednodes array to change appropriate values to 1.

Next, you declare a result variable equal to zero, which will count the number of edges which connect to nodes of different colours. You iterate over all the edges, and check if the vertices they connect are of varying colours. If so, increment the result variable.