org.grouplens.grapht.graph

Class DAGNode<V,E>

java.lang.Object

org.grouplens.grapht.graph.DAGNode<V,E>

Type Parameters:

V - The type of node (vertex) labels.

E - The type of edge labels.

All Implemented Interfaces:

Serializable

@Immutable
public class DAGNode<V,E>
extends Object
implements Serializable

A node in a (rooted) DAG. Since DAGs are rooted, a full graph is just represented by its root node. Nodes are compared using reference equality, so distinct nodes do not compare equal even if they have identical labels and edge sets.

Nodes and edges may not have null labels. There may be multiple edges from one node to another, so long as those edges have distinct labels.

Nodes know about all nodes reachable from them, and the edges connecting those nodes.

DAGs and their nodes are immutable. You can build them using a builder, obtained from newBuilder(Object).

Since:

0.7.0

Author:

GroupLens Research

See Also:

Serialized Form

Method Summary

Methods

Modifier and Type	Method and Description
static <V,E> DAGNodeBuilder<V,E>	copyBuilder(DAGNode<V,E> node) Create a new builder initialized to build a copy of the specified node.
DAGEdge<V,E>	findEdgeBFS(com.google.common.base.Predicate<? super DAGEdge<V,E>> pred) Do a breadth-first search for an edge.
DAGNode<V,E>	findNodeBFS(com.google.common.base.Predicate<? super DAGNode<V,E>> pred) Do a breadth-first search for a node.
Set<DAGNode<V,E>>	getAdjacentNodes() Get the nodes that are adjacent to this node (only considering outgoing edges).
Set<DAGEdge<V,E>>	getIncomingEdges(DAGNode<V,E> node) Get the incoming edges to a node reachable from this node.
V	getLabel() Get the label for this node.
DAGEdge<V,E>	getOutgoingEdge(DAGNode<V,E> target, E label) Get the outgoing edge with the specified target and label, if it exists.
Set<DAGEdge<V,E>>	getOutgoingEdges() Get the outgoing edges of this node.
DAGEdge<V,E>	getOutgoingEdgeWithLabel(E label) Get an outgoing edge from this node with the specified label, if it exists.
DAGEdge<V,E>	getOutgoingEdgeWithLabel(com.google.common.base.Predicate<? super E> predicate) Search for an outgoing edge by a predicate.
Set<DAGNode<V,E>>	getReachableNodes()
List<DAGNode<V,E>>	getSortedNodes() Topographical sort all nodes reachable from the given root node.
static <V> com.google.common.base.Predicate<DAGNode<V,?>>	labelMatches(com.google.common.base.Predicate<? super V> pred)
static <V,E> DAGNodeBuilder<V,E>	newBuilder() Construct a new DAG node builder.
static <V,E> DAGNodeBuilder<V,E>	newBuilder(V label) Construct a new DAG node builder.
DAGNode<V,E>	replaceNode(DAGNode<V,E> node, DAGNode<V,E> replacement, Map<DAGNode<V,E>,DAGNode<V,E>> memory) Replace one node with another in this graph.
static <V,E> DAGNode<V,E>	singleton(V label) Create a new DAG node with no outgoing edges.
String	toString()
DAGNode<V,E>	transformEdges(com.google.common.base.Function<? super DAGEdge<V,E>,? extends DAGEdge<V,E>> function) Transform the edges in this graph.

Methods inherited from class java.lang.Object

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

Method Detail

singleton

public static <V,E> DAGNode<V,E> singleton(V label)

Create a new DAG node with no outgoing edges.

Type Parameters:

V - The type of node labels.

E - The type of edge labels.

Parameters:

label - The node label.

newBuilder

public static <V,E> DAGNodeBuilder<V,E> newBuilder()

Construct a new DAG node builder.

Type Parameters:

V - The type of node labels.

E - The type of edge labels.

Returns:

The DAG node builder.

newBuilder

public static <V,E> DAGNodeBuilder<V,E> newBuilder(V label)

Construct a new DAG node builder.

Type Parameters:

V - The type of node labels.

E - The type of edge labels.

Parameters:

label - The node label.

Returns:

The DAG node builder.

copyBuilder

public static <V,E> DAGNodeBuilder<V,E> copyBuilder(DAGNode<V,E> node)

Create a new builder initialized to build a copy of the specified node.

Type Parameters:

V - The type of node labels.

E - The type of edge labels.

Parameters:

node - The node to copy.

Returns:

A new builder initialized with the labels and edges of node.

getLabel

@Nonnull
public V getLabel()

Get the label for this node.

Returns:

The node's label.

getOutgoingEdges

@Nonnull
public Set<DAGEdge<V,E>> getOutgoingEdges()

Get the outgoing edges of this node.

Returns:

The outgoing edges of the node.

getOutgoingEdge

public DAGEdge<V,E> getOutgoingEdge(DAGNode<V,E> target,
                           E label)

Get the outgoing edge with the specified target and label, if it exists.

Parameters:

target - The target node.

label - The label.

Returns:

The edge from this node to target with label label, if it exists, or null if no such edge exists.

getOutgoingEdgeWithLabel

public DAGEdge<V,E> getOutgoingEdgeWithLabel(E label)

Get an outgoing edge from this node with the specified label, if it exists.

Parameters:

label - The label.

Returns:

An outgoing edge with the specified label, or null if no such edge exists. If multiple edges have this label, an arbitrary one is returned.

getOutgoingEdgeWithLabel

public DAGEdge<V,E> getOutgoingEdgeWithLabel(com.google.common.base.Predicate<? super E> predicate)

Search for an outgoing edge by a predicate.

Parameters:

predicate - A predicate over labels.

Returns:

An outgoing edge matching the predicate, or null if no such edge exists. If multiple edges have labels matching the predicate, it is undefined which one will be added.

getAdjacentNodes

public Set<DAGNode<V,E>> getAdjacentNodes()

Get the nodes that are adjacent to this node (only considering outgoing edges).

Returns:

The set of adjacent nodes.

getReachableNodes

@Nonnull
public Set<DAGNode<V,E>> getReachableNodes()

getSortedNodes

@Nonnull
public List<DAGNode<V,E>> getSortedNodes()

Topographical sort all nodes reachable from the given root node. Nodes that are farther away, or more connected, are at the beginning of the list.

Nodes in the graph that are not connected to the root will not appear in the returned list.

Returns:

The sorted list of reachable nodes.

getIncomingEdges

@Nonnull
public Set<DAGEdge<V,E>> getIncomingEdges(DAGNode<V,E> node)

Get the incoming edges to a node reachable from this node.

Returns:

The set of incoming edges, or an empty set if the node is not reachable.

replaceNode

public DAGNode<V,E> replaceNode(DAGNode<V,E> node,
                       DAGNode<V,E> replacement,
                       Map<DAGNode<V,E>,DAGNode<V,E>> memory)

Replace one node with another in this graph. All edges referencing node are replaced with edges referencing replacement.

Parameters:

node - The node to replace.

replacement - The replacement node.

memory - A table to remember node replacements. It maintains a mapping of every node that has to be replaced with the node that replaces it. This map should usually be empty on the initial call to this method. In particular, it should not contain any reachable nodes on the initial call, or unexpected behavior may arise. Recursive calls of this method to itself do contain such nodes.

Returns:

The graph with the replaced node.

findNodeBFS

public DAGNode<V,E> findNodeBFS(@Nonnull
                       com.google.common.base.Predicate<? super DAGNode<V,E>> pred)

Do a breadth-first search for a node.

Parameters:

pred - The predicate for matching nodes.

Returns:

The first node matching pred in a breadth-first search, or null if no such node is found.

findEdgeBFS

public DAGEdge<V,E> findEdgeBFS(@Nonnull
                       com.google.common.base.Predicate<? super DAGEdge<V,E>> pred)

Do a breadth-first search for an edge.

Parameters:

pred - The predicate for matching nodes.

Returns:

The first node matching pred in a breadth-first search, or null if no such node is found.

transformEdges

public DAGNode<V,E> transformEdges(com.google.common.base.Function<? super DAGEdge<V,E>,? extends DAGEdge<V,E>> function)

Transform the edges in this graph. Edges in parent nodes are passed after their target nodes are rewritten, if necessary.

Parameters:

function - The edge transformation function. Any edge returned by this function must have the same head node as the function it was passed. The transform function may need to replace the head node on a returned edge; the label and tail will be preserved. If the function returns null, that is the same as returning its input unmodified.

Returns:

The rewritten graph.

toString

public String toString()

Overrides:

toString in class Object

labelMatches

public static <V> com.google.common.base.Predicate<DAGNode<V,?>> labelMatches(com.google.common.base.Predicate<? super V> pred)