X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/24dbcb1a8071fe684d776063f04b314d92094e8d..23da67335f942457b0d8b1f10e9849eba0eee9f7:/contrib/psg/src/peersim/graph/NeighbourListGraph.java diff --git a/contrib/psg/src/peersim/graph/NeighbourListGraph.java b/contrib/psg/src/peersim/graph/NeighbourListGraph.java deleted file mode 100644 index 50b3c9721b..0000000000 --- a/contrib/psg/src/peersim/graph/NeighbourListGraph.java +++ /dev/null @@ -1,173 +0,0 @@ -/* - * 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 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 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> 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(1000); - neighbors = new ArrayList>(1000); - nodeindex = new HashMap(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>(size); - for(int i=0; i()); - 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()); - 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 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(); } -} - - - -