Adjacency Matrix in java, Breadth First Search

Question

The following code performs a breadth first search algorithm using an adjacency list structure. I was curious. If I were to implement this an adjacency matrix, what kinds of edits would I have to do to the code?

I know I would have to create a grid (n by n matrix), but would my data file have to correspond to this grid structure? Or would I just fill an empty grid structure and implement the level design my text file already has?

I feel that implementing this in actual code is what I am mostly confused about, in regards to the code below (which uses a stack). I've never done bfs using a matrix, only adjacency list.

Here it is:

import java.io.*;
import java.util.*;

public class MainM {

    private Graph graph;

    /**
     * Constructor.
     */
    public MainM(Graph g) {
        graph = g;
    }

    /**
     * 1 - Create a stack to store all the vertices of our path on.
     * 2 - First push the 'end' vertex on our stack.
     * 3 - Now loop from the highest level back to the first level and
     *     a. loop through each level and
     *     b. check each vertex in that level if it's connected to the
     *        vertex on the top of our stack, if we find a match, push that
     *        match on the stack and break out of the loop.
     * 4 - Now we only need to reverse the collection (stack) before returning 
     *     the path in the "correct" order (from start to finish).
     * 
     * Here's an example ASCII drawing of backtracking from the end vertex "n" 
     * to the starting vertex "g". The arrows, <-, denote the path that was 
     * found.
     * 
     * level:  0      1      2      3       4      5      6    7     8
     *        ---------------------------------------------------------
     *         g <-+  IV     e      I       a   +- III <- o <- VI <- n 
     *             +- V <-+  f   +- II <-+  b   |         p
     *                    +- c <-+       |  d   |
     *                       j           +- h <-+
     *                                      q
     *                                      r
     */
    private List<String> backTrack(List<List<String>> container, String end) {
        Stack<String> path = new Stack<String>();                     // 1
        path.push(end);                                               // 2
        for(int i = container.size()-1; i >= 0; i--) {                // 3
            List<String> level = container.get(i);
            String last = path.peek();
            for(String s : level) {                                   // a
                if(graph.isConnectedTo(last, s)) {                     // b
                    path.push(s);
                    break;
                }
            }
        }
        Collections.reverse(path);                                    // 4
        return path;
    }

    /**
     * 1 - Get the level from the 'container' which was added last.
     * 2 - Create a new level to store (possible) unexplored verices in.
     * 3 - Loop through each of the vertices from the last added level, and
     *     a. get the neighboring vertices connected to each vertex,
     *     b. loop through each connecting vertex and if the connecting vertex
     *        has not yet been visited,
     *     c. only then add it to the newly created level-list and mark it as 
     *        visited in our set.
     * 4 - We don't need to search any further if we stumble upon the 'end' 
     *     vertex. In that case, just "return" from this method.
     * 5 - Only make the recursive call if we have found vertices which have 
     *     not been explored yet.
     */
    private void bfs(List<List<String>> container, 
            String end, Set<String> visited) {

        List<String> lastLevel = container.get(container.size()-1);   // 1
        List<String> newLevel = new ArrayList<String>();              // 2

        for(String vertex : lastLevel) {                              // 3
            List<String> edges = graph.getEdges(vertex);              // a
            for(String edge : edges) {                                // b
                if(!visited.contains(edge)) {                         // c
                    visited.add(edge);
                    newLevel.add(edge);
                }
                if(edge.equals(end)) return;                          // 4
            }
        }  
        if(newLevel.size() > 0) {                                     // 5
            container.add(newLevel);
            bfs(container, end, visited);
        }
    }

    /**
     * 1 - Create an empty 'container' to store all the levels from the 
     *     'start'-vertex in. A level is also a list with one or more vertices.
     * 2 - The first level only holds the 'start' vertex, which is added first,
     *     this is the 'init' list.
     * 3 - The 'start' vertex is also stored in a Set which keeps track of all 
     *     the vertices we have encountered so that we don't traverse vertices
     *     twice (or more).
     * 4 - Once we initialized the steps 1-3, we can call the actual BFS-
     *     algorithm.
     * 5 - Once the BFS-algorithm is done, we call the backTrack(...) method 
     *     to find the shortest path between 'end' and 'start' between the 
     *     explored levels of the graph. 
     */
    public List<String> getShortestPath(String start, String end) {
        List<List<String>> container = new ArrayList<List<String>>(); // 1
        List<String> init = new ArrayList<String>();                  // 2
        init.add(start);
        container.add(init);
        Set<String> visited = new HashSet<String>();                  // 3
        visited.add(start);
        bfs(container, end, visited);                                 // 4
        return backTrack(container, end);                             // 5
    }

    /**
     * Main method:
     *  1 - Create a Graph.
     *  2 - Get a shortest path between two vertices.
     *  3 - Print the shortest path.
     */
    public static void main(String[] args) throws FileNotFoundException {
        Graph graph = new Graph("data.txt");                          // 1
        MainM bfsAlgorithm = new MainM(graph);
        Scanner sc = new Scanner(System.in);
        System.out.println("Please enter starting city: ");
        String shortPath = sc.nextLine();

        System.out.println("Please enter ending city: ");
        String shortPath2 = sc.nextLine();
        List<String> shortestPath = bfsAlgorithm.getShortestPath(shortPath, shortPath2);
        //List<String> shortestPath = 
          //  bfsAlgorithm.getShortestPath("g", "n");                   // 2
        for(int i = 0; i < shortestPath.size(); i++) {
            System.out.print(shortestPath.get(i));                    // 3
            System.out.print(i < shortestPath.size()-1 ? " --> " : " ");
        }
    }
}

And here is the graph class:

import java.io.*;
import java.util.*;

public class Graph {

    private Map<String, List<String>> adjacencyList;

    /**
     * Instatiates the 'adjacencyList' and then parse the data file.
     */
    public Graph(String fileName) throws FileNotFoundException {
        adjacencyList = new HashMap<String, List<String>>();
        parseDataFile(fileName);
    }

    /**
     * This is an undirected graph, so we connect 'vertexA' to 'vertexB' 
     * and the other way around.
     */
    public void addConnection(String vertexA, String vertexB) {
        connect(vertexA, vertexB);
        connect(vertexB, vertexA);
    }

    /**
     * A private helper-method to connect 'vertexA' to 'vertexB'.
     * If 'vertexA' alreay exists in our 'adjacencyList', get it's 
     * edges-list and add 'vertexB' to it. If it doesn't exist,  
     * create a new ArrayList, add 'vertexB' to it and put it all 
     * in our 'adjacencyList'.
     */
    private void connect(String vertexA, String vertexB) {
        List<String> edges;
        if(adjacencyList.containsKey(vertexA)) {
            edges = adjacencyList.get(vertexA);
            edges.add(vertexB);
        } else {
            edges = new ArrayList<String>();
            edges.add(vertexB);
            this.adjacencyList.put(vertexA, edges);
        }
    }

    /**
     * Returns true iff 'vertexA' poits to to 'vertexB'.
     * Note that since this is an undirected graph, we do not 
     * need to check the other way around, the case if 'vertexB' 
     * is points to 'vertexA'.
     */
    public boolean isConnectedTo(String vertexA, String vertexB) {
        List<String> edges = getEdges(vertexA);
        return edges.contains(vertexB);
    }

    /**
     * Returns all the edges of a certain vertex, or throws an 
     * exception if the vertex doesn't exist in this graph.
     */
    public List<String> getEdges(String vertex) {
        List<String> edges = adjacencyList.get(vertex);
        if(edges == null) {
            throw new RuntimeException(vertex+" not present in the graph.");
        }
        return edges;
    }

    /**
     * Reads a text file with the graph-data. The text file contains 
     * N-blocks of lines where each block starts with the city followed
     * by N-lines of text representing the city2s and ending with an 
     * empty line.
     */
    private void parseDataFile(String fileName) throws FileNotFoundException {
        Scanner file = new Scanner(new File(fileName));
        while(file.hasNextLine()) {
            String city = file.nextLine().trim();
            while(file.hasNextLine()) {
                String city2 = file.nextLine().trim();
                if(city2.length() == 0) break;
                addConnection(city, city2);
            }
        }
    }

    /**
     * A Sting representation if this Graph.
     */
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Iterator<String> vertices = adjacencyList.keySet().iterator();
        while(vertices.hasNext()) {
            String vertex = vertices.next();
            List<String> edges = adjacencyList.get(vertex);
            builder.append(vertex);
            builder.append(" --> ");
            builder.append(edges);
            builder.append('\n');
        }
        return builder.toString();
    }

    /**
     * main
     */
    public static void main(String[] args) {
        try {
            Graph graph = new Graph("data.txt");
            System.out.println(graph);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
}

here is a text test file:

Seattle
  a
  b
  01
  d
  e

II
  c
  h
  q
  r

III
  h
  o
  p

IV
  e
  f
  g

V
  c
  g
  j

VI
  k
  m
  n
  o

Answer 1

That's the fun part of OO programming :-)

If you create a common interface for a Graph and give 2 implementations (e.g., AdjListGraph and AdjMxGraph), you don't have to change anything in your MainM class except the declaration. Just implement the common functions (addConnection(), isConnectedTo(), etc.) in the new adjacency matrix based implementation.

I wouldn't consider changing my input data structure. Btw, there are plenty of options to use, the most common is the Pajek format -- which may be kinda strange for the first sight.

Also, there are dozens of graphing libs out there (GraphStream, JUNG, etc.), take a look on them. You can learn quite a lot by simply browsing those codebases.

Hope that helps something ;]