Итак, вот простой пример того, что я имею в виду.Посмотрите, как долго это выполняется - намного больше времени для инициализации, но обратный процесс идет мгновенно и только один
package graph.nodes.simple;
import java.util.ArrayList;
public class GArrayListGraph extends ArrayList<GArrayListNode> {
/**
*
*/
private static final long serialVersionUID = 2493196722065921126L;
boolean calculated = false;
public GArrayListNode addNode(Object e) {
GArrayListNode ret = new GArrayListNode(e);
super.add(ret);
return ret ;
}
public void addEdge(GArrayListNode a, GArrayListNode b) {
a.neighbours.add(b);
}
public void printall() {
System.out.println("GArrayListGraph");
for (GArrayListNode node : this) {
System.out.println(node.toString());
}
}
public void reverce() {
if (!calculated) {
for (GArrayListNode node : this) {
for (GArrayListNode neighbour : node.neighbours) {
neighbour.neighboursReverse.add(node);
}
}
this.calculated = true;
}
// swap neighbours and neighboursReverse
for (GArrayListNode node : this) {
ArrayList<GArrayListNode> temp = node.neighbours;
node.neighbours = node.neighboursReverse;
node.neighboursReverse = temp;
}
}
}
package graph.nodes.simple;
import java.util.ArrayList;
import java.util.Random;
import java.util.Timer;
import java.util.TimerTask;
public class GArrayListNode {
Object val;
ArrayList<GArrayListNode> neighbours;
ArrayList<GArrayListNode> neighboursReverse;
public GArrayListNode(Object val) {
this.val = val;
this.neighbours = new ArrayList<GArrayListNode>();
this.neighboursReverse = new ArrayList<GArrayListNode>();
}
@Override
public String toString() {
return val.toString() + " : " + this.toStringChildren();
}
public String toStringChildren() {
StringBuilder sb = new StringBuilder();
for (GArrayListNode node : neighbours) {
sb.append(node.val).append(',');
}
return sb.toString();
}
public static void main(String[] args) {
GArrayListGraph g = new GArrayListGraph();
GArrayListNode n10 = g.addNode(10);
GArrayListNode n11 = g.addNode(11);
GArrayListNode n12 = g.addNode(12);
GArrayListNode n13 = g.addNode(13);
GArrayListNode n14 = g.addNode(14);
g.addEdge(n10, n11);
g.addEdge(n11, n12);
g.addEdge(n10, n12);
g.addEdge(n12, n13);
g.addEdge(n12, n14);
g.addEdge(n14, n10);
g.printall();
g.reverce();
g.printall();
g.reverce();
g.printall();
System.out.println("see its the same, now time performance test");
int nodes = 1000 * 1000 * 10;
for (int i = 0; i < nodes; i++) {
g.addNode(i);
}
int edges = 1000 * 10;
Random r = new Random();
for (int i = 0; i < nodes; i++) {
int from = r.nextInt(nodes);
int to = r.nextInt(nodes);
g.addEdge(g.get(from), g.get(to));
}
long startTime = System.currentTimeMillis();
System.out.println("start" );
g.reverce();
long elapsed = System.currentTimeMillis() - startTime;
System.out.println("elapsed " + elapsed);
}
}