Package model.graph

Class UGraph<A>

java.lang.Object

model.graph.UGraph<A>

Type Parameters:

A - the type of vertices in the simple undirected graph

All Implemented Interfaces:

Graph<A>

public final class UGraph<A>
extends Object
implements Graph<A>

A representation of a simple undirected graph. More formally, a structure containing a set vertices and a set edges such that:

• The set edges is a subset of the set vertices choose 2, which is the set of all subsets of vertices with size 2.
• Each edge in edges is undirected so that it can be represented as a mathematical set, or an unordered pair, and the edge {u, v} = {v, u} for any u, v in vertices.
• There are no self-loops, so no vertex has an edge to itself. Hence for all edges {u, v} where u, v in vertices, we have that u ≠v.

This class models the mathematical simple undirected graph in the following way:

• vertices contains elements all of type A
• edges contains UEdge objects which are unordered pairs. Moreover, the condition of no self-loops is enforced in the construction of UEdge.

Since:

2025

See Also:

• UEdge

Constructor Summary

Constructors

Constructor	Description
UGraph(Set<A> vertices, Set<UEdge<A>> edges)	Constructs a new simple undirected graph from a set of vertices and undirected edges.

Method Summary

Modifier and Type	Method	Description
UGraph<A>	addEdge(UEdge<A> edge)	Returns a new UGraph with the specified edge added.
static <A> UGraph<A>	complete(Set<A> vertices)	Constructs the complete undirected graph on the given set of vertices.
static <A> UGraph<A>	cycle(List<A> vertices)	Constructs the cycle graph from a list vertices [v1, v2,..., vn] such that there is an edge between each two consecutive vertices in the list and an edge, {vn, v1}, between the last vertex and the first vertex in the list.
long	degree(A v)	Returns the degree of vertex v.
List<Long>	degreeSequence()	Returns the non-increasing degree sequence of the graph as a list.
Set<UEdge<A>>	edges()	Returns the set of edges in the simple undirected graph.
int	edgesCount()	Returns the number of edges in the graph.
boolean	equals(Object o)
static <A> UGraph<A>	fromEdges(Set<UEdge<A>> edges)	Constructs a new simple undirected from a set of undirected edges.
boolean	hasEdge(A v, A u)	Returns true if the graph contains an edge between vertex v and vertex u.
int	hashCode()
int	incidencesCount()	Returns the number of incidences in the graph.
Set<A>	neighbours(A v)	Returns the set of vertices that are adjacent to vertex v.
static <A> UGraph<A>	path(List<A> vertices)	Constructs the path graph from a list vertices [v1, v2,..., vn] such that there is an edge between each two consecutive vertices in the list.
UGraph<A>	removeEdge(UEdge<A> edge)	Returns a new UGraph without the specified edge.
UGraph<A>	removeVertex(A v)	Returns a new UGraph with the specified vertex v removed.
static <A> UGraph<A>	star(Set<A> vertices, A centre)	Constructs the star graph with one central vertex adjacent to all other vertices in a given set of vertices and a centre vertex
UGraph<A>	subdivideEdge(A w, UEdge<A> edge)	Returns a new UGraph with the specified vertex w added in such a way that it subdivides the specified edge into two new edges by placing the specified vertex w in between the end vertices of the specified edge.
String	toString()
Set<A>	vertices()	Returns the set of vertices in the simple undirected graph.
int	verticesCount()	Returns the number of vertices in the graph.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Details

UGraph

public UGraph(Set<A> vertices,
 Set<UEdge<A>> edges)

Constructs a new simple undirected graph from a set of vertices and undirected edges.

Parameters:

vertices - the set of vertices in the undirected graph

edges - the set of undirected edges, UEdge objects, in the graph

Method Details

fromEdges

public static <A> UGraph<A> fromEdges(Set<UEdge<A>> edges)

Constructs a new simple undirected from a set of undirected edges. The set of vertices is inferred from the set of edges, so that the resulting graph is connected.

Constructs a graph with the set of edges edges and sets the set of vertices vertices so that the graph is connected. In other words, it is the set of all endpoints of edges.

Parameters:

edges - the set of all edges in the graph

Returns:

the connected graph with the edge set edges

Throws:

NullPointerException - if edges is null

complete

public static <A> UGraph<A> complete(Set<A> vertices)

Constructs the complete undirected graph on the given set of vertices.

For a set of vertices V of size n, this returns the graph containing all n(n-1)/2 possible unordered edges between distinct vertices so that every pair of vertices is adjacent

Type Parameters:

A - the vertex type

Parameters:

vertices - the set of vertices V

Returns:

the complete graph on vertices

Throws:

NullPointerException - if set vertices is null

IllegalArgumentException - if set vertices contains less than 2 elements

star

public static <A> UGraph<A> star(Set<A> vertices,
 A centre)

Constructs the star graph with one central vertex adjacent to all other vertices in a given set of vertices and a centre vertex

For a set of vertices V, this returns the graph where the only edges are the edges connecting the centre vertex to each of the other vertices

Type Parameters:

A - the vertex type

Parameters:

vertices - the set of vertices V

centre - the centre vertex in V

Returns:

the star graph on vertices with centre as the central vertex

Throws:

NullPointerException - if provided set of vertices or centre vertex is null

IllegalArgumentException - if the provided centre vertex is not contained in the set of vertices

path

public static <A> UGraph<A> path(List<A> vertices)

Constructs the path graph from a list vertices [v1, v2,..., vn] such that there is an edge between each two consecutive vertices in the list.

From a list of vertices [v1, v2,..., vn], this returns a graph where the set of vertices is the set of the elements of the list {v1, v2,..., vn} and the set of edges is {{v(i), v(i + 1)}} for i = 0, 1,..., n - 1.

Type Parameters:

A - the vertex type

Parameters:

vertices - the list of vertices

Returns:

the path graph from the list vertices

Throws:

NullPointerException - if list vertices is null

IllegalArgumentException - if the list vertices has less than 2 elements or if the list contains duplicate elements

cycle

public static <A> UGraph<A> cycle(List<A> vertices)

Constructs the cycle graph from a list vertices [v1, v2,..., vn] such that there is an edge between each two consecutive vertices in the list and an edge, {vn, v1}, between the last vertex and the first vertex in the list.

From a list of vertices [v1, v2,..., vn], this returns a graph where the set of vertices is the set of the elements of the list {v1, v2,..., vn} and the set of edges is {{v(i), v(i + 1)}} ∪ {vn, v1} for i = 0, 1,..., n - 1.

Type Parameters:

A - the vertex type

Parameters:

vertices - the list of vertices

Returns:

the cycle graph from the list vertices

Throws:

NullPointerException - if list vertices is null

IllegalArgumentException - if the list vertices has less than 3 elements or if the list contains duplicate elements

hasEdge

public boolean hasEdge(A v,
 A u)

Returns true if the graph contains an edge between vertex v and vertex u. In other words, returns true if vertex v is adjacent (a neighbour of) vertex u.

Returns true if and only if the set of edges edges contains the UEdge with components v and u.

Parameters:

v -

u -

Returns:

true if the vertex v is adjacent to vertex u in the graph

degree

public long degree(A v)

Returns the degree of vertex v.

Counts the number of edges that the vertex v is a part of and returns the result. v is a part of an edge if the UEdge has one of its components equal to v

Parameters:

v - the vertex

Returns:

the number of edges the vertex v is a part of

Throws:

IllegalArgumentException - if v is not contained in the set of vertices

neighbours

public Set<A> neighbours(A v)

Returns the set of vertices that are adjacent to vertex v. In other words, returns the set of neighbours, or the neighbourhood of v.

Returns a subset of the set of all vertices in the graph such that each vertex, w, in the subset is adjacent to v, hence the set of edges contains the UEdge with components v and w.

Parameters:

v - the vertex

Returns:

a subset of vertices such that all vertices in the subset are adjacent to v

Throws:

IllegalArgumentException - if v is not contained in the set of all vertices

incidencesCount

public int incidencesCount()

Returns the number of incidences in the graph.

Returns the number of all possible ordered pairs (v, e) in the graph where v is a vertex in vertices and e is an edge in edges. This number corresponds to twice the size of the set edges, or the sum of the degrees of all vertices.

Returns:

the number of incidences in the graph

See Also:

• degree(Object)

edgesCount

public int edgesCount()

Returns the number of edges in the graph.

Returns the size of the set edges.

Returns:

the number of edges in the graph

verticesCount

public int verticesCount()

Returns the number of vertices in the graph.

Returns the size of the set vertices.

Returns:

the number of vertices in the graph

degreeSequence

public List<Long> degreeSequence()

Returns the non-increasing degree sequence of the graph as a list.

For each vertex in vertices, this finds the degree of the vertex and adds the result to a list that is sorted in reverse order so that the result is a non-increasing sequence of degrees of all vertices in the graph.

Returns:

the non-increasing degree sequence of the graph as a list

See Also:

• degree(Object)

removeEdge

public UGraph<A> removeEdge(UEdge<A> edge)

Returns a new UGraph without the specified edge.

Returns a new UGraph with the same set vertices and the set of edges as edges - edge, thus all edges in edges except for the specified edge to remove.

Parameters:

edge - the edge to remove in the new graph

Returns:

the new UGraph without the specified edge

Throws:

IllegalArgumentException - if edge is not contained in the set edges

addEdge

public UGraph<A> addEdge(UEdge<A> edge)

Returns a new UGraph with the specified edge added.

Returns a new UGraph with the same set vertices and the set of edges as edges ∪ edge, thus the set containing all edges in edges and the specified edge to add.

Parameters:

edge - the edge to add to the new graph

Returns:

the new UGraph with the specified edge added.

Throws:

IllegalArgumentException - if the specified edge is between vertices that are not contained in the set vertices

removeVertex

public UGraph<A> removeVertex(A v)

Returns a new UGraph with the specified vertex v removed.

Returns a new UGraph with the set of vertices as vertices - v, thus all vertices in vertices except for the specified vertex v to remove and the set of edges as all the edges in edges except for those that have the vertex v as one of its ends.

Parameters:

v - the vertex to remove in the new graph

Returns:

the new UGraph with the specified vertex v removed

Throws:

IllegalArgumentException - if the specified vertex v is not contained in the set vertices

subdivideEdge

public UGraph<A> subdivideEdge(A w,
 UEdge<A> edge)

Returns a new UGraph with the specified vertex w added in such a way that it subdivides the specified edge into two new edges by placing the specified vertex w in between the end vertices of the specified edge.

Specifically, if the specified edge has the end vertices u and v, the new vertex w is placed so that the specified edge is replaced with two new edges, {u, w} and {w, v}. Then, returns a new UGraph with the set of vertices as vertices ∪ w, thus the set containing all vertices in vertices and the specified vertex w to add, and the set of edges as (edges - edge) ∪ {{u, w}, {w, v}}, hence the set edges with edge replaced by the edges {u, w} and {w, v}.

Parameters:

w - the vertex to add to the new graph

edge - the edge to subdivide in the new graph

Returns:

the new UGraph with the edge subdivided by the vertex w

vertices

public Set<A> vertices()

Returns the set of vertices in the simple undirected graph.

Returns:

the set of vertices

edges

public Set<UEdge<A>> edges()

Returns the set of edges in the simple undirected graph.

Returns:

the set of edges

equals

public boolean equals(Object o)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

toString

public String toString()

Overrides:

toString in class Object