constundirgraph.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.
 *
 */
		
package peersim.graph;

import java.util.*;

/**
* This class is an adaptor making any Graph an undirected graph
* by making its edges bidirectional. The graph to be made undirected
* is passed to the constructor. Only the reference is stored.
* However, at construction time the incoming edges are stored
* for each node, so if the graph
* passed to the constructor changes over time then
* methods {@link #getNeighbours(int)} and {@link #degree(int)}
* become inconsistent (but only those).
* The upside of this inconvenience is that {@link #getNeighbours} will have
* constant time complexity.
* @see UndirectedGraph
*/
public class ConstUndirGraph implements Graph {


// ====================== private fileds ========================
// ==============================================================


protected final Graph g;

protected final List<Integer>[] in;

// ====================== public constructors ===================
// ==============================================================

/**
* Initialization based on given graph. Stores the graph and if necessary
* (if the graph is directed) searches for the incoming edges and stores
* them too. The given graph is stored by reference (not cloned) so it should
* not be modified while this object is in use.
*/
public ConstUndirGraph( Graph g ) {

	this.g = g;
	if( !g.directed() )
	{
		in = null;
	}
	else
	{
		in = new List[g.size()];
	}
	
	initGraph();
}
	
// --------------------------------------------------------------

/** Finds and stores incoming edges */
protected void initGraph() {

	final int max = g.size();
	for(int i=0; i<max; ++i) in[i] = new ArrayList<Integer>();
	for(int i=0; i<max; ++i)
	{
		for(Integer j:g.getNeighbours(i))
		{
			if( ! g.isEdge(j,i) ) in[j].add(i);
		}
	}
}


// ======================= Graph implementations ================
// ==============================================================


public boolean isEdge(int i, int j) {
	
	return g.isEdge(i,j) || g.isEdge(j,i);
}

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

/**
* Uses sets as collection so does not support multiple edges now, even if
* the underlying directed graph does.
*/
public Collection<Integer> getNeighbours(int i) {
	
	List<Integer> result = new ArrayList<Integer>();
	result.addAll(g.getNeighbours(i));
	if( in != null ) result.addAll(in[i]);
	return Collections.unmodifiableCollection(result);
}

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

/** Returns the node from the underlying graph */
public Object getNode(int i) { return g.getNode(i); }
	
// ---------------------------------------------------------------

/**
* If there is an (i,j) edge, returns that, otherwise if there is a (j,i)
* edge, returns that, otherwise returns null.
*/
public Object getEdge(int i, int j) {
	
	if( g.isEdge(i,j) ) return g.getEdge(i,j);
	if( g.isEdge(j,i) ) return g.getEdge(j,i);
	return null;
}

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

public int size() { return g.size(); }

// --------------------------------------------------------------------
	
public boolean directed() { return false; }

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

/** not supported */
public boolean setEdge( int i, int j ) {
	
	throw new UnsupportedOperationException();
}

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

/** not supported */
public boolean clearEdge( int i, int j ) {
	
	throw new UnsupportedOperationException();
}

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

public int degree(int i) { return g.degree(i)+(in==null?0:in[i].size()); }

// ---------------------------------------------------------------
/*
public static void main( String[] args ) {

	Graph net = new BitMatrixGraph(20);
	GraphFactory.wireKOut(net,5,new Random());
	ConstUndirGraph ug = new ConstUndirGraph(net);
	for(int i=0; i<net.size(); ++i)
		System.err.println(
			i+" "+net.getNeighbours(i)+" "+net.degree(i));
	System.err.println("============");
	for(int i=0; i<ug.size(); ++i)
		System.err.println(i+" "+ug.getNeighbours(i)+" "+ug.degree(i));
	System.err.println("============");
	for(int i=0; i<ug.size(); ++i)
		System.err.println(i+" "+ug.in[i]);
	for(int i=0; i<ug.size(); ++i)
	{
		for(int j=0; j<ug.size(); ++j)
			System.err.print(ug.isEdge(i,j)?"W ":"+ ");
		System.err.println();
	}

	GraphIO.writeUCINET_DL(net,System.out);
	GraphIO.writeUCINET_DL(ug,System.out);
}
*/
}