vertexgroup.java

最小生成树 支持鼠标点击生成结点 并且动态生成最小树

import java.awt.Color;
import java.awt.Graphics;

class vertexGroup
{
public vertexGroup(){//构造函数．
vertex.classChar='A';
vertexList=new vertex[MAX_VERTS];
adjMat=new disIs[MAX_VERTS][MAX_VERTS];
adjMat2=new disIs[MAX_VERTS][MAX_VERTS];
nVerts=0;
thePQ=new priorityQ();
tree=new int[MAX_VERTS];
nTree=0;
for(int i=0;i<MAX_VERTS;i++)
{
for(int j=0;j<MAX_VERTS;j++)
{
adjMat[i][j] = new disIs(INFINITY, false);
adjMat2[i][j] = new disIs(INFINITY, false);
}

}//结束初始化．

showAdjm = false;
startingVertex = -1;
note = "Double-click mouse to make vertex";
drawMode = 4;
}

public void makeVertex(int i, int j){
madeVertex = true;
if(nVerts > MAX_VERTS-1)
{
note = "CAN'T INSERT more vertices";
return;
} 
else
{
vertexList[nVerts++] = new vertex(i, j);
note = "Made vertex " + vertexList[nVerts - 1].label;
displayVertex = nVerts - 1;
opMode = 0;
drawMode = 2;
return;
}
}

public void startDrag(int i, int j)//得到起始点坐标
{
xStartDrag = i;
yStartDrag = j;
int k = closeTo(i, j);
startingVertex = k;
if(k < 0)
note="To make edge, drag from vertex to vertex";
else
note="Starting edge at vertex "+vertexList[k].label;
drawMode = 1;
}

public void endDrag(boolean flag, int i, int j, int k)
{
if(madeVertex)
{
madeVertex = false;
drawMode = 2;
return;
}
int l = closeTo(xStartDrag, yStartDrag);
int i1 = closeTo(j, k);
if(opMode > 0)
{
if(startingVertex == -1)
 note = "Click on a VERTEX";
else
note = "You clicked on "+vertexList[startingVertex].label;
drawMode = 1;
return;
}
if(l<0 || i1<0 || l==i1)
{
note="CAN'T MAKE EDGE: Drag from vertex to vertex";
drawMode = 1;
return;
}
if(!flag || i<0 || i>99)
{
note="CAN'T MAKE EDGE: Enter a weight (0 to " + 99 + ")";
drawMode = 1;
return;
} 
else
{
note="Made edge from "+vertexList[l].label+" to "+vertexList[i1].label+" with weight "+i;
adjMat[l][i1].distance = i;
adjMat[i1][l].distance = i;
madeVertex = false;
displayEdge1 = l;
displayEdge2 = i1;
drawMode = 3;
return;
}
}

public int closeTo(int i, int j)
{
byte byte0 = 11;
for(int k = 0; k < nVerts; k++)
if(Math.abs(vertexList[k].x-i)<byte0 && Math.abs(vertexList[k].y-j)<byte0)
return k;

return -1;
}

public void changeView()
{
if(showAdjm)
{
note = oldNote;
showAdjm = false;
return;
}
oldNote = note;
if(nVerts == 0)
 note="No vertices; adjacency matrix is empty";
else
 note="Press View button again to show graph";
showAdjm = true;
drawMode = 4;
}

public void mst(){
if(opMode != 1)
{
opMode = 1;
codePart = 1;
}
switch(codePart)
{
case 1: 
saveState();
note = "Single-click on vertex from which to start tree";
startingVertex = -1;
drawMode = 1;
codePart = 2;
return;

case 2: 
if(startingVertex == -1)
{
note = "INVALID VERTEX";
codePart = 1;
} else
{
note = "Starting tree from vertex "+vertexList[startingVertex].label;
currentVert = startingVertex;
codePart = 3;
}
drawMode = 1;
return;

case 3: 
tree[nTree++] = currentVert;
vertexList[currentVert].isInTree = true;
note = "Placed vertex "+vertexList[currentVert].label+" in tree";
if(nTree == nVerts)
codePart = 6;
else
  codePart = 4;
drawMode = 4;
return;

case 4: 
for(int i = 0; i < nVerts; i++)
if(i != currentVert && !vertexList[i].isInTree)
{
int j = adjMat[currentVert][i].distance;
if(j != 0xf4240)
putInPQ(i, j);
}

if(thePQ.size() > 0)
 {
note = "Placed vertices adj to " + vertexList[currentVert].label + " in priority queue";
codePart = 5;
} else
 {
note = "Graph not connected";
codePart = 8;
}
drawMode = 1;
return;

case 5: 
edge edge1 = thePQ.removeMin();
currentVert = edge1.destVert;
int k = edge1.srcVert;
adjMat[k][currentVert].isInTree = true;
adjMat[currentVert][k].isInTree = true;
note="Removed minimum-distance edge "+vertexList[edge1.srcVert].label+vertexList[edge1.destVert].label+edge1.distance+" from priority queue";
drawMode = 1;
codePart = 3;
return;

case 6: 
note = "Press again to delete unmarked edges";
drawMode = 1;
codePart = 7;
return;

case 7: 
for(int l = 0; l < nVerts; l++)
{
for(int j1 = 0; j1 < nVerts; j1++)
if(adjMat[l][j1].distance != INFINITY)
if(!adjMat[l][j1].isInTree)
adjMat[l][j1].distance = INFINITY;
else
adjMat[l][j1].isInTree = false;

}

note = "Minimum spanning tree; press again to restore tree";
drawMode = 4;
codePart = 8;
return;

case 8: 
restoreState();
note = "Press any button";
nTree = 0;
for(int i1 = 0; i1 < nVerts; i1++)
vertexList[i1].isInTree = false;

for(; !thePQ.isEmpty(); thePQ.removeMin());
codePart = 1;
opMode = 0;
drawMode = 4;
return;
}
}

public void saveState(){
for(int i = 0; i < nVerts; i++){
for(int j = 0; j < nVerts; j++){
adjMat2[i][j].distance = adjMat[i][j].distance;
adjMat2[i][j].isInTree = adjMat[i][j].isInTree;
}
}
}

public void restoreState(){
for(int i = 0; i < nVerts; i++){
for(int j = 0; j < nVerts; j++){
adjMat[i][j].distance = adjMat2[i][j].distance;
adjMat[i][j].isInTree = adjMat2[i][j].isInTree;
}
}
}

public void putInPQ(int i, int j)//点进队列
{
int k = thePQ.find(i);
if(k != -1)
{
edge edge1 = thePQ.peekN(k);
int l = edge1.distance;
if(l > j)
{
thePQ.removeN(k);
edge edge3 = new edge(currentVert, i, j);
thePQ.insert(edge3);
return;
}
}
else
{
edge edge2 = new edge(currentVert, i, j);
thePQ.insert(edge2);
}
}

public String dtoS(int i)//剪切字到面板
{
if(i == INFINITY)
return "inf";
else
return String.valueOf(i);
}

public void warningNew()
{
note = "ARE YOU SURE? Press again to clear old graph";
}

public void drawOneVertex(Graphics g, int i)
{
if(i < 0)
return;
Color color = vertexList[i].color;
char c = vertexList[i].label;
int j = vertexList[i].x - 11;
int k = vertexList[i].y - 11;
g.setColor(color);
g.fillOval(j, k, 22, 22);
g.setColor(Color.black);
g.drawOval(j, k, 22, 22);
if(vertexList[i].isInTree)
{
g.setColor(Color.red);
g.drawOval(j - 3, k - 3, 28, 28);
}
g.drawString(String.valueOf(c), j + 8, (k + 22) - 5);
}

public void draw(Graphics g)
{
if(showAdjm)
{
g.setColor(Color.lightGray);
g.fillRect(0, 0, 440, 300);
g.setColor(Color.black);
g.drawString(note, 16, 64);
drawAdjm(g);
return;
}
switch(drawMode)
{
default:
break;

case 2: 
drawOneVertex(g, displayVertex);
break;

case 3: 
int i = adjMat[displayEdge1][displayEdge2].distance;
if(i < 0xf4240)
drawEdge(g, displayEdge1, displayEdge2);
drawOneVertex(g, displayEdge1);
drawOneVertex(g, displayEdge2);
break;

case 4: 
g.setColor(Color.lightGray);//
g.fillRect(0, 0, 440, 300);
g.setColor(Color.black);
g.drawRect(2, 71, 436, 207);
for(int k = 0; k < nVerts; k++){
for(int j1 = 0; j1 < nVerts; j1++){
int j = adjMat[k][j1].distance;
if(j < INFINITY)
drawEdge(g, k, j1);
}
}
for(int l = 0; l < nVerts; l++)
drawOneVertex(g, l);

break;
}
g.setColor(Color.lightGray);//lightGray
g.fillRect(10, 45, 430, 25);
g.setColor(Color.black);
g.drawString(note, 16, 64);
g.setColor(Color.lightGray);//lightGray
g.fillRect(10, 280, 430, 25);
g.setColor(Color.black);
if(opMode == 1)
{
String s = "Tree: ";
for(int i1 = 0; i1 < nTree; i1++)
s = s + vertexList[tree[i1]].label + " ";

g.drawString(s, 10, 296);
s = "PQ: ";
for(int k1 = 0; k1 < thePQ.size(); k1++)
{
s = s + vertexList[thePQ.peekN(k1).srcVert].label;
s = s + vertexList[thePQ.peekN(k1).destVert].label;
s = s + thePQ.peekN(k1).distance + " ";
}

g.drawString(s, 210, 296);
}
drawMode = 4;
}

private void drawEdge(Graphics g, int i, int j){
int k = vertexList[i].x;
int l = vertexList[i].y;
int i1 = vertexList[j].x;
int j1 = vertexList[j].y;
g.setColor(Color.black);
g.drawLine(k, l, i1, j1);
if(adjMat[i][j].isInTree)
{
g.drawLine(k+1,l,i1+1,j1);
if((i1-k>0)!=(j1-l>0))
g.drawLine(k,l-1,i1,j1-1);
else
g.drawLine(k,l+1,i1,j1+1);
}
int k1=(k+i1)/2-8;
int l1=(l+j1)/2-7;
g.setColor(Color.white);
g.fillRect(k1, l1, 17, 15);
g.setColor(Color.black);
g.drawRect(k1, l1, 17, 15);
int i2 = adjMat[i][j].distance;
byte byte0 = i2 <= 9 ? ((byte) (6)) : 2;
g.drawString(String.valueOf(i2), k1 + byte0, (l1 + 15) - 2);
}

public void drawAdjm(Graphics g)
{
if(nVerts == 0)
{
note = "No vertices; adjacency matrix is empty";
return;
}
byte byte0 = 90;
byte byte1 = 106;
byte byte2 = 27;
byte byte3 = 18;
g.drawLine(byte0-byte2,(byte1-byte3)+4,((byte0+nVerts*byte2)-byte2)+8,(byte1-byte3)+4);
g.drawLine((byte0-byte2/2)+2,(byte1-2*byte3)+8,(byte0-byte2/2)+2,byte1+(nVerts-1)*byte3);
for(int i = 0; i < nVerts; i++)
g.drawString(String.valueOf(vertexList[i].label), byte0-byte2,byte1+i*byte3);

for(int j = 0; j < nVerts; j++)
{
g.drawString(String.valueOf(vertexList[j].label), byte0+j*byte2,byte1-byte3);
for(int k = 0; k < nVerts; k++)
g.drawString(dtoS(adjMat[k][j].distance),byte0+j*byte2,byte1+k*byte3);

}

}
private final int MAX_VERTS = 10;
private final int MAX_WEIGHT = 99;
private final int INFINITY = 0xf4240;
private vertex vertexList[];
private disIs adjMat[][];
private disIs adjMat2[][];
private int nVerts;
private priorityQ thePQ;
private int tree[];
private int nTree;
private String note;
private String oldNote;
private int opMode;
private int codePart;
private int drawMode;
private int xStartDrag;
private int yStartDrag;
private boolean madeVertex;
private boolean showAdjm;
private int startingVertex;
private int currentVert;
private int displayVertex;
private int displayEdge1;
private int displayEdge2;
}