Я пишу Java-программу, которая ищет и выводит циклы на графике. Я использую список смежности для хранения моего графа, списки которого хранятся как LinkedLists. Моя программа использует входные данные, отформатированные с первой строкой, в качестве числа узлов в графе и каждой последующей строки 2, которые образуют ребро, например ::100100
3
1 2
2 3
3 1
Моя проблема в том, что когда входные данные становятся очень большими (большой граф, который я использую, имеет 10 тыс. Узлов, и я не знаю, сколько ребер, файл равен 23 МБ только ребер), я получаю java.lang.StackOverflowError , но я не получаю никаких ошибок с небольшими входами. Мне интересно, было бы лучше использовать другую структуру данных для формирования моих списков смежности или есть какой-то метод, который я мог бы использовать, чтобы избежать этой ошибки, так как я бы предпочел не просто изменять настройку в моей локальной установке Java (потому что я должен быть уверен, что он будет работать на других компьютерах, на которых я не могу управлять настройками). Ниже мой код, класс Vertex, а затем мой основной класс. Спасибо за любую помощь, вы можете дать!
Vertex.java:
package algorithms311;
import java.util.*;
public class Vertex implements Comparable {
public int id;
public LinkedList adjVert = new LinkedList();
public String color = "white";
public int dTime;
public int fTime;
public int prev;
public Vertex(int idnum) {
id = idnum;
}
public int getId() {
return id;
}
public int compareTo(Object obj) {
Vertex vert = (Vertex) obj;
return id-vert.getId();
}
@Override public String toString(){
return "Vertex # " + id;
}
public void setColor(String newColor) {
color = newColor;
}
public String getColor() {
return color;
}
public void setDTime(int d) {
dTime = d;
}
public void setFTime(int f) {
fTime = f;
}
public int getDTime() {
return dTime;
}
public int getFTime() {
return fTime;
}
public void setPrev(int v) {
prev = v;
}
public int getPrev() {
return prev;
}
public LinkedList getAdjList() {
return adjVert;
}
public void addAdj(int a) { //adds a vertex id to this vertex's adj list
adjVert.add(a);
}
}
CS311.java:
package algorithms311;
import java.util.*;
import java.io.*;
public class CS311 {
public static final String GRAPH= "largegraph1";
public static int time = 0;
public static LinkedList[] DFS(Vertex[] v) {
LinkedList[] l = new LinkedList[2];
l[0] = new LinkedList();
l[1] = new LinkedList(); //initialize the array with blank lists, otherwise we get a nullpointerexception
for(int i = 0; i < v.length; i++) {
v[i].setColor("white");
v[i].setPrev(-1);
}
time = 0;
for(int i = 0; i < v.length; i++) {
if(v[i].getColor().equals("white")) {
l = DFSVisit(v, i, l);
}
}
return l;
}
public static LinkedList[] DFSVisit(Vertex[] v, int i, LinkedList[] l) { //params are a vertex of nodes and the node id you want to DFS from
LinkedList[] VOandBE = new LinkedList[2]; //two lists: visit orders and back edges
VOandBE[0] = l[0]; // l[0] is visit Order, a linked list of ints
VOandBE[1] = l[1]; // l[1] is back Edges, a linked list of arrays[2] of ints
VOandBE[0].add(v[i].getId());
v[i].setColor("gray"); //color[vertex i] <- GRAY
time++; //time <- time+1
v[i].setDTime(time); //d[vertex i] <- time
LinkedList adjList = v[i].getAdjList(); // adjList for the current vertex
for(int j = 0; j < adjList.size(); j++) { //for each v in adj[vertex i]
if(v[(Integer)adjList.get(j)].getColor().equals("gray") && v[i].getPrev() != v[(Integer)adjList.get(j)].getId()) { // if color[v] = gray and Predecessor[u] != v do
int[] edge = new int[2]; //pair of vertices
edge[0] = i; //from u
edge[1] = (Integer)adjList.get(j); //to v
VOandBE[1].add(edge);
}
if(v[(Integer)adjList.get(j)].getColor().equals("white")) { //do if color[v] = WHITE
v[(Integer)adjList.get(j)].setPrev(i); //then "pi"[v] <- vertex i
DFSVisit(v, (Integer)adjList.get(j), VOandBE); //DFS-Visit(v)
}
}
VOandBE[0].add(v[i].getId());
v[i].setColor("black");
time++;
v[i].setFTime(time);
return VOandBE;
}
public static void main(String[] args) {
try {
// --Read First Line of Input File
// --Find Number of Vertices
FileReader file1 = new FileReader("W:\\Documents\\NetBeansProjects\\algorithms311\\src\\algorithms311\\" + GRAPH);
BufferedReader bReaderNumEdges = new BufferedReader(file1);
String numVertS = bReaderNumEdges.readLine();
int numVert = Integer.parseInt(numVertS);
System.out.println(numVert + " vertices");
// --Make Vertices
Vertex vertex[] = new Vertex[numVert];
for(int k = 0; k <= numVert - 1; k++) {
vertex[k] = new Vertex(k);
}
// --Adj Lists
FileReader file2 = new FileReader("W:\\Documents\\NetBeansProjects\\algorithms311\\src\\algorithms311\\" + GRAPH);
BufferedReader bReaderEdges = new BufferedReader(file2);
bReaderEdges.readLine(); //skip first line, that's how many vertices there are
String edge;
while((edge = bReaderEdges.readLine()) != null) {
StringTokenizer ST = new StringTokenizer(edge);
int vArr[] = new int[2];
for(int j = 0; ST.hasMoreTokens(); j++) {
vArr[j] = Integer.parseInt(ST.nextToken());
}
vertex[vArr[0]-1].addAdj(vArr[1]-1);
vertex[vArr[1]-1].addAdj(vArr[0]-1);
}
for(int i = 0; i < vertex.length; i++) {
System.out.println(vertex[i] + ", adj nodes: " + vertex[i].getAdjList());
}
LinkedList[] l = new LinkedList[2];
l = DFS(vertex);
System.out.println("");
System.out.println("Visited Nodes: " + l[0]);
System.out.println("");
System.out.print("Back Edges: ");
for(int i = 0; i < l[1].size(); i++) {
int[] q = (int[])(l[1].get(i));
System.out.println("[" + q[0] + "," + q[1] + "] ");
}
for(int i = 0; i < l[1].size(); i++) { //iterate through the list of back edges
int[] q = (int[])(l[1].get(i)); // q = pair of vertices that make up a back edge
int u = q[0]; // edge (u,v)
int v = q[1];
LinkedList cycle = new LinkedList();
if(l[0].indexOf(u) < l[0].indexOf(v)) { //check if u is before v
for(int z = l[0].indexOf(u); z <= l[0].indexOf(v); z++) { //if it is, look for u first; from u to v
cycle.add(l[0].get(z));
}
}
else if(l[0].indexOf(v) < l[0].indexOf(u)) {
for(int z = l[0].indexOf(v); z <= l[0].indexOf(u); z++) { //if it is, look for u first; from u to v
cycle.add(l[0].get(z));
}
}
System.out.println("");
System.out.println("Cycle detected! : " + cycle);
if((cycle.size() & 1) != 0) {
System.out.println("Cycle is odd, graph is not 2-colorable!");
}
else {
System.out.println("Cycle is even, we're okay!");
}
}
}
catch (IOException e) {
System.out.println("AHHHH");
e.printStackTrace();
}
}
}