euler circuit

D

dkultasev

Hello,
could anyone help with euler circuit ? I tried to find it, found some,
but they are not working. Tried to write my own one, but it supposed
to be slow with big graphs because it trying all possibles situations.
Prefer to get something on c++ or java, but other languages are
welcome also.
Tnanks
 
D

dkultasev

The problem is, that I did that program, and it is finding euler
circuit. But it is not good because the algorithm was written by
myself.
 
Z

Zara

The problem is, that I did that program, and it is finding euler
circuit. But it is not good because the algorithm was written by
myself.

Show your code, so it may be commented

Zara
 
D

dkultasev

It might be not the smart one, but... I tried to translate into
English language, but I haven't check, because I just reinstalled my
OS and don't have anything installed on it yet. I put not english, but
working source after this one.

package euler;

public class Programa
{
static int graphs[][];
static int i1, j1;
static int which;
static int till;
static int the_end;
static int routes;
static int edges;
static int cik = 7;

public Programa()
{
graphs = new int[cik][cik];
}

public static void main(String[] args)
{
Programa a = new Programa();
a.formatArray();
edges = a.nEdges();
a.indexs();
int how_much = a.hm();
boolean tess;
for (int i = 0; i < 1000; i++)
tess = a.way(1);
}
public void formatArray()
{
for (int i = 0; i < cik; i++)
for (int j = 0; j < cik; j++)
graphs[j] = 0;

graphs[0][1] = 1;
graphs[0][5] = 1;
graphs[0][3] = 1;
graphs[0][6] = 1;

graphs[1][0] = 1;
graphs[1][2] = 1;

graphs[2][1] = 1;
graphs[2][3] = 1;
graphs[2][4] = 1;
graphs[2][5] = 1;

graphs[3][0] = 1;
graphs[3][2] = 1;


graphs[4][5] = 1;
graphs[4][2] = 1;


graphs[5][0] = 1;
graphs[5][2] = 1;
graphs[5][4] = 1;
graphs[5][6] = 1;

graphs[6][0] = 1;
graphs[6][5] = 1;


}
void indexs()
{
formatArray();
int hm = 0;
for (int i = 0; i < cik; i++)
for (int j = 0; j < cik; j++)
{
if (graphs[j] == 1) hm++;
}
}

int hm()
{
int a = 0;
for (int i = 0; i < cik; i++)
for (int j = 0; j < cik; j++)
if (graphs[j] == 0) a++;
return a;
}
boolean way(int hm)
{
int the_last=0;

int i = 0;
int j = 0;
boolean test = false;
boolean ar2 = false;
String ats = "";
if (routes!=0)
test2(routes);
for (i = 0; i < cik; i++)
{
if (testIt(i)) { //tikrina ar yra vienetuku eiluteje
while (!test) { //eina till pirmo vienetuko
if (graphs[j] != 0) {
if (graphs[j] == 2)
{
graphs[j] = 1;
ar2 = true;
}
if (graphs[j] == 1 && !ar2)
{
the_last = i;

graphs[j] = -1;
graphs[j] = -1;
i = j - 1;
test = true;
}
ar2=false;
}
if (j < cik-1) j++;
else test = true;
}
ats=ats+the_last;
test = false;
j = 0;

}
else
{
ats= ats+i;
routes++;
if ((ats.length()==edges || ats.length()==edges) &&
ats.toCharArray()[0] == ats.toCharArray()[edges-1])
System.out.println(ats + " - Oilerio ciklas");
else if (ats.length()==edges || ats.length()==edges + 1)
System.out.println(ats + " - Oilerio kelias");
return true;
}
}
routes++;
System.out.println("");

return false;
}
boolean testIt(int i)
{
for (int jj = 0; jj <cik; jj++)
{
if (graphs[jj] == 1) return true;
}
return false;
}
public void test2(int xxx)
{
formatArray();
int eil = 1;
eil = xxx/(edges*2-2) + 1;
int last[][] = new int[2][xxx];
int temp = xxx;
int test = 0;
for (int i = 0; i < eil; i++)
{
ffind(temp);
last[0][test] = i1;
last[1][test] = j1;
test++;
temp = temp - test*(edges*2-2);
}
for (int i = 0; i < test; i++)
{
graphs[last[0]][last[1]] = 2;
}

}
public void ffind(int xxx)
{
int hm = 0;
for (int i =0; i < cik; i++)
for (int j = 0; j < cik; j++)
{
if (graphs[j] == 1 && xxx == hm)
{
i1=i; j1=j;
}
hm++;
}
}



public int nEdges()
{
int test = 0;
for (int i = 0; i < cik; i++)
for (int j = 0; j < cik; j++)
if (graphs[j]==1) test++;
return test/2+1;
}
}

//--------------------------------------------------------------------------------------------

package euler;

public class Programa
{
static int grafai[][];
static int i1, j1;
static int kelintas;
static int iki;
static int pabaiga;
static int kiek_marsrutu;
static int kiek_briaunu;
static int cik = 7;

public Programa()
{
grafai = new int[cik][cik];
}

public static void main(String[] args)
{
Programa a = new Programa();
a.suformuotiMasyva();
kiek_briaunu = a.kiekBriaunu();
a.indeksai();
int kiekis = a.kiek();
boolean tess;
for (int i = 0; i < 1000; i++)
tess = a.kelias(1);
}
public void suformuotiMasyva()
{
for (int i = 0; i < cik; i++)
for (int j = 0; j < cik; j++)
grafai[j] = 0;

grafai[0][1] = 1;
grafai[0][5] = 1;
grafai[0][3] = 1;
grafai[0][6] = 1;

grafai[1][0] = 1;
grafai[1][2] = 1;
// grafai[1][3] = 1;
// grafai[1][4] = 1;

grafai[2][1] = 1;
grafai[2][3] = 1;
grafai[2][4] = 1;
grafai[2][5] = 1;

grafai[3][0] = 1;
// grafai[3][1] = 1;
grafai[3][2] = 1;
// grafai[3][4] = 1;

grafai[4][5] = 1;
grafai[4][2] = 1;
// grafai[4][2] = 1;
// grafai[4][3] = 1;

grafai[5][0] = 1;
grafai[5][2] = 1;
grafai[5][4] = 1;
grafai[5][6] = 1;

grafai[6][0] = 1;
grafai[6][5] = 1;
// grafai[6][2] = 1;
// grafai[6][3] = 1;


}
void indeksai()
{
suformuotiMasyva();
int kiek = 0;
for (int i = 0; i < cik; i++)
for (int j = 0; j < cik; j++)
{
if (grafai[j] == 1) kiek++;
}
}

int kiek()
{
int a = 0;
for (int i = 0; i < cik; i++)
for (int j = 0; j < cik; j++)
if (grafai[j] == 0) a++;
return a;
}
boolean kelias(int kiek)
{
int paskutinis=0;

int i = 0;
int j = 0;
boolean test = false;
boolean ar2 = false;
String ats = "";
if (kiek_marsrutu!=0)
{
test2(kiek_marsrutu);
// spausdintiGrafus();

}
// spausdintiGrafus();
for (i = 0; i < cik; i++)
{
if (patikra(i)) { //tikrina ar yra vienetuku eiluteje
while (!test) { //eina iki pirmo vienetuko
if (grafai[j] != 0) {
if (grafai[j] == 2)
{
grafai[j] = 1;
ar2 = true;
}
if (grafai[j] == 1 && !ar2)
{
paskutinis = i;

grafai[j] = -1;
grafai[j] = -1;
i = j - 1;
test = true;
}
ar2=false;
}
// if (grafai[j] == 2) grafai[j]=1;
if (j < cik-1) j++;
else test = true;
}
ats=ats+paskutinis;
test = false;
j = 0;
// spausdint();

}
else
{
ats= ats+i;
kiek_marsrutu++;
if ((ats.length()==kiek_briaunu || ats.length()==kiek_briaunu)
&& ats.toCharArray()[0] == ats.toCharArray()[kiek_briaunu-1])
System.out.println(ats + " - Oilerio ciklas");
else if (ats.length()==kiek_briaunu ||
ats.length()==kiek_briaunu + 1) System.out.println(ats + " - Oilerio
kelias");
return true;
}
}
kiek_marsrutu++;
System.out.println("");
// test2(kiek_marsrutu);

return false;
}
boolean patikra(int i)
{
for (int jj = 0; jj <cik; jj++)
{
if (grafai[jj] == 1) return true;
}
return false;
}
public void test2(int kuris)
{
suformuotiMasyva();
int eil = 1;
eil = kuris/(kiek_briaunu*2-2) + 1;
int laikinas[][] = new int[2][kuris];
int laik = kuris;
int test = 0;
for (int i = 0; i < eil; i++)
{
surasti(laik);
laikinas[0][test] = i1;
laikinas[1][test] = j1;
test++;
laik = laik - test*(kiek_briaunu*2-2);
}
for (int i = 0; i < test; i++)
{
grafai[laikinas[0]][laikinas[1]] = 2;
}

}
public void surasti(int kuris)
{
int kiek = 0;
for (int i =0; i < cik; i++)
for (int j = 0; j < cik; j++)
{
if (grafai[j] == 1 && kuris == kiek)
{
i1=i; j1=j;
}
kiek++;
}
}

public void spausdintiGrafus()
{
for (int i = 0 ; i < cik; i++)
{
for (int j = 0; j < cik; j++)
System.out.print(grafai[j] + " ");
System.out.println("");
}

}


public int kiekBriaunu()
{
int test = 0;
for (int i = 0; i < cik; i++)
for (int j = 0; j < cik; j++)
if (grafai[j]==1) test++;
return test/2+1;
}
}
 
R

Ralph D. Ungermann

package euler;

public class Programa
{ //...
public static void main(String[] args)
{
Programa a = new Programa();
a.formatArray(); //...
boolean tess;

Sorry, but this is not a C++ program.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top