Index: src/main/java/weka/clusterers/SimpleClusterer.java
===================================================================
--- src/main/java/weka/clusterers/SimpleClusterer.java	(revision 6)
+++ src/main/java/weka/clusterers/SimpleClusterer.java	(revision 6)
@@ -0,0 +1,68 @@
+package weka.clusterers;
+
+
+import java.util.Iterator;
+
+import weka.clusterers.forMetisMQI.Graph;
+import weka.clusterers.forMetisMQI.GraphAlgorithms;
+import weka.core.Capabilities;
+import weka.core.Instance;
+import weka.core.Instances;
+import weka.core.Capabilities.Capability;
+
+public class SimpleClusterer extends AbstractClusterer {
+
+	private int numberOfClusters = 0;
+
+	/**
+	 * 
+	 */
+	private static final long serialVersionUID = 1L;
+
+	@Override
+	public void buildClusterer(Instances data) throws Exception {
+		getCapabilities().testWithFail(data);
+		
+		Graph g = new Graph(data);
+		GraphAlgorithms ga = new GraphAlgorithms();
+		ga.coarse(g);
+		numberOfClusters = 1;
+	}
+
+	@Override
+	public int clusterInstance(Instance instance) throws Exception {
+		return 0;
+	}
+
+	@Override
+	public double[] distributionForInstance(Instance instance) 
+	throws Exception {
+		double[] d = new double[numberOfClusters()];
+		d[clusterInstance(instance)] = 1.0;
+		return d;
+	}
+
+	@Override
+	public Capabilities getCapabilities() {
+		Capabilities result = super.getCapabilities();
+		result.enable(Capability.NUMERIC_ATTRIBUTES);
+		result.enable(Capability.NO_CLASS);
+		return result;
+	}
+
+	@Override
+	public int numberOfClusters() throws Exception {
+		return numberOfClusters;
+	}
+
+	/**
+	 * Main method for executing this clusterer.
+	 * 
+	 * @param args
+	 *            the options, use "-h" to display options
+	 */
+	public static void main(String[] args) {
+		AbstractClusterer.runClusterer(new SimpleClusterer(), args);
+	}
+
+}
Index: src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java
===================================================================
--- src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java	(revision 6)
+++ src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java	(revision 6)
@@ -0,0 +1,29 @@
+package weka.clusterers.forMetisMQI;
+
+import java.util.List;
+
+public class CoarserGraphElement {
+	
+	private Graph g;
+	private List<Integer> match;
+	private List<Integer> map;
+	
+	public CoarserGraphElement(Graph g, List<Integer> match, List<Integer> map) {
+		this.g = g;
+		this.match = match;
+		this.map = map;
+	}
+	
+	public List<Integer> getMatch() {
+		return match;
+	}
+	
+	public List<Integer> getMap() {
+		return map;
+	}
+	
+	public Graph getGraph() {
+		return g;
+	}
+
+}
Index: src/main/java/weka/clusterers/forMetisMQI/Graph.java
===================================================================
--- src/main/java/weka/clusterers/forMetisMQI/Graph.java	(revision 6)
+++ src/main/java/weka/clusterers/forMetisMQI/Graph.java	(revision 6)
@@ -0,0 +1,309 @@
+package weka.clusterers.forMetisMQI;
+
+import java.io.PrintStream;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+
+import weka.core.Attribute;
+import weka.core.Instance;
+import weka.core.Instances;
+
+public class Graph {
+	
+	protected static class NodeInfo {
+		/** The weight of the node */
+		protected int vwgt;
+		/** The size of the adjacency list of the node */
+		protected int nedges;
+		/**
+		 * The index into the adjacency list that is the beginning of the
+		 * adjacency list of v
+		 */
+		protected int iedges;
+		/** The weight of the edges that have been contracted to create the node */
+		protected int cewgt;
+		/** The sum of the weight of the edges adjacent to v */
+		protected int adjwgt;
+
+		public NodeInfo() {
+			this.vwgt = 1;
+			this.cewgt = 0;
+			this.iedges = 0;
+			this.nedges = 0;
+			this.adjwgt = 0;
+
+		}
+
+		@Override
+		public String toString() {
+			return "Vwgt: " + vwgt + " Cewgt: " + cewgt + " Iedges: " + iedges
+					+ " Nedges: " + nedges + " Adjwgt: " + adjwgt;
+		}
+	}
+
+	/**
+	 * Additional node info for all vertices..
+	 */
+	private List<NodeInfo> vtxs;
+	/**
+	 * Adjacency vector.
+	 */
+	private List<Integer> adjncy;
+	/**
+	 * Weights vector
+	 */
+	private List<Integer> weights;
+	
+	private HashMap<Integer,Integer> label;
+	private HashMap<Integer,Integer> index;
+
+	/**
+	 * Build a new graph given a set of instances.
+	 * 
+	 * @param data
+	 */
+	public Graph(Instances data) {
+		vtxs = new ArrayList<NodeInfo>();
+		adjncy = new ArrayList<Integer>();
+		weights = new ArrayList<Integer>();
+		label = new HashMap<Integer,Integer>();
+		index = new HashMap<Integer,Integer>();
+		Iterator<Instance> dataIterator = data.iterator();
+		Attribute from = data.attribute("from");
+		Attribute to = data.attribute("to");
+		if (from == null || to == null)
+			throw new RuntimeException(
+					"Unsupported data: check the list of attributes (from and to are needed).");
+		while (dataIterator.hasNext()) {
+			Instance edge = dataIterator.next();
+			int node1 = (int) Math.round(edge.value(from));
+			int node2 = (int) Math.round(edge.value(to));
+			addNode(node1); addNode(node2);
+			addEdgeUndirected(node1, node2, 1);
+		}
+	}
+
+	public Graph() {
+		vtxs = new ArrayList<NodeInfo>();
+		adjncy = new ArrayList<Integer>();
+		weights = new ArrayList<Integer>();
+		label = new HashMap<Integer,Integer>();
+		index = new HashMap<Integer,Integer>();
+	}
+	
+	/**
+	 * Returns an iterator over the nodes of the graph.
+	 * @return
+	 */
+	public Iterator<Integer> iterator() {
+		return label.keySet().iterator();
+	}
+	
+	/**
+	 * Returns the label associated with a given index.
+	 * @param index
+	 * @return
+	 */
+	private int getLabel(int index) {
+		return this.index.get(index);
+	}
+	
+	/**
+	 * Returns the index associated with a given label.
+	 * @param index
+	 * @return
+	 */
+	private int getIndex(int label) {
+		return this.label.get(label);
+	}
+	
+	private void updateAssociation(int index, int label) {
+		this.index.put(index,label);
+		this.label.put(label,index);
+	}
+	
+	/**
+	 * Returns the weight of the edge (u,v).
+	 * @param u
+	 * @param v
+	 * @return
+	 */
+	public int getWeight(int u, int v) {
+		int i = getIndex(u);
+		int istart = vtxs.get(i).iedges;
+		int iend = vtxs.get(i).iedges + vtxs.get(i).nedges;
+		int weight = -1; boolean found = false;
+		for(int k = istart; k < iend && !found; k++) {
+			if(adjncy.get(k) == v) {
+				weight = weights.get(k);
+				found = true;
+		    }
+		}
+		return weight;
+	}
+	
+	public void setWeight(int u, int v, int weight) {
+		int i = getIndex(u);
+		int j = getIndex(v);
+		int istart = vtxs.get(i).iedges;
+		int iend = istart + vtxs.get(i).nedges;
+		for(int k = istart; k < iend; k++){
+			if(adjncy.get(k) == v) {
+				weights.set(k, weight);
+			}
+		}
+		int jstart = vtxs.get(j).iedges;
+		int jend = jstart + vtxs.get(j).nedges;
+		for(int k = jstart; k < jend; k++){
+			if(adjncy.get(k) == u)
+				weights.set(k, weight);
+		}
+	}
+	
+	public NodeInfo getNode(int u) {
+		int i = getIndex(u);
+		return vtxs.get(i);
+	}
+	
+	public int nedge() {
+		return adjncy.size();
+	}
+	
+	public boolean isNode(int u) {
+		return label.containsKey(u);
+	}
+	
+	public void addNode(int u) {
+		if(!isNode(u)) {
+			int index = size();
+			updateAssociation(index, u);
+			NodeInfo node = new NodeInfo();
+			node.iedges = nedge();
+			node.nedges = 0;
+			node.vwgt = 1;
+			node.adjwgt = 0;
+			node.cewgt = 0;
+			vtxs.add(index, node);
+		}
+	}
+	
+	public int size() {
+		return vtxs.size();
+	}
+	
+	public List<Integer> getNeighbors(int u) {
+		int i = getIndex(u);
+		List<Integer> neighbors = new ArrayList<Integer>();
+		int istart = vtxs.get(i).iedges;
+		int iend = vtxs.get(i).iedges + vtxs.get(i).nedges;
+		for(int k = istart; k < iend; k++) {
+			neighbors.add(adjncy.get(k));
+		}
+		return neighbors;
+	}
+	
+	/**
+	 * Return true if u is neighbor of v.
+	 * @param u
+	 * @param v
+	 * @return
+	 */
+	public boolean isNeighbor(int u, int v){
+		return getNeighbors(u).contains(v);
+	}
+	
+	public void addEdgeUndirected(int i, int j, int w) {
+		addEdgeDirectedl(i, j, w);
+		addEdgeDirectedl(j, i, w);
+	}
+	
+	/**
+	 * Add an edge from i to j of weight w if previously it doesn't exists, otherwise
+	 * simply update the weight of the edge.
+	 * @param i
+	 * @param j
+	 * @param w
+	 */
+	public void addEdgeDirectedl(int u, int v, int w) {
+		int i = getIndex(u);
+		if(!isNeighbor(u,v)) {
+			int istart = getNode(u).iedges;
+			adjncy.add(istart,v);
+			for(int k = i + 1; k < size(); k++) {
+				vtxs.get(k).iedges++;
+			}
+			vtxs.get(i).nedges++;
+			vtxs.get(i).adjwgt += w;
+			weights.add(istart, w);
+		} else
+			setWeight(u, v, w);
+	}
+	
+	public boolean isEdge(int u, int v) {
+		int i = getIndex(u);
+		int istart = vtxs.get(i).iedges;
+		int iend = vtxs.get(i).iedges + vtxs.get(i).nedges;
+		boolean found = false;
+		for(int k = istart; k < iend && !found; k++) {
+			found = (adjncy.get(k) == v);
+		}
+		return found;
+	}
+
+	/**
+	 * Print the graph structure.
+	 */
+	public void printGraph(PrintStream io) {
+		for(int i = 0; i < vtxs.size(); i++) {
+			int u = getLabel(i);
+			io.print("Node: " + u + " Neighbors: ");
+			Iterator<Integer> neighbors = getNeighbors(u).iterator();
+			while(neighbors.hasNext()) {
+				int v = neighbors.next();
+				io.print(v + " [w: " + getWeight(u, v) + "] ");
+			}
+			io.println(getNode(u).toString());
+		}
+	}
+	
+	/**
+	 * Return a list containing a random permutation of the vertices.
+	 * 
+	 * @return a random permutation of vertices
+	 */
+	public List<Integer> vtxsPermutation() {
+		Random r = Random.instance(); 
+		List<Integer> perm = new ArrayList<Integer>();
+		for (int i = 0; i < vtxs.size(); i++) {
+			perm.add(getLabel(i));
+		}
+		for (int i = 0; i < perm.size(); i++) {
+			int k = r.nextInt(perm.size());
+			int swap = perm.get(k);
+			perm.set(k, perm.get(i));
+			perm.set(i, swap);
+		}
+		return perm;
+	}
+	
+	/**
+	 * Randomize the adjacency list.
+	 */
+	public void adjncyPermutation() {
+		Random r = Random.instance();
+		for (int i = 0; i < vtxs.size(); i++) {
+			NodeInfo n = vtxs.get(i);
+			for (int j = n.iedges; j < n.nedges + n.iedges; j++) {
+				int k = r.nextInt(n.nedges) + n.iedges;
+				int swap = adjncy.get(k);
+				adjncy.set(k, adjncy.get(j));
+				adjncy.set(j, swap);
+				swap = weights.get(k);
+				weights.set(k, weights.get(j));
+				weights.set(j, swap);
+			}
+		}
+	}
+}
Index: src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java
===================================================================
--- src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java	(revision 6)
+++ src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java	(revision 6)
@@ -0,0 +1,149 @@
+package weka.clusterers.forMetisMQI;
+
+import java.io.PrintStream;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Set;
+
+public class GraphAlgorithms {
+	
+	boolean debug = true;
+	PrintStream debugStream = System.err;
+	
+	/**
+	 * Return true if the vertex v is matched
+	 * 
+	 * @param v
+	 *            the index of the vertex
+	 * @return true if the vertex v is matched, false o.w.
+	 */
+	private boolean isMatched(List<Integer> match, int v) {
+		return match.get(v) != v;
+	}
+
+	private void RMMatch(Graph g, List<Integer> match, List<Integer> map) {
+		int labelCounter = 0;
+		for (int i = 0; i < g.size(); i++) {
+			match.add(i);
+			map.add(i);
+		}
+		g.adjncyPermutation();
+		Iterator<Integer> nodeIterator = g.vtxsPermutation().iterator();
+		while (nodeIterator.hasNext()) {
+			int u = nodeIterator.next();
+			if (debug)
+				debugStream.println("Visiting node " + u + " Matched = " + isMatched(match,u));
+			if (!isMatched(match,u)) {
+				boolean foundMatch = false;
+				int matchedNode = -1;
+				Iterator<Integer> iterator = g.getNeighbors(u).iterator();
+				while(iterator.hasNext() && !foundMatch){
+					int v = iterator.next();
+					if (!isMatched(match,v)) {
+						matchedNode = v;
+						foundMatch = true;
+						if (debug)
+							debugStream.println("Found a match with node "
+									+ matchedNode);
+					}
+				}
+				if (debug && !foundMatch)
+					debugStream.println("There aren't unmatched neighbors.");
+				if(foundMatch) {
+					match.set(u, matchedNode);
+					match.set(matchedNode, u);
+					map.set(u, labelCounter);
+					map.set(matchedNode, labelCounter);
+					if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + map.get(u));
+				} else
+					map.set(u, labelCounter);
+				labelCounter++;
+			}
+		}
+	}
+	
+	/**
+	 * Return a new contracted graph.
+	 */
+	private Graph contract(Graph g, List<Integer> match, List<Integer> map) {
+		Graph output = new Graph();
+		Iterator<Integer> iterator = g.iterator();
+		while(iterator.hasNext()) {
+			int u = iterator.next();
+			output.addNode(map.get(u));
+			Iterator<Integer> it = g.getNeighbors(u).iterator();
+			Set<Integer> neighbors = new HashSet<Integer>();
+			while(it.hasNext()) {
+				int v = it.next();
+				neighbors.add(map.get(v));
+			}
+			it = g.getNeighbors(match.get(u)).iterator();
+			while(it.hasNext()) {
+				int v = it.next();
+				neighbors.add(map.get(v));
+			}
+			neighbors.remove(map.get(u));
+			it = neighbors.iterator();
+			while(it.hasNext()) {
+				int v = it.next();
+				output.addNode(v);
+				output.addEdgeUndirected(map.get(u), v, 0);
+			}
+		}	
+		//calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v.
+		//w(map(u),map(v)) += w(u,v). 
+		for(int u=0; u < g.size(); u++) {
+			Iterator<Integer> it = g.getNeighbors(u).iterator();
+			while(it.hasNext()) {
+				int v = it.next();
+				if(map.get(u) != map.get(v) && output.isEdge(map.get(u), map.get(v)) && u < v) {
+					output.setWeight(map.get(u), map.get(v), output.getWeight(map.get(u), map.get(v)) + g.getWeight(u, v));
+				}
+			}
+		}
+		for(int u = 0; u < g.size(); u++) {
+			if(isMatched(match,u)) {
+				int v = match.get(u);
+				if(u < v) {
+					output.getNode(map.get(u)).vwgt = g.getNode(u).vwgt + g.getNode(v).vwgt;
+					output.getNode(map.get(u)).cewgt = g.getNode(u).cewgt + g.getNode(v).cewgt +
+					g.getWeight(u, v);
+					output.getNode(map.get(u)).adjwgt = g.getNode(u).adjwgt + g.getNode(v).adjwgt - 2 *
+					g.getWeight(u, v);
+				}
+			} else {
+				output.getNode(map.get(u)).vwgt = g.getNode(u).vwgt;
+				output.getNode(map.get(u)).cewgt = g.getNode(u).cewgt;
+				output.getNode(map.get(u)).adjwgt = g.getNode(u).adjwgt;
+			}
+		}
+		return output;
+	}
+
+	/**
+	 * Performs the first stage of the METIS algorithm, using RM.
+	 */
+	private CoarserGraphElement coarseOneStep(Graph g) {
+		List<Integer> match = new ArrayList<Integer>();
+		List<Integer> map = new ArrayList<Integer>();
+		RMMatch(g,match,map);
+		g = contract(g,match,map);
+		return new CoarserGraphElement(g, match, map);
+	}
+	
+	public void coarse(Graph g) {
+		int n = 1;
+		Graph prev = g;
+		CoarserGraphElement e;
+		g.printGraph(System.out);
+	    do {
+	    	e = coarseOneStep(g);
+	    	prev = g;
+	    	g = e.getGraph();
+	    	g.printGraph(System.out);
+	    } while(prev.size() > g.size() && g.size() > n);
+	}
+
+}
Index: src/main/java/weka/clusterers/forMetisMQI/Random.java
===================================================================
--- src/main/java/weka/clusterers/forMetisMQI/Random.java	(revision 6)
+++ src/main/java/weka/clusterers/forMetisMQI/Random.java	(revision 6)
@@ -0,0 +1,23 @@
+package weka.clusterers.forMetisMQI;
+
+public class Random extends java.util.Random {
+
+	private static final long serialVersionUID = 1L;
+	
+	private static Random instance = null;
+	
+	/**
+	 * Return an instance of a random generator with a default seed.
+	 * @return
+	 */
+	public static Random instance() {
+		if(instance == null)
+			instance = new Random();
+		return instance;
+	}
+	
+	private Random() {
+		super(1234567890);
+	}
+
+}