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)