Topic: topological sort?
Author: Daniel Gutson <danielgutson@gmail.com>
Date: Thu, 2 Aug 2018 15:48:57 -0300
Raw View
--0000000000002c8b9c05727844f2
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
I couldn't find any paper proposing a topological sort.
Is there any reason nobody proposed it yet?
Would there be interest?
Thanks,
Daniel.
--=20
Who=E2=80=99s got the sweetest disposition?
One guess, that=E2=80=99s who?
Who=E2=80=99d never, ever start an argument?
Who never shows a bit of temperament?
Who's never wrong but always right?
Who'd never dream of starting a fight?
Who get stuck with all the bad luck?
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/CAFdMc-2q3WhPMVXppbGQtRT9pfAEn8-S-z%3DFB3PVHjJ9q=
-8Q%2Bg%40mail.gmail.com.
--0000000000002c8b9c05727844f2
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">I couldn't find any paper proposing a topological sort=
..<div>Is there any reason nobody proposed it yet?</div><div>Would there be =
interest?</div><div><br></div><div>Thanks,</div><div><br></div><div>=C2=A0 =
=C2=A0 Daniel.<br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr" clas=
s=3D"gmail_signature" data-smartmail=3D"gmail_signature">Who=E2=80=99s got =
the sweetest disposition?<br>One guess, that=E2=80=99s who?<br>Who=E2=80=99=
d never, ever start an argument?<br>Who never shows a bit of temperament?<b=
r>Who's never wrong but always right?<br>Who'd never dream of start=
ing a fight?<br>Who get stuck with all the bad luck? </div></div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CAFdMc-2q3WhPMVXppbGQtRT9pfAEn8-S-z%3=
DFB3PVHjJ9q-8Q%2Bg%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter"=
>https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAFdMc-2q3WhP=
MVXppbGQtRT9pfAEn8-S-z%3DFB3PVHjJ9q-8Q%2Bg%40mail.gmail.com</a>.<br />
--0000000000002c8b9c05727844f2--
.
Author: florian.csdt@gmail.com
Date: Thu, 2 Aug 2018 12:17:19 -0700 (PDT)
Raw View
------=_Part_405_1084027636.1533237439454
Content-Type: multipart/alternative;
boundary="----=_Part_406_844575729.1533237439454"
------=_Part_406_844575729.1533237439454
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Le jeudi 2 ao=C3=BBt 2018 20:49:11 UTC+2, Daniel Gutson a =C3=A9crit :
>
> I couldn't find any paper proposing a topological sort.
> Is there any reason nobody proposed it yet?
> Would there be interest?
>
> =20
My feeling is: to standardize a topological sort, you would need to=20
standardize a graph class. Standardizing such a class would require big=20
efforts, especially because there is no a best way to represent a graph.
Remember that dense linear algebra has not been standardized yet, despite a=
=20
strong interest and simpler structures.
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2a9c3%40isocpp.or=
g.
------=_Part_406_844575729.1533237439454
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Le jeudi 2 ao=C3=BBt 2018 20:49:11 UTC+2, Daniel Gutson a =
=C3=A9crit=C2=A0:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"l=
tr">I couldn't find any paper proposing a topological sort.<div>Is ther=
e any reason nobody proposed it yet?</div><div>Would there be interest?</di=
v><br></div></blockquote><div>=C2=A0</div><div>My feeling is: to standardiz=
e a topological sort, you would need to standardize a graph class. Standard=
izing such a class would require big efforts, especially because there is n=
o a best way to represent a graph.</div><div>Remember that dense linear alg=
ebra has not been standardized yet, despite a strong interest and simpler s=
tructures.<br></div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2a9c3%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2a9c3=
%40isocpp.org</a>.<br />
------=_Part_406_844575729.1533237439454--
------=_Part_405_1084027636.1533237439454--
.
Author: Daniel Gutson <danielgutson@gmail.com>
Date: Thu, 2 Aug 2018 16:20:12 -0300
Raw View
--000000000000ec9331057278b36a
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
On Thu, Aug 2, 2018 at 4:17 PM <florian.csdt@gmail.com> wrote:
> Le jeudi 2 ao=C3=BBt 2018 20:49:11 UTC+2, Daniel Gutson a =C3=A9crit :
>>
>> I couldn't find any paper proposing a topological sort.
>> Is there any reason nobody proposed it yet?
>> Would there be interest?
>>
>>
> My feeling is: to standardize a topological sort, you would need to
> standardize a graph class. Standardizing such a class would require big
> efforts, especially because there is no a best way to represent a graph.
>
I expected this question, and I agree at some degree. However, I strongly
think that a graph would be implementation. I think that a topological
sorting function could just receive a container of relationships (edges,
potentially std::pair), a begin/end, and a back inserter iterator.
Whether you implement it with a graph, and it happens that you also want to
expose it as a stand alone utility, is a different talk.
> Remember that dense linear algebra has not been standardized yet, despite
> a strong interest and simpler structures.
>
> --
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> To view this discussion on the web visit
> https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523=
c-4ec7-aa49-599becf2a9c3%40isocpp.org
> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-52=
3c-4ec7-aa49-599becf2a9c3%40isocpp.org?utm_medium=3Demail&utm_source=3Dfoot=
er>
> .
>
--=20
Who=E2=80=99s got the sweetest disposition?
One guess, that=E2=80=99s who?
Who=E2=80=99d never, ever start an argument?
Who never shows a bit of temperament?
Who's never wrong but always right?
Who'd never dream of starting a fight?
Who get stuck with all the bad luck?
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/CAFdMc-1JgZhmh0GC744hjkkkHiQ1J2TYf8tMX9absHa5ter=
JJA%40mail.gmail.com.
--000000000000ec9331057278b36a
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Thu=
, Aug 2, 2018 at 4:17 PM <<a href=3D"mailto:florian.csdt@gmail.com">flor=
ian.csdt@gmail.com</a>> wrote:<br></div><blockquote class=3D"gmail_quote=
" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><=
div dir=3D"ltr">Le jeudi 2 ao=C3=BBt 2018 20:49:11 UTC+2, Daniel Gutson a =
=C3=A9crit=C2=A0:<blockquote class=3D"gmail_quote" style=3D"margin:0;margin=
-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">I=
couldn't find any paper proposing a topological sort.<div>Is there any=
reason nobody proposed it yet?</div><div>Would there be interest?</div><br=
></div></blockquote><div>=C2=A0</div><div>My feeling is: to standardize a t=
opological sort, you would need to standardize a graph class. Standardizing=
such a class would require big efforts, especially because there is no a b=
est way to represent a graph.</div></div></blockquote><div><br></div><div>I=
expected this question, and I agree at some degree. However, I strongly th=
ink that a graph would be implementation. I think that a topological sortin=
g function could just receive a container of relationships (edges, potentia=
lly std::pair), a begin/end, and a back inserter iterator.</div><div>Whethe=
r you implement it with a graph, and it happens that you also want to expos=
e it as a stand alone utility, is a different talk.</div><div>=C2=A0</div><=
blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px=
#ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>Remember that dense lin=
ear algebra has not been standardized yet, despite a strong interest and si=
mpler structures.<br></div></div>
<p></p>
-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_=
blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2a9c3%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter" target=3D"_blank">=
https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-=
4ec7-aa49-599becf2a9c3%40isocpp.org</a>.<br>
</blockquote></div><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr"=
class=3D"gmail_signature" data-smartmail=3D"gmail_signature">Who=E2=80=99s=
got the sweetest disposition?<br>One guess, that=E2=80=99s who?<br>Who=E2=
=80=99d never, ever start an argument?<br>Who never shows a bit of temperam=
ent?<br>Who's never wrong but always right?<br>Who'd never dream of=
starting a fight?<br>Who get stuck with all the bad luck? </div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CAFdMc-1JgZhmh0GC744hjkkkHiQ1J2TYf8tM=
X9absHa5terJJA%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">htt=
ps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAFdMc-1JgZhmh0GC=
744hjkkkHiQ1J2TYf8tMX9absHa5terJJA%40mail.gmail.com</a>.<br />
--000000000000ec9331057278b36a--
.
Author: Daniel Gutson <danielgutson@gmail.com>
Date: Thu, 2 Aug 2018 16:24:37 -0300
Raw View
--000000000000b52112057278c398
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
One possible overload, just illustrative:
template <class Element, class OutputIt, class Compare>
void topological_sort(std::initialization_list<std::pair<Element>> edges,
OutputIt d_first, Compare comp);
On Thu, Aug 2, 2018 at 4:20 PM Daniel Gutson <danielgutson@gmail.com> wrote=
:
>
>
> On Thu, Aug 2, 2018 at 4:17 PM <florian.csdt@gmail.com> wrote:
>
>> Le jeudi 2 ao=C3=BBt 2018 20:49:11 UTC+2, Daniel Gutson a =C3=A9crit :
>>>
>>> I couldn't find any paper proposing a topological sort.
>>> Is there any reason nobody proposed it yet?
>>> Would there be interest?
>>>
>>>
>> My feeling is: to standardize a topological sort, you would need to
>> standardize a graph class. Standardizing such a class would require big
>> efforts, especially because there is no a best way to represent a graph.
>>
>
> I expected this question, and I agree at some degree. However, I strongly
> think that a graph would be implementation. I think that a topological
> sorting function could just receive a container of relationships (edges,
> potentially std::pair), a begin/end, and a back inserter iterator.
> Whether you implement it with a graph, and it happens that you also want
> to expose it as a stand alone utility, is a different talk.
>
>
>> Remember that dense linear algebra has not been standardized yet, despit=
e
>> a strong interest and simpler structures.
>>
>> --
>> You received this message because you are subscribed to the Google Group=
s
>> "ISO C++ Standard - Future Proposals" group.
>> To unsubscribe from this group and stop receiving emails from it, send a=
n
>> email to std-proposals+unsubscribe@isocpp.org.
>> To post to this group, send email to std-proposals@isocpp.org.
>> To view this discussion on the web visit
>> https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-52=
3c-4ec7-aa49-599becf2a9c3%40isocpp.org
>> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-5=
23c-4ec7-aa49-599becf2a9c3%40isocpp.org?utm_medium=3Demail&utm_source=3Dfoo=
ter>
>> .
>>
>
>
> --
> Who=E2=80=99s got the sweetest disposition?
> One guess, that=E2=80=99s who?
> Who=E2=80=99d never, ever start an argument?
> Who never shows a bit of temperament?
> Who's never wrong but always right?
> Who'd never dream of starting a fight?
> Who get stuck with all the bad luck?
>
--=20
Who=E2=80=99s got the sweetest disposition?
One guess, that=E2=80=99s who?
Who=E2=80=99d never, ever start an argument?
Who never shows a bit of temperament?
Who's never wrong but always right?
Who'd never dream of starting a fight?
Who get stuck with all the bad luck?
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/CAFdMc-2W4Y4UnkZ%3DwtkZtkH3VDd8NiK8FC8KiBccoCyD3=
YmvCw%40mail.gmail.com.
--000000000000b52112057278c398
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">One possible overload, just illustrative:<div><br></div><d=
iv>template <class Element, class OutputIt, class Compare></div><div>=
void topological_sort(std::initialization_list<std::pair<Element>&=
gt; edges, OutputIt d_first, Compare comp);</div></div><br><div class=3D"gm=
ail_quote"><div dir=3D"ltr">On Thu, Aug 2, 2018 at 4:20 PM Daniel Gutson &l=
t;<a href=3D"mailto:danielgutson@gmail.com">danielgutson@gmail.com</a>> =
wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8e=
x;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><br><br><di=
v class=3D"gmail_quote"><div dir=3D"ltr">On Thu, Aug 2, 2018 at 4:17 PM <=
;<a href=3D"mailto:florian.csdt@gmail.com" target=3D"_blank">florian.csdt@g=
mail.com</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D=
"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D=
"ltr">Le jeudi 2 ao=C3=BBt 2018 20:49:11 UTC+2, Daniel Gutson a =C3=A9crit=
=C2=A0:<blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8e=
x;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">I couldn=
9;t find any paper proposing a topological sort.<div>Is there any reason no=
body proposed it yet?</div><div>Would there be interest?</div><br></div></b=
lockquote><div>=C2=A0</div><div>My feeling is: to standardize a topological=
sort, you would need to standardize a graph class. Standardizing such a cl=
ass would require big efforts, especially because there is no a best way to=
represent a graph.</div></div></blockquote><div><br></div><div>I expected =
this question, and I agree at some degree. However, I strongly think that a=
graph would be implementation. I think that a topological sorting function=
could just receive a container of relationships (edges, potentially std::p=
air), a begin/end, and a back inserter iterator.</div><div>Whether you impl=
ement it with a graph, and it happens that you also want to expose it as a =
stand alone utility, is a different talk.</div><div>=C2=A0</div><blockquote=
class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc soli=
d;padding-left:1ex"><div dir=3D"ltr"><div>Remember that dense linear algebr=
a has not been standardized yet, despite a strong interest and simpler stru=
ctures.<br></div></div>
<p></p>
-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_=
blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2a9c3%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter" target=3D"_blank">=
https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-=
4ec7-aa49-599becf2a9c3%40isocpp.org</a>.<br>
</blockquote></div><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr"=
class=3D"m_4296947007403037229gmail_signature" data-smartmail=3D"gmail_sig=
nature">Who=E2=80=99s got the sweetest disposition?<br>One guess, that=E2=
=80=99s who?<br>Who=E2=80=99d never, ever start an argument?<br>Who never s=
hows a bit of temperament?<br>Who's never wrong but always right?<br>Wh=
o'd never dream of starting a fight?<br>Who get stuck with all the bad =
luck? </div></div>
</blockquote></div><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr"=
class=3D"gmail_signature" data-smartmail=3D"gmail_signature">Who=E2=80=99s=
got the sweetest disposition?<br>One guess, that=E2=80=99s who?<br>Who=E2=
=80=99d never, ever start an argument?<br>Who never shows a bit of temperam=
ent?<br>Who's never wrong but always right?<br>Who'd never dream of=
starting a fight?<br>Who get stuck with all the bad luck? </div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CAFdMc-2W4Y4UnkZ%3DwtkZtkH3VDd8NiK8FC=
8KiBccoCyD3YmvCw%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">h=
ttps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAFdMc-2W4Y4Unk=
Z%3DwtkZtkH3VDd8NiK8FC8KiBccoCyD3YmvCw%40mail.gmail.com</a>.<br />
--000000000000b52112057278c398--
.
Author: =?utf-8?Q?Dietmar_K=C3=BChl?= <dietmar.kuehl@gmail.com>
Date: Thu, 2 Aug 2018 20:28:18 +0100
Raw View
--Apple-Mail-4A94A27D-E3BF-4749-9268-E18A7EBCC359
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
You=E2=80=99d certainy *not* define a =E2=80=9Cgraph class=E2=80=9D. If at =
all a graph *abstraction* like that used by the Boost Graph Library would b=
e defined.
That said, for a topological sort there is no need to define a graph class.=
All that=E2=80=99s needed is a binary predicate Depends(a, b) which states=
whether a depends on b. I think the dependency relation is actually equiva=
lent to a strict weak order.
> On 2 Aug 2018, at 20:17, florian.csdt@gmail.com wrote:
>=20
> Le jeudi 2 ao=C3=BBt 2018 20:49:11 UTC+2, Daniel Gutson a =C3=A9crit :
>>=20
>> I couldn't find any paper proposing a topological sort.
>> Is there any reason nobody proposed it yet?
>> Would there be interest?
>>=20
> =20
> My feeling is: to standardize a topological sort, you would need to stand=
ardize a graph class. Standardizing such a class would require big efforts,=
especially because there is no a best way to represent a graph.
> Remember that dense linear algebra has not been standardized yet, despite=
a strong interest and simpler structures.
> --=20
> You received this message because you are subscribed to the Google Groups=
"ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an=
email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> To view this discussion on the web visit https://groups.google.com/a/isoc=
pp.org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2a9c3%40isocpp.=
org.
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/50C0A1B7-1DCA-4576-B65C-FE43050657B9%40gmail.com=
..
--Apple-Mail-4A94A27D-E3BF-4749-9268-E18A7EBCC359
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<html><head><meta http-equiv=3D"content-type" content=3D"text/html; charset=
=3Dutf-8"></head><body dir=3D"auto"><div></div><div>You=E2=80=99d certainy =
*not* define a =E2=80=9Cgraph class=E2=80=9D. If at all a graph *abstractio=
n* like that used by the Boost Graph Library would be defined.</div><div><b=
r></div><div>That said, for a topological sort there is no need to define a=
graph class. All that=E2=80=99s needed is a binary predicate Depends(a, b)=
which states whether a depends on b. I think the dependency relation is ac=
tually equivalent to a strict weak order.</div><div><br>On 2 Aug 2018, at 2=
0:17, <a href=3D"mailto:florian.csdt@gmail.com">florian.csdt@gmail.com</a> =
wrote:<br><br></div><blockquote type=3D"cite"><div><div dir=3D"ltr">Le jeud=
i 2 ao=C3=BBt 2018 20:49:11 UTC+2, Daniel Gutson a =C3=A9crit :<blockq=
uote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-lef=
t: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">I couldn't find any =
paper proposing a topological sort.<div>Is there any reason nobody proposed=
it yet?</div><div>Would there be interest?</div><br></div></blockquote><di=
v> </div><div>My feeling is: to standardize a topological sort, you wo=
uld need to standardize a graph class. Standardizing such a class would req=
uire big efforts, especially because there is no a best way to represent a =
graph.</div><div>Remember that dense linear algebra has not been standardiz=
ed yet, despite a strong interest and simpler structures.<br></div></div>
<p></p>
-- <br>
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2a9c3%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.goo=
gle.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2=
a9c3%40isocpp.org</a>.<br>
</div></blockquote></body></html>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1DCA-4576-B65C-FE43050657B9%=
40gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1DCA-4576-B65C-FE43050657B9%=
40gmail.com</a>.<br />
--Apple-Mail-4A94A27D-E3BF-4749-9268-E18A7EBCC359--
.
Author: Daniel Gutson <danielgutson@gmail.com>
Date: Thu, 2 Aug 2018 16:35:20 -0300
Raw View
--0000000000000a65ce057278eaca
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
On Thu, Aug 2, 2018 at 4:28 PM Dietmar K=C3=BChl <dietmar.kuehl@gmail.com> =
wrote:
> You=E2=80=99d certainy *not* define a =E2=80=9Cgraph class=E2=80=9D. If a=
t all a graph
> *abstraction* like that used by the Boost Graph Library would be defined.
>
> That said, for a topological sort there is no need to define a graph
> class. All that=E2=80=99s needed is a binary predicate Depends(a, b) whic=
h states
> whether a depends on b. I
>
That predicate is actually better than my container of relations.
(Additionally, there is no need to provide a Compare object I think).
So I propose a different thing: those interested in participating in the
proposal of a topological_sort() function, please let me know in a private
email. I will create a shared document.
First thing will be to define the prototype.
Thanks,
Daniel.
> think the dependency relation is actually equivalent to a strict weak
> order.
>
> On 2 Aug 2018, at 20:17, florian.csdt@gmail.com wrote:
>
> Le jeudi 2 ao=C3=BBt 2018 20:49:11 UTC+2, Daniel Gutson a =C3=A9crit :
>>
>> I couldn't find any paper proposing a topological sort.
>> Is there any reason nobody proposed it yet?
>> Would there be interest?
>>
>>
> My feeling is: to standardize a topological sort, you would need to
> standardize a graph class. Standardizing such a class would require big
> efforts, especially because there is no a best way to represent a graph.
> Remember that dense linear algebra has not been standardized yet, despite
> a strong interest and simpler structures.
>
> --
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> To view this discussion on the web visit
> https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523=
c-4ec7-aa49-599becf2a9c3%40isocpp.org
> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-52=
3c-4ec7-aa49-599becf2a9c3%40isocpp.org?utm_medium=3Demail&utm_source=3Dfoot=
er>
> .
>
> --
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> To view this discussion on the web visit
> https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1DC=
A-4576-B65C-FE43050657B9%40gmail.com
> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1D=
CA-4576-B65C-FE43050657B9%40gmail.com?utm_medium=3Demail&utm_source=3Dfoote=
r>
> .
>
--=20
Who=E2=80=99s got the sweetest disposition?
One guess, that=E2=80=99s who?
Who=E2=80=99d never, ever start an argument?
Who never shows a bit of temperament?
Who's never wrong but always right?
Who'd never dream of starting a fight?
Who get stuck with all the bad luck?
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/CAFdMc-2mCCXUkAYthyxr0O%2BeOaHE783Q6SL0ks5LWsFt4=
MNvrg%40mail.gmail.com.
--0000000000000a65ce057278eaca
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Thu=
, Aug 2, 2018 at 4:28 PM Dietmar K=C3=BChl <<a href=3D"mailto:dietmar.ku=
ehl@gmail.com">dietmar.kuehl@gmail.com</a>> wrote:<br></div><blockquote =
class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid=
;padding-left:1ex"><div dir=3D"auto"><div></div><div>You=E2=80=99d certainy=
*not* define a =E2=80=9Cgraph class=E2=80=9D. If at all a graph *abstracti=
on* like that used by the Boost Graph Library would be defined.</div><div><=
br></div><div>That said, for a topological sort there is no need to define =
a graph class. All that=E2=80=99s needed is a binary predicate Depends(a, b=
) which states whether a depends on b. I </div></div></blockquote><div><br>=
</div><div>That predicate is actually better than my container of relations=
.. (Additionally, there is no need to provide a Compare object I think).</di=
v><div><br></div><div>So I propose a different thing: those interested in p=
articipating in the proposal of a topological_sort() function, please let m=
e know in a private email. I will create a shared document.</div><div>First=
thing will be to define the prototype.</div><div><br></div><div>Thanks,</d=
iv><div><br></div><div>=C2=A0 =C2=A0 Daniel.</div><div><br></div><div>=C2=
=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;borde=
r-left:1px #ccc solid;padding-left:1ex"><div dir=3D"auto"><div>think the de=
pendency relation is actually equivalent to a strict weak order.</div><div>=
<br>On 2 Aug 2018, at 20:17, <a href=3D"mailto:florian.csdt@gmail.com" targ=
et=3D"_blank">florian.csdt@gmail.com</a> wrote:<br><br></div><blockquote ty=
pe=3D"cite"><div><div dir=3D"ltr">Le jeudi 2 ao=C3=BBt 2018 20:49:11 UTC+2,=
Daniel Gutson a =C3=A9crit=C2=A0:<blockquote class=3D"gmail_quote" style=
=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"=
><div dir=3D"ltr">I couldn't find any paper proposing a topological sor=
t.<div>Is there any reason nobody proposed it yet?</div><div>Would there be=
interest?</div><br></div></blockquote><div>=C2=A0</div><div>My feeling is:=
to standardize a topological sort, you would need to standardize a graph c=
lass. Standardizing such a class would require big efforts, especially beca=
use there is no a best way to represent a graph.</div><div>Remember that de=
nse linear algebra has not been standardized yet, despite a strong interest=
and simpler structures.<br></div></div>
<p></p>
-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_=
blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2a9c3%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter" target=3D"_blank">=
https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-=
4ec7-aa49-599becf2a9c3%40isocpp.org</a>.<br>
</div></blockquote></div>
<p></p>
-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_=
blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1DCA-4576-B65C-FE43050657B9%=
40gmail.com?utm_medium=3Demail&utm_source=3Dfooter" target=3D"_blank">h=
ttps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1DCA-4=
576-B65C-FE43050657B9%40gmail.com</a>.<br>
</blockquote></div><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr"=
class=3D"gmail_signature" data-smartmail=3D"gmail_signature">Who=E2=80=99s=
got the sweetest disposition?<br>One guess, that=E2=80=99s who?<br>Who=E2=
=80=99d never, ever start an argument?<br>Who never shows a bit of temperam=
ent?<br>Who's never wrong but always right?<br>Who'd never dream of=
starting a fight?<br>Who get stuck with all the bad luck? </div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CAFdMc-2mCCXUkAYthyxr0O%2BeOaHE783Q6S=
L0ks5LWsFt4MNvrg%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">h=
ttps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAFdMc-2mCCXUkA=
Ythyxr0O%2BeOaHE783Q6SL0ks5LWsFt4MNvrg%40mail.gmail.com</a>.<br />
--0000000000000a65ce057278eaca--
.
Author: Richard Smith <richard@metafoo.co.uk>
Date: Thu, 2 Aug 2018 13:42:40 -0700
Raw View
--000000000000db717a057279da0d
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
On Thu, 2 Aug 2018 at 12:28, Dietmar K=C3=BChl <dietmar.kuehl@gmail.com> wr=
ote:
> You=E2=80=99d certainy *not* define a =E2=80=9Cgraph class=E2=80=9D. If a=
t all a graph
> *abstraction* like that used by the Boost Graph Library would be defined.
>
> That said, for a topological sort there is no need to define a graph
> class. All that=E2=80=99s needed is a binary predicate Depends(a, b) whic=
h states
> whether a depends on b. I think the dependency relation is actually
> equivalent to a strict weak order.
>
I think you want a partial order, not merely a strict weak order; a
topological sort over a structure whose partial order is a strict weak
order is exactly the same thing as a regular sort.
But I'm not sure that this is a useful algorithm when treated as operating
on an arbitrary partial order: I think you lose the O(V+E) time bound if
you describe your graph that way, and instead get an O(N^2) time bound.
> On 2 Aug 2018, at 20:17, florian.csdt@gmail.com wrote:
>
> Le jeudi 2 ao=C3=BBt 2018 20:49:11 UTC+2, Daniel Gutson a =C3=A9crit :
>>
>> I couldn't find any paper proposing a topological sort.
>> Is there any reason nobody proposed it yet?
>> Would there be interest?
>>
>>
> My feeling is: to standardize a topological sort, you would need to
> standardize a graph class. Standardizing such a class would require big
> efforts, especially because there is no a best way to represent a graph.
> Remember that dense linear algebra has not been standardized yet, despite
> a strong interest and simpler structures.
>
> --
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> To view this discussion on the web visit
> https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523=
c-4ec7-aa49-599becf2a9c3%40isocpp.org
> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-52=
3c-4ec7-aa49-599becf2a9c3%40isocpp.org?utm_medium=3Demail&utm_source=3Dfoot=
er>
> .
>
> --
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> To view this discussion on the web visit
> https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1DC=
A-4576-B65C-FE43050657B9%40gmail.com
> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1D=
CA-4576-B65C-FE43050657B9%40gmail.com?utm_medium=3Demail&utm_source=3Dfoote=
r>
> .
>
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/CAOfiQqmr-ua-JTzM1TAGQiAeoWK__mrPh-32hx3utXEy72c=
MXQ%40mail.gmail.com.
--000000000000db717a057279da0d
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_quote"><div dir=3D"ltr">On Thu, 2 Aug =
2018 at 12:28, Dietmar K=C3=BChl <<a href=3D"mailto:dietmar.kuehl@gmail.=
com">dietmar.kuehl@gmail.com</a>> wrote:<br></div><blockquote class=3D"g=
mail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-l=
eft:1ex"><div dir=3D"auto"><div></div><div>You=E2=80=99d certainy *not* def=
ine a =E2=80=9Cgraph class=E2=80=9D. If at all a graph *abstraction* like t=
hat used by the Boost Graph Library would be defined.</div><div><br></div><=
div>That said, for a topological sort there is no need to define a graph cl=
ass. All that=E2=80=99s needed is a binary predicate Depends(a, b) which st=
ates whether a depends on b. I think the dependency relation is actually eq=
uivalent to a strict weak order.</div></div></blockquote><div><br></div><di=
v>I think you want a partial order, not merely a strict weak order; a topol=
ogical sort over a structure whose partial order is a strict weak order is =
exactly the same thing as a regular sort.</div><div><br></div><div>But I=
9;m not sure that this is a useful algorithm when treated as operating on a=
n arbitrary partial order: I think you lose the O(V+E) time bound if you de=
scribe your graph that way, and instead get an O(N^2) time bound.</div><div=
>=C2=A0<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"auto"><div>On 2=
Aug 2018, at 20:17, <a href=3D"mailto:florian.csdt@gmail.com" target=3D"_b=
lank">florian.csdt@gmail.com</a> wrote:<br><br></div><blockquote type=3D"ci=
te"><div><div dir=3D"ltr">Le jeudi 2 ao=C3=BBt 2018 20:49:11 UTC+2, Daniel =
Gutson a =C3=A9crit=C2=A0:<blockquote class=3D"gmail_quote" style=3D"margin=
:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=
=3D"ltr">I couldn't find any paper proposing a topological sort.<div>Is=
there any reason nobody proposed it yet?</div><div>Would there be interest=
?</div><br></div></blockquote><div>=C2=A0</div><div>My feeling is: to stand=
ardize a topological sort, you would need to standardize a graph class. Sta=
ndardizing such a class would require big efforts, especially because there=
is no a best way to represent a graph.</div><div>Remember that dense linea=
r algebra has not been standardized yet, despite a strong interest and simp=
ler structures.<br></div></div>
<p></p>
-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_=
blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2a9c3%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter" target=3D"_blank">=
https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-=
4ec7-aa49-599becf2a9c3%40isocpp.org</a>.<br>
</div></blockquote></div>
<p></p>
-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_=
blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1DCA-4576-B65C-FE43050657B9%=
40gmail.com?utm_medium=3Demail&utm_source=3Dfooter" target=3D"_blank">h=
ttps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1DCA-4=
576-B65C-FE43050657B9%40gmail.com</a>.<br>
</blockquote></div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CAOfiQqmr-ua-JTzM1TAGQiAeoWK__mrPh-32=
hx3utXEy72cMXQ%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">htt=
ps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAOfiQqmr-ua-JTzM=
1TAGQiAeoWK__mrPh-32hx3utXEy72cMXQ%40mail.gmail.com</a>.<br />
--000000000000db717a057279da0d--
.
Author: =?utf-8?Q?Dietmar_K=C3=BChl?= <dietmar.kuehl@gmail.com>
Date: Thu, 2 Aug 2018 23:24:39 +0100
Raw View
--Apple-Mail-80A61FFD-C73A-4C4E-86D4-2CD8A1DFACDE
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Yes, agreed. I got a bit carried away: it is necessary to obtain the edges=
rather than just the relation between the edges. Assuming there is are eff=
icient approaches to extract the end points of an edge and a way to associa=
te some data with the end points it should be sufficient to get hold of the=
edges. On the other hand it still necessary to somehow store some data str=
ucture for the nodes.
I think there could be a nice formulation of the algorithm in terms of prop=
erty maps for the nodes to store a count and an indication of the next node=
: that=E2=80=99s the only reason I=E2=80=99m somewhat interested.
> On 2 Aug 2018, at 21:42, Richard Smith <richard@metafoo.co.uk> wrote:
>=20
>> On Thu, 2 Aug 2018 at 12:28, Dietmar K=C3=BChl <dietmar.kuehl@gmail.com>=
wrote:
>> You=E2=80=99d certainy *not* define a =E2=80=9Cgraph class=E2=80=9D. If =
at all a graph *abstraction* like that used by the Boost Graph Library woul=
d be defined.
>>=20
>> That said, for a topological sort there is no need to define a graph cla=
ss. All that=E2=80=99s needed is a binary predicate Depends(a, b) which sta=
tes whether a depends on b. I think the dependency relation is actually equ=
ivalent to a strict weak order.
>=20
> I think you want a partial order, not merely a strict weak order; a topol=
ogical sort over a structure whose partial order is a strict weak order is =
exactly the same thing as a regular sort.
>=20
> But I'm not sure that this is a useful algorithm when treated as operatin=
g on an arbitrary partial order: I think you lose the O(V+E) time bound if =
you describe your graph that way, and instead get an O(N^2) time bound.
> =20
>>> On 2 Aug 2018, at 20:17, florian.csdt@gmail.com wrote:
>>>=20
>>> Le jeudi 2 ao=C3=BBt 2018 20:49:11 UTC+2, Daniel Gutson a =C3=A9crit :
>>>>=20
>>>> I couldn't find any paper proposing a topological sort.
>>>> Is there any reason nobody proposed it yet?
>>>> Would there be interest?
>>>>=20
>>> =20
>>> My feeling is: to standardize a topological sort, you would need to sta=
ndardize a graph class. Standardizing such a class would require big effort=
s, especially because there is no a best way to represent a graph.
>>> Remember that dense linear algebra has not been standardized yet, despi=
te a strong interest and simpler structures.
>>> --=20
>>> You received this message because you are subscribed to the Google Grou=
ps "ISO C++ Standard - Future Proposals" group.
>>> To unsubscribe from this group and stop receiving emails from it, send =
an email to std-proposals+unsubscribe@isocpp.org.
>>> To post to this group, send email to std-proposals@isocpp.org.
>>> To view this discussion on the web visit https://groups.google.com/a/is=
ocpp.org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2a9c3%40isocp=
p.org.
>>=20
>> --=20
>> You received this message because you are subscribed to the Google Group=
s "ISO C++ Standard - Future Proposals" group.
>> To unsubscribe from this group and stop receiving emails from it, send a=
n email to std-proposals+unsubscribe@isocpp.org.
>> To post to this group, send email to std-proposals@isocpp.org.
>> To view this discussion on the web visit https://groups.google.com/a/iso=
cpp.org/d/msgid/std-proposals/50C0A1B7-1DCA-4576-B65C-FE43050657B9%40gmail.=
com.
>=20
> --=20
> You received this message because you are subscribed to the Google Groups=
"ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an=
email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> To view this discussion on the web visit https://groups.google.com/a/isoc=
pp.org/d/msgid/std-proposals/CAOfiQqmr-ua-JTzM1TAGQiAeoWK__mrPh-32hx3utXEy7=
2cMXQ%40mail.gmail.com.
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/C475FD3A-1387-4719-A25C-1FF5A0A7063D%40gmail.com=
..
--Apple-Mail-80A61FFD-C73A-4C4E-86D4-2CD8A1DFACDE
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<html><head><meta http-equiv=3D"content-type" content=3D"text/html; charset=
=3Dutf-8"></head><body dir=3D"auto"> Yes, agreed. I got a bit carried =
away: it is necessary to obtain the edges rather than just the relation bet=
ween the edges. Assuming there is are efficient approaches to extract the e=
nd points of an edge and a way to associate some data with the end points i=
t should be sufficient to get hold of the edges. On the other hand it still=
necessary to somehow store some data structure for the nodes.<div><br></di=
v><div>I think there could be a nice formulation of the algorithm in terms =
of property maps for the nodes to store a count and an indication of the ne=
xt node: that=E2=80=99s the only reason I=E2=80=99m somewhat interested.</d=
iv><div><br><div>On 2 Aug 2018, at 21:42, Richard Smith <<a href=3D"mail=
to:richard@metafoo.co.uk">richard@metafoo.co.uk</a>> wrote:<br><br></div=
><blockquote type=3D"cite"><div><div dir=3D"ltr"><div class=3D"gmail_quote"=
><div dir=3D"ltr">On Thu, 2 Aug 2018 at 12:28, Dietmar K=C3=BChl <<a hre=
f=3D"mailto:dietmar.kuehl@gmail.com">dietmar.kuehl@gmail.com</a>> wrote:=
<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bord=
er-left:1px #ccc solid;padding-left:1ex"><div dir=3D"auto"><div></div><div>=
You=E2=80=99d certainy *not* define a =E2=80=9Cgraph class=E2=80=9D. If at =
all a graph *abstraction* like that used by the Boost Graph Library would b=
e defined.</div><div><br></div><div>That said, for a topological sort there=
is no need to define a graph class. All that=E2=80=99s needed is a binary =
predicate Depends(a, b) which states whether a depends on b. I think the de=
pendency relation is actually equivalent to a strict weak order.</div></div=
></blockquote><div><br></div><div>I think you want a partial order, not mer=
ely a strict weak order; a topological sort over a structure whose partial =
order is a strict weak order is exactly the same thing as a regular sort.</=
div><div><br></div><div>But I'm not sure that this is a useful algorithm wh=
en treated as operating on an arbitrary partial order: I think you lose the=
O(V+E) time bound if you describe your graph that way, and instead get an =
O(N^2) time bound.</div><div> <br></div><blockquote class=3D"gmail_quo=
te" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"=
><div dir=3D"auto"><div>On 2 Aug 2018, at 20:17, <a href=3D"mailto:florian.=
csdt@gmail.com" target=3D"_blank">florian.csdt@gmail.com</a> wrote:<br><br>=
</div><blockquote type=3D"cite"><div><div dir=3D"ltr">Le jeudi 2 ao=C3=BBt =
2018 20:49:11 UTC+2, Daniel Gutson a =C3=A9crit :<blockquote class=3D"=
gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid=
;padding-left:1ex"><div dir=3D"ltr">I couldn't find any paper proposing a t=
opological sort.<div>Is there any reason nobody proposed it yet?</div><div>=
Would there be interest?</div><br></div></blockquote><div> </div><div>=
My feeling is: to standardize a topological sort, you would need to standar=
dize a graph class. Standardizing such a class would require big efforts, e=
specially because there is no a best way to represent a graph.</div><div>Re=
member that dense linear algebra has not been standardized yet, despite a s=
trong interest and simpler structures.<br></div></div>
<p></p>
-- <br>
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_=
blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2a9c3%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter" target=3D"_blank">=
https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-=
4ec7-aa49-599becf2a9c3%40isocpp.org</a>.<br>
</div></blockquote></div>
<p></p>
-- <br>
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_=
blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1DCA-4576-B65C-FE43050657B9%=
40gmail.com?utm_medium=3Demail&utm_source=3Dfooter" target=3D"_blank">h=
ttps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1DCA-4=
576-B65C-FE43050657B9%40gmail.com</a>.<br>
</blockquote></div></div>
<p></p>
-- <br>
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CAOfiQqmr-ua-JTzM1TAGQiAeoWK__mrPh-32=
hx3utXEy72cMXQ%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter"=
>https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAOfiQqmr-ua-=
JTzM1TAGQiAeoWK__mrPh-32hx3utXEy72cMXQ%40mail.gmail.com</a>.<br>
</div></blockquote></div></body></html>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/C475FD3A-1387-4719-A25C-1FF5A0A7063D%=
40gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/C475FD3A-1387-4719-A25C-1FF5A0A7063D%=
40gmail.com</a>.<br />
--Apple-Mail-80A61FFD-C73A-4C4E-86D4-2CD8A1DFACDE--
.