[prev in list] [next in list] [prev in thread] [next in thread] 

List:       boost-users
Subject:    Re: [Boost-users] Levelization of DAG in Boost graph -- trying again
From:       Dominique Devienne <ddevienne () gmail ! com>
Date:       2015-10-30 21:54:00
Message-ID: CAFCRh-9igNfww9gWTuEpFnugy_sN4s2bBHH0GLgePFHahk--dQ () mail ! gmail ! com
[Download RAW message or body]

[Attachment #2 (multipart/alternative)]


On Fri, Oct 30, 2015 at 8:46 PM, bhattach <bhattach@yahoo.com> wrote:

> It's based on topological sorting (available with BGL -- don't have to
> write
> your own, unlike the solution shown at the URL above)


that's this part

std::vector<Vrtx> sorted_vertices;
boost::topological_sort(dag, std::back_inserter(sorted_vertices));

followed by a one-pass
> traversal of the vertices in the topologically sorted order to compute
> level
> number/longest path distance using your own code.
>

and that's this part

        std::vector<int> time(vrtx_count, 1);
        for (Vrtx u : sorted_vertices) {
            if (boost::out_degree(u, dag) > 0) {
                int maxdist = 0;
                for (Edge e : range_of(boost::out_edges(u, dag))) {
                    Vrtx v = boost::target(e, dag);
                    maxdist = std::max(time[v], maxdist);
                }
                time[u] = maxdist + 1;
            }
        }

So I'm not sure what you mean by "don't have to write your own". --DD

[Attachment #5 (text/html)]

<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Oct 30, 2015 \
at 8:46 PM, bhattach <span dir="ltr">&lt;<a href="mailto:bhattach@yahoo.com" \
target="_blank">bhattach@yahoo.com</a>&gt;</span> wrote:<br><blockquote \
class="gmail_quote" style="margin:0px 0px 0px \
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">It&#39;s \
based on topological sorting (available with BGL -- don&#39;t have to write<br> your \
own, unlike the solution shown at the URL \
above)</blockquote><div><br></div><div>that&#39;s this \
part</div><div><br></div><div><span style="font-size:12.8px">std::vector&lt;Vrtx&gt; \
sorted_vertices;</span></div><div \
style="font-size:12.8px">boost::topological_sort(dag, \
std::back_inserter(sorted_vertices));</div><div \
style="font-size:12.8px"><br></div><blockquote class="gmail_quote" style="margin:0px \
0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">followed \
by a one-pass<br> traversal of the vertices in the topologically sorted order to \
compute level<br> number/longest path distance using your own \
code.<br></blockquote><div><br></div><div>and that&#39;s this \
part</div><div><br></div><div style="font-size:12.8px">            \
std::vector&lt;int&gt; time(vrtx_count, 1);</div><div style="font-size:12.8px">       \
for (Vrtx u : sorted_vertices) {</div><div style="font-size:12.8px">                  \
if (boost::out_degree(u, dag) &gt; 0) {</div><div style="font-size:12.8px">           \
int maxdist = 0;</div><div style="font-size:12.8px">                        for (Edge \
e : range_of(boost::out_edges(u, dag))) {</div><div style="font-size:12.8px">         \
Vrtx v = boost::target(e, dag);</div><div style="font-size:12.8px">                   \
maxdist = std::max(time[v], maxdist);</div><div style="font-size:12.8px">             \
}</div><div style="font-size:12.8px">                        time[u] = maxdist + \
1;</div><div style="font-size:12.8px">                  }<br></div><div><span \
style="font-size:12.8px">            }</span></div><div>  </div><div>So I&#39;m not \
sure what you mean by &quot;don&#39;t have to write your own&quot;. \
--DD</div></div></div></div>



_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[prev in list] [next in list] [prev in thread] [next in thread]