[Lemon-user] remark on graphwriter

[Alpár Jüttner]

On Fri, 2011-01-07 at 19:42 +0100, Tapolcai János wrote:
> Hi,
> 
> you were right, the problem was something very different:
> 
> I had an undirected graph and saved with DigraphWriter, next I loaded
>  as GraphReader, and every edge became duplicated.

I still can't understand why the cost values are different for the
opposite arcs belonging to the same edge. When you write an EdgeMap with
DigraphWriter, it should write the same value to both opposite arcs.
Could you please check it again if DigraphWriter works correctly?

> To avoided such a mistake, it might be a good idea to implement: 
> (1) the GraphReader writing a warning message, when it reads the label "@arcs",

      * First of all, I think it always a bad idea from a library to
        write any kind warning. Remember, the "user" of the library is
        the developer and not the end user of the software. Thus a
        warning like this should be sent to the developer, not to the
        user. An alternative could be to use the LEMON_DEBUG or
        LEMON_ASSERT macro to check it. However,
      * @arcs and @edged are fully equivalent by design, because test
        graphs and the output of the well known graph generators are
        very often used to test both undirected and directed graph
        algorithms.
      * Therefore it isn't clear who should emit a warning. I think the
        mistake was done when you wrote the undirected graph with
        DigraphWriter and not when you read it. What follows is that
        DigraphWriter should warn you when you use it with an undirected
        graph. BUT, undirected graphs are required to be fully
        compatible with directed graphs, thus this exception would also
        be quite odd.

So I currently can't see any better than warn people to take care of
this issue.

> (2) a new Reading Rule for GraphReader named simpleGraph(), which
>  filters the duplicated edges when parsing the lgf file.

Which 'cost' value should be kept when removing the parallel edges?

Once again, the mistake was made at writing, not at reading.

Regards,
Alpar

> 
> Thanks
> János
> 
>  
> 
> > -----Original Message-----
> > From: Alpár Jüttner [mailto:alpar.juttner at gmail.com] On Behalf Of Alpár
> > Jüttner
> > Sent: Thursday, January 06, 2011 12:24 PM
> > To: Tapolcai János
> > Cc: lemon-user at lemon.cs.elte.hu
> > Subject: Re: [Lemon-user] remark on graphwriter
> > 
> > Hi,
> > 
> > The output below is indeed strange.
> > Could you please send the exact code producing this output?
> > 
> > On Thu, 2011-01-06 at 08:57 +0100, Tapolcai János wrote:
> > > Hi All,
> > >
> > > I have a remark related to the lemon lgf undirected graph writer. When I
> > print a graph, each Edge is printed in two lines (in both direction), and
> > in the reverse direction some strange (default?) values are printed for the
> > Edgemaps.
> > >
> > > The result looks very confusing (the default value for the map was 0),
> > e.g.:
> > >
> > > @edges
> > > 		label	cost
> > > 0	4	0	1
> > > 4	0	1	0
> > > 0	2	2	1
> > > 2	0	3	10
> > > 0	5	4	0
> > > 5	0	5	10
> > > 1	3	6	10
> > > 3	1	7	0
> > > 1	4	8	1
> > > 4	1	9	0
> > > 1	6	10	10
> > > 6	1	11	0
> > > 2	5	12	0
> > > 5	2	13	10
> > > 3	4	14	10
> > > 4	3	15	0
> > > 4	6	16	0
> > > 6	4	17	1
> > >
> > > I know lgf was not designed for human reading, however to avoid any
> > confusion I suggest  printing the same value of Edgemaps in both directions,
> > or printing each edge in a single line.
> > >
> > > Thanks
> > > János
> > > _______________________________________________
> > > Lemon-user mailing list
> > > Lemon-user at lemon.cs.elte.hu
> > > http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
> > 
> 
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user