Это для класса структур данных в Java, и мне нужно создать граф, который читает текстовый ввод, преобразует эту информацию в граф, и оттуда распечатывает список смежности и печатает максимальное связующее дерево, которое я сделал,Однако последний аспект - это
Полная таблица маршрутизации, которую должна создать ваша программа, будет иметь для каждой пары [i, j] (i! = J) компьютеров в сети, первого компьютерапо оптимальному маршруту от i до j.Если у i и j есть прямое соединение, то j будет результатом (запись таблицы) для этого маршрута (пара [i, j]).Если оптимальным маршрутом от i до j является i -> a -> b -> j, то a будет результатом (запись в таблице) для этого маршрута.Затем можно построить маршрут, посмотрев на значение из [i, j] (= a), затем [a, j] (= b), затем [b, j] (= j).
Так что в основном алгоритм Дейкста.Тем не менее, я не могу использовать какие-либо API Java, которые имеют дело с графами (все остальные разрешены).Пока у меня есть
import java.util.ArrayList;
//import java.util.Stack;
public class Graph2 {
ArrayList<Vertex> vert = new ArrayList<Vertex>();
private static int counter = 0;
private int edges;
private Edge[] allEdges = new Edge[50];
private class Vertex{
String ip;
private int id;
ArrayList<Edge> nb = new ArrayList<Edge>();
/**
* Constructor for Vertex
* @param String of IP
*/
public Vertex(String s){
ip = s;
id = counter;
counter++;
}
/**
* Gets the ID of a vertex
* @return unique ID
*/
public int getId(){
return id;
}
/*
public boolean isSame(Vertex v){
if(this.ip.equals(v.getIp()))
return true;
else
return false;
}
*/
/**
* Gets the IP of a vertex
* @return the IP of the vertex
*/
public String getIp(){
return this.ip;
}
/**
* Adds an edge to nb
* @param edge to be added
*/
public void addList(Edge e){
nb.add(e);
}
/**
* Determines if an edge exists
* @param edge to be checked
* @return true if exists, false if not
*/
public boolean exists(Edge e){
if(nb.indexOf(e) != -1){
return true;
}
else
return false;
}
/**
* Gets the size of an edge
* @return size of edge
*/
public int edgeSize(){
return nb.size();
}
/**
* Gets the edges
* @return String of edges
*/
public String getEdges(){
String all = "";
Edge e;
for(int i = 0; i < nb.size(); i++){
e = nb.get(i);
int ti = this.getId();
int fin = e.getFinish().getId();
if(ti == fin)
all += e.getStart().getId() + " ";
else
all += e.getFinish().getId() + " ";
}
return all;
}
/**
* Overrides toString method
* @return ID and IP of vertex
*/
public String toString(){
return id + " " + " " + ip;
}
}
private class Edge{
int weight;
Vertex finish;
Vertex start;
/**
* Constructor of Edge
* @param vertex 1, start vertex
* @param vertex 2, endpoint vertex
* @param weight of edge
*/
public Edge(Vertex v, Vertex v2, int w){
start = v;
finish = v2;
weight = w;
}
/**
* Gets the start of an edge
* @return edge start
*/
public Vertex getStart(){
return start;
}
/**
* Gets the endpoint of an edge
* @return endpoint of edge
*/
public Vertex getFinish(){
return finish;
}
/**
* Gets the weight of an edge
* @return weight of edge
*/
public int getWeight(){
return weight;
}
/**
* Overrides toString
* @return start of edge and endpoint of edge
*/
public String toString(){
return start + " " + finish;
}
}
/**
* Adds an edge to 2 verticies
* @param s, starting vertex IP
* @param t, enpoint vertex IP
* @param w, weight of edge
*/
public void add(String s, String t, int w){
Vertex v3, v4;
v3 = exists(new Vertex(s));
v4 = exists(new Vertex(t));
Edge e;
if(v3 == null && v4 == null){
v3 = new Vertex(s);
v4 = new Vertex(t);
vert.add(v3);
vert.add(v4);
e = new Edge(v3, v4, w);
v3.addList(e);
v4.addList(e);
}
else if(v3 != null && v4 == null){
counter--;
v4 = new Vertex(t);
vert.add(v4);
e = new Edge(v3, v4, w);
v3.addList(e);
v4.addList(e);
}
else if(v3 == null && v4 !=null){
counter--;
v3 = new Vertex(s);
vert.add(v3);
e = new Edge(v3, v4, w);
v3.addList(e);
v4.addList(e);
}
else{
counter -= 2;
e = new Edge(v3, v4, w);
if(!v3.exists(e)){
v3.addList(e);
v4.addList(e);
}
}
allEdges[edges] = e;
edges++;
}
/**
* Determines if an edge already exists
* @param vertex to be checked
* @return vertex if exists, null if not
*/
public Vertex exists(Vertex v){
for(int i = 0; i < vert.size(); i++){
if(v.getIp().equals(vert.get(i).getIp()))
return vert.get(i);
}
counter--;
return null;
}
/**
* Puts vert ArrayList into an array
* @return String array of vert
*/
public String[] toArray(){
String[] all = new String[vert.size()];
for(int i = 0; i < vert.size(); i++){
all[i] = vert.get(i).toString();
}
return all;
}
/**
* Determines if a vertex is adjacent to another vertex
* @return String array of adjacent verticies
*/
public String[] adjaceny(){
String[] all = new String[vert.size()];
Vertex v1;
for(int i = 0; i < vert.size(); i++){
v1 = vert.get(i);
all[i] = v1.getEdges();
}
return all;
}
/**
* Determines which vertex is in which cluster
* @return String array of clusters
*/
/*
public String[] cluster(){
Vertex[] temp = (Vertex[]) vert.toArray();
Sorter sort = new Sorter();
sort.heapsort(temp);
String[] cluster = new String[vert.size()];
int[] verts = new int[vert.size()];
for(int i = 0; i < vert.size();i++)
verts[i] = i;
return null;
}
*/
/**
* Gets the max spanning tree of the graph
* @return spanning tree of graph
*/
public String[] maxTree(){
sortEdges();
String[] max = new String[vert.size() -1];
Edge e;
for(int i = 0; i < vert.size()-1; i++){
e = allEdges[i];
max[i] = e.getStart().getId() + ", " + e.getFinish().getId() + ", " + e.getWeight();
}
return max;
}
/**
* Sorts edges by max weight
*/
private void sortEdges(){
Sorter sort = new Sorter();
sort.heapsort(allEdges);
}
public class Sorter{
/**
* Heapsorts the Object array
* @param Object array to be sorted
*/
public void heapsort(Object[] a)
{
for(int i = edges / 2; i >= 0; i-- ) /* buildHeap */
percDown(a, i, edges);
for( int i = edges - 1; i > 0; i-- )
{
swapReferences( a, 0, i ); /* deleteMax */
percDown( a, 0, i );
}
}
/**
* Performs swapping of elements
* @param Object array
* @param index1
* @param index2
*/
public void swapReferences(Object[] a, int index1, int index2 )
{
if(a[0] instanceof Edge){
Edge tmp = (Edge)a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
else if(a[0] instanceof Vertex){
Vertex temp = (Vertex)a[index1];
a[index1] = a[index2];
a[index2] = temp;
}
}
/**
* Internal method for heapsort.
* @param i the index of an item in the heap.
* @return the index of the left child.
*/
private int leftChild(int i)
{
return 2 * i + 1;
}
/**
* Internal method for heapsort that is used in
* deleteMax and buildHeap.
* @param a an array of Comparable items.
* @int i the position from which to percolate down.
* @int n the logical size of the binary heap.
*/
private void percDown(Object[] a, int i, int n)
{
int child;
if(a[0] instanceof Edge){
Edge tmp;
for( tmp = (Edge) a[i]; leftChild(i) < n; i = child )
{
child = leftChild(i);
if( child != n - 1 && ((Edge)a[child]).getWeight() - ((Edge)(a[child + 1])).getWeight() > 0 )
child++;
if(tmp.getWeight() - ((Edge)a[child]).getWeight() > 0 )
a[i] = a[child];
else
break;
}
a[i] = tmp;
}
else if(a[0] instanceof Vertex){
Vertex temp;
for(temp = (Vertex) a[i]; leftChild(i) < n; i = child){
child = leftChild(i);
if(child != n-1 && ((Vertex)a[child]).edgeSize() - ((Vertex)a[child+1]).edgeSize() > 0)
child++;
if(temp.edgeSize() - ((Vertex)a[child]).edgeSize() > 0)
a[i] = a[child];
else
break;
}
a[i] = temp;
}
}
}
}
}
С основным состоящим из:
import java.util.*;
import java.io.*;
public class pg6main {
public static void main(String[] args) throws IOException{
String filename;
String first, second;
int weight;
Graph2 graph = new Graph2();
Scanner kb = new Scanner(System.in);
boolean go = false;
Scanner infile = null;
PrintWriter outfile = new PrintWriter(new FileWriter("results.txt"));
do{
try{
System.out.print("Enter a file to read from: ");
filename = kb.nextLine();
infile = new Scanner(new FileReader(filename));
}catch(Exception e){
go = true;
System.out.println("file doesn't exist");
}
}while(go);
while(infile.hasNext()){
first = infile.next().trim();
second = infile.next().trim();
weight = Integer.parseInt(infile.nextLine().trim());
graph.add(first, second, weight);
}
outfile.println("IP and their unique IDs: ");
String[] a = graph.toArray();
for(int i = 0; i < a.length; i++)
outfile.println(a[i]);
outfile.println("Adjaceny List: ");
String[] adj = graph.adjaceny();
for(int j = 0; j < adj.length; j++)
outfile.println(j + ": " + adj[j]);
outfile.println("Max spanning tree: ");
String[] max = graph.maxTree();
for(int k = 0; k < max.length; k++)
outfile.println("(" + max[k] + ") ");
/*
//Attempting to do clusters based on length of string of neighbors, does not work
for(int x = 0; x < adj.length; x++){
if(adj[x].length() > adj[x+1].length()){
outfile.println("WHAT I DID: " + adj[x]);
}
else if(adj[x].length() == adj[x+1].length()){
adj[x] = adj[x+1];
outfile.println("WHAT I DID: " + adj[x]);
}
else if(adj[x].length() < adj[x+1].length()){
adj[x] = adj[x+1];
outfile.println("WHAT I DID: " + adj[x]);
}
*/
/*//Attempted to do neighbors slighly different way
String[] cluster = graph.cluster();
for(int x = 0; x < cluster.length; x++){
if(cluster[x] != null)
outfile.println(cluster[x]);
*/
outfile.close();
}//end main
}//end pg6main
Мне было интересно, если кто-нибудь может помочь, я никогда не работал с графиками до сегодняшнего дня.Пока что я считаю, что мой код работает как задумано, но в моей логике могут быть некоторые ошибки.По сути, моя проблема в том, что большинство реализаций Дейкстры имеют параметры в виде графа, и я не уверен, что именно так мне и следует делать.Спасибо за любую помощь.