+++ /dev/null
-/*
- * 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(); }
-}
-
-
-
-
