-
Notifications
You must be signed in to change notification settings - Fork 0
/
Graph.java
73 lines (66 loc) · 1.72 KB
/
Graph.java
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
import java.util.*;
import java.io.*;
/**
* The graph on which the algorithm runs.
* An object of this class is created and populated by GraphReader.readGraph().
*
* @author Shalin Shah
* Email: shah.shalin@gmail.com
*/
public class Graph {
public Node [] sortedNodes;
public Node [] nodes;
/** Creates a new instance of Graph */
public Graph()
{
sortedNodes = new Node[Constants.NUMBER_NODES];
nodes = new Node[Constants.NUMBER_NODES];
for(int i=0; i<Constants.NUMBER_NODES; i++)
{
nodes[i] = new Node(i);
sortedNodes[i] = nodes[i];
}
}
/* Sort the list of vertices based on their degrees in non-increasing order */
public void sortList()
{
Arrays.sort(sortedNodes);
}
/* Get the array of sorted nodes. Used to create the initial greedy solution */
public Node [] getSortedNodes()
{
return sortedNodes;
}
/* Add an edge to this graph */
public void addEdge(int sv, int ev)
{
Node node = nodes[sv];
if(node == null)
{
node = new Node(sv);
nodes[sv] = node;
node.addEdge(ev);
sortedNodes[sv] = node;
node.degree++;
}
else
{
node.addEdge(ev);
node.degree++;
}
node = nodes[ev];
if(node == null)
{
node = new Node(ev);
nodes[ev] = node;
node.addEdge(sv);
sortedNodes[ev] = node;
node.degree++;
}
else
{
node.addEdge(sv);
node.degree++;
}
}
}