Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 3cbd399

Browse files
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
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)

AltStyle によって変換されたページ (->オリジナル) /