7

たとえば、グラフのエッジを含むテキストファイルがあります

1 2

1 3

2 5

など、そして何らかの方法で私のグラフを表現したい。ハッシュマップを使用しようとしましたが、エッジを表すための最良の方法ですか？そして2番目の質問、ハッシュマップの最初と2番目のエントリにアクセスするにはどうすればよいですか？ここに私のコード

    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();
}
4

5 に答える 5

8

グラフの多くの可能な表現のうち、2 つの基本は次のとおりです。

  • 隣接リスト

ここに画像の説明を入力

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);
}
  • 隣接行列

ここに画像の説明を入力

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;
}

以下は、これら 2 つの表現の操作とストレージ効率の比較です。

                   |     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

隣接ノードを格納するために LinkedList の代わりに、隣接リストをわずかに変更して HashSet を使用することもできます。その場合、O(1) の複雑さ (償却) を持つ isAdjacent(x1,x2) 操作を除いて、すべて同じです。

于 2016-07-14T14:42:48.683 に答える
3

HashMap指定されたキーに対して単一の値を持つことができるため、この場合にはAは適していません。キーの複数の値を保持できるマップが必要です。Guavaは、 ArrayListMultimapのような実装を備えたMultimapでまさにこの概念を持っています。

于 2013-02-24T08:52:18.140 に答える
2

このような PNG を生成するには:

ここに画像の説明を入力

または、次のような 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>

あなたもそれを自分で行うことができます：

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

クラス 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;
   }
}

クラスグラフ:

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;
   }
}

クラス 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 );
   }
}
于 2013-02-24T09:19:17.507 に答える
0

グラフのトラバーサルは最適ではないため、HashMap はエッジを表す最良の方法ではありません。N 個のエッジのパスを通過するには、N 個の hashmap get() 操作が必要です。

于 2013-02-24T08:59:07.083 に答える
0

リストのマップを使用できます

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

このようにして、ノードを複数のノードにマップできます

于 2014-05-15T12:37:57.333 に答える