fastundirgraph.java

peersim仿真chord协议的测试过的环境

/*
 * Copyright (c) 2003-2005 The BISON Project
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License version 2 as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */

/*
 * Created on Jan 30, 2005 by Spyros Voulgaris
 *
 */
package peersim.graph;

import java.util.ArrayList;
import java.util.BitSet;

/**
* Speeds up {@link ConstUndirGraph#isEdge} by storing the links in an
* adjacency matrix (in fact in a triangle).
* Its memory consumption is huge but it's much faster if the isEdge method
* of the original underlying graph is slow.
*/
public class FastUndirGraph extends ConstUndirGraph
{

private BitSet[] triangle;


// ======================= initializarion ==========================
// =================================================================


/** Calls super constructor */
public FastUndirGraph(Graph graph)
{
	super(graph);
}

// -----------------------------------------------------------------

protected void initGraph()
{
	final int max = g.size();
	triangle = new BitSet[max];
	for (int i=0; i<max; ++i)
	{
		in[i] = new ArrayList<Integer>();
		triangle[i] = new BitSet(i);
	}

	for(int i=0; i<max; ++i)
	{
		for(Integer out:g.getNeighbours(i))
		{
			int j=out.intValue();
			if( ! g.isEdge(j,i) )
				in[j].add(i);
			// But always add the link to the triangle
			if (i>j) // make sure i>j
				triangle[i].set(j);
			else
				triangle[j].set(i);
		}
	}
}


// ============================ Graph functions ====================
// =================================================================


public boolean isEdge(int i, int j)
{
	// make sure i>j
	if (i<j)
	{
		int ii=i;
		i=j;
		j=ii;
	}
	return triangle[i].get(j);
}
}