Re: [Boost-users] dijkstra-example.cpp (BOOST GRAPH)

Subject: Re: [Boost-users] dijkstra-example.cpp (BOOST GRAPH)
From: Kunzman, Douglas (Doug) (DKunzman_at_[hidden])
Date: 2012-01-31 13:30:17

I have a non-directed graph based upon the dijkstra-example.cpp and have discovered a change that is required for my graph.  Any insight would be helpful.  When outputting the graph as a .dot file I need to change the code as follows:

if (v== p[u])
        dot_file << ", color=\"black\"";
else if (p[v] == u) 
        dot_file << ", color=\"black\"";

rather than,

  if (p[v] == u)
      dot_file << ", color=\"black\"";

My list of parents are std::vectors p where u and v are vertices.  
I was wondering if this comment would be useful to other people.

Doug

-----Original Message-----
From: boost-users-bounces_at_[hidden] [mailto:boost-users-bounces_at_[hidden]] On Behalf Of Jeremiah Willcock
Sent: Friday, January 27, 2012 8:42 PM
To: boost-users_at_[hidden]
Subject: Re: [Boost-users] dijkstra-example.cpp

On Fri, 27 Jan 2012, Kunzman, Douglas (Doug) wrote:

> The tree that result from calling dijkstra's algorithm does not result 
> in a each vertice have at least one black edge reaching it.  I would 
> assume something is wrong?  Can someone offer some suggestions?

Each vertex (other than the start node itself) that is reachable from the start node should have exactly one black edge to it, at least in the directed case.  Do you have graphs that produce different behavior than that?

-- Jeremiah Willcock


>
> -----Original Message-----
> From: boost-users-bounces_at_[hidden] 
> [mailto:boost-users-bounces_at_[hidden]] On Behalf Of Jeremiah 
> Willcock
> Sent: Friday, January 27, 2012 4:18 PM
> To: boost-users_at_[hidden]
> Subject: Re: [Boost-users] dijkstra-example.cpp
>
> On Fri, 27 Jan 2012, fergie wrote:
>
>> I’ve been reviewing the dijkstra-example.cpp that is provided as part 
>> of boost Graph.  I think I understand most of it and have been able 
>> to demonstrate the application working to my boss.  I have one 
>> question about the code.  When output the .dot file near the end of 
>> the program the results are shaded either grey or black.  What is the 
>> significance of the black and grey lines?
>
> Black lines are edges in the single-source shortest path tree, while gray lines are edges that are not in the tree.  Look at http://www.cs.cmu.edu/~avrim/451/lectures/lect1008.pdf for exactly what the tree represents.
>
>> I’ve looked through the documentation and am also confused about the 
>> source and the target since we have an iterator going through the 
>> entire graph.  What defines a source and target vertex?
>
> The graph is directed, so each edge goes from a defined source to a defined target.  The arrows in the output file show the directions of the edges.
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users

>