graph.algorithms.lrpartition

Class LRPartition<V extends Vertex,E extends Edge<V>>

java.lang.Object

graph.algorithms.lrpartition.LRPartition<V,E>

Type Parameters:

V - The vertex type

E - The edge type

public class LRPartition<V extends Vertex,E extends Edge<V>>
extends java.lang.Object

A partition B = L U R of DFS oriented graph's back edges into two classes, referred to as left and right, is called left-right partition, or LR partition for short

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
LRPartition(Graph<V,E> graph)

Method Summary

Modifier and Type	Method and Description
boolean	createLRPartition() An LR partition is a partition of the back edges into Left and Right so that for every fork all return edges of e ending strictly higher than lowpt(e2) belong to one partition, and all return edges of e2 ending strictly higher than lowpt(e1) belong to the other.
boolean	createLRPartition(DFSTree<V,E> tree)
java.util.List<E>	getLeft() Returns the left partition
java.util.List<E>	getRight() Returns the right partition
void	printPartition()
void	setLeft(java.util.List<E> left)
void	setRight(java.util.List<E> right)
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

LRPartition

public LRPartition(Graph<V,E> graph)

Method Detail

createLRPartition

public boolean createLRPartition()

An LR partition is a partition of the back edges into Left and Right so that for every fork all return edges of e ending strictly higher than lowpt(e2) belong to one partition, and all return edges of e2 ending strictly higher than lowpt(e1) belong to the other.

Returns:

true if it can be partitioned, false otherwise

createLRPartition

public boolean createLRPartition(DFSTree<V,E> tree)

Parameters:

tree - Tree whose back edges are being partitioned

Returns:

true if it can be partitioned, false otherwise

getRight

public java.util.List<E> getRight()

Returns the right partition

Returns:

A list of edges in the right partition

setRight

public void setRight(java.util.List<E> right)

Parameters:

right - Edges in the right partition

getLeft

public java.util.List<E> getLeft()

Returns the left partition

Returns:

A list of edges in the left partition

setLeft

public void setLeft(java.util.List<E> left)

Parameters:

left - Edges in the left partition

printPartition

public void printPartition()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object