Interface AugmentedGraph

All Superinterfaces:
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


public boolean isNode(java.lang.Object obj)

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


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.