Maximize the number of nodes that could be reachable in a graph

Description of my code:

I am trying to maximize the number of nodes that could be reachable in a graph. Please do not consider my main algorithm, I want it to be like that. The only parts that I need to be boosted are the way of using data structures and reachability. I don't want to change my main algorithm.

I am looking for boosting the performance of my program. Here is the source code of that. Is there any part that could perform faster? Any little speed up would be great because of this algorithm should be run on a graph with more than 1m nodes.

```
public LinkedHashSet retentionSeedFinder(int budget,
HashSet churnerNodes, int delay,
DirectedSparseGraph network) {

LinkedHashSet seedSet = new LinkedHashSet();
numberofNodes = network.getVertexCount();
churnNet = new HashSet();
HashSet tmpchurnNet = new HashSet();
HashSet availableNodes;
// at timestep 0

churnNet.addAll(churnerNodes);
churnNet.addAll(getNeighbors(churnerNodes, network));

availableNodes = getReachableNodes(churnNet, network);

// at timestep 1
int timestep = 1;
tmpchurnNet = churnNet;
while (timestep neighbors;

System.out.println("***At timestep:" + timestep
+ "*");
for (Customer churner : churnNet) {
neighbors = network.getNeighbors(churner);
for (Customer specificNeighbor : neighbors) {
tmpchurnNet.add(specificNeighbor);
}
}
churnNet = tmpchurnNet;
timestep++;
}

PriorityQueue marginalGainHeap = new PriorityQueue(
1, new Comparator() {
public int compare(Customer c1, Customer c2) {
if (c1.getMarginalGain() c2.getMarginalGain())
return -1;
if (c1.getMarginalGain() == c2.getMarginalGain()) {
if (c1.getRevenue() c2.getRevenue())

Lots to think about, this is not a comprehensive evaluation

Use Java7

your code style indicates you are using Java6 (you are not using the diamond operator <>...).

Java 7 and it's recent updates are faster than Java6.

Extract the comparator:

private static final Comparator PRIORITY_COMPARATOR = new Comparator<>() {
            public int compare(Customer c1, Customer c2) {
                if (c1.getMarginalGain()  c2.getMarginalGain())
                    return -1;
                if (c1.getMarginalGain() == c2.getMarginalGain()) {
                    if (c1.getRevenue()  c2.getRevenue())
                        return -1;
                }
                return 0;
            }
        }

Then use it as:

PriorityQueue marginalGainHeap = new PriorityQueue<>(1, PRIORITY_COMPARATOR);

LinkedHashSet

Your method returns LinkedHashSet. This strikes me as odd.... To me this means:

• the order is important

• you don't know what your data does in terms of duplicates.

Using a Set means you expect duplicate data, and you only discover it is a duplicate after you have done the work, and you add it to the set.

You should adjust this to be a more natural structure, like a List and then ensure that you are not processing the same customer twice....

Dubious Queue Usage

for (Customer remainingNode : tmpAvailNodes) {
        remainingNode.setMarginalGain(calculateMarginalGain(
                remainingNode, seedSet, network, availableNodes,
                churnNet));

        // heapify bar asase mg
        marginalGainHeap.remove(remainingNode);
        marginalGainHeap.add(remainingNode);
    }

marginalGainHeap is a Priority queue. It is not a free data structure.

Changing the priority of a value is dubious (I had to check that the remove() will actually succeed... It will, but it performs slowly ( O(n) performance ). Because of the way you remove() and add() ( O( log n) ) the same values multiple times, you are running at essentially O(n2log(n)) performance in that section.

System.out.println

You are doing this a lot.

It is slow.

Don't

calculateMarginalGain

This method looks horrendous for performance.

• 2 new HashSets

• 4 O(n) operations - addAll, addAll, retainAll, removeAll

Call to getNeighbours adds:

• 2 new HashSet

• 1 addAll

• O(n * m) loop system

Conclusion....

You have to change your code to NOT do things you have to Undo Later

• Don't add things to a priority queue if you have to change the priority

• Don't add things to a HashSet if you have to remove them later.

• .....

StackExchange Code Review Q#44159, answer score: 4