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? 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? Thanks, D -- View this message in context: http://boost.2283326.n4.nabble.com/dijkstra-example-cpp-tp4334386p4334386.ht... Sent from the Boost - Users mailing list archive at Nabble.com.
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
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? Doug -----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: Friday, January 27, 2012 4:18 PM To: boost-users@lists.boost.org 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
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@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: Friday, January 27, 2012 4:18 PM To: boost-users@lists.boost.org 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: Friday, January 27, 2012 8:42 PM To: boost-users@lists.boost.org 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@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: Friday, January 27, 2012 4:18 PM To: boost-users@lists.boost.org 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Tue, 31 Jan 2012, Kunzman, Douglas (Doug) wrote:
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.
Yes, it is useful; thanks for sending it. I might update the example, at least with your part commented out with a note. -- Jeremiah Willcock
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: Friday, January 27, 2012 8:42 PM To: boost-users@lists.boost.org 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@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: Friday, January 27, 2012 4:18 PM To: boost-users@lists.boost.org 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (3)
-
fergie -
Jeremiah Willcock -
Kunzman, Douglas (Doug)