peersim.graph
Class NeighbourListGraph

java.lang.Object
  peersim.graph.NeighbourListGraph

All Implemented Interfaces:

java.io.Serializable, Graph

public class NeighbourListGraph
extends java.lang.Object
implements Graph, java.io.Serializable

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.

See Also:

Serialized Form

Constructor Summary

NeighbourListGraph(boolean directed)
Constructs an empty graph.

NeighbourListGraph(int size, boolean directed)
Constructs a graph with a fixed size without edges.

Method Summary

int	addNode(java.lang.Object o) If the given object is not associated with a node yet, adds a new node.
boolean	clearEdge(int i, int j) Removes given edge, returns true if it existed before.
int	degree(int i) Returns the degree of the given node.
boolean	directed() Returns true if the graph is directed otherwise false.
java.lang.Object	getEdge(int i, int j) Returns null always.
java.util.Collection<java.lang.Integer>	getNeighbours(int i) Returns a collection view to all outgoing edges from i.
java.lang.Object	getNode(int i) If the graph was gradually grown using addNode(java.lang.Object), returns the object associated with the node, otherwise null
boolean	isEdge(int i, int j) Returns true if there is a directed edge between node i and node j.
boolean	setEdge(int i, int j) Sets given edge, returns true if it did not exist before.
int	size() The number of nodes in the graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

NeighbourListGraph

public NeighbourListGraph(boolean directed)

Constructs an empty graph. That is, the graph has zero nodes, but any number of nodes and edges can be added later.

Parameters:

directed - if true the graph will be directed

NeighbourListGraph

public NeighbourListGraph(int size,
                          boolean 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 addNode(java.lang.Object).

Parameters:

directed - if true the graph will be directed

Method Detail

addNode

public int addNode(java.lang.Object o)

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:

java.lang.NullPointerException - if the size was specified at construction time.

setEdge

public boolean setEdge(int i,
                       int j)

Description copied from interface: Graph

Sets given edge, returns true if it did not exist before. If the graph is undirected, sets the edge (j,i) as well. Optional operation.

Specified by:

setEdge in interface Graph

clearEdge

public boolean clearEdge(int i,
                         int j)

Description copied from interface: Graph

Removes given edge, returns true if it existed before. If the graph is undirected, removes the edge (j,i) as well. Optional operation.

Specified by:

clearEdge in interface Graph

isEdge

public boolean isEdge(int i,
                      int j)

Description copied from interface: Graph

Returns true if there is a directed edge between node i and node j.

Specified by:

isEdge in interface Graph

getNeighbours

public java.util.Collection<java.lang.Integer> getNeighbours(int i)

Description copied from interface: Graph

Returns a collection view to all outgoing edges from i. The collection should ideally be unmodifiable. In any case, modifying the returned collection is not safe and may result in unspecified behavior.

Specified by:

getNeighbours in interface Graph

getNode

public java.lang.Object getNode(int i)

If the graph was gradually grown using addNode(java.lang.Object), returns the object associated with the node, otherwise null

Specified by:

getNode in interface Graph

getEdge

public java.lang.Object getEdge(int i,
                                int j)

Returns null always.

Specified by:

getEdge in interface Graph

size

public int size()

Description copied from interface: Graph

The number of nodes in the graph.

Specified by:

size in interface Graph

directed

public boolean directed()

Description copied from interface: Graph

Returns true if the graph is directed otherwise false.

Specified by:

directed in interface Graph

degree

public int degree(int i)

Description copied from interface: Graph

Returns the degree of the given node. If the graph is directed, returns out degree.

Specified by:

degree in interface Graph