edu.stanford.math.plex4.graph

Class UndirectedListGraph

java.lang.Object

edu.stanford.math.plex4.graph.UndirectedListGraph

All Implemented Interfaces:

AbstractUndirectedGraph, java.io.Serializable, java.lang.Iterable<edu.stanford.math.primitivelib.autogen.pair.IntIntPair>

public class UndirectedListGraph
extends java.lang.Object
implements AbstractUndirectedGraph

This class implements the functionality of an undirected graph. It uses an adjacency list data structure. That is, for each vertex u, it stores the set of vertices {v_1, .., v_k} such that u is connected to v_i and v_i < u. For example consider the following graph: 0 -- 1 | | 2 -- 3 -- 4 The following storage scheme is used: 1: {0} 2: {0} 3: {1, 2} 4: {3}

Author:

Andrew Tausz

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
UndirectedListGraph(AbstractUndirectedGraph graph) This constructor initializes the graph with the contents of another graph.
UndirectedListGraph(int numVertices) Constructor which initializes the graph to consist of disconnected vertices.
UndirectedListGraph(int[][] adjacencyMatrix) Constructor which initializes the graph to contain the edges given in the specified adjacency matrix.
UndirectedListGraph(int numVertices, gnu.trove.TIntObjectHashMap<gnu.trove.TIntHashSet> adjacencySets)

Method Summary

Methods

Modifier and Type	Method and Description
void	addEdge(int i, int j) This function adds the edge (i, j) to the graph.
boolean	containsEdge(int i, int j) This function returns true if the edge (i, j) is in the graph, and false otherwise.
int	getDegree(int v)
int[]	getDegreeSequence()
gnu.trove.TIntHashSet	getLowerNeighbors(int i) This function returns the set of neighbors of vertex i in the graph which have indices less than i.
int[]	getNeighbors(int v)
int	getNumEdges() Gets the number of edges in the graph.
int	getNumVertices() Gets the number of vertices in the graph.
java.util.Iterator<edu.stanford.math.primitivelib.autogen.pair.IntIntPair>	iterator() This function returns an edge iterator that allows the user to iterate over the set of edges in the graph.
void	removeEdge(int i, int j) This function removes the edge (i, j) from the graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

UndirectedListGraph

public UndirectedListGraph(int numVertices)

Constructor which initializes the graph to consist of disconnected vertices. The number of vertices is initialized to numVertices.

Parameters:

numVertices - the number of vertices to initialize the graph with

UndirectedListGraph

public UndirectedListGraph(int numVertices,
                   gnu.trove.TIntObjectHashMap<gnu.trove.TIntHashSet> adjacencySets)

UndirectedListGraph

public UndirectedListGraph(AbstractUndirectedGraph graph)

This constructor initializes the graph with the contents of another graph.

Parameters:

graph - the graph to initialize with

UndirectedListGraph

public UndirectedListGraph(int[][] adjacencyMatrix)

Constructor which initializes the graph to contain the edges given in the specified adjacency matrix.

Parameters:

adjacencyMatrix - the adjacency matrix to initialize with

Method Detail

addEdge

public void addEdge(int i,
           int j)

Description copied from interface: AbstractUndirectedGraph

This function adds the edge (i, j) to the graph.

Specified by:

addEdge in interface AbstractUndirectedGraph

Parameters:

i - the first vertex of the edge to add

j - the second vertex of the edge to add

containsEdge

public boolean containsEdge(int i,
                   int j)

Description copied from interface: AbstractUndirectedGraph

This function returns true if the edge (i, j) is in the graph, and false otherwise.

Specified by:

containsEdge in interface AbstractUndirectedGraph

Parameters:

i - the first vertex of the edge

j - the second vertex of the edge

Returns:

true if (i, j) is an edge in the graph and false otherwise

getNumEdges

public int getNumEdges()

Description copied from interface: AbstractUndirectedGraph

Gets the number of edges in the graph.

Specified by:

getNumEdges in interface AbstractUndirectedGraph

Returns:

the number of edges in the graph

getNumVertices

public int getNumVertices()

Description copied from interface: AbstractUndirectedGraph

Gets the number of vertices in the graph.

Specified by:

getNumVertices in interface AbstractUndirectedGraph

Returns:

the number of vertices in the graph

removeEdge

public void removeEdge(int i,
              int j)

Description copied from interface: AbstractUndirectedGraph

This function removes the edge (i, j) from the graph.

Specified by:

removeEdge in interface AbstractUndirectedGraph

Parameters:

i - the first vertex of the edge to add

j - the second vertex of the edge to add

getLowerNeighbors

public gnu.trove.TIntHashSet getLowerNeighbors(int i)

This function returns the set of neighbors of vertex i in the graph which have indices less than i.

Specified by:

getLowerNeighbors in interface AbstractUndirectedGraph

Parameters:

i - the vertex to query

Returns:

the set of j such that j < i and i ~ j

iterator

public java.util.Iterator<edu.stanford.math.primitivelib.autogen.pair.IntIntPair> iterator()

Description copied from interface: AbstractUndirectedGraph

This function returns an edge iterator that allows the user to iterate over the set of edges in the graph.

Specified by:

iterator in interface AbstractUndirectedGraph

Specified by:

iterator in interface java.lang.Iterable<edu.stanford.math.primitivelib.autogen.pair.IntIntPair>

Returns:

an Iterator

getDegree

public int getDegree(int v)

Specified by:

getDegree in interface AbstractUndirectedGraph

getDegreeSequence

public int[] getDegreeSequence()

Specified by:

getDegreeSequence in interface AbstractUndirectedGraph

getNeighbors

public int[] getNeighbors(int v)

Specified by:

getNeighbors in interface AbstractUndirectedGraph