java - 基于矩阵元素和 jgrapht 库定义顶点和边

Question

我有一个代表网格的矩阵，由 0、1 和 2 组成。当网格上没有任何元素时为 0，当有可以移动的元素时为 1，当有不可移动的元素时为 2。

例如:

0 0 0 0 2 2 0 0 0 0 
0 0 1 1 2 2 1 1 1 0 
0 0 1 0 0 0 1 0 1 0 
0 0 1 0 0 0 1 1 1 0 
0 0 1 1 1 1 1 0 0 0 
0 0 0 0 1 0 1 0 0 0 
0 0 0 0 1 1 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0

我想把它变成一个有向图，每个1都是一个顶点，边是两个顶点之间的链接。为此，我想使用 jgrapht 库，并且我尝试使用他们的演示代码:

package org.jgrapht.demo;

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.generate.*;
import org.jgrapht.graph.*;
import org.jgrapht.traverse.*;


public final class CompleteGraphDemo
{


    static Graph<Object, DefaultEdge> completeGraph;

    //Number of vertices
    static int size = 10;



    public static void main(String [] args)
    {
        //Create the graph object; it is null at this point
        completeGraph = new SimpleGraph<Object, DefaultEdge>(DefaultEdge.class);

        //Create the CompleteGraphGenerator object
        CompleteGraphGenerator<Object, DefaultEdge> completeGenerator =
            new CompleteGraphGenerator<Object, DefaultEdge>(size);

        //Create the VertexFactory so the generator can create vertices
        VertexFactory<Object> vFactory =
            new ClassBasedVertexFactory<Object>(Object.class);

        //Use the CompleteGraphGenerator object to make completeGraph a
        //complete graph with [size] number of vertices
        completeGenerator.generateGraph(completeGraph, vFactory, null);

        //Now, replace all the vertices with sequential numbers so we can ID
        //them
        Set<Object> vertices = new HashSet<Object>();
        vertices.addAll(completeGraph.vertexSet());
        Integer counter = 0;
        for (Object vertex : vertices) {
            replaceVertex(vertex, (Object) counter++);
        }

        //Print out the graph to be sure it's really complete
        Iterator<Object> iter =
            new DepthFirstIterator<Object, DefaultEdge>(completeGraph);
        Object vertex;
        while (iter.hasNext()) {
            vertex = iter.next();
            System.out.println(
                "Vertex " + vertex.toString() + " is connected to: "
                + completeGraph.edgesOf(vertex).toString());
        }
    }

    public static boolean replaceVertex(Object oldVertex, Object newVertex)
    {
        if ((oldVertex == null) || (newVertex == null)) {
            return false;
        }
        Set<DefaultEdge> relatedEdges = completeGraph.edgesOf(oldVertex);
        completeGraph.addVertex(newVertex);

        Object sourceVertex;
        Object targetVertex;
        for (DefaultEdge e : relatedEdges) {
            sourceVertex = completeGraph.getEdgeSource(e);
            targetVertex = completeGraph.getEdgeTarget(e);
            if (sourceVertex.equals(oldVertex)
                && targetVertex.equals(oldVertex))
            {
                completeGraph.addEdge(newVertex, newVertex);
            } else {
                if (sourceVertex.equals(oldVertex)) {
                    completeGraph.addEdge(newVertex, targetVertex);
                } else {
                    completeGraph.addEdge(sourceVertex, newVertex);
                }
            }
        }
        completeGraph.removeVertex(oldVertex);
        return true;
    }
}

// End CompleteGraphDemo.java

但是，这段代码根据 size 声明的顶点数量创建一个随机有向图，而我需要添加矩阵的元素(1)作为顶点，然后使用程序生成有向图并返回循环数(在上面的矩阵中将有 3 个循环)。

我不知道如何替换该行:

completeGenerator.generateGraph(completeGraph, vFactory, null);

将矩阵元素作为输入。有谁知道如何做到这一点 ？ (我使用的是基于java的处理)

Answer 1

虽然不清楚你到底想做什么(2s会发生什么？哪些边相连？这是一个完整的图吗？它与网格有什么关系？)你的问题的答案可能是不使用现成的工艺。是的，示例中的方法创建 a complete graph顾名思义，我不确定上面所说的是否是您想要的。

您可以做的是自己处理矩阵并使用此库中的其他方法手动添加顶点和边，例如 in one of the examples上the library's home page ，(此处进行修改以制作字符串的有向图，并打印它)

    DirectedGraph<String, DefaultEdge> g =
        new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);

    String v1 = "v1";
    String v2 = "v2";
    String v3 = "v3";
    String v4 = "v4";

    // add the vertices
    g.addVertex(v1);
    g.addVertex(v2);
    g.addVertex(v3);
    g.addVertex(v4);

    // add edges to create a circuit
    g.addEdge(v1, v2);
    g.addEdge(v2, v3);
    g.addEdge(v3, v4);
    g.addEdge(v4, v1);


    //Print the edges
    Iterator<String> iter =
        new DepthFirstIterator<String, DefaultEdge>(g);
    String vertex;
    while (iter.hasNext()) {
        vertex = iter.next();
        System.out.println(
            "Vertex " + vertex + " is connected to: "
            + g.edgesOf(vertex));
    }

附注:请注意，在本例中，节点的类型是“String”。它可以是任何非 primitive类型或新类。例如，我在下面附加了“Integer”的相同代码

    DirectedGraph<Integer, DefaultEdge> g =
        new DefaultDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);

    Integer v1 = 2367;
    Integer v2 = 56799;
    Integer v3 = 78678;
    Integer v4 = 343;

    // add the vertices
    g.addVertex(v1);
    g.addVertex(v2);
    g.addVertex(v3);
    g.addVertex(v4);

    // add edges to create a circuit
    g.addEdge(v1, v2);
    g.addEdge(v2, v3);
    g.addEdge(v3, v4);
    g.addEdge(v4, v1);

    //Print out the graph to be sure it's really complete
    Iterator<Integer> iter =
        new DepthFirstIterator<Integer, DefaultEdge>(g);
    Integer vertex;
    while (iter.hasNext()) {
        vertex = iter.next();
        System.out.println(
            "Vertex " + vertex + " is connected to: "
            + g.edgesOf(vertex));
    }