org.metasyntactic.math
Interface Graph

All Known Subinterfaces:

DirectedGraph, UndirectedGraph

All Known Implementing Classes:

AbstractGraph

public interface Graph

A Graph G is a pair (V, E), where V is a finite set and E is a binary relation on V. The set V is called the vertex set of G, and its elements are called vertices (singular: vertex). The set E is called the edge set of G, and its elements are called edges.

Nested Class Summary

static interface	Graph.Edge
static interface	Graph.Path A path of length k from a vertex u to a vertex u' in a Graph G = (V, E) is a sequence ⟨v0, v1, 2, …, vk⟩ of vertices such that u = v0, u' = vk, and (vi-1, vi) ∈ E for i = 1, 2, …, k.

Method Summary

boolean	addEdge(java.util.List edge) Adds this edge to the graph.
boolean	addVertex(java.lang.Object vertex) Adds this vertex to the graph.
boolean	areAdjacent(java.lang.Object u, java.lang.Object v) If (u, v) is an edge in a Graph G = (V, E), we say that vertex v is adjacent to vertex u.
boolean	containsEdge(java.util.List edge)
boolean	containsVertex(java.lang.Object vertex)
int	degree(java.lang.Object vertex) The degree of a vertex in an undirected graph is the number of of edges incident on it.
java.util.Set	getEdges() For a graph G = (V, E), this return E
java.util.Set	getVertices() For a graph G = (V, E), this returns V
Graph	induce(java.util.Set v_prime) Given a set V' ⊆ V, the subgraph of g induced is the graph G' = (V', E'), where: E' = { (u, v) ∈ E : u, v ∈ V' }
boolean	isReachable(java.lang.Object u, java.lang.Object u_prime) If there is a path p from u to u' we say that u' is reachable from u via p.
boolean	isSubgraph(Graph g_prime) We say that a graph G' = (V', E') is a subgraph of G = (V, E) if V' ⊆ V and E' ⊆ E.

Method Detail

areAdjacent

public boolean areAdjacent(java.lang.Object u,
                           java.lang.Object v)

If (u, v) is an edge in a Graph G = (V, E), we say that vertex v is adjacent to vertex u. When the graph is undirected, the adjacency relation is symmetric. When the graph is directed, the adjacency relation is not necessarily symmetric. If v is adjacent to u in a directed graph, we sometimes write u → v.

Parameters:

u - A node of the graph

v - A node of the graph

Returns:

true If and only if u → v

degree

public int degree(java.lang.Object vertex)

The degree of a vertex in an undirected graph is the number of of edges incident on it. The degree of a vertex in a directed graph is its in-degree plus its out-degree.

Parameters:

vertex - The vertex to determine the degree of

Returns:

The degree of that vertex

isSubgraph

public boolean isSubgraph(Graph g_prime)

We say that a graph G' = (V', E') is a subgraph of G = (V, E) if V' ⊆ V and E' ⊆ E.

Parameters:

g_prime - The graph you are checking whether or not it is a subgraph of this graph

Returns:

true if g_prime is a subgraph of this graph

induce

public Graph induce(java.util.Set v_prime)

Given a set V' ⊆ V, the subgraph of g induced is the graph G' = (V', E'), where:
E' = { (u, v) ∈ E : u, v ∈ V' }

Parameters:

v_prime - The subset of vertices with which to induce a subgraph out of

Returns:

The graph induced from this using that subset of V

addVertex

public boolean addVertex(java.lang.Object vertex)

Adds this vertex to the graph.

Parameters:

vertex - The vertex to add to this graph

Returns:

true if this vertex was not already in the graph

addEdge

public boolean addEdge(java.util.List edge)

Adds this edge to the graph. If the edge must only contain vertices already in this graph.

Parameters:

edge - The edge to add. This must be a tuple with order 2

Returns:

true if this edge did not exist in the graph

getVertices

public java.util.Set getVertices()

For a graph G = (V, E), this returns V

Returns:

the vertices of this graph

getEdges

public java.util.Set getEdges()

For a graph G = (V, E), this return E

Returns:

the edges of this graph

isReachable

public boolean isReachable(java.lang.Object u,
                           java.lang.Object u_prime)

If there is a path p from u to u' we say that u' is reachable from u via p.

containsVertex

public boolean containsVertex(java.lang.Object vertex)

containsEdge

public boolean containsEdge(java.util.List edge)