Re: [Boost-users] 1.33.1 read_graphviz possible parser issue

From: Brian Stadler (bdotstadler_at_[hidden])
Date: 2007-09-28 11:15:43

Hello again,

I apologize for the late reply.  I've been busy.

To restate the question, I orginally claimed that a file being interpreted
with read_graphviz() was being interpreted incorrectly.  The file in
question is below.

Source graphviz file:

strict graph  {
    0 -- 3;
    0 -- 4;
    1 -- 3;
    1 -- 4;
    2 -- 3;
    2 -- 4;
    3 -- 4;
}

I then claimed there was a problem and after looking at the output from
write_graphviz() I noticed that what was read and what was written were
different.  The output from write_graphviz() after reading it with
read_graphviz() is below.  Notice that the labeling is no longer the same
but the actual structure of the graph is retained, e.g. it still looks like
a triangle or something.

graph G {
0;
1;
2;
3;
4;
0--1 ;
0--2 ;
3--1 ;
3--2 ;
4--1 ;
4--2 ;
1--2 ;
}

So, after this, I beleived it was a problem with boost and I still beleive
that.  So, I took this same file and ran it through graphviz's dot with the
following command and received the output below.  (command was dot -o
<source file>   output went to stdout)

strict graph {
        node [label="\N"];
        graph [bb="0,0,201,180"];
        0 [pos="27,162", width="0.75", height="0.50"];
        3 [pos="82,90", width="0.75", height="0.50"];
        4 [pos="109,18", width="0.75", height="0.50"];
        1 [pos="100,162", width="0.75", height="0.50"];
        2 [pos="174,162", width="0.75", height="0.50"];
        0 -- 3 [pos="39,146 48,134 61,118 70,106"];
        0 -- 4 [pos="28,144 29,125 33,94 46,72 56,54 74,40 89,30"];
        1 -- 3 [pos="96,144 93,133 89,119 86,108"];
        1 -- 4 [pos="107,144 111,134 115,120 118,108 122,83 117,54 113,36"];
        2 -- 3 [pos="156,148 140,135 116,116 100,104"];
        2 -- 4 [pos="166,145 154,117 129,63 117,35"];
        3 -- 4 [pos="89,72 93,61 98,47 103,36"];
}

Notice how graphviz preprocesses the file and creates the nodes with the
correct labels first.  Then it goes back and creates the edges between the
nodes.  Boost doesn't do this.  With the original file (seen below)
read_graphviz() reads and creates nodes as it goes in a linear fashion.  For
example, with the first line it reads 0 -- 3 and creates node 0, as it
should, and goes on to read 3.  But, the problem starts here.  Instead of
read_graphviz() preprocessing the entire file it simply creates as it goes.
So, it created a node internally, starting at 0.  Then when it came time to
create another node it just counted up to 1, created it and gave it the
label 3.  This is where I beleive read_graphviz() is broken.  This is not
the way graphviz's programs interpret the file.  I believe read_graphviz()
should work as it does with the creators language.  I find it silly to have
to include code with appropiate labeling when reading such simple files.
Nothing extra should be needing to interpret something like this in
read_graphviz().

strict graph  {
    0 -- 3;
    0 -- 4;
    1 -- 3;
    1 -- 4;
    2 -- 3;
    2 -- 4;
    3 -- 4;
}

I hope this clears up any previous misunderstandings.

Sincerely,

--Brian

On 9/20/07, Ronald Garcia <garcia_at_[hidden]> wrote:
>
>
> On Sep 19, 2007, at 10:29 PM, Brian Stadler wrote:
>
> > Hello again,
> >
> > I'm still not convinced boost is interpreting these file
> > correctly.  I understand and agree that node id's are strings.  I
> > do not understand why you think these graph files are a special case.
> It is a special case that your node id's happen to be integers.  The
> node name information is stored in the dynamic_properties (and in the
> internal vertex_name property of your graph).  The write_graphviz
> operation requires you to explicitly pass along a mapping from nodes
> to ids if you want to control the ids of the vertices.
>
> >
> > Answer me the following.  Why is that when I process the following
> > using the dot binary that i get back a picture with the correct
> > interpretation, but when I read the same file using the boost
> > library its interpretation is skewed?
> >
>
> What precisely do you mean when you say that its interpretation is
> "skewed"?
>
> Cheers,
> ron
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>