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
Appearance settings

Commit 779d9e0

Browse filesBrowse files
darecoderdarecoder
committed
Map updated
1 parent 95b633f commit 779d9e0
Copy full SHA for 779d9e0

File tree

3 files changed

+16
-51
lines changed
Filter options

3 files changed

+16
-51
lines changed

‎.idea/workspace.xml

Copy file name to clipboardExpand all lines: .idea/workspace.xml
+10-2Lines 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

Copy file name to clipboardExpand all lines: src/com/company/Lecture22/AdjMapGraph.java
-33Lines 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

Copy file name to clipboardExpand all lines: src/com/company/Lecture22/AdjMapWeightGraph.java
+6-16Lines 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 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.