java 图的哈希图表示

Hashmap representation of graph

提问by user2081119

I have a text file with graph edges, for example

例如，我有一个带有图形边缘的文本文件

1 2

1 2

1 3

1 3

2 5

2 5

etc. , and want to represent my graph in some way. I tried to use a hashmap, is it the best way to represent edges? And second question, how can I access first and second entries in my hashmap? My code here

等，并想以某种方式表示我的图表。我尝试使用哈希图，这是表示边缘的最佳方式吗？第二个问题，如何访问哈希图中的第一个和第二个条目？我的代码在这里

    DataInputStream dStream = new DataInputStream(new FileInputStream("C:/Programming/Java/test.txt"));
    BufferedReader bReader = new BufferedReader(new InputStreamReader(dStream));

    HashMap<Integer, Integer> graphEdges = new HashMap<Integer, Integer>();
    String line;
    while( (line = bReader.readLine()) != null) {
        String[] firstSecond = line.split(" ");
        int firstDigit = Integer.parseInt(firstSecond[0]);
        int secondDigit = Integer.parseInt(firstSecond[1]);

        graphEdges.put(firstDigit, secondDigit);
    }

    System.out.println(graphEdges);

    bReader.close();
}

回答by Dimos

Among many possible representations of a graph, the 2 basic are the following:

在图形的许多可能表示中，2 种基本表示如下：

• Adjacency lists

• 邻接表

In Java:

在 Java 中：

Map<Integer, List<Integer>> graph = new HashMap<>();
...
while( (line = bReader.readLine()) != null) {
    String[] tokens = line.split(" ");
    int firstNode = Integer.parseInt(tokens[0]);
    int secondNode = Integer.parseInt(tokens[1]);

    if(!graph.containsKey(firstNode)) graph.put(firstNode, new LinkedList());
    graphEdges.get(firstNode).add(secondNode);
}

• Adjacency Matrix

• 邻接矩阵

In Java:

在 Java 中：

int[][] graph = new int[numberOfNodes][numberOfNodes];
while( (line = bReader.readLine()) != null) {
    String[] tokens = line.split(" ");
    int firstNode = Integer.parseInt(tokens[0]);
    int secondNode = Integer.parseInt(tokens[1]);

    graph[firstNode-1][secondNode-1] = 1;
    graph[secondNode-1][firstNode-1] = 1;
}

Below is a comparison of operations and storage efficiency of these 2 representations:

下面是这两种表示的操作和存储效率的比较：

                   |     Adjacency List    |   Adjacency Matrix   |
Storage            |      O(nodes+edges)   |     O(nodes^2)       |
Add node           |          O(1)         |     O(nodes^2)*      |
Add edge           |          O(1)         |        O(1)          |
Remove node        |        O(edges)       |     O(nodes^2)*      |
Remove edge        |        O(edges)       |        O(1)          |
isAdjacent(x1,x2)  |        O(nodes)       |        O(1)          |
*Requires copying of the whole array

You can also make a slight modification in the adjacency lists and use HashSets, instead of LinkedList for storing the adjacent nodes. In that case, everything is the same, except the isAdjacent(x1,x2) operation that now has O(1) complexity (amortized).

也可以对邻接表稍作修改，使用HashSets代替LinkedList来存储邻接节点。在这种情况下，除了 isAdjacent(x1,x2) 操作现在具有 O(1) 复杂度（摊销）之外，一切都相同。

回答by dan

A HashMapis not suited in this case since for a specified key you can have a single value. You need a map that can hold multiple values for a key. Guavahas exactly this concept in Multimapwith an implementations like ArrayListMultimap.

AHashMap不适合这种情况，因为对于指定的键，您可以有一个值。您需要一个可以为一个键保存多个值的映射。Guava在Multimap 中有这个概念，有一个像ArrayListMultimap这样的实现。

回答by Aubin

To produce a PNG like this:

要生成这样的 PNG：

or an XML (GraphML) like this:

或这样的 XML ( GraphML)：

<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
    <graph id="G" edgedefault="directed">
        <node id="Off" />
        <node id="Standby" />
        <node id="Fail" />
        <node id="Oper" />
        <node id="Recovery" />
        <node id="Shutdown" />
        <edge id="1" source="Off" target="Standby" />
        <hyperedge>
            <endpoint node=Standby" type="in" />
            <endpoint node=Fail" type="out" />
            <endpoint node=Oper" type="out" />
            <endpoint node=Shutdown" type="out" />
        </hyperedge>
        <hyperedge>
            <endpoint node=Fail" type="in" />
            <endpoint node=Shutdown" type="out" />
            <endpoint node=Recovery" type="out" />
        </hyperedge>
        <hyperedge>
            <endpoint node=Oper" type="in" />
            <endpoint node=Standby" type="out" />
            <endpoint node=Fail" type="out" />
            <endpoint node=Shutdown" type="out" />
        </hyperedge>
        <edge id="2" source="Shutdown" target="Off" />
        <hyperedge>
            <endpoint node=Recovery" type="in" />
            <endpoint node=Oper" type="out" />
            <endpoint node=Shutdown" type="out" />
        </hyperedge>
    </graph>
</graphml>

You may do it yourself too:

你也可以自己做：

public abstract class Edge {
   protected final Node _endPoint1;
   public Edge( Node endPoint ) {
      _endPoint1 = endPoint;
   }
   public Node getEndPoint1() {
      return _endPoint1;
   }
}

class DirectedEdge:

类定向边缘：

public final class DirectedEdge extends Edge {
   private final Node[] _to;
   public DirectedEdge( Node from, Node ... to ) {
      super( from );
      _to = to;
   }
   public Node getFrom() {
      return _endPoint1;
   }
   public Node[] getTo() {
      return _to;
   }
}

class Graph:

类图：

import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;

public final class Graph {
   private /* */ String              _name = "G";
   private final Map< String, Node > _nodes = new LinkedHashMap<>();
   private final Set< DirectedEdge > _edges = new LinkedHashSet<>();

   public boolean addNode( Node node ) {
      return _nodes.put( node._label, node ) == null;
   }
   public void addEdge( DirectedEdge edge ) {
      _edges.add( edge );
   }
   public String getName() {
      return _name;
   }
   public void setName( String name ) {
      _name = name;
   }
   public final Map<String, Node> getNodes() {
      return _nodes;
   }
   public final Set<DirectedEdge> getEdges() {
      return _edges;
   }
}

class Main, example of use:

类 Main，使用示例：

import java.io.File;

public class Main {
   private static Graph getGraph() {
      Graph graph = new Graph();
      Node off      = new Node( "Off" );
      Node standby  = new Node( "Standby" );
      Node fail     = new Node( "Fail" );
      Node oper     = new Node( "Oper" );
      Node recovery = new Node( "Recovery" );
      Node shutdown = new Node( "Shutdown" );
      graph.addNode( off );
      graph.addNode( standby );
      graph.addNode( fail );
      graph.addNode( oper );
      graph.addNode( recovery );
      graph.addNode( shutdown );
      graph.addEdge( new DirectedEdge( off     , standby ));
      graph.addEdge( new DirectedEdge( standby , fail, oper, shutdown ));
      graph.addEdge( new DirectedEdge( fail    , shutdown, recovery ));
      graph.addEdge( new DirectedEdge( oper    , standby, fail, shutdown ));
      graph.addEdge( new DirectedEdge( shutdown, off ));
      graph.addEdge( new DirectedEdge( recovery, oper, shutdown ));
      return graph;
   }
   public static void main( String[] args ) throws Exception {
      Graph graph = getGraph();
      new DotFileGenerator().save( new File( "States.png"     ), graph );
      new GraphMLGenerator().save( new File( "States.graphml" ), graph );
   }
}

回答by user3640824

You can use a Map of List

您可以使用列表地图

HashMap<Integer, LinkedList<Integer>> graphEdges = new HashMap<Integer,LinkedList<Integer>>();

This way you can map a node to more than one node

这样你就可以将一个节点映射到多个节点

回答by Oded Peer

A HashMap is not the best way to represent edges since graph traversal is not optimal. Going over a path of N edges requires N hashmap get() operations.

HashMap 不是表示边的最佳方式，因为图遍历不是最优的。遍历 N 条边的路径需要 N 个 hashmap get() 操作。