1

私はアンドロイドプログラムを書いていますが、問題が発生しました。

私のプログラムは、グラフを作成し、それらに対していくつかの特定のアルゴリズム (Dijsktra、BelmanFord など) を実行し、グラフを SD カードに保存し、再度ロードするのに役立ちます。

問題:少し大きくて複雑なグラフを保存すると、stackoverflow エラーが発生します。

シリアライゼーション:

public void createExternalStoragePublicGraph(String filename) {
    File dir = Environment.getExternalStoragePublicDirectory("grapher");

    try {
        if (!dir.exists()) {
            dir.mkdirs();
        }
        File file = new File(dir, filename);
        FileOutputStream fileOutputStream = new FileOutputStream(file);
        ObjectOutputStream objectOutputStream = new ObjectOutputStream(fileOutputStream);
        objectOutputStream.writeObject(graphDrawerView.getGraph());
        objectOutputStream.close();

    } catch (IOException e) {
        Log.w("ExternalStorage", "Error Writing" + filename, e);
    }

}

逆シリアル化:

public Graph loadExternalStoragePublicGraph(String filename) {
    File file = new File(Environment.getExternalStoragePublicDirectory("grapher"), filename);
    Graph graph = null;

    try {

        FileInputStream fint = new FileInputStream(file);
        ObjectInputStream ois = new ObjectInputStream(fint);
        graph = (Graph) ois.readObject();
        ois.close();

    } catch (Exception e) {
        Log.e("Deserialization error:", e.getMessage());
        e.printStackTrace();
    }
    return graph;
}

グラフ クラス:

package com.cslqaai.grapher;

import android.util.Log;
import java.io.Serializable;
import java.util.LinkedList;

public class Graph implements Serializable {

    private String name;
    private boolean directed = false;
    private boolean weighted = false;
    private LinkedList<Vertex> vertexes = new LinkedList<Vertex>();
    private LinkedList<Edge> edges = new LinkedList<Edge>();

    // --------------------------------------------------------------------------------------------------------------------------------------
    public Graph(boolean weighted, boolean directed) {
        this.directed = directed;
        this.weighted = weighted;
    }

    // --------------------------------------------------------------------------------------------------------------------------------------
    public void add(AbstractGraphObject ago) {
        if (ago instanceof Vertex) {
            this.vertexes.add((Vertex) ago);
        } else if (ago instanceof Edge) {

            this.edges.add((Edge) ago);
        } else {
        }
    }

    // --------------------------------------------------------------------------------------------------------------------------------------
    public boolean isWeighted() {
        return this.weighted;
    }

    // --------------------------------------------------------------------------------------------------------------------------------------
    public boolean isDirected() {
        return this.directed;
    }

    // --------------------------------------------------------------------------------------------------------------------------------------\
    public LinkedList<Edge> getEdges() {
        return this.edges;
    }

    // --------------------------------------------------------------------------------------------------------------------------------------
    public LinkedList<Vertex> getVertexes() {
        return this.vertexes;
    }

    // --------------------------------------------------------------------------------------------------------------------------------------
    public void reset() {
        for (int i = 0; i < this.edges.size(); i++) {
            this.edges.get(i).setColorToDefault();
        }
    }

    // --------------------------------------------------------------------------------------------------------------------------------------
    void remove(AbstractGraphObject ago) {
        if (ago instanceof Vertex) {
            Log.d("Graph", "Remove Vertex from graph");
            this.vertexes.remove((Vertex) ago);
        } else if (ago instanceof Edge) {
            Log.d("Graph", "Remove Edge to graph");
            this.edges.remove((Edge) ago);
        }
    }
    // --------------------------------------------------------------------------------------------------------------------------------------

    public void setWeighted(boolean weighted) {
        this.weighted = weighted;
    }
    // --------------------------------------------------------------------------------------------------------------------------------------

    public void setDirected(boolean directed) {
        this.directed = directed;
    }
    // --------------------------------------------------------------------------------------------------------------------------------------

    public String getName() {
        return this.name;
    }
    // --------------------------------------------------------------------------------------------------------------------------------------

    public void setName(String name) {
        this.name = name;
    }
}
// ----------------------------------------------------------------------------------------------------------------------------------------

頂点クラス:

package com.cslqaai.grapher;
import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import android.graphics.Typeface;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

public class Vertex extends AbstractGraphObject {

public static final int RADIUS_SIZE = 20;
public static final int SURROUNDING_RADIUS_SIZE = 30;
private static Layer defaultVertexLayer = AbstractGraphObject.defaultLayer;
private static int no = 0;
private static Paint paint = new Paint(Paint.ANTI_ALIAS_FLAG);
private static Paint paintColored = new Paint(Paint.ANTI_ALIAS_FLAG);
private static Paint textPaint = new Paint(Paint.ANTI_ALIAS_FLAG);
private static Paint textBgPaint = new Paint(Paint.ANTI_ALIAS_FLAG);
private final int id;
private String name = null;
private Coord coord;
private Coord cachedCoord;
private ArrayList<Edge> edges = new ArrayList<Edge>();
private boolean colored = false;

// --------------------------------------------------------------------------------------------------------------------------------------
static {
    Vertex.paint.setColor(0xFF0FF5F5);
    Vertex.paintColored.setColor(Color.RED);
    Vertex.textPaint.setStyle(Paint.Style.FILL);
    Vertex.textPaint.setColor(Color.BLACK);
    Vertex.textPaint.setTextAlign(Paint.Align.CENTER);
    Vertex.textPaint.setTextSize(20);
    Vertex.textPaint.setTypeface(Typeface.create("Helvetica", Typeface.BOLD));
    Vertex.textBgPaint.setStyle(Paint.Style.FILL);
    Vertex.textBgPaint.setColor(0xFF0FF5F5);
}

// --------------------------------------------------------------------------------------------------------------------------------------
public Vertex(Coord coord) {
    super(Vertex.defaultVertexLayer);
    this.id = Vertex.no++;
    this.coord = coord;
    this.recalculate();
}

// --------------------------------------------------------------------------------------------------------------------------------------
public Vertex(int x, int y) {
    this(new Coord(x, y));
}

// --------------------------------------------------------------------------------------------------------------------------------------
@Override
public void recalculate() {
    this.cachedCoord = new Coord(Math.round((Vertex.baseX + this.coord.getX()) * Vertex.scaleFactor), Math.round((Vertex.baseY + this.coord.getY()) * Vertex.scaleFactor));
    this.onScreen = this.cachedCoord.getX() + Vertex.RADIUS_SIZE > 0 && this.cachedCoord.getY() + Vertex.RADIUS_SIZE > 0
            && this.cachedCoord.getX() - Vertex.RADIUS_SIZE < Vertex.screenWidth && this.cachedCoord.getY() - Vertex.RADIUS_SIZE < this.cachedCoord.getY();
}

// --------------------------------------------------------------------------------------------------------------------------------------
public Coord getCoord() {
    return this.coord;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public Coord getCachedCoord() {
    return this.cachedCoord;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public int getRadiusSize() {
    return Vertex.RADIUS_SIZE;
}

// --------------------------------------------------------------------------------------------------------------------------------------
@Override
public void draw(Canvas canvas) {
    this.recalculate();

    if (!this.onScreen) {
        return;
    }

    canvas.drawCircle(this.cachedCoord.getX(), this.cachedCoord.getY(), Vertex.RADIUS_SIZE * Vertex.scaleFactor, Vertex.paint);
    if (this.name != null) {
        float width = Vertex.textPaint.measureText(this.name) + 10;
        float height = Vertex.textPaint.getTextSize() + 5;
        canvas.drawRect(this.cachedCoord.getX() - width / 2, this.cachedCoord.getY() - height / 2, this.cachedCoord.getX() + width / 2, this.cachedCoord.getY() + height / 2, Vertex.textBgPaint);
        canvas.drawText(this.name, this.cachedCoord.getX(), this.cachedCoord.getY() + height * 0.25f, Vertex.textPaint);
    }
}
// --------------------------------------------------------------------------------------------------------------------------------------

private boolean searchingCoordOn(float radius, float pX, float pY) {
    return this.onScreen && ((Math.pow(pX - this.cachedCoord.getX(), 2) + Math.pow(pY - this.cachedCoord.getY(), 2)) < (Math.pow(radius * Vertex.scaleFactor, 2)));
}

// --------------------------------------------------------------------------------------------------------------------------------------
public boolean isOnCoord(float pX, float pY) {
    return this.searchingCoordOn(Vertex.RADIUS_SIZE, pX, pY);
}

// --------------------------------------------------------------------------------------------------------------------------------------
public boolean isInCoordSurroundings(float pX, float pY) {
    return this.searchingCoordOn(Vertex.SURROUNDING_RADIUS_SIZE, pX, pY);
}
// --------------------------------------------------------------------------------------------------------------------------------------

public void addEdge(Edge edge) {
    if (!this.edges.contains(edge)) {
        this.edges.add(edge);
    }
}

// --------------------------------------------------------------------------------------------------------------------------------------
public ArrayList<Edge> getEdges() {
    return this.edges;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public void removeEdge(Edge edge) {
    if (this.edges.contains(edge)) {
        this.edges.remove(edge);
    }
}

// --------------------------------------------------------------------------------------------------------------------------------------
public boolean hasEdge(Edge edge) {
    return this.edges.contains(edge);
}

// --------------------------------------------------------------------------------------------------------------------------------------
public static void setDefaultLayer(Layer layer) {
    Vertex.defaultVertexLayer = layer;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public static Layer getDefaultLayer() {
    return Vertex.defaultVertexLayer;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public static void remove(Vertex vertex) {
    Iterator<Edge> edges = vertex.getEdges().iterator();
    while (edges.hasNext()) {
        Edge e = edges.next();
        edges.remove();
        Edge.remove(e);
    }

    Vertex.defaultVertexLayer.remove(vertex);
    if (Vertex.graph != null) {
        Vertex.graph.remove(vertex);
    }
}

// --------------------------------------------------------------------------------------------------------------------------------------
public boolean hasName() {
    return this.name != null;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public void setName(String name) {
    this.name = name;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public String getName() {
    return this.name;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public int getId() {
    return this.id;
}
// --------------------------------------------------------------------------------------------------------------------------------------
}

エッジ クラス:

package com.cslqaai.grapher;

import android.graphics.*;
import java.util.ArrayList;
import java.util.LinkedList;

public class Edge extends AbstractGraphObject {

public static final float STROKE_WIDTH = 5f;
public static final float SENSOR_WIDTH = 50f;
public static final float SURROUNDING_SENSOR_WIDTH = 15f;
public static final float TRIANGLE_SIZE = 8f;
private static Paint paint = new Paint(Paint.ANTI_ALIAS_FLAG);
private static Paint paintColored = new Paint(Paint.ANTI_ALIAS_FLAG);
private static Paint textPaint = new Paint(Paint.ANTI_ALIAS_FLAG);
private static Paint textBgPaint = new Paint(Paint.ANTI_ALIAS_FLAG);
private static Layer defaultEdgeLayer = AbstractGraphObject.defaultLayer;
private static int no = 0;
private final int id;
private int weight = 1;
private Coord cachedSourceCoord;
private Coord cachedTargetCoord;
private Vertex sourceVertex;
private Vertex targetVertex;
private Coord weightCoord;
private boolean colored = false;

// --------------------------------------------------------------------------------------------------------------------------------------
static {
    Edge.paint.setColor(0xFFFFFFFF);
    Edge.paint.setStrokeWidth(Edge.STROKE_WIDTH * Edge.scaleFactor);
    Edge.paint.setStrokeCap(Paint.Cap.ROUND);
    Edge.paint.setStyle(Paint.Style.FILL_AND_STROKE);
    Edge.paintColored.setColor(0xFFFF0000);
    Edge.paintColored.setStrokeWidth(Edge.STROKE_WIDTH * Edge.scaleFactor);
    Edge.paintColored.setStrokeCap(Paint.Cap.ROUND);
    Edge.paintColored.setStyle(Paint.Style.FILL_AND_STROKE);
    Edge.textPaint.setStyle(Paint.Style.FILL);
    Edge.textPaint.setColor(Color.BLACK);
    Edge.textPaint.setTextAlign(Paint.Align.CENTER);
    Edge.textPaint.setTextSize(20);
    Edge.textPaint.setTypeface(Typeface.create("Helvetica", Typeface.BOLD));
    Edge.textBgPaint.setStyle(Paint.Style.FILL);
    Edge.textBgPaint.setColor(Color.WHITE);
}

// --------------------------------------------------------------------------------------------------------------------------------------
public Edge(Vertex sourceVertex, Vertex targetVertex) {
    super(Edge.defaultEdgeLayer);
    this.id = Edge.no++;
    this.sourceVertex = sourceVertex;
    this.targetVertex = targetVertex;
    this.sourceVertex.addEdge(this);
    this.targetVertex.addEdge(this);
    this.recalculate();
}

// --------------------------------------------------------------------------------------------------------------------------------------
public void recalculate() {
    this.cachedSourceCoord = new Coord(Math.round((Edge.baseX + this.sourceVertex.getCoord().getX()) * Edge.scaleFactor), Math.round((Edge.baseY + this.sourceVertex.getCoord().getY()) * Edge.scaleFactor));
    this.cachedTargetCoord = new Coord(Math.round((Edge.baseX + this.targetVertex.getCoord().getX()) * Edge.scaleFactor), Math.round((Edge.baseY + this.targetVertex.getCoord().getY()) * Edge.scaleFactor));

    Line line = new Line(this.cachedSourceCoord, this.cachedTargetCoord);
    this.weightCoord = line.getMiddle();

    this.onScreen = Edge.screenBottomLine.hasIntersection(line)
            || Edge.screenLeftLine.hasIntersection(line)
            || Edge.screenRightLine.hasIntersection(line)
            || Edge.screenTopLine.hasIntersection(line)
            || this.cachedSourceCoord.getX() > 0 && this.cachedSourceCoord.getX() < Edge.screenWidth && this.cachedSourceCoord.getY() > 0 && this.cachedSourceCoord.getY() < Edge.screenHeight
            || this.cachedTargetCoord.getX() > 0 && this.cachedTargetCoord.getX() < Edge.screenWidth && this.cachedTargetCoord.getY() > 0 && this.cachedTargetCoord.getY() < Edge.screenHeight;
}

// --------------------------------------------------------------------------------------------------------------------------------------
@Override
public void draw(Canvas canvas) {
    this.recalculate();

    if (!this.onScreen) {
        return;
    }

    canvas.drawLine(this.cachedSourceCoord.getX(), this.cachedSourceCoord.getY(), this.cachedTargetCoord.getX(), this.cachedTargetCoord.getY(), this.colored ? Edge.paintColored : Edge.paint);

    if (Edge.graph != null && Edge.graph.isDirected()) {
        Line line = new Line(this.cachedSourceCoord, this.cachedTargetCoord);
        Coord v = line.getVector();
        float t = (float) ((Vertex.RADIUS_SIZE + 5) / Math.sqrt(Math.pow(v.getX(), 2) + Math.pow(v.getY(), 2)));
        Coord t1 = new Coord((int) (this.cachedTargetCoord.getX() - t * v.getX()), (int) (this.cachedTargetCoord.getY() - t * v.getY()));
        if (!line.isOnLine(t1)) {
            t1 = new Coord((int) (this.cachedTargetCoord.getX() + t * v.getX()), (int) (this.cachedTargetCoord.getY() + t * v.getY()));
        }
        t = (float) ((Vertex.RADIUS_SIZE + 5 + Edge.TRIANGLE_SIZE) / Math.sqrt(Math.pow(v.getX(), 2) + Math.pow(v.getY(), 2)));
        Coord p = new Coord((int) (this.cachedTargetCoord.getX() - t * v.getX()), (int) (this.cachedTargetCoord.getY() - t * v.getY()));
        if (!line.isOnLine(p)) {
            p = new Coord((int) (this.cachedTargetCoord.getX() + t * v.getX()), (int) (this.cachedTargetCoord.getY() + t * v.getY()));
        }
        v = line.getNormalVector().getVector();
        t = (float) ((Edge.TRIANGLE_SIZE) / Math.sqrt(Math.pow(v.getX(), 2) + Math.pow(v.getY(), 2)));
        Coord t2 = new Coord((int) (p.getX() - t * v.getX()), (int) (p.getY() - t * v.getY()));
        Coord t3 = new Coord((int) (p.getX() + t * v.getX()), (int) (p.getY() + t * v.getY()));
        Path path = new Path();

        path.setFillType(Path.FillType.EVEN_ODD);
        path.moveTo(t1.getX(), t1.getY());
        path.lineTo(t2.getX(), t2.getY());
        path.lineTo(t3.getX(), t3.getY());
        path.lineTo(t1.getX(), t1.getY());
        path.close();

        canvas.drawPath(path, Edge.paint);
    }

    if (Edge.graph != null && Edge.graph.isWeighted()) {
        float width = Edge.textPaint.measureText(Integer.toString(this.weight)) + 10;
        float height = Edge.textPaint.getTextSize() + 5;
        canvas.drawRect(this.weightCoord.getX() - width / 2, this.weightCoord.getY() - height / 2, this.weightCoord.getX() + width / 2, this.weightCoord.getY() + height / 2, Edge.textBgPaint);
        canvas.drawText(Integer.toString(this.weight), this.weightCoord.getX(), this.weightCoord.getY() + height * 0.25f, Edge.textPaint);
    }
}

// --------------------------------------------------------------------------------------------------------------------------------------
private boolean searchingCoordOn(float distance, float pX, float pY) {
    Coord p = new Coord((int) pX, (int) pY);
    Coord v = (new Line(this.cachedSourceCoord, this.cachedTargetCoord)).getNormalVector().getVector();
    float t = (float) (distance / Math.sqrt(Math.pow(v.getX(), 2) + Math.pow(v.getY(), 2)));
    Coord c1 = new Coord((int) (this.cachedSourceCoord.getX() - t * v.getX()), (int) (this.cachedSourceCoord.getY() - t * v.getY()));
    Coord c2 = new Coord((int) (this.cachedSourceCoord.getX() + t * v.getX()), (int) (this.cachedSourceCoord.getY() + t * v.getY()));
    Coord c3 = new Coord((int) (this.cachedTargetCoord.getX() - t * v.getX()), (int) (this.cachedTargetCoord.getY() - t * v.getY()));
    Coord v1 = new Coord(c2.getX() - c1.getX(), c2.getY() - c1.getY());
    Coord v2 = new Coord(c3.getX() - c1.getX(), c3.getY() - c1.getY());
    v = Coord.minus(p, c1);

    return this.onScreen
            && 0 <= Coord.dotProduct(v, v1) && Coord.dotProduct(v, v1) <= Coord.dotProduct(v1, v1)
            && 0 <= Coord.dotProduct(v, v2) && Coord.dotProduct(v, v2) <= Coord.dotProduct(v2, v2);
}

// --------------------------------------------------------------------------------------------------------------------------------------
public boolean isOnCoord(float pX, float pY) {
    return this.searchingCoordOn(Edge.SENSOR_WIDTH / 2, pX, pY);
}

// --------------------------------------------------------------------------------------------------------------------------------------
public boolean isInCoordSurroundings(float pX, float pY) {
    return this.searchingCoordOn(Edge.SURROUNDING_SENSOR_WIDTH / 2, pX, pY);
}

// --------------------------------------------------------------------------------------------------------------------------------------
public Vertex getSourceVertex() {
    return this.sourceVertex;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public Vertex getTargetVertex() {
    return this.targetVertex;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public static void setDefaultLayer(Layer layer) {
    Edge.defaultEdgeLayer = layer;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public static Layer getDefaultLayer() {
    return Edge.defaultEdgeLayer;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public static void remove(Edge edge) {
    edge.getSourceVertex().removeEdge(edge);
    edge.getTargetVertex().removeEdge(edge);
    Edge.defaultEdgeLayer.remove(edge);
    if (Edge.graph != null) {
        Edge.graph.remove(edge);
    }
}

// --------------------------------------------------------------------------------------------------------------------------------------
public void setWeight(int weight) {
    this.weight = weight;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public int getWeight() {
    return this.weight;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public int getId() {
    return this.id;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public void setColored() {
    this.colored = true;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public void setColorToDefault() {
    this.colored = false;
}

// --------------------------------------------------------------------------------------------------------------------------------------
public static ArrayList<Edge> getEdgesBetween(Vertex v1, Vertex v2) {
    ArrayList<Edge> edges = v1.getEdges();
    ArrayList<Edge> edgesRet = new ArrayList<Edge>();
    for (Edge edge : edges) {
        if (v2.hasEdge(edge)) {
            edgesRet.add(edge);
        }
    }
    return edges;
}
// --------------------------------------------------------------------------------------------------------------------------------------
}

これは、「通常の」シリアライゼーションでは各エントリに対して別の writeObject(e) が再帰的に呼び出され、長いリストの場合は StackOverflowError が発生するためです。反復シリアライゼーションはこれを回避します。

これはstackoverflowで見つけました。私の問題は長いLinkedListに関連していると思います..

Graph オブジェクトを適切にシリアライズおよびデシリアライズする方法に関するアイデアやアドバイスはありますか?

前もって感謝します！

4

2 に答える 2

0

迅速な修正として、LinkedList リストの実装を ArrayList に置き換えてみることができます。あなたは十分な詳細を提供しませんでした (頂点とエッジの正確な例外と実装が役立つでしょう) が、あなたが引用したことは正しいかもしれません: 再帰呼び出しのためにメモリが不足しています。私は試しませんでしたが、ArrayList のデフォルトの Java シリアライゼーションはこの問題を回避します。

本当に良い解決策として、グラフ オブジェクトのシリアル化メソッドを再実装するか、テスト済みでメモリ効率の高いライブラリを使用することができます (例: kryo )。

この質問も参考になります。

于 2013-05-08T19:57:30.407 に答える