prajna.util

Interface Graph<N,E>

Type Parameters:

N - The class representing the nodes of the graph

E - The class representing the edges of the graph

All Known Implementing Classes:

AbstractGraph, ClusterGraph, DirectedGraph, TimedGraph, TreeGraph, UndirectedGraph

public interface Graph<N,E>

An object which provides relationships between two objects. This interface provides implementation details for the Graph data structure as defined in formal mathematics and computer science theory. Specifically, a graph is defined as a set objects (the nodes) and relations between those objects (the Edges). The graph function G:(N,E,g) is defined so that if g(n1, n2) = e, the edge e is said to connect n1 and n2. The size of a graph is defined to be its number of edges. The number of nodes of a graph is the order of the graph.

A graph can be of two types, directed or undirected. An undirected graph is a graph where the ordering of the nodes defining an edge is not significant, and may be reversed. Formally, g(n1,n2)=g(n2,n1). A directed graph is a graph where g(n1,n2) != g(n2, n1).

This interface implements graphs on arbitrary objects, and conforms to the conventions of the Collections interfaces. It uses generics to allow specific implementations of graphs on specific objects.

Author:

Edward Swing

Nested Class Summary

Nested Classes

Modifier and Type	Interface and Description
static interface	Graph.Segment<N,E> Edge segments are composed of an edge and its two connected nodes.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(N node) Add a node to the graph
void	addAll(Graph<? extends N,? extends E> graph) Add all elements from the specified graph to this graph.
boolean	addEdge(E edge, N orig, N dest) Add the edge element to the graph.
void	clear() Clear all nodes and edges from this graph
boolean	contains(java.lang.Object obj) Determines whether the given object is a node within this graph.
boolean	containsEdge(java.lang.Object obj) Determines whether the given object is an edge within this graph.
java.util.Iterator<E>	edgeIterator() Return an iterator over the set of edges for this graph.
boolean	equals(java.lang.Object obj) Determine whether another object is the same as this graph.
E	getEdge(N n1, N n2) Get the edge between two nodes
Graph.Segment<N,E>	getEdgeSegment(E edge) Get the edge segment for the specified edge
java.util.Set<E>	getEdgeSet() Get the set of edges for this graph
java.util.Set<E>	getNodeEdges(N node) Get the set of edges which connect to a particular node.
java.util.Set<N>	getNodeSet() Get the set of nodes for this graph
java.util.Set<Graph.Segment<N,E>>	getSegmentSet() Get the set of edge segments for this graph
int	hashCode() Get the hashcode for this graph
boolean	isDirected() Return whether this graph is a directed graph
boolean	isEmpty() Return whether the graph is empty.
java.util.Iterator<N>	iterator() Return an iterator over the set of nodes for this graph.
int	order() Return the order of the graph.
boolean	remove(java.lang.Object obj) Remove an object from the graph.
boolean	removeEdge(java.lang.Object edge) Remove the edge from the graph
int	size() Return the size of the graph.

Method Detail

add

boolean add(N node)

Add a node to the graph

Parameters:

node - the node to add

Returns:

true if the node was not already in the graph, false otherwise

addAll

void addAll(Graph<? extends N,? extends E> graph)

Add all elements from the specified graph to this graph.

Parameters:

graph - the graph to add

addEdge

boolean addEdge(E edge,
              N orig,
              N dest)

Add the edge element to the graph. If the origin or destination nodes are not included in the graph, they are also added.

Parameters:

edge - the edge to add

orig - the origin node

dest - the destination node

Returns:

true if the graph was modified as a result of this operation, false otherwise.

clear

void clear()

Clear all nodes and edges from this graph

contains

boolean contains(java.lang.Object obj)

Determines whether the given object is a node within this graph.

Parameters:

obj - the object to test

Returns:

true if the object is a node of this graph, false otherwise

containsEdge

boolean containsEdge(java.lang.Object obj)

Determines whether the given object is an edge within this graph.

Parameters:

obj - the object to test

Returns:

true if the object is an edge of this graph, false otherwise

edgeIterator

java.util.Iterator<E> edgeIterator()

Return an iterator over the set of edges for this graph.

Returns:

an iterator over the set of edges.

equals

boolean equals(java.lang.Object obj)

Determine whether another object is the same as this graph. This method returns true if the object compared is a graph, and contains the same nodes and edges as this graph.

Overrides:

equals in class java.lang.Object

Parameters:

obj - the object to test

Returns:

true if the object is a graph with the same elements as this graph.

getEdge

E getEdge(N n1,
        N n2)

Get the edge between two nodes

Parameters:

n1 - The first node

n2 - The second node

Returns:

the edge between the two nodes, or null if no edge exists.

getEdgeSegment

Graph.Segment<N,E> getEdgeSegment(E edge)

Get the edge segment for the specified edge

Parameters:

edge - the edge

Returns:

the segment containing the edge.

getEdgeSet

java.util.Set<E> getEdgeSet()

Get the set of edges for this graph

Returns:

the set of edges

getNodeEdges

java.util.Set<E> getNodeEdges(N node)

Get the set of edges which connect to a particular node. This includes all edges connecting to the node, regardless of directionality.

Parameters:

node - the node to check

Returns:

the set of edges connecting to the node

getNodeSet

java.util.Set<N> getNodeSet()

Get the set of nodes for this graph

Returns:

the set of nodes

getSegmentSet

java.util.Set<Graph.Segment<N,E>> getSegmentSet()

Get the set of edge segments for this graph

Returns:

the set of edge segments

hashCode

int hashCode()

Get the hashcode for this graph

Overrides:

hashCode in class java.lang.Object

Returns:

the hashcode

isDirected

boolean isDirected()

Return whether this graph is a directed graph

Returns:

true if the graph is directed, false if it is undirected.

isEmpty

boolean isEmpty()

Return whether the graph is empty. The graph is empty if it has no nodes.

Returns:

true if the graph is empty, false otherwise

iterator

java.util.Iterator<N> iterator()

Return an iterator over the set of nodes for this graph.

Returns:

an iterator over the set of nodes.

order

int order()

Return the order of the graph. The order of the graph is the number of nodes in the graph

Returns:

the graph order

remove

boolean remove(java.lang.Object obj)

Remove an object from the graph. This removes the object from the node set, and removes any incident edges as well.

Parameters:

obj - the object to remove

Returns:

true if the graph was changed as a result of this operation

removeEdge

boolean removeEdge(java.lang.Object edge)

Remove the edge from the graph

Parameters:

edge - the edge to remove

Returns:

true if the graph was changed as a result of this operation

size

int size()

Return the size of the graph. The size of the graph is the number of edges in the graph

Returns:

the graph size