Package aud.graph

Class AbstractGraph<Node extends AbstractNode,Edge extends AbstractEdge>

java.lang.Object

aud.graph.AbstractGraph<Node,Edge>

Type Parameters:

Node - represents a node

Edge - represents an e dge

All Implemented Interfaces:

Graphvizable, GraphvizDecorable, Iterable<Node>

Direct Known Subclasses:

GraphAM

public abstract class AbstractGraph<Node extends AbstractNode,Edge extends AbstractEdge>
extends Object
implements Iterable<Node>, Graphvizable, GraphvizDecorable

Interface to a graph.

Methods throw an IllegalArgumentException if a given node or edge is invalid, i.e., it equals null, or it is not part of this graph.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	AbstractGraph.Edges	Defines iterator over all edges of an @{link AbstractGraph}.

Constructor Summary

Constructors

Constructor	Description
AbstractGraph(Node nodeGenerator, Edge edgeGenerator)	Constructor.

Method Summary

Modifier and Type	Method	Description
abstract Edge	addEdge(Node source, Node destination)	Create and add new edge from source to destination.
abstract Node	addNode()	create and add new node
protected Edge	check(Edge edge)	helper: check if edge is valid
protected Node	check(Node node)	helper: check if node is valid
AbstractGraph<Node,Edge>.Edges	edges()	Get Edges instance to obtain iterator.
Edge	ensureEdge(Node source, Node destination)	Same as getEdge(Node, Node) but throw if there is no such edge.
GraphvizDecorator	getDecorator()	get decoration or null
int	getDegree(Node node)	Get total degree.
abstract Edge	getEdge(Node source, Node destination)	Get edge from source to destination.
abstract Iterator<Edge>	getEdgeIterator()	Get iterator over all edges.
int	getInDegree(Node node)	get number of edges incident to node
abstract Vector<Edge>	getInEdges(Node node)	Get incident edges of node.
abstract int	getNumNodes()	get number of nodes
int	getOutDegree(Node node)	get number of edges emanating from node
abstract Vector<Edge>	getOutEdges(Node node)	Get incident edges of node.
abstract Node	getSomeNode()	Get some node.
abstract boolean	isDirected()	Is graph directed?
abstract void	removeEdge(Edge edge)	Remove edge.
abstract void	removeNode(Node node)	Remove node and all its incident and excident edges.
String	toDot()	Get dot representation.
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, iterator, spliterator

Constructor Details

AbstractGraph

public AbstractGraph(Node nodeGenerator,
 Edge edgeGenerator)

Constructor.

The constructor takes two objects that serve as "templates" for creating new Node (AbstractNode.create()) and Edge (AbstractEdge.create()) instances.

Note: The instances are required due to the way how Java generics work (see type erasure). This is different (indeed much simpler but weaker) than, e.g., C++ templates.

Parameters:

nodeGenerator - "template" for creating Node instances

edgeGenerator - "template" for creating Edge instances

Method Details

isDirected

public abstract boolean isDirected()

Is graph directed?

addNode

public abstract Node addNode()

create and add new node

Returns:

node instance

addEdge

public abstract Edge addEdge(Node source,
 Node destination)

Create and add new edge from source to destination.

• For undirected graphs, source and destination may be swapped such that always source.index()<=destination.index().
• RuntimeException is thrown if the edge already exists.

Parameters:

source - source node

destination - destination node

Returns:

edge instance

Throws:

IllegalArgumentException

RuntimeException

See Also:

• AbstractNode.index()

removeNode

public abstract void removeNode(Node node)

Remove node and all its incident and excident edges.

Throws:

IllegalArgumentException

removeEdge

public abstract void removeEdge(Edge edge)

Remove edge.

Throws:

IllegalArgumentException

getNumNodes

public abstract int getNumNodes()

get number of nodes

getSomeNode

public abstract Node getSomeNode()

Get some node.

This may be any node of the graph.

Returns:

node

Throws:

NoSuchElementException - (for empty graph)

getEdge

public abstract Edge getEdge(Node source,
 Node destination)

Get edge from source to destination.

Order of arguments is not relevant for undirected graphs.

Returns:

edge or null if there is no such edge

Throws:

IllegalArgumentException

ensureEdge

public Edge ensureEdge(Node source,
 Node destination)

Same as getEdge(Node, Node) but throw if there is no such edge.

Returns:

edge

Throws:

RuntimeException - if there is no such edge

IllegalArgumentException

getInEdges

public abstract Vector<Edge> getInEdges(Node node)

Get incident edges of node.

For undirected graphs same as getOutEdges(Node).

Returns:

vector of edges

Throws:

IllegalArgumentException

getOutEdges

public abstract Vector<Edge> getOutEdges(Node node)

Get incident edges of node. For undirected graphs same as getInEdges(Node).

Returns:

vector of edges

Throws:

IllegalArgumentException

getInDegree

public int getInDegree(Node node)

get number of edges incident to node

getOutDegree

public int getOutDegree(Node node)

get number of edges emanating from node

getDegree

public int getDegree(Node node)

Get total degree.

• sum of getInEdges(Node) and getOutEdges(Node) for directed graphs isDirected()
• getInEdges(Node) (equals getOutEdges(Node)} for undirected graphs

getEdgeIterator

public abstract Iterator<Edge> getEdgeIterator()

Get iterator over all edges.

Edges are traversed in arbitrary order.

check

protected Node check(Node node)

helper: check if node is valid

Returns:

node

Throws:

IllegalArgumentException

check

protected Edge check(Edge edge)

helper: check if edge is valid

Returns:

node

Throws:

IllegalArgumentException

edges

public AbstractGraph<Node,Edge>.Edges edges()

Get Edges instance to obtain iterator. Provided for convenience.

Use as for (edge : graph.edges()) { ... }

toString

public String toString()

Overrides:

toString in class Object

getDecorator

public GraphvizDecorator getDecorator()

Description copied from interface: GraphvizDecorable

get decoration or null

Specified by:

getDecorator in interface GraphvizDecorable

toDot

public String toDot()

Description copied from interface: Graphvizable

Get dot representation.

Specified by:

toDot in interface Graphvizable