-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathMatrixGraph.java
More file actions
106 lines (88 loc) · 3.13 KB
/
MatrixGraph.java
File metadata and controls
106 lines (88 loc) · 3.13 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
/**
* Author: Kevin Richardson <[email protected]>
* Date: 2011-Nov-28
* Time: 5:50 PM EST
*
* Contains generic methods for operating upon an unweighted graph's table.
* This class utilizes matrices to store its connections.
*/
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class MatrixGraph {
// Contains the direct connections in the graph. If a direct connection exists between 0->1,
// table[0][1] = 1..
// If a direct connection between the two does not exist, table[0][1] = -1.
int[][] table;
// Tracks which nodes of this graph have been visited.
boolean[] visited;
// Used by the constructor to read in the graph's information file.
Scanner fileScanner;
// Used to store an examined file line and its components.
String line;
String[] pieces;
// Constructs a graph out of the information in inputFile.
public MatrixGraph(String inputFile)
{
try
{
fileScanner = new Scanner(new File(inputFile));
}
catch(FileNotFoundException e)
{
System.out.println("The specified file was not found.");
System.exit(-1);
}
// Get the number of nodes and edges from the first line.
line = fileScanner.nextLine();
pieces = line.split(" ");
int numNodes = Integer.parseInt(pieces[0]);
int numEdges = Integer.parseInt(pieces[1]);
// Create an adjacency matrix of the appropriate size (numNodes x numNodes).
table = new int[numNodes][numNodes];
// We will store a (currently) nonexistent connection as -1 and connections between the same
// node as 0.
for(int i = 0; i < table.length; i++)
{
for(int j = 0; j < table[i].length; j++)
{
if(i == j)
{
table[i][j] = 0;
}
else
{
table[i][j] = -1;
}
}
}
// Run through the connections and add them to the graph of connections.
for(int i = 0; i < numEdges; i++)
{
line = fileScanner.nextLine();
pieces = line.split(" ");
int origin = Integer.parseInt(pieces[0]);
int destination = Integer.parseInt(pieces[1]);
table[origin][destination] = 1;
table[destination][origin] = 1;
}
// Create an array to track which nodes have been visited by the algorithm operating upon this graph.
visited = new boolean[numNodes];
}
// Prints out the graph's table.
public String toString()
{
String toReturn = "";
for(int i = 0; i < table.length; i++)
{
for(int j = 0; j < table[i].length; j++)
{
if(table[i][j] != Integer.MAX_VALUE)
{
toReturn += i + " --> " + j + ": " + table[i][j] + "\n";
}
}
}
return toReturn;
}
}