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.

  • Why would getFeasibleNeighbours modify visited and uf? – Winston Ewert May 1 '13 at 13:17
  • Because in picking the feasible neighbor it will have to accordingly update the state variables - visited and UF, and at the same time those variable need to persist across executions of the loop – LordDoskias May 1 '13 at 17:25
  • But getFeasibleNeighbors doesn't pick the neighbour. It just returns a list of them. – Winston Ewert May 1 '13 at 17:30
  • Yes, but in order to get the list it needs to follow certain rules such as not creating loop in a graph (the union-find portion) and also it shouldn't consider already visited nodes. – LordDoskias May 1 '13 at 18:18
  • Yes it checks the visited status, but it doesn't change the visited status does it? – Winston Ewert May 1 '13 at 18:22

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;
}
  • +1 for everything after "So you could something like", and encapsulating via getFeasableNeighbors(). The big clue to putting while up front is that the mid-loop break and while condition look for the same thing. – radarbob May 2 '13 at 14:38

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?

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.