220 39508 <50C0A1B7-1DCA-4576-B65C-FE43050657B9@gmail.com> article Path: news.gmane.org!.POSTED!not-for-mail From: =?utf-8?Q?Dietmar_K=C3=BChl?= Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Re: topological sort? Date: Thu, 2 Aug 2018 20:28:18 +0100 Lines: 108 Approved: news@gmane.org Message-ID: <50C0A1B7-1DCA-4576-B65C-FE43050657B9@gmail.com> References: <3a8a66f7-523c-4ec7-aa49-599becf2a9c3@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 (1.0) Content-Type: multipart/alternative; boundary=Apple-Mail-4A94A27D-E3BF-4749-9268-E18A7EBCC359 Content-Transfer-Encoding: 7bit X-Trace: blaine.gmane.org 1533237975 31540 195.159.176.226 (2 Aug 2018 19:26:15 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Thu, 2 Aug 2018 19:26:15 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBDZYDW6QHYINLNUN3MCRUBEJQYNOE@isocpp.org Thu Aug 02 21:26:11 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-wm0-f72.google.com ([74.125.82.72]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1flJEh-00087K-4E for gclcip-std-proposals@m.gmane.org; Thu, 02 Aug 2018 21:26:11 +0200 Original-Received: by mail-wm0-f72.google.com with SMTP id f11-v6sf2291420wmc.3 for ; Thu, 02 Aug 2018 12:28:22 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1533238102; cv=pass; d=google.com; s=arc-20160816; b=HLFkH8Io9pM0oa08lGTqWiMeoa0nDzbjCldgGLxrBbruqWze0MRDm1PMZ+NcdRDm+q Xlo19fzhIzKyf66KQZdeW1Jak+zkEp6kWUl63GUiViXwbaSO9B581uZe2l+oz3QrAv9M +Q1YCLCAkSkTCKm8JmQzz0WegZ9h0Jp7DyP/RgfeJcllbljHrRtc4nu18OUGrZAC4CTl PB6yP77LpBw5Qaz8tmWbNm9kKdrV8bcgzwe9rWG8zpCg1A7xfTkLxhTaQhJDQKwNeVxR emO0iMT9F7qJTMjd44uMMFVFLbbzbg0hWx9VRT/BpZ59yZRxv+RqDFvegNooiIWiSSDC jX9Q== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:to:in-reply-to:references :message-id:subject:date:mime-version:content-transfer-encoding:from :arc-authentication-results:arc-message-signature:dkim-signature :arc-authentication-results; bh=79sLY756PsBBDEJepRFfop+HYgwuKINRB15C2tAl6UU=; b=P8lMQXfsUmpLzai/S4KWHonGJUWstCV89i4X8Bggmvv6+8Vn7b9bgAu5Z63qWPMuZU 5ajGn5qlbn3h6KbMBdoo7Kgx6Tny9tpFaAyQSKbyr5SC+DCgXVrTA00lxsowXqnrRAT+ 1GF408sLQJqU69o6npbcoyH3fPTG7IvovHzQBMAfaTAzN4wwjIoK8BTdx1WradJ+BGO9 Lxa17vl50S8GnNfD3MTMIgsGqBiTauGI/jMl02OZZft4RAfnAOPeeX05j5taT8etEL1X rGOZCBicCXTp5ibGUGC2a0rZmlmlvMV2J5HsrxnR2IxALtgDRnw+6l3inkcKSTFZfoAq z/ww== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=JM04w6Wl; spf=pass (google.com: domain of dietmar.kuehl@gmail.com designates 209.85.220.41 as permitted sender) smtp.mailfrom=dietmar.kuehl@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=from:content-transfer-encoding:mime-version:date:subject:message-id :references:in-reply-to:to:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe; bh=79sLY756PsBBDEJepRFfop+HYgwuKINRB15C2tAl6UU=; b=0xFHsATmpqWZDA9f526bMdeYhLD4xHlREdtk0EBsgIB3LMjRWl8TKOe52BvBUBnZDr c9hYQpJeJ3m2N+9svr7LrgxxLI0IY34pinciNJVCs5qwkAnPyNj3Dw4I8LRf+PVsHNRm 49kHrw7DG1OmDvusv3Xp1fbaZZzwFqmz8984G7xmcUORFosurgj3Z+cq8zJrmzMIAlkb rcgOvbL78etjcTx9i1KhgxQDNtqZlJ1Z7TiLkDhxrpmklAyFWDalxMLstQiHzAXyUvpI RofW05baeu8o274Nybyj30lZHeVYe6CCOiKoV0ABWuYq8AI+r6ECOGGgRSmwRmEAW/Wh aTmA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:content-transfer-encoding:mime-version:date :subject:message-id:references:in-reply-to:to:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:x-spam-checked-in-group:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=79sLY756PsBBDEJepRFfop+HYgwuKINRB15C2tAl6UU=; b=EroPIws+4SI3uwIyB3o6i7PX85C18JwPto+rAjCQeI8nXk4+GCIr1z7kf8zTNqHIJT kEBCBpXcQ8w5lZwjaurU4UFCtDOO4aG9C+J6DBBh4lHaL1euY6w0BxM3f3GbjE4z7tcw 2CzjocjR4ISFiu4N2ZNc2SOcGyT2lkhVbL+2YydnRmtegWBNznfOMLoSPGevqKXD+yf1 xjz8NT1nO35vTrObHseLqmjq6PFhF1a7xhhoxNkleDqciC2KdoRvCfYX+61H7tQcv1y+ rmY25DBgfXyDXYCJtIJEEUwsArp6Ee/aSG/Zjj8EkbkrupXiuYLBfPhSg+cNPyjb7s/9 c6J X-Gm-Message-State: AOUpUlEAdD4TJ2zSrwdGDjUYww+2w+UZSYUOzHl6GK74ybnK4bsd+Eo9 5KCMj88Y5Rc5lmAnIyiSehgD4w== X-Google-Smtp-Source: AAOMgpeKcwK86TiVjfteCq4Utz5onEJhSKZkokWm277Owi9PVGR0z6iKB0wO9TKvXWWjkt8hFel3/w== X-Received: by 2002:a1c:7c12:: with SMTP id x18-v6mr420583wmc.27.1533238102022; Thu, 02 Aug 2018 12:28:22 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a1c:f00a:: with SMTP id a10-v6ls796335wmb.12.canary-gmail; Thu, 02 Aug 2018 12:28:20 -0700 (PDT) X-Received: by 2002:a1c:6bc9:: with SMTP id a70-v6mr2959957wmi.92.1533238100607; Thu, 02 Aug 2018 12:28:20 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1533238100; cv=none; d=google.com; s=arc-20160816; b=NbPGY3UeGnl9uBGKBD4+esPBDU3dxok6Kz7h579H9qKyYkZImfxVR4Jp/3n8YP96x+ SCq6ThDvtD8udpCZkveH6Yb7jO6W0vaztt9IlSfknZ1sJ23Wnf1PInJ4OEzVZikWlfSa 5L3bTn8A67i2gLSdyzLzlSzA+Ht1VcVUyiP1gpWigIe/TKxJkjIqNifSUSwkBsxJh3In Zv54r9nYEFycUJn03Ae8sEGgh3C8rUNQDIezM6bAouYw1muXAFt0XCljivscdb2H4LmZ oGyGBLFLxVRdbTPhUDvOsuZrp1Uk+iGZCYf9svd5o2Ja5ncEz6M8Xe5joc0ObzeSA4RV cXxg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:in-reply-to:references:message-id:subject:date:mime-version :content-transfer-encoding:from:dkim-signature :arc-authentication-results; bh=e3gyDGoudHnM2A6SLMp/xKAZCjlriM23Te3h+oQaOMg=; b=RvM9y2pbmuZWgEcIePcLMCEQWRx7mXkGSzBF3a/E46kqv0py0+71tubkLf+RxFcePv 5hK0+Z/oZVSJ5AcQbsmkvd2UGlhcqKE7Phl785WfZzRlAgEEfzEJ+uwr81T6k4YDLRcf pUXOXdXDKVrMTnW4acI9QVG5cd1JJ3LGZO9fmSFLMRjQMoh27m/x+qNVXtG7DaD2+LQi CduI8vLJvY2O0gHcfwdCCwdw7449rgVtFssgBZOsw1kwglZ9P5YjDWWrbePKwGoQ6bRM zGWdYZxxfVsw+MW4Vo4eqfqEGP5vjpX9jy/AmiB/uamvmgMkP+R7ElkdnrFhtahdMalu XHRw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=JM04w6Wl; spf=pass (google.com: domain of dietmar.kuehl@gmail.com designates 209.85.220.41 as permitted sender) smtp.mailfrom=dietmar.kuehl@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Original-Received: from mail-sor-f41.google.com (mail-sor-f41.google.com. [209.85.220.41]) by mx.google.com with SMTPS id a17-v6sor619391wmg.88.2018.08.02.12.28.20 for (Google Transport Security); Thu, 02 Aug 2018 12:28:20 -0700 (PDT) Received-SPF: pass (google.com: domain of dietmar.kuehl@gmail.com designates 209.85.220.41 as permitted sender) client-ip=209.85.220.41; X-Received: by 2002:a1c:7d58:: with SMTP id y85-v6mr2779620wmc.91.1533238100059; Thu, 02 Aug 2018 12:28:20 -0700 (PDT) Original-Received: from [10.2.161.146] (82-132-226-153.dab.02.net. [82.132.226.153]) by smtp.gmail.com with ESMTPSA id r5-v6sm1694710wmc.39.2018.08.02.12.28.19 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 02 Aug 2018 12:28:19 -0700 (PDT) In-Reply-To: <3a8a66f7-523c-4ec7-aa49-599becf2a9c3@isocpp.org> X-Mailer: iPhone Mail (15G77) X-Original-Sender: dietmar.kuehl@gmail.com X-Original-Authentication-Results: mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=JM04w6Wl; spf=pass (google.com: domain of dietmar.kuehl@gmail.com designates 209.85.220.41 as permitted sender) smtp.mailfrom=dietmar.kuehl@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:39508 Archived-At: --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
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.
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.

On 2 Aug 2018, at 2= 0:17, florian.csdt@gmail.com = wrote:

Le jeud= i 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 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.
Remember that dense linear algebra has not been standardiz= ed 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 e= mail to std-proposa= ls+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.goo= gle.com/a/isocpp.org/d/msgid/std-proposals/3a8a66f7-523c-4ec7-aa49-599becf2= a9c3%40isocpp.org.

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+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.c= om/a/isocpp.org/d/msgid/std-proposals/50C0A1B7-1DCA-4576-B65C-FE43050657B9%= 40gmail.com.
--Apple-Mail-4A94A27D-E3BF-4749-9268-E18A7EBCC359-- .