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 prepared.
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: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 physical.
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: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:03 Okay. Okay.
14:09:05 Unless you want to do, intro first to lead into, you know, set up to what you were your stuff.
14:09:13 Either way.
14:09:15 Yeah, I
14:09:18 don't know how long I can see us taking 45 minutes or so on, on my stuff fence on the, the feedback.
14:09:29 Okay. An angel How long do you think your peaceful be
14:09:34 probably about the same. Okay.
14:09:44 That sounds fine yeah 1015 minutes, 10, talking, 5% feedback.
14:09:49 That sounds good. Okay, why don't why don't we start.
14:09:52 So let's see if I can find it.
14:09:57 Oh, there it is.
14:10:00 Okay, go ahead. Go ahead. Well, so yes I can just talk over the paper if you like I have some time so I could show, I didn't do any slides.
14:10:09 So, this proposal is a small proposal was put in about 20 months ago first in December 2019 and then quickly a first revision.
14:10:20 The authors are talking about a second revision. The main author, a young guy amazing guy he worked for a while, for the c++ alliance.
14:10:31 And somehow, you know he's still a student I think but got into standard the US reading the standard.
14:10:35 I'm not sure who the second author is he's perhaps an academic. But, anyway, the, the paper itself is somewhat academic it.
14:10:46 You know, it includes the wording.
14:10:48 It's been criticized by some people high up in the c++ Committee is lacking motivation.
14:10:54 I can talk to that if we need so the reason why I think this is of interest, the machine learning group is it's related, and the remit here is pretty much rate related when you read it.
14:11:07 Now, this is going back 50 years really fixing an issue from see that then was inherited into c++, that arrays are not regular types, you can't copy them to be fully regular you need to compare as well, a semi regular type is called people.
14:11:24 And that can mostly be fixed and I don't understand why it wasn't done back when Richie made struct comfortable. So for a while in early. See, you would have to copy every single member of a struct when you copy destruct but somewhere between one and
14:11:42 two, structural help people with your rep with a raised hand side.
14:11:44 So that's one place where you get to wake up in the C, and c++.
14:11:48 The other singular cases string literal Wars character array can be initialized from right hand side string literal.
14:12:02 Now, in recent years have been a couple of other cases of array copies have been added, where that is convenient. So, lenders will copy the by value capture of an array structure bindings will copy an array, right hand side, oh sorry I'm not talking over
14:12:22 the paper here at all. That's not included. So there is a nice examples in the paper. So one of the questions that comes up incessantly is, why isn't good enough.
14:12:34 And I don't see that as a relevant question I want good built in a race. I want them in order to build better class arrays. So, I've been kind of working in array related stuff for many years, I did blessing, implementation, many years ago.
14:12:50 I'm kind of in the Python data, ecosystem at the moment, used to do MATLAB
14:12:56 arrays, can be comfortable. I, you know, this paper hasn't seen any, any issues raised against it people haven't come up with any reasons why it won't work.
14:13:07 I've been trying to look at it from, you know, an attackers point of view what what could be wrong with this what doesn't work. I, I know of two small breakages that were discussed with this see.
14:13:22 Okay, so what's the history of this, so 20 months ago, it hasn't seen any interest. I'm the main proponent keep pushing on it, the author has gone on to other things, but it's still kind of keeping his hand in a little probably would be involved with
14:13:35 this, if there's a revision.
14:13:37 So about a year ago, I joined this group, mostly to push rate related things and the SG 22, the newly formed C and c++ liaison group, partly because I realized that they were more likely to be interested in this proposal then c++.
14:13:56 As you know, array is a somewhat to boo within the c++ Committee and community where it's still very central to see.
14:14:03 I mean that's foundational in c++, as well, but it creates something of a two worlds view of and that you know, coming back to standard array, it's kind of typify by standard array.
14:14:16 So what's the problem with standard rate. One of the problems listed in this paper is the initialization issue. So I call this the member array initialization conundrum.
14:14:28 And there is the few kind of work around solutions I've blogged on a few of them.
14:14:35 But the problem is, you have an existing l value array. How do you initialize the standard away with it.
14:14:41 Now we have stood ranges copy. So ranges copy can do can do that for a one dimensional array, but fails, as soon as it is nested, so it won't do it for nested see array.
14:14:53 I believe it won't do it for nested standard right but I haven't tried that
14:14:58 out, I'll try that.
14:15:02 Now, with bit cast you can build custom array and created that way. But, you know, standard rate was standardized with c++ 11 but really came from boost 10 years before that.
14:15:13 And it's you know an early example of a way of wrapping horrible see and giving it to c++ facade or API to work with the other algorithms. That's not necessary now in c++ 17 we got data and science free member functions, along with the existing data and
14:15:50 data science. Yeah.
14:15:42 Yeah. So, oh beginning End Of course. So, you know, all of those three functions, interoperate fine with a radius and built in arrays also have a specialization for stud swap.
14:15:55 So, effectively, you know that's a, an old range algorithm that will copy even nested array is properly recursive Lee.
14:16:02 I'm drifting off again. So, standard rate in c++ 20 we got standard to array, which will take an array of value and create a standard array from it. But what wasn't noticed is that in the is Luke here, yeah.
14:16:20 Oh yeah, look see So Luke noticed a couple of months ago that the earlier experimental maker Ray was able to make zero sized standard array.
14:16:27 But to array cannot do that because it's converting built in and ready to a standard rate you can't have a zero size built in array. So, so you know one of the advantages of standard rate is that it's got the zero sys specialization.
14:16:45 And then one of the downsides, is it needs to zero size specialization so every array class you right you have to do as he works on a specialization. And it's a little tricky to write, it's easy to get wrong.
14:16:56 And there's several of the standard library implementations got it wrong and had issues raised against it.
14:17:01 But anyway, I'm rambling again I guess so.
14:17:04 The history then so it got viewed, but it got raised on the liaison mailing list and was discussed, a month ago was August the sixth.
14:17:14 It holiday season. So, that partly member to dissenting voices are not dissenting there was some concern raised at the highest levels.
14:17:25 Worried of WG 21 didn't make it to the meeting, but sent messages to the reflector with, you know, unspecified concerns that when arrays have been dealt with.
14:17:37 When it's been attempted to improve it raised in the past, it's led to difficulties.
14:17:44 So that's what I want to drill down on you know I'm so, so what came out of that meeting is we need implementations we need compiler implementations. So, the paper has been forwarded to EWG, but it's not worth doing, until we have implementation experience.
14:18:00 And similarly on the sea side wg 14. I've got much stronger gating they require implementations.
14:18:09 So, I happen to have a few weeks, open before contract, that's coming up in mid October, so I volunteered to do the planning and GCC implementations.
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: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 seen.
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 evolution.
14:24:29 working group.
14:24:31 So that's so it's it's do for evolution working group, and the implementation is what is required to make it worth going there.
14:24:39 So hopefully, by early October I'll have something by mid October, enough to move it to EWG while that might be true.
14:24:49 Your, yo, yo, you might also be your, you're also risking the idea that evolution can change this significantly on you, or just rejected outright. And then you might not have anything to you might have wasted some time right so that's true.
14:25:04 And, you know, that was flagged up in liaison as well.
14:25:08 But somebody needs to do this, I'm not, I'm not the best I'm a hacker I can dive in. I've done a couple of PC patches in the past. I'll give it my best go yeah and and the fact that the fact of doing it will allow you to find, you know some some some
14:25:24 of the answers that this paper is posing and, you know, maybe it should smoke, it should smoke out any issues, and hopefully quell the third because you know there is fear, uncertainty and doubt being spread.
14:25:36 And this will get more certainty.
14:25:40 So, at the end of the day, if this works then you're going to be able to copy a raise to raise directly, without going through some sort of loop. Is that is that right that's right and then it happens to kind of mend a whole bunch of standard algorithms
14:25:58 that are the moment it doesn't make sense to pass a raised because they will fail. So you know ranges is pretty good but as soon as you get to multi dimensional raise it fails, or once you go past the level where you need now value it will fail, I think.
14:26:12 So this just makes it more robust. There's also a c++ 23 proposal to allow braced initialization in more standard algorithms, and that will just work with a radius once, once this is done.
14:26:27 And I think.
14:26:27 Recently, that was a cosmetic change that allows you to do square brackets with, with commerce, to be to be parsed properly as an array.
14:26:39 Sorry, I missed that, this, this.
14:26:43 So this is a paper by.
14:26:46 I'll have to dig it out later it was put in.
14:26:49 My name is Mark Coleman.
14:26:55 No, I'm thinking of another paper this is
14:26:55 I braced initialization in standard algorithm.
14:26:59 Yeah, I know. Yeah.
14:27:02 But yes, I'll check check this afterwards and send out links. Okay, thank you.
14:27:08 Okay, I mean this is this is only the start.
14:27:12 You know, we make it a semi regular, and then there's a bunch of other things that improve things more, like this one, you know that what you're getting into, because if you don't put push this through EWG first, and then do an implementation, while that's
14:27:27 that. That is really helpful it snot smoking out the, the Gremlins you, you know, ew, you might totally reject this or change it. So just be careful.
14:27:40 I mean, I mean, I'm interested in any opinions from the group here as well if anybody thinks either this is crazy or this is great, please drop me a line.
14:27:48 If anybody sees any issues especially. Great.
14:27:54 And yes thanks for that heads up Michael Yeah that's it some hopefully people will have a bit of a chance to look at I mean arrays is of interest to a lot of people, I would say, especially the high performance computing people and of course by influence
14:28:07 the machine learning people, it would be it would be good if you can pass this to people like Mark Coleman.
14:28:14 Yes, I've talked with him in the past. Yeah, see what he thinks, because they you stay as he is still firmly involved in high performance computing.
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 biggest
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 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 ranges.
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:20 standard library containers.
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: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 anymore.
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 neighbors.
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 them.
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 movies.
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 are.
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 structures.
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 direction.
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: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:39 I can stop sharing and.
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 operations.
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: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 you.
15:00:02 I think one of the things.
15:00:05 So Andrew and I come at this from different perspectives so he's really been in the algorithms a lot.
15:00:10 I've been on products that have a graph embedded in it.
15:00:14 And so those brings unique challenges from both of those.
15:00:20 So I think both are valid and both are interesting.
15:00:23 I think, in, in this expression of stuff I really like the sickness, and brevity of being able to express the buttons there.
15:00:32 And I've always looked at this and is, and.
15:00:36 And the same.
15:00:38 Can we get there.
15:00:41 To do that, and the other thing that I've looked at the the thing that's going there's there's an emphasis on index looked up.
15:00:50 And when I look at the STL, there's an emphasis on using iterator as the core element here, and. And so this is really great because I think we're getting a lot closer than we used to me.
15:01:07 And I'll show that in a little bit.
15:01:10 But how can we make this most expressive and also.
15:01:15 First of all, so that, for instance, we can adapt existing graphs out in the wild, to the algorithms that are in the standard, for instance, because that's always been a strength of the STL is that somebody that writes this container over here can use
15:01:36 an algorithm that's developed somewhere else.
15:01:40 And so,
15:01:44 there's just kind of my some general observations, I don't think that we're that far off in a lot of ways. Okay, and what what do you think Andrew do you think,
15:02:00 Well I think that's right i mean so they're in one of the, I guess, preface slides I mentioned that
15:02:12 we abstract from concrete efficient algorithms to obtain generic algorithms. And the other part of that is the algorithms that can be combined with different data representations.
15:02:25 So, you know, making sure the you know the the concept definitions are the main type requirements can encompass those different data representations is is kind of important part.
15:02:39 And so, in some sense, it also mentioned. He was kind of coming at this from the point of view of the different data representations. And, and I was trying to start with, you know, the concrete efficient algorithms.
15:02:53 And also, you know, in some ways I've been, you know, deliberately sticking out maybe an extreme approach in that I wanted to 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 algorithm.
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 there.
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, right.
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:35 Okay. Hopefully everyone can see what I have here.
15:07:23 I'm just, it's been a while since we've looked this up but just to remind everyone, I have, you know, played, we're seeing your entire screen, and the actual text you want to show is taking up about one third of the screen.
15:07:36 It would be very helpful to fix that by either resizing your window and and or just sharing the window you want to you want to share with us.
15:07:49 Thank you for
15:07:55 this better.
15:08:05 It's, it's slightly better Yeah, yeah, no, it's getting even better. Okay.
15:08:09 Okay, so, you know, there is an abstraction for, say, Dextre, which is one of the things that Andrew was sharing and so there's the idea of having a function called a distance function its weight function.
15:08:27 It provides the same feature. And so I think,
15:08:32 you know, I, we haven't been looking at that as much here in the recent reviews, because I think it's in large part, Pretty good stab at it.
15:08:44 And I think, in all of the reviews that we've done it.
15:08:50 There hasn't been any disagreement with any of this.
15:08:54 Okay, so just, just as a reminder.
15:08:59 And so I think a lot of the, this has been trying to figure out the right abstractions for representing the data models.
15:09:08 So, And that's, and it's dealing with the concepts and the types. And what does that mean and giving that abstraction right and that's a lot of what I'm going to be talking about today.
15:09:21 And also wanting to do a little bit of a demo of how it would be used.
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 contributed.
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: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: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 default.
15:14:09 So there's no special behind the scenes things I'm doing for this demo
15:14:32 Worse, you have a problem with us. You know I went through this.
15:14:50 Well I guess I can't run it, but you get the idea. It ran, just an hour ago, without any problem.
15:14:58 You can see the vertices that I'm getting the vertices, out of the graph.
15:15:03 And in this case, it's just saying, I can take this off right
15:15:12 now. give me the same results.
15:15:16 Even though I can't prove it with pilot.
15:15:20 So in this case it's just saying if it's a range.
15:15:50 Suzanne is asking what are the five, five inches.
15:15:55 Oh, I see. It's good because I help.
15:16:05 So the edges are 021 or two little ones over 2122123, and three to zero.
15:16:19 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: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: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: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 graphs.
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 stuff.
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 range.
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 well.
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 iterations.
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: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: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:08 an index value of sorts or something like that, it could be some more some more complicated data structure of that actually gives you what you want.
15:29:17 Now, Andrew was also doing things like this where he was returning to a tool that had multiple values. Yes, sure. How are you feeling about that.
15:29:34 I don't. I personally.
15:29:38 I don't think that's a problem, I think it's natural for. If you think and abuse, and abuse, fear, it's natural that you will not necessarily have iterate over scalar values but might iterate over more complicated values such as couples, or ranges in
15:29:59 this case.
15:30:01 So that seems seems plausible.
15:30:06 So, yeah, why not.
15:30: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 available.
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: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: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 agree.
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: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 doing.
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: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: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 iterator.
15:40:18 So once we have those now we can start to describe what these graphs are a vertex list graph is a vertex range. I think under has a different a little different idea of what that might be.
15:40:31 That's just focused on the keys.
15:40:34 There's an incidence graph, which is the vertex range. the edge range, and it has an address function.
15:40:46 Now, in a sense, there's some duplication here because the edge range calls the edges function.
15:40:53 And so, in a sense, I don't really have to define that. But I think it's helpful to be clear on the design.
15:41:02 So, once we see those, the interesting see graph is the same exact thing. The only difference is that range that we're using the explicit range.
15:41:12 And it's matching function.
15:41:15 Same thing with the edge of this graph and the edge range, and the edges.
15:41:25 There's finally an adjacent to the matrix and it's just false. There's some algorithms that can get benefit, knowing that it's working on a matrix. and one of the tears that way.
15:41:37 And so, this is a way to tag your graph, of being initiation two matrix.
15:41:47 There's some contains concepts which are contains vertex contains edge.
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 value.
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 function.
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 overriding
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: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: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: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 personally.
15:51:21 Right. Well, not all graph algorithms are are have good parallel answers.
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: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 important.
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: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 graphs.
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 it.
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 to.
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: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: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 know.
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 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 problem.
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:08 Yeah, thank you.
16:07:05 And then we'll see you guys in a month and. Cheers. Bye bye.