The WeightedGraph Class

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  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  vertices, int[][] edges) {
        this.vertices = vertices;

        for (int i = 0; i ()); // Create a list for vertices
        }

        for (int i = 0; i  vertices, List<weightededge> edges) {
        this.vertices = vertices;

        for (int i = 0; i ()); // 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  T = new ArrayList();

        // Expand T
        while (T.size()  ((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  T = new ArrayList();

        // Expand T
        while (T.size()  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 



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

<p>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.</p>

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172557366620531.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="The WeightedGraph Class"></p>

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172557366768226.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="The WeightedGraph Class"><br>
</p>

<pre class="brush:php;toolbar:false">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();
    }
}

</integer></string>

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)

プログラムは、3 ～ 27 行目で、上図のグラフの graph1 を作成します。 graph1 の頂点は 3 ～ 5 行目で定義されています。 graph1 のエッジは 7 ～ 24 行目で定義されています。エッジは 2 次元配列を使用して表現されます。配列内の各行 i について、edges[i][0] および edges[i][1] は、頂点 edges[i] からのエッジがあることを示します。 [0] は頂点 edges[i][1] であり、エッジの重みは edges[i][2] です。たとえば、{0、1、807} (8 行目) は頂点 0 からのエッジを表します (edges[ 0][0]) を頂点 1 (edges[0][1])、ウェイト 807 (edges[0]) [2])。 {0, 5, 2097} (8 行目) は頂点 0 (edges[2][ 0]) から頂点 5 (edges[2][1])、ウェイト 2097 (edges[2][2]) )。 35 行目は、graph1 の printWeightedEdges() メソッドを呼び出して、graph1 のすべてのエッジを表示します。

プログラムは、37 ～ 44 行目で、上図 a のグラフの graph2 のエッジを作成します。 46 行目は、graph2 の printWeightedEdges() メソッドを呼び出して、graph2 のすべてのエッジを表示します。

The above is the detailed content of The WeightedGraph Class. For more information, please follow other related articles on the PHP Chinese website!