Список смежности для неориентированного графа

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

Создание списка смежности и выполнение стандартных методов Graph 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;
    }
}