euler circuit

[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

[red floyd]

dk*******@gmail.com wrote:

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.

Your question is answered here:
http://www.parashift.com/c++-faq-lit...st.html#faq5.2

[mliptak]

On Mar 19, 3:52 am, red floyd <[e-mail]:

[e-mail] wrote:

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.

Your question is answered here:http://www.parashift.com/c++-faq-lit...st.html#faq5.2

Or here:
http://www.parashift.com/c++-faq-lit...t.html#faq-5.2

[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.

[Zara]

On 19 Mar 2007 05:41:26 -0700, dk*******@gmail.com wrote:

>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

[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[i][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[i][j] == 1) hm++;
}
}

int hm()
{
int a = 0;
for (int i = 0; i < cik; i++)
for (int j = 0; j < cik; j++)
if (graphs[i][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[i][j] != 0) {
if (graphs[i][j] == 2)
{
graphs[i][j] = 1;
ar2 = true;
}
if (graphs[i][j] == 1 && !ar2)
{
the_last = i;

graphs[i][j] = -1;
graphs[j][i] = -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[i][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][i]][last[1][i]] = 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[i][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[i][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[i][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[i][j] == 1) kiek++;
}
}

int kiek()
{
int a = 0;
for (int i = 0; i < cik; i++)
for (int j = 0; j < cik; j++)
if (grafai[i][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[i][j] != 0) {
if (grafai[i][j] == 2)
{
grafai[i][j] = 1;
ar2 = true;
}
if (grafai[i][j] == 1 && !ar2)
{
paskutinis = i;

grafai[i][j] = -1;
grafai[j][i] = -1;
i = j - 1;
test = true;
}
ar2=false;
}
// if (grafai[i][j] == 2) grafai[i][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[i][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][i]][laikinas[1][i]] = 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[i][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[i][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[i][j]==1) test++;
return test/2+1;
}
}

[Ralph D. Ungermann]

dk*******@gmail.com wrote:

>
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.

[Reporter]

On Mar 20, 3:32 pm, "Ralph D. Ungermann" <[e-mail]:

[e-mail] wrote:

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.

Amazing