Создание двудольного графика, расширяющего класс графа. Нужно руководствоваться

Question

Ищете шаг в правильном направлении. У меня со мной 4 класса, которые я сделал. Один из них - суперкласс, который представляет собой граф и 3 подкласса, называемый Edge, DirectedGraph и BipartiteGraph.

У меня возникли проблемы с созданием двудольного графа. В частности, мне дано следующее:

Расширение класса Graph для создания нового класса BipartiteGraph. Он должен наследовать всю функциональность суперкласса:

• Автоматически определять все четные индекса вершины (0,2,4) как часть «А раздела» из класса и всех нечетных индексов вершин (1,3,5) как часть раздела «B». Это не требует нового кода, а просто концептуального ожидания .

• Переопределите конструктор для того, чтобы граф имел один и тот же вход (количество вершин), вызывал супер конструктор, а затем проверял, что граф двудольный. То есть убедитесь, что все существующие ребра из вершины в A в вершину в B. Если граф не двудольный, уничтожьте внутреннее представление (например, для матрицы смежности, сделайте массив размером 0x0), чтобы он не мог использоваться!

• Добавить метод setPreferences(), который принимает в качестве параметра целое число и массив или ArrayList целых чисел. Первое целое число - это вершина, к которой мы хотим привязать предпочтения, а список - это список предпочтений, от большинства до наименее предпочтительных. Убедитесь, что массив ints содержит все члены другого раздела в некотором порядке, затем сохранит эту информацию (для хранения этих списков вам понадобится 1-D массив массивов/ArrayLists, по одному на вершину).

• Добавить метод stableMatching, который не имеет параметров и возвращает устойчивое соответствие (в виде массива ArrayList из пар int). Будет полезно ознакомиться с Википедии: http://en.wikipedia.org/wiki/Stable_marriage_problem. В начале я предлагаю проверить, что для каждой вершины установлен список предпочтений!

Вот мой конструктор в супер класс:

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. Также вам не нужно хранить оба, так как один является дополнительным к другому.

Answer 2

Возможно, я что-то пропустил, но вам нужно написать это как домашнюю работу? в противном случае, вы можете рассчитывать на JUNG и использовать гиперграф:

http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/Hypergraph.html