Représentation du graphique sous forme de hachisch

Question

J'ai un fichier texte avec des bords de graphe, par exemple

1 2

1 3

2 5

etc. , et je veux représenter mon graphe d'une certaine manière. J'ai essayé d'utiliser un hashmap, est-ce la meilleure façon de représenter les bords ? Et deuxième question, comment puis-je accéder à la première et à la deuxième entrée de mon hashmap ? Mon code est ici

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

Answer 1

Parmi les nombreuses représentations possibles d'un graphique, les deux principales sont les suivantes :

• Listes d'adjacence

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

• Matrice d'adjacence

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

Vous trouverez ci-dessous une comparaison des opérations et de l'efficacité de stockage de ces 2 représentations :

                   |     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

Vous pouvez également apporter une légère modification aux listes d'adjacence et utiliser des HashSets, au lieu de LinkedList pour stocker les nœuds adjacents. Dans ce cas, tout est identique, sauf l'opération isAdjacent(x1,x2) qui a maintenant une complexité O(1) (amortie).

Answer 2

A HashMap ne convient pas dans ce cas, car pour une clé donnée, on ne peut avoir qu'une seule valeur. Vous avez besoin d'une carte qui peut contenir plusieurs valeurs pour une clé. Goyave a exactement ce concept dans Multimap avec une mise en œuvre comme ArrayListMultimap .

Answer 3

Pour produire un PNG comme celui-ci :

ou un XML ( GraphML ) comme ceci :

<?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>

Vous pouvez aussi le faire vous-même :

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

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

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

classe Principale, exemple d'utilisation :

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

Answer 4

Un HashMap n'est pas le meilleur moyen de représenter les arêtes puisque la traversée du graphe n'est pas optimale. Traverser un chemin de N arêtes nécessite N opérations get() de hashmap.

Answer 5

Vous pouvez utiliser une carte de liste

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

De cette façon, vous pouvez faire correspondre un nœud à plus d'un nœud.