Datenstrukturen für Graphen

Auf dieser Seite werden die Datenstrukturen für Graphen behandelt. In Java gibt es keine hauseigene Graphimplementierung, aber es gibt diverse Pakete für verschiedene Anwendungen.

Jung (http://jung.sourceforge.net)

Graph<Integer, String> g = new SparseMultigraph<Integer, String>(); 
g.addVertex((Integer)1); 
g.addVertex((Integer)2); 
g.addEdge("Edge1", 1, 2);

Neo4j (http://www.neo4j.org)

GraphDatabaseService= new 
"GraphDatabaseFactory().newEmbeddedDatabase(“PATH”); 
Transaction tx = graphDb.beginTx(); 
try{ 
   Node firstNode = graphDb.createNode(); 
   Node secondNode = graphDb.createNode(); 
   Relationship relationship = firstNode.createRelationshipTo(secondNode, 
    … ); 
   tx.success(); 
}finally{ 
   tx.finish(); 
}

Die allgemeine Schnittstelle für die Vorlesung ist:

 public interface Graph {
   public int addNode();
   public boolean addEdge (int orig, int dest);
}

Implementierung Adjazenzliste

 public class AdjazenzListGraph implements Graph {
   private int [][] adjacencyList=null;

   //Knoten hinzufügen:
   public int addNode() {
      int nodeNumber = (adjacencyList ==null)?0: adjacencyList.length;
      int [][] newAdjacencyList= new int [nodeNumber+1][];
      //alte adjacencyList kopieren
      for (int i=0; i< nodeNumber; i++) 
         newAdjacencyList [i]=adjacencyList[i];
      //neuer Knoten hat noch keine Kanten
      newAdjacencyList[nodeNumber] =null; 
      adjacencyList=newAdjacencyList;
      return nodeNumber+1;
   }

   //Kante hinzufügen:
   public boolean addEdge (int orig, int dest){
      int nodeNumber = (adjacencyList == null)? 0: adjacencyList.length;
      if (orig > nodeNumber || dest > nodeNumber || orig < 1 || dest < 1 )
         return false;
      if (adjacencyList[orig-1] != null)
         for (int n : adjacencyList[orig-1])
            //Kante bereits vorhanden?
            if (n==dest) return false; 
      //Erste Kante am Knoten orig?
      if ( adjacencyList[orig-1] == null ) { 
         adjacencyList [orig-1] = new int[1];
         adjacencyList[orig-1][0]=dest;
      }  
      else {
         int[] newList= new int[adjacencyList[orig-1].length+1];
         System.arraycopy(adjacencyList[orig-1],0,newList,0,adjacencyList[orig-1].length);
         newList[adjacencyList[orig-1].length]=dest;
         adjacencyList [orig-1]=newList;
      }
      return true;
   }
}