<?php
$example = range(0, 9);
foreach ($example as $value)
{
echo $value;
}
Graph and basic Graph Traversals:
package com.amazom.graph;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Graph<T> {
private List<Edge<T>> allEdges;
private Map<Long, Vertex<T>> allVertex;
boolean isDirected = false;
public Graph(boolean isDirected) {
allEdges = new ArrayList<Edge<T>>();
allVertex = new HashMap<Long, Vertex<T>>();
this.isDirected = isDirected;
}
public void addEdge(long id1, long id2) {
addEdge(id1, id2, 0);
}
public void addEdge(long id1, long id2, int weight) {
Vertex<T> vertex1 = null;
if (allVertex.containsKey(id1)) {
vertex1 = allVertex.get(id1);
} else {
vertex1 = new Vertex<T>(id1);
allVertex.put(id1, vertex1);
}
Vertex<T> vertex2 = null;
if (allVertex.containsKey(id2)) {
vertex1 = allVertex.get(id2);
} else {
vertex2 = new Vertex<T>(id2);
allVertex.put(id2, vertex2);
}
Edge<T> edge = new Edge<T>(vertex1, vertex2, isDirected, weight);
allEdges.add(edge);
vertex1.addAdjacentVertex(edge, vertex1);
if (!isDirected) {
vertex2.addAdjacentVertex(edge, vertex1);
}
}
public List<Edge<T>> getEdges() {
return allEdges;
}
public Collection<Vertex<T>> getAllVertex() {
return allVertex.values();
}
}
class Edge<T> {
private boolean isDirected = false;
private Vertex<T> vertex1;
private Vertex<T> vertex2;
private int weight;
Edge(Vertex<T> vertex1, Vertex<T> vertex2) {
this.vertex1 = vertex1;
this.vertex2 = vertex2;
}
Edge(Vertex<T> vertex1, Vertex<T> vertex2, boolean isDirected, int weight) {
this.vertex1 = vertex1;
this.vertex2 = vertex2;
this.isDirected = isDirected;
this.weight = weight;
}
Edge(Vertex<T> vertex1, Vertex<T> vertex2, boolean isDirected) {
this.isDirected = isDirected;
this.vertex1 = vertex1;
this.vertex2 = vertex2;
}
public Vertex<T> getVertex1() {
return vertex1;
}
public Vertex<T> getVertex2() {
return vertex2;
}
int getWeight() {
return weight;
}
public boolean isDirected() {
return isDirected;
}
}
class Vertex<T> {
long id;
private T data;
private List<Edge<T>> edges = new ArrayList<Edge<T>>();
private List<Vertex<T>> adjacentVertex = new ArrayList<Vertex<T>>();
Vertex(long id) {
this.id = id;
}
public long getId() {
return id;
}
public void setId(long id) {
this.id = id;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public void addAdjacentVertex(Edge<T> e, Vertex<T> v) {
edges.add(e);
adjacentVertex.add(v);
}
public List<Vertex<T>> getAdjacentVertexes(){
return adjacentVertex;
}
}
Depth First Traversal for Graph:
package com.amazom.graph;
import java.util.HashSet;
import java.util.Set;
public class GraphTraversal {
public void DFS(Graph<Integer> graph) {
Set<Long> visited = new HashSet<Long>();
for (Vertex<Integer> vertex : graph.getAllVertex()) {
if (!visited.contains(vertex.getId())) {
DFSUtil(vertex, visited);
}
}
}
private void DFSUtil(Vertex<Integer> vertex, Set<Long> visited) {
visited.add(vertex.getId());
System.out.println(" vertex " + vertex.id);
for (Vertex<Integer> ver : vertex.getAdjacentVertexes()) {
if (!visited.contains(ver.getId())) {
DFSUtil(vertex, visited);
}
}
}
public static void main(String args[]) {
Graph<Integer> graph = new Graph<Integer>(true);
graph.addEdge(1, 2);
graph.addEdge(1, 5);
graph.addEdge(1, 6);
graph.addEdge(1, 9);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(6, 7);
graph.addEdge(7, 8);
GraphTraversal graphTraversal = new GraphTraversal();
graphTraversal.DFS(graph);
}
}
- Graph: Boggele Game
package com.amazom.graph;
import java.util.Dictionary;
import java.util.HashSet;
import java.util.Set;
public class Boggle {
public void game(Set<String> dictionary, char board[][]) {
boolean visited[][] = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
StringBuffer buffer = new StringBuffer();
DFS(dictionary, i, j, board, visited, buffer);
}
}
}
private void DFS(Set<String> set, int i, int j, char[][] board,
boolean[][] visited, StringBuffer buffer) {
if (i < 0 || j < 0 || i >= board.length || j >= board[i].length) {
return;
}
if (visited[i][j] == true)
return;
visited[i][j] = true;
buffer.append(board[i][j]);
if (set.contains(buffer.toString())) {
System.out.println(" String is " + buffer.toString());
}
for (int k = i - 1; k <= i + 1; k++) {
for (int l = j - 1; l <= j + 1; l++) {
DFS(set, k, l, board, visited, buffer);// Recursion for the overlapping Strings
}
}
buffer.deleteCharAt(buffer.length() - 1);
visited[i][j] = false;
}
public static void main(String args[]) {
Boggle boggle = new Boggle();
char[][] board = { { 't', 'a', 's', 'g' }, { 'l', 'u', 'n', 'h' },
{ 't', 'e', 'i', 'a' }, { 'a', 'w', 's', 'r' }
};
Set<String> dictionary = new HashSet<String>();
dictionary.add("tushar");
dictionary.add("anisweta");
boggle.game(dictionary, board);
}
}
- Binary MaxHeap:
import java.util.ArrayList;
import java.util.List;
class BinaryMaxHeap<T> {
private List<Node> allNodes = new ArrayList<Node>();
class Node {
int weight;
T data;
}
public T extractMax() {
int size = allNodes.size() - 1;
T max = allNodes.get(0).data;
int lastNodeWeight = allNodes.get(size).weight;
allNodes.get(0).weight = lastNodeWeight;
allNodes.get(0).data = allNodes.get(size).data;
allNodes.remove(size);
int currentIndex = 0;
size--;
while (true) {
int left = 2 * currentIndex + 1;
int right = 2 * currentIndex + 2;
if (left > size)
break;
if (right > size) {
right = left;
}
int largerIndex = allNodes.get(left).weight >= allNodes.get(right).weight ? left
: right;
if (allNodes.get(currentIndex).weight < allNodes.get(largerIndex).weight) {
Node temp = allNodes.get(currentIndex);
temp.data = allNodes.get(currentIndex).data;
temp.weight = allNodes.get(currentIndex).weight;
allNodes.get(currentIndex).data = allNodes.get(largerIndex).data;
allNodes.get(currentIndex).weight = allNodes.get(largerIndex).weight;
allNodes.get(largerIndex).data = temp.data;
allNodes.get(largerIndex).weight = temp.weight;
currentIndex = largerIndex;
} else {
break;
}
}
return max;
}
public void add(int weight, T data) {
Node node = new Node();
node.weight = weight;
node.data = data;
allNodes.add(node);
int size = allNodes.size();
int current = size - 1;
int parentIndex = (current - 1) / 2;
while (parentIndex >= 0) {
Node parentNode = allNodes.get(parentIndex);
Node currentNode = allNodes.get(current);
if (parentNode.weight < currentNode.weight) {
/* swap(parentNode,currentNode); */
data = parentNode.data;
weight = parentNode.weight;
parentNode.data = currentNode.data;
parentNode.weight = currentNode.weight;
currentNode.data = data;
currentNode.weight = weight;
current = parentIndex;
parentIndex = (parentIndex - 1) / 2;
} else {
break;
}
}
}
public void displayHeap() {
for (Node n : allNodes) {
System.out.println(" " + n.data + " -- " + n.weight);
}
}
private void swap(Node first, Node second) {
T data = first.data;
int weight = second.weight;
first.data = second.data;
first.weight = second.weight;
second.data = data;
second.weight = weight;
}
}
public class BinaryMaxHeapSample {
public static void main(String args[]) {
BinaryMaxHeap<String> binaryMaxHeap = new BinaryMaxHeap<String>();
BinaryMaxHeap<Integer> binaryMaxHeapInt = new BinaryMaxHeap<Integer>();
binaryMaxHeap.add(3, "Tushar");
binaryMaxHeap.add(4, "Ani");
binaryMaxHeap.add(8, "Vijay");
binaryMaxHeap.add(10, "pramila");
binaryMaxHeap.add(5, "Roy");
binaryMaxHeap.add(6, "NTF");
binaryMaxHeap.displayHeap();
System.out.println(" Max is " + binaryMaxHeap.extractMax());
System.out.println(" HEAP WITH DATATYPE : Integer");
binaryMaxHeapInt.add(3, 007);
binaryMaxHeapInt.add(4, 1007);
binaryMaxHeapInt.add(1, 4007);
binaryMaxHeapInt.add(6, 2007);
binaryMaxHeapInt.add(9, 507);
binaryMaxHeapInt.displayHeap();
System.out.println(" Max is " + binaryMaxHeapInt.extractMax());
}
}
The above example explains the ArrayList implementation for MaxHeap
Explains the usage for the Generic Type defined as the data hence two use case:
1. data as String
2. data as Integer
