根据矩阵的元素和 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 声明的顶点数创建随机有向图，而我需要添加矩阵的元素 (1s) 作为顶点，然后使用程序生成有向图和 return 循环数（在上面的矩阵中将有 3 个循环）。

我不知道如何替换行：

completeGenerator.generateGraph(completeGraph, vFactory, null);

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

Answer 1

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

不过，您可以自己处理矩阵并使用此库中的其他方法手动添加顶点和边，例如 in one of the examples on 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 类型或新的 class。例如，我在下面附上 "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));
    }

根据矩阵的元素和 jgrapht 库定义顶点和边

Define vertices and edges based on a matrix' elements and jgrapht library

java

matrix

processing

digraphs