java - 创建扩展 Graph 类的二分图。需要一些指导

Question

寻找正确方向的一步。我已经完成了 4 节课。一个是父类(super class)，即图和 3 个子类，分别称为 Edge、DirectedGraph 和 BipartiteGraph。

我在创建二分图时遇到一些问题。具体来说，我得到了以下指示:

Extend the Graph class to create a new BipartiteGraph class. It should inherit all the functionality of the super class:

• Automatically designate all even-index vertices (0,2,4) as part of the "A partition" from class and all odd-index vertices (1,3,5) as part of the "B partition". This requires no new code, just a conceptual expectation.

• Override the constructor for Graph to have the same input (number of vertices), call the super constructor, and then verify the graph is bipartite. That is, make sure that all existing edges are from a vertex in A to a vertex in B. If the graph is not bipartite, wipe out the internal representation (e.g., for an adjacency matrix, make a size 0x0 array) so it cannot be used!

• Add a method setPreferences() that takes as a parameter an integer and an array or ArrayList of integers. The first integer is the vertex we want to attach preferences to and the list is that list of preferences, from most to least preferred. Verify that the array of ints contains all the members of the other partition in some order then save that information (you will need a 1-D array of arrays/ArrayLists to store these lists, one per vertex).

• Add the method stableMatching that has no parameters and returns a stable matching (in the form of an ArrayList of Pairs of ints). It will be helpful to consult Wikipedia: http://en.wikipedia.org/wiki/Stable_marriage_problem . As a start, I suggest verifying that each vertex has a preference list set for it!

这是我在父类(super class)中的构造函数:

public class Graph {

// Setup privately modified variables which will define the graph

// These two parameters are storage variables for edges and vertices
// These variables were changed from Vertex and Edge to numVertices and
// numEdges.
private int numVertices;
private int numEdges;

// This will be the adjacency matrix to represent our graph, this will
// represent edges.
// adj_Matrix_Edges was previously static meaning it did not have access to
// multiple graphs, onyl one graph.
protected boolean[][] adj_Matrix_Edges;

// first step will be to setup the graph, using this constructor
public Graph(int vertices) {

    numVertices = vertices;

    if (numVertices < 0) {
        throw new RuntimeException(
                "Number of vertices cannot be a nonnegative value");
    }

    System.out.println("There are now " + numVertices
            + " vertices in the graph.");

    // A graph is created based on the specifications, N X N or (n^2)
    // graph.
    adj_Matrix_Edges = new boolean[vertices][vertices];
    }

这是迄今为止我对 BipartiteGraph 类的了解:

    public class BipartiteGraph extends Graph{

//Initialize two partitions for bipartite graph.
boolean[][] a;
boolean[][] b;


//Constructor of BipartiteGraph class
public BipartiteGraph(int vertices) {
    super(vertices);

    //Copy over even elements of graph into partition A.
    for (int i = 0; i < adj_Matrix_Edges.length; i++){
        for (int j = 0; j < adj_Matrix_Edges[i].length; j++){
            if (j%2 == 0){
                adj_Matrix_Edges[j] = a[j];
            }
        }
    }

    //Copy over odd elements of graph into Partition B.
    for (int i = 0; i < adj_Matrix_Edges.length; i++){
        for (int j = 0; j < adj_Matrix_Edges[i].length; j++){
            if (j%2 != 0){
                adj_Matrix_Edges[j] = b[j];
            }
        }
    }

}


public void setPreferences(int vertex, int[] preferences){

    if ()

}

public List stableMatching(){
    java.util.List<Integer> matching = new ArrayList<Integer>();


}

我是否让事情变得太复杂了，代码是否比看起来更简单？

Answer 1

我认为BipartiteGraph的声明有一个错误:

public class BipartiteGraph extends Graph{

boolean[][] a;
boolean[][] b;

您将 a 和 b 声明为二维数组，即矩阵。 a 和 b 对顶点集的互补子集进行建模。因此，它们应该是顶点列表或 boolean 数组，表示第i个顶点是否在a中。此外，您不需要同时存储两者，因为其中一个是另一个的补充。