Package cpsc331.collections

Interface Graph

public interface Graph

Provides an interface for a simple undirected graph.

Graph Invariant: An undirected graph G = (V, E) such that

V = { v₀, v₁, v₂, ..., v_n−1 }

for some positive integer n is maintained.

Additional Requirement: A constructor with an integer input, “numberVertices”, should be supplies.

• If numbeVertices ≥ 0 then an instance, such that |V| = numberVertices and E is initially the empty set, should be created.
• If numberVertices < 0 then an IllegalArgumentException should be thrown and no instance should be created.

Method Summary

Modifier and Type	Method	Description
void	addEdge(int i, int j)	Adds an edge to this graph.
int	degree(int i)	Returns the degree of an input vertex.
int[]	edges()	Returns the edges in this graph.
boolean	isEdge(int i, int j)	Reports whether an edge from a given vertex to another given vertex exists.
int[]	neighbours(int i)	Returns the neighbours of a given vertex.
int	numberEdges()	Returns the number of edges in this graph.
int	numberVertices()	Reports the number of vertices in this graph.
void	removeEdge(int i, int j)	Removes an edge from this graph.

Method Detail

numberVertices

int numberVertices()

Reports the number of vertices in this graph.

Returns:

number of vertices in this graph

Precondition:

1. The Graph Invariant is satisfied.

Postcondition:

1. The number of vertices in this graph is returned as output.

addEdge

void addEdge(int i,
             int j)
      throws java.lang.IllegalArgumentException,
             EdgeFoundException

Adds an edge to this graph.

Parameters:

i - an integer, representing the index of a vertex in this graph

j - an integer, representing the index of another vertex in this graph

Throws:

java.lang.IllegalArgumentException - if one or both of the integers i and j do not represent (indices of) vertices in this graph or if they represent the same vertex

EdgeFoundException - if there is already an edge from the vertex represented by i to the vertex represented by j in this graph

Precondition:

1. The Graph Invariant is satisfied, so that a graph G = (V, E)) is represented.
2. A pair of integers i and j are given as input.
   
   

Postcondition:

1. If i < 0, i ≥ |V|, j < 0, j ≥ |V|, or 0 ≤ i, j < |V| but i = j, then an IllegalArgumentException is thrown and the graph is not changed.
2. If 0 ≤ i, j < |V| and i ≠ j, but (v_i, v_j) ∈ E, then an EdgeFoundException is thrown and the graph is not changed.
3. If 0 ≤ i, j < |V|, i ≠ j and (v_i, v_j) ∉ E then this edge is added to the graph, that is, E is replaced by E ∪ {(v_i, v_j)}

removeEdge

void removeEdge(int i,
                int j)
         throws java.lang.IllegalArgumentException,
                NoSuchEdgeException

Removes an edge from this graph.

Parameters:

i - an integer, representing the index of a vertex in this graph

j - an integer, representing the index of another vertex in this graph

Throws:

java.lang.IllegalArgumentException - if one or both of the integers i and j do not represent vertices in this graph or if they represent the same vertex

NoSuchEdgeException - if there is no edge (v_i, v_j) in this graph

Precondition:

1. The Graph Invariant is satisfied, so that a graph G = (V, E) is represented.
2. A pair of integers i and j are given as input.
   
   

Postcondition:

1. If i < 0, i ≥ |V|, j < 0, j ≥ |V|, or 0 ≤ i, j < |V| but i = j, then an IllegalArgumentException is thrown and the graph is not changed.
2. If 0 ≤ i, j < |V| and i ≠ j, but (v_i, v_j) ∉ E, then a NoSuchEdgeException is thrown and the graph is not changed.
3. If 0 ≤ i, j < |V|, i ≠ j and (v_i, v_j) ∈ E then this edge is removed, that is, (v_i, v_j) is removed from the set E.

isEdge

boolean isEdge(int i,
               int j)
        throws java.lang.IllegalArgumentException

Reports whether an edge from a given vertex to another given vertex exists.

Parameters:

i - an integer, representing the index of a vertex in this graph

j - an integer, representing the index of another vertex in this graph

Returns:

true if there is an edge from the vertex represented by i to the vertex represented by j, returning false, otherwise

Precondition:

1. The Graph Invariant is satisfied, so that a graph G = (V, E) is represented.
2. A pair of integers i and j are given as input.
   
   

Postcondition:

1. If i < 0, i ≥ |V|, j < 0, j ≥ |V|, or 0 ≤ i, j < |V| but i = j, then an IllegalArgumentException is thrown.
2. If 0 ≤ i, j < |V| and i ≠ j then true is returned if (v_i, v_j) isin; E, and false is returned, otherwise.

Throws:

java.lang.IllegalArgumentException - if one or both of the integers i and j do not represent indices of vertices in this graph or if they represent the same vertex

degree

int degree(int i)
    throws java.lang.IllegalArgumentException

Returns the degree of an input vertex.

Parameters:

i - an integer, representing the index of a vertex in this graph

Returns:

the degree of v_i

Precondition:

1. The Graph Invariant is satisfied, so that a graph G = (V, E) is represented.
2. An integer i is given as input.
   
   

Postcondition:

1. If i < 0 or i ≥ |V| then an IllegalArgumentException is thrown.
2. If 0 ≤ i < |V| then the degree of v_i is returned as output.

Throws:

java.lang.IllegalArgumentException - if i does not represent a vertex in this graph

neighbours

int[] neighbours(int i)
          throws java.lang.IllegalArgumentException

Returns the neighbours of a given vertex.

Parameters:

i - an integer, representing the index of a vertex in this graph

Returns:

an array of integers that represent the neighbours of the input vertex

Precondition:

1. The Graph Invariant is satisfied, so that a graph G = (V, E) is represented.
2. An integer i is given as input.
   
   

Postcondition:

1. If i < 0 or i ≥ |V| then an IllegalArgumentException is thrown.
2. If 0 ≤ i < |V| then an an array of integers, whose length is the degree of the input vertex v_i and whose entries represent the neighbours of the input vertex, is returned.

Throws:

java.lang.IllegalArgumentException - if i does not represent a vertex in this graph

numberEdges

int numberEdges()

Returns the number of edges in this graph.

Returns:

the number of edges in this graph

Precondition:

1. The Graph Invariant is satisfied, so that a graph G = (V, E) is represented.
   
   

Postcondition:

1. The number of edges in this graph is returned.

edges

int[] edges()

Returns the edges in this graph.

Returns:

an array of integers that represent the edges in this graph

Precondition:

1. The Graph Invariant is satisfied, so that a graph G = (V, E) is represented.
   
   

Postcondition:

1. An array of ordered pairs of integers, whose length is the number of edges in the graph and whose entries represent the edges of the graph, is returned.