Skip to content

Commit 779d9e0

Browse files
darecoderdarecoder
committed
Map updated
1 parent 95b633f commit 779d9e0

File tree

3 files changed

+16
-51
lines changed

3 files changed

+16
-51
lines changed

‎.idea/workspace.xml

Lines changed: 10 additions & 2 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/com/company/Lecture22/AdjMapGraph.java

Lines changed: 0 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,6 @@
33
import java.util.*;
44

55
public class AdjMapGraph<E> {
6-
76
private Map<E, Vertex> vertices = new HashMap<E, Vertex>();
87

98
public void addVertex(E value){
@@ -15,83 +14,51 @@ public void addVertex(E value){
1514
public void addEdge(E first, E second){
1615
Vertex f = vertices.get(first);
1716
Vertex s = vertices.get(second);
18-
1917
if(f != null && s != null && f != s){ //f comparing to s to deny self loops
2018
f.neighbours.put(second, s);
2119
s.neighbours.put(first, f);
22-
2320
}
2421
}
2522

2623
public void removeEdge(E first, E second){
2724
Vertex f = vertices.get(first);
2825
Vertex s = vertices.get(second);
29-
3026
if(f != null && s != null && f != s){ //f comparing to s to deny self loops
3127
f.neighbours.remove(second);
3228
s.neighbours.remove(first);
33-
3429
}
3530
}
3631

3732
private Map<Vertex, Vertex> generateParents(){
3833
Map<Vertex,Vertex> parents = new HashMap<Vertex, Vertex>();
39-
4034
for(Vertex vertex : vertices.values()){
4135
parents.put(vertex, null);
4236
}
43-
4437
return parents;
4538
}
4639

4740
private Vertex find(Vertex vertex, Map<Vertex, Vertex> parents){
4841
while (parents.get(vertex) != null){
4942
vertex = parents.get(vertex);
5043
}
51-
5244
return vertex;
5345
}
5446

5547
private boolean Union(Vertex first,Vertex second, Map<Vertex, Vertex> parents){
5648
first = find(first, parents);
5749
second = find(second, parents);
58-
5950
if(first != second){
6051
parents.put(first, second);
6152
return true;
6253
}
63-
6454
return false;
6555
}
6656

6757
private class Vertex{
6858
E value;
6959
Map<E, Vertex> neighbours = new HashMap<E, Vertex>();
70-
7160
public Vertex(E value) {
7261
this.value = value;
7362
}
7463
}
75-
76-
public void DFT(E value){
77-
Vertex v = vertices.get(value);
78-
79-
Stack<Vertex> stack = new Stack<Vertex>();
80-
Set<Vertex> set= new HashSet<Vertex>();
81-
82-
set.add(v);
83-
stack.push(v);
84-
85-
while (!stack.empty()){
86-
Vertex top = stack.pop();
87-
System.out.print(top.value + " ");
88-
89-
for (Vertex vertex : top.neighbours.values()){
90-
if(!set.contains(vertex)){
91-
stack.push(vertex);
92-
set.add(vertex);
93-
}
94-
}
95-
}
96-
}
9764
}

‎src/com/company/Lecture22/AdjMapWeightGraph.java

Lines changed: 6 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,17 @@
11
package com.company.Lecture22;
22

33
import java.util.*;
4-
54
import static java.util.Comparator.*;
65

76
public class AdjMapWeightGraph<E> {
8-
9-
private Map<E, Vertex> vertices = new HashMap<E, Vertex>();
7+
private Map<E, Vertex> vertices = new HashMap<>();
108

119
private class Vertex{
1210
E value;
13-
Map<Vertex, Integer> neighbours = new HashMap<Vertex, Integer>();
14-
11+
Map<Vertex, Integer> neighbours = new HashMap<>();
1512
public Vertex(E value) {
1613
this.value = value;
1714
}
18-
1915
public void addNeighbour(Vertex vertex, Integer weight){
2016
neighbours.put(vertex,weight);
2117
}
@@ -25,7 +21,6 @@ private class Edge{
2521
private Vertex start;
2622
private Vertex end;
2723
private Integer weight;
28-
2924
public Edge(Vertex start, Vertex end, Integer weight) {
3025
this.start = start;
3126
this.end = end;
@@ -69,7 +64,6 @@ public int prims(){
6964
Set<Vertex> visited = new HashSet<Vertex>();
7065

7166
PriorityQueue<Edge> queue = new PriorityQueue<Edge>(comparingInt(o -> o.weight));
72-
7367
visited.add(start);
7468
for (Vertex end : start.neighbours.keySet()){
7569
int weight = start.neighbours.get(end);
@@ -87,7 +81,6 @@ public int prims(){
8781
if (!visited.contains(temp_e)){
8882
int weight = temp_s.neighbours.get(temp_e);
8983
queue.add(new Edge(temp_s, temp_e, weight));
90-
9184
}
9285
}
9386
}
@@ -118,25 +111,21 @@ public void removeEdge(E first, E second){
118111
if(f != null && s != null && f != s){ //f comparing to s to deny self loops
119112
f.neighbours.remove(second);
120113
s.neighbours.remove(first);
121-
122114
}
123115
}
124116

125117
private Map<Vertex, Vertex> generateParents(){
126118
Map<Vertex,Vertex> parents = new HashMap<Vertex, Vertex>();
127-
128119
for(Vertex vertex : vertices.values()){
129120
parents.put(vertex, null);
130121
}
131-
132122
return parents;
133123
}
134124

135125
private Vertex find(Vertex vertex, Map<Vertex, Vertex> parents){
136126
while (parents.get(vertex) != null){
137127
vertex = parents.get(vertex);
138128
}
139-
140129
return vertex;
141130
}
142131

@@ -148,7 +137,6 @@ private boolean Union(Vertex first,Vertex second, Map<Vertex, Vertex> parents){
148137
parents.put(first, second);
149138
return true;
150139
}
151-
152140
return false;
153141
}
154142

@@ -229,8 +217,10 @@ public void dijkstra(E source) {
229217
if (map.containsKey(padosi.value)) {
230218
DjPair pair = map.get(padosi.value);
231219
int oldcost = pair.cost;
232-
/* source se current vertex tak ka cost + current vertex se padosi tak jaane ka cost */
233-
int newcost = current.cost + vertices.get(current.endVertex).neighbours.get(padosi);
220+
/* source se current vertex tak ka cost +
221+
current vertex se padosi tak jaane ka cost */
222+
int newcost = current.cost +
223+
vertices.get(current.endVertex).neighbours.get(padosi);
234224
if (newcost < oldcost) {
235225
/* Heap se pichla cost vala pair remove kar
236226
do kyunki naya cost jaada chhota hai ab */

0 commit comments

Comments
 (0)