DEV Community: Paul Ike

Case Study: The Weighted Nine Tails Problem

Paul Ike — Thu, 05 Sep 2024 17:01:46 +0000

The weighted nine tails problem can be reduced to the weighted shortest path problem.
Section presented the nine tails problem and solved it using the BFS algorithm. This section presents a variation of the problem and solves it using the shortest-path algorithm.

The nine tails problem is to find the minimum number of the moves that lead to all coins facing down. Each move flips a head coin and its neighbors. The weighted nine tails problem assigns the number of flips as a weight on each move. For example, you can change the coins in Figure below a to those in Figure below b by flipping the first coin in the first row and its two neighbors. Thus, the weight for this move is 3. You can change the coins in Figure below c to Figure below d by flipping the center coin and its four neighbors. So the weight for this move is 5.

The weighted nine tails problem can be reduced to finding a shortest path from a starting node to the target node in an edge-weighted graph. The graph has 512 nodes. Create an edge from node v to u if there is a move from node u to node v. Assign the number of flips to be the weight of the edge.

Recall that in Section we defined a class NineTailModel for modeling the nine tails problem. We now define a new class named WeightedNineTailModel that extends NineTailModel, as shown in Figure below.

The NineTailModel class creates a Graph and obtains a Tree rooted at the target node 511. WeightedNineTailModel is the same as NineTailModel except that it creates a WeightedGraph and obtains a ShortestPathTree rooted at the target node 511. WeightedNineTailModel extends NineTailModel. The method getEdges() finds all edges in the graph. The getNumberOfFlips(int u, int v) method returns the number of flips from node u to node v. The getNumberOfFlips(int u) method returns the number of flips from node u to the target node.

The code below implements WeightedNineTailModel.

package demo;
import java.util.*;

public class WeightedNineTailModel extends NineTailModel {
    /** Construct a model */
    public WeightedNineTailModel() {
        // Create edges
        List<WeightedEdge> edges = getEdges();

        // Create a graph
        WeightedGraph<Integer> graph = new WeightedGraph<>(edges, NUMBER_OF_NODES);

        // Obtain a shortest path tree rooted at the target node
        tree = graph.getShortestPath(511);
    }

    /** Create all edges for the graph */
    private List<WeightedEdge> getEdges() {
        // Store edges
        List<WeightedEdge> edges = new ArrayList<>();

        for(int u = 0; u < NUMBER_OF_NODES; u++) {
            for(int k = 0; k < 9; k++) {
                char[] node = getNode(u); // Get the node for vertex u
                if(node[k] == 'H') {
                    int v = getFlippedNode(node, k);
                    int numberOfFlips = getNumberOfFlips(u, v);

                    // Add edge (v, u) for a legal move from node u to node v
                    edges.add(new WeightedEdge(v, u, numberOfFlips));
                }
            }
        }

        return edges;
    }

    private static int getNumberOfFlips(int u, int v) {
        char[] node1 = getNode(u);
        char[] node2 = getNode(v);

        int count = 0; // Count the number of different cells
        for(int i = 0; i < node1.length; i++)
            if(node1[i] != node2[i]) count++;

        return count;
    }

    public int getNumberOfFlips(int u) {
        return (int)((WeightedGraph<Integer>.ShortestPathTree)tree).getCost(u);
    }
}

WeightedNineTailModel extends NineTailModel to build a WeightedGraph to model the weighted nine tails problem (lines 10–11). For each node u, the getEdges() method finds a flipped node v and assigns the number of flips as the weight for edge (v, u) (line 30). The getNumberOfFlips(int u, int v) method returns the number of flips from node u to node v (lines 38–47). The number of flips is the number of the different cells between the
two nodes (line 44).

The WeightedNineTailModel obtains a ShortestPathTree rooted at the target node 511 (line 14). Note that tree is a protected data field defined in NineTailModel and ShortestPathTree is a subclass of Tree. The methods defined in NineTailModel use the tree property.

The getNumberOfFlips(int u) method (lines 49–52) returns the number of flips from node u to the target node, which is the cost of the path from node u to the target node. This cost can be obtained by invoking the getCost(u) method defined in the ShortestPathTree class (line 51).

The code below gives a program that prompts the user to enter an initial node and displays the minimum number of flips to reach the target node.

package demo;

import java.util.Scanner;

public class WeightedNineTail {

    public static void main(String[] args) {
        // Prompt the user to enter nine coins' Hs and Ts
        System.out.print("Enter the initial nine coins Hs and Ts: ");
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        char[] initialNode = s.toCharArray();

        WeightedNineTailModel model = new WeightedNineTailModel();
        java.util.List<Integer> path = model.getShortestPath(NineTailModel.getIndex(initialNode));

        System.out.println("The steps to flip the coins are ");
        for (int i = 0; i < path.size(); i++)
            NineTailModel.printNode(NineTailModel.getNode(path.get(i).intValue()));

        System.out.println("The number of flips is " +  model.getNumberOfFlips(NineTailModel.getIndex(initialNode)));
    }

}

Enter an initial nine coins Hs and Ts: HHHTTTHHH

The steps to flip the coins are

HHH TTT HHH

HHH THT TTT

TTT TTT TTT

The number of flips is 8

The program prompts the user to enter an initial node with nine letters with a combination of Hs and Ts as a string in line 8, obtains an array of characters from the string (line 9), creates a model (line 11), obtains the shortest path from the initial node to the target node (lines 12–13), displays the nodes in the path (lines 16–17), and invokes getNumberOfFlips to get the number of flips needed to reach the target node (line 20).

Finding Shortest Paths

Paul Ike — Thu, 05 Sep 2024 16:41:27 +0000

The shortest path between two vertices is a path with the minimum total weights.
Given a graph with nonnegative weights on the edges, a well-known algorithm for finding a shortest path between two vertices was discovered by Edsger Dijkstra, a Dutch computer scientist. In order to find a shortest path from vertex s to vertex v, Dijkstra’s algorithm finds the shortest path from s to all vertices. So Dijkstra’s algorithm is known as a single-source shortest path algorithm. The algorithm uses cost[v] to store the cost of a shortest path from vertex v to the source vertex s. cost[s] is 0. Initially assign infinity to cost[v] for all other vertices. The algorithm repeatedly finds a vertex u in V – T with the smallest cost[u] and moves u to T.

The algorithm is described in code below.

Input: a graph G = (V, E) with non-negative weights
Output: a shortest path tree with the source vertex s as the root
 1 ShortestPathTree getShortestPath(s) {
 2 Let T be a set that contains the vertices whose
 3 paths to s are known; Initially T is empty;
 4 Set cost[s] = 0; and cost[v] = infinity for all other vertices in V;
 5
 6 while (size of T < n) {
 7 Find u not in T with the smallest cost[u];
 8 Add u to T;
 9 for (each v not in T and (u, v) in E)
10 if (cost[v] > cost[u] + w(u, v)) {
11 cost[v] = cost[u] + w(u, v); parent[v] = u;
12 }
13 }
14 }

This algorithm is very similar to Prim’s for finding a minimum spanning tree. Both algorithms divide the vertices into two sets: T and V - T. In the case of Prim’s algorithm, set T contains the vertices that are already added to the tree. In the case of Dijkstra’s, set T contains the vertices whose shortest paths to the source have been found. Both algorithms repeatedly find a vertex from V – T and add it to T. In the case of Prim’s algorithm, the vertex is adjacent to some vertex in the set with the minimum weight on the edge. In Dijkstra’s algorithm, the vertex is adjacent to some vertex in the set with the minimum total cost to the source.

The algorithm starts by setting cost[s] to 0 (line 4), sets cost[v] to infinity for all other vertices. It then continuously adds a vertex (say u) from V – T into T with smallest cost[u] (lines 7–8), as shown in Figure below a. After adding u to T, the algorithm updates cost[v] and parent[v] for each v not in T if (u, v) is in T and cost[v] > cost[u] + w(u, v) (lines 10–11).

Let us illustrate Dijkstra’s algorithm using the graph in Figure below a. Suppose the source vertex is 1. Therefore, cost[1] = 0 and the costs for all other vertices are initially ∞, as shown in Figure below b. We use the parent[i] to denote the parent of i in the path. For convenience, set the parent of the source node to -1.

Initially set T is empty. The algorithm selects the vertex with the smallest cost. In this case, the vertex is 1. The algorithm adds 1 to T, as shown in Figure below a. Afterwards, it adjusts the cost for each vertex adjacent to 1. The cost for vertices 2, 0, 6, and 3 and their parents are now updated, as shown, as shown in Figure below b.

Vertices 2, 0, 6, and 3 are adjacent to the source vertex, and vertex 2 is the one in V-T with the smallest cost, so add 2 to T, as shown in Figure below and update the cost and parent for vertices in V-T and adjacent to 2. cost[0] is now updated to 6 and its parent is set to 2. The arrow line from 1 to 2 indicates that 1 is the parent of 2 after 2 is added into T.

Now T contains {1, 2}. Vertex 0 is the one in V-T with the smallest cost, so add 0 to T, as shown in Figure below and update the cost and parent for vertices in V-T and adjacent to 0 if applicable. cost[5] is now updated to 10 and its parent is set to 0 and cost[6] is now updated to 8 and its parent is set to 0.

Now T contains {1, 2, 0}. Vertex 6 is the one in V-T with the smallest cost, so add 6 to T, as shown in Figure below and update the cost and parent for vertices in V-T and adjacent to 6 if applicable.

Now T contains {1, 2, 0, 6}. Vertex 3 or 5 is is the one in V-T with the smallest cost. You may add either 3 or 5 into T. Let us add 3 to T, as shown in Figure below and update the cost and parent for vertices in V-T and adjacent to 3 if applicable. cost[4] is now updated to 18 and its parent is set to 3.

Now T contains {1, 2, 0, 6, 3}. Vertex 5 is the one in V-T with the smallest cost, so add 5 to T, as shown in Figure below and update the cost and parent for vertices in V-T and adjacent to 5 if applicable. cost[4] is now updated to 10 and its parent is set to 5.

Now T contains {1, 2, 0, 6, 3, 5}. Vertex 4 is the one in V-T with the smallest cost, so add 4 to T, as shown in Figure below.

As you can see, the algorithm essentially finds all shortest paths from a source vertex, which produces a tree rooted at the source vertex. We call this tree a single-source all-shortest-path tree (or simply a shortest-path tree). To model this tree, define a class named ShortestPathTree that extends the Tree class, as shown in Figure below. ShortestPathTree is defined as an inner class in WeightedGraph in lines 200–224 in WeightedGraph.java.

The getShortestPath(int sourceVertex) method was implemented in lines 156–197 in WeightedGraph.java. The method sets cost[sourceVertex] to 0 (line 162) and cost[v] to infinity for all other vertices (lines 159–161). The parent of sourceVertex is set to -1 (line 166). T is a list that stores the vertices added into the shortest path tree (line 169). We use a list for T rather than a set in order to record the order of the vertices added to T.

Initially, T is empty. To expand T, the method performs the following operations:

Find the vertex u with the smallest cost[u] (lines 175–181) and add it into T (line 183).
After adding u in T, update cost[v] and parent[v] for each v adjacent to u in V-T if cost[v] > cost[u] + w(u, v) (lines 186–192).

Once all vertices from s are added to T, an instance of ShortestPathTree is created (line 196).

The ShortestPathTree class extends the Tree class (line 200). To create an instance of ShortestPathTree, pass sourceVertex, parent, T, and cost (lines 204–205). sourceVertex becomes the root in the tree. The data fields root, parent, and searchOrder are defined in the Tree class, which is an inner class defined in AbstractGraph.

Note that testing whether a vertex i is in T by invoking T.contains(i) takes O(n) time, since T is a list. Therefore, the overall time complexity for this implemention is O(n^3).

Dijkstra’s algorithm is a combination of a greedy algorithm and dynamic programming. It is a greedy algorithm in the sense that it always adds a new vertex that has the shortest distance to the source. It stores the shortest distance of each known vertex to the source and uses it later to avoid redundant computing, so Dijkstra’s algorithm also uses dynamic programming.

The code below gives a test program that displays the shortest paths from Chicago to all other cities in Figure below and the shortest paths from vertex 3 to all vertices for the graph in Figure below a, respectively.

package demo;

public class TestShortestPath {

    public static void main(String[] args) {
String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1, 807}, {0, 3, 1331}, {0, 5, 2097},
                {1, 0, 807}, {1, 2, 381}, {1, 3, 1267},
                {2, 1, 381}, {2, 3, 1015}, {2, 4, 1663}, {2, 10, 1435},
                {3, 0, 1331}, {3, 1, 1267}, {3, 2, 1015}, {3, 4, 599}, {3, 5, 1003},
                {4, 2, 1663}, {4, 3, 599}, {4, 5, 533}, {4, 7, 1260}, {4, 8, 864}, {4, 10, 496},
                {5, 0, 2097}, {5, 3, 1003}, {5, 4, 533}, {5, 6, 983}, {5, 7, 787},
                {6, 5, 983}, {6, 7, 214},
                {7, 4, 1260}, {7, 5, 787}, {7, 6, 214}, {7, 8, 888},
                {8, 4, 864}, {8, 7, 888}, {8, 9, 661}, {8, 10, 781}, {8, 11, 810},
                {9, 8, 661}, {9, 11, 1187},
                {10, 2, 1435}, {10, 4, 496}, {10, 8, 781}, {10, 11, 239},
                {11, 8, 810}, {11, 9, 1187}, {11, 10, 239}
        };

        WeightedGraph<String> graph1 = new WeightedGraph<>(vertices, edges);
        WeightedGraph<String>.ShortestPathTree tree1 = graph1.getShortestPath(graph1.getIndex("Chicago"));
        tree1.printAllPaths();

        // Display shortest paths from Houston to Chicago       
        System.out.println("Shortest path from Houston to Chicago: ");
        java.util.List<String> path = tree1.getPath(graph1.getIndex("Houston"));
        for(String s: path) {
            System.out.print(s + " ");
        }

        edges = new int[][]{
            {0, 1, 2}, {0, 3, 8},
            {1, 0, 2}, {1, 2, 7}, {1, 3, 3},
            {2, 1, 7}, {2, 3, 4}, {2, 4, 5},
            {3, 0, 8}, {3, 1, 3}, {3, 2, 4}, {3, 4, 6},
            {4, 2, 5}, {4, 3, 6}
        };

        WeightedGraph<Integer> graph2 = new WeightedGraph<>(edges, 5);
        WeightedGraph<Integer>.ShortestPathTree tree2 = graph2.getShortestPath(3);
        System.out.println("\n");
        tree2.printAllPaths();
    }

}

All shortest paths from Chicago are: A path from Chicago to Seattle: Chicago Seattle (cost: 2097.0) A path from Chicago to San Francisco: Chicago Denver San Francisco (cost: 2270.0) A path from Chicago to Los Angeles: Chicago Denver Los Angeles (cost: 2018.0) A path from Chicago to Denver: Chicago Denver (cost: 1003.0) A path from Chicago to Kansas City: Chicago Kansas City (cost: 533.0) A path from Chicago to Chicago: Chicago (cost: 0.0) A path from Chicago to Boston: Chicago Boston (cost: 983.0) A path from Chicago to New York: Chicago New York (cost: 787.0) A path from Chicago to Atlanta: Chicago Kansas City Atlanta (cost: 1397.0) A path from Chicago to Miami: Chicago Kansas City Atlanta Miami (cost: 2058.0) A path from Chicago to Dallas: Chicago Kansas City Dallas (cost: 1029.0) A path from Chicago to Houston: Chicago Kansas City Dallas Houston (cost: 1268.0) Shortest path from Houston to Chicago: Houston Dallas Kansas City Chicago

All shortest paths from 3 are: A path from 3 to 0: 3 1 0 (cost: 5.0) A path from 3 to 1: 3 1 (cost: 3.0) A path from 3 to 2: 3 2 (cost: 4.0) A path from 3 to 3: 3 (cost: 0.0) A path from 3 to 4: 3 4 (cost: 6.0)

The program creates a weighted graph for Figure above in line 27. It then invokes the getShortestPath(graph1.getIndex("Chicago")) method to return a Path object that contains all shortest paths from Chicago. Invoking printAllPaths() on the ShortestPathTree object displays all the paths (line 30).

The graphical illustration of all shortest paths from Chicago is shown in Figure below. The shortest paths from Chicago to the cities are found in this order: Kansas City, New York, Boston, Denver, Dallas, Houston, Atlanta, Los Angeles, Miami, Seattle, and San Francisco.

Minimum Spanning Trees

Paul Ike — Thu, 05 Sep 2024 15:46:04 +0000

A minimum spanning tree of a graph is a spanning tree with the minimum total weights.

A graph may have many spanning trees. Suppose that the edges are weighted. A minimum spanning tree has the minimum total weights. For example, the trees in Figures below b, c, d are spanning trees for the graph in Figure a. The trees in Figures c and d are minimum spanning trees.

The problem of finding a minimum spanning tree has many applications. Consider a company with branches in many cities. The company wants to lease telephone lines to connect all the branches together. The phone company charges different amounts of money to connect different pairs of cities. There are many ways to connect all branches together. The cheapest way is to find a spanning tree with the minimum total rates.

Minimum Spanning Tree Algorithms

How do you find a minimum spanning tree? There are several well-known algorithms for doing so. This section introduces Prim’s algorithm. Prim’s algorithm starts with a spanning tree T that contains an arbitrary vertex. The algorithm expands the tree by repeatedly adding a vertex with the lowest-cost edge incident to a vertex already in the tree. Prim’s algorithm is a greedy algorithm, and it is described in code below.

Input: A connected undirected weighted G = (V, E) with non-negative weights
 Output: MST (a minimum spanning tree)
 1 MST minimumSpanningTree() {
 2 Let T be a set for the vertices in the spanning tree;
 3 Initially, add the starting vertex to T;
 4
 5 while (size of T < n) {
 6 Find u in T and v in V – T with the smallest weight
 7 on the edge (u, v), as shown in Figure 29.6;
 8 Add v to T and set parent[v] = u;
 9 }
10 }

The algorithm starts by adding the starting vertex into T. It then continuously adds a vertex (say v) from V – T into T. v is the vertex that is adjacent to the vertex in T with the smallest weight on the edge. For example, there are five edges connecting vertices in T and V – T as shown in Figure below, and (u, v) is the one with the smallest weight.

Consider the graph in Figure below. The algorithm adds the vertices to T in this order:

Add vertex 0 to T.
Add vertex 5 to T, since Edge(5, 0, 5) has the smallest weight among all edges incident to a vertex in T, as shown in Figure a. The arrow line from 0 to 5 indicates that 0 is the parent of 5.
Add vertex 1 to T, since Edge(1, 0, 6) has the smallest weight among all edges incident to a vertex in T, as shown in Figure b.
Add vertex 6 to T, since Edge(6, 1, 7) has the smallest weight among all edges incident to a vertex in T, as shown in Figure c.
Add vertex 2 to T, since Edge(2, 6, 5) has the smallest weight among all edges incident to a vertex in T, as shown in Figure d.
Add vertex 4 to T, since Edge(4, 6, 7) has the smallest weight among all edges incident to a vertex in T, as shown in Figure e.
Add vertex 3 to T, since Edge(3, 2, 8) has the smallest weight among all edges incident to a vertex in T, as shown in Figure f.

A minimum spanning tree is not unique. For example, both (c) and (d) in Figure below are minimum spanning trees for the graph in Figure a. However, if the weights are distinct, the graph has a unique minimum spanning tree.

Assume that the graph is connected and undirected. If a graph is not connected or directed, the algorithm will not work. You can modify the algorithm to find a spanning forest for any undirected graph. A spanning forest is a graph in which each connected component is a tree.

Refining Prim’s MST Algorithm

To make it easy to identify the next vertex to add into the tree, we use cost[v] to store the cost of adding a vertex v to the spanning tree T. Initially cost[s] is 0 for a starting vertex and assign infinity to cost[v] for all other vertices. The algorithm repeatedly finds a vertex u in V – T with the smallest cost[u] and moves u to T. The refined version of the alogrithm is given in code below.

Input: A connected undirected weighted G = (V, E) with non-negative weights
Output: a minimum spanning tree with the starting vertex s as the root
 1 MST getMinimumSpanngingTree(s) {
 2 Let T be a set that contains the vertices in the spanning tree;
 3 Initially T is empty;
 4 Set cost[s] = 0; and cost[v] = infinity for all other vertices in V;
 5
 6 while (size of T < n) {
 7 Find u not in T with the smallest cost[u];
 8 Add u to T;
 9 for (each v not in T and (u, v) in E)
10 if (cost[v] > w(u, v)) { // Adjust cost[v]
11 cost[v] = w(u, v); parent[v] = u;
12 }
13 }
14 }

Implementation of the MST Algorithm

The getMinimumSpanningTree(int v) method is defined in the WeightedGraph class. It returns an instance of the MST class, as shown in Figure below.

The MST class is defined as an inner class in the WeightedGraph class, which extends the Tree class, as shown in Figure below.

The Tree class was shown in Figure below. The MST class was implemented in lines 141–153 in WeightedGraph.java.

The refined version of the Prim’s algoruthm greatly simplifies the implementation. The getMinimumSpanningTree method was implemented using the refined version of the Prim’s algorithm in lines 99–138 in Listing 29.2. The getMinimumSpanningTree(int startingVertex) method sets cost[startingVertex] to 0 (line 105) and cost[v] to infinity for all other vertices (lines 102–104). The parent of startingVertex is set to -1 (line 108). T is a list that stores the vertices added into the spanning tree (line 111). We use a list for T rather than a set in order to record the order of the vertices added to T.

Initially, T is empty. To expand T, the method performs the following operations:

Find the vertex u with the smallest cost[u] (lines 118–123 and add it into T (line 125).
After adding u in T, update cost[v] and parent[v] for each v adjacent to u in V-T if cost[v] > w(u, v) (lines 129–134).

After a new vertex is added to T, totalWeight is updated (line 126). Once all vertices are added to T, an instance of MST is created (line 137). Note that the method will not work if the graph is not connected. However, you can modify it to obtain a partial MST.

The MST class extends the Tree class (line 141). To create an instance of MST, pass root, parent, T, and totalWeight (lines 144-145). The data fields root, parent, and searchOrder are defined in the Tree class, which is an inner class defined in AbstractGraph.

Note that testing whether a vertex i is in T by invoking T.contains(i) takes O(n) time, since T is a list. Therefore, the overall time complexity for this implemention is O(n3).

The code below gives a test program that displays minimum spanning trees for the graph in Figure below and the graph in Figure below a, respectively.

package demo;

public class TestMinimumSpanningTree {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1, 807}, {0, 3, 1331}, {0, 5, 2097},
                {1, 0, 807}, {1, 2, 381}, {1, 3, 1267},
                {2, 1, 381}, {2, 3, 1015}, {2, 4, 1663}, {2, 10, 1435},
                {3, 0, 1331}, {3, 1, 1267}, {3, 2, 1015}, {3, 4, 599}, {3, 5, 1003},
                {4, 2, 1663}, {4, 3, 599}, {4, 5, 533}, {4, 7, 1260}, {4, 8, 864}, {4, 10, 496},
                {5, 0, 2097}, {5, 3, 1003}, {5, 4, 533}, {5, 6, 983}, {5, 7, 787},
                {6, 5, 983}, {6, 7, 214},
                {7, 4, 1260}, {7, 5, 787}, {7, 6, 214}, {7, 8, 888},
                {8, 4, 864}, {8, 7, 888}, {8, 9, 661}, {8, 10, 781}, {8, 11, 810},
                {9, 8, 661}, {9, 11, 1187},
                {10, 2, 1435}, {10, 4, 496}, {10, 8, 781}, {10, 11, 239},
                {11, 8, 810}, {11, 9, 1187}, {11, 10, 239}
        };

        WeightedGraph<String> graph1 = new WeightedGraph<>(vertices, edges);
        WeightedGraph<String>.MST tree1 = graph1.getMinimumSpanningTree();
        System.out.println("Total weight is " + tree1.getTotalWeight());
        tree1.printTree();

        edges = new int[][]{
            {0, 1, 2}, {0, 3, 8},
            {1, 0, 2}, {1, 2, 7}, {1, 3, 3},
            {2, 1, 7}, {2, 3, 4}, {2, 4, 5},
            {3, 0, 8}, {3, 1, 3}, {3, 2, 4}, {3, 4, 6},
            {4, 2, 5}, {4, 3, 6}
        };

        WeightedGraph<Integer> graph2 = new WeightedGraph<>(edges, 5);
        WeightedGraph<Integer>.MST tree2 = graph2.getMinimumSpanningTree(1);
        System.out.println("\nTotal weight is " + tree2.getTotalWeight());
        tree2.printTree();
    }

}

Total weight is 6513.0 Root is: Seattle Edges: (Seattle, San Francisco) (San Francisco, Los Angeles) (Los Angeles, Denver) (Denver, Kansas City) (Kansas City, Chicago) (New York, Boston) (Chicago, New York) (Dallas, Atlanta) (Atlanta, Miami) (Kansas City, Dallas) (Dallas, Houston)

Total weight is 14.0 Root is: 1 Edges: (1, 0) (3, 2) (1, 3) (2, 4)

The program creates a weighted graph for Figure above in line 27. It then invokes getMinimumSpanningTree() (line 28) to return an MST that represents a minimum spanning tree for the graph. Invoking printTree() (line 30) on the MST object displays the edges in the tree. Note that MST is a subclass of Tree. The printTree() method is defined in the Tree class.

The graphical illustration of the minimum spanning tree is shown in Figure below. The vertices are added to the tree in this order: Seattle, San Francisco, Los Angeles, Denver, Kansas City, Dallas, Houston, Chicago, New York, Boston, Atlanta, and Miami.

The WeightedGraph Class

Paul Ike — Thu, 05 Sep 2024 15:26:26 +0000

The WeightedGraph class extends AbstractGraph.
The preceding chapter designed the Graph interface, the AbstractGraph class, and the UnweightedGraph class for modeling graphs. Following this pattern, we design WeightedGraph as a subclass of AbstractGraph, as shown in Figure below.

WeightedGraph simply extends AbstractGraph with five constructors for creating concrete WeightedGraph instances. WeightedGraph inherits all methods from AbstractGraph, overrides the clear and addVertex methods, implements a new addEdge method for adding a weighted edge, and also introduces new methods for obtaining minimum spanning trees and for finding all single-source shortest paths. Minimum spanning trees and shortest paths will be introduced in Sections Minimum spanning trees and shortest paths, respectively.

The code below implements WeightedGraph. Edge adjacency lists (lines 38–63) are used internally to store adjacent edges for a vertex. When a WeightedGraph is constructed, its edge adjacency lists are created (lines 47 and 57). The methods getMinimumSpanningTree() (lines 99–138) and getShortestPath() (lines 156–197) will be introduced in upcoming sections.

package demo;
import java.util.*;

public class WeightedGraph<V> extends AbstractGraph<V> {
    /** Construct an empty */
    public WeightedGraph() {}

    /** Construct a WeightedGraph from vertices and edged in arrays */
    public WeightedGraph(V[] vertices, int[][] edges) {
        createWeightedGraph(java.util.Arrays.asList(vertices), edges);
    }

     /** Construct a WeightedGraph from vertices and edges in list */
    public WeightedGraph(int[][] edges, int numberOfVertices) {
        List<V> vertices = new ArrayList<>();
        for (int i = 0; i < numberOfVertices; i++)
            vertices.add((V)(new Integer(i)));

        createWeightedGraph(vertices, edges);
    }

    /** Construct a WeightedGraph for vertices 0, 1, 2 and edge list */
    public WeightedGraph(List<V> vertices, List<WeightedEdge> edges) {
        createWeightedGraph(vertices, edges);
    }

    /** Construct a WeightedGraph from vertices 0, 1, and edge array */
    public WeightedGraph(List<WeightedEdge> edges, int numberOfVertices) {
        List<V> vertices = new ArrayList<>();
        for (int i = 0; i < numberOfVertices; i++)
            vertices.add((V)(new Integer(i)));

        createWeightedGraph(vertices, edges);
    }

    /** Create adjacency lists from edge arrays */
    private void createWeightedGraph(List<V> vertices, int[][] edges) {
        this.vertices = vertices;

        for (int i = 0; i < vertices.size(); i++) {
            neighbors.add(new ArrayList<Edge>()); // Create a list for vertices
        }

        for (int i = 0; i < edges.length; i++) {
            neighbors.get(edges[i][0]).add(new WeightedEdge(edges[i][0], edges[i][1], edges[i][2]));
        }
    }

    /** Create adjacency lists from edge lists */
    private void createWeightedGraph(List<V> vertices, List<WeightedEdge> edges) {
        this.vertices = vertices;

        for (int i = 0; i < vertices.size(); i++) {
            neighbors.add(new ArrayList<Edge>()); // Create a list for vertices
        }

        for (WeightedEdge edge: edges) {
            neighbors.get(edge.u).add(edge); // Add an edge into the list
        }
    }

    /** Return the weight on the edge (u, v) */
    public double getWeight(int u, int v) throws Exception {
        for (Edge edge : neighbors.get(u)) {
            if (edge.v == v) {
                return ((WeightedEdge)edge).weight;
            }
        }

        throw new Exception("Edge does not exit");
    }

    /** Display edges with weights */
    public void printWeightedEdges() {
        for (int i = 0; i < getSize(); i++) {
            System.out.print(getVertex(i) + " (" + i + "): ");
            for (Edge edge : neighbors.get(i)) {
                System.out.print("(" + edge.u + ", " + edge.v + ", " + ((WeightedEdge)edge).weight + ") ");
            }

            System.out.println();
        }
    }

    /** Add edges to the weighted graph */
    public boolean addEdge(int u, int v, double weight) {
        return addEdge(new WeightedEdge(u, v, weight));
    }

    /** Get a minimum spanning tree rooted at vertex 0 */
    public MST getMinimumSpanningTree() {
        return getMinimumSpanningTree(0);
    }

    /** Get a minimum spanning tree rooted at a specified vertex */
    public MST getMinimumSpanningTree(int startingVertex) {
        // cost[v] stores the cost by adding v to the tree
        double[] cost = new double[getSize()];
        for (int i = 0; i < cost.length; i++) {
            cost[i] = Double.POSITIVE_INFINITY; // Initial cost
        }
        cost[startingVertex] = 0; // Cost of source is 0

        int[] parent = new int[getSize()]; // Parent of a vertex
        parent[startingVertex] = -1; // startingVertex is the root
        double totalWeight = 0; // Total weight of the tree thus far

        List<Integer> T = new ArrayList<>();

        // Expand T
        while (T.size() < getSize()) {
            // Find smallest cost v in V - T
            int u = -1; // Vertex to be determined
            double currentMinCost = Double.POSITIVE_INFINITY;
            for (int i = 0; i < getSize(); i++) {
                if (!T.contains(i) && cost[i] < currentMinCost) {
                    currentMinCost = cost[i];
                    u = i;
                }
            }

            T.add(u); // Add a new vertex to T
            totalWeight += cost[u]; // Add cost[u] to the tree

            // Adjust cost[v] for v that is adjacent to u and v in V - T
            for (Edge e : neighbors.get(u)) {
                if (!T.contains(e.v) && cost[e.v] > ((WeightedEdge)e).weight) {
                    cost[e.v] = ((WeightedEdge)e).weight;
                    parent[e.v] = u;
                }
            }
        } // End of while

        return new MST(startingVertex, parent, T, totalWeight);
    }

    /** MST is an inner class in WeightedGraph */
    public class MST extends Tree {
        private double totalWeight; // Total weight of all edges in the tree

        public MST(int root, int[] parent, List<Integer> searchOrder, double totalWeight) {
            super(root, parent, searchOrder);
            this.totalWeight = totalWeight;
        }

        public double getTotalWeight() {
            return totalWeight;
        }
    }

    /** Find single source shortest paths */
    public ShortestPathTree getShortestPath(int sourceVertex) {
        // cost[v] stores the cost of the path from v to the source
        double[] cost = new double[getSize()];
        for (int i = 0; i < cost.length; i++) {
            cost[i] = Double.POSITIVE_INFINITY; // Initial cost set to infinity
        }
        cost[sourceVertex] = 0; // Cost of source is 0

        // parent[v] stores the previous vertex of v in the path
        int[] parent = new int[getSize()];
        parent[sourceVertex] = -1; // The parent of source is set to -1

        // T stores the vertices whose path found so far
        List<Integer> T = new ArrayList<>();

        // Expand T
        while (T.size() < getSize()) {
            // Find smallest cost v in V - T
            int u = -1; // Vertex to be determined
            double currentMinCost = Double.POSITIVE_INFINITY;
            for (int i = 0; i < getSize(); i++) {
                if (!T.contains(i) && cost[i] < currentMinCost) {
                    currentMinCost = cost[i];
                    u = i;
                }
            }

            T.add(u); // Add a new vertex to T

            // Adjust cost[v] for v that is adjacent to u and v in V - T
            for (Edge e : neighbors.get(u)) {
                if (!T.contains(e.v) && cost[e.v] > cost[u] + ((WeightedEdge)e).weight) {
                    cost[e.v] = cost[u] + ((WeightedEdge)e).weight;
                    parent[e.v] = u;
                }
            }
        } // End of while

        // Create a ShortestPathTree
        return new ShortestPathTree(sourceVertex, parent, T, cost);
    }

    /** ShortestPathTree is an inner class in WeightedGraph */
    public class ShortestPathTree extends Tree {
        private double[] cost; // cost[v] is the cost from v to source

        /** Construct a path */
        public ShortestPathTree(int source, int[] parent, List<Integer> searchOrder, double[] cost) {
            super(source, parent, searchOrder);
            this.cost = cost;
        }

        /** Return the cost for a path from the root to vertex v */
        public double getCost(int v) {
            return cost[v];
        }

        /** Print paths from all vertices to the source */
        public void printAllPaths() {
            System.out.println("All shortest paths from " + vertices.get(getRoot()) + " are:");
            for (int i = 0; i < cost.length; i++) {
                printPath(i); // Print a path from i to the source
                System.out.println("(cost: " + cost[i] + ")"); // Path cost
            }
        }
    }
}

The WeightedGraph class extends the AbstractGraph class (line 3). The properties vertices and neighbors in AbstractGraph are inherited in WeightedGraph.neighbors is a list. Each element is the list is another list that contains edges. For unweighted graph, each edge is an instance of AbstractGraph.Edge. For a weighted graph, each edge is an instance of WeightedEdge. WeightedEdge is a subtype of Edge. So you can add a weighted edge into neighbors.get(i) for a weighted graph (line 47).

The code below gives a test program that creates a graph for the one in Figure below and another graph for the one in Figure below a.

package demo;

public class TestWeightedGraph {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1, 807}, {0, 3, 1331}, {0, 5, 2097},
                {1, 0, 807}, {1, 2, 381}, {1, 3, 1267},
                {2, 1, 381}, {2, 3, 1015}, {2, 4, 1663}, {2, 10, 1435},
                {3, 0, 1331}, {3, 1, 1267}, {3, 2, 1015}, {3, 4, 599}, {3, 5, 1003},
                {4, 2, 1663}, {4, 3, 599}, {4, 5, 533}, {4, 7, 1260}, {4, 8, 864}, {4, 10, 496},
                {5, 0, 2097}, {5, 3, 1003}, {5, 4, 533}, {5, 6, 983}, {5, 7, 787},
                {6, 5, 983}, {6, 7, 214},
                {7, 4, 1260}, {7, 5, 787}, {7, 6, 214}, {7, 8, 888},
                {8, 4, 864}, {8, 7, 888}, {8, 9, 661}, {8, 10, 781}, {8, 11, 810},
                {9, 8, 661}, {9, 11, 1187},
                {10, 2, 1435}, {10, 4, 496}, {10, 8, 781}, {10, 11, 239},
                {11, 8, 810}, {11, 9, 1187}, {11, 10, 239}
        };

        WeightedGraph<String> graph1 = new WeightedGraph<>(vertices, edges);
        System.out.println("The number of vertices in graph1: " + graph1.getSize());
        System.out.println("The vertex with index 1 is " + graph1.getVertex(1));
        System.out.println("The index for Miami is " + graph1.getIndex("Miami"));
        System.out.println("The edges for graph1:");
        graph1.printWeightedEdges();

        edges = new int[][] {
            {0, 1, 2}, {0, 3, 8},
            {1, 0, 2}, {1, 2, 7}, {1, 3, 3},
            {2, 1, 7}, {2, 3, 4}, {2, 4, 5},
            {3, 0, 8}, {3, 1, 3}, {3, 2, 4}, {3, 4, 6},
            {4, 2, 5}, {4, 3, 6}
        };
        WeightedGraph<Integer> graph2 = new WeightedGraph<>(edges, 5);
        System.out.println("\nThe edges for graph2:");
        graph2.printWeightedEdges();
    }
}

The number of vertices in graph1: 12 The vertex with index 1 is San Francisco The index for Miami is 9 The edges for graph1: Vertex 0: (0, 1, 807) (0, 3, 1331) (0, 5, 2097) Vertex 1: (1, 2, 381) (1, 0, 807) (1, 3, 1267) Vertex 2: (2, 1, 381) (2, 3, 1015) (2, 4, 1663) (2, 10, 1435) Vertex 3: (3, 4, 599) (3, 5, 1003) (3, 1, 1267) (3, 0, 1331) (3, 2, 1015) Vertex 4: (4, 10, 496) (4, 8, 864) (4, 5, 533) (4, 2, 1663) (4, 7, 1260) (4, 3, 599) Vertex 5: (5, 4, 533) (5, 7, 787) (5, 3, 1003) (5, 0, 2097) (5, 6, 983) Vertex 6: (6, 7, 214) (6, 5, 983) Vertex 7: (7, 6, 214) (7, 8, 888) (7, 5, 787) (7, 4, 1260) Vertex 8: (8, 9, 661) (8, 10, 781) (8, 4, 864) (8, 7, 888) (8, 11, 810) Vertex 9: (9, 8, 661) (9, 11, 1187) Vertex 10: (10, 11, 239) (10, 4, 496) (10, 8, 781) (10, 2, 1435) Vertex 11: (11, 10, 239) (11, 9, 1187) (11, 8, 810)

The edges for graph2: Vertex 0: (0, 1, 2) (0, 3, 8) Vertex 1: (1, 0, 2) (1, 2, 7) (1, 3, 3) Vertex 2: (2, 3, 4) (2, 1, 7) (2, 4, 5) Vertex 3: (3, 1, 3) (3, 4, 6) (3, 2, 4) (3, 0, 8) Vertex 4: (4, 2, 5) (4, 3, 6)

The program creates graph1 for the graph in Figure above in lines 3–27. The vertices for graph1 are defined in lines 3–5. The edges for graph1 are defined in lines 7–24. The edges are represented using a two-dimensional array. For each row i in the array, edges[i][0] and edges[i][1] indicate that there is an edge from vertex edges[i][0] to vertex edges[i][1] and the weight for the edge is edges[i][2]. For example, {0, 1, 807} (line 8) represents the edge from vertex 0 (edges[0][0]) to vertex 1 (edges[0][1]) with weight 807 (edges[0][2]). {0, 5, 2097} (line 8) represents the edge from vertex 0 (edges[2][0]) to vertex 5 (edges[2][1]) with weight 2097 (edges[2][2]). Line 35 invokes the printWeightedEdges() method on graph1 to display all edges in graph1.

The program creates the edges for graph2 for the graph in Figure above a in lines 37–44. Line 46 invokes the printWeightedEdges() method on graph2 to display all edges in graph2.

Representing Weighted Graphs

Paul Ike — Thu, 05 Sep 2024 15:08:03 +0000

Weighted edges can be stored in adjacency lists.

There are two types of weighted graphs: vertex weighted and edge weighted. In a vertex-weighted graph, each vertex is assigned a weight. In an edge-weighted graph, each edge is assigned a weight. Of the two types, edge-weighted graphs have more applications. This chapter considers edge-weighted graphs.

Weighted graphs can be represented in the same way as unweighted graphs, except that you have to represent the weights on the edges. As with unweighted graphs, the vertices in weighted graphs can be stored in an array. This section introduces three representations for the edges in weighted graphs.

Representing Weighted Edges: Edge Array

Weighted edges can be represented using a two-dimensional array. For example, you can store all the edges in the graph in Figure below (a) using the array in Figure below (b).

Weights can be of any type: Integer, Double, BigDecimal, and so on. You can use a two-dimensional array of the Object type to represent weighted edges as follows:

Object[][] edges = { {new Integer(0), new Integer(1), new SomeTypeForWeight(2)}, {new Integer(0), new Integer(3), new SomeTypeForWeight(8)}, ... };

Weighted Adjacency Matrices

Assume that the graph has n vertices. You can use a two-dimensional n * n matrix, say weights, to represent the weights on edges. weights[i][j] represents the weight on edge (i, j). If vertices i and j are not connected, weights[i][j] is null. For example, the weights in the graph in Figure above (a) can be represented using an adjacency matrix as follows:

Adjacency Lists

Another way to represent the edges is to define edges as objects. The AbstractGraph.Edge class was defined to represent an unweighted edge in AbstractGraph.java. For weighted edges, we define the WeightedEdge class as shown in code below.

AbstractGraph.Edge is an inner class defined in the AbstractGraph class. It represents an edge from vertex u to v. WeightedEdge extends AbstractGraph.Edge with a new property weight.

To create a WeightedEdge object, use new WeightedEdge(i, j, w), where w is the weight on edge (i, j). Often you need to compare the weights of the edges. For this reason, the WeightedEdge class implements the Comparable interface.

For unweighted graphs, we use adjacency lists to represent edges. For weighted graphs, we still use adjacency lists, the adjacency lists for the vertices in the graph in Figure below a can be represented as follows:

java.util.List<WeightedEdge>[] list = new java.util.List[5];

list[i] stores all edges adjacent to vertex i.

For flexibility, we will use an array list rather than a fixed-sized array to represent list as follows:

List<List<WeightedEdge>> list = new java.util.ArrayList<>();

Weighted Graphs and Applications

Paul Ike — Thu, 05 Sep 2024 14:50:39 +0000

A graph is a weighted graph if each edge is assigned a weight. Weighted graphs have many practical applications.

Figure above assumes that the graph represents the number of flights among cities. You can apply the BFS to find the fewest number of flights between two cities. Assume that the edges represent the driving distances among the cities as shown in Figure below. How do you find the minimal total distances for connecting all cities? How do you find the shortest path between two cities? This chapter will address these questions. The former is known as the minimum spanning tree (MST) problem and the latter as the shortest path problem.

The preceding chapter introduced the concept of graphs. You learned how to represent edges using edge arrays, edge lists, adjacency matrices, and adjacency lists, and how to model a graph using the Graph interface, the AbstractGraph class, and the UnweightedGraph class. The preceding chapter also introduced two important techniques for traversing graphs: depth-first search and breadth-first search, and applied traversal to solve practical problems. The following posts will introduce weighted graphs. You will learn the algorithm for finding a minimum spanning tree in post and the algorithm for finding shortest paths in post .

Case Study: The Nine Tails Problem

Paul Ike — Fri, 09 Aug 2024 16:51:32 +0000

The nine tails problem can be reduced to the shortest path problem.
The nine tails problem is as follows. Nine coins are placed in a three-by-three matrix with some face up and some face down. A legal move is to take a coin that is face up and reverse it, together with the coins adjacent to it (this does not include coins that are diagonally adjacent). Your task is to find the minimum number of moves that lead to all coins being face down. For example, start with the nine coins as shown in Figure below (a). After you flip the second coin in the last row, the nine coins are now as shown in Figure below (b). After you flip the second coin in the first row, the nine coins are all face down, as shown in Figure below (c).

We will write a program that prompts the user to enter an initial state of the nine coins and displays the solution, as shown in the following sample run.

Enter the initial nine coins Hs and Ts: HHHTTTHHH The steps to flip the coins are HHH TTT HHH HHH THT TTT TTT TTT TTT

Each state of the nine coins represents a node in the graph. For example, the three states in Figure above correspond to three nodes in the graph. For convenience, we use a 3 * 3 matrix to represent all nodes and use 0 for heads and 1 for tails. Since there are nine cells and each cell is either 0 or 1, there are a total of 2^9 (512) nodes, labeled 0, 1, . . . , and 511, as shown in Figure below.

We assign an edge from node v to u if there is a legal move from u to v. Figure below shows a partial graph. Note there is an edge from 511 to 47, since you can flip a cell in node 47 to become node 511.

The last node in Figure below represents the state of nine face-down coins. For convenience, we call this last node the target node. Thus, the target node is labeled 511. Suppose the initial state of the nine tails problem corresponds to the node s. The problem is reduced to finding a shortest path from node s to the target node, which is equivalent to finding a shortest path from node s to the target node in a BFS tree rooted at the target node.

Now the task is to build a graph that consists of 512 nodes labeled 0, 1, 2, . . . , 511, and edges among the nodes. Once the graph is created, obtain a BFS tree rooted at node 511. From the BFS tree, you can find a shortest path from the root to any vertex. We will create a class named NineTailModel, which contains the method to get a shortest path from the target node to any other node. The class UML diagram is shown in Figure below.

Visually, a node is represented in a 3 * 3 matrix with the letters H and T. In our program, we use a single-dimensional array of nine characters to represent a node. For example, the node for vertex 1 in Figure below is represented as {'H', 'H', 'H', 'H', 'H', 'H', 'H', 'H', 'T'} in the array.

The getEdges() method returns a list of Edge objects.

The getNode(index) method returns the node for the specified index. For example, getNode(0) returns the node that contains nine Hs. getNode(511) returns the node that contains nine Ts. The getIndex(node) method returns the index of the node.

Note that the data field tree is defined as protected so that it can be accessed from the WeightedNineTail subclass.

The getFlippedNode(char[] node, int position) method flips the node at the specified position and its adjacent positions. This method returns the index of the new node.

The position is a value from 0 to 8, which points to a coin in the node, as shown in the following figure.

For example, for node 56 in Figure below, flip it at position 0, and you will get node 51. If you flip node 56 at position 1, you will get node 47.

The flipACell(char[] node, int row, int column) method flips a node at the specified row and column. For example, if you flip node 56 at row 0 and column 0, the new node is 408. If you flip node 56 at row 2 and column 0, the new node is 30.

The code below shows the source code for NineTailModel.java.

import java.util.*;

public class NineTailModel {
    public final static int NUMBER_OF_NODES = 512;
    protected AbstractGraph<Integer>.Tree tree; // Define a tree

    /** Construct a model */
    public NineTailModel() {
        // Create edges
        List<AbstractGraph.Edge> edges = getEdges();

        // Create a graph
        UnweightedGraph<Integer> graph = new UnweightedGraph<>(edges, NUMBER_OF_NODES);

        // Obtain a BSF tree rooted at the target node
        tree = graph.bfs(511);
    }

    /** Create all edges for the graph */
    private List<AbstractGraph.Edge> getEdges() {
        List<AbstractGraph.Edge> edges = new ArrayList<>(); // Store edges

        for (int u = 0; u < NUMBER_OF_NODES; u++) {
            for (int k = 0; k < 9; k++) {
                char[] node = getNode(u); // Get the node for vertex u
                if (node[k] == 'H') {
                    int v = getFlippedNode(node, k);
                    // Add edge (v, u) for a legal move from node u to node v
                    edges.add(new AbstractGraph.Edge(v, u));
                }
            }
        }

        return edges;
    }

    public static int getFlippedNode(char[] node, int position) {
        int row = position / 3;
        int column = position % 3;

        flipACell(node, row, column);
        flipACell(node, row - 1, column);
        flipACell(node, row + 1, column);
        flipACell(node, row, column - 1);
        flipACell(node, row, column + 1);

        return getIndex(node);
    }

    public static void flipACell(char[] node, int row, int column) {
        if (row >= 0 && row <= 2 && column >= 0 && column <= 2) {
            // Within the boundary
            if (node[row * 3 + column] == 'H')
                node[row * 3 + column] = 'T'; // Flip from H to T
            else
                node[row * 3 + column] = 'H'; // Flip from T to H
            }
    }

    public static int getIndex(char[] node) {
        int result = 0;

        for (int i = 0; i < 9; i++)
            if (node[i] == 'T')
                result = result * 2 + 1;
            else
                result = result * 2 + 0;

        return result;
    }

    public static char[] getNode(int index) {
        char[] result = new char[9];

        for (int i = 0; i < 9; i++) {
            int digit = index % 2;
            if (digit == 0)
                result[8 - i] = 'H';
            else
                result[8 - i] = 'T';
            index = index / 2;
        }

        return result;
    }

    public List<Integer> getShortestPath(int nodeIndex) {
        return tree.getPath(nodeIndex);
    }

    public static void printNode(char[] node) {
        for (int i = 0; i < 9; i++)
            if (i % 3 != 2)
                System.out.print(node[i]);
            else
                System.out.println(node[i]);

        System.out.println();
    }
}

The constructor (lines 8–18) creates a graph with 512 nodes, and each edge corresponds to the move from one node to the other (line 10). From the graph, a BFS tree rooted at the target node 511 is obtained (line 17).

To create edges, the getEdges method (lines 21–37) checks each node u to see if it can be flipped to another node v. If so, add (v, u) to the Edge list (line 31). The getFlippedNode(node, position) method finds a flipped node by flipping an H cell and its neighbors in a node (lines 43–47). The flipACell(node, row, column) method actually flips an H cell and its neighbors in a node (lines 52–60).

The getIndex(node) method is implemented in the same way as converting a binary number to a decimal number (lines 62–72). The getNode(index) method returns a node consisting of the letters H and T (lines 74–87).

The getShortestpath(nodeIndex) method invokes the getPath(nodeIndex)
method to get a vertices in a shortest path from the specified node to the target node
(lines 89–91).

The printNode(node) method displays a node on the console (lines 93–101).

The code below gives a program that prompts the user to enter an initial node and displays the steps to reach the target node.

import java.util.Scanner;

public class NineTail {

    public static void main(String[] args) {
        // Prompt the user to enter nine coins' Hs and Ts
        System.out.print("Enter the initial nine coins Hs and Ts: ");
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        char[] initialNode = s.toCharArray();

        NineTailModel model = new NineTailModel();
        java.util.List<Integer> path = model.getShortestPath(NineTailModel.getIndex(initialNode));

        System.out.println("The steps to flip the coins are ");
        for (int i = 0; i < path.size(); i++)
            NineTailModel.printNode(NineTailModel.getNode(path.get(i).intValue()));
    }

}

The program prompts the user to enter an initial node with nine letters with a combination of Hs and Ts as a string in line 8, obtains an array of characters from the string (line 9), creates a graph model to get a BFS tree (line 11), obtains a shortest path from the initial node to the
target node (lines 12–13), and displays the nodes in the path (lines 16–18).

Breadth-First Search (BFS)

Paul Ike — Fri, 09 Aug 2024 16:17:10 +0000

The breadth-first search of a graph visits the vertices level by level. The first level consists of the starting vertex. Each next level consists of the vertices adjacent to the vertices in the preceding level. The breadth-first traversal of a graph is like the breadth-first traversal of a tree discussed in Tree Traversal. With breadth-first traversal of a tree, the nodes are visited level by level. First the root is visited, then all the children of the root, then the grandchildren of the root, and so on. Similarly, the breadth-first search of a graph first visits a vertex, then all its adjacent vertices, then all the vertices adjacent to those vertices, and so on. To ensure that each vertex is visited only once, it skips a vertex if it has already been visited.

Breadth-First Search Algorithm

The algorithm for the breadth-first search starting from vertex v in a graph is described in the code below.

Input: G = (V, E) and a starting vertex v Output: a BFS tree rooted at v 1 Tree bfs(vertex v) { 2 create an empty queue for storing vertices to be visited; 3 add v into the queue; 4 mark v visited; 5 6 while (the queue is not empty) { 7 dequeue a vertex, say u, from the queue; 8 add u into a list of traversed vertices; 9 for each neighbor w of u 10 if w has not been visited { 11 add w into the queue; 12 set u as the parent for w in the tree; 13 mark w visited; 14 } 15 } 16 }

Consider the graph in Figure below (a). Suppose you start the breadth-first search from vertex 0. First visit 0, then visit all its neighbors, 1, 2, and 3, as shown in Figure below (b). Vertex 1 has three neighbors: 0, 2, and 4. Since 0 and 2 have already been visited, you will now visit just 4, as shown in Figure below (c). Vertex 2 has three neighbors, 0, 1, and 3, which have all been visited. Vertex 3 has three neighbors, 0, 2, and 4, which have all been visited. Vertex 4 has two neighbors, 1 and 3, which have all been visited. Hence, the search ends.

Since each edge and each vertex is visited only once, the time complexity of the bfs method is O(|E| + |V|), where |E| denotes the number of edges and |V| the number of vertices.

Implementation of Breadth-First Search

The bfs(int v) method is defined in the Graph interface and implemented in the AbstractGraph.java class (lines 197–222). It returns an instance of the Tree class with vertex v as the root. The method stores the vertices searched in the list searchOrder (line 198), the parent of each vertex in the array parent (line 199), uses a linked list for a queue (lines 203–204), and uses the isVisited array to indicate whether a vertex has been visited (line 207). The search starts from vertex v. v is added to the queue in line 206 and is marked as visited (line 207). The method now examines each vertex u in the queue (line 210) and adds it to searchOrder (line 211). The method adds each unvisited neighbor e.v of u to the queue (line 214), sets its parent to u (line 215), and marks it as visited (line 216).

The code below gives a test program that displays a BFS for the graph in Figure above starting from Chicago.

public class TestBFS {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<String> graph = new UnweightedGraph<>(vertices, edges);
        AbstractGraph<String>.Tree bfs = graph.bfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = bfs.getSearchOrder();
        System.out.println(bfs.getNumberOfVerticesFound() + " vertices are searched in this BFS order:");
        for(int i = 0; i < searchOrders.size(); i++)
            System.out.print(graph.getVertex(searchOrders.get(i)) + " ");
        System.out.println();

        for(int i = 0; i < searchOrders.size(); i++)
            if(bfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(bfs.getParent(i)));
    }

}

12 vertices are searched in this order: Chicago Seattle Denver Kansas City Boston New York San Francisco Los Angeles Atlanta Dallas Miami Houston parent of Seattle is Chicago parent of San Francisco is Seattle parent of Los Angeles is Denver parent of Denver is Chicago parent of Kansas City is Chicago parent of Boston is Chicago parent of New York is Chicago parent of Atlanta is Kansas City parent of Miami is Atlanta parent of Dallas is Kansas City parent of Houston is Atlanta

Applications of the BFS

Many of the problems solved by the DFS can also be solved using the BFS. Specifically, the BFS can be used to solve the following problems:

Detecting whether a graph is connected. A graph is connected if there is a path between any two vertices in the graph.
Detecting whether there is a path between two vertices.
Finding a shortest path between two vertices. You can prove that the path between the root and any node in the BFS tree is a shortest path between the root and the node.
Finding all connected components. A connected component is a maximal connected subgraph in which every pair of vertices are connected by a path.
Detecting whether there is a cycle in the graph.
Finding a cycle in the graph.
Testing whether a graph is bipartite. (A graph is bipartite if the vertices of the graph can be divided into two disjoint sets such that no edges exist between vertices in the same set.)

Case Study: The Connected Circles Problem

Paul Ike — Fri, 09 Aug 2024 15:40:45 +0000

The connected circles problem is to determine whether all circles in a two-dimensional plane are connected. This problem can be solved using a depth-first traversal. The DFS algorithm has many applications. This section applies the DFS algorithm to solve the connected circles problem.

In the connected circles problem, you determine whether all the circles in a two-dimensional plane are connected. If all the circles are connected, they are painted as filled circles, as shown in Figure below (a). Otherwise, they are not filled, as shown in Figure below (b).

We will write a program that lets the user create a circle by clicking a mouse in a blank area that is not currently covered by a circle. As the circles are added, the circles are repainted filled if they are connected or unfilled otherwise.

We will create a graph to model the problem. Each circle is a vertex in the graph. Two circles are connected if they overlap. We apply the DFS in the graph, and if all vertices are found in the depth-first search, the graph is connected.

The program is given in the code below.

import javafx.application.Application;
import javafx.geometry.Point2D;
import javafx.scene.Node;
import javafx.scene.Scene;
import javafx.scene.layout.Pane;
import javafx.scene.paint.Color;
import javafx.scene.shape.Circle;
import javafx.stage.Stage;

public class ConnectedCircles extends Application {
    @Override // Override the start method in the Application class
    public void start(Stage primaryStage) {
        // Create a scene and place it in the stage
        Scene scene = new Scene(new CirclePane(), 450, 350);
        primaryStage.setTitle("ConnectedCircles"); // Set the stage title
        primaryStage.setScene(scene); // Place the scene in the stage
        primaryStage.show(); // Display the stage
    }

    public static void main(String[] args) {
        Application.launch(args);
    }

    /** Pane for displaying circles */
    class CirclePane extends Pane {
        public CirclePane() {
            this.setOnMouseClicked(e -> {
                if (!isInsideACircle(new Point2D(e.getX(), e.getY()))) {
                    // Add a new circle
                    getChildren().add(new Circle(e.getX(), e.getY(), 20));
                    colorIfConnected();
                }
            });
        }

        /** Returns true if the point is inside an existing circle */
        private boolean isInsideACircle(Point2D p) {
            for (Node circle: this.getChildren())
                if (circle.contains(p))
                    return true;

            return false;
        }

        /** Color all circles if they are connected */
        private void colorIfConnected() {
            if (getChildren().size() == 0)
                return; // No circles in the pane

            // Build the edges
            java.util.List<AbstractGraph.Edge> edges = new java.util.ArrayList<>();
            for (int i = 0; i < getChildren().size(); i++)
                for (int j = i + 1; j < getChildren().size(); j++)
                    if (overlaps((Circle)(getChildren().get(i)), (Circle)(getChildren().get(j)))) {
                        edges.add(new AbstractGraph.Edge(i, j));
                        edges.add(new AbstractGraph.Edge(j, i));
                    }

            // Create a graph with circles as vertices
            Graph<Node> graph = new UnweightedGraph<>((java.util.List<Node>)getChildren(), edges);
            AbstractGraph<Node>.Tree tree = graph.dfs(0); // a DFS tree
            boolean isAllCirclesConnected = getChildren().size() == tree.getNumberOfVerticesFound();

            for (Node circle: getChildren()) {
                if (isAllCirclesConnected) { // All circles are connected
                    ((Circle)circle).setFill(Color.RED);
                }
                else {
                    ((Circle)circle).setStroke(Color.BLACK);
                    ((Circle)circle).setFill(Color.WHITE);
                }
            }
        }
    }

    public static boolean overlaps(Circle circle1, Circle circle2) {
        return new Point2D(circle1.getCenterX(), circle1.getCenterY()).distance(circle2.getCenterX(), circle2.getCenterY()) <= circle1.getRadius() + circle2.getRadius();
    }
}

The JavaFX Circle class contains the data fields x, y, and radius, which specify the circle’s center location and radius. It also defines the contains for testing if a point is in the circle. The overlaps method (lines 76–80) checks whether two circles overlap.

When the user clicks the mouse outside of any existing circle, a new circle is created centered at the mouse point and the circle is added to the pane (line 26).

To detect whether the circles are connected, the program constructs a graph (lines 46–59). The circles are the vertices of the graph. The edges are constructed in lines 49–55. Two circle vertices are connected if they overlap (line 51). The DFS of the graph results in a tree (line 60). The tree’s getNumberOfVerticesFound() returns the number of vertices searched. If it is equal to the number of circles, all circles are connected (lines 61–62).

Depth-First Search (DFS)

Paul Ike — Fri, 09 Aug 2024 15:30:42 +0000

The depth-first search of a graph starts from a vertex in the graph and visits all vertices in the graph as far as possible before backtracking.
The depth-first search of a graph is like the depth-first search of a tree discussed in Tree Traversal, Tree Traversal. In the case of a tree, the search starts from the root. In a graph, the search can start from any vertex.

A depth-first search of a tree first visits the root, then recursively visits the subtrees of the root. Similarly, the depth-first search of a graph first visits a vertex, then it recursively visits all the vertices adjacent to that vertex. The difference is that the graph may contain cycles, which could lead to an infinite recursion. To avoid this problem, you need to track the vertices that have already been visited.

The search is called depth-first because it searches “deeper” in the graph as much as possible. The search starts from some vertex v. After visiting v, it visits an unvisited neighbor of v. If v has no unvisited neighbor, the search backtracks to the vertex from which it reached v. We assume that the graph is connected and the search starting from any vertex can reach all the vertices.

Depth-First Search Algorithm

The algorithm for the depth-first search is described in the code below.

Input: G = (V, E) and a starting vertex v Output: a DFS tree rooted at v 1 Tree dfs(vertex v) { 2 visit v; 3 for each neighbor w of v 4 if (w has not been visited) { 5 set v as the parent for w in the tree; 6 dfs(w); 7 } 8 }

You can use an array named isVisited to denote whether a vertex has been visited. Initially, isVisited[i] is false for each vertex i. Once a vertex, say v, is visited, isVisited[v] is set to true.

Consider the graph in Figure below (a). Suppose we start the depth-first search from vertex 0. First visit 0, then any of its neighbors, say 1. Now 1 is visited, as shown in Figure below (b). Vertex 1 has three neighbors—0, 2, and 4. Since 0 has already been visited, you will visit either 2 or 4. Let us pick 2. Now 2 is visited, as shown in Figure below (c). Vertex 2 has three neighbors: 0, 1, and 3. Since 0 and 1 have already been visited, pick 3. 3 is now visited, as shown in Figure below (d). At this point, the vertices have been visited in this order:

0, 1, 2, 3

Since all the neighbors of 3 have been visited, backtrack to 2. Since all the vertices of 2 have been visited, backtrack to 1. 4 is adjacent to 1, but 4 has not been visited. Therefore, visit 4, as shown in Figure below (e). Since all the neighbors of 4 have been visited, backtrack to 1.
Since all the neighbors of 1 have been visited, backtrack to 0. Since all the neighbors of 0 have been visited, the search ends.

Since each edge and each vertex is visited only once, the time complexity of the dfs method is O(|E| + |V|), where |E| denotes the number of edges and |V| the number of vertices.

Implementation of Depth-First Search

The algorithm for DFS in the code above uses recursion. It is natural to use recursion to implement it. Alternatively, you can use a stack.

The dfs(int v) method is implemented in lines 164–193 in AbstractGraph.java. It returns an instance of the Tree class with vertex v as the root. The method stores the vertices searched in the list searchOrder (line 165), the parent of each vertex in the array parent (line 166), and uses the isVisited array to indicate whether a vertex has been visited (line 171). It invokes the helper method dfs(v, parent, searchOrder, isVisited) to perform a depth-first search (line 174).

In the recursive helper method, the search starts from vertex u. u is added to searchOrder in line 184 and is marked as visited (line 185). For each unvisited neighbor of u, the method is recursively invoked to perform a depth-first search. When a vertex e.v is visited, the parent of e.v is stored in parent[e.v] (line 189). The method returns when all vertices are visited for a connected graph, or in a connected component.

The code below gives a test program that displays a DFS for the graph in Figure above starting from Chicago. The graphical illustration of the DFS starting from Chicago is shown in Figure below.

public class TestDFS {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<String> graph = new UnweightedGraph<>(vertices, edges);
        AbstractGraph<String>.Tree dfs = graph.dfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = dfs.getSearchOrder();
        System.out.println(dfs.getNumberOfVerticesFound() + " vertices are searched in this DFS order:");
        for(int i = 0; i < searchOrders.size(); i++)
            System.out.print(graph.getVertex(searchOrders.get(i)) + " ");
        System.out.println();

        for(int i = 0; i < searchOrders.size(); i++)
            if(dfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(dfs.getParent(i)));
    }

}

12 vertices are searched in this DFS order: Chicago Seattle San Francisco Los Angeles Denver Kansas City New York Boston Atlanta Miami Houston Dallas parent of Seattle is Chicago parent of San Francisco is Seattle parent of Los Angeles is San Francisco parent of Denver is Los Angeles parent of Kansas City is Denver parent of Boston is New York parent of New York is Kansas City parent of Atlanta is New York parent of Miami is Atlanta parent of Dallas is Houston parent of Houston is Miami

Applications of the DFS

The depth-first search can be used to solve many problems, such as the following:

Detecting whether a graph is connected. Search the graph starting from any vertex. If the number of vertices searched is the same as the number of vertices in the graph, the graph is connected. Otherwise, the graph is not connected.
Detecting whether there is a path between two vertices.
Finding a path between two vertices.
Finding all connected components. A connected component is a maximal connected subgraph in which every pair of vertices are connected by a path.
Detecting whether there is a cycle in the graph.
Finding a cycle in the graph.
Finding a Hamiltonian path/cycle. A Hamiltonian path in a graph is a path that visits each vertex in the graph exactly once. A Hamiltonian cycle visits each vertex in the graph exactly once and returns to the starting vertex.

The first six problems can be easily solved using the dfs method in AbstractGraph.java. To find a Hamiltonian path/cycle, you have to explore all possible DFSs to find the one that leads to the longest path. The Hamiltonian path/cycle has many applications, including for solving the well-known Knight’s Tour problem.

Graph Traversals

Paul Ike — Fri, 09 Aug 2024 15:05:46 +0000

Depth-first and breadth-first are two common ways to traverse a graph.
Graph traversal is the process of visiting each vertex in the graph exactly once. There are two popular ways to traverse a graph: depth-first traversal (or depth-first search) and breadth-first traversal (or breadth-first search). Both traversals result in a spanning tree, which can be modeled using a class, as shown in Figure below. Note that Tree is an inner class defined in the AbstractGraph class. AbstractGraph.Tree is different from the Tree interface defined in Searching for an Element. AbstractGraph.Tree is a specialized class designed for describing the parent–child relationship of the nodes, whereas the Tree interface defines common operations such as searching, inserting, and deleting in a tree. Since there is no need to perform these operations for a spanning tree, AbstractGraph.Tree is not defined as a subtype of Tree.

The Tree class is defined as an inner class in the AbstractGraph class in lines 226–293 in AbstractGraph.java. The constructor creates a tree with the root, edges, and a search order.

The Tree class defines seven methods. The getRoot() method returns the root of the tree. You can get the order of the vertices searched by invoking the getSearchOrder() method. You can invoke getParent(v) to find the parent of vertex v in the search. Invoking getNumberOfVerticesFound() returns the number of vertices searched. The method getPath(index) returns a list of vertices from the specified vertex index to the root. Invoking printPath(v) displays a path from the root to v. You can display all edges in the tree using the printTree() method.

Graph Visualization

Paul Ike — Fri, 09 Aug 2024 14:52:17 +0000

To display a graph visually, each vertex must be assigned a location. The preceding section introduced how to model a graph using the Graph interface, AbstractGraph class, and UnweightedGraph class. This section discusses how to display graphs graphically. In order to display a graph, you need to know where each vertex is displayed and the name of each vertex. To ensure a graph can be displayed, we define an interface named Displayable that has the methods for obtaining the x- and y-coordinates and their names, and make vertices instances of Displayable, in the code below.

A graph with Displayable vertices can now be displayed on a pane named GraphView, as shown in the code below.

To display a graph on a pane, simply create an instance of GraphView by passing the graph as an argument in the constructor (line 9). The class for the graph’s vertex must implement the Displayable interface in order to display the vertices (lines 13–22). For each vertex index i, invoking graph.getNeighbors(i) returns its adjacency list (line 26). From this list, you can find all vertices that are adjacent to i and draw a line to connect i with its adjacent vertex (lines 27–34).

The code below gives an example of displaying the graph in Figure above, as shown in Figure below.

import javafx.application.Application;
import javafx.scene.Scene;
import javafx.stage.Stage;

public class DisplayUSMap extends Application {
    @Override // Override the start method in the Application class
    public void start(Stage primaryStage) {
        City[] vertices = {new City("Seattle", 75, 50),
                new City("San Francisco", 50, 210),
                new City("Los Angeles", 75, 275), new City("Denver", 275, 175),
                new City("Kansas City", 400, 245),
                new City("Chicago", 450, 100), new City("Boston", 700, 80),
                new City("New York", 675, 120), new City("Atlanta", 575, 295),
                new City("Miami", 600, 400), new City("Dallas", 408, 325),
                new City("Houston", 450, 360)};

        // Edge array for graph
        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5}, {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7}, {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11}, {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<City> graph = new UnweightedGraph<>(vertices, edges);

        // Create a scene and place it in the stage
        Scene scene = new Scene(new GraphView(graph), 750, 450);
        primaryStage.setTitle("DisplayUSMap"); // Set the stage title
        primaryStage.setScene(scene); // Place the scene in the stage
        primaryStage.show(); // Display the stage
    }

    public static void main(String[] args) {
        Application.launch(args);
    }

    static class City implements Displayable {
        private int x, y;
        private String name;

        City(String name, int x, int y) {
            this.name = name;
            this.x = x;
            this.y = y;
        }

        @Override
        public int getX() {
            return x;
        }

        @Override
        public int getY() {
            return y;
        }

        @Override
        public String getName() {
            return name;
        }
    }
}

The class City is defined to model the vertices with their coordinates and names (lines 39–63). The program creates a graph with the vertices of the City type (line 30). Since City implements Displayable, a GraphView object created for the graph displays the graph in the pane (line 33).