com.kuka.graph.impl
Class TransposeGraph<N,E extends Edge<N>>

java.lang.Object
  com.kuka.graph.impl.AbstractGraph<N,E>
      com.kuka.graph.impl.TransposeGraph<N,E>

Type Parameters:

N - the type of the nodes.

E - the type of the edges.

All Implemented Interfaces:

Graph<N,E>, Iterable<N>

public class TransposeGraph<N,E extends Edge<N>>
extends AbstractGraph<N,E>

In the mathematical and algorithmic study of graph theory, the converse, transpose or reverse of a directed graph G is another directed graph on the same set of vertices with all of the edges reversed compared to the orientation of the corresponding edges in G. That is, if G contains an edge (i,j) then the transpose of G contains an edge (j,i) and vice versa.

This class implements the transpose graph as an unmodifiable view of the original graph, i.e. it is not allowed to change the transpose graph but changes to the original graph are also visible in the transpose graph.

See also https://en.wikipedia.org/wiki/Transpose_graph.

Constructor Summary

TransposeGraph(Graph<N,E> graph)
Creates a transposed view of the given graph.

Method Summary

boolean	addEdge(E edge) Adds the specified edge to this graph if it is not already present (optional operation).
boolean	addNode(N node) Adds the specified node to this graph if it is not already present (optional operation).
boolean	containsEdge(E edge) Returns true if this graph contains the specified edge.
boolean	containsNode(N node) Returns true if this graph contains the specified node.
E	createEdge(N source, N target) Creates a new edge from the specified source node to the target node, adds it to this graph and returns the created edge.
N	createNode() Creates a new node, adds it to this graph and returns the created node.
Set<E>	edges() Returns an unmodifiable Set view of the edges contained in this graph.
E	getEdge(N source, N target) Returns the edge e=(source,target) from the specified source node to the target node, or null if this graph contains no such edge.
Set<E>	incomingEdges(N node) Returns the set of all incoming edges of the specified node.
Set<N>	neighbors(N node) Returns the set of all neighbors of the specified node.
Set<N>	nodes() Returns an unmodifiable Set view of the nodes contained in this graph.
Set<E>	outgoingEdges(N node) Returns the set of all outgoing edges of the specified node.
boolean	removeEdge(E edge) Removes the specified edge e from this graph if it is present (optional operation).
boolean	removeNode(N node) Removes the specified node n from this graph if it is present (optional operation).

Methods inherited from class com.kuka.graph.impl.AbstractGraph

addAllEdges, addAllNodes, clear, containsAllEdges, containsAllNodes, containsEdge, edges, edgeSize, isEmpty, iterator, nodes, nodeSize, removeAllEdges, removeAllNodes, removeEdge, retainAllEdges, retainAllNodes, toString

Methods inherited from class java.lang.Object

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

Constructor Detail

TransposeGraph

public TransposeGraph(Graph<N,E> graph)

Creates a transposed view of the given graph.

Parameters:

graph - the graph from which the transposed view is to be created

Method Detail

containsNode

public boolean containsNode(N node)

Description copied from interface: Graph

Returns true if this graph contains the specified node. More formally, returns true if and only if this graph contains a node n* such that node.equals(n*).

Parameters:

node - node whose presence in this graph is to be tested

Returns:

true if this graph contains the specified node

containsEdge

public boolean containsEdge(E edge)

Description copied from interface: Graph

Returns true if this graph contains the specified edge. More formally, returns true if and only if this graph contains an edge e* such that edge.equals(e*).

Parameters:

edge - edge whose presence in this graph is to be tested

Returns:

true if this graph contains the specified edge

nodes

public Set<N> nodes()

Description copied from interface: Graph

Returns an unmodifiable Set view of the nodes contained in this graph. The set is backed by the graph, so changes to the graph are reflected in the set. If the graph is modified while an iteration over the set is in progress, the results of the iteration are undefined.

Returns:

a set view of the nodes contained in this graph

edges

public Set<E> edges()

Description copied from interface: Graph

Returns an unmodifiable Set view of the edges contained in this graph. The set is backed by the graph, so changes to the graph are reflected in the set. If the graph is modified while an iteration over the set is in progress, the results of the iteration are undefined.

Returns:

a set view of the edges contained in this graph

getEdge

public E getEdge(N source,
                 N target)

Description copied from interface: Graph

Returns the edge e=(source,target) from the specified source node to the target node, or null if this graph contains no such edge.

More formally, if this graph contains an edge e* such that e.equals(e*), where e=(source,target), then this method returns e*, otherwise it returns null.

Parameters:

source - the source node of the edge that is to be returned

target - the target node of the edge that is to be returned

Returns:

the the edge from the specified source node to the target node, or null if this graph contains no such edge

outgoingEdges

public Set<E> outgoingEdges(N node)

Description copied from interface: Graph

Returns the set of all outgoing edges of the specified node. If no such edge exists, then the returned set is empty.

More formally, this method returns all edges e in this graph such that the given node is the source node of e, i.e. e=(node,*).

Parameters:

node - the source node

Returns:

the set of all edges with the given node as source

incomingEdges

public Set<E> incomingEdges(N node)

Description copied from interface: Graph

Returns the set of all incoming edges of the specified node. If no such edge exists, then the returned set is empty.

More formally, this method returns all edges e in this graph such that the given node is the target node of e, i.e. e=(*,node).

Parameters:

node - the target node

Returns:

the set of all edges with the given node as target

neighbors

public Set<N> neighbors(N node)

Returns the set of all neighbors of the specified node. If no such node exists, the the returned set is empty.

In this transposed view of the underlying graph G all neighbors of the given node are returned after reversing all edges of G.

Parameters:

node - the node of which all neighboring nodes are to be returned

Returns:

the set of all neighbors of the given node

createNode

public N createNode()

Description copied from interface: Graph

Creates a new node, adds it to this graph and returns the created node.

Returns:

the created node

createEdge

public E createEdge(N source,
                    N target)

Description copied from interface: Graph

Creates a new edge from the specified source node to the target node, adds it to this graph and returns the created edge. If graph does not contain the specified nodes they are added, too.

Parameters:

source - the source node of the edge that is to be created

target - the target node of the edge that is to be created

Returns:

the created edge

addNode

public boolean addNode(N node)

Description copied from interface: Graph

Adds the specified node to this graph if it is not already present (optional operation).

More formally, adds the specified node n to this graph if the graph contains no element n2 such that n.equals(n2)) . If this graph already contains the element, the call leaves the graph unchanged and returns false.

Parameters:

node - node to be added to this graph

Returns:

true if this graph did not already contain the specified node

addEdge

public boolean addEdge(E edge)

Description copied from interface: Graph

Adds the specified edge to this graph if it is not already present (optional operation).

More formally, adds the specified edge e to this graph if the graph contains no element e2 such that e.equals(e2)) . If this graph already contains the element, the call leaves the graph unchanged and returns false.

Parameters:

edge - edge to be added to this graph

Returns:

true if this graph did not already contain the specified edge

removeNode

public boolean removeNode(N node)

Description copied from interface: Graph

Removes the specified node n from this graph if it is present (optional operation).

More formally, removes a node n* such that n.equals(n*) , if this graph contains such a node. Furthermore, all edges incident to this node are removed. Returns true if this graph contained the node (or equivalently, if this graph changed as a result of the call).

Parameters:

node - node to be removed from this graph, if present

Returns:

true if this graph contained the specified node

removeEdge

public boolean removeEdge(E edge)

Description copied from interface: Graph

Removes the specified edge e from this graph if it is present (optional operation).

More formally, removes an edge e* such that e.equals(e*), if this graph contains such an edge. Returns true if this graph contained the edge (or equivalently, if this graph changed as a result of the call).

Parameters:

edge - edge to be removed from this graph, if present

Returns:

true if this graph contained the specified edge