Skip to content

Commit 3cbd399

Browse files
ishan-guptishan-gupt
committed
Added all Lab Material
1 parent e353a55 commit 3cbd399

File tree

5 files changed

+438
-0
lines changed

5 files changed

+438
-0
lines changed

‎Floyd Warshall Algorithm/FloydWarshall.java‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package com.ishan.daa;
2+
3+
import java.util.Scanner;
4+
5+
public class FloydWarshall {
6+
private int distancematrix[][];
7+
private int numberofvertices;
8+
public static final int INFINITY = 999;
9+
10+
public FloydWarshall(int numberofvertices) {
11+
distancematrix = new int[numberofvertices + 1][numberofvertices + 1];
12+
this.numberofvertices = numberofvertices;
13+
}
14+
15+
public void floydwarshall(int adjacencymatrix[][]) {
16+
for (int source = 1; source <= numberofvertices; source++) {
17+
for (int destination = 1; destination <= numberofvertices; destination++) {
18+
distancematrix[source][destination] = adjacencymatrix[source][destination];
19+
}
20+
}
21+
for (int intermediate = 1; intermediate <= numberofvertices; intermediate++) {
22+
for (int source = 1; source <= numberofvertices; source++) {
23+
for (int destination = 1; destination <= numberofvertices; destination++) {
24+
if (distancematrix[source][intermediate] + distancematrix[intermediate][destination]
25+
< distancematrix[source][destination])
26+
distancematrix[source][destination] = distancematrix[source][intermediate]
27+
+ distancematrix[intermediate][destination];
28+
}
29+
}
30+
}
31+
for (int source = 1; source <= numberofvertices; source++)
32+
System.out.print("\t" + source);
33+
System.out.println();
34+
for (int source = 1; source <= numberofvertices; source++) {
35+
System.out.print(source + "\t");
36+
for (int destination = 1; destination <= numberofvertices; destination++) {
37+
System.out.print(distancematrix[source][destination] + "\t");
38+
}
39+
System.out.println();
40+
}
41+
}
42+
43+
public static void main(String[] arg) {
44+
int adjacency_matrix[][];
45+
int numberofvertices;
46+
Scanner sc = new Scanner(System.in);
47+
System.out.println("Enter the number of vertices");
48+
numberofvertices = sc.nextInt();
49+
adjacency_matrix = new int[numberofvertices + 1][numberofvertices + 1];
50+
System.out.println("Enter the Weighted Matrix for the graph");
51+
for (int source = 1; source <= numberofvertices; source++) {
52+
for (int destination = 1; destination <= numberofvertices; destination++) {
53+
adjacency_matrix[source][destination] = sc.nextInt();
54+
if (source == destination) {
55+
adjacency_matrix[source][destination] = 0;
56+
continue;
57+
}
58+
if (adjacency_matrix[source][destination] == 0) {
59+
adjacency_matrix[source][destination] = INFINITY;
60+
}
61+
}
62+
}
63+
System.out.println("The Transitive Closure of the Graph");
64+
FloydWarshall floydwarshall = new FloydWarshall(numberofvertices);
65+
floydwarshall.floydwarshall(adjacency_matrix);
66+
System.out.println("Ishan Gupta - 19BCE7467");
67+
}
68+
}

‎KnapSack/FractionalKnapsack.java‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package com.ishan.daa;
2+
3+
import java.util.Arrays;
4+
import java.util.Comparator;
5+
import java.util.Scanner;
6+
7+
class FractionalKnapSack {
8+
private static double getMaxValue(int[] wt, int[] val, int capacity) {
9+
ItemValue[] iVal = new ItemValue[wt.length];
10+
11+
for (int i = 0; i < wt.length; i++) {
12+
iVal[i] = new ItemValue(wt[i], val[i], i);
13+
}
14+
Arrays.sort(iVal, new Comparator<ItemValue>() {
15+
@Override
16+
public int compare(ItemValue o1, ItemValue o2) {
17+
return o2.cost.compareTo(o1.cost);
18+
}
19+
});
20+
21+
double totalValue = 0d;
22+
23+
for (ItemValue i : iVal) {
24+
25+
int curWt = (int) i.wt;
26+
int curVal = (int) i.val;
27+
28+
if (capacity - curWt >= 0) {
29+
capacity = capacity - curWt;
30+
totalValue += curVal;
31+
} else {
32+
double fraction = ((double) capacity / (double) curWt);
33+
totalValue += (curVal * fraction);
34+
capacity = (int) (capacity - (curWt * fraction));
35+
break;
36+
}
37+
}
38+
39+
return totalValue;
40+
}
41+
42+
static class ItemValue {
43+
Double cost;
44+
double wt, val, ind;
45+
46+
public ItemValue(int wt, int val, int ind) {
47+
this.wt = wt;
48+
this.val = val;
49+
this.ind = ind;
50+
cost = new Double((double) val / (double) wt);
51+
}
52+
}
53+
54+
public static void main(String[] args) {
55+
Scanner sc = new Scanner(System.in);
56+
System.out.println("Enter the number of objects");
57+
int n = sc.nextInt();
58+
System.out.println("Enter the weights");
59+
int[] wt = new int[n];
60+
for (int i = 0; i < n; i++) {
61+
wt[i] = sc.nextInt();
62+
}
63+
System.out.println("Enter the weights");
64+
int[] val = new int[n];
65+
for (int i = 0; i < n; i++) {
66+
val[i] = sc.nextInt();
67+
}
68+
System.out.println("Enter the capacity");
69+
int capacity = sc.nextInt();
70+
double maxValue = getMaxValue(wt, val, capacity);
71+
System.out.println("Maximum value we can obtain = " + maxValue);
72+
System.out.println("Ishan Gupta - 19BCE7467");
73+
}
74+
}

‎KnapSack/KnapSack.java‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package com.ishan.daa;
2+
3+
import java.util.Scanner;
4+
5+
public class KnapSack {
6+
static int max(int a, int b) {
7+
return (a > b) ? a : b;
8+
}
9+
static int knapSack(int W, int wt[], int val[], int n) {
10+
if (n == 0 || W == 0)
11+
return 0;
12+
if (wt[n - 1] > W)
13+
return knapSack(W, wt, val, n - 1);
14+
else
15+
return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));
16+
}
17+
public static void main(String args[]) {
18+
Scanner sc = new Scanner(System.in);
19+
System.out.print("Number of items : ");
20+
int n = sc.nextInt();
21+
int val[] = new int[n];
22+
System.out.println("Input the values : ");
23+
for(int i=0;i<n;i++){
24+
val[i] = sc.nextInt();
25+
}
26+
System.out.println("Input the weight : ");
27+
int wt[] = new int[n];
28+
for (int i = 0; i < n; i++) {
29+
wt[i] = sc.nextInt();
30+
}
31+
System.out.print("Enter the maximum weight that can be carried : ");
32+
int W = sc.nextInt();
33+
System.out.println("The maximum value is : " + knapSack(W, wt, val, n));
34+
System.out.println("IshanGupta-19BCE7467");
35+
}
36+
}

‎Maximum Flow/MaximumFlow.java‎

Lines changed: 210 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,210 @@
1+
package com.ishan.daa;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashMap;
5+
import java.util.LinkedList;
6+
import java.util.Scanner;
7+
8+
public class MaximumFlow {
9+
public static class DirectedGraph {
10+
private HashMap<Object, Node> nodes = new HashMap<Object, Node>();
11+
private LinkedList<Edge> edges = new LinkedList<Edge>();
12+
13+
void addEdge(Object startNodeID, Object endNodeID, int capacity) {
14+
Node startNode;
15+
Node endNode;
16+
if (!this.nodes.containsKey(startNodeID)) {
17+
startNode = new Node();
18+
this.nodes.put(startNodeID, startNode);
19+
} else {
20+
startNode = this.nodes.get(startNodeID);
21+
}
22+
if (!this.nodes.containsKey(endNodeID)) {
23+
endNode = new Node();
24+
this.nodes.put(endNodeID, endNode);
25+
} else {
26+
endNode = this.nodes.get(endNodeID);
27+
}
28+
Edge edge = new Edge(startNodeID, endNodeID, capacity);
29+
startNode.addEdge(edge);
30+
endNode.addEdge(edge);
31+
this.edges.add(edge);
32+
}
33+
34+
Node getNode(Object nodeID) {
35+
return this.nodes.get(nodeID);
36+
}
37+
38+
LinkedList<Edge> getEdges() {
39+
return this.edges;
40+
}
41+
}
42+
43+
public static class Edge {
44+
private final Object target;
45+
private final Object start;
46+
private final int capacity;
47+
48+
Edge(Object start, Object target, int capacity) {
49+
this.capacity = capacity;
50+
this.target = target;
51+
this.start = start;
52+
}
53+
54+
Object getTarget() {
55+
return target;
56+
}
57+
58+
Object getStart() {
59+
return start;
60+
}
61+
62+
int getCapacity() {
63+
return capacity;
64+
}
65+
66+
@Override
67+
public String toString() {
68+
return this.start + "->" + this.target + "(" + this.capacity + ")";
69+
}
70+
}
71+
72+
public static class Node {
73+
private ArrayList<Edge> edges = new ArrayList<Edge>();
74+
75+
void addEdge(Edge edge) {
76+
this.edges.add(edge);
77+
}
78+
79+
Edge getEdge(int number) {
80+
if (this.edges.size() <= number) {
81+
return null;
82+
} else {
83+
return this.edges.get(number);
84+
}
85+
}
86+
87+
int getOutLeadingOrder() {
88+
return this.edges.size();
89+
}
90+
}
91+
92+
public static void main(String[] args) {
93+
Scanner sc = new Scanner(System.in);
94+
System.out.println("Enter the Source");
95+
int source = sc.nextInt();
96+
System.out.println("Enter the Sink");
97+
int sink = sc.nextInt();
98+
System.out.println("Enter the number of edges");
99+
int edge = sc.nextInt();
100+
DirectedGraph g = new DirectedGraph();
101+
for (int i = 0; i < edge; i++) {
102+
System.out.println("Enter the StartNode");
103+
int s = sc.nextInt();
104+
System.out.println("Enter the EndNode");
105+
int e = sc.nextInt();
106+
System.out.println("Enter the Capacity");
107+
int c = sc.nextInt();
108+
g.addEdge(s, e, c);
109+
}
110+
111+
HashMap<Edge, Integer> flow = getMaxFlow(g, source, sink);
112+
System.out.println("The Max Flow is" + getFlowSize(flow, g, source));
113+
System.out.println("Ishan Gupta - 19BCE7467");
114+
}
115+
116+
static HashMap<Edge, Integer> getMaxFlow(DirectedGraph g, Object source, Object sink) {
117+
LinkedList<Edge> path;
118+
HashMap<Edge, Integer> flow = new HashMap<Edge, Integer>();
119+
for (Edge e : g.getEdges()) {
120+
flow.put(e, 0);
121+
}
122+
while ((path = bfs(g, source, sink, flow)) != null) {
123+
int minCapacity = Integer.MAX_VALUE;
124+
Object lastNode = source;
125+
for (Edge edge : path) {
126+
int c;
127+
if (edge.getStart().equals(lastNode)) {
128+
c = edge.getCapacity() - flow.get(edge);
129+
lastNode = edge.getTarget();
130+
} else {
131+
c = flow.get(edge);
132+
lastNode = edge.getStart();
133+
}
134+
if (c < minCapacity) {
135+
minCapacity = c;
136+
}
137+
}
138+
lastNode = source;
139+
for (Edge edge : path) {
140+
if (edge.getStart().equals(lastNode)) {
141+
flow.put(edge, flow.get(edge) + minCapacity);
142+
lastNode = edge.getTarget();
143+
} else {
144+
flow.put(edge, flow.get(edge) - minCapacity);
145+
lastNode = edge.getStart();
146+
}
147+
}
148+
}
149+
return flow;
150+
}
151+
152+
static int getFlowSize(HashMap<Edge, Integer> flow, DirectedGraph g, Object source) {
153+
int maximumFlow = 0;
154+
Node sourceNode = g.getNode(source);
155+
for (int i = 0; i < sourceNode.getOutLeadingOrder(); i++) {
156+
maximumFlow += flow.get(sourceNode.getEdge(i));
157+
}
158+
return maximumFlow;
159+
}
160+
161+
static LinkedList<Edge> bfs(DirectedGraph g, Object start, Object target, HashMap<Edge, Integer> flow) {
162+
HashMap<Object, Edge> parent = new HashMap<Object, Edge>();
163+
LinkedList<Object> fringe = new LinkedList<Object>();
164+
parent.put(start, null);
165+
fringe.add(start);
166+
all:
167+
while (!fringe.isEmpty()) {
168+
LinkedList<Object> newFringe = new LinkedList<Object>();
169+
for (Object nodeID : fringe) {
170+
Node node = g.getNode(nodeID);
171+
for (int i = 0; i < node.getOutLeadingOrder(); i++) {
172+
Edge e = node.getEdge(i);
173+
if (e.getStart().equals(nodeID)
174+
&& !parent.containsKey(e.getTarget())
175+
&& flow.get(e) < e.getCapacity()) {
176+
parent.put(e.getTarget(), e);
177+
if (e.getTarget().equals(target)) {
178+
break all;
179+
}
180+
newFringe.add(e.getTarget());
181+
} else if (e.getTarget().equals(nodeID)
182+
&& !parent.containsKey(e.getStart())
183+
&& flow.get(e) > 0) {
184+
parent.put(e.getStart(), e);
185+
if (e.getStart().equals(target)) {
186+
break all;
187+
}
188+
newFringe.add(e.getStart());
189+
}
190+
}
191+
}
192+
fringe = newFringe;
193+
}
194+
if (fringe.isEmpty()) {
195+
return null;
196+
}
197+
Object node = target;
198+
LinkedList<Edge> path = new LinkedList<Edge>();
199+
while (!node.equals(start)) {
200+
Edge e = parent.get(node);
201+
path.addFirst(e);
202+
if (e.getStart().equals(node)) {
203+
node = e.getTarget();
204+
} else {
205+
node = e.getStart();
206+
}
207+
}
208+
return path;
209+
}
210+
}

0 commit comments

Comments
 (0)