neighbourlistgraph.java

peersim最新版1.0.4

/*
 * 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.*;

/**
* Implements a graph which uses the neighbour list representation.
* No multiple edges are allowed. The implementation also supports the
* growing of the graph. This is very useful when the number of nodes is
* not known in advance or when we construct a graph reading a file.
*/
public class NeighbourListGraph implements Graph, java.io.Serializable {

// =================== private fields ============================
// ===============================================================

/** Contains the objects associated with the node indeces.*/
private final ArrayList<Object> nodes;

/**
* Contains the indices of the nodes. The vector "nodes" contains this
* information implicitly but this way we can find indexes in log time at
* the cost of memory (node that the edge lists typically use much more memory
* than this anyway). Note that the nodes vector is still necessary to
* provide constant access to nodes based on indexes.
*/
private final HashMap<Object,Integer> nodeindex;

/** Contains sets of node indexes. If "nodes" is not null, indices are 
* defined by "nodes", otherwise they correspond to 0,1,... */
private final ArrayList<Set<Integer>> neighbors;

/** Indicates if the graph is directed. */
private final boolean directed;

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

/**
* Constructs an empty graph. That is, the graph has zero nodes, but any
* number of nodes and edges can be added later.
* @param directed if true the graph will be directed
*/
public NeighbourListGraph( boolean directed ) {

	nodes = new ArrayList<Object>(1000);	
	neighbors = new ArrayList<Set<Integer>>(1000);
	nodeindex = new HashMap<Object,Integer>(1000);
	this.directed = directed;
}

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

/**
* Constructs a graph with a fixed size without edges. If the graph is
* constructed this way, it is not possible to associate objects to nodes,
* nor it is possible to grow the graph using {@link #addNode}.
* @param directed if true the graph will be directed
*/
public NeighbourListGraph( int size, boolean directed ) {

	nodes = null;
	neighbors = new ArrayList<Set<Integer>>(size);
	for(int i=0; i<size; ++i) neighbors.add(new HashSet<Integer>());
	nodeindex = null;
	this.directed = directed;
}

// =================== public methods =============================
// ================================================================

/**
* If the given object is not associated with a node yet, adds a new
* node. Returns the index of the node. If the graph was constructed to have
* a specific size, it is not possible to add nodes and therefore calling
* this method will throw an exception.
* @throws NullPointerException if the size was specified at construction time.
*/
public int addNode( Object o ) {

	Integer index = nodeindex.get(o);
	if( index == null )
	{
		index = nodes.size();
		nodes.add(o);
		neighbors.add(new HashSet<Integer>());
		nodeindex.put(o,index);
	}

	return index;
}


// =================== graph implementations ======================
// ================================================================


public boolean setEdge( int i, int j ) {
	
	boolean ret = neighbors.get(i).add(j);
	if( ret && !directed ) neighbors.get(j).add(i);
	return ret;
}

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

public boolean clearEdge( int i, int j ) {
	
	boolean ret = neighbors.get(i).remove(j);
	if( ret && !directed ) neighbors.get(j).remove(i);
	return ret;
}

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

public boolean isEdge(int i, int j) {
	
	return neighbors.get(i).contains(j);
}

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

public Collection<Integer> getNeighbours(int i) {
	
	return Collections.unmodifiableCollection(neighbors.get(i));
}

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

/** If the graph was gradually grown using {@link #addNode}, returns the
* object associated with the node, otherwise null */
public Object getNode(int i) { return (nodes==null?null:nodes.get(i)); }
	
// ---------------------------------------------------------------

/**
* Returns null always. 
*/
public Object getEdge(int i, int j) { return null; }

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

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

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

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

public int degree(int i) { return neighbors.get(i).size(); }
}