C++ Logo


Advanced search

Subject: Re: SG19 Sept 9 (Graph) Zoom call
From: Michael Wong (fraggamuffin_at_[hidden])
Date: 2021-09-13 09:49:06

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
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 type.
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
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 need.
14:59:56 And, in fact, the the implementation that's there would agree with
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 avoid.
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
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
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
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 points,
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
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
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
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 it.
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, 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]> wrote:

> 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
>> location):
>> > 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.
>> >
>> >
>> https://isotc.iso.org/livelink/livelink/fetch/2000/2122/3770791/Common_Policy.htm?nodeid=6344764&vernum=-2
>> >
>> > The WG21 Practices and Procedures and Code of Conduct:
>> >
>> https://isocpp.org/std/standing-documents/sd-4-wg21-practices-and-procedures
>> >
>> > 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
>> >
>> > 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
>> meeting.
>> >
>> >
>> https://docs.google.com/document/d/1OpH-xxRri7tJTtJJIZTYmSHkkrZJkdBwm9zJ7LqolfQ/edit?usp=sharing
>> >
>> >
> Andrew Lumsdaine' proposal.
>> >
>> >
>> > P1709R3:
>> >
>> https://docs.google.com/document/d/1kLHhbSTX7j0tPeTYECQFSNx3R35Mu3xO5_dyYdRy4dM/edit?usp=sharing
>> >
>> >
>> https://docs.google.com/document/d/1QkfDzGyfNQKs86y053M0YHOLP6frzhTJqzg1Ug_vkkE/edit?usp=sharing
>> >
>> > <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2119r0.html>
>> >
>> > <
>> >
>> https://docs.google.com/document/d/175wIm8o4BNGti0WLq8U6uZORegKVjmnpfc-_E8PoGS0/edit?ts=5fff27cd#heading=h.9ogkehmdmtel
>> >>
>> >
>> > 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
>> >
>> > Reinforcement Learning Larry Lewis Jorge Silva
>> >
>> > Reinforcement Learning proposal:
>> >
>> > Differential Calculus:
>> >
>> >
>> https://docs.google.com/document/d/175wIm8o4BNGti0WLq8U6uZORegKVjmnpfc-_E8PoGS0/edit?ts=5fff27cd#heading=h.9ogkehmdmtel
>> >
>> > 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
>> >
>> https://docs.google.com/document/d/1IKUNiUhBgRURW-UkspK7fAAyIhfXuMxjk7xKikK4Yp8/edit#heading=h.tj9hitg7dbtr
>> >
>> > P1415: Machine Learning Layered list
>> >
>> https://docs.google.com/document/d/1elNFdIXWoetbxjO1OKol_Wj8fyi4Z4hogfj5tLVSj64/edit#heading=h.tj9hitg7dbtr
>> >
>> > 2.2.2 SG14 Linear Algebra progress:
>> > Different layers of proposal
>> >
>> https://docs.google.com/document/d/1poXfr7mUPovJC9ZQ5SDVM_1Nb6oYAXlK_d0ljdUAtSQ/edit
>> >
>> > 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
>> https://www.cs.uregina.ca/WebMail/
>> --
>> SG19 mailing list
>> SG19_at_[hidden]
>> https://lists.isocpp.org/mailman/listinfo.cgi/sg19

SG19 list run by sg19-owner@lists.isocpp.org

SG19 Archives on Google Groups