Dijkstra-Implementation/Graph.java at master · jrdonovan/Dijkstra-Implementation · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

import java.util.List;
import java.util.Map;
import java.util.HashMap;

public class Graph {

    private Map<String, Integer> edgeWeights;
    private Map<String, List<Vertex>> adjList;
    private Map<String, Vertex> vertices;

    public Graph() {
        this.edgeWeights = new HashMap<String, Integer>();
        this.adjList = new HashMap<String, List<Vertex>>();
        this.vertices = new HashMap<String, Vertex>();
    }

    public Map<String, Integer> getEdgeWeights() {
        return this.edgeWeights;
    }

    public Map<String, List<Vertex>> getAdjList() {
        return this.adjList;
    }

    public Map<String, Vertex> getVertices() {
        return vertices;
    }

    public void setEdge(Edge e) {
        Vertex v1 = e.getVertex1();
        Vertex v2 = e.getVertex2();
        if (!edgeWeights.containsKey(e.toString()))
            this.edgeWeights.put(e.toString(), e.getWeight());
        addVertex(v1);
        addVertex(v2);
        v1.setNeighbor(v2);
        addToAdjList(v1, v2);
    }

    public void addVertex(Vertex v) {
        if (!vertices.containsKey(v.toString()))
            vertices.put(v.toString(), v);
    }

    public void addToAdjList(Vertex v1, Vertex v2) {
        if (!adjList.containsKey(v1.toString())) {
            this.adjList.put(v1.toString(), v1.getNeighbors());
        }
        else {
            List<Vertex> value = this.adjList.get(v1.toString());
            value.add(v2);
        }

        if (!adjList.containsKey(v2.toString())) {
            this.adjList.put(v2.toString(), v2.getNeighbors());
        }
        else {
            List<Vertex> value = this.adjList.get(v2.toString());
            value.add(v1);
        }
    }

    public void removeFromAdjList(Vertex v1, Vertex v2) {
        if (adjList.containsKey(v1.toString())) {
            List<Vertex> neighborList = this.adjList.get(v1.toString());
            for (int i = 0; i < neighborList.size(); i++) {
                if (neighborList.get(i).getName().equals(v2.toString())) {
                    neighborList.remove(i);
                    break;
                }
            }
        }

        if (adjList.containsKey(v2.toString())) {
            List<Vertex> neighborList = this.adjList.get(v2.toString());
            for (int i = 0; i < neighborList.size(); i++) {
                if (neighborList.get(i).getName().equals(v1.toString())) {
                    neighborList.remove(i);
                    break;
                }
            }
        }
    }

    @Override
    public String toString() {
        String s = "";
        for (Map.Entry<String, List<Vertex>> entry : adjList.entrySet()) {
            String key = entry.getKey();
            List<Vertex> value = entry.getValue();
            s += key + ": ";
            for (Vertex v : value) {
                s += v.toString() + " ";
            }
            s += "\n";
        }
        return s;
    }
}