-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGraphComplex.java
More file actions
135 lines (117 loc) · 3.52 KB
/
GraphComplex.java
File metadata and controls
135 lines (117 loc) · 3.52 KB
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package ds;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
/**
* A representation of graph more efficient and easy to work with.
*
* @author shivam.maharshi
*/
public class GraphComplex {
private Map<Integer, Node> graph = new HashMap<Integer, Node>();
// Constructor of graph.
public GraphComplex(Map<Integer, List<Integer>> adjacencyMap) {
if (adjacencyMap != null && !adjacencyMap.isEmpty()) {
for (Entry<Integer, List<Integer>> entry : adjacencyMap.entrySet()) {
int id = entry.getKey();
Node node = new Node(id);
graph.put(id, node);
}
for (Entry<Integer, List<Integer>> entry : adjacencyMap.entrySet()) {
int nodeId = entry.getKey();
List<Integer> adjIdList = entry.getValue();
if (adjIdList != null) {
Node node = graph.get(nodeId);
for (int adjId : adjIdList) {
Node adjNode = graph.get(adjId);
if (node.getAdjNodes() == null) {
node.setAdjNodes(new ArrayList<Node>());
}
node.getAdjNodes().add(adjNode);
}
}
}
}
}
public int size() {
return this.graph.size();
}
public Node get(int i) {
return graph.get(i);
}
/*
* Specific functionalities.
*/
// Are two nodes connected.
public boolean isConnected(int id1, int id2) {
return getDistance(id1, id2) == -1 ? false : true;
}
// Get distance between two nodes.
public int getDistance(int id1, int id2) {
Node startNode = graph.get(id1);
return searchNodeBfs(startNode, id2);
}
// Using breadth first search for shortest distance.
private int searchNodeBfs(Node start, int id) {
int level = 0;
List<List<Node>> nodeLevelList = new ArrayList<List<Node>>();
ArrayList<Node> nodeList = new ArrayList<Node>();
nodeList.add(start);
nodeLevelList.add(nodeList);
while (true) {
level++;
nodeList = new ArrayList<>();
for (Node node : nodeLevelList.get(level - 1)) {
for (Node adjNode : node.getAdjNodes()) {
if (adjNode.getState() == State.UNVISITED) {
adjNode.setState(State.VISITED);
adjNode.setLevel(level);
if (adjNode.getId() == id) {
return level;
} else {
nodeList.add(adjNode);
}
}
}
}
nodeLevelList.add(nodeList);
}
}
// Get specific node.
public Node getNode(int id) {
return graph.get(id);
}
// Utility method.
public static List<Integer> getList(Integer... values) {
List<Integer> list = new ArrayList<Integer>();
for (Integer value : values) {
list.add(value);
}
return list;
}
// Utility method.
public static Map<Integer, List<Integer>> getTestData() {
Map<Integer, List<Integer>> adjacencyMap = new HashMap<Integer, List<Integer>>();
adjacencyMap.put(1, getList(2, 5));
adjacencyMap.put(2, getList(1, 3, 4, 5));
adjacencyMap.put(3, getList(2, 5, 6));
adjacencyMap.put(4, getList(2));
adjacencyMap.put(5, getList(1, 2, 3, 6, 7));
adjacencyMap.put(6, getList(3, 5, 8));
adjacencyMap.put(7, getList(5));
adjacencyMap.put(8, getList(6));
return adjacencyMap;
}
public static GraphComplex getPopulatedGraph() {
return new GraphComplex(getTestData());
}
public static void main(String[] args) {
GraphComplex graph = new GraphComplex(getTestData());
int id1 = 1, id2 = 8;
System.out.println("Distance between nodes : " + graph.getDistance(id1, id2));
// System.out.println("Are nodes connected : " + graph.isConnected(id1,
// id2));
}
}