edu.stanford.math.plex4.graph

Class UndirectedWeightedListGraph

java.lang.Object

edu.stanford.math.plex4.graph.UndirectedWeightedListGraph

All Implemented Interfaces:

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

public class UndirectedWeightedListGraph
extends java.lang.Object
implements AbstractWeightedUndirectedGraph

This class implements the functionality of an undirected weighted graph. It uses an adjacency list representation. See the class UndirectedListGraph for more information about the internal representation.

Author:

Andrew Tausz

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
UndirectedWeightedListGraph(int numVertices) Constructor which initializes the graph to consist of disconnected vertices.

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.
void	addEdge(int i, int j, double weight) This function adds an edge with specified weight.
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.
gnu.trove.TIntObjectHashMap<gnu.trove.TIntHashSet>	getUnweightedAdjacencySets()
double	getWeight(int i, int j) This function returns the weight of the edge (i, j).
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.
UndirectedListGraph	toUnweightedGraph()

Methods inherited from class java.lang.Object

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

Constructor Detail

UndirectedWeightedListGraph

public UndirectedWeightedListGraph(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

Method Detail

addEdge

public void addEdge(int i,
           int j,
           double weight)

Description copied from interface: AbstractWeightedUndirectedGraph

This function adds an edge with specified weight.

Specified by:

addEdge in interface AbstractWeightedUndirectedGraph

Parameters:

i - the index of the first vertex of the edge

j - the index of the second vertex of the edge

weight - the weight of the edge

getWeight

public double getWeight(int i,
               int j)

Description copied from interface: AbstractWeightedUndirectedGraph

This function returns the weight of the edge (i, j).

Specified by:

getWeight in interface AbstractWeightedUndirectedGraph

Parameters:

i - the index of the first vertex of the edge

j - the index of the second vertex of the edge

Returns:

the weight of the edge (i, j)

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

getUnweightedAdjacencySets

public gnu.trove.TIntObjectHashMap<gnu.trove.TIntHashSet> getUnweightedAdjacencySets()

toUnweightedGraph

public UndirectedListGraph toUnweightedGraph()

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