Simplifying finding neighbors in graph

Question

private static List<ConstrDirectedEdge> kruskalConstruct(ConstructionDigraph CG) {

    int current = CG.srcVertexIndex();
    boolean visited[] = new boolean[CG.V()];
    visited[current] = true;
    UF uf = new UF(CG.V());
    List<ConstrDirectedEdge> feasibleNeighbours = new ArrayList<ConstrDirectedEdge>();
    List<ConstrDirectedEdge> solution = new ArrayList<ConstrDirectedEdge>();

    do {
        /* clear neighbours from prev iteration */
        feasibleNeighbours.clear();

        /* build feasible neighbour list */
        for (ConstrDirectedEdge directedEdge : CG.adj(current)) {
            int v = CG.getVertex(directedEdge.to()).getSource();
            int w = CG.getVertex(directedEdge.to()).getDestination();

            if (!visited[directedEdge.to()] && !uf.connected(v, w)) {
                feasibleNeighbours.add(directedEdge);
            }
        }

        //TODO: code smell
        if (feasibleNeighbours.isEmpty()) {
            break;
        }

        /* calculate the probability for each neighbour */
        double R = calculateR(feasibleNeighbours);
        System.out.println("R for source is : " + R);
        for (ConstrDirectedEdge feasibleneighbour : feasibleNeighbours) {
            feasibleneighbour.calcProbability(R, alpha, beta);
        }

        /* pick a neighbour */
        ConstrDirectedEdge pickedUp = choiceEdgeAtRandom(feasibleNeighbours);
        visited[pickedUp.to()] = true;
        current = pickedUp.to();
        solution.add(pickedUp);
        uf.union(CG.getVertex(current).getSource(),   CG.getVertex(current).getDestination());
    } while (!feasibleNeighbours.isEmpty());

    return solution;
}

I want to eliminate the code smell that is the break in the middle of the loop. As can be seen I have chosen to use a do {} while() in order to do the initialization with the initial node being CG.srcVertexIndex(). What I was thinking about is make the following code:

        for (ConstrDirectedEdge directedEdge : CG.adj(current)) {
            int v = CG.getVertex(directedEdge.to()).getSource();
            int w = CG.getVertex(directedEdge.to()).getDestination();

            if (!visited[directedEdge.to()] && !uf.connected(v, w)) {
                feasibleNeighbours.add(directedEdge);
            }
        }

into a separate function that will be returning a List<ConstrDirectedEdge> and then the loop can turn into:

while(!(feasibleNeighbours = getFeasibleNeighbours(CG, visited,  uf)).isEmpty()) {
/* calculate the probability for each neighbour */
/* pick a neighbour */
}

But then I will have to pass visited and uf as parameter which in fact are going to be manipulated by getFeasibleNeighbours functions - in essence I will be using input parameters to store output state which is not a good idea.

Finally I could just make visited and uf static private vars and just reinitialize them when needed and use them directly, but again this seems kind of wrong.

The code is working fine, however I'd like to hear opinions on how this can be made more readable.

Answer 1

Your proposed getFeasibleNeighbours doesn't modify the two parameters. The visited array isn't modified at all. The cf is modified by the union-find process, but that's really more of a caching then a modification. So there isn't any concerns about the parameters of getFeasibleNeighbors.

} while (!feasibleNeighbours.isEmpty());

There doesn't seem to be any point in checking this here. It can't possibly have changed since you checked it in the middle of the loop.

while(!(feasibleNeighbours = getFeasibleNeighbours(CG, visited,  uf)).isEmpty()) {

You can do something like this, but I find it rather ugly.

In the general case of break-in-the-middle loops you have something like:

get_stuff_ready();
while(1)
{
     do_stuff_before();
     if( !some_test() )
           break;
     do_stuff_after();
}

This equivalent to:

get_stuff_ready();
do_stuff_before();
while( some_test() )
{
     do_stuff_after();
     do_stuff_before(); 
}

This does repeat do_stuff_before() twice. However, you can often combine get_stuff_ready() and do_stuff_before().

So you could something like:

private static List<ConstrDirectedEdge> kruskalConstruct(ConstructionDigraph CG) {

    int current = CG.srcVertexIndex();
    boolean visited[] = new boolean[CG.V()];
    visited[current] = true;
    UF uf = new UF(CG.V());
    List<ConstrDirectedEdge> solution = new ArrayList<ConstrDirectedEdge>();
    List<ConstrDirectedEdge> feasibleNeighbours = getFeasibleNeighbors(CG, current, uf);

    while( !feasibleNeighbours.isEmpty() )
    {

        ConstrDirectedEdge pickedUp = pickNeighbour(feasibleNeighbours);
        current = pickedUp.to();

        visited[current] = true;
        uf.union(CG.getVertex(current).getSource(),   CG.getVertex(current).getDestination());
        solution.add(pickedUp);

        feasibleNeighbours = getFeasibleNeighbors(CG, current, uf);
    }

    return solution;
}

Answer 2

If visited and uf are so tightly coupled with the feasibleNeighbor-calculation, maybe you should have something like a FeasibleNeighborCalculator class which is holding all of this stuff, and which you can ask for the next neighbor list?