[vtk-developers] vtkDIMACS reader/writer bug

Wed Jun 22 16:21:38 EDT 2011

I think I wrote the reader a few years back ... I don't recall developing the writer though.

I added some expanded documentation earlier today to the reader which should go in when I commit.

DIMACS has definitely been a format that's varied a bit over time.  In a nutshell, the reader looks for the problem specification line (the p <problem> V E line).  If it finds one that it has a specific reader built for it then it'll load the problem-specific information.  Otherwise it just loads the graph as a generic graph.

Currently, I think I only put in specific readers for the max-flow problem (p max n e) or the coloring problem (p edge n e), otherwise specifics are ignored.  It should also be tolerant of edges being labeled with either an 'a' or an 'e'.  I think I opted to go with floating point values since they'll also work for integers.

Somehow I don't think the DIMACS reader/writers have been used much since the filters have been in for a while now and this error hadn't been caught yet ;-)  Things should be a bit better when I push out my fixes later on today or tomorrow.

-William

From: "Eric E. Monson" <emonson at cs.duke.edu<mailto:emonson at cs.duke.edu>>
Date: Wed, 22 Jun 2011 15:51:15 -0400
To: William C McLendon <wcmclen at sandia.gov<mailto:wcmclen at sandia.gov>>
Cc: "vtk-developers at vtk.org<mailto:vtk-developers at vtk.org> Developers" <vtk-developers at vtk.org<mailto:vtk-developers at vtk.org>>
Subject: Re: [vtk-developers] vtkDIMACS reader/writer bug

It's a strange format, though, that's changed over time depending on which "challenge" it's being used in. I see that this 9th challenge is the one linked from the doxygen page, but the reader also seems to accept some form of the 2nd challenge format with "n" node descriptor lines and "e" instead of "a" for edges. Also, in all the formats I've seen today they seem to describe any "weight" values as integers, but the VTK writer/reader seems to use/accept floating point values...

So, as long as you're making changes, it might be good to update the documentation to not just specify the 1...n IDs, but to clarify what formats are acceptable. Also, if it really needs 1...n IDs with no gaps, is there any guarantee that an arbitrary graph someone constructs will have all sequential IDs?

Anyway, I'm glad the immediate problem seems to be solved.

Talk to you later,
-Eric

On Jun 22, 2011, at 3:15 PM, Mclendon, William C III wrote:

Ah!  I didn't look closely at the DIMACS file specs at http://www.dis.uniroma1.it/~challenge9/format.shtml#graph:

[http://www.dis.uniroma1.it/%7Echallenge9/images/bullet-orange.gif] A graph contains n nodes and m arcs
[http://www.dis.uniroma1.it/%7Echallenge9/images/bullet-orange.gif] Nodes are identified by integers 1...n
[http://www.dis.uniroma1.it/%7Echallenge9/images/bullet-orange.gif] Graphs can be interpreted as directed or undirected, depending on the problem being studied
[http://www.dis.uniroma1.it/%7Echallenge9/images/bullet-orange.gif] Graphs can have parallel arcs and self-loops
[http://www.dis.uniroma1.it/%7Echallenge9/images/bullet-orange.gif] Arc weights are signed integers

It looks like the writer is happily writing out files with vertices from 0..n-1 rather than 1..n.

I'll toss in a couple checks into the code this afternoon to make the writer generate vertices numbered from 1..n and the reader to add a check to generate a useful warning message if it detects a vertex 0...

Thanks for providing a few extra pairs of eyeballs... :D

-William

From: "Eric E. Monson" <emonson at cs.duke.edu<mailto:emonson at cs.duke.edu>>
Date: Wed, 22 Jun 2011 14:52:34 -0400
To: William C McLendon <wcmclen at sandia.gov<mailto:wcmclen at sandia.gov>>
Cc: "vtk-developers at vtk.org<mailto:vtk-developers at vtk.org> Developers" <vtk-developers at vtk.org<mailto:vtk-developers at vtk.org>>
Subject: Re: [vtk-developers] vtkDIMACS reader/writer bug

Yup, if I add one to the source and target IDs in the writer code, I don't seem to get the crashes any more. Maybe there are other things wrong, too, but that seems to fix it for me.

-Eric

On Jun 22, 2011, at 2:46 PM, Eric E. Monson wrote:

You know, it looks like the graph reader doesn't like node IDs of 0, it likes them to start with 1. If I write out a simpler graph with only 10 nodes, then manually increment each node ID in the file by 1 so they start with 1 instead of 0, it works.

-Eric

On Jun 22, 2011, at 1:47 PM, Mclendon, William C III wrote:

I'm trying to run a script that just generates a random graph and saves it using the DIMACS writer then reads it back using the DIMACS reader.  Unfortunately, when I try to render the graph I get a segfault.

It seems odd since the graphs seem to load properly.  The attached script seems to be crashing for me on both OS-X and under Linux.

-William
<dimacs.py>_______________________________________________
Powered by www.kitware.com<http://www.kitware.com/>

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Follow this link to subscribe/unsubscribe:
http://www.vtk.org/mailman/listinfo/vtk-developers

_______________________________________________
Powered by www.kitware.com<http://www.kitware.com/>

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Follow this link to subscribe/unsubscribe:
http://www.vtk.org/mailman/listinfo/vtk-developers

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20110622/c9df68d5/attachment.html>