Subject: Re: SG19 Sept 9 (Graph) Zoom call
From: Michael Wong (fraggamuffin_at_[hidden])
Date: 2021-09-13 16:00:32
Awesome! Thank you for working hard towards unification.
On Mon, Sep 13, 2021 at 11:56 AM Phil Ratzloff <Phil.Ratzloff_at_[hidden]>
> Andrew and I have had discussions about bringing things together.
> Hopefully weâll have some good things in a few months. Thanks for your
> *From:* SG19 <sg19-bounces_at_[hidden]> *On Behalf Of *Michael Wong
> via SG19
> *Sent:* Monday, September 13, 2021 10:49 AM
> *To:* sg19_at_[hidden]
> *Cc:* Michael Wong <fraggamuffin_at_[hidden]>
> *Subject:* Re: [SG19] SG19 Sept 9 (Graph) Zoom call
> HI all, here is the closed caption notes:
> 14:03:01 Hi everybody, welcome to the September monthly SG 19th call. I'm
> just setting up.
> 14:03:22 So on the call.
> 14:03:23 We have people are just joining but since zoom is pick up all the
> attendees automatically just going to call out a few names so I have Andrew
> lumps thing.
> 14:03:34 Benjamin Brock, Yulia Birla Larry Lewis Luke della Sandro also no
> soy, Phil rats la Renee Ferdinand revere morale. cn go to see the rest of
> the name.
> 14:03:53 Guess saying Gosh, Scott McMillan Scott Moore will Ray and Joe
> sacks and I'm like a wall of SG 19.
> 14:04:05 So just moving through our agenda.
> 14:04:13 We have.
> 14:04:16 So that's the roll call the agenda today, I believe, is to go
> over two proposals the main source is the graph proposal I think we've been
> reviewing it as we're going along, and there's been some changes.
> 14:04:30 And I believe.
> 14:04:32 Phil has something that he's ready to show us he's excited about
> showing the current progress. It's already gone over, it's been reviewed
> pretty much almost all of for over a year now actually almost two years
> since the pandemic.
> 14:04:46 And so, there's been a lot of modifications, and it's, it's been
> going on long nicely so I think this is just another intermediate
> checkpoint, to see where we are, I believe, Andrew has something that he's
> 14:05:00 And there is a and will I think you have you have a proxy for a,
> an array proposal that you want to consider.
> 14:05:11 That's right, it's more of a news update, so it's something
> that's ongoing, for the last month. Right. And it's just one day this
> machine learning group on the progress of that.
> 14:05:21 Ray, is it is the author here for that or you know i i sent out
> messages to the two authors and receive a reply is but I don't think I
> don't think we need that it's a small modest proposal.
> 14:05:33 Okay, that's fine.
> 14:05:38 Any other issues people want to bring up. So what we do what we
> do is we rotate between three proposals three or four proposals. And right
> now, because we took a break in August for the summer.
> 14:05:52 September is the graph proposal the October meeting is probably
> going to go back to calculus and reinforcement learning but it could be
> replaced by something else depending on whether people have other proposals
> they have in mind.
> 14:06:07 November because of the DST change we usually take a break and
> cancel, and that puts stats.
> 14:06:13 Back on the list on December 9.
> 14:06:17 So that's the current current plan.
> 14:06:21 We don't have the stats how to offer here today Richard Dawson is
> a professor. And I think we're China, and he's teaching right now so he
> can't. He can't come, but that's okay, because that's it would not going to
> be talking about stats today.
> 14:06:35 It's his proposal has actually progressed into LWG meeting at
> some, it's already outside it's already been loaded out of this group.
> 14:06:46 So module any kind of changes from LDL p wg, but we will leave
> it, leave it where it is. Okay. Does anyone have any other things that
> people want to talk about before I go into general.
> 14:06:55 So that's part of general logistics numbers section 2.1. And I'll
> talk a little bit about ISO meeting status.
> 14:07:03 Let me think there is a plenary in October for ISO c++ is a
> virtual plenary.
> 14:07:11 And then there's an attempt at potential face to face meeting. In
> February, in Portland, but because of the pandemic uncertainty and delta
> variants and people's quarantines and varying varying restrictions on
> travels from different countries to different
> 14:07:30 countries.
> 14:07:31 There's now talk of moving, that one also to virtual, but nothing
> has been decided yet they're still looking at either virtual hybrid or
> 14:07:42 So, these this is just the sign of the times, his face.
> 14:07:46 Okay so that pretty much gets through all of my logistics things
> to other people have it any logistics, or any other things that they want
> to bring up before we launch into the papers.
> 14:07:59 Okay, well Hearing none, let's proceed, given that will raise.
> 14:08:12 Ray update is probably the shoulders. Would you say, well, we'll
> do you want to do the update right away and then we'll move into the grant
> proposal. And I think if that's, is that okay, that works for me and just
> tell tell me when to stop.
> 14:08:20 Okay, I'm graph proposal, people
> 14:08:25 Phil and and Andrew, are you Do you guys have any deadlines that
> you need to to like get a drop off or something like that.
> 14:08:33 No, I'm fine.
> 14:08:35 Okay.
> 14:08:37 Andrew Are you wanting to where you plan on covering something
> outside of our paper. It was just the intro pieces of the paper.
> 14:08:46 Okay, so what I'd like to do on that is just cover the, the, the,
> the stuff that I've done, and then we hopefully we'll have some time at the
> end to look at the intros Are you okay with that.
> 14:09:01 Sure.
> 14:09:03 Okay. Okay.
> 14:09:05 Unless you want to do, intro first to lead into, you know, set up
> to what you were your stuff.
> 14:09:13 Either way.
> 14:09:15 Yeah, I
> 14:09:18 don't know how long I can see us taking 45 minutes or so on, on
> my stuff fence on the, the feedback.
> 14:09:29 Okay. An angel How long do you think your peaceful be
> 14:09:34 probably about the same. Okay.
> 14:09:44 That sounds fine yeah 1015 minutes, 10, talking, 5% feedback.
> 14:09:49 That sounds good. Okay, why don't why don't we start.
> 14:09:52 So let's see if I can find it.
> 14:09:57 Oh, there it is.
> 14:10:00 Okay, go ahead. Go ahead. Well, so yes I can just talk over the
> paper if you like I have some time so I could show, I didn't do any slides.
> 14:10:09 So, this proposal is a small proposal was put in about 20 months
> ago first in December 2019 and then quickly a first revision.
> 14:10:20 The authors are talking about a second revision. The main author,
> a young guy amazing guy he worked for a while, for the c++ alliance.
> 14:10:31 And somehow, you know he's still a student I think but got into
> standard the US reading the standard.
> 14:10:35 I'm not sure who the second author is he's perhaps an academic.
> But, anyway, the, the paper itself is somewhat academic it.
> 14:10:46 You know, it includes the wording.
> 14:10:48 It's been criticized by some people high up in the c++ Committee
> is lacking motivation.
> 14:10:54 I can talk to that if we need so the reason why I think this is
> of interest, the machine learning group is it's related, and the remit here
> is pretty much rate related when you read it.
> 14:11:07 Now, this is going back 50 years really fixing an issue from see
> that then was inherited into c++, that arrays are not regular types, you
> can't copy them to be fully regular you need to compare as well, a semi
> regular type is called people.
> 14:11:24 And that can mostly be fixed and I don't understand why it wasn't
> done back when Richie made struct comfortable. So for a while in early.
> See, you would have to copy every single member of a struct when you copy
> destruct but somewhere between one and
> 14:11:42 two, structural help people with your rep with a raised hand side.
> 14:11:44 So that's one place where you get to wake up in the C, and c++.
> 14:11:48 The other singular cases string literal Wars character array can
> be initialized from right hand side string literal.
> 14:12:02 Now, in recent years have been a couple of other cases of array
> copies have been added, where that is convenient. So, lenders will copy the
> by value capture of an array structure bindings will copy an array, right
> hand side, oh sorry I'm not talking over
> 14:12:22 the paper here at all. That's not included. So there is a nice
> examples in the paper. So one of the questions that comes up incessantly
> is, why isn't good enough.
> 14:12:34 And I don't see that as a relevant question I want good built in
> a race. I want them in order to build better class arrays. So, I've been
> kind of working in array related stuff for many years, I did blessing,
> implementation, many years ago.
> 14:12:50 I'm kind of in the Python data, ecosystem at the moment, used to
> do MATLAB
> 14:12:56 arrays, can be comfortable. I, you know, this paper hasn't seen
> any, any issues raised against it people haven't come up with any reasons
> why it won't work.
> 14:13:07 I've been trying to look at it from, you know, an attackers point
> of view what what could be wrong with this what doesn't work. I, I know of
> two small breakages that were discussed with this see.
> 14:13:22 Okay, so what's the history of this, so 20 months ago, it hasn't
> seen any interest. I'm the main proponent keep pushing on it, the author
> has gone on to other things, but it's still kind of keeping his hand in a
> little probably would be involved with
> 14:13:35 this, if there's a revision.
> 14:13:37 So about a year ago, I joined this group, mostly to push rate
> related things and the SG 22, the newly formed C and c++ liaison group,
> partly because I realized that they were more likely to be interested in
> this proposal then c++.
> 14:13:56 As you know, array is a somewhat to boo within the c++ Committee
> and community where it's still very central to see.
> 14:14:03 I mean that's foundational in c++, as well, but it creates
> something of a two worlds view of and that you know, coming back to
> standard array, it's kind of typify by standard array.
> 14:14:16 So what's the problem with standard rate. One of the problems
> listed in this paper is the initialization issue. So I call this the member
> array initialization conundrum.
> 14:14:28 And there is the few kind of work around solutions I've blogged
> on a few of them.
> 14:14:35 But the problem is, you have an existing l value array. How do
> you initialize the standard away with it.
> 14:14:41 Now we have stood ranges copy. So ranges copy can do can do that
> for a one dimensional array, but fails, as soon as it is nested, so it
> won't do it for nested see array.
> 14:14:53 I believe it won't do it for nested standard right but I haven't
> tried that
> 14:14:58 out, I'll try that.
> 14:15:02 Now, with bit cast you can build custom array and created that
> way. But, you know, standard rate was standardized with c++ 11 but really
> came from boost 10 years before that.
> 14:15:13 And it's you know an early example of a way of wrapping horrible
> see and giving it to c++ facade or API to work with the other algorithms.
> That's not necessary now in c++ 17 we got data and science free member
> functions, along with the existing data and
> 14:15:50 data science. Yeah.
> 14:15:42 Yeah. So, oh beginning End Of course. So, you know, all of those
> three functions, interoperate fine with a radius and built in arrays also
> have a specialization for stud swap.
> 14:15:55 So, effectively, you know that's a, an old range algorithm that
> will copy even nested array is properly recursive Lee.
> 14:16:02 I'm drifting off again. So, standard rate in c++ 20 we got
> standard to array, which will take an array of value and create a standard
> array from it. But what wasn't noticed is that in the is Luke here, yeah.
> 14:16:20 Oh yeah, look see So Luke noticed a couple of months ago that the
> earlier experimental maker Ray was able to make zero sized standard array.
> 14:16:27 But to array cannot do that because it's converting built in and
> ready to a standard rate you can't have a zero size built in array. So, so
> you know one of the advantages of standard rate is that it's got the zero
> sys specialization.
> 14:16:45 And then one of the downsides, is it needs to zero size
> specialization so every array class you right you have to do as he works on
> a specialization. And it's a little tricky to write, it's easy to get wrong.
> 14:16:56 And there's several of the standard library implementations got
> it wrong and had issues raised against it.
> 14:17:01 But anyway, I'm rambling again I guess so.
> 14:17:04 The history then so it got viewed, but it got raised on the
> liaison mailing list and was discussed, a month ago was August the sixth.
> 14:17:14 It holiday season. So, that partly member to dissenting voices
> are not dissenting there was some concern raised at the highest levels.
> 14:17:25 Worried of WG 21 didn't make it to the meeting, but sent messages
> to the reflector with, you know, unspecified concerns that when arrays have
> been dealt with.
> 14:17:37 When it's been attempted to improve it raised in the past, it's
> led to difficulties.
> 14:17:44 So that's what I want to drill down on you know I'm so, so what
> came out of that meeting is we need implementations we need compiler
> implementations. So, the paper has been forwarded to EWG, but it's not
> worth doing, until we have implementation experience.
> 14:18:00 And similarly on the sea side wg 14. I've got much stronger
> gating they require implementations.
> 14:18:09 So, I happen to have a few weeks, open before contract, that's
> coming up in mid October, so I volunteered to do the planning and GCC
> 14:18:22 And that's what I've started on this, this week.
> 14:18:26 I don't think we have any other clan guys here it was William
> Moses and the, the array, the young, the calculus guy is like do to have
> some sessions with them on the VM side.
> 14:18:39 Oh yeah, so there's a bunch of Tony tables that are worth looking
> at. So what does it propose the initialization is fairly simple that you
> can initialize an array from an array, right hand side.
> 14:18:52 Then copy. If you have to raise a and b. Now you can just do A
> equals B, and you get the copy.
> 14:19:00 Then a little trickier perhaps that's placeholder semantics. So,
> an auto.
> 14:19:09 We are playing array will declaration will deduce the element
> 14:19:16 Now that interacts a little oddly with existing language
> features, and there's a c++ 20 edition. That allows pointers or references
> to incomplete arrays to be initialized from array is with no deduction
> going on there.
> 14:19:30 So that's an template deduction with all with auto attack. So
> anyway, the placeholder is one possible area of dragons. The other possible
> area is praised initialization.
> 14:19:42 You know the code for that and GCC is pretty horrible I've dived
> into that before. And I'm sure the same is true in clang.
> 14:19:49 And it's different also between C and c++. So at the moment I'm
> focusing on the c++ implementation of this
> 14:20:00 array return from function in fact yes that's the main thing that
> I kind of got into this foreign, and wanting.
> 14:20:07 So, that change. I believe will be easy enough to implement, but
> it then leads to Abi, that this is a new API for both C and c++, and for
> the wider foreign function interface world.
> 14:20:21 And that's obviously going to take time, you know, there's so
> many platforms, especially on the, on the sea side of things, and, you
> know, who are the API people, they think that meeting some smoky room.
> 14:20:33 So even find out who they are and how this how this happens, is
> likely to take some time.
> 14:20:43 So I guess I'm up to 10 minutes so if if there are any questions
> we can spend five minutes or so before the next papers.
> 14:20:51 At the end of this will this make or break a regular type.
> 14:20:56 Sorry Sagan with this make array regular lets me know it will
> make it mostly semi regular. So, this. So the problem is with array
> parameter types or formal parameter types.
> 14:21:10 So, for the liaison meeting. The authors were keen to discuss it,
> but the extremely strong feedback was just let's not even discuss it
> because this proposal will be sunk.
> 14:21:21 If we talk about passing arrays by value two functions. The
> syntax is broken and see an array parameter in either a function or a
> template argument list gets adjusted to the point to type.
> 14:21:37 And there's nothing you can do about that. Actually, there is on
> the template argument side and this is something I'm thinking of amending
> revising the proposal with.
> 14:21:48 So, in a function you cannot declare an argument with dental type
> auto, you know, auto works but that gives you a decay copy of the argument
> that will type of auto with an array argument will deduce array.
> 14:22:01 But then as a function argument that will be interpreted as an
> array as the element pointer and, but in a template document list, you can
> actually use deco type auto that's allowed you pass it in a way it will
> produce an array.
> 14:22:17 But then the array can't be initialized.
> 14:22:20 It will be really nice if you could do that with string literal
> because it gives you for free.
> 14:22:25 You know strings as template arguments, which is what people will
> be finally getting with static string, this is you know you can already do
> that in c++ 20 but this allows you to use a built in a way to do that, and
> potentially, you know, arrays of integers
> 14:22:40 or floating point numbers, or whatever. So in fact, that only
> requires a tiny change in the wording for what constitutes a structural
> type, because that is the requirement on non tight template arguments now.
> 14:22:56 And TTP is I should say.
> 14:22:59 And so, Has this been reviewed by any c++ groups.
> 14:23:05 No.
> 14:23:06 Okay, except the liaison group officially counts as.
> 14:23:10 Yeah. Okay, so it was passed over. Because, so December 2019 was
> a was a tricky period because right after that we got shut down. So, if
> it's not on anybody's radar is this or no I mean I talked to friends about
> it because he you know he frequents this
> 14:23:30 group as well as SG 22.
> 14:23:33 And he's written a rave related papers in the past, you know
> after the Vla the array study group debacle. He, he wrote the last paper on
> killing and helping this and what has he said, is he.
> 14:23:47 I'm not sure so he before the liaison meeting he sent out a
> strange message saying why are we talking about this, I don't think he
> realized it had been on the agenda, but also when I, when I said well it's
> been you know it hasn't been looked up to 20
> 14:24:02 months he said, That's usual for c++ proposals small proposals
> like this go in and unless somebody is pushing it, it's not going to get
> 14:24:13 So, it hasn't had sufficient inspection from language experts,
> and I would really like to get that done before the labor that really needs
> an examination from the design people like so this needs to go through
> 14:24:29 working group.
> 14:24:31 So that's so it's it's do for evolution working group, and the
> implementation is what is required to make it worth going there.
> 14:24:39 So hopefully, by early October I'll have something by mid
> October, enough to move it to EWG while that might be true.
> 14:24:49 Your, yo, yo, you might also be your, you're also risking the
> idea that evolution can change this significantly on you, or just rejected
> outright. And then you might not have anything to you might have wasted
> some time right so that's true.
> 14:25:04 And, you know, that was flagged up in liaison as well.
> 14:25:08 But somebody needs to do this, I'm not, I'm not the best I'm a
> hacker I can dive in. I've done a couple of PC patches in the past. I'll
> give it my best go yeah and and the fact that the fact of doing it will
> allow you to find, you know some some some
> 14:25:24 of the answers that this paper is posing and, you know, maybe it
> should smoke, it should smoke out any issues, and hopefully quell the third
> because you know there is fear, uncertainty and doubt being spread.
> 14:25:36 And this will get more certainty.
> 14:25:40 So, at the end of the day, if this works then you're going to be
> able to copy a raise to raise directly, without going through some sort of
> loop. Is that is that right that's right and then it happens to kind of
> mend a whole bunch of standard algorithms
> 14:25:58 that are the moment it doesn't make sense to pass a raised
> because they will fail. So you know ranges is pretty good but as soon as
> you get to multi dimensional raise it fails, or once you go past the level
> where you need now value it will fail, I think.
> 14:26:12 So this just makes it more robust. There's also a c++ 23 proposal
> to allow braced initialization in more standard algorithms, and that will
> just work with a radius once, once this is done.
> 14:26:27 And I think.
> 14:26:27 Recently, that was a cosmetic change that allows you to do square
> brackets with, with commerce, to be to be parsed properly as an array.
> 14:26:39 Sorry, I missed that, this, this.
> 14:26:43 So this is a paper by.
> 14:26:46 I'll have to dig it out later it was put in.
> 14:26:49 My name is Mark Coleman.
> 14:26:55 No, I'm thinking of another paper this is
> 14:26:55 I braced initialization in standard algorithm.
> 14:26:59 Yeah, I know. Yeah.
> 14:27:02 But yes, I'll check check this afterwards and send out links.
> Okay, thank you.
> 14:27:08 Okay, I mean this is this is only the start.
> 14:27:12 You know, we make it a semi regular, and then there's a bunch of
> other things that improve things more, like this one, you know that what
> you're getting into, because if you don't put push this through EWG first,
> and then do an implementation, while that's
> 14:27:27 that. That is really helpful it snot smoking out the, the
> Gremlins you, you know, ew, you might totally reject this or change it. So
> just be careful.
> 14:27:40 I mean, I mean, I'm interested in any opinions from the group
> here as well if anybody thinks either this is crazy or this is great,
> please drop me a line.
> 14:27:48 If anybody sees any issues especially. Great.
> 14:27:54 And yes thanks for that heads up Michael Yeah that's it some
> hopefully people will have a bit of a chance to look at I mean arrays is of
> interest to a lot of people, I would say, especially the high performance
> computing people and of course by influence
> 14:28:07 the machine learning people, it would be it would be good if you
> can pass this to people like Mark Coleman.
> 14:28:14 Yes, I've talked with him in the past. Yeah, see what he thinks,
> because they you stay as he is still firmly involved in high performance
> 14:28:24 Anybody who's doing work in the US National Labs, especially some
> of the high performance computing labs. So sure, Andrew might be interested
> who was on the call.
> 14:28:40 Maybe, Devon Devon Lieber at all gone Nevin Yes, yes, so yes I
> dropped Andrew line earlier in the year actually along with the other. Some
> of these guys, they have time they might end and they care, then they might
> actually take a look.
> 14:28:50 I think you have to tread a little bit more carefully on that on
> paper on display but as you said this. This area has lots of Gremlins, and
> there's a lot of people who have historic antagonism towards any kind of
> work towards standard on standard array
> 14:29:03 and still the rest right yes it's almost to do it feels, and I
> didn't make any friends. So, the last time I was here, I had a rant about p
> 2128, the multi dimensional array subscript operator.
> 14:29:15 And we should have a one minute silence because yesterday that
> was voted to call in do. Yes.
> 14:29:23 So, you know, I probably didn't make any friends by opposing that
> but in the end I didn't publish the paper, and it's gone in the world
> hasn't ended. Okay.
> 14:29:32 It's good to know. Good to have you bring this to our attention,
> just to make sure. But, but yeah, this is, this is full of potholes I
> suspect, in some ways, but if it works, it is it will challenge one of our
> 14:29:46 areas that we've been having troubles with and that's why we've
> tried creating replacements for story.
> 14:29:53 There was an attempt that there was an array subcommittee The
> reason Yes, his name is so prominent involved in it was because yes he
> cares about this.
> 14:30:00 And he was actually chairing this array.
> 14:30:04 Working Group subgroup.
> 14:30:06 Okay, which got terminated because they ran into this huge
> problem with this new design of a library type array which can switch
> between the heat, and the stack, which was amazingly incredibly difficult
> to implement.
> 14:30:23 Yes, I tried to follow the history of that I don't have the
> reflector access, but I followed the history of that working group and you
> know went right back to the earlier see groups as well to follow the
> history of this as far back as I could.
> 14:30:37 And Yano was deeply involved in this as well, too, he in fact
> proposed one of the proposed solutions. And I don't know if you can get on
> his attention on this.
> 14:30:50 Yes, I've tried, I've opened channels with him and his main
> feedback is, it's poorly motivated. And this just general concern that when
> it's kind of in the past it's caused issues.
> 14:30:59 So you've got a lot of. You don't say you got almost everything
> covered which is good. I written up more motivation, but to me that's not
> the most important thing I know why I wanted.
> 14:31:10 And I'm just ahead of the curve, no problem, that's that's why a
> lot of us are here, ahead of the curve and that's that's okay.
> 14:31:16 All right, anything else in the group. Anybody have any questions
> and things like that on this issue
> 14:31:25 here hearing none.
> 14:31:26 Well, thank you.
> 14:31:29 Well, thank you for for letting me get the news. Yeah.
> 14:31:32 And we're going to switch over to graph fully now so would
> Andrew, or Phil would like to go first.
> 14:31:38 I don't know why we left it at.
> 14:31:41 I'm going to turn off my shares, and you have you guys go ahead
> and and and share. Can you guys do.
> 14:32:30 Okay, so you want to go first. Yeah.
> 14:32:20 Okay, what do you go ahead. Can you can you share it.
> 14:32:30 I think so.
> 14:32:18 host disabled participants screen sharing.
> 14:32:39 Just a few slides.
> 14:32:43 talking about so if everyone see my screen. So.
> 14:32:50 Yep.
> 14:32:50 And we also, as I mentioned, this was sort of I'm kind of a
> overview of the first part of the paper that, Phil.
> 14:33:01 And I've been working on the.
> 14:33:06 And I should also say its absence represents some of this is just
> represents my point of view on this and not necessarily feel so if you can,
> you know, speak up if when there's differences of opinion and, you know,
> some of what I think we're looking for
> 14:33:24 is some guidance from the group here as to, you know, what's the
> best direction to go in regards to certain things and so that we can get
> the paper wrapped up and move into LWG.
> 14:33:41 So just as a kind of reminder some of the goals, behind.
> 14:33:48 Having a generic library in general or, you know, graph library
> particular, are that you know following generic programming practice we
> want to abstract or begin with concrete efficient algorithms to generate
> generic algorithms that are parameter eyes
> 14:34:07 and can be combined with different data structures to produce a
> wide variety of useful software.
> 14:34:16 So, I think airport principles for an actual c++ standard library
> is that the
> 14:34:26 resulting libraries would support and embrace modern c++ idioms.
> 14:34:34 Rai other, you know, other things in c++ core guidelines for
> instance, that the existing standard library be embraced for graphs.
> 14:34:46 You know, I think we need to brace the scale of real world
> graphs. These days, which might be even on a single laptop, might still be
> billions millions or billions of vertices and edges, and my own view some
> stats on this is that graphs.
> 14:35:05 The important part of standardizing graphs for graph algorithms
> is the ability to traverse structures implied by relationships among data,
> not necessarily for storing data.
> 14:35:21 So some anti desert Radha, kind of come from more than 20 years
> feedback now from boost graph.
> 14:35:33 Some of the pushback we've gotten over the years is, you know,
> boost graph is very very flexible has all kinds of features for every
> imagined possible use case, but also then tends to be expert friendly on a
> particular property maps, and visitors introduced
> 14:35:53 a lot of overhead.
> 14:35:56 In both in terms of learning and use the library. You want to do
> simple things.
> 14:36:01 And on top of all that the library itself in use, particularly
> with large graphs has very poor efficiency and performance, and because
> it's so peak in many ways it's hard to diagnose what the causes of the
> performance loss are.
> 14:36:22 So, one point of view I guess I want to introduce and throw out
> for consideration by the group is kind of a following that, the c++
> standard library, which began as the standard library has, you know, rich
> set of algorithms and data structures for one
> 14:36:48 dimensional containers. And, at the original interface of that
> based on iterator is has grown, or been further generalized abstracted into
> 14:37:01 Then the library also has rich language if you like standardized
> mechanisms for defining the type requirements, again, you know, based on
> iterator is ranges.
> 14:37:13 So, has a standardized mechanisms for defining these types of
> requirements that form the interface to generic algorithms and that is now
> has language support as formerly as concepts and the micro claim is a claim
> is that the standard library, as it is
> 14:37:32 with these mechanisms and containers.
> 14:37:39 Already provides sufficient capability to support generic graph
> algorithms and data structures.
> 14:37:45 And in particular, we can define generic graph algorithms as
> range ranges and use that as requirement on a paragraph types of course
> you'd want to collect these.
> 14:37:58 These are the range of ranges is the only requirement. And so we
> want to collect those into particularly particular set of name requirements
> or concepts, and then
> 14:38:12 call those graphs or whatever, if you like.
> 14:38:17 And in many cases, compositions of standard library containers
> already meet these requirements for graph algorithms, and that if one wants
> to use graph data structure or third party structure with any kind of
> algorithms we define over graphs this way.
> 14:38:36 They can provide, they could do so, simply by providing this
> library compliant on the interface. This is how things have worked with the
> standard library.
> 14:38:45 So the.
> 14:38:56 I just jumped right into some of this abstraction process so if
> we look for instance at graph algorithms. This is a representative for
> class of algorithms.
> 14:38:59 When we call it JC list algorithms. There's a few things that the
> algorithm does over its input arguments so BFS takes a geographic gee I'm
> starting to protect us.
> 14:39:15 It first enumerate all the vertices. And then for each vertex
> sets a value in the color property map to be white, and then it puts the
> starting vertex of the queue and then pulls vertices off the queue for each
> for kicks it pulls off the q amp visit slows
> 14:39:34 vertices and specs whether they've been visited before and if
> they haven't been visited, but some on the queue says, This actually is
> abbreviated but taken directly from CSRS text.
> 14:39:49 And so again, kind of the things need to be able to do a new
> right the vertices.
> 14:39:54 Use the vertices to random access into containers or vertex
> properties, if you like, and then most important sort of the reversal idiom
> in many many graph algorithms is that given a starting vertex you, the need
> to be able to enumerate or traverse the
> 14:40:14 neighbor vertices.
> 14:40:18 And so one minimalist approach to realize this just in terms of
> your existing standard library algorithms will be something like this,
> where we enumerate the vertices by just running through an integral value
> from zero to the size of the graph, we store
> 14:40:41 the colors in STD vector. And so we set each one that we visit
> the white. We put things in the queue.
> 14:40:55 The neighbor vertices. So something like this will work with
> graphs that are defined for instance IPS as an SG vector of STD vector of
> em, or STD vector, vector, but to pull event to double or what have you and
> we can call this algorithm on compositions
> 14:41:17 of
> 14:41:20 standard library containers.
> 14:41:24 Another.
> 14:41:26 So if we, kind of, collect those things into abstract
> requirements. You know we have that an index a tasty graph.
> 14:41:36 In this case the vertex identifiers are integral graph that the
> thing that graph is actually using is what we call the Jason CMT in the
> abstract algorithm.
> 14:41:49 That in turn is a random access range, because we can index into
> it. Random Access fashion. And then if the Jason ZGMU gives us board range
> that we can iterate through to get get the neighbors.
> 14:42:05 Another principle that sort of underlying that is kind of what is
> a graph, really. And so sometimes I like to say there is no graph.
> 14:42:16 And this kind of comes from recent experiences working with large
> data sets that have graph like relationships. And so if we think about, you
> know, a graph that might represent circuit, the quantities of interest are
> was the vertices, or the note circuit
> 14:42:35 nodes.
> 14:42:37 And then the circuit elements between vertices, we can convert
> that into a graph suitable for doing breakfast search whatever if you like
> by first turning the data which could be strings or whatever.
> 14:42:57 The point is that vertices have
> 14:43:01 that vertices, have some kind of identifier edges, our
> relationships between things in the vertex set, which might also properties.
> 14:43:12 We can create with library functionality create an index list and
> then create a Jason, see List, with those indices, and the ideas that you
> know general user shouldn't be trying to build this and they don't need to.
> 14:43:29 And this, the adjacent the list really represents structure, not
> actual data bomb if we look, there's kind of one important.
> 14:43:41 Additional aspect in graph algorithms.
> 14:43:45 Speaking of data, which we can see and other algorithms like like
> Dykstra that is that we might have properties associated with edges. In
> addition to properties associated with vertices.
> 14:43:56 Typically, and I think this is almost universally true.
> 14:44:02 When we need a property of a vertex, it's actually, or I'm sorry
> property of an edge. We need that at the same time as we're accessing the
> edge. So, basically we can store the property information about an edge
> with the edge in some way or you can store
> 14:44:24 an index into the corresponding property, again with that edge so
> when my child have an algorithm for extra that looks like this, where.
> 14:44:39 Here we have a vertex property map distances.
> 14:44:44 and then an edge.
> 14:44:48 Property map or container let's say your range of that we index
> into with the edge identifier that sword with the edge.
> 14:44:59 So the requirements that I guess for this type of graph are that
> are you know basically the same as we had for the previous type of graph,
> but the difference is that the value type, now that we get when we are
> traversing neighbors is twofold.
> 14:45:22 The first is a vertex identifier the neighbor neighbors were tax
> ID, and the second is an identifier for the edge, and what that is is
> context dependent so it could be the actual property, it could be another
> identifier into the edge.
> 14:45:40 So, In the case of storing indices with edges.
> 14:45:44 We have our next address would look like this, and we would store
> notionally in the library would store.
> 14:45:52 Again the neighbor vertices, as well as the edge indexes us more.
> 14:46:04 Maybe more generalized approach would be to actually store the
> 14:46:13 kind of abstract whether we're actually storing weights on the
> edges or storing indices into another container on the edges by just
> passing away function.
> 14:46:27 So, here again we win iterating through the graph, we have an
> identifier weights returns the prop weights of that identifier returns,
> what it is and that subsumes both storing indices or storing actual
> properties on the edges.
> 14:46:44 And there's different reasons to want to do one or the other,
> storing the properties on the edges does give you some efficiency in terms
> of accessing that cash behavior and so forth.
> 14:46:58 But, you know, these these might be much larger than an index
> value would be and so you might actually want to just refer back into the
> original Angeles to get the properties.
> 14:47:12 So one important thing also in in graphs and thinking about them
> as standard library components is we, I think we need to be able to iterate
> through them or traverse them with idioms that are used these days in c++
> so we saw before.
> 14:47:35 You know we could iterate through the graph just with indices
> from zero to the size of the graph. We also might want to use
> 14:47:48 range based fours, to iterate through the graph or iterate
> through the neighborhood. The problem with just the plain
> 14:47:58 range base for is that we don't actually have the source vertex
> 14:48:04 We're doing that but we have an adapter could provide an adapter
> around the graph, so that if you actually need that index you can have that
> in the range base for.
> 14:48:20 Similarly, we would want to use standard library.
> 14:48:26 Algorithms on ranges, in particular, maybe standard for each, and
> as different ways of using that.
> 14:48:34 One important use case in using yesterday for eight for each is
> that we can use.
> 14:48:41 Execution policies to do this do these things in parallel. And I
> think it's important for efficient graph algorithms that we be able to
> support this.
> 14:48:55 In the BTL.
> 14:48:57 Some of these are they had had similar concepts so that a graph
> was basically something that she had two associated types of protection
> scripture and and it's descriptor.
> 14:49:19 Then there was a concept that just for the first step that we had
> in with research for new breeding vertices. So there's a concept for Texas
> graph. So the vertices function returned to range of our text descriptors,
> and number two C's return to the size
> 14:49:26 of that range.
> 14:49:26 Then there were two types of graphs for
> 14:49:32 doing visiting neighbors one was Jason vertices, where the Jason
> vertices returned a range of our text descriptors corresponding the
> neighbors. And then there was an incidence graph that had four functions
> out edges about degree.
> 14:49:47 And then sort of the source function which could take an edge
> descriptor from the source vertex and target that takes a ninja script or
> for its target.
> 14:49:58 So, an example using this kind of interface would look like this.
> 14:50:04 Again, we don't. this isn't the full Biggio with
> 14:50:11 properly maps and all that and still just use a random access
> range for instance, but we can get the number of vertices is number two
> seasons the graph can get the neighbors.
> 14:50:23 With the vertices of gigas arrange get it right over for the
> 14:50:29 And then we can get the adjacent neighbors, and iterate through,
> through those without function,
> 14:50:42 go quick through. There's a couple of, there's one other content
> against reversible and that has to do with edge lyst algorithms, where you
> actually just might want to traverse the edges that are contained in the
> graph, rather than in just one by one
> 14:50:56 rather than traversing them in in the order, you get in.
> 14:51:01 By visiting neighbors, for instance, so you don't need that
> particular organization.
> 14:51:08 And there's an example of customers algorithm for instance, how
> to do that.
> 14:51:14 And so then in vgl, there was a final concept of an analyst graph
> that provided the functionality of edges to give you a range of the edges
> now managers and then source and target to get the source vertex and target
> vertex from an edge.
> 14:51:33 Thing is, we've also been looking at his range adapters. So it's,
> again, in this thinking that graphs are really good ranges of ranges, very
> powerful part of the ranges library is this notion of adapters.
> 14:51:49 And when I guess.
> 14:51:56 And that, in graph, sometimes when people talk about graph, Coco
> algorithms, they really just mean reversal patterns. So breath research in
> depth research aren't really algorithms per se, what you want to do with
> 14:52:10 Depends.
> 14:52:12 And you just want to diverse and breathless source of passionate
> and do something and so in BTL.
> 14:52:18 These traverse the patterns were adapted with visitors, which
> again, we're very heavy weight and confusing mechanism.
> 14:52:28 So, what we're proposing instead is range adapters that present
> range of vertices, or edges in order. This particular algorithm to traverse
> them. So an example for instance of the use of this and this can also shows
> you know the use of algorithms.
> 14:52:47 Just over a container of containers.
> 14:52:49 So you could, you know, given a list of CO stars in different
> 14:52:57 And, you know, an array of movie stars.
> 14:53:01 We can nationalize the Jason's team structure go with that.
> 14:53:06 And then we can just reverse that graph of CO stars in BFS order,
> and given each edge, and this would be if I said range to get the judges
> and visited.
> 14:53:22 We can set the Bacon number for that each vertex has visited. And
> then we can go through all the actors and report with their bacon numbers
> 14:53:38 So other important utility functions are basically for
> constructing graphs that before you know there's really no reason to build
> and Jason structure oneself.
> 14:53:49 So, given sets of vertices and pairs of vertices or property
> Associated Press vertices we can easily make those adjustments the
> 14:54:01 We can also make the transfer of the JC structure, so you might
> want the, you know, the edges in one direction versus edges in the other
> 14:54:13 And then, so one particular type.
> 14:54:31 Then we think it's important to include in this sort of adjacent
> to structure is a compressed graph, type something got compressed bars row.
> 14:54:28 It isn't actually a composition of containers like we were
> looking at before, but can provide that same range of ranges interface, and
> this is highly efficient, it's in benchmarks we've done it's using this
> instead of saying vector vectors is about 40% 40%
> 14:54:46 faster.
> 14:54:48 And then finally, one thing to, we like to maybe get some
> feedback on is the importance of by apartheid graphs. And the reason I
> mentioned this isn't is more, because they kind of come up naturally and
> even the simplest example of of the IMDb doing Kevin
> 14:55:11 Bacon numbers, and that really what you're given as entities are
> movies and actors and the association, that's given for instance by IMDb is
> just movies and actors have relationships, so your edge list is really
> between movies and actors, and that really
> 14:55:30 gives you two different Jason t lists that don't quite meet the
> requirements we have before. Because there's a different card and out, you
> know, the things that are being stored in the Jason's the list index into
> the other or Jason to listen to kind of
> 14:55:45 cross reference each other.
> 14:55:49 reference each other. And then that one kind of given that type
> of decency list. It's easy to provide a library function that would create
> the actor actor movie movie.
> 14:56:02 Actually actual graph.
> 14:56:05 So there's a lot of options and this is I think will be one
> difficulty in thinking about a graph standard graph libraries what
> algorithms to actually include, I think it's because there's so many
> different algorithms and so many variants of them.
> 14:56:21 I think we need to make it easy to build those.
> 14:56:25 So, the community can share and build on them, rather than
> standardizing very many of them.
> 14:56:34 However, one building block that has emerged, and this might be
> 14:56:43 a subject of untold talk or. I know, Scott McMillan who's been a
> proponent of this will be talking about graft laws at CPP con. The idea is
> basically to generalize there certain linear algebra operations, based on
> the correspondence pretty graphs and
> 14:57:00 sparse matrices and kind of the core operations, there are
> generalized sparse matrix by density vector product and a generalized
> sparse matrix by sparse matrix product.
> 14:57:11 Given those one can compose those operations and create sets of
> algorithms like some of the ones that might, one might see in the water so
> this is another set of building blocks, one could imagine.
> 14:57:27 Instead of just the traversing and so forth, we talked about so
> far, so that I can turn it over to
> 14:57:36 feel.
> 14:57:39 I can stop sharing and.
> 14:57:45 Yeah.
> 14:57:45 Yeah. Is there a sauce about at this any feedback.
> 14:57:49 Before I started, was it was it any, any policy wanted to, to
> catch you out of the slides was at the operations or anything like that
> that you wanted to highlight.
> 14:58:01 I'm just trying to figure out
> 14:58:05 if you were trying to highlight the, the need for certain
> 14:58:13 Yeah,
> 14:58:16 maybe.
> 14:58:27 Maybe it's some sort, some sense ease.
> 14:58:42 And, you know, some of the design then once the concepts, I
> guess, are these requirements operations are collected is, you know, what
> are the
> 14:58:55 subsequent.
> 14:59:01 What's the subsequent syntax for realizing these, so one approach
> and and you know this was kind of this minimalist approach.
> 14:59:13 We just use range, and you know container syntax to access things
> that might not be, you know, little sufficient or might not be desirable by
> the group or the community, but I think what's important are these.
> 14:59:31 And I think, well, we're bill will jump off from is, you know
> that we have these certain requirements that the output of what algorithms
> 14:59:56 And, in fact, the the implementation that's there would agree
> with you.
> 15:00:02 I think one of the things.
> 15:00:05 So Andrew and I come at this from different perspectives so he's
> really been in the algorithms a lot.
> 15:00:10 I've been on products that have a graph embedded in it.
> 15:00:14 And so those brings unique challenges from both of those.
> 15:00:20 So I think both are valid and both are interesting.
> 15:00:23 I think, in, in this expression of stuff I really like the
> sickness, and brevity of being able to express the buttons there.
> 15:00:32 And I've always looked at this and is, and.
> 15:00:36 And the same.
> 15:00:38 Can we get there.
> 15:00:41 To do that, and the other thing that I've looked at the the thing
> that's going there's there's an emphasis on index looked up.
> 15:00:50 And when I look at the STL, there's an emphasis on using iterator
> as the core element here, and. And so this is really great because I think
> we're getting a lot closer than we used to me.
> 15:01:07 And I'll show that in a little bit.
> 15:01:10 But how can we make this most expressive and also.
> 15:01:15 First of all, so that, for instance, we can adapt existing graphs
> out in the wild, to the algorithms that are in the standard, for instance,
> because that's always been a strength of the STL is that somebody that
> writes this container over here can use
> 15:01:36 an algorithm that's developed somewhere else.
> 15:01:40 And so,
> 15:01:44 there's just kind of my some general observations, I don't think
> that we're that far off in a lot of ways. Okay, and what what do you think
> Andrew do you think,
> 15:02:00 Well I think that's right i mean so they're in one of the, I
> guess, preface slides I mentioned that
> 15:02:12 we abstract from concrete efficient algorithms to obtain generic
> algorithms. And the other part of that is the algorithms that can be
> combined with different data representations.
> 15:02:25 So, you know, making sure the you know the the concept
> definitions are the main type requirements can encompass those different
> data representations is is kind of important part.
> 15:02:39 And so, in some sense, it also mentioned. He was kind of coming
> at this from the point of view of the different data representations. And,
> and I was trying to start with, you know, the concrete efficient algorithms.
> 15:02:53 And also, you know, in some ways I've been, you know,
> deliberately sticking out maybe an extreme approach in that I wanted to
> 15:03:05 You know, getting into the super Swiss Army Knife situation of
> the, of the moose graph show show you each come from it from a slightly
> different points of views one is from product ization the other ones from
> 15:03:17 And you are trying to find some unification there. And maybe what
> we need to do is see what Phyllis is doing now and see if it's getting
> closer and closer to it to some midpoint, so that it's not particularly
> leaning to one or the other.
> 15:03:31 I mean, if it comes to it, we might have, what I'm hearing and I
> don't know if that's the case that we might have to at some point.
> 15:03:41 And up have having two different to two proposals, but we wanted
> to try to avoid that if we can.
> 15:03:47 That's what linear algebra has has has, has become but, but, but
> I'm still I'm still hopeful that we can still avoid that, but some sort of
> unification that.
> 15:03:55 Yeah, I think so on as Phil mentioned I think we're heading that
> direction, and he has had his hand up. also I guess. Yeah, go ahead. Yes.
> 15:04:09 Ok I can hear you. I can't hear you. Yes. Are you are you double
> muted perhaps I'm double muted, for some reason I don't know why.
> 15:04:19 So I think the first of all, it seems that, avoiding the booth
> graph library abstraction layers that have been piled on top of each other
> 15:04:37 Seems like a seems like a good idea. I share the sentiment that
> exclusively relying on indices might require for example, what you showed
> in your slides might require that there is some pre processing of the
> incoming data structure into some index based
> 15:04:58 arrays or something like that.
> 15:05:00 And that not everybody might want to do that, just to run a graph
> algorithm over something that has all the information present, but just in
> a slightly different, different way.
> 15:05:15 That said, it seems the abstraction of having a range of ranges.
> At the core of most of the input requirements is actually a fairly powerful
> abstraction and that means you should be able to map, most of your data
> structures that are suitable to run graph
> 15:05:36 algorithms on in the first place, you should be able to map that
> to the range of ranges abstraction which might mean to actually, you know,
> 15:05:55 Gosh, view on your data structure. And actually, a to level up
> because you need a range of ranges.
> 15:05:53 Yeah, that's, I mean, if you look at some of the standard library
> views that come with a lot of Jewish method its writers and sentinels and
> crap that that might be slightly interesting to do, but at least you know
> there are literatures fillers looking
> 15:07:20 Okay.
> 15:07:35 Okay. Hopefully everyone can see what I have here.
> 15:07:23 I'm just, it's been a while since we've looked this up but just
> to remind everyone, I have, you know, played, we're seeing your entire
> screen, and the actual text you want to show is taking up about one third
> of the screen.
> 15:07:36 It would be very helpful to fix that by either resizing your
> window and and or just sharing the window you want to you want to share
> with us.
> 15:07:49 Thank you for
> 15:07:55 this better.
> 15:08:05 It's, it's slightly better Yeah, yeah, no, it's getting even
> better. Okay.
> 15:08:09 Okay, so, you know, there is an abstraction for, say, Dextre,
> which is one of the things that Andrew was sharing and so there's the idea
> of having a function called a distance function its weight function.
> 15:08:27 It provides the same feature. And so I think,
> 15:08:32 you know, I, we haven't been looking at that as much here in the
> recent reviews, because I think it's in large part, Pretty good stab at it.
> 15:08:44 And I think, in all of the reviews that we've done it.
> 15:08:50 There hasn't been any disagreement with any of this.
> 15:08:54 Okay, so just, just as a reminder.
> 15:08:59 And so I think a lot of the, this has been trying to figure out
> the right abstractions for representing the data models.
> 15:09:08 So, And that's, and it's dealing with the concepts and the types.
> And what does that mean and giving that abstraction right and that's a lot
> of what I'm going to be talking about today.
> 15:09:21 And also wanting to do a little bit of a demo of how it would be
> 15:09:27 And I think you'll see how it's, it's coming closer to what
> Andrew was just shown.
> 15:09:33 It's not completely there yet, but at least I think we'll be able
> to see where that's out.
> 15:09:41 When we were reviewed this last, there was a pretty strong
> recommendation to reduce the size of the paper. So, at the time it was 70
> pages. And so now, and then we're recommendation of making changes so I've
> brought those in as best I can.
> 15:10:02 We're so now we're down to about 46 pages.
> 15:10:07 Still more than I think people would like, what is definitely
> improvement from this, I've been doing a lot of work in how types are
> defined, how the type aliases are defined, how the concepts are defined.
> 15:10:25 And, and so I can say that the graph traits structure is now gone.
> 15:10:30 All of the function prototypes are all gone. And the concepts are
> simpler now.
> 15:10:37 And so, the.
> 15:10:43 I've removed those things have removed the mutable concepts for
> adding and removing things I've removed the inward and outward outward
> ranges, because we're just not referencing them in any of the algorithms,
> even though I believe that's important element
> 15:11:02 to describe graphs in it. I can't justify it. I've also removed
> that ordered parent I know repair that were there, so that's all
> 15:11:13 And so, Let me put that on this on pause.
> 15:11:20 And I just want to go to the demo.
> 15:11:31 See if I can find the right.
> 15:12:13 You're not sharing anything, the smell and I'm trying to find it.
> I have too many windows open.
> 15:12:27 Try with less main memory than your program is a new computer
> crashes if you have too many windows open.
> 15:12:35 All right, there we go.
> 15:12:49 Can you see that okay
> 15:12:49 should be showing a void demo. Yes.
> 15:12:46 Alright. So, If we start with us.
> 15:12:52 I'm using Andrews example of a vector for lips.
> 15:13:00 And in this case, I have a vertex key.
> 15:13:05 And in this case, it's just the target vertex it's what it is.
> And in this case the edge is just that target vertex. And I have a vector
> of a forward list.
> 15:13:16 Okay.
> 15:13:18 And then I can define my graph.
> 15:13:29 The contents aren't that important. Really, we've got four
> vertices, with five edges. In this case, and then we can if we want to do
> that, we want to live through that.
> 15:13:43 We can then create
> 15:13:46 some
> 15:13:51 loops.
> 15:13:52 Now what I've done is I've all of the functions that are in there
> are now customization point objects CPS.
> 15:14:01 And so, in this I've been able to define some very reasonable
> 15:14:09 So there's no special behind the scenes things I'm doing for this
> 15:14:32 Worse, you have a problem with us. You know I went through this.
> 15:14:50 Well I guess I can't run it, but you get the idea. It ran, just
> an hour ago, without any problem.
> 15:14:58 You can see the vertices that I'm getting the vertices, out of
> the graph.
> 15:15:03 And in this case, it's just saying, I can take this off right
> 15:15:12 now. give me the same results.
> 15:15:16 Even though I can't prove it with pilot.
> 15:15:20 So in this case it's just saying if it's a range.
> 15:15:31 I'm.
> 15:15:50 Suzanne is asking what are the five, five inches.
> 15:15:55 Oh, I see. It's good because I help.
> 15:16:05 So the edges are 021 or two little ones over 2122123, and three
> to zero.
> 15:16:19 Right
> 15:16:19 now I can take this back off and I can show you that it's the
> same exact thing.
> 15:16:24 So these are customization point objects. So there's a default
> behavior but then you if you've got your own graph it, you can override
> this for your own situation.
> 15:16:37 And then the same thing for the address and these are the same
> functions that I've been showing for over a year.
> 15:16:44 And in this case, we're just counting what's there.
> 15:16:48 Right.
> 15:16:50 And again with the edges. It's just a little simple rapper.
> 15:16:58 To do that, and so it can do that by saying, Well, if it's like
> on the vertices if it's a random accessing range.
> 15:17:08 Then I'll just give you.
> 15:17:19 I'll just treat it as a range. As the vertices.
> 15:17:14 Okay.
> 15:17:18 Now the question then is, does is it just going to work without
> any problem, and almost, because in this case.
> 15:17:29 If I want to get a target key. There will be a problem.
> 15:17:35 Because I don't know what this is, it's a property on on the
> edge. And so how do we work around that.
> 15:17:45 Well, we can define a
> 15:17:52 function.
> 15:17:59 We really want to do is just say this is
> 15:18:08 our duty to get that Ed twitches, are these values here.
> 15:18:14 Well that doesn't quite work, what we really have to do
> 15:18:23 is put in the stood namespace.
> 15:18:28 And the reason that we're having to do that, is that it's using
> our argument dependent look up to, so it's looking, and that's where the
> vector lives is in stood namespace.
> 15:18:40 So this is not a good example, don't do this at home, don't use
> it in production code that you give us an idea of what how this works.
> 15:18:49 So anything that works, that
> 15:18:53 is a property. Within the graph is going to require
> customization. That's the one thing for sure that you need. There's also a
> source key, or I'll bring this up.
> 15:19:12 There are the four functions that really need customization.
> 15:19:16 If you need them.
> 15:19:19 If you, if you want to source vertex on edge, you would have to
> define that and store it.
> 15:19:26 The other three are really optional.
> 15:19:30 It really depends on what algorithms you want to use and what how
> you're storing things on on your graph.
> 15:19:38 But everything else I think is pretty reasonable definitions and
> later on when we look at the concepts I've put in there, what those, those
> default. The default behavior is.
> 15:19:52 This is just a start, because also within the customization
> 15:20:00 skip down here.
> 15:20:02 Um, there's different ways of representing that.
> 15:20:13 If we look at the vertices,
> 15:20:20 there's three ways of of executing the vertices one is the
> default which we just looked at.
> 15:20:29 And if we.
> 15:20:43 I'm gonna
> 15:20:50 I'm gonna do it this way if I have my own special graph, I can
> create a member function called vertices that takes a graph parameter, and
> it will look for that first.
> 15:21:03 If it doesn't find that
> 15:21:07 it will look for
> 15:21:12 something that looks like this
> 15:21:15 is a free function that takes a graph as a parameter.
> 15:21:21 And that actually. Is that right, yeah. Anyway,
> 15:21:29 and if you can't find it.
> 15:21:40 It will finally look.
> 15:21:44 And it will do a default implementation that looks like this
> it's, there's not actually a function does it as part of the Cpl.
> 15:21:54 So Tim the namespace stood name, said graph namespace.
> 15:22:01 So you can see there's a hierarchy here, that allows for graph
> authors to override the standard functionality so that we now have a
> uniform way of getting to these things that we're interested in, in the
> 15:22:19 One of the things that.
> 15:22:24 So, with what Andrew presented, you know he was addressing the
> additional things beyond the incident scraps but then how do you get that
> the urgency graphs are there Jason seedless arrangements excuse me
> 15:22:41 say this all the right way there's the Tracy Ranger this over the
> edge list ranges.
> 15:22:47 And so there needs to be ways of doing that.
> 15:22:50 Alright, so DNS has his hand up. Okay, go ahead.
> 15:22:56 So what you're showing here is what I would expect. The standard
> way how ranges related customization point objects work, you first try the
> member function then he tried he.
> 15:23:19 And then he tried the
> 15:23:13 function, and then you fall back to some, some plausible
> plausible other thing, the OD, the difference would be that in Andrews
> approach, instead of talking about making vertices then similar
> customization point objects, you would instead.
> 15:23:39 Define a view on your graph. And that, and you would then
> possibly customize the begin and end customization point objects on that
> view if you really must, but usually you don't.
> 15:23:54 And then that you will just get you the vertices from using
> whatever technology or or means as necessary to inspect your craft to get
> those lists, and possibly defining specialized results and all that kind of
> 15:24:12 Okay.
> 15:24:14 I'm hearing what you're saying I'm not as familiar with the
> fields. So that's a note to look for me to understand that better.
> 15:24:22 Yeah, so, because what what is returned from this vertices
> faction. What do you anticipate is being returned from there. From it's a
> 15:24:32 It's a range, right. So,
> 15:24:37 right. And
> 15:24:43 why would you scroll up a little bit, you see your edges visited
> thing, which is very very close to permitting arrangements for loop.
> 15:24:53 Because the begin customization parent object business is
> actually what you would get from A.
> 15:25:02 is more or less what you would get from a range based for loop as
> 15:25:06 Yes, and I'm one of the. So let's look at that.
> 15:25:25 And we could do.
> 15:25:40 this reason I was doing.
> 15:25:43 Copy faces because I've had somebody from there's a lot.
> 15:25:50 I think right now is not very far from what Andrew has had on the
> slides right. Exactly. And that's a really good point.
> 15:26:00 Um, and I've seen that.
> 15:26:04 But now you see there's a difference because there's a, this is a
> reference. Right. should be a reference.
> 15:26:16 And, and so can we go farther to achieve Anders goal.
> 15:26:24 And that's part of the challenge here. And that's kind of the
> next step is how far can I go.
> 15:26:35 You really need the iterator for your further explorations, or is
> it enough to get to the values, I mean, the shortcut Andrew took for that
> was, I have editor indeed indices all around them, don't care for the
> 15:26:54 So, say that again.
> 15:26:57 The bottom range based for loop treats in values, your loops
> above deal in integrators. Correct. The you is an iterator above, it's a
> value below, and pretty presumably.
> 15:27:15 Yeah, so, and Andrew gets away with dealing and values because
> everything is an index, an integer index. Right.
> 15:27:25 Right. And so at this point now UV is actually an,
> 15:27:32 an index value. That's the target key.
> 15:27:36 Right.
> 15:27:37 And so now, at this point, I'm, I'm having to deal with an index
> to find the target value.
> 15:27:46 And so there's kind of this mismatch between dealing with
> integrators and index says that, that where I'm finding it difficult.
> 15:27:59 And I haven't put as much time into it.
> 15:28:02 Okay, so, just from a from a beauty perspective, doing arrange
> base for loop to run over the vertices is certainly the preferred way of
> doing it.
> 15:28:14 Well I think it's also important for, well, to be able to use STD
> for each, so that it can be done in parallel.
> 15:28:23 Yes.
> 15:28:28 Yes.
> 15:28:30 Yeah.
> 15:28:32 So, maybe the next step in that area but I don't want to
> interrupt your presentation for too long. The next step in that area would
> be to investigate what you can do to make that match was for work, and
> actually the, and actually was this level of abstraction
> 15:28:50 and the concept of us, it's not.
> 15:28:53 I mean, the you in there is not really required to be.
> 15:29:00 I mean, to be
> 15:29:05 a,
> 15:29:08 an index value of sorts or something like that, it could be some
> more some more complicated data structure of that actually gives you what
> you want.
> 15:29:17 Now, Andrew was also doing things like this where he was
> returning to a tool that had multiple values. Yes, sure. How are you
> feeling about that.
> 15:29:34 I don't. I personally.
> 15:29:38 I don't think that's a problem, I think it's natural for. If you
> think and abuse, and abuse, fear, it's natural that you will not
> necessarily have iterate over scalar values but might iterate over more
> complicated values such as couples, or ranges in
> 15:29:59 this case.
> 15:30:01 So that seems seems plausible.
> 15:30:06 So, yeah, why not.
> 15:30:13 Okay.
> 15:30:11 I think that opens up the possibilities for doing that. Okay.
> 15:30:18 Well, we'll show examples for algorithms that actually need that
> feature because they don't not only need to iterate over the values but
> they also need the index of the source, I think, which wasn't otherwise
> 15:30:31 Right.
> 15:30:33 Right. And I think, essentially do is you.
> 15:30:39 We actually have a views colon colon enumerate that actually
> takes a view of our range of values and ads, as an integer index number as
> a couple, and iterate essentially over a pair of index number plus the
> value the original view would have given you.
> 15:31:01 And that's exactly what Andrew did with his key thing, except
> that we have already made you with that gives that for you from the
> standard library know invention necessary.
> 15:31:13 So, what's your thoughts on the center.
> 15:31:20 Well I mean I, as I had in the slides I think having.
> 15:31:27 Being able to range based for being able to go quickly, you know,
> be able to do things with in parallel, is important.
> 15:31:37 So, you know, using kind of values or references rather than
> 15:31:44 generators.
> 15:31:46 I think is preferable. And
> 15:31:49 so the slower for lupus of more attractive thing.
> 15:31:54 Although I would probably still pass in you rather than ampersand
> you edges.
> 15:32:02 Yeah, I remember, of course.
> 15:32:09 Okay.
> 15:32:12 Okay. Now this really good, I like this.
> 15:32:19 Okay, that's, that's really all for the demo I want to go back
> 15:32:25 to the paper.
> 15:32:33 And I guess what it well fields.
> 15:32:36 Switching back. One quick comment I didn't list on the
> requirements on the slides but there are complexity requirements as well on
> some of these things for you know so that graph algorithms will realize
> their stated computational complexity.
> 15:32:53 So, looking up a neighborhood or whatever, for instance, has to
> be constant time.
> 15:32:58 Random Access.
> 15:33:02 Well, I think in terms of that, then that's how it's designed,
> but if you've gotten something that would work that is less than that, it
> might be just as attractive to use it.
> 15:33:17 Rather than having to create a whole new data structure just to
> do the same thing.
> 15:33:22 As long as you properly formulate the resulting complexities of
> the algorithms that you apply to your sub optimal data structures
> appropriately so that you don't promise complexities that, you know, don't
> 15:33:42 And of course you can always claim that some kind of look up is
> sort of constant because usually we would formulate complexities in terms
> of number of lockups the graph data structure or whatever.
> 15:33:56 Well, if you look up itself a slow them. Tough luck.
> 15:34:02 Right.
> 15:34:03 So now when we switch over here, look at the the ranges, the
> types and the concepts that are there. So, we've been looking at what we'll
> see now is, it's gotten a lot shorter.
> 15:34:25 We have one vertex range, and three edge ranges, and I've thrown
> in the iterator types as well as convenience, just because I was finding is
> using them quite a bit.
> 15:34:40 So, The difference here is now is dependent these types are
> dependent on say the vertices function, whatever returns benefit of this is
> now we don't need graph traits.
> 15:34:53 And we can rely on the type returned by the function.
> 15:34:57 We also don't need separate conquest versions of all of these,
> which was a goal at hand. So this is all working very nicely.
> 15:35:07 It's very succinct. In terms of the ranges to represent what
> we've been talking about.
> 15:35:15 So all of these were there before I've just taken things out.
> 15:35:20 The other things, the other types that we're talking about are
> the value types. There's an optional graph vertex and edge value type
> defined by the user.
> 15:35:29 There's also a key type vertex key type. And then, just the
> vertex type itself.
> 15:35:38 And then there's niche type and the edge key type
> 15:35:50 is the grace values, sorry to interrupt is the grace value
> function supposed to do something other than returned.
> 15:35:58 Other than using the return type or is that actually returning
> some sort of value.
> 15:36:04 Well, it's going to return a reference or value.
> 15:36:10 Sure, but but what graph value of G doing.
> 15:36:18 I don't know what kind of value would return on the entire graph.
> So I'm asking. Well, I mean it's just so we have three different types
> there's a graph engine vertex right.
> 15:36:28 And sometimes you want user defined values on these objects.
> 15:36:33 Right. And so, for the context in your context of what you're
> 15:36:38 And this is from my experience in in working with graphs in a
> domain area.
> 15:36:47 You're not going to find a graph value in.
> 15:36:53 In the algorithms, you might find an edge value.
> 15:36:59 And.
> 15:37:01 Yes.
> 15:37:01 Right. And so it's just returning a value on the edge.
> 15:37:08 Yes, this one. Sure, but what does graph value do Is it is it
> supposed to return one value or a tablet maybe that is attached to the
> entire graph somehow yes to both.
> 15:37:24 Okay. Okay.
> 15:37:25 Fine. Seems unrelated to the graph algorithms were talking about
> that fight.
> 15:37:30 Okay.
> 15:37:32 Okay.
> 15:37:33 Okay. Yeah. Okay.
> 15:37:38 Any other comments here.
> 15:37:45 One thing that's because of the way the types of defined, it's no
> longer quite as explicit.
> 15:37:57 So when we get in, we have some basic concepts that we have to
> define and so I've created this vertex iterator. So what is a vertex
> iterator is something that you can get a key from.
> 15:38:10 There's a vertex range.
> 15:38:14 That is a forward range, at minimum, in society size range, and
> it has vertex iterator so that it has vertex key that you can use.
> 15:38:26 It has the vertices function, and a fine vertex function, which
> could just be an array look up.
> 15:38:36 Again, you can start to see where the default behaviors that I've
> defined here for this.
> 15:38:48 There's an edge iterator,
> 15:38:53 which is a forward iterator.
> 15:38:57 It has a target, and that target key function.
> 15:39:02 And so its target key is user override required.
> 15:39:09 There's a source edge iterator Andrew was pointing out that, and
> a lot of things you don't need to know what the source key is, are you
> don't have to store it.
> 15:39:21 And so, let's pull that out as a separate concept so that's what
> I've done.
> 15:39:25 There's the source and the source key,
> 15:39:29 there's this thing called the other vertex.
> 15:39:34 that says in when you're an undirected graph.
> 15:39:41 There's no order to the vertices on an edge, and so you need to
> know where you've come from that source or source key, And that's what
> that's for.
> 15:39:54 When you have. And then there's the edgy.
> 15:40:01 There's the edge range concept, which has a Ford range, and with
> an edge iterator.
> 15:40:12 And then the source to edge range, go with the source edge
> 15:40:18 So once we have those now we can start to describe what these
> graphs are a vertex list graph is a vertex range. I think under has a
> different a little different idea of what that might be.
> 15:40:31 That's just focused on the keys.
> 15:40:34 There's an incidence graph, which is the vertex range. the edge
> range, and it has an address function.
> 15:40:46 Now, in a sense, there's some duplication here because the edge
> range calls the edges function.
> 15:40:53 And so, in a sense, I don't really have to define that. But I
> think it's helpful to be clear on the design.
> 15:41:02 So, once we see those, the interesting see graph is the same
> exact thing. The only difference is that range that we're using the
> explicit range.
> 15:41:12 And it's matching function.
> 15:41:15 Same thing with the edge of this graph and the edge range, and
> the edges.
> 15:41:25 There's finally an adjacent to the matrix and it's just false.
> There's some algorithms that can get benefit, knowing that it's working on
> a matrix. and one of the tears that way.
> 15:41:37 And so, this is a way to tag your graph, of being initiation two
> 15:41:47 There's some contains concepts which are contains vertex contains
> 15:41:54 It can be useful to have that kind of function available.
> 15:42:00 Especially when you think of an ACC matrix, it can be a constant
> time function.
> 15:42:12 There's the find edge concepts, which is just one per edge type
> that is just defining a couple functions there's a fine vertex edge.
> 15:42:28 Based on iterating hours are based on keys.
> 15:42:34 The same exact thing for the other ranges.
> 15:42:45 There's the path and cycle concepts, those haven't changed from
> the past, that's just a less to pass or a list of integrators.
> 15:43:07 Um, there are some functions that are not in concepts and I've
> covered most of these there's the graph value of vertex value and adds
> 15:43:06 And the reason I don't have concepts for those is because really
> the way the algorithms have been designed is that they'll accept the
> 15:43:14 Now they may refer to say an edge value, and that's fine, but
> they're not the algorithms themselves are not dependent on the presence of
> the function.
> 15:43:47 There's another edition which is the degree function is a
> convenience function that would just return the size of, say, the, the
> incidence edges or the adjacent see efforts.
> 15:43:47 It all depends on whatever is appropriate.
> 15:43:53 Again, these are all customization point objects that can be
> 15:44:01 over coverage.
> 15:44:04 And so there's a section on the customization point on FX we've
> really covered all of the content in here with the demo.
> 15:44:13 There's another point, and you know we've talked about the
> agency, less than the edge list.
> 15:44:22 There's no, it would be very helpful to have adapters that would
> take the vertex range, and the incident range and create
> 15:44:36 ranges for these things. The straightforward to do, but I'm
> trying to keep this simple and keep the pitch count down.
> 15:44:52 And that's, that's really all the changes, haven't touched the
> rest of the paper, the algorithms BFS DFS for me says is.
> 15:45:01 And there we go.
> 15:45:04 comments.
> 15:45:14 I guess the only thing I might have a.
> 15:45:17 It sounded like you wanted, you were trying to make the changes
> Andrew was looking for but you just wasn't sure how to do it, especially
> using views. Do you think you might have something that that can work now
> with Jen's input for youngsters his hands
> 15:45:32 up next anyway so maybe he's answering that. Go ahead. Yes.
> 15:45:37 I cannot certainly.
> 15:45:40 I certainly have no opinion on whether Filton do something with
> my input or not, or whether my input is helpful.
> 15:45:49 But, yeah, so I I just feel that the current Phil's current
> design is closer to booth graph in terms of doing a calling all kinds of
> mapping functions and in this case customization point objects and all that.
> 15:46:10 In the middle of it that
> 15:46:15 that Andrew was explicitly avoiding because it felt to me that he
> learned from what was crafted, and that didn't actually wasn't very
> efficient and at some point that it was just some abstraction penalty that
> couldn't be optimized the way.
> 15:46:36 So I the the flip side is of course that Andrew gave up on on
> arbitrary data structures and just said, there's integer indices all
> around. And that's what you deal with, and there's helper functions to, to
> actually create those ensure indices lists and
> 15:46:55 from, from other data structures that you may have. And you keep
> going from there.
> 15:47:03 So, I'm.
> 15:47:07 I'm.
> 15:47:09 I'm curious to see whether there's a middle ground here, that
> might abstract away from the integer indices.
> 15:47:16 On one hand, but does not have the, the performance penalties
> that apparently bootstrap had or has it at least some use cases, so.
> 15:47:31 Well,
> 15:47:35 I'm not sure that I see where there would be a performance
> penalties in the things that I've done.
> 15:47:44 But maybe I'm wrong.
> 15:47:49 So I'm not sure, but I would like to hear what other.
> 15:47:54 So far, you haven't. You haven't accumulated enough layers of
> abstraction that would get you close to bootstrap library.
> 15:48:07 Okay, was Lucas his hand up, and then I want to see what he's
> what he thinks, how would how you would evaluate it, go ahead.
> 15:48:15 Thanks, Mike. I just had some comments that really expect any
> reactions. Yes, but I feel like it's dangerous to do any of this
> particularly for graphs, in the absence of a really
> 15:48:28 deep analysis of parallelism parallel applications parallel
> algorithms on these graphs and how that might work, particularly in sort of
> where we live in where we're going, either via sort of explicit parallelism
> in the in the API's or, you know, playing
> 15:48:43 nice with the existing parallel SPL constructs, which is
> something I understood a little bit of but I really think that, you know,
> anything to be universally useful.
> 15:48:53 Given that the standard has parallelism in it now, we really, it
> really needs to be, you know, part of are addressed in this particular
> effort and in addition, like some of the more modern kinds of parallels and
> things like co routines and the executioner's
> 15:49:12 work that's going on right now that you know they're not standard
> yet but it looks very likely that we will have some form of executed
> parallelism and things like that I think will be very very important and
> need to be at least plan for or, there needs
> 15:49:26 to be space in this in what we're standardizing now, so that when
> those things come online, they're compatible with what has, you know what
> has gone through us I mean this is a successful effort, I was really,
> really all I want to say is the I can't forget
> 15:49:43 the parallelism.
> 15:49:46 With these very large data graphs and things.
> 15:49:52 I think with what I've shown today it's really more on, you know,
> providing a uniform access to this structures.
> 15:50:03 In terms of the algorithms, I think what you're really addressing
> is the algorithms. And, and so what I've represented is different ranges,
> you know, these things edges or vertices or just ranges, as two plus plus
> or a step defines them.
> 15:50:22 When it comes to the, the algorithms, it's really or the
> parallelism is really on the algorithms.
> 15:50:32 Based on the ranges, and it has to do with just defining an
> additional parameter that says you know, that gives an option for doing
> parallelism, is the view that I've had, or I don't disagree i don't
> disagree at all I guess all I'm saying is things like
> 15:50:49 are we using iterator is are we using indices, you know, when you
> start to think about how parallel algorithms are off and implemented those
> things matter.
> 15:50:59 And so it was really just an observation that, you know, I feel
> like if if I can't use it in parallel, I don't want it, that's sort of a
> personal opinion if I can't.
> 15:51:09 If I can't use it on a modern, you know, system in parallel going
> parallel parallel kinds of algorithms, then it's not helpful to, to me, so
> 15:51:21 Right. Well, not all graph algorithms are are have good parallel
> 15:51:29 And maybe you should supply them if they can't.
> 15:51:34 Here's it here's the standard algorithm that can't be done
> efficiently, right doesn't seem like a good plan in parallel, I mean I
> understand what you're saying and I'm, I'm a unique user right I only
> really care about parallelism.
> 15:51:47 I don't think you're that unique I care a lot about parallelism
> as well. I mean I don't care at all about sequential algorithms, I guess.
> 15:51:56 Well let's make it unique.
> 15:51:59 I'm guessing Luke, you care about efficiency. I do I'm joking.
> 15:52:03 I'm not trying to be. I know when the transcript comes out, it
> should be it. You know the nuances got I'm joking, but I am saying that I
> really do care about the parallel applications of these right well.
> 15:52:15 The interesting thing about algorithms is that some of the
> sequential items are faster than the attempts at the parallel.
> 15:52:21 So again, I think what we all care about is efficiency and graph
> of it.
> 15:52:26 Okay, yes it is waiting on line going again.
> 15:52:30 Okay, yes this is waiting on line, go ahead. Again, I just want
> to point out that I do agree with the parallelism concerns, in general, we
> should. However, this particular graph paper should not try to do more than
> what the usual.
> 15:52:46 You know one dimensional algorithms and the standard library
> already support which is a single parameter was an execution policy.
> 15:52:52 So, and and the algorithms we already have are for example don't
> work with routines full stop.
> 15:52:59 And there should be no attempt for the graph algorithms to try to
> somehow over with Cortines.
> 15:53:06 Just don't do it at that level that's a totally different
> discussion, and we should first discover how the existing standard library
> one dimensional algorithms work as core routines or can be made to work
> with authorities before we even tried to integrate
> 15:53:20 that here. Yes, I totally agree and I really was thinking the
> execution policies in parallel STL, but I was also thinking that in the
> future we will have other forms of parallelism as well, that might very
> well be the case but then I first want to see
> 15:53:34 those kinds of fellows, apply to the existing standard library
> algorithms before we burden filled with somehow doing clever thanks for the
> graph library.
> 15:53:48 That's all.
> 15:53:50 Thank you.
> 15:53:51 Anyone else. I think we should have Andrew have the last word to
> see if his vision is go ahead and do little things.
> 15:54:00 Yeah.
> 15:54:03 So a couple of comments I guess one of you know regarding.
> Usually, when you presented grasses, you know, based on indices a lot of
> this did come from, you know, if we really do define a graph, as it's a
> range of ranges or really a random access range
> 15:54:23 of forward rages that implies immediately a lot of things that I
> think lead to using indices, so prisons, cups of time look up and having a
> different type and all these sorts of things.
> 15:54:42 So, I think you'll get the kind of the point of view of
> 15:54:51 coming from is that the data are are separate from separate
> things from the graph.
> 15:54:59 And that know we're really just trying to capture and be able to
> iterate through structure that's implied by certain kinds of relationships
> among the data.
> 15:55:13 And I also can echo Luke's point that, you know, being able to do
> things within the context of the standard library parallelism is really
> 15:55:25 The.
> 15:55:43 And this is, again, you know, one of the themes I guess are we're
> sort of principles is or, you know, maybe the thought experiment I was
> engaging and is can you, you know, does the standard library already
> provided enough to implement graph algorithms
> 15:55:47 in a generic way and how, what sort of the answer that yes but
> then the question is what sort of interfaces, do you want to put on the
> resulting concepts to meet the class of actual data structures that we want
> to use it was algorithms, as large as possible.
> 15:56:12 But don't you also want to be able to use facilities outside of
> the standard.
> 15:56:23 How do you mean.
> 15:56:25 So if I've got a better vector, or a vector that I like to use,
> and I'll point to the visit.
> 15:56:33 What's that one that's being proposed.
> 15:56:38 Think of cyclone, that's wrong thing.
> 15:56:42 It just has different characteristics to support stable iterator
> So for instance, if I wanted to use that or and I've got my own that I'd
> like to us.
> 15:56:55 How would I use that. Well, to use me if you're going to use me I
> guess the question is, is that structure already, is that usable with the
> standard library.
> 15:57:06 Now, if it's a provides generators and all of the things that we
> like. If it's already usable with the standard library, then it should be
> usable with the graph algorithms that are built using standard library.
> 15:57:21 So how do we do that. Yeah, and that that's that's the whole
> point so if, if I have a new thing I guess what a colony or hive structure
> ago yeah that is usable as a standard library container.
> 15:57:37 And it meets certain standard library container concept
> interfaces, then graph algorithms, written to conform to standard library
> concepts in interfaces, you could drop in any type that meets standard
> library interfaces.
> 15:57:53 Right.
> 15:57:54 And so what I've tried to do share today is to at least with
> those functions for fine is an attempt to abstract that so that we can use
> 15:58:07 So what other mechanism that I'm sure there are other ways.
> 15:58:12 How would we do that, um, you know, like I said, the you know,
> the interface right now the concepts you were defining his range of ranges.
> 15:58:19 You know colony is a range.
> 15:58:23 Then, you know, to be able to drop it in, without any difference
> than, you know what, what's already there.
> 15:58:32 Okay, so you're going to then. Don't you have to then, also,
> somehow represent these other types of ranges the adjacent see range and
> the edge less range.
> 15:58:53 Are you saying that you would just create views or adopters to,
> 15:58:58 to represent us.
> 15:59:02 Yes, I mean, again you know the kind of the idea or the theme
> was, you know, build things using standard library interfaces and since to
> interoperate with, if you have a new data structure to interoperate with
> c++ standard library wanted offices interfaces.
> 15:59:20 Then, you know, anything, having those interfaces will work with
> 15:59:26 Then, I think, you know, there are things though I think as we've
> talked about, you know, graph data structures that are will just make lists
> of nodes and the nodes are data, heavy and so forth it.
> 15:59:47 one of the right ways of providing the necessary interfaces to
> those. But a lot of that is, you know, I think the interfaces that are
> defined we shouldn't just give something that's already in c++ standard
> library, a new name arbitrarily mean sometimes
> 16:00:01 I think we might want to just to be friendly, you know, because
> we're talking, are talking about graphs. After all, but I don't think, you
> know, the lighter weight, the interface can be in the lesson programs have
> to kind of keep in their brains as they're
> 16:00:17 using using it.
> 16:00:20 So what you've, you've expressed things as saying using tools for
> actors and such, but there's the graphs can be much more wider variety and
> so you need to, if you want to get that target key for instance, how do you
> get that out in a uniform way.
> 16:00:41 Are you going to be forcing things into that structure that
> you've expressed or how are you going to do that.
> 16:00:48 Well I mean there's two ways right i mean one is you put views on
> it, that the would allow access in that way to have the underlying
> infrastructure, or, you know, you create a more general function to access
> 16:01:07 But then, you know, the user has to adapt to that interface
> anyway. So the, you know, the question is what interface or the user adapt
> 16:01:19 And if it's easy.
> 16:01:21 You know if they can provide you know there's some standard
> interface and, you know, it's already have you were arranged or whatever
> then putting range adapters on top to provide that view is is one option.
> 16:01:35 So think about that one more I think we need to have some kind of
> non composed container examples to work with.
> 16:01:55 Now,
> 16:01:58 I'm not sure where to go from my, my focus at this point.
> 16:02:05 I mean I can continue on, on all of this, but I'm not feeling,
> getting a sense that there's a clear direction here.
> 16:02:16 Well, this is certainly a research exercise I mean, in some way,
> because that what you're doing here in that particular shape and form has
> not been done before.
> 16:02:29 So,
> 16:02:33 the the incremental progress updates we get in these meetings are
> certainly helpful, but random comments during a one hour video presentation.
> 16:02:46 Replace, actually, you know,
> 16:02:51 maybe the comments are totally off because some things just don't
> work or so, I don't know, but I
> 16:03:00 I would certainly want would like to see some more.
> 16:03:06 Some more.
> 16:03:12 Now, well,
> 16:03:16 Andrew is one of the things that under does is pre processing the
> input data into stuff that has indices. And he says, Well, if you have a
> random access range then obviously you have you have a difference type.
> 16:03:31 So, you have entity or entities, right there.
> 16:03:35 And I think bridging that gap is, is important, and understanding
> 16:03:49 where the problems are, can we bridge that gap by providing a
> view on some other data structure.
> 16:03:59 Understand that Phil you don't want a pre processing of your data
> to just do this index index based stuff that Andrew.
> 16:04:21 And so it would be interesting to see if there is some way to
> have a view around your data structures that actually presents to address
> algorithms interfaces that actually work for example, maybe not, I don't
> 16:04:36 And it could very well be that, and the end of the day, at the
> end of the day doing the pre processing.
> 16:04:43 And then running the algorithm is actually faster because,
> because it's just so much faster to deal with them than more elaborate
> things than that it's actually worthwhile to do that pre processing step
> before running the actual process, rather, as opposed
> 16:05:02 to running the graph algorithm on some complicated internal data
> structure that just takes it takes comparatively long time to traverse.
> 16:05:10 You know cache misses and all that.
> 16:05:16 So,
> 16:05:16 I don't know, sorry that this is all relatively hazy and not
> giving you clear marching orders but that's I guess the nature of the
> 16:05:38 Well I think maybe Andrew and I. One thing that's happened.
> 16:05:46 Andrew and I've been accepted to do a talk at CPP con.
> 16:05:52 In a couple months. And so I think that would give us some good
> opportunities to discuss this more and explore some more.
> 16:06:09 So I look forward to doing that and it'll be interesting to see
> how that that comes out.
> 16:06:21 Yeah, I think that's some.
> 16:06:23 That's gonna be a good opportunity to see if we can come
> together. I think the call is done.
> 16:06:30 It might still be some things you guys can work out.
> 16:06:32 I'm glad you're called, I'm glad your talk was accepted the, the
> general talk was was rejected which is fine because I kind of figured that
> it was a fallback option in case the your thoughts are not accepted.
> 16:06:44 So, so thank you very much for presenting guys and follows a
> great feedback and comments, and I will see you guys, unless there's
> anything else. Anyone wants to see any last things.
> 16:06:57 If not, Thanks everyone.
> 16:07:01 Okay.
> 16:07:02 Yeah.
> 16:07:08 Yeah, thank you.
> 16:07:05 And then we'll see you guys in a month and. Cheers. Bye bye.
> On Thu, Sep 9, 2021 at 12:41 PM Michael Wong <fraggamuffin_at_[hidden]>
> Thanks no worries. I have adjusted the agenda a little bit
> On Thu, Sep 9, 2021 at 12:11 PM Richard Dosselmann via SG19 <
> sg19_at_[hidden]> wrote:
> I am unable to attend due to meetings and teaching.
> Quoting Michael Wong via SG19 <sg19_at_[hidden]>:
> > Hi all, SG19 Sept meeting is tomorrow Sept 9.
> > SG19 Machine Learning 2 hours. This session will focus on Graph
> > Hi,
> > Michael Wong is inviting you to a scheduled Zoom meeting.
> > Topic: SG19 monthly
> > Time: 02:00 PM Eastern Time (US and Canada) 1800 UTC Stats
> > Every month on the Second Thu,
> > Join from PC, Mac, Linux, iOS or Android:
> > https://iso.zoom.us/j/93084591725?pwd=K3QxZjJlcnljaE13ZWU5cTlLNkx0Zz09
> > Password: 035530
> > Or iPhone one-tap :
> > US: +13017158592,,93084591725# or +13126266799,,93084591725#
> > Or Telephone:
> > Dial(for higher quality, dial a number based on your current
> > US: +1 301 715 8592 or +1 312 626 6799 or +1 346 248 7799 or +1
> > 408 638 0968 or +1 646 876 9923 or +1 669 900 6833 or +1 253 215 8782
> > or 877 853 5247 (Toll Free)
> > Meeting ID: 930 8459 1725
> > Password: 035530
> > International numbers available: https://iso.zoom.us/u/agewu4X97
> > Or Skype for Business (Lync):
> > https://iso.zoom.us/skype/93084591725
> > Agenda:
> > 1. Opening and introductions
> > The ISO Code of conduct:
> > https://www.iso.org/files/live/sites/isoorg/files/store/en/PUB100397.pdf
> > IEC Code of Conduct:
> > https://www.iec.ch/basecamp/iec-code-conduct-technical-work
> > ISO patent policy.
> > The WG21 Practices and Procedures and Code of Conduct:
> > 1.1 Roll call of participants
> > 1.2 Adopt agenda
> > 1.3 Approve minutes from previous meeting, and approve publishing
> > previously approved minutes to ISOCPP.org
> > 1.4 Action items from previous meetings
> > 2. Main issues (125 min)
> > 2.1 General logistics
> > Meeting plan, focus on one paper per meeting but does not preclude other
> > paper updates:
> > Sep 9, 2021 02:00 PM ET 1800 UTC Graph
> > Oct 14, 2021 02:00 PM ET 1800 UTC Differential calculus/Reinforcement
> > Learning
> > Nov 11 , 2021 02:00 PM ET 1800 UTC DST break/cancelled
> > Dec 9 2021 02:00 PM ET 1800 UTC Stats
> > ISO meeting status
> > future C++ Std meetings
> > 2.2 Paper reviews
> > 2.2.1: ML topics
> > 184.108.40.206 Graph Proposal Phil Ratsloff et al
> > Latest paper:
> > Here?s a link to the paper (different than the previous paper reviewed).
> > There are some additional updates I?m planning on making before the
> Andrew Lumsdaine' proposal.
> > P1709R3:
> > <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2119r0.html
> > <
> > Array copy semantics:
> > array copy-semantics paper P1997 "Relaxing Restrictions on Arrays",
> > https://wg21.link/p1997
> > Stats feedback:
> > P2376R0
> > <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2376r0.pdf
> > Comments
> > on Simple Statistical Functions (p1708r4): Contracts, Exceptions and
> > Special cases Johan Lundberg
> > 220.127.116.11 Reinforcement Learning Larry Lewis Jorge Silva
> > Reinforcement Learning proposal:
> > 18.104.22.168 Differential Calculus:
> > 22.214.171.124
> Stats paper
> > Current github
> > https://github.com/cplusplus/papers/issues/475
> > https://github.com/cplusplus/papers/issues/979
> > Stats review Richard Dosselman et al
> > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1708r4.pdf
> > Feedback from Johan Lundberg and Oleksandr Korval
> > https://isocpp.org/files/papers/D2376R0.pdf
> > P1708R3: Math proposal for Machine Learning: 3rd review
> > PXXXX: combinatorics: 1st Review
> >> std.org/jtc1/sc22/wg21/docs/papers/2020/p1708r2
> >> above is the stats paper that was reviewed in Prague
> >> http://wiki.edg.com/bin/view/Wg21prague/P1708R2SG19
> >> Review Jolanta Polish feedback.
> >> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2119r0.html
> > 2.2.3 any other proposal for reviews?
> > 2.3 Other Papers and proposals
> > P1416R1: SG19 - Linear Algebra for Data Science and Machine Learning
> > P1415: Machine Learning Layered list
> > 2.2.2 SG14 Linear Algebra progress:
> > Different layers of proposal
> > 2.5 Future F2F meetings:
> > 2.6 future C++ Standard meetings:
> > https://isocpp.org/std/meetings-and-participation/upcoming-meetings
> > None
> > 3. Any other business
> > New reflector
> > http://lists.isocpp.org/mailman/listinfo.cgi/sg19
> > Old Reflector
> > https://groups.google.com/a/isocpp.org/forum/#!newtopic/sg19
> > <https://groups.google.com/a/isocpp.org/forum/?fromgroups=#!forum/sg14
> > Code and proposal Staging area
> > 4. Review
> > 4.1 Review and approve resolutions and issues [e.g., changes to SG's
> > working draft]
> > 4.2 Review action items (5 min)
> > 5. Closing process
> > 5.1 Establish next agenda
> > Oct 14
> > 5.2 Future meeting
> > Oct 14, 2021 02:00 PM ET 1800 UTC Differential calculus/Reinforcement
> > Learning
> > Nov 11 , 2021 02:00 PM ET 1800 UTC DST break/cancelled
> > Dec 9 2021 02:00 PM ET 1800 UTC Stats
> This e-mail was sent via the Secure Web Server at the
> University of Regina, Department of Computer Science
> SG19 mailing list
SG19 list run by email@example.com
SG19 Archives on Google Groups