in src/main/java/com/twitter/sbf/graph/BipartiteGraph.java [110:206]
public BipartiteGraph(SimpleIterator<String> lines) {
Optional<String> lineOpt;
lineOpt = lines.next();
if (!lineOpt.isPresent()) {
throw new RuntimeException("No lines in input!");
} else {
String[] tokens = lineOpt.get().trim().split("\\s+");
assert tokens.length == 3;
this.numLeftVertices = Integer.parseInt(tokens[0]);
this.numRightVertices = Integer.parseInt(tokens[1]);
//this is the number of vertices we expect there to be in the graph
//we will ensure that the number of edges in the string matches in this.
long expectedNumEdges = Long.parseLong(tokens[2]);
//initialize the adjacency lists for vertices on the left and the right
this.neighborsForLeft = new int[numLeftVertices][];
this.neighborsForRight = new int[numRightVertices][];
//temp variables and loop to read in graph data from the string
//checks incorporated to make sure input is valid and consistent
int nodeId = 0;
long edgesSoFar = 0;
while (true) {
lineOpt = lines.next();
if (!lineOpt.isPresent()) {
break;
} else {
int[] myNeighbors;
String line = lineOpt.get();
if (line.startsWith("%")) {
continue;
}
line = line.trim();
// Fields are separated by spaces
tokens = line.split("\\s+");
if (line.isEmpty()) { // vertices with no neighbor
myNeighbors = new int[0];
} else { // The rest are adjacency lists
int numNeighbors = tokens.length;
edgesSoFar += numNeighbors;
myNeighbors = new int[numNeighbors];
for (int i = 0; i < numNeighbors; i++) {
int nId = Integer.parseInt(tokens[i]) - 1; // 0-based indexing
if (nId < 0) {
throw new IllegalArgumentException(
String.format(
"Line %d: neighbor %d is less than 1 (all vertex ids are positive)\n",
nodeId + 1, nId + 1
)
);
} else if (nodeId < this.numLeftVertices && nId >= this.numRightVertices) {
throw new IllegalStateException(
String.format(
"Line %d: neighbor %d is more than the number of right side vertices %d\n",
nodeId + 1, nId + 1, this.numRightVertices
)
);
} else if (nodeId > this.numLeftVertices && nId >= this.numLeftVertices) {
throw new IllegalArgumentException(
String.format(
"Line %d: neighbor %d is more than the number of left side vertices %d\n",
nodeId + 1, nId + 1, this.numLeftVertices
)
);
}
myNeighbors[i] = nId;
}
Arrays.sort(myNeighbors);
}
if (nodeId < this.numLeftVertices) {
this.neighborsForLeft[nodeId++] = myNeighbors;
} else if (nodeId < this.numLeftVertices + this.numRightVertices) {
this.neighborsForRight[(nodeId++) - this.numLeftVertices] = myNeighbors;
} else {
int totalVertices = this.numLeftVertices + this.numRightVertices;
throw new IllegalArgumentException("Expected number of nodes " + totalVertices
+ " is inconsistent with number of adjacency lists");
}
if (nodeId % 100000 == 0) {
System.err.print("\rDone loading " + nodeId + " lines.");
}
}
}
if (edgesSoFar % 2 != 0) {
throw new RuntimeException("Got odd number of edges: "
+ edgesSoFar + ". Graph is not valid undirected graph.");
} else if (edgesSoFar != expectedNumEdges * 2) {
throw new RuntimeException("Expected " + 2 * expectedNumEdges
+ " (counting both directions), but got " + edgesSoFar + " edges.");
} else if (nodeId < this.numLeftVertices + this.numRightVertices) {
throw new IllegalArgumentException("Incomplete METIS data file!");
} else {
this.numEdges = expectedNumEdges;
}
}
this.areListsSortedAndSymmetric();
}