無向グラフの隣接リスト

Question

無向グラフを表すために隣接リストを使用するための汎用サンプルコードはどこから入手できますか？

グラフデータは.txtファイルになります。ノードはスペースで区切られた最初の行に指定されます。エッジは次の行で指定され、各エッジは別々の行に指定されます。このよう

...

1 2 3 4 5 6 7 8 9 

1 2 

1 4 

1 3 

2 4 

2 5 

3 6 

4 6 

5 7 

5 8 

6 9 

7 9 

8 9 

私の.txtファイルには、グラフの方法で接続されていません。私はまた、次のNPEエラーを取得しています：

Error: java.lang.NullPointerException 

は無向グラフのための標準的なグラフのADTの方法を実行する隣接リスト&を作成します。

//TON of imports up here (removed for now) 

class Graph<V> implements GraphADT1 <V>{ 

// Map of adjacency lists for each node 
private HashMap<Integer, LinkedList<Integer>> adj; 
private ArrayList<V> vertices; 
private HashMap<V, LinkedHashSet<V>> neighbors; 
private HashMap<V, Set<V>> neighborsView; 
private int edgeCount; 


public Graph(int[] nodes) { 

    vertices = new ArrayList<V>(); 
    neighbors = new HashMap<V, LinkedHashSet<V>>(); 
    neighborsView = new HashMap<V, Set<V>>(); 
    adj = new HashMap<Integer, LinkedList<Integer>>(); 

    for (int i = 0; i < nodes.length; ++i) { 
     adj.put(i, new LinkedList<Integer>()); 
    } 
} 

//Add Vertex Method 
public void addVertex(V vid) { 
    vertices.add(vid); 
    LinkedHashSet<V> neighborV = new LinkedHashSet<V>(); 
    neighbors.put(vid, neighborV); 
    neighborsView.put(vid, Collections.unmodifiableSet(neighborV)); 

} 

// Removes Vertex Method 
public void removeVertex(V vid) { 
    if(vertices.remove(vid)) { 
     LinkedHashSet<V> neighborV = neighbors.remove(vid); 
     for(V uid : neighborV) { 
      LinkedHashSet<V> neighborU = neighbors.get(uid); 
      neighborU.remove(vid); 
      --edgeCount; 
     } 
     neighborsView.remove(vid); 

    } else { 
     throw new NoSuchElementException("no such vertex"); 
    } 
} 

//Add Edge Method 
public void addEdge(V uid, V vid) { 
    LinkedHashSet<V> neighborU = neighbors.get(uid); 
    LinkedHashSet<V> neighborV = neighbors.get(vid); 
    if(neighborU == null) throw new NoSuchElementException("first argument not in graph"); 
    if(neighborV == null) throw new NoSuchElementException("second argument not in graph"); 
    if(neighborU.add(vid) && neighborV.add(uid)) { 
     ++edgeCount; 
    } 
} 

//Remove Edge Method 
public void removeEdge(V uid, V vid) { 
    LinkedHashSet<V> neighborU = neighbors.get(uid); 
    LinkedHashSet<V> neighborV = neighbors.get(vid); 
    if(neighborU == null) throw new NoSuchElementException("first argument not in graph"); 
    if(neighborV == null) throw new NoSuchElementException("second argument not in graph"); 
    if(neighborU.remove(vid) && neighborV.remove(uid)) { 
     --edgeCount; 
    } else { 
     throw new NoSuchElementException("no edge between vertices"); 
    } 
} 



public void addNeighbor(int neighborV, int neighborU) { 
    adj.get(neighborV).add(neighborU); 
} 

public List<Integer> getNeighbors(int v) { 
    return adj.get(v); 
} 

public static void main(String[] args) { 
    try { 

     File file = new File("data.txt"); 
     InputStreamReader streamReader = new InputStreamReader(
       new FileInputStream(file)); 
     BufferedReader br = new BufferedReader(streamReader); 
     String line = br.readLine(); 

     if (line != null) { 

      // read nodes 
      String[] nodeNames = line.split(" "); 
      int[] nodes = new int[nodeNames.length]; 
      for (int i = 0; i < nodes.length; ++i) { 
       nodes[i] = Integer.parseInt(nodeNames[i]); 
      } 

      // create graph 
       Graph V = new Graph(nodes); 


      // read edges 
      while ((line = br.readLine()) != null) { 
       String[] tokens = line.split(" "); 
       int neighborV = Integer.parseInt(tokens[0]); 
       int neighborU = Integer.parseInt(tokens[1]); 

       // we add neighbor to each node in both directions. 
       V.addNeighbor(neighborV, neighborU); 
       V.addNeighbor(neighborU, neighborV); 
      } 

     } 
     br.close(); 
    } catch (FileNotFoundException ex) { 
     ex.printStackTrace(); 
    } catch (IOException ex) { 
     ex.printStackTrace(); 
    } catch (Exception e) { 
     System.out.println("Error: " + e); 
    } 
} 




public Iterator<?> iteratorBFS(Object startVertex) { 

    return null; 
} 

public Iterator<?> iteratorDFS(Object startVertex) { 

    return null; 
} 

public boolean isEmpty() { 
    return size() == 0; 
} 

public boolean isConnected() { 

    return false; 
} 

public int size() { 

    return 0; 
} 
} 

Answer 1

あなたはクラスであなたのグラフを囲むことができます。その後、

class Graph { 
    //Map of adjacency lists for each node 
    Map<Integer, List<Integer>> adj; 

    public Graph(int[] nodes) { 
     //your node labels are consecutive integers starting with one. 
     //to make the indexing easier we will allocate an array of adjacency one element larger than necessary 
     adj = new HashMap<Integer, LinkedList<Integer>>(); 
     for (int i = 0; i < nodes.length; ++i) { 
      adj.put(i, new LinkedList<Integer>()); 
     } 
    } 

    public addNeighbor(int v1, int v2) { 
     adj.get(v1).add(v2); 
    } 

    public List<Integer> getNeighbors(int v) { 
     return adj.get(v); 
    } 

} 

そして、このように多かれ少なかれそれを読む：リトルより具体的下さい

public static void main(String[] args) { 
    try { 
     BufferedReader br = new BufferedReader(new StreamReader(System.in)); 
     String line = br.readLine(); 


     if (line != null) { 
      //read nodes 
      String[] nodeNames = line.split(" "); 
      int[] nodes = new int[nodeNames.length] 
      for (int i = 0; i < nodes.length; ++i) { 
       nodes[i] = Integer.parseInt(nodeNames[i]); 
      } 

      //create graph 
      Graph g = new Graph(nodes); 

      //read edges 
      while((line = br.readLine()) != null) { 
       String[] tokens = line.split(" "); 
       int v1 = Integer.parseInt(tokens[0]); 
       int v2 = Integer.parseInt(tokens[1]); 


       //we add neighbor to each node in both directions. 
       g.addNeighbor(v1, v2); 
       g.addNeighbor(v2, v1); 
      } 

     } 
     br.close(); 
    } 
    catch(exceptions) { 
     handle them 
    } 

} 

Answer 2

public static void main(String [] Args){ 
    try { 

     Scanner s = new Scanner(new File("your file.txt")); 
     StringTokenizer t = new StringTokenizer(s.nextLine()); 
     Hashtable<Integer,Node> nodes = new Hashtable<Integer,Node>(); 
     while(t.hasMoreTokens()){ 
      int id = Integer.parseInt(t.nextToken()); 
      nodes.put(id, new Node(id)); 
     } 

     while(s.hasNextInt()){ 
      Node e1 = nodes.get(s.nextInt()); 
      Node e2 = nodes.get(s.nextInt()); 

      e1.adjacent.add(e2); 
      e2.adjacent.add(e1); 
     } 

     \\now you can use the nodes Map above to retrieve nodes or to get a list: 

     List<Node> adjencyNodeList = new ArrayList(nodes.values()); 
    } catch (FileNotFoundException e) { 
     // TODO Auto-generated catch block 
     e.printStackTrace(); 
    } 
} 

class Node { 
    int id; 
    List<Node> adjacent = new ArrayList<Node>(); 

    public Node(int id){ 
     this.id = id; 
    } 
}