I have implemented Pre Flow Push in Java. I am getting array out of bounds exception when I input a random graph. Can someone explain to me why I am getting this exception and how to fix it?
I am able to get the flow value for Bipartite Graphs, but not for any other type of graphs
public class PreFlowPush {
public class Height {
private int itemCount;
private int maxHeightIndex;
private final LinkedList<Vertex>[] list;
public int getMaxHeightIndex() {
return maxHeightIndex;
}
public Height(int n){
this.itemCount = 0;
this.maxHeightIndex = 0;
list = new LinkedList[n];
for(int i = 0; i < n; i++){
list[i] = new LinkedList<Vertex>();
}
}
public boolean isEmpty(){
return itemCount == 0;
}
public void add(int index, Vertex v){
list[index].add(v);
if(index > maxHeightIndex){
maxHeightIndex = index;
}
itemCount++;
}
public void remove(int index, Vertex v){
list[index].remove(v);
if(maxHeightIndex == index && list[index].size() == 0) {
while (maxHeightIndex >= 0) {
if(list[maxHeightIndex].size() != 0){
break;
}
maxHeightIndex--;
}
}
itemCount--;
}
public boolean contains(int index, Vertex v){
return list[index].contains(v);
}
public Vertex getFirst(int index){
return list[index].getFirst();
}
public int getListSize(int index){
return list[index].size();
}
}
public class Vertex_data {
private int height;
private int excess;
public Node current;
public edgeList edgeLinkedList;
public Vertex_data(Iterator<Edge> edgeIterator){
this.height = 0;
this.excess = 0;
edgeLinkedList = new edgeList();
while(edgeIterator.hasNext()){
Edge e = edgeIterator.next();
edgeLinkedList.put(e);
}
this.current = edgeLinkedList.getFirst();
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
public int getExcess() {
return excess;
}
public void setExcess(int excess) {
this.excess = excess;
}
public boolean hasExcess(){
return excess > 0;
}
}
public class Edge_Data {
private int flow = 0;
private final int capacity;
public Edge forwardEdge;
public Edge backwardEdge;
public Edge_Data(int capacity, Vertex v, Vertex w, String name){
this.capacity = capacity;
this.forwardEdge = new Edge(v, w, capacity - flow, "forward");
this.backwardEdge = new Edge(w, v, flow, "backward");
}
public int getFlow() {
return flow;
}
public void setFlow(int flow) {
this.flow = flow;
setForward();
setBackward();
}
public int getCapacity() {
return capacity;
}
public void setForward(){
forwardEdge.setData(capacity-flow);
}
public void setBackward(){
backwardEdge.setData(flow);
}
public Integer getForwardCapacity(){
return (Integer) forwardEdge.getData();
}
public Integer getBackwardCapacity() {
return (Integer) backwardEdge.getData();
}
public boolean hasForwardEdge(){
return !forwardEdge.getData().equals(0);
}
public boolean hasBackwardEdge(){
return !backwardEdge.getData().equals(0);
}
}
public class edgeList {
private Node head;
/**
* Gets the Node for a given Edge
*
* @param Edge
* @return for a search hit or null for a search miss
*/
public Node get(Edge Edge) {
Node current = head;
while (current != null) {
if (Edge.equals(current.Edge)) {
return current;
}
current = current.next;
}
return null;
}
public Node getFirst(){
return head;
}
/**
* puts a Edge- pair at the beginning of the list
*
* @param Edge
*/
public void put(Edge Edge) {
for (Node current = head; current != null; current = current.next) {
if (Edge.equals(current.Edge)) {
return;
}
}
head = new Node(Edge, head);
}
/**
* Lazy deletion of the Node with a given Edge
*
* @param Edge given Edge
* @throws NullPointerException if the given Edge is not found in the list
*/
public void delete(Edge Edge) {
Node currentPrevious = null;
Node current = head;
while (current != null) {
if (Edge.equals(current.Edge)) {
if (current == head) {
head = head.next;
current.next = null;
return;
} else {
currentPrevious.next = current.next;
current.next = null;
return;
}
}
currentPrevious = current;
current = current.next;
}
throw new NullPointerException("The given Edge is not present in the list!");
}
}
public class Node {
Edge Edge;
Node next;
public Node(Edge Edge, Node nextNode) {
this.Edge = Edge;
this.next = nextNode;
}
public Edge getEdge(){
return this.Edge;
}
public Node getNext(){
return this.next;
}
}
private final SimpleGraph graph;
private final Height heights;
public PreFlowPush(SimpleGraph graph){
this.graph = graph;
heights = new Height(graph.numVertices()+1);
initialize();
}
public int preflow_push(){
int Flow_Value = 0;
boolean can_push = false;
boolean can_relabel = false;
Vertex v = heights.getFirst(heights.getMaxHeightIndex());
while(!heights.isEmpty()) {
Vertex_data vData = (Vertex_data) v.getData();
Node current = vData.current;
while(vData.hasExcess()) {
while (current != null) {
Edge e = current.getEdge();
Edge_Data eData = (Edge_Data) e.getData();
Vertex w = graph.opposite(v, e);
Vertex_data wData = (Vertex_data) w.getData();
can_push = push(v, vData, w, wData, e, eData);
if (can_push) {
if (!vData.hasExcess()) {
if (eData.getCapacity() != eData.getFlow()) {
break;
} else {
if (vData.current.next != null) {
vData.current = vData.current.getNext();
}
break;
}
}
}
current = current.getNext();
}
if (!can_push) {
can_relabel = relabel(v, vData);
if (can_relabel) {
vData.current = vData.edgeLinkedList.getFirst();
current = vData.current;
} else {
break;
}
}
}
if(heights.isEmpty()){
break;
}
v = heights.getFirst(heights.getMaxHeightIndex());
}
Iterator vertexIterator = graph.vertices();
while(vertexIterator.hasNext()){
Vertex p = (Vertex) vertexIterator.next();
if(p.getName().equals("s")){
Iterator edgeIterator = graph.incidentEdges(p);
while(edgeIterator.hasNext()){
Edge e = (Edge) edgeIterator.next();
Edge_Data eData = (Edge_Data) e.getData();
Flow_Value += eData.getFlow();
}
}
}
return Flow_Value;
}
private void Height_add(int height, Vertex v){
Vertex_data vData = (Vertex_data) v.getData();
if(!v.getName().equals("t") && vData.hasExcess()) {
heights.add(height, v);
}
}
private void moveToNewHeight(int prevHeight, int newHeight, Vertex v){
heights.remove(prevHeight, v);
if(!v.getName().equals("t")) {
heights.add(newHeight, v);
}
}
private void modifyHeight(Vertex v, Vertex_data vData){
int height = vData.getHeight();
if(!vData.hasExcess() && heights.contains(height, v)){
removeFromHeight(height, v);
} else{
if(!heights.contains(height, v)){
Height_add(height, v);
}
}
}
private void removeFromHeight(int height, Vertex v){
heights.remove(height, v);
}
private boolean relabel(Vertex v, Vertex_data vData){
if(vData.getExcess() > 0){
Iterator<Edge> edgeIterator = (Iterator<Edge>) graph.incidentEdges(v);
while(edgeIterator.hasNext()){
Edge e = edgeIterator.next();
Edge_Data eData = (Edge_Data) e.getData();
Vertex w = graph.opposite(v, e);
Vertex_data wData = (Vertex_data) w.getData();
if(e.getSecondEndpoint().equals(v)){
if(!eData.hasBackwardEdge()){
continue;
}
} else if(e.getFirstEndpoint().equals(v)){
if(!eData.hasForwardEdge()){
continue;
}
}
if(!(wData.getHeight() >= vData.getHeight())){
return false;
}
}
moveToNewHeight(vData.getHeight(), vData.getHeight() + 1, v);
vData.setHeight(vData.getHeight() + 1);
return true;
}
return false;
}
private boolean push(Vertex v, Vertex_data vData, Vertex w, Vertex_data wData, Edge e, Edge_Data eData){
if(!(vData.getExcess() > 0 && wData.getHeight() < vData.getHeight())){
return false;
}
int delta;
if(e.getFirstEndpoint().equals(v)){
if(eData.hasForwardEdge()){
delta = Math.min(vData.getExcess(), eData.getForwardCapacity());
eData.setFlow(eData.getFlow() + delta);
modifyExcess(v, e, vData, eData);
return true;
}
} else if(e.getSecondEndpoint().equals(v)){
if(eData.hasBackwardEdge()){
delta = Math.min(vData.getExcess(), eData.getFlow());
eData.setFlow(eData.getFlow() - delta);
modifyExcess(v, e, vData, eData);
return true;
}
}
return false;
}
private void initialize(){
Iterator<Vertex> it = (Iterator<Vertex>) graph.vertices();
Iterator<Edge> edgeIterator = (Iterator<Edge>) graph.edges();
while(edgeIterator.hasNext()){
Edge e = edgeIterator.next();
Double data = (Double) e.getData();
int capacity = (int) data.doubleValue();
String name = (String) e.getName();
Edge_Data eData = new Edge_Data(capacity, e.getFirstEndpoint(), e.getSecondEndpoint(), name);
e.setData(eData);
}
while(it.hasNext()){
Vertex v = it.next();
Iterator<Edge> edgeIteratorV = (Iterator<Edge>) graph.incidentEdges(v);
Vertex_data vData = new Vertex_data(edgeIteratorV);
if(v.getName().equals("s")){
continue;
}
vData.setHeight(0);
v.setData(vData);
}
it = (Iterator<Vertex>) graph.vertices();
while(it.hasNext()) {
Vertex v = it.next();
Iterator<Edge> edgeIteratorV = (Iterator<Edge>) graph.incidentEdges(v);
Vertex_data vData = new Vertex_data(edgeIteratorV);
if (v.getName().equals("s")) {
v.setData(vData);
initializeSource(v, vData);
break;
}
}
edgeIterator = (Iterator<Edge>) graph.edges();
while(edgeIterator.hasNext()){
Edge e = edgeIterator.next();
Edge_Data eData = (Edge_Data) e.getData();
if(!(e.getFirstEndpoint().getName().equals("s") || e.getSecondEndpoint().getName().equals("s"))){
eData.setFlow(0);
}
}
}
private void modifyExcess(Vertex v, Edge e, Vertex_data vData, Edge_Data eData){
Vertex w = graph.opposite(v, e);
int excess = eData.getFlow();
Vertex_data wData = (Vertex_data) w.getData();
vData.setExcess(vData.getExcess() - excess);
wData.setExcess(wData.getExcess() + excess);
modifyHeight(v, vData);
modifyHeight(w, wData);
}
private void initializeSource(Vertex v, Vertex_data vData){
vData.setHeight(graph.numVertices());
int Flow_Value = 0;
Iterator<Edge> edgeIterator = (Iterator<Edge>) graph.incidentEdges(v);
while(edgeIterator.hasNext()){
Edge e = edgeIterator.next();
Edge_Data eData = (Edge_Data) e.getData();
eData.setFlow(eData.getCapacity());
modifyExcess(v, e, vData, eData);
Flow_Value += eData.getFlow();
}
if(vData.hasExcess()) {
Height_add(graph.numVertices(), v);
}
Flow_Value = -1*Flow_Value;
vData.setExcess(Flow_Value);
v.setData(vData);
}
public static void main(String[] args) {
SimpleGraph G = new SimpleGraph();
Vertex s = null;
Vertex t = null;
Iterator itr;
System.out.print("Please enter the full path of input graph: ");
String userinput;
userinput = KeyboardReader.readString();
GraphInput.LoadSimpleGraph(G,userinput);
itr= G.vertices();
while (itr.hasNext()) {
Vertex vert = (Vertex) itr.next();
if (vert.getName().equals("s")) {
s = vert;
}else if (vert.getName().equals("t")) {
t = vert;
}
}
long startTime=System.currentTimeMillis();
PreFlowPush runPreFlowPush = new PreFlowPush(G);
long flow = runPreFlowPush.preflow_push();
long endTime=System.currentTimeMillis();
System.out.println("The max flow of this graph is " + flow);
System.out.println("PFP's running time is " + (endTime - startTime) + "ms");
}
}
