EDK : FSL macros defined by Xilinx are wrong

[Hans]

"Antti" <Antti.Lukats@xilant.com> wrote in message
news:1158775355.824339.155710@m7g2000cwm.googlegroups.com...

bart schrieb:

it's my humble understanding that Mico32 is truly RTL, i.e. we do not
use any library elements, so it should be portable. (although, of
course, we'd like for you to buy our chips!)
rgds,
Bart Borosky, Lattice, online marketing manager

Source yes, but not RTL. My guess it's lots of instantiated primitives,
thus not portable.

Yes it is.

but it uses verilog at such advanced level that is not supported
by Xilinx XST synthesis, e.g. it is only useable with Synplify
as synthesis tool

I believe they have an OEM agreement with Mentor so Precision should be OK

as well (I hope

Hans
www.ht-lab.com

Antti

 

[John McGrath]

Jon Beniston wrote:

but it uses verilog at such advanced level that is not supported
by Xilinx XST synthesis, e.g. it is only useable with Synplify
as synthesis tool

It's about time Xilinx had full Verilog 2001 support really. What year
is it?

Still, on the plus side, if you do use Synplify, at least the rest of
your design might work too ;-)

Cheers,
Jon

In fairness, the verilog2001 support is not the issue.
The main reason the source did not compile was XST's adherence to some
rules, like naming generate statement begin blocks, etc, and an issue
with using clogb2 in a parameter.
All small issues really - few tweaks here and there, took me a half an
hour to do, and it synthesized!

This was for a (very) basic configuration, I just tried to synth this
to the slowest speed grade V5,

Number of Slice Registers: 780
Number of Slice LUTs: 1174
Number used as Logic: 1046
Number used as Memory: 128
Number used as RAM: 128

and it came out at 170MHz (post synth timing only - did not run PAR).
Would be Interesting to see if it works, and with more features turned
on..though I have no time to test it..
But XST can do it - with relatively small amount of code massaging.

 

[Jon Beniston]

In fairness, the verilog2001 support is not the issue.
The main reason the source did not compile ... and an issue
with using clogb2 in a parameter.

Is this not a Verilog 2001 feature that isn't supported?

Cheers,
Jon

 

[rickman]

John McGrath wrote:

Jon Beniston wrote:
but it uses verilog at such advanced level that is not supported
by Xilinx XST synthesis, e.g. it is only useable with Synplify
as synthesis tool

It's about time Xilinx had full Verilog 2001 support really. What year
is it?

Still, on the plus side, if you do use Synplify, at least the rest of
your design might work too ;-)

Cheers,
Jon

In fairness, the verilog2001 support is not the issue.
The main reason the source did not compile was XST's adherence to some
rules, like naming generate statement begin blocks, etc, and an issue
with using clogb2 in a parameter.
All small issues really - few tweaks here and there, took me a half an
hour to do, and it synthesized!

This was for a (very) basic configuration, I just tried to synth this
to the slowest speed grade V5,

Number of Slice Registers: 780
Number of Slice LUTs: 1174
Number used as Logic: 1046
Number used as Memory: 128
Number used as RAM: 128

and it came out at 170MHz (post synth timing only - did not run PAR).
Would be Interesting to see if it works, and with more features turned
on..though I have no time to test it..
But XST can do it - with relatively small amount of code massaging.

I don't understand the idea of using post syn timing. Is that at all
accurate? Why not let it do a PAR and see what kind of real results
you get? I guess I shouldn't knock post syn timing. The eval I did on
my CPU gave pretty close numbers between syn and PAR. I think it
actually sped up a little in PAR.

 

[Jon Beniston]

I don't understand the idea of using post syn timing. Is that at all
accurate?

Sometimes it is close, sometimes it is woefully inaccurate.

Why not let it do a PAR and see what kind of real results you get?

It's the only way to know.

Cheers,
Jon

 

[John McGrath]

Jon Beniston wrote:

I don't understand the idea of using post syn timing. Is that at all
accurate?

Sometimes it is close, sometimes it is woefully inaccurate.

Why not let it do a PAR and see what kind of real results you get?

It's the only way to know.

Cheers,
Jon

True - and as soon as I know you will know! - I left it PARing as I
left the office, and won't see the result myself until I am back
monday. However, from the post MAP timing, it looked good. I also put a
clock constraint of 200MHz on it (just to see). I'm curious myself. I
think the result would be more useful if I included a few more of the
core features, like debug logic, jtag, multiplier support etc. I just
left it with the defaults.

Regarding the verilog2001 support - XST seems to have clogb2 support,
but just there seemed to be some restrictions on where it can be used -
it could be because the RTL code is using it in a way that violates the
strict rules on the LRM, or it could be XST simply needs to allow the
use of this function more liberally (like in a preprocessing function
when reading the RTL, as its used as a constant), who knows. All I know
is it was not much effort to make it work, so hardly makes XST unsable
for synthesis of this core. This info mught help a few people out who
do not have access to alternatives....but if you really want to knock
synthesizers..check out design compiler in an asic context *shudder*.

 

[Antti]

John McGrath schrieb:

Jon Beniston wrote:
I don't understand the idea of using post syn timing. Is that at all
accurate?

Sometimes it is close, sometimes it is woefully inaccurate.

Why not let it do a PAR and see what kind of real results you get?

It's the only way to know.

Cheers,
Jon


True - and as soon as I know you will know! - I left it PARing as I
left the office, and won't see the result myself until I am back
monday. However, from the post MAP timing, it looked good. I also put a
clock constraint of 200MHz on it (just to see). I'm curious myself. I
think the result would be more useful if I included a few more of the
core features, like debug logic, jtag, multiplier support etc. I just
left it with the defaults.

Regarding the verilog2001 support - XST seems to have clogb2 support,
but just there seemed to be some restrictions on where it can be used -
it could be because the RTL code is using it in a way that violates the
strict rules on the LRM, or it could be XST simply needs to allow the
use of this function more liberally (like in a preprocessing function
when reading the RTL, as its used as a constant), who knows. All I know
is it was not much effort to make it work, so hardly makes XST unsable
for synthesis of this core. This info mught help a few people out who
do not have access to alternatives....but if you really want to knock
synthesizers..check out design compiler in an asic context *shudder*.

whah? it hasnt finished? you should have used relaxed timing
constraints.

A microblaze design with all CPU options enabled and with Floating
Point unit included, targetting XC3S4000 using 489 IO's and having
192KB used local memory runs within some minutes until bitstream done.
(takes 14% BTW from s3-4000)

I bet your LM32 test desing is far less complex

getting 200MHz in slowest speed V5 seems unlikely, OpenFire demo design
did pass 200MHz in fastest V5 after a few xplorer runs.

so I bet the LatticeMico32 want pass timing on 200Mhz

Antti

 

[Jon Beniston]

True - and as soon as I know you will know! - I left it PARing as I
left the office, and won't see the result myself until I am back
monday. However, from the post MAP timing, it looked good. I also put a
clock constraint of 200MHz on it (just to see).

Sometimes overconstraining the design too much will mean the tool will
give up earlier than it otherwise would if it was quite close, or so
I've been led to believe.

I'm curious myself. I
think the result would be more useful if I included a few more of the
core features, like debug logic, jtag, multiplier support etc. I just
left it with the defaults.

The JTAG logic requires Lattice specific cells, so you wouldn't be able
to use that, unless you converted it to work with the Xilinx JTAG
primitive.

Regarding the verilog2001 support - XST seems to have clogb2 support,

clogb2 is a function defined in the Mico32 source.

but just there seemed to be some restrictions on where it can be used
it could be because the RTL code is using it in a way that violates the
strict rules on the LRM, or it could be XST simply needs to allow the
use of this function more liberally (like in a preprocessing function
when reading the RTL, as its used as a constant), who knows.

I do XST doesn't support Verilog 2001 constant functions, which is
what is being used here.

Cheers,
Jon

 

[rickman]

Perhaps a bit off topic, but I use Google to access these newsgroups
and this thread is not displaying properly. Instead of showing a post
number beside each post in the tree to the left, it puts the number 1
beside each one. That makes it very hard to see just which post is
which in the thread.

Does anyone else see this or is it just me?

 

[larwe]

rickman wrote:

Perhaps a bit off topic, but I use Google to access these newsgroups
and this thread is not displaying properly. Instead of showing a post
number beside each post in the tree to the left, it puts the number 1
beside each one. That makes it very hard to see just which post is

I see it too. A problem shared is a problem halved?

 

[Isaac Bosompem]

larwe wrote:

rickman wrote:
Perhaps a bit off topic, but I use Google to access these newsgroups
and this thread is not displaying properly. Instead of showing a post
number beside each post in the tree to the left, it puts the number 1
beside each one. That makes it very hard to see just which post is

I see it too. A problem shared is a problem halved?

Same here, weird..

-Isaac

 

[Hans-Bernhard Broeker]

In comp.arch.embedded rickman <gnuarm@gmail.com> wrote:

Perhaps a bit off topic, but I use Google to access these newsgroups
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Well, as some people used to jest at the height of the "intel inside"
logo campaign: how's that for a problem neatly encircled.

As well as Google knows how to do a web search engine, as bad is their
grasp of Usenet. They're arguably the biggest threat to Usenet's
continuing existence since "the September that never ended".

--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

 

[John McGrath]

Antti wrote:

John McGrath schrieb:

Jon Beniston wrote:
I don't understand the idea of using post syn timing. Is that at all
accurate?

Sometimes it is close, sometimes it is woefully inaccurate.

Why not let it do a PAR and see what kind of real results you get?

It's the only way to know.

Cheers,
Jon


True - and as soon as I know you will know! - I left it PARing as I
left the office, and won't see the result myself until I am back
monday. However, from the post MAP timing, it looked good. I also put a
clock constraint of 200MHz on it (just to see). I'm curious myself. I
think the result would be more useful if I included a few more of the
core features, like debug logic, jtag, multiplier support etc. I just
left it with the defaults.

Regarding the verilog2001 support - XST seems to have clogb2 support,
but just there seemed to be some restrictions on where it can be used -
it could be because the RTL code is using it in a way that violates the
strict rules on the LRM, or it could be XST simply needs to allow the
use of this function more liberally (like in a preprocessing function
when reading the RTL, as its used as a constant), who knows. All I know
is it was not much effort to make it work, so hardly makes XST unsable
for synthesis of this core. This info mught help a few people out who
do not have access to alternatives....but if you really want to knock
synthesizers..check out design compiler in an asic context *shudder*.

whah? it hasnt finished? you should have used relaxed timing
constraints.

A microblaze design with all CPU options enabled and with Floating
Point unit included, targetting XC3S4000 using 489 IO's and having
192KB used local memory runs within some minutes until bitstream done.
(takes 14% BTW from s3-4000)

I bet your LM32 test desing is far less complex

getting 200MHz in slowest speed V5 seems unlikely, OpenFire demo design
did pass 200MHz in fastest V5 after a few xplorer runs.

so I bet the LatticeMico32 want pass timing on 200Mhz

Antti

Sorry to give the wrong impression about how long it took - PAR did not
take that long, it was just the case that I started PARing right before
leaving the office on Thursday evening, and was not due back in to see
the result until today - The actual PAR time was 33mins with the 200MHz
constraint.

And now for the result:
182MHz post PAR timing.

Again - this was just a bare-bones system - purely proof of concept
that XST could do it! I did not use any techniques to improve the
timing result, standard levels of all options, and no xplorer. It took
3% of a V5 LX50 device.

It would be interesting to see what could be seqeezed out of this
design and speed grade with the right options, or maybe using
PlanAhead, but I'll leave that to others.

 

[Weng Tianxiang]

Arthur J. O'Dwyer wrote:

On Sun, 24 Sep 2006, Weng Tianxiang wrote:
eKo1 wrote:

Let V' be a subset of V. V' is a vertex cover if it satisfies the
following test:

E' = Ř
for each v in V'
for each edge e in E
if v is incident to e then
add e to E'
end if
end for
end for
if |E| = |E'| then
return true // V' is a vertex cover
end if
return false

Would this be correct?

Hi eKo1,
The algorithm you mentioned for a vertex cover is right.

Yes, that's right. (And it suggests a trivial brute-force algorithm
to find a minimum vertex cover:

M = V
for each V' in V
if (V' is a vertex cover of G) then
if |V'| < |M| then
M = V
end if
end if
end for
return M

Now M is a minimum vertex cover.)


Here is my full new algorithm that can get minimum vertex cover:

To make discussion simpler, we assume that every vertex has a positive
integer, starting with 1 to n and input cells have the following
structure:
(edge count, edge starting vertex, edge ending vertexes).

For example vertex 1 has edges: (1, 2), (1, 3), (1, 4), then its input
cell has the following representation: (3, 1, 2, 3, 4). Cell length
vary dependent on the cell's degree, or the number of edges which is
incident on the cell.

Whoof, that's a clumsy representation! Next time, consider using a
more natural representation, such as "Each vertex has a list of
neighbors. For example, vertex 1 has neighbors {2,3,4}."

Here is new full algorithm to get minimum vertex cover:
1. Count = 0.
2. If input cell is empty, algorithm ends, otherwise
Sort the input cell serials based on count in increasing order.

What are the "input cell serials"? I'm guessing you mean to sort the
cells in increasing order by degree, i.e., the cells with lower degree
come first in the list. Okay, but let me know if I'm wrong.

3. for all vertexes with edge count = 1, do following:
a. Set original starting vertex;

What?

b. Count++;
c. Print out its edge ending vertex #; (only one)
d. Delete its input cell;
e. In the edge ending vertex cell, do the followings:
a. delete the original starting vertex in edge ending
vertexes area;

What?

b. edge count is decreased by 1;
c. if edge count = 1, set current ending vertex as new
original starting vertex and go to b.
d. if edge count = 0, delete the cell;
4. If input cell is empty, algorithm ends, otherwise
sort the input cell serials based on count in decreasing order.

What? What is the "input cell"? What is an "empty" cell --- is ()
the only empty cell, or could (0, 5) be considered empty too?

5. If there is only one cell that has the largest degree, select the
cell
and go to 6. If there are more than one cell that have the equal
largest degree, select the cell that has not been the end vertex
of the last selected cell with the largest degree, or select any of
them
if all of them have have been the end vertexes of last selected cell

What? What?

(snip much more gibberish)

Manually I tried more than 20 graphs and get the right answers for
every graph.

Good for you.

Do you have any smart tips?

Yes. Stop trying to find a polynomial algorithm for minimum vertex
cover until you've read at least one existing (non-polynomial) algorithm
and understand how it works. Also, try to write in plain English, or,
failing that, some common programming language.

If you can find a graph that fails the algorithm, please let me know.

Yes, I can. So now you know.

-Arthur

Hi Arthur,
I cannot read the page. Can you please post the page on the group or
send me an email?

My email address is wtxwtx at gmail dot com (without space).

I don't know if my algorithm is the same as the one you mentioned.

Actually I checked my algorithm with more than 20 hand-drawn graphs and
all results generated are the minimum vertex cover, no exception!!!

Otherwise I couldn't publish my 2nd version so quickly. If another
error is found, I can also quickly change my design to correct the
error without destroying the full design.

The key point is:
1. First delete all claws until there are no any claws; (Claw is a
vertex of degree 1).
2. Next delete the vertex with largest degree and mark its neighbors to
keep them from being selected next time unless next time all vertexes
that have the largest degree are its neighbors. Later if a vertex's
edge is deleted, the vertex's neighbor mark should be deleted too if
any.
3. Repeat 1. and 2. until all input cells are deleted.

I will start writing a program in C and write some programs to generate
random graphs to check if there are any violations:
1. Randomly generate a graph;
2. Generate its minimum vertex cover, m= |V'| by my program.
3. Check C(n, m-1) choices to see if any of them meets the minimum
vertex cover.

I have "An introduction to Algorithm" written by Thomas H. Cormen etc.
It has a problem 35.1-3:
Professor Nixon proposes the following heuristic to solve the
vertex-cover problem. Repeatedly select a vertex of highest degree, and
remove all of its incident edges. Give an example to show that the
professor's heuristic doesn't not have an approximation ratio of 2.
(Hint: Try a bipartite graph with vertexes of uniform degree on the
left and vertexes of varying degree on the right. )

That is exactly what I suggested in my first version. But with the
problem exposed, I changed my strategy to delete any claws first, then
do the selection.

If you can post a graph that fails my algorithm, it will be great!!!

Thank you.

Weng

 

[Patricia Shanahan]

Weng Tianxiang wrote:
....

The key point is:
1. First delete all claws until there are no any claws; (Claw is a
vertex of degree 1).
2. Next delete the vertex with largest degree and mark its neighbors to
keep them from being selected next time unless next time all vertexes
that have the largest degree are its neighbors. Later if a vertex's
edge is deleted, the vertex's neighbor mark should be deleted too if
any.
3. Repeat 1. and 2. until all input cells are deleted.

At some stages in all this deleting, you presumably tag some vertices as
being members of the resulting cover. Could you restate the algorithm
making it clear which they are?

Thanks,

Patricia

 

[David Ashley]

Weng Tianxiang wrote:

Arthur J. O'Dwyer wrote:

On Sun, 24 Sep 2006, Weng Tianxiang wrote:

eKo1 wrote:

Let V' be a subset of V. V' is a vertex cover if it satisfies the
following test:

E' = Ř
for each v in V'
for each edge e in E
if v is incident to e then
add e to E'
end if
end for
end for
if |E| = |E'| then
return true // V' is a vertex cover
end if
return false

Would this be correct?

Hi eKo1,
The algorithm you mentioned for a vertex cover is right.

Yes, that's right. (And it suggests a trivial brute-force algorithm
to find a minimum vertex cover:

M = V
for each V' in V
if (V' is a vertex cover of G) then
if |V'| < |M| then
M = V
end if
end if
end for
return M

Now M is a minimum vertex cover.)



Here is my full new algorithm that can get minimum vertex cover:

To make discussion simpler, we assume that every vertex has a positive
integer, starting with 1 to n and input cells have the following
structure:
(edge count, edge starting vertex, edge ending vertexes).

For example vertex 1 has edges: (1, 2), (1, 3), (1, 4), then its input
cell has the following representation: (3, 1, 2, 3, 4). Cell length
vary dependent on the cell's degree, or the number of edges which is
incident on the cell.

Whoof, that's a clumsy representation! Next time, consider using a
more natural representation, such as "Each vertex has a list of
neighbors. For example, vertex 1 has neighbors {2,3,4}."


Here is new full algorithm to get minimum vertex cover:
1. Count = 0.
2. If input cell is empty, algorithm ends, otherwise
Sort the input cell serials based on count in increasing order.

What are the "input cell serials"? I'm guessing you mean to sort the
cells in increasing order by degree, i.e., the cells with lower degree
come first in the list. Okay, but let me know if I'm wrong.


3. for all vertexes with edge count = 1, do following:
a. Set original starting vertex;

What?


b. Count++;
c. Print out its edge ending vertex #; (only one)
d. Delete its input cell;
e. In the edge ending vertex cell, do the followings:
a. delete the original starting vertex in edge ending
vertexes area;

What?


b. edge count is decreased by 1;
c. if edge count = 1, set current ending vertex as new
original starting vertex and go to b.
d. if edge count = 0, delete the cell;
4. If input cell is empty, algorithm ends, otherwise
sort the input cell serials based on count in decreasing order.

What? What is the "input cell"? What is an "empty" cell --- is ()
the only empty cell, or could (0, 5) be considered empty too?


5. If there is only one cell that has the largest degree, select the
cell
and go to 6. If there are more than one cell that have the equal
largest degree, select the cell that has not been the end vertex
of the last selected cell with the largest degree, or select any of
them
if all of them have have been the end vertexes of last selected cell

What? What?

(snip much more gibberish)


Manually I tried more than 20 graphs and get the right answers for
every graph.

Good for you.


Do you have any smart tips?

Yes. Stop trying to find a polynomial algorithm for minimum vertex
cover until you've read at least one existing (non-polynomial) algorithm
and understand how it works. Also, try to write in plain English, or,
failing that, some common programming language.


If you can find a graph that fails the algorithm, please let me know.

Yes, I can. So now you know.

-Arthur


Hi Arthur,
I cannot read the page. Can you please post the page on the group or
send me an email?

My email address is wtxwtx at gmail dot com (without space).

I don't know if my algorithm is the same as the one you mentioned.

Actually I checked my algorithm with more than 20 hand-drawn graphs and
all results generated are the minimum vertex cover, no exception!!!

Otherwise I couldn't publish my 2nd version so quickly. If another
error is found, I can also quickly change my design to correct the
error without destroying the full design.

The key point is:
1. First delete all claws until there are no any claws; (Claw is a
vertex of degree 1).
2. Next delete the vertex with largest degree and mark its neighbors to
keep them from being selected next time unless next time all vertexes
that have the largest degree are its neighbors. Later if a vertex's
edge is deleted, the vertex's neighbor mark should be deleted too if
any.
3. Repeat 1. and 2. until all input cells are deleted.

I will start writing a program in C and write some programs to generate
random graphs to check if there are any violations:
1. Randomly generate a graph;
2. Generate its minimum vertex cover, m= |V'| by my program.
3. Check C(n, m-1) choices to see if any of them meets the minimum
vertex cover.

I have "An introduction to Algorithm" written by Thomas H. Cormen etc.
It has a problem 35.1-3:
Professor Nixon proposes the following heuristic to solve the
vertex-cover problem. Repeatedly select a vertex of highest degree, and
remove all of its incident edges. Give an example to show that the
professor's heuristic doesn't not have an approximation ratio of 2.
(Hint: Try a bipartite graph with vertexes of uniform degree on the
left and vertexes of varying degree on the right. )

That is exactly what I suggested in my first version. But with the
problem exposed, I changed my strategy to delete any claws first, then
do the selection.

If you can post a graph that fails my algorithm, it will be great!!!

Thank you.

Weng

Weng,

Did you mean to post this to comp.arch.fpga?

It's an interesting problem and all, but...?

-Dave

--
David Ashley http://www.xdr.com/dash
Embedded linux, device drivers, system architecture

 

[Weng Tianxiang]

Patricia Shanahan wrote:

Weng Tianxiang wrote:
...
The key point is:
1. First delete all claws until there are no any claws; (Claw is a
vertex of degree 1).
2. Next delete the vertex with largest degree and mark its neighbors to
keep them from being selected next time unless next time all vertexes
that have the largest degree are its neighbors. Later if a vertex's
edge is deleted, the vertex's neighbor mark should be deleted too if
any.
3. Repeat 1. and 2. until all input cells are deleted.

At some stages in all this deleting, you presumably tag some vertices as
being members of the resulting cover. Could you restate the algorithm
making it clear which they are?

Thanks,

Patricia

Hi Patricia,
Yes.

1. First delete all claws until there are no any claws; (Claw is a
vertex of degree 1).
output claws's only neighbor vertexes as members of the minimum vertex
cover;

1--2--3--4--5--6--7
|
8
|
9
Vertex 1 is a claw and deleted, output vertex 2 because it is vertex
1's neighbor, and vertex 2 is deleted. When one edge of vertex 2 is
deleted, vertex 3 become a claw and is deleted, then output vertex 4,
vertex 3's neighbor; vertex 8 become a claw and is deleted, output
vertex 9; vertex 5 is a claw, output vertex 6.
So the minimum vertex cover is:
2, 4, 6, 9. |V'| = 4.

2. Next delete the vertex with the largest degree, output the vertex as
a member of the minimum vertex cover and mark its neighbors to keep
them from being selected next time unless next time all vertexes that
have the largest degree are its neighbors. Later if a vertex's edge is
deleted, the vertex's neighbor mark should be deleted too if any.

(5, 1, 2, 3, 4, 5, 6)
(5, 2, 1, 3, 5, 6, 7)
(5, 3, 1, 2, 4, 5, 6)

Select any one of above 3 vertexes, delete it, it become (when the
first is selected):
(4, 2, 3, 5, 6, 7)+
(4, 3, 2, 4, 5, 6)+

'+' means it is a neighbor of the deleted vertex with the largest
degree. On next selectiono, If one of vertexes of the largest degree
has a neighbor mark, it must not selected unless all vertexes of the
largest degree are the neighbors of deleted vertexes of the largest
degree.

Now any of the two above vertexes can be deleted and output because
both are the neighbors.

3. Repeat 1. and 2. until all input cells are deleted.

If you can list a graph that fails my algorithm, you beat me.

Thank you.

Weng

 

[Patricia Shanahan]

Weng Tianxiang wrote:
....

If you can list a graph that fails my algorithm, you beat me.

I wish my algorithm design professor had taken that attitude. It would
have made homeworks much easier. Instead, he insisted on proofs that my
algorithms gave correct answers, as well as meeting their claimed time
complexity.

Patricia

 

[Weng Tianxiang]

David Ashley wrote:

Weng Tianxiang wrote:
Arthur J. O'Dwyer wrote:

On Sun, 24 Sep 2006, Weng Tianxiang wrote:

eKo1 wrote:

Let V' be a subset of V. V' is a vertex cover if it satisfies the
following test:

E' = Ř
for each v in V'
for each edge e in E
if v is incident to e then
add e to E'
end if
end for
end for
if |E| = |E'| then
return true // V' is a vertex cover
end if
return false

Would this be correct?

Hi eKo1,
The algorithm you mentioned for a vertex cover is right.

Yes, that's right. (And it suggests a trivial brute-force algorithm
to find a minimum vertex cover:

M = V
for each V' in V
if (V' is a vertex cover of G) then
if |V'| < |M| then
M = V
end if
end if
end for
return M

Now M is a minimum vertex cover.)



Here is my full new algorithm that can get minimum vertex cover:

To make discussion simpler, we assume that every vertex has a positive
integer, starting with 1 to n and input cells have the following
structure:
(edge count, edge starting vertex, edge ending vertexes).

For example vertex 1 has edges: (1, 2), (1, 3), (1, 4), then its input
cell has the following representation: (3, 1, 2, 3, 4). Cell length
vary dependent on the cell's degree, or the number of edges which is
incident on the cell.

Whoof, that's a clumsy representation! Next time, consider using a
more natural representation, such as "Each vertex has a list of
neighbors. For example, vertex 1 has neighbors {2,3,4}."


Here is new full algorithm to get minimum vertex cover:
1. Count = 0.
2. If input cell is empty, algorithm ends, otherwise
Sort the input cell serials based on count in increasing order.

What are the "input cell serials"? I'm guessing you mean to sort the
cells in increasing order by degree, i.e., the cells with lower degree
come first in the list. Okay, but let me know if I'm wrong.


3. for all vertexes with edge count = 1, do following:
a. Set original starting vertex;

What?


b. Count++;
c. Print out its edge ending vertex #; (only one)
d. Delete its input cell;
e. In the edge ending vertex cell, do the followings:
a. delete the original starting vertex in edge ending
vertexes area;

What?


b. edge count is decreased by 1;
c. if edge count = 1, set current ending vertex as new
original starting vertex and go to b.
d. if edge count = 0, delete the cell;
4. If input cell is empty, algorithm ends, otherwise
sort the input cell serials based on count in decreasing order.

What? What is the "input cell"? What is an "empty" cell --- is ()
the only empty cell, or could (0, 5) be considered empty too?


5. If there is only one cell that has the largest degree, select the
cell
and go to 6. If there are more than one cell that have the equal
largest degree, select the cell that has not been the end vertex
of the last selected cell with the largest degree, or select any of
them
if all of them have have been the end vertexes of last selected cell

What? What?

(snip much more gibberish)


Manually I tried more than 20 graphs and get the right answers for
every graph.

Good for you.


Do you have any smart tips?

Yes. Stop trying to find a polynomial algorithm for minimum vertex
cover until you've read at least one existing (non-polynomial) algorithm
and understand how it works. Also, try to write in plain English, or,
failing that, some common programming language.


If you can find a graph that fails the algorithm, please let me know.

Yes, I can. So now you know.

-Arthur


Hi Arthur,
I cannot read the page. Can you please post the page on the group or
send me an email?

My email address is wtxwtx at gmail dot com (without space).

I don't know if my algorithm is the same as the one you mentioned.

Actually I checked my algorithm with more than 20 hand-drawn graphs and
all results generated are the minimum vertex cover, no exception!!!

Otherwise I couldn't publish my 2nd version so quickly. If another
error is found, I can also quickly change my design to correct the
error without destroying the full design.

The key point is:
1. First delete all claws until there are no any claws; (Claw is a
vertex of degree 1).
2. Next delete the vertex with largest degree and mark its neighbors to
keep them from being selected next time unless next time all vertexes
that have the largest degree are its neighbors. Later if a vertex's
edge is deleted, the vertex's neighbor mark should be deleted too if
any.
3. Repeat 1. and 2. until all input cells are deleted.

I will start writing a program in C and write some programs to generate
random graphs to check if there are any violations:
1. Randomly generate a graph;
2. Generate its minimum vertex cover, m= |V'| by my program.
3. Check C(n, m-1) choices to see if any of them meets the minimum
vertex cover.

I have "An introduction to Algorithm" written by Thomas H. Cormen etc.
It has a problem 35.1-3:
Professor Nixon proposes the following heuristic to solve the
vertex-cover problem. Repeatedly select a vertex of highest degree, and
remove all of its incident edges. Give an example to show that the
professor's heuristic doesn't not have an approximation ratio of 2.
(Hint: Try a bipartite graph with vertexes of uniform degree on the
left and vertexes of varying degree on the right. )

That is exactly what I suggested in my first version. But with the
problem exposed, I changed my strategy to delete any claws first, then
do the selection.

If you can post a graph that fails my algorithm, it will be great!!!

Thank you.

Weng


Weng,

Did you mean to post this to comp.arch.fpga?

It's an interesting problem and all, but...?

-Dave

--
David Ashley http://www.xdr.com/dash
Embedded linux, device drivers, system architecture

Hi David,
Yes, I post it for comp.arch.fpga too.

1. comp.arch.fpga has a group of engineers who have many experiences
with logic design, are talent and should pay attention to the deepest
problem in computing complexity.

2. I dream someday we can design a NP machine that runs all NP problems
in polynomial time using a FPGA chip. Personally I think Turing machine
should be dying with powerful FPGA chips growing and the fact should be
reflected in computing theory.

3. The above posting is my a small step in a direction I am thinking is
right: first to design an algorithm that is not using brute force, but
some smart ideas of the special problem.

4. I select the minimum vertex cover because its memory will never be
expanded and it depends on a smarter selection to finish the cover.

5. At the current moment, I am devoting to design an algorithm that
works with minimum vertex cover.

6. If the algorithm works, all of us have a chance to finish a NP
machine with performance in polynomial time.

Thank you.

jWeng

 

[Weng Tianxiang]

Patricia Shanahan wrote:

Weng Tianxiang wrote:
...
If you can list a graph that fails my algorithm, you beat me.

I wish my algorithm design professor had taken that attitude. It would
have made homeworks much easier. Instead, he insisted on proofs that my
algorithms gave correct answers, as well as meeting their claimed time
complexity.

Patricia

Hi Patricia,
1. Yes, I have to prove the following theorem:
If a graph has no claws (vertex of degree 1), the vertex with the
largest degree can be a member of the minimum vertex cover.

2. I am doing the following things:
a. Develop the algorithm in C;
b. Develop an algorithm in C that can generate random graphs;
c. Feed the graphs to my algorithm and generate |V'| data;
d. Enumerate all cover options of C(N, |V'|-1) to confirm that there is
no graph cover with less degrees.

It takes time, but if all people help me, it will be great!

Thank you.

Weng