javautils.graph.adt
Interface AugmentedGraph

All Superinterfaces:

Graph

All Known Implementing Classes:

AnAugmentedGraph, AugmentedGraphDecorator

public interface AugmentedGraph

extends Graph

An augmented graph allows accessing edges from target nodes. This can improve the efficiency of graph algorithms that would otherwise need to effectively compute the transpose of the graph first (in O(N+E) time).

Note: Clients of non-trivial graph libraries usually do not explicitly need to implement this interface - not even for efficiency reasons. A non-trivial library can easily compute the augmented graph if necessary. If the client passes an already augmented graph to the library, then only the initial augmentation step will be bypassed.

Method Summary

java.util.List	edgesTo(java.lang.Object node) List of all edges to the specified target node.
boolean	isNode(java.lang.Object obj) True if and only if the object is a node of this graph.

Methods inherited from interface javautils.graph.adt.Graph

edgesFrom, nodes, sourceOf, targetOf

Method Detail

isNode

public boolean isNode(java.lang.Object obj)

True if and only if the object is a node of this graph.

edgesTo

public java.util.List edgesTo(java.lang.Object node)

List of all edges to the specified target node.

Important: This method should have O(1) time complexity. This means that you should avoid constructing the list each time this method is called.

Note: The order of edges in the returned list may have an effect on the results of graph algorithms.