public class Suprafata extends Canvas implements MouseListener, MouseMotionListener, KeyListener {
Suprafata(Proiect proiect)
{
D = new int[9][9];
DC = new int[9][9];
Pi = new int[9][9];
x_coord = new int[9];
y_coord = new int[9];
sageti = new Shape[9][9];
pathVector = new int[9];
ftext=new Font("Times New Roman",2,15);
fmetrics = getFontMetrics(ftext);
ai = new int[4];
ai1 = new int[4];
edgepresent = new boolean[9][9];
edgecolor = new int[9][9];
parent = proiect;
numar_graf = 0;
d = new int[9];
t = new int[9];
s = new int[9];
h = new int[9];
e = new int[30][2];
G = new int[10][10];
drum = new int[9];
matback = new int[9][9];
source = 0;
numar_el_drum = 0;
nr_laturi = 0;
init();
setBackground(new Color(122,150,173));
parent.info.infodoc.setBackground(new Color(122,150,173));
}
public void init()
{ parent.info.infodoc.showLine("string3");
nr_puncte = 0;
for(int i=0;i < 9;i++) {
x_coord[i]=0;y_coord[i]=0;
pathVector[i] = 0;
}
x_coord[0]=12;
y_coord[0]=33;
for(int i=0;i < 9;i++) {
for(int j=0;j < 9;j++) {
if (i==j) D[i][j] = 0;
else D[i][j] = 999;
DC[i][j]=D[i][j];
Pi[i][j] = -1;
}
}
for(int i=0;i < 9;i++) {
for(int j=0;j < 9;j++) {
sageti[i][j] = new Polygon();
edgepresent[i][j] = false;
edgecolor[i][j] = 0;
G[i][j]=0;
matback[i][j] = 0;
}
}
nr_sageti = 0;
x_coord[0]=12;
y_coord[0]=33;
nr_elem = 0;
nr_noduri_sel = 0;
clicked = false;
pressed = false;
iesire = false;
sageata_clicked = false;
clickinline = false;
zero = false;
fw = false;
johnson = false;
nopath = false;
ispath = false;
nodstart = -1;
nodend = -1;
if (numar_graf==0) {
addMouseListener(this);
addMouseMotionListener(this);
}
numar_graf++;
repaint();
}
public void update(Graphics g)
{
paint(g);
}
public void paint(Graphics g)
{
g2D = (Graphics2D)g;
dim = getSize();
if(bufferimg!=null) graf.clearRect(0,0,dim.width,dim.height);
else
{ bufferimg = (BufferedImage)createImage(dim.width,dim.height);
graf = bufferimg.createGraphics();
}
graf.setStroke(new BasicStroke(3.0f));
FontRenderContext frc = g2D.getFontRenderContext();
graf.setColor(Color.blue);
graf.draw(new Line2D.Double(dim.width/2,0,dim.width/2,dim.height));
graf.draw(new Line2D.Double(dim.width/2,dim.height/2,dim.width,dim.height/2));
if (ispath) { for(int i=1;i < nr_elem;i++)
edgecolor[pathVector[i-1]-1][pathVector[i]-1] = 1; }
for(int i=0;i < nr_puncte;i++) {
for(int j=0;j < nr_puncte;j++)
if(D[i][j]!=0 && D[i][j]!=999) {
if(edgecolor[i][j] == 1) graf.setColor(Color.red);
else graf.setColor(Color.blue);
graf.draw(new Line2D.Double(x_coord[i],y_coord[i],x_coord[j],y_coord[j]));
drawarrow(i,j);
}
}
for(int i=0;i < nr_puncte;i++)
{
if (x_coord[i] != 0)
{
if (i == nodstart || i == nodend)
graf.setColor(Color.red);
else graf.setColor(Color.green);
graf.fill(new Ellipse2D.Double(x_coord[i]-15,y_coord[i]-15,30,30));
graf.setColor(Color.blue);
graf.draw(new Ellipse2D.Double(x_coord[i]-15,y_coord[i]-15,30,30));
TextLayout text = new TextLayout(""+(i+1), ftext, frc);
if (i+1 < 10) text.draw(graf, x_coord[i]-5, y_coord[i]+7);
else text.draw(graf, x_coord[i]-10, y_coord[i]+7);
}
}
if (!fw && !johnson) makePiMatrix();
graf.setStroke(new BasicStroke(1.0f));
drawGrid(dim.width/2+20,20);
drawGrid(dim.width/2+20,dim.height/2+20);
if (!johnson) drawMatrixNumbers(dim.width/2+20,20,DC);
else drawMatrixNumbers(dim.width/2+20,20,matback);
drawPiNumbers(dim.width/2+20,dim.height/2+20);
g2D.drawImage(bufferimg,0,0,this);
}
public void mousePressed(MouseEvent e)
{
int x = e.getX();
int y = e.getY();
int modifiers = e.getModifiers();
if (x < dim.width/2-15) {
if ((modifiers & InputEvent.BUTTON1_MASK) == InputEvent.BUTTON1_MASK) {
for(int i=0;i < nr_puncte;i++) {
nod = new Ellipse2D.Double(x_coord[i]-15,y_coord[i]-15,30,30);
if (nod.contains(x,y)) {
pressed = true;
nr_nod = i;
}
}
}
else {
if ((modifiers & InputEvent.BUTTON3_MASK) == InputEvent.BUTTON3_MASK) {
for(int i=0;i < nr_puncte;i++) {
nod = new Ellipse2D.Double(x_coord[i]-15,y_coord[i]-15,30,30);
if (nod.contains(x,y)) {
nr_nod = i;
pressed =true;
}
}
}
}
}
}
public void mouseDragged(MouseEvent e)
{
int x = e.getX();
int y = e.getY();
int modifiers = e.getModifiers();
if (x < dim.width/2 - 15) {
if ((modifiers & InputEvent.BUTTON3_MASK) == InputEvent.BUTTON3_MASK && pressed) {
x_coord[nr_nod] = x;
y_coord[nr_nod] = y;
}
}
repaint();
}
public void mouseReleased(MouseEvent e)
{
int x = e.getX();
int y = e.getY();
int modifiers = e.getModifiers();
if (x < dim.width-15) {
if ((modifiers & InputEvent.BUTTON1_MASK) == InputEvent.BUTTON1_MASK) {
for(int i=0;i < nr_puncte;i++) {
nod = new Ellipse2D.Double(x_coord[i]-15,y_coord[i]-15,30,30);
if(nod.contains(x,y) && pressed && edgepresent[i][nr_nod]!=true&&nr_nod!=i) {
D[nr_nod][i]= 5;
edgepresent[nr_nod][i] = true;
pressed = false;
drawarrow(nr_nod,i);
sageti[nr_nod][i] = new Polygon(ai,ai1,4);
}
}
}
else {
if ((modifiers & InputEvent.BUTTON3_MASK) == InputEvent.BUTTON3_MASK) {
if(pressed) {
x_coord[nr_nod] = x;
y_coord[nr_nod] = y;
pressed = false;
for(int i=0;i < nr_puncte;i++) {
if (edgepresent[nr_nod][i]) {
drawarrow(nr_nod,i);
sageti[nr_nod][i] = new Polygon(ai,ai1,4);
}
if (edgepresent[i][nr_nod]) {
drawarrow(i,nr_nod);
sageti[i][nr_nod] = new Polygon(ai,ai1, 4);
}
}
}
}
}
}
repaint();
}
public void mouseMoved(MouseEvent e) {
}
public void mouseClicked(MouseEvent e)
{
int x = e.getX();
int y = e.getY();
int modifiers = e.getModifiers();
if(x < dim.width/2-15) {
//se sterge nodul pe care am dat click dreapta
if ((modifiers & InputEvent.BUTTON3_MASK) == InputEvent.BUTTON3_MASK ) {
nod = new Ellipse2D.Double(x_coord[nr_puncte-1]-15,y_coord[nr_puncte-1]-15,30,30);
if (nod.contains(x,y)) {
x_coord[nr_puncte-1]=0;
y_coord[nr_puncte-1]=0;
for(int j=0;j < nr_puncte;j++) {
if (edgepresent[nr_puncte-1][j]) {
edgepresent[nr_puncte-1][j] = false;
D[nr_puncte-1][j] = 999;
Pi[nr_puncte-1][j] = -1;
}
if(edgepresent[j][nr_puncte-1]) {
edgepresent[j][nr_puncte-1] = false;
D[j][nr_puncte-1] = 999;
Pi[j][nr_puncte-1] = -1;
}
}
nr_puncte--;
}
}
else {
if ((modifiers & InputEvent.BUTTON1_MASK) == InputEvent.BUTTON1_MASK && !clickinline) {
clicked = true;
if (!fw && !johnson) {
for(int i=0;i < nr_puncte;i++) {
for(int j=0;j < nr_puncte;j++)
if (sageti[i][j].contains(x,y)) {
edgecolor[i][j] = 1;
nodunu = i;
noddoi = j;
clickinline = true;
parent.optiuni.enable();
}
}
if (nr_puncte <= 8 && clickinline != true ) {
for(int i=0;i < nr_puncte;i++)
if (x_coord[i]==0 && y_coord[i]==0) {
x_coord[i] = x;
y_coord[i] = y;
zero = true;
break;
}
if (!zero) {
x_coord[nr_puncte] = x;
y_coord[nr_puncte] = y;
nr_puncte++;
}
}
}
else {
for(int i=0;i < nr_puncte;i++) {
nod = new Ellipse2D.Double(x_coord[i]-15,y_coord[i]-15,30,30);
if (nod.contains(x,y) && nr_noduri_sel < 2) {
if (nr_noduri_sel == 0) {nodstart = i; nr_noduri_sel++;}
else { nodend = i;nr_noduri_sel++;}
}
}
} }
}
}
zero = false;
repaint();
}
public void mouseExited(MouseEvent e){}
public void mouseEntered(MouseEvent e){}
public void updateLocation(MouseEvent e){}
public void keyPressed(KeyEvent key) {}
public void keyReleased(KeyEvent key) {}
public void keyTyped(KeyEvent key) {k = key.getKeyCode();}
public void drawarrow(int i, int j)
{
int i2 = x_coord[j] - x_coord[i];
int j2 = y_coord[j] - y_coord[i];
float f = (float)Math.sqrt((float)(i2 * i2 + j2 * j2));
float f1 = (float)i2 / f;
float f2 = (float)j2 / f;
int x_pos = x_coord[j] + (x_coord[i] - x_coord[j]) / 2;
int y_pos = y_coord[j] + (y_coord[i] - y_coord[j]) / 2;
int k = (int)(((float)x_pos - 3F * f1) + 6F * f2);
int l = (int)((float)x_pos - 3F * f1 - 6F * f2);
int i1 = (int)((float)x_pos + 6F * f1);
int j1 = (int)((float)y_pos - 3F * f2 - 6F * f1);
int k1 = (int)(((float)y_pos - 3F * f2) + 6F * f1);
int l1 = (int)((float)y_pos + 6F * f2);
ai[0] = k;
ai[1] = l;
ai[2] = i1;
ai[3] = k;
ai1[0] = j1;
ai1[1] = k1;
ai1[2] = l1;
ai1[3] = j1;
graf.fill(new Polygon(ai,ai1,4));
i2 = (int)Math.abs(7F * f2);
j2 = (int)Math.abs(7F * f1);
String s = new String("" + D[i][j]);
if(x_coord[i] > x_coord[j] && y_coord[i] >= y_coord[j])
graf.drawString(s, x_pos + i2, y_pos - j2);
if(x_coord[i] >= x_coord[j] && y_coord[i] < y_coord[j])
graf.drawString(s, x_pos - fmetrics.stringWidth(s) - i2, y_pos - j2);
if(x_coord[i] < x_coord[j] && y_coord[i] <= y_coord[j])
graf.drawString(s, x_pos - fmetrics.stringWidth(s), y_pos + fmetrics.getHeight());
if(x_coord[i] <= x_coord[j] && y_coord[i] > y_coord[j])
graf.drawString(s, x_pos + i2, y_pos + fmetrics.getHeight());
}
public void increaseWeight() {
if (clickinline)
D[nodunu][noddoi]++;
repaint();
}
public void decreaseWeight() {
if (clickinline)
D[nodunu][noddoi]--;
repaint();
}
public void finish() {
if(clickinline) {
edgecolor[nodunu][noddoi]=0;
if (D[nodunu][noddoi] == 0) {
D[nodunu][noddoi] = 999;
edgepresent[nodunu][noddoi] = false;
}
clickinline = false;
try {
parent.optiuni.buton5.setVisible(false);
parent.optiuni.buton6.setVisible(false);
parent.optiuni.buton7.setVisible(false);
}
catch (NullPointerException e) {}
repaint();
}
}
public void drawGrid(int xfirst , int yfirst) {
for(int i=0;i <= nr_puncte;i++) {
if (i!=0) {
graf.drawString(""+i,xfirst+25*i-15,yfirst);
graf.drawString(""+i,xfirst-13,yfirst+13*i);
}
graf.draw(new Line2D.Double(xfirst,yfirst+13*i,xfirst+25*nr_puncte,yfirst+13*i));
graf.draw(new Line2D.Double(xfirst+25*i,yfirst,xfirst+25*i,yfirst+13*nr_puncte));
}
}
public void drawMatrixNumbers(int xfirst, int yfirst,int DC[][]) {
for(int i=0;i < nr_puncte;i++) {
for(int j=0;j < nr_puncte;j++)
if (DC[i][j] == 999)
graf.drawString("INF",xfirst+(j+1)*25-19,yfirst+(i+1)*13);
else graf.drawString(""+DC[i][j],xfirst+(j+1)*25-15,yfirst+(i+1)*13);
}
}
public void makePiMatrix() {
for(int i=0;i < nr_puncte;i++) {
for(int j=0;j < nr_puncte;j++) {
DC[i][j]=D[i][j];
if(i!=j && DC[i][j] < 999 )
Pi[i][j] = i+1;
}
}
}
public void drawPiNumbers(int xfirst, int yfirst) {
for(int i=0;i < nr_puncte;i++) {
for(int j=0;j < nr_puncte;j++)
if (Pi[i][j] == -1)
graf.drawString("NIL",xfirst+(j+1)*25-23,yfirst+(i+1)*13);
else graf.drawString(""+Pi[i][j],xfirst+(j+1)*25-15,yfirst+(i+1)*13);
}
}
public void FloydWarshall() {
fw = true;
int suma = 0;
for(int i=0;i < nr_puncte+1;i++) {
for(int j=0;j < nr_puncte+1;j++)
if (i==0) G[i][j] = 0;
else if (j==0) G[i][j] = 999;
else G[i][j] = D[i-1][j-1];
}
calcLaturi();
if (BellmanFord(0)==0) parent.info.infodoc.showLine("string4");
for( int k = 0; k < nr_puncte; k++ )
for( int i = 0; i < nr_puncte; i++ )
for( int j = 0; j < nr_puncte; j++ ) {
if (DC[i][k] == 999 || DC[k][j] == 999) suma = 999;
else suma = DC[i][k] + DC[k][j];
if( DC[i][j] > suma ) {
DC[i][j] = DC[i][k] + DC[k][j];
Pi[i][j] = Pi[k][j];
}
}
repaint();
}
public void Example()
{
init();
nr_puncte = 5;
x_coord[0] = 100;
y_coord[0] = 50;
x_coord[1] = 300;
y_coord[1] = 50;
x_coord[2] = 50;
y_coord[2] = 140;
x_coord[3] = 250;
y_coord[3] = 230;
x_coord[4] = 120;
y_coord[4] = 230;
edgepresent[0][1] = true; D[0][1] = 3; drawarrow(0,1);sageti[0][1] = new Polygon(ai,ai1,4);
edgepresent[0][2] = true; D[0][2] = 8; drawarrow(0,2);sageti[0][2] = new Polygon(ai,ai1,4);
edgepresent[0][4] = true; D[0][4] = -4;drawarrow(0,4);sageti[0][4] = new Polygon(ai,ai1,4);
edgepresent[1][3] = true; D[1][3] = 1; drawarrow(1,3);sageti[1][3] = new Polygon(ai,ai1,4);
edgepresent[1][4] = true; D[1][4] = 7; drawarrow(1,4);sageti[1][4] = new Polygon(ai,ai1,4);
edgepresent[2][1] = true; D[2][1] = 4; drawarrow(2,1);sageti[2][1] = new Polygon(ai,ai1,4);
edgepresent[3][0] = true; D[3][0] = 2; drawarrow(3,0);sageti[3][0] = new Polygon(ai,ai1,4);
edgepresent[3][2] = true; D[3][2] = -5;drawarrow(3,2);sageti[3][2] = new Polygon(ai,ai1,4);
edgepresent[4][3] = true; D[4][3] = 6; drawarrow(4,3);sageti[4][3] = new Polygon(ai,ai1,4);
repaint();
}
public void PrintAllPairs(int Pi[][],int i, int j) {
if (i == j) ispath = true;
else if (Pi[i-1][j-1] == -1 ) { nopath = true;parent.info.infodoc.showLine("string1");}
else PrintAllPairs(Pi,i,Pi[i-1][j-1]);
pathVector[nr_elem] = j;
nr_elem++;
ispath = true;
}
public void reinit() {
nodstart = -1;
nodend = -1;
for(int i=0;i < 9;i++) pathVector[i] = 0;
nr_noduri_sel = 0;
nr_elem = 0;
ispath = false;
for(int i=0;i < nr_puncte;i++) {
for(int j=0;j < nr_puncte;j++)
edgecolor[i][j] = 0;
}
repaint();
}
void initialize(int source) {
for(int i=0;i < nr_puncte+1;i++) {
d[i] = 999;
s[i] = 0;
t[i] = -1;
}
d[source] = 0;
}
void relax(int u, int v) {
if (d[v] > d[u]+G[u][v]) { d[v] = d[u] + G[u][v]; t[v] = u;}
}
void relax1(PriorityQueue Q,int u, int v) {
if (Q.heapArray[v].key > d[u] + DC[u][Q.heapArray[v].nod-1]) {
Q.heapArray[v].key = d[u] + DC[u][Q.heapArray[v].nod-1]; t[Q.heapArray[v].nod-1] = u;
}
}
int BellmanFord(int source) {
initialize(source);
for(int i=0;i < nr_puncte+1;i++)
for(int j=0;j < nr_laturi;j++)
relax(e[j][0],e[j][1]);
for(int i=0;i < nr_laturi;i++)
if(d[e[i][1]] > d[e[i][0]]+G[e[i][0]][e[i][1]]) return 0;
return 1;
}
void Dijkstra(int source) {
int minKey = 0;
int u = 0;
initialize(source);
int x = nr_puncte+1;
PriorityQueue Q = new PriorityQueue(x,d);
while(Q.heapSize() > 0) {
minKey = Q.getMin();
u = Q.extractMin();
d[u] = minKey;
s[u] = 1;
for(int j=1;j <= Q.heapSize();j++) relax1(Q,u,j);
Q.makeHeap();
}
}
public void Johnson() {
johnson = true;
for(int i=0;i < nr_puncte+1;i++) {
for(int j=0;j < nr_puncte+1;j++)
if (i==0) G[i][j] = 0;
else if (j==0) G[i][j] = 999;
else G[i][j] = D[i-1][j-1];
}
calcLaturi();
if (BellmanFord(0)==0) parent.info.infodoc.showLine("string4");
else for(int i=0;i < nr_puncte+1;i++)
h[i]=d[i];
for(int i=0;i < nr_laturi;i++) {
G[e[i][0]][e[i][1]] = G[e[i][0]][e[i][1]] + h[e[i][0]] - h[e[i][1]];
if (e[i][0]!=0 && e[i][1]!=0) DC[e[i][0]-1][e[i][1]-1] = G[e[i][0]][e[i][1]];
}
for(int i=0;i < nr_puncte;i++) {
Dijkstra(i);
for(int j=0;j < nr_puncte;j++) {
if (t[j]== -1) Pi[i][j] = t[j];
else if (i!=j ) Pi[i][j] = t[j]+1;
else Pi[i][j] = t[i];
int suma = 0;
if (d[j] == 999 || h[j+1] == 999 || h[i+1] == 999) suma = 999;
else suma = d[j] +h[j+1] - h[i+1];
matback[i][j] = suma;
}
}
for(int i=0;i < nr_puncte;i++) {
for(int j=0;j < nr_puncte;j++)
DC[i][j] = matback[i][j];
}
repaint();
}
void calcLaturi() {
nr_laturi = 0;
for(int i=0;i < nr_puncte+1;i++) {
for(int j=0;j < nr_puncte+1;j++)
if (G[i][j] < 999 && i!=j) {
e[nr_laturi][0] = i;
e[nr_laturi][1] = j;
nr_laturi++;
}
}
}
Graphics2D g2D;
Graphics2D graf;
BufferedImage bufferimg;
int D[][]; //matricea de adiacenta
public int DC[][]; //copia matricei D
int nr_puncte; //numarul de noduri
int x_coord[];//coordonata x a nodului
int y_coord[];//coordonata y a nodului
public int Pi[][]; //matricea predecesorilor
int pathVector[]; //vector in care se retin nodurile care alcatuiesc un drum minim
int nr_elem; //numarul curent de elemente din vectorul pathVector
public int nodstart;
public int nodend;
int nr_nod; //numarul nodului pe care s-a apasat mouse-ul
int nodunu,noddoi;
boolean clicked;
boolean pressed;
boolean sageata_clicked;
boolean edgepresent[][];
boolean clickinline; //daca s-a dat click pe o linie
boolean iesire;
boolean zero; //arata daca exista un nod cu coordonatele (0,0)
boolean fw;
boolean nopath;
boolean ispath;
int edgecolor[][];
Shape nod;
Shape linie;
Shape[][] sageti; //matricea care retine poligoanele (sagetile)
FontMetrics fmetrics;
Font ftext; //tipul fonturilor folosite
int nr_sageti;
int ai[]; //vectori care retin coordonatele sagetilor
int ai1[];
Proiect parent;
int x,y; //coordonatele curente in care s-a apsta butonul mouseului
int k; //codul tastei apasate
Dimension dim; //dimensiunea suprafetei de desenare
int numar_graf;//retine de cate ori s-a apelat functia init()
public int nr_noduri_sel; //numarul de noduri selectate dupa ce s-a aplicat una din teoreme
int d[];
int s[];
int t[];
int h[];
int G[][];
int e[][];
int matback[][];
int drum[];
int numar_el_drum;
int source;
int nr_laturi;//numarul de laturi pentru matricea G
public boolean johnson;
PriorityQueue Q;
}