graph

Interface Graph<L>

Type Parameters:

L - type of vertex labels in this graph, must be immutable

public interface Graph<L>

A mutable weighted directed graph with labeled vertices. Vertices have distinct labels of an immutable type L when compared using the equals method. Edges are directed and have a positive weight of type int.

PS2 instructions: this is a required ADT interface. You MUST NOT change the specifications or add additional methods.

Method Summary

Modifier and Type	Method and Description
boolean	add(L vertex) Add a vertex to this graph.
static <L> Graph<L>	empty() Create an empty graph.
boolean	remove(L vertex) Remove a vertex from this graph; any edges to or from the vertex are also removed.
int	set(L source, L target, int weight) Add, change, or remove a weighted directed edge in this graph.
Map<L,Integer>	sources(L target) Get the source vertices with directed edges to a target vertex and the weights of those edges.
Map<L,Integer>	targets(L source) Get the target vertices with directed edges from a source vertex and the weights of those edges.
Set<L>	vertices() Get all the vertices in this graph.

Method Detail

empty

static <L> Graph<L> empty()

Create an empty graph.

Type Parameters:

L - type of vertex labels in the graph, must be immutable

Returns:

a new empty weighted directed graph

add

boolean add(L vertex)

Add a vertex to this graph.

Parameters:

vertex - label for the new vertex

Returns:

true if this graph did not already include a vertex with the given label; otherwise false (and this graph is not modified)

set

int set(L source,
        L target,
        int weight)

Add, change, or remove a weighted directed edge in this graph. If weight is nonzero, add an edge or update the weight of that edge; vertices with the given labels are added to the graph if they do not already exist. If weight is zero, remove the edge if it exists (the graph is not otherwise modified).

Parameters:

source - label of the source vertex

target - label of the target vertex

weight - nonnegative weight of the edge

Returns:

the previous weight of the edge, or zero if there was no such edge

remove

boolean remove(L vertex)

Remove a vertex from this graph; any edges to or from the vertex are also removed.

Parameters:

vertex - label of the vertex to remove

Returns:

true if this graph included a vertex with the given label; otherwise false (and this graph is not modified)

vertices

Set<L> vertices()

Get all the vertices in this graph.

Returns:

the set of labels of vertices in this graph

sources

Map<L,Integer> sources(L target)

Get the source vertices with directed edges to a target vertex and the weights of those edges.

Parameters:

target - a label

Returns:

a map where the key set is the set of labels of vertices such that this graph includes an edge from that vertex to target, and the value for each key is the (nonzero) weight of the edge from the key to target

targets

Map<L,Integer> targets(L source)

Get the target vertices with directed edges from a source vertex and the weights of those edges.

Parameters:

source - a label

Returns:

a map where the key set is the set of labels of vertices such that this graph includes an edge from source to that vertex, and the value for each key is the (nonzero) weight of the edge from source to the key