implementation of Ford Fulkerson algorithm

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.LinkedList;
class MaxFlow
{
static final int V = 6; //Number of vertices in graph
boolean bfs(int rGraph[][], int s, int t, int parent[])
{
boolean visited[] = new boolean[V];
for(int i=0; i<V; ++i)
visited[i]=false;
LinkedList<Integer> queue = new LinkedList<Integer>();
queue.add(s);
visited[s] = true;
parent[s]=-1;
while (queue.size()!=0)
{ int u = queue.poll();
for (int v=0; v<V; v++)
{
if (visited[v]==false && rGraph[u][v] > 0)
{
queue.add(v);
parent[v] = u;
visited[v] = true;
}
}
}
 return (visited[t] == true);
}
int fordFulkerson(int graph[][], int s, int t)
{
int u, v;

int rGraph[][] = new int[V][V];

for (u = 0; u < V; u++)

for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];

int parent[] = new int[V];

int max_flow = 0; // There is no flow initially

// Augment the flow while tere is path from source

// to sink
while (bfs(rGraph, s, t, parent))
{
int path_flow = Integer.MAX_VALUE;
for (v=t; v!=s; v=parent[v])
{
u = parent[v];
path_flow = Math.min(path_flow, rGraph[u][v]);
}

for (v=t; v != s; v=parent[v])

{
 u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}

// Add path flow to overall flow

max_flow += path_flow;
}
return max_flow;
}
public static void main (String[] args) throws java.lang.Exception
{
int graph[][] =new int[][] { {0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};
MaxFlow m = new MaxFlow();

System.out.println("The maximum possible flow is " +

m.fordFulkerson(graph, 0, 5));

}
}
Implementation of bipartite graph

import java.util.*;
class Edge
{
int source, dest;

public Edge(int source, int dest) {

this.source = source;
this.dest = dest;
}
};

// Class to represent a graph object

class Graph
{
// A List of Lists to represent an adjacency list
List<List<Integer>> adjList = null;

// Constructor
Graph(List<Edge> edges, int N) {
adjList = new ArrayList<>(N);
for (int i = 0; i < N; i++) {
adjList.add(i, new ArrayList<>());
}

// add edges to the undirected graph

for (int i = 0; i < edges.size(); i++)
 {
int src = edges.get(i).source;
int dest = edges.get(i).dest;
adjList.get(src).add(dest);
adjList.get(dest).add(src);
} }
}
class BipartiteGraph
{ public static boolean BFS(Graph graph, int v, int N)
{
boolean[] discovered = new boolean[N];
int[] level = new int[N];
discovered[v] = true;
level[v] = 0;
Queue<Integer> q = new ArrayDeque<>();
q.add(v);

// run till queue is not empty

while (!q.isEmpty())
{
v = q.poll();
for (int u : graph.adjList.get(v))
{

if (!discovered[u])
{
discovered[u] = true;
level[u] = level[v] + 1;
q.add(u);
}
 else if (level[v] == level[u])
return false;
}
}
return true;
}

public static void main(String[] args)

List<Edge> edges = Arrays.asList(

new Edge(1, 2), new Edge(2, 3), new Edge(2, 8),
new Edge(3, 4), new Edge(4, 6), new Edge(5, 7),
new Edge(5, 9), new Edge(8, 9));
final int N = 10;
Graph graph = new Graph(edges, N);

if (BFS(graph, 1, N))
System.out.println("Bipartite Graph");
else
System.out.println("Not a Bipartite Graph");
}
}
Implementation of Red Black Tree

#include<stdio.h>
#include<stdlib.h>

//A Red-Black tree node structure

struct node
{
int data; // for data part
char color; // for color property

struct node *left, *right, *parent;

};

void LeftRotate(struct node **root,struct node *x)

struct node *y = x->right;

x->right = y->left;

if (x->right != NULL)
x->right->parent = x;

y->parent = x->parent;
 if (x->parent == NULL)
(*root) = y;

// store y at the place of x

else if (x == x->parent->left)
x->parent->left = y;
else x->parent->right = y;

y->left = x;

x->parent = y;
}

void rightRotate(struct node **root,struct node *y)

{
struct node *x = y->left;
y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
x->parent =y->parent;
if (x->parent == NULL)
(*root) = x;
else if (y == y->parent->left)
y->parent->left = x;
else y->parent->right = x;
x->right = y;
y->parent = x;
}

void insertFixUp(struct node **root,struct node *z)

{

while (z != *root && z->parent->color == 'R')

{
struct node *y;
if (z->parent == z->parent->parent->left)
y = z->parent->parent->right;
else
y = z->parent->parent->left;

if (y->color == 'R')
{
y->color = 'B';
z->parent->color = 'B';
z->parent->parent->color = 'R';
z = z->parent->parent;
}

else
{

if (z->parent == z->parent->parent->left &&

z == z->parent->left)
{
char ch = z->parent->color ;
z->parent->color = z->parent->parent->color;
z->parent->parent->color = ch;
rightRotate(root,z->parent->parent);
}

if (z->parent == z->parent->parent->left &&

z == z->parent->right)
{
char ch = z->color ;
z->color = z->parent->parent->color;
z->parent->parent->color = ch;
 LeftRotate(root,z->parent);
rightRotate(root,z->parent->parent);
}

if (z->parent == z->parent->parent->right &&

z == z->parent->right)
{
char ch = z->parent->color ;
z->parent->color = z->parent->parent->color;
z->parent->parent->color = ch;
LeftRotate(root,z->parent->parent);
}

if (z->parent == z->parent->parent->right &&

z == z->parent->left)
{
char ch = z->color ;
z->color = z->parent->parent->color;
z->parent->parent->color = ch;
rightRotate(root,z->parent);
LeftRotate(root,z->parent->parent);
}
}
}
(*root)->color = 'B'; //keep root always black
}

void insert(struct node **root, int data)

struct node *z = (struct node*)malloc(sizeof(struct node));

z->data = data;
z->left = z->right = z->parent = NULL;
 if (*root == NULL)
{
z->color = 'B';
(*root) = z;
}
else
{
struct node *y = NULL;
struct node *x = (*root);

while (x != NULL)
{
y = x;
if (z->data < x->data)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (z->data > y->data)
y->right = z;
else
y->left = z;
z->color = 'R';

insertFixUp(root,z);
}
}

void inorder(struct node *root)

{
if (root == NULL)
return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
 int main()
{
struct node *root = NULL;
insert(&root,10);
insert(&root,20);
insert(&root,40);
insert(&root,30);
insert(&root,50);
insert(&root,35);
insert(&root,25);
insert(&root,37);
printf("inorder Traversal Is : ");
inorder(root);

return 0;
}

Implement 2-3 Tree

import
java.util.*;

class TwoThreeTree<T extends Comparable<T>> implements Iterable

{
private Node root;
private int size;
private boolean modified = true;
private Traversal traverse;

TwoThreeTree()
{
root = null;
traverse = new Traversal();
 size = 0;
}

void addAll(Collection<T> collection)

{
for (T item: collection)
this.insert(item);
modified = true;
}

void insert(T x)
{
if (root == null)
{
root = new Node(x);
size++;
}
root.insert(x);
modified = true;
}

int size()
{
return size;
}

boolean search(T x)
{
if (root == null)
return false;
return root.search(x).keys.contains(x);
}

void clear()
{
root = null;
size = 0;
}
 public Iterator<T> iterator()
{
if (modified)
{
traverse.traverseTree();
modified = false;

}
return traverse.ordered.iterator();
}

//-----------------------------------------Inner Iterator Class-------------------------------

------------------//

private class Traversal

{
ArrayList<T> ordered;

void traverseTree()
{
ordered = new ArrayList<>();
traverse(root);
}

void traverse(Node n)
{
if (n.children.size() == 0)
ordered.addAll(n.keys);
else
{
traverse(n.children.get(0));
ordered.add(n.keys.get(0));
traverse(n.children.get(1));

if (n.children.size() == 3)
{
ordered.add(n.keys.get(1
 traverse(n.children.get(2));
}
}
}
}

//-------------------------------------------INNER CLASS NODE-------------------------

--------------------------//
private class Node
{
ArrayList<T> keys = new ArrayList<>(3);
ArrayList<Node> children = new ArrayList<>(4);

Node(T data)
{
keys.add(data);
}

private void addKey(T x)

{
this.keys.add(x
int lastIndex = this.keys.size()-1;
for (int i = 0; i < lastIndex; i
{
if (this.keys.get(i).compareTo(this.keys.get(lastIndex)) > 0)
{

this.keys.set(i, this.keys.get(lastIndex));
this.keys.set(lastIndex, temp);
}
}
}

private boolean insert(T x)

{

int i = 0;
 while (i < this.keys.size() && x.compareTo(this.keys.get(i)) > 0)
i++;
boolean childWasSplit;

if (i < this.children.size())
childWasSplit = this.children.get(i).insert(x);
else
{
this.addKey(x);
size++;
if (this.keys.size() == 3)
{
this.splitify();
return true;
}
return false;
}

if (childWasSplit)
{
Node tempChild = this.children.get(i);
this.addKey(tempChild.keys.get(0));
this.children.set(i, tempChild.children.get(0));
this.children.add(i+1, tempChild.children.get(1));
if (this.children.size() == 4)
{
this.splitify();

return true;
}
}
return false;
}

private void splitify()

{
Node left = new Node(this.keys.get(0));
Node right = new Node(this.keys.get(2));
if (this.children.size() == 4)
{
left.children.add(this.children.get(0));
 left.children.add(this.children.get(1));
right.children.add(this.children.get(2));
right.children.add(this.children.get(3));
}
this.children.clear();
this.children.add(left);
this.children.add(right);

T tempKey = this.keys.get(1);
this.keys.clear
this.keys.add(tempKey);
}

private Node search(T val)

{
if (this.children.size() == 0 || this.keys.contains(val))
return this;
else
{
int i = 0;
while (i < this.keys.size() && val.compareTo(this.keys.get(i)) > 0
i++;
return this.children.get(i).search(val);
}
}

public String toString()

{
return this.keys.get(0) + (this.keys.size() == 2 ? " " + this.keys.get(1) :
"");
}
}
}