Child pages
  • Practical Java Algorithm Development

Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

Section Table of Contents

Table of Contents

Introduction

In this tutorial we will create an algorithm to test the "Attack Tolerance" of a network (deleting high degree nodes), as an example of a simple algorithm which has data input and output, and utilitizes user-input parameters. Testing Attack Tolerance is done by removing a certain number of the nodes with the highest degree (nodes with the most edges). If the network is relatively unfractured after the application of this algorithm, it can be said to have a high attack tolerance. This algorithm already exists in Network Workbench under the name "Delete High Degree Nodes"https://nwb.slis.indiana.edu/community/?n=AnalyzeData.HighDegreeNodeDeletionTo. To help us in this analysis, we will be using the JUNG graph library.

...

Your AttackToleranceAlgorithm file should initially look like this:package org.my.attacktolerance;

Code Block

import java.util.Dictionary;

import org.cishell.framework.CIShellContext;
import org.cishell.framework.algorithm.Algorithm;
import org.cishell.framework.algorithm.AlgorithmExecutionException;
import org.cishell.framework.data.Data;

public class AttackToleranceAlgorithm implements Algorithm {
private Data\[\] data;
private Dictionary parameters;
private CIShellContext context;

public AttackToleranceAlgorithm(Data\[\] data, Dictionary parameters, CIShellContext context) {
        this.data = data;
        this.parameters = parameters;
        this.context = context;
    }

public Data\[\] execute() throws AlgorithmExecutionException {
    	return null;
    }
}

...

Because we specified the Jung graph as the in_data type, CIShell will arrange for us to be given a Jung graph object when this algorithm is run (if a network in the Data Manager is of some other type, CIShell's conversion service will convert that network to a Jung graph). The input objects are held in the data array that is passed as a constructor to the algorithm. We use the following code to access the Jung graph in this array.

Code Block

public Data\[\] execute() throws AlgorithmExecutionException {
        Graph graph = (Graph)(data[0].getData());
    	return null;
    }

...

The following line is used to extract the number of nodes we should delete, "numNodesToDelete" from the Dictionary. int numNodesToDelete = ((Integer) parameters.get("numNodesToDelete")).intValue();
Now we have obtain everything we need to do the attack tolerance analysis. Since the specifics of this algorithm are not important to learning about CIShell, I have provided the core code in the class below:

AttackTolerance:

Code Block

AttackTolerance:package org.my.attacktolerance;

import java.util.Iterator;

import edu.uci.ics.jung.algorithms.importance.DegreeDistributionRanker;
import edu.uci.ics.jung.algorithms.importance.NodeRanking;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.Vertex;

public class AttackTolerance {

/*\*
* Perform an attack tolerance test on the graph.
\*
* @return a Graph with 'numNodesToDelete' of its highest degree nodes deleted.
* Edges associated with deleted nodes will be removed as well.
\*/
public static Graph testAttackTolerance(final Graph graph, int numNodesToDelete) {

Graph graphToAttack = (Graph) graph.copy();

DegreeDistributionRanker rankByDegree = new  DegreeDistributionRanker(graphToAttack);
rankByDegree.evaluate();

Iterator nodesByDegree = rankByDegree.getRankings().iterator();
for (int numNodesDeleted = 0;
numNodesDeleted < numNodesToDelete && nodesByDegree.hasNext();
numNodesDeleted++) {

			Vertex v = ((NodeRanking) nodesByDegree.next()).vertex;

			graphToAttack.removeVertex(v);
		}

return graphToAttack;
}
}

...

Below is the updated code for AttackToleranceAlgorithm, which now utilizes the AttackTolerance class, and returns the modified graph as Data:package org.my.attacktolerance;

Code Block

import java.util.Dictionary;

import org.cishell.framework.CIShellContext;
import org.cishell.framework.algorithm.Algorithm;
import org.cishell.framework.data.BasicData;
import org.cishell.framework.data.Data;
import org.cishell.framework.data.DataProperty;

import edu.uci.ics.jung.graph.Graph;

public class AttackToleranceAlgorithm implements Algorithm {

private Data\[\] data;
private int numNodesToDelete;

public AttackToleranceAlgorithm(Data\[\] data, Dictionary parameters, CIShellContext context) {
		this.data = data;
		this.numNodesToDelete = ((Integer) parameters.get("numNodesToDelete")).intValue();
	}

public Data\[\] execute() {
Graph inputGraph = (Graph) (data[0].getData());

Graph outputGraph = AttackTolerance.testAttackTolerance(inputGraph, numNodesToDelete);

Data outputData = prepareOutputData(outputGraph);

return new Data\[\] { outputData };
}

private Data prepareOutputData(Graph outputGraph) {
		Data outputData = new BasicData(outputGraph, Graph.class.getName());

		Dictionary metadata = outputData.getMetadata();
		metadata.put(DataProperty.PARENT, data[0]);
		metadata.put(DataProperty.TYPE, DataProperty.NETWORK_TYPE);
		metadata.put(DataProperty.LABEL, "High Degree Node Deletion (Attack Tolerance)");

		return outputData;
	}
}

...

Source code for AttackToleranceAlgorithmFactory as a ParameterMutator:package org.my.attacktolerance;

Code Block

import java.util.Dictionary;

import org.cishell.framework.CIShellContext;
import org.cishell.framework.algorithm.Algorithm;
import org.cishell.framework.algorithm.AlgorithmFactory;
import org.cishell.framework.algorithm.ParameterMutator;
import org.cishell.framework.data.Data;
import org.cishell.reference.service.metatype.BasicAttributeDefinition;
import org.cishell.reference.service.metatype.BasicObjectClassDefinition;
import org.osgi.service.metatype.AttributeDefinition;
import org.osgi.service.metatype.ObjectClassDefinition;

import edu.uci.ics.jung.graph.Graph;

public class AttackToleranceAlgorithmFactory implements AlgorithmFactory, ParameterMutator {
public Algorithm createAlgorithm(Data\[\] data, Dictionary parameters, CIShellContext context) {
        return new AttackToleranceAlgorithm(data, parameters, context);
    }

public static final int DELETE_ONE_IN_N_NODES_BY_DEFAULT = 10;

/\*
* set the default value for 'Number of Highest Degree Nodes to Delete'
* to 1/Nth of the total number of nodes in the graph.
\*/
public ObjectClassDefinition mutateParameters(Data\[\] data, ObjectClassDefinition parameters) {

//calculate how many nodes to delete by default

Graph inputGraph = (Graph) data[0].getData();
int defaultNumNodesToDelete = calculateDefaultNumNodesToDelete(inputGraph);

BasicObjectClassDefinition newParameters = new BasicObjectClassDefinition(
parameters.getID(),
parameters.getName(),
parameters.getDescription(), null);


//for each attribute definition in the original attribute parameters
AttributeDefinition\[\] paramAttributes =
parameters.getAttributeDefinitions(ObjectClassDefinition.ALL);
for (int ii = 0; ii < paramAttributes.length; ii++) {
AttributeDefinition paramAttribute = paramAttributes[ii];
//if it is the numNodesToDelete attribute...
if (paramAttribute.getID().equals("numNodesToDelete")) {
				/*
				 * add that attribute to our new set of attributes,
				 *  but with the new default value we calculated
				 */
				AttributeDefinition modifiedAttribute = new BasicAttributeDefinition(
						paramAttribute.getID(), paramAttribute.getName(),
						paramAttribute.getDescription(), paramAttribute.getType(),
						String.valueOf(defaultNumNodesToDelete));
				newParameters.addAttributeDefinition(
						ObjectClassDefinition.REQUIRED, modifiedAttribute);

			} else {
				//add any other attribute to our new set of attributes as-is.
				newParameters.addAttributeDefinition(
						ObjectClassDefinition.REQUIRED, paramAttributes[ii]);
			}
}

//return our new attribute parameters
return newParameters;
}

private int calculateDefaultNumNodesToDelete(Graph graph) {
		int numNodesInGraph = graph.numVertices();
		int recommendedToDelete = Math.max(numNodesInGraph / DELETE_ONE_IN_N_NODES_BY_DEFAULT, 1);
		return recommendedToDelete;
	}
}

...