Package edu.princeton.cs.algs4

Class AdjMatrixEdgeWeightedDigraph

Object

edu.princeton.cs.algs4.AdjMatrixEdgeWeightedDigraph

public class AdjMatrixEdgeWeightedDigraph
extends Object

The AdjMatrixEdgeWeightedDigraph class represents an edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight. It supports the following two primary operations: add a directed edge to the digraph and iterate over all of edges incident from a given vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges are disallowed; self-loops are permitted.

This implementation uses an adjacency-matrix representation. All operations take constant time (in the worst case) except iterating over the edges incident from a given vertex, which takes time proportional to V.

For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

Constructor	Description
AdjMatrixEdgeWeightedDigraph(int V)	Initializes an empty edge-weighted digraph with V vertices and 0 edges.
AdjMatrixEdgeWeightedDigraph(int V, int E)	Initializes a random edge-weighted digraph with V vertices and E edges.

Method Summary

Modifier and Type	Method	Description
void	addEdge(DirectedEdge e)	Adds the directed edge e to the edge-weighted digraph (if there is not already an edge with the same endpoints).
Iterable<DirectedEdge>	adj(int v)	Returns the directed edges incident from vertex v.
int	E()	Returns the number of edges in the edge-weighted digraph.
static void	main(String[] args)	Unit tests the AdjMatrixEdgeWeightedDigraph data type.
String	toString()	Returns a string representation of the edge-weighted digraph.
int	V()	Returns the number of vertices in the edge-weighted digraph.

Methods inherited from class java.lang.Object

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

Constructor Detail

AdjMatrixEdgeWeightedDigraph

public AdjMatrixEdgeWeightedDigraph(int V)

Initializes an empty edge-weighted digraph with V vertices and 0 edges.

Parameters:

V - the number of vertices

Throws:

IllegalArgumentException - if V < 0

AdjMatrixEdgeWeightedDigraph

public AdjMatrixEdgeWeightedDigraph(int V,
                                    int E)

Initializes a random edge-weighted digraph with V vertices and E edges.

Parameters:

V - the number of vertices

E - the number of edges

Throws:

IllegalArgumentException - if V < 0

IllegalArgumentException - if E < 0

Method Detail

V

public int V()

Returns the number of vertices in the edge-weighted digraph.

Returns:

the number of vertices in the edge-weighted digraph

E

public int E()

Returns the number of edges in the edge-weighted digraph.

Returns:

the number of edges in the edge-weighted digraph

addEdge

public void addEdge(DirectedEdge e)

Adds the directed edge e to the edge-weighted digraph (if there is not already an edge with the same endpoints).

Parameters:

e - the edge

adj

public Iterable<DirectedEdge> adj(int v)

Returns the directed edges incident from vertex v.

Parameters:

v - the vertex

Returns:

the directed edges incident from vertex v as an Iterable

Throws:

IllegalArgumentException - unless 0 <= v < V

toString

public String toString()

Returns a string representation of the edge-weighted digraph. This method takes time proportional to V².

Overrides:

toString in class Object

Returns:

the number of vertices V, followed by the number of edges E, followed by the V adjacency lists of edges

main

public static void main(String[] args)

Unit tests the AdjMatrixEdgeWeightedDigraph data type.

Parameters:

args - the command-line arguments