✅ Development Work: Dec 2023 - Jun 2024: Automated system testing and Topological sorting #72
Replies: 11 comments 8 replies
-
|
Hi @KennedyRichard, thank you for the detailed write up. I agree with everything you said regarding topological sorting. Especially that executing nodes asynchronously/in parallel is out of scope for now. Please let me know if you need any help with the implementation or testing. Enjoy your vacation! |
Beta Was this translation helpful? Give feedback.
-
|
Hello, everyone, Stopping by just to update you on my progress on this schedule work for Nodezator. As explained before in this discussion, I worked on Bionic Blue this past November. Although, due to other tasks of the Indie Python project I had to start later than anticipated and only managed to begin my work on it at the middle of November. Because of that I still kept working on it this first half of December. I'm finished with my work on Bionic Blue for now though and already began my scheduled work for Nodezator. This first phase required a bit of research in order to answer some important questions, which is why I didn't begin to work on the repo yet (except for accepting a pull request and adding some small changes to it that were discussed with the author of the PR). I managed to find the answers I needed. I wanted to confirm what kind of information I'd need to ensure I had the right test cases for the automated GUI testing feature. I posted about such answers in this twitter thread. In summary, I need to document Nodezator's design in order to use it as the basis for the test cases. I already started writing such design information needed, but didn't upload anything yet, although already created the repository where will publish all the information. It is this one (it may be empty if you are accessing it close to the date this message was posted, since I didn't upload anything yet). In order to not prolong myself in that task and risk delaying the schedule, though, I'll only introduce enough information to be able to write the most crucial test cases and jump right into making the final touches in the automated GUI testing feature and making into available to users. The rest of the design document content needed for the remaining test cases will be written incrementally over time. This design document is actually a great tool to communicate the current and planned design for Nodezator, so it will be very useful to manage the project, both to me and to people willing to submit code to the project. As planned, from today (23th) until the first Saturday of 2024 (6th) I'll be enjoying the second half of my vacations. Then, I'll resume my scheduled work on Nodezator. Merry Christ/Xmas and Happy New Year |
Beta Was this translation helpful? Give feedback.
-
|
Hello, everyone, I'm here to give you an update on my work in Nodezator and the Indie Python project in the roughly 40 days of work since the end of my small planned vacations. Sundays are not included in the count, since I don't work on them. Holidays are not included as well, naturally. I apologize for taking so long to update you, though. I've been doing so many different things that it's been difficult to stop a bit to write updates. I acknowledge this is not a valid excuse, though, hence the apology. From now on I'll get back to my usual frequency of updates, that is, every couple of weeks. Without further ado, let's get into the update, that is, what I've been doing since the end of my vacations on January 6th. Planned development workI managed to write a lot for Nodezator's SDD (Software Design Document). This is important, as explained in the previous post, because I need to carefully document its design in order to define the test cases for the automated GUI testing feature, which is one of the planned features the next release. At the time of the previous post, I mentioned I'd not spend too much time on writing about the overall design of Nodezator, but focus on the test cases in order to be able to proceed with my work on the feature as soon as possible. However, I ended up writing a lot about the overall design first. There are several reasons for this. One of them is that I really need to ensure all my ideas are organized in order to visualize the software correctly in my mind, lest I risk defining test cases that do not correspond to the full design I planned for Nodezator. This is specially important given the complexity of the app. Another reason is that having a more complete SDD is crucial not only for the completion of the development work for the automated GUI tests that is planned, but for at least 02 very important pieces of content that I need to release to the community: (1) the overall design itself so code contributors can make decisions more confidently when working on pull requests and (2) a roadmap for Nodezator, so the community now the development path that is planned for Nodezator with the features to be implemented, their order, dilemmas, challenges, etc. Given all those reasons, only recently I began to write about testing in Nodezator, and should soon finally write the test cases. Of course, I still don't plan to finish the entire SDD for now. This is something which will take even more time than what is planned for the current development work for Nodezator. But now I can write the test cases with more confidence and sooner, after the planned development work is finished, release the roadmap for further discussion with the community. You can find all I've written for the Nodezator's SDD for now in the dedicated repo, in the development branch: Nodezator's SDD - dev branch. If by the time you access the link it doesn't work anymore, it just means the content was already merged into the main branch. Since I'm still to write the test cases and make all the necessary adjustments to the automated GUI testing feature, and only then proceed to implement topological sorting, a delay in the original timeline planned for the development work is inevitable. Like me, you may have been already expecting a delay, because as explained in the previous post, I also had to delay the planned work for Bionic Blue back in November. Because of that, our planned development work will probably only be completed around the middle or end of March. The Indie Python project requires much work: promoting the project online, content production, community support, just to name a few. In the next brief subsections I'll also update you on my work on such stuff. Indie Python online promotionWith the exception of this week, every week since the end of my small vacation I've been promoting the Indie Python project online, specially the Nodezator app. I've been doing it mostly on Mondays and/or Tuesdays. I'm only doing it in those days because I've been mostly replying to pygame posts on Twitter, and it takes at least one week for enough content to pile to require an entire day to reply to everything. In these replies I have the opportunity to let people know of the Indie Python project and its flagship project, the Nodezator app. Even when I don't mention them directly my interactions have been attracting a lot of new visits and users, since my profile has an abundance of links and other references to them. The Nodezator's repository has also been gaining a lot of new stars thanks to this work. Soon, I intend to expand this work to other online platforms like Reddit, other Discord channels, etc. I can't tell exactly until I properly verify how good those platforms are to help us get new visits/users. For now, I know at least Reddit is good for this. Also, I don't think the kind of online promotion that just pushes links into people's channels/emails/social media comments on the internet is good. Certainly, if we used this kind of marketing we could get more visits, but it is devoid of character and abuses people's privacy and patience. I rather approach people with the genuine purpose of helping them with something related to the project or offer an honest comment to some interesting content someone posted then spam people with unsolicited content. This is how we must approach online promotion for the Indie Python project. It takes more time to get clicks and users, but at least we keep the growth of the project organic and focus on the quality of people's experience. Rather than discovering the project via unsolicited content shoved down people's throats, people can discover it by the reference of someone interacting with them politely and genuinely. Indie Python community supportWith the increased number of visits and newcomers to the community, more and more help/support is need. Just take a look at the discussion tab of the Nodezator repo. It is filled with new discussions and questions, many still unanswered. Of course I've been answering them here and there along the weeks whenever the time allows and will eventually answer all of them, as I always do. Answering such discussions is often a complex task, because it requires me to review the design and recall decisions made in the past and touch many different topics before being able to present a complete answer. In case you are curious, one such example is discussion #79. Thankfully, I like doing what I do, and the extra effort and time required doesn't faze me at all. Quite the contrary, sometimes I even have to exercise a bit of restraint and submit a reply with x paragraphs when in fact I wanted to submit 2x or 3x paragraphs, going over additional topics in order to provide an even more complete answer. But time is limited and I must refrain from taking too much time away from bug fixing and scheduled development work, which is the reason I didn't answer all discussions at once, but been answering them gradually over the weeks. Other development work (issues/bug fixing)Besides the scheduled work for Nodezator, I still have to tend to issues, fix bugs and release patches. Sometimes this kind of work is treated with more urgency than scheduled development work, when there are bugs that are too harmful, preventing effective usage of Nodezator for some users, depending on what they are doing. It is the case of issue #88, which was causing the user to be locked out of Nodezator, having to restart the app to be able to keep using it. I've been working recently on that issue, already wrote the code to fix it and should soon merge such code and release the related patch. Content productionGiven the amount of work scheduled and the discussions and issues to tend to, I've not been spending time on content production, but this is part of the Indie Python project regular activities. Although not producing content per se, I've been at least releasing some of our produced content online. For instance, at the end of last year I discussed some 3D experiments with Mr. Adams on discord and I repurposed the contents of such discussion as a thread on Twitter and as a post on reddit. This is yet another kind of task that takes time. Even though the content was already produced, I had to reread, reformat and sometimes increment the text (to give additional context). All of this in order to prepare the content for the specific channels where they were to be posted. It is important work as well: content production is closely tied to our online promotion strategy, so it is something that we should not neglect. Such posts bring more visits and allow people to discover and engage with the Indie Python project in a fun, interesting and instructional context, instead of spamming them. ConclusionIn other words, despite delays being undesirable, at least in the Indie Python project our delays were caused by more work being done in other areas, rather than no work being done, which is a plus. Moreover, such additional work (more time spent writing a more complete design document for Nodezator and more time spent on discussions and bug fixes) is valuable work with good/great outcomes for the Indie Python project or for the subsequent tasks (for instance, a more complete design document helps me with the scheduled work of finishing the automated GUI testing feature, because it helps ensure I'm writing effective test cases). Given such delays, though, I'll update the title of this discussion on the scheduled work for Nodezator so it reads "March" where it read "February" previously. If something in my report wasn't satisfactory to you or was cause for concern (perhaps a measure I took or how I allocated time/effort), please let me know. You can write about it here or on the Discord channels. If you are not comfortable with using a public space, you can also DM me on Discord. I'm always willing to listen and improve my workflow. Again, I apologize for taking so long for updating you and will strive to report more often as I was doing previously (twice a month, every couple of weeks). All in all, I think I've been doing at least a decent job of keeping the Indie Python project alive and healthy:
Thank you all for your attention. As you could see, maintaining an open-source project is a lot of work. Please if you don't do it yet or didn't do it in the past, consider helping support the project by becoming a patron or making a one-time donation via one of the methods listed here, to help support my work on the Indie Python project. Peace. |
Beta Was this translation helpful? Give feedback.
-
|
Hello, everyone! I'm here to update you on my recent work (as promised, I'll be updating you more frequently, that is, every couple of weeks). Among the work done, I:
After working on Nodezator's SDD in this past couple of weeks I finally reached a point where I can start writing and implementing test cases as I add the final touches to the automated GUI testing feature of Nodezator (by the way, the automated GUI testing feature will be renamed to "system testing", as I'll explain further in this update). For now, I'll stop working on the SDD's overall content and only work on its test cases and Nodezator's source. I expect to have the test cases working in Nodezator by next week. The current contents of Nodezator's SDD are:
As I mentioned briefly, I'm changing the name of the automated GUI testing feature to system testing. That's because the original name is technically wrong. After consulting a lot of materials, I reached the conclusion that instead of automated GUI testing, what we are actually doing with it is system testing. It is just that this system testing is performed with the help of automated GUI interactions. This is an important distinction to make so we can properly manage Nodezator's development. I think this is all for now. Thank you for your attention. Peace |
Beta Was this translation helpful? Give feedback.
-
|
Hello, everyone! Update on current workI finally have a video demonstrating the system testing feature in action! automated_system_testing_demo.mp4To try this by yourself, just:
Now that system testing is functional, I just need to polish it and then write and implement the remaining test cases. You may want to know why I didn't write all the test cases first as I said I'd do once the SDD was good enough to allow me to do that. The reason is that instead of writing the test cases first, I just wrote the first one and then used it to implement and test the system testing feature. In other words, I decided to get the most complex part of the work done first. In case you are curious, this is what the System testing report looks like when tests fail and/or produce errors (I used dummy data here):
By the way, I forgot to tell you before, but the test cases have their own dedicated repo here: https://github.com/IndiePython/nodezator-system-testing. This will help us keep track of related changes. I expect the test cases the undergo much more edits than the SDD, so I didn't want the test cases to be part of the SDD as originally intended, otherwise the SDD repo history would change a lot over the time when in fact most of the changes would be on the test cases. Also, instead of calling the feature System testing with automated GUI interactions, I decided to shorten it to automated system testing which is simpler and although less specific is still helpful enough (I believe). Once I write and implement the remaining test cases I'll finally be able to wrap up my work on the system testing feature and finally start working on researching and implementing the topological sorting algorithm for graph execution in Nodezator. I also plan to use the opportunity to add some small quality of life features like a dialog to move the canvas to specific nodes using their id. This will help users find specific nodes when working in large graphs with many nodes. You'll notice the commit messages in the development branch are not much helpful, but that is on purpose. The reason is that a complex feature like automated system testing has no obvious steps of implementation, so there's really no use trying to care much for the commit messages at this point. Instead, since I understand the feature and what needs to be done, I just record each step as a general commits without much care. Once I'm finished, before merging the changes into the main branch, I'll just squash everything together into a single or handful of commits and write a helpful summary of the steps and changes performed. Also bear in mind that commits in branches other than main are always possible targets for edits, like amends or squashes. But I'll avoid touching commits that I mentioned recently in my posts like the e78885c that I mentioned above, at least until right before merging the changes into main. Regarding not meeting the deadlineI apologize for missing the deadline for the scheduled development work, specially after having extended it from February to March. I'd like to stress that I'm not neglecting my work on the Indie Python project. I missed the deadline due to two main reasons:
But don't worry, my work on the Indie Python project and Nodezator has been progressing non-stop. Although I can't always work full-time on the project, I have still been working daily (not only on software development, but other tasks needed to manage and maintain the project, like promoting the project online, solving issues, joining discussions, etc.). Also, please, bear in mind that, as an open-source project, quality is our priority. Rather than avidly aiming to meet deadlines and avoid delays, we prefer to spend more time where needed to guarantee the quality of our deliveries. That is a priviledge that commercial projects don't have. And one that we should make use of whenever needed, as long as we don't abuse it nor use it as an excuse for poor performance. Considering the time needed to finish and polish the system testing feature and that we'll still begin working on the topological sorting feature, I'll be extending the deadline yet again. This time, instead of extending another month (to April), will extend it to May. The reason is that, as I described, we still have a good amount of work to be done, so extending the deadline to May is a lot more realistic. If anyone disagrees or have anything to add, please, as always, feel free to share your opinion/concerns. They are always appreciated. Thank you all for your patience and selflessness. Even those who can't contribute with money still donate their time by submitting issues and new discussions and this also helps us make Nodezator a better application for everyone. However, just in case, let me ask again, as always: If you can help the project with a one-time donation or by becoming our patron, please consider doing so. You can see all the available options here: https://indiepython.com/donate Peace. |
Beta Was this translation helpful? Give feedback.
-
|
Hello, everyone! As always, I'm here to update you on my progress on Nodezator's development. The automated system testing feature/service is finally ready!It just needs to be populated with the needed test cases now, but all the needed components are right there! Here's a video demonstrating the finished version of the feature: automated_system_testing_finished.mp4Squashed commitsAs mentioned in the discussion tab for the Indie Python project, I like to squash all my intermediary commits into a single one. That's because such intermediary commits are only useful during implementation. They serve as incremental backups of my development work, but they do not represent meaningful slices of work, just midway spots towards the finished implementation. Once a feature is finished, they are just noise in my honest opinion. Here's a comparison of the difference between the main and development branches before and after the squash:
However, for the sake of transparency, I also attached a copy of my local repository before the squash to this post, so that you can inspect the individual commits if you wish. Here's the file 👇 Summary of all the changesThe resulting squashed commit representing all the changes has a message that summarizes all the changes made. I pasted this message below. commit message starts here add: automated system testing service Added several new subpackages/modules so people can now perform automated system testing sessions. The main additions were:
The nodezator/systemtesting subpackage has subpackages/modules to assist in system testing throughout the package. One of such subpackages is nodezator/systemtesting/reportviewer, which defines a system testing report viewer, a panel used to visualize the results of a system testing session, that is, which tests passed, failed or raised errors and much more. This report viewer also has buttons to export the results in several formats like .html, .pyl and .png. The nodezator/editing/playback/systemtesting.py module contains a form for users to set and trigger system testing sessions. In this form people can pick which test cases to perform and the speed. For now, the automated system testing feature/service has only 02 test cases, since we focused on finishing the system rather than defining all the needed test cases and populating it with them. In order to assist in this new feature, several other existing services were updated/incremented and some smaller ones were created. For users, the feature works like this: the user goes to the form in the menubar option "Playback > Perform system testing session", sets and triggers a system testing session, which starts performing the test cases selected. All tests are executed automatically. During the tests, the app moves automatically and the user must wait for the test cases to finish executing. Optionally, the user can abort the testing at any time by pressing the F7 key. If the user waits for the tests to finish, a report of the results is shown. The report can be revisited any time by selecting the menubar option "Help > Show system testing report". commit message ends here Appearance of report and different exportsAs explained in the commit message, the automated system testing report produced at the end of the automated system testing session can be exported to many different formats. The .png export reproduces the exact content and looks of the report. Here's the .png export of the testing session displayed in the video shown in this post, so that you can see what exactly the report looks like (the image may appear blurry in this post if the page shrinks the image to fit the post's width, but you can see the full clear image by right-clicking it and opening it in another tab):
The .html export is also attached to this post in case you want to see what it looks like. Here's the .html export 👇 The .pyl export ("pyl" stands for PYthon Literal) is just the raw data produced by the testing session as a Python literal (in this case we use a dictionary) and is also shown below in case you want to know which data is produced and how it is formatted. .pyl export contents 👇 { 'end_time': '2024-04-17 11:10:41.760387',
'playback_speed': 0,
'requested_cases': [0, 1],
'result': 'passed',
'start_time': '2024-04-17 11:10:17.167962',
'test_cases_stats': { 0: { 'assertions_results': { 'Single object in APP_REFS.gm.text_blocks is TextBlock instance': True,
'There must be exactly 8 items in the nodes iterable': True,
'There must be only one built-in node among the existing ones': True,
'There must be only one data node among the existing ones': True,
'There must be only one general viewer node among the existing ones': True,
'There must be only one operation node among the existing ones': True,
'There must be only one pygame-ce node among the existing ones': True,
'There must be only one redirect node among the existing ones': True,
'There must be only one snippet node among the existing ones': True,
'There must be only one standard library node among the existing ones': True,
"There's only one object in APP_REFS.gm.text_blocks": True},
'end_time': '2024-04-17 11:10:31.874218',
'result': 'passed',
'start_time': '2024-04-17 11:10:17.258992'},
1: { 'assertions_results': { 'There must be no items in APP_REFS.gm.nodes': True,
"There's no objects in APP_REFS.gm.text_blocks": True},
'end_time': '2024-04-17 11:10:41.760087',
'result': 'passed',
'start_time': '2024-04-17 11:10:31.963199'}},
'utc_offset': '-0300'}Next step: Topological sorting for graph executionNow that the automated system testing feature is finally finished, the only missing thing is to populate it with the needed test cases. I already have a list of many test cases defined on paper. For now I'll probably only add a handful of them. The remaining ones will be added later, little by little. This is so because I'd like to start the research and implementation of the topological sorting feature for Nodezator ASAP, in order to have all the features ready until the end of May, as scheduled. Nodezator 1.5I'm excited for this release because although the features to be released are mostly backend work (system testing and graph execution), they both represent large steps in the quality of Nodezator. I won't comment on the topological sorting algorithm, since I already discussed it, although briefly, in the opening post of this discussion. However, regarding the automated system testing feature, there's something which will fundamentally change in Nodezator once the feature is released in Nodezator 1.5: we'll finally be able to get rid of the
I never released pre-release version of Nodezator, that is, versions like I actually marked the releases until now with a beta classifier ( Of course, I might still make use of pre-releases some time in the future, in which case they will be properly marked with the Finally, I'd like to highlight again the benefits brought by the automated system testing and the stability it helps ensure:
Thankfully, even before releasing Nodezator to the public, several of its subsystems already underwent several refactorings. However, due to its inherent complexity and number of subsystems, I've been postponing refactoring changes. More precisely, all other things being equal, any new implementation/change should be followed by at least a general refactoring pass. Additionally, even when no change was being make or planned, general refactoring efforts should also be scheduled. This may seem far from common practice in software development, where people often focus on releasing new features to the detriment of quality/maintainability of the system, but I actually did this with some regularity before releasing Nodezator to the public and thanks to that Nodezator reached a relatively simple and maintainable design with much room for growth. Since Nodezator was released, however, I've been focusing on performing important fixes and implementing essential features in order to help users. But the increased speed with each new changes and additions have been made, and the resulting growth in volume of the codebase, require a great deal of refactoring to ensure the continued maintainability of the app. And all these needed changes/additions require the system to be thoroughly tested at each step of such changes/additions. That's why the automated system testing feature is so crucial and I'm so excited and relieved that it is finally ready and should be released soon. Changes in how I allocate my time and effortBefore wrapping up this update, I'd like to leave this link to another relevant discussion: regarding a change in how I allocate my time for the Indie Python project. I'd like to say in advance that the amount of time and effort I dedicate to the project won't change. In the linked post I just discuss how I intend to reallocate such time from now on. I'll still continue working daily and as much as always on the Indie Python project. Wrapping upThank you all again for your attention. As always, let me know if you need anything or have any questions. I'm always eager for feedback. Also, if you didn't do so already, please consider becoming our patron. You can also making one-time donations or contribute in other ways, all summarized here: https://indiepython.com/donate Peace |
Beta Was this translation helpful? Give feedback.
-
|
Hello, everyone, Update on scheduled workI Just finished implementing the topological sorting technique for graph execution in Nodezator. I still need to refactor the code a bit, but the implemented solution is ready and functional. The commit from the development branch where you can find the implemented feature is e8f0fea. Bear in mind that at some point I'll squash the commits related to this feature, both the existing ones and the future ones from refactoring, so if by the time you are reading this you can't find this commit, it just means it was squashed (I'll probably upload a local copy of the repo before the squash so anyone may inspect each commit if desired). As mentioned in the first post on this discussion, my work on implementing topological sorting for graph execution in Nodezator began by translating one of the pseudocodes documented in this wikipedia page into actual code. The page lists the Kahn algorithm, a depth-first-search-based algorithm and parallel algorithms. Of course, as I also discussed in the first post, it is too soon for us to worry about parallel execution (and other forms of asynchronous execution) due to the complexity of the endeavour and the more urgent need of other more basic features (check the final subtopic on the first post for more info on this). Additionally, as discussed more recently with another user, implementing asynchrounous execution in Nodezator requires an inordinate amount of research and design work. Therefore, of the two algorithms remaining, I picked the depth-first-search-based algorithm for implementation. Both algorithms are relatively simple and straightforward, but the data structures and data modelling used by Nodezator are more straightforwardly implemented using the depth-first-search-based algorithm. More specifically, the Kahn algorithm would require Nodezator to create and keep track of 02 additional groups of objects: a set of nodes with no incoming edge and a collection for the edges themselves. Nodezator doesn't even represent edges as individual instances, it only tracks the nodes and the parent-child relationships between their output sockets and the input sockets from the next nodes in the graph. This is the pseudocode of the depth-first-search-based algorithm exactly as documented on the wikipedia page: The algorithm was also simplified in Nodezator, because of the pre-existing feature to prevent cycles from being formed, as mentioned in the first post on this discussion. In other words, we operate under the assumption that cycles are never formed in Nodezator and can thus ditch the temporary marking used in the algorithm: L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
select an unmarked node n
visit(n)
function visit(node n)
if n has a permanent mark then
return
- if n has a temporary mark then
- stop (graph has at least one cycle)
- mark n with a temporary mark
for each node m with an edge from n to m do
visit(m)
- remove temporary mark from n
mark n with a permanent mark
add n to head of LAs we also discussed on the first post, I'll soon be researching the solutions from the NetworkX and igraph libs recommended by Mr. Alexander to see if our own solution can be improved or if it is worth adopting a solution from those libs. However, I reiterate that due to several factors listed on the first post, implementing our own solution is (not always, but usually) better for several reasons. For this feature, particularly, it is very likely that we'll keep the current version and at most improve it with insights from the other libs. To be more precise, since Nodezator is a full-fledged app with a lot of state, objects and data to manage/keep track of, a custom solution can make more effective usage of the available data and take into account several other operations/admin tasks involved in the process of executing the graph. For instance, not all objects in a Nodezator graph are executable, like redirect nodes. Since redirect nodes are used just to pass data forward to other nodes, we need to adapt the original algorithm once again to take them into account. That is, we can only add nodes to L that are not redirect nodes. Something like this: L ← Empty list that will contain the sorted nodes
+S ← Set of redirect nodes
while exists nodes without a permanent mark do
select an unmarked node n
visit(n)
function visit(node n)
if n has a permanent mark then
return
for each node m with an edge from n to m do
visit(m)
mark n with a permanent mark
- add n to head of L
+ if n not in S:
+ add n to head of LThis is only a small example of the stuff Nodezator has to consider before even sorting the nodes, let alone executing the graph. Among other things, we must also...
Again, this doesn't decrease one bit the relevance of Mr. Alexander's recommendation. I reiterate what I said in the previous post: checking other solutions is the scientific thing to do and how sustainable progress is achieved. If you look more closely on the wikipedia article, the pseudocode for the depth-first-search-based algorithm documented there is itself based on the solution by Cormen et al. from the 2nd edition of their book, entitled Introduction to Algorithms. The authors and their book are thus credited in the source code. Tests and resultsHere are a few examples of graphs on which I tested the solution. Each image is followed by the list of the nodes as sorted by the implemented algorithm. Each node represented by their id (which can be seen on the body of the nodes): ➡️ Sorted nodes: 0, 1, 2, 3 ➡️ Sorted nodes: 4, 3, 0, 1, 7, 8, 6, 2, 5, 9 ➡️ Sorted nodes: 0, 5, 7, 3, 4, 10, 11, 13, 9 Note that the data nodes are not on the sorted list: ids 2, 6, 8 and 12. As I said before, not all nodes in Nodezator are executable. Data nodes just hold data, they don't depend on any other nodes. Therefore, they are not sorted nor executed. I just pass their data forward to the next nodes and sort the remaining ones. Same thing when the graph has nodes in callable mode (nodes that just represent references to the callables that define them): they don't need to be executed, so they are not sorted. We just pass the reference forward to the next nodes. Next stepsHere are a few of my next steps, more or less in the order I intend to take them:
I'm not sure about implementing the QOL features now though, I may implement them only after the next release. At some point in the month I also intend to get back to my work on Bionic Blue, but just for a few days, as finishing the scheduled work for Nodezator on time is my priority. I'd like you all to bear in mind that, given the ever-present possibility of new micro tasks popping up at any point during my scheduled work for Nodezator, there's always the possibility of the deadline being extended a bit. However, I intend to avoid this outcome as much as possible and, given that both intended features are already implemented and functional (automated system testing and topological sorting for graph execution), a possible delay should likely take no more than a week or so. Additionally, the last time I extended the deadline I was careful to include this month in it, taking into account the complexity of the remaining work and avoiding underestimating the time needed to finish it. In other words, I believe we are on our way to finish things on time and a further delay, if any at all, shouldn't take long. Thank you all for your attention and patience. As always, all feedback and questions are appreciated. Also let me know if you need anything. Peace. |
Beta Was this translation helpful? Give feedback.
-
|
Hi @KennedyRichard. This is great! I'd recommend using breadth-first search instead of depth-first search. This will make it easier to implement parallel execution in the future if you decide to do so. With breath-first search you can arrange the ordering of the nodes into "layers". For your last example, the output should look something like this: I looked around and found 2 good resources for this algorithm: Also, what will Nodezator do if there is a cycle in the graph? |
Beta Was this translation helpful? Give feedback.
-
|
Thank you for the recommendation and links. Such benefits indeed seem worth it. When I made a quick web search to know a bit more about the depth-first-search-based algorithm, I actually stumbled upon the breadth-first algorithm, nothing in the material I read mentioned its application for topological sorting, which is why I didn't consider it. I'll check the links when I get back to work tomorrow, since today is Sunday.
In Nodezator, as I said before, connections that would otherwise cause cycles are not allowed to exist. In other words, users cannot introduce cycles on the graph. That is why we operate under the assumption that no cycle will ever be present. If you didn't do so already, I recommend trying it yourself. A connection won't be established if it causes a cycle. Of course, among the test cases that remain to be implemented for the automated system testing, I'll also include one to always put this feature to test, ensuring it is always functional. However, maybe you are considering the possibility of a user changing the .ndz file manually? That is a fair assumption, no doubt. Nonetheless, it is also a problem with an inordinate amount of other problems branching out from it. For instance, the user may accidentally delete vital data from an existing node, or change such data leaving the data corrupted, just to name a few problems. If we consider each implication, the problem quickly becomes intractable. That is, the implications are enough to require a high volume of new code in order to cover all possibilities. And yet, such problem stems from something which we can't control, which is the user autonomy to change the .ndz data. Considering all of that, it is far less expensive (in terms of time and effort), to deal with such problems by:
Even so, such measure would only be something to consider if problems with cycles on graphs somehow begin popping up, but to this day we haven't had even a single one. So, at least for now, I think it is far more reasonable to follow the principle that "a programmer should not add functionality until deemed necessary." (wikipedia). Please, if there's anything else you'd like to know about all of this, don't hesitate to ask. My job is to guarantee that users/contributors/patrons feel confident about the stability and reliability of the app and its features/subsystems. I can further explain the mechanism by which cycles are prevented in Nodezator and point you to the source files where it is implemented. Have a nice weekend. Footnotes
|
Beta Was this translation helpful? Give feedback.
-
Managed to implement BFS topological sortingMr. Alexander, today I updated the custom solution to use the breadth-first-search-based algorithm as you recommended. This morning, after looking into the links you shared and doing some research, I could confirm that your recommendation is indeed preferable. It is true that, since Nodezator can't take advantage of parallel execution yet, for practical purposes both the depth-first-search-based (DFS) and breadth-first-search-based (BFS) topological sorting algorithms are equivalent. That is, in the end, we are just executing the nodes one by one anyway. However, the format provided by the BFS algorithm may indeed be more useful for us in the future for parallel execution or whichever asynchronous paradigm(s) or mix thereof we may adopt in the future. Put simply, it is more insightful when it comes to perceiving different pathways we can travel during execution. I looked into the links you sent me and also did a quick research on my own. This stack exchange answer was especially helpful. Even the comments contesting its validity helped me gain insight on the problem. In fact, I gained insight not only on the algorithm, but also in the Kahn algorithm that I mentioned briefly in my update from Saturday (despite the fact that Kahn's algorithm isn't BFS-based). I mentioned in that update that I didn't pick Kahn's algorithm because of how data is modelled/managed by Nodezator. However, after reading the materials, I managed not only to come up with ideas to implement it, but also to see its resemblance to a breadth-first-search-based algorithm. In other words, the Kahn algorithm, that works this way (wikipedia): ...is very similar to breadth-first-search-based algorithm. In fact, converting it into a BFS algorithm is relatively simple. For instance, just by removing the lines indicated below (the for-each-loop) we already prevent the nodes deeper in the graph from being visited first (the algorithm doesn't work in that state yet, but this is just to give us a glimpse of the effect of such simple change): L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is not empty do
remove a node n from S
add n to L
- for each node m with an edge e from n to m do
- remove edge e from the graph
- if m has no other incoming edges then
- insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)From that point onwards, and with help from the links I got from you and my additional research, I managed to implement a custom BFS-based topological sorting solution for Nodezator. It is already available in the commit 30debe6. Test and resultsSince the links you provided also had examples on how to achieve the same results with the NetworkX library I also tested it. Both my custom solution and the NetworkX solution produced the same results or equivalent results. For instance, for the image of the
I also tested all the other graphs from the update post and the results were also equal/compatible. Of course, if the order of the nodes in each generation was important, I could have also passed each generation to Python's built-in In other words, our solution is also effective/reliable. Our custom solution is also faster. Here's the sorting time for the same
This is probably due to the combination of many libraries and techniques employed by NetworkX and the fact that, I think it is safe to assume (since I didn't inspect its source), NetworkX has to perform the extra checks needed to guarantee the graph has no cycles. I also want to test the solutions in larger graphs, but didn't do so yet because I have to copy my larger .ndz files from my laptop to my desktop. Nonetheless, at least for now, I'm not really worried about the difference in speed. We don't even have benchmarks or speed requirements to fulfill. For now I'm only concerned with efficacy and reliability, which our custom solution has, as demonstrated by the generations produced. I just measured sorting speed for the sake of completion/curiosity/learning. If you, or anyone reading this, want to reproduce my test in your machine, just download Nodezator's def _sort_nodes_for_execution(self):
"""Sort nodes to be executed.
Uses a breadth-first topological sort algorithm.
"""
### clear list where references to the node generations to be
### executed will be referenced in order
self.clear_node_generations()
### reference objects locally for quicker and easier access
## operation to append node generations
append_node_generation = self.append_node_generation
## set of nodes for execution
nodes_for_execution = self.nodes_for_execution
### send ids of nodes for execution to their direct children,
### so they can keep track of their indegree
for node in nodes_for_execution:
node.send_id_to_direct_children()
########## execution time and results of NetworkX #############
### NetworkX
import networkx as nx
from time import time
extend_node_generations = self.node_generations.extend
start = time() # time tracking starts
edges = (
(ascendant_id, node.id)
for node in nodes_for_execution
for ascendant_id in node.input_source_ids
)
extend_node_generations(nx.topological_generations(nx.DiGraph(edges)))
xdur = time() - start # time tracking ends
print()
print('NetworkX solution:', friendly_delta_from_secs(xdur))
print('Generations:', *self.node_generations)
self.clear_node_generations()
############################################################
########## execution time and results of our custom solution #############
### while there's nodes for execution, keep creating and appending
### new node generations from the nodes with indegree == 0, always
### decrementing the indegree of their direct children
start = time() # time tracking starts
while nodes_for_execution:
node_generation = [
node
for node in nodes_for_execution
if len(node.input_source_ids) == 0
]
append_node_generation(node_generation)
nodes_for_execution.difference_update(node_generation)
ids_to_remove = {node.id for node in node_generation}
for node in nodes_for_execution:
node.remove_source_ids(ids_to_remove)
our_dur = time() - start # time tracking ends
print()
print('Custom solution duration:', friendly_delta_from_secs(our_dur))
print('Generations:', end=' ')
for gen in self.node_generations:
print([node.id for node in gen], end=' ')
print()
print('-----------')
print()Then launch Nodezator, open any .ndz file you want and execute it (if you didn't open Nodezator via terminal, execute the graph with Shift+F12, so the printed text shows on the app's screen). Ignore the results printed the first time because NetworkX sorts much slower (~200 milliseconds) the first time around. This is probably because the operations involved need extra setups the first time they are executed. I think that's all I wanted to share for now. Again, thank you for the suggestion, Mr. Alexander. Peace. Footnotes
|
Beta Was this translation helpful? Give feedback.
-
|
This is great! I'm glad you were able to implement it so quickly. And the fact that your solution is so much faster than NetworkX is a huge plus. Yes, the order of the nodes in each layer doesn't matter. Great work, as always! |
Beta Was this translation helpful? Give feedback.
-
|
Hello, everyone, I'm here with another update regarding my progress on the scheduled development work for Nodezator. All the work can be found in the development branch of the repo. As can be seen from the few replies to my last update, Mr. Alexander recommended updating the topological sorting algorithm so it was based on a breadth-first search algorithm rather than the original depth-first-search-based one. I accepted the recommendation after assessing its merits and implemented the corresponding changes. All this process was documented in the aforementioned replies, so you can check them if you want the details. In addition to this change, I also worked in some long-awaited quality of life features for Nodezator that were essential to solve some common problems users were running into when working on large graphs. As shown in the video below, I implemented a small dialog to jump to an existing node by providing its id: demo_jump_to_node_by_id.mp4You can find it in the Graph > Jump to node by id menubar command or by pressing Shift+J. This will help people working on large graphs to find problematic nodes. As you may know, currently, whenever a graph raises an error during execution, a dialog appears providing further instructions and informing the id of the node. However, users working on large graphs may find it hard to find that specific node. Once this feature is released, users won't have this kind of problem anymore. I also implemented the Bird's eye view feature. It displays a representation of the entire graph that fits the screen, so you can see the whole graph at once. You can also use it for navigation: keeping the mouse pressed while hovering the view will cause the screen to scroll to the respective spot in the actual graph. That is, that spot will appear centered on the screen. The video below demonstrates it in action (notice, for instance, when the mouse hovers over the small text block icons, the respective text blocks in the actual graph appear behind the view at the center of the screen): demo_birds_eye_view.mp4You can find it in the Graph > toggle bird's eye view menubar command or by pressing B (pressing B again or Escape exits the view). This will also help people working on large graphs, as they'll be able to instantly jump to and inspect any spot on the graph. The corresponding commits are labeled as "wip" because I still need to refactor some code and put the finishing touches to the feature, but the feature already works. Note that the view has just enough transparency to allow the user to see what's behind it. In my tests, using too much transparency turns everything into a mess. It becomes difficult to distinguish the elements of the view from the elements of the actual graph at a glance, specially the connections. Additionally, toggling the view on and off by pressing B repeatedly is very quick and easy, so users can do just that when they need to see what's behind the view more clearly. I'm considering exposing the transparency of the view as a user preference setting, so users can adjust as desire. I'm not sure for now, though. I'll probably wait for users' feedback. I also improved the appearance of the "not found" illustrations. They are now generated with SVG, resulting in smooth strokes. Check the difference in the image below:
Another small changes is on the backend. In summary, I replaced how the app picks a location on the disk to save data like user preferences, recent files, etc. Now, instead of using my custom makeshift solution it uses a solution provided by the pygame-ce library (which already is a Nodezator's dependency, so it is a very tiny change). Such solution is the I also fixed a bug in int float entries that caused them to execute a specific command twice, when they should do it only once. Thankfully this bug doesn't disrupt they way Nodezator works nor how the int float entries are supposed to work, which means there was never any harm to users nor any need for further action. The fix simply prevents the command from executing a second time. Now, almost everything I wanted for the release is finished! Yay! The only things remaining are:
Again, as I said in the last update, even if we have a delay I expect it to be brief (a couple weeks at most). Thank you all for your attention and patience! As always, let me now if you have any questions or feedback. Have a nice weekend! Peace |
Beta Was this translation helpful? Give feedback.
-
|
Hello, everyone, This update will be a bit shorter than usual, because as you know, all the scheduled features and the additional quality-of-life features are implemented already, so the changes since my last update are mostly back-end development. Stuff like refactoring, fixes or improvements. Although there are some improvements on GUI/visuals/user experience as well. Final touches for the bird's eye view featureFinally finished the final touches on the bird's eye view feature. As always, I squashed all the commits into a single one. For the sake of transparency, you can find a copy of my local repository in this Google Drive link: https://indiepython.com/local-commits. This way you can inspect the micro changes I made along the way. This copy won't be available there forever, but I intend to leave it there for a long time, at least a month or so, but likely more. If you want to inspect the commits, just download the zipped repo and execute a
Regardless of all this, the most recent changes will always be in the development branch (or in the main branch, when I merge the development branch with it). Other changesBelow I list the other changes. All these changes have corresponding commits in the development branch, so you can check the commits there for more info, since I usually comment the commits in detail. Changes on the back end
Changes on GUI/visuals, user experience
Last couple weeks before Nodezator 1.5's releaseIdeally we'd be releasing within a day or two, but as I said on the previous update, this extra couple weeks were a possibility given the amount of micro tasks involved. Regardless, we are finally in the last couple weeks before the release of Nodezator 1.5, which is a good thing. The next week or so I'll be:
Then I'll need a few extra days for release/package management tasks, like
As always, let me know if you need anything clarified or need help with anything. Have a nice weekend. Peace. Edit: Oh, one more thing (almost forgot): I already began writing a list of the missing test cases, you can see it here: https://github.com/IndiePython/nodezator-system-testing/tree/development. Implementing them should be very quick, since all the underlying services are implemented already. However, I won't probably implement all of them in that list for this 1.5 release. More precisely, just like I'll finish the software design document gradually after the 1.5 release, I'll also implement all the other missing test cases gradually after the 1.5 release. This is so because listing, writing and implementing all test cases will take a lot of time. I'm estimating we'd need nearly a hundred test cases to cover Nodezator's functionality, maybe more. I can't tell for sure until the software design document is finished and all Nodezator's functionality/features are properly mapped. This is why such implementation has to be done gradually. Even so, many of the most basic/fundamental functionality should have test cases available for the 1.5 release, which will help development a lot going forward. |
Beta Was this translation helpful? Give feedback.
-
|
Hello, everyone, First of all, I wanted to say that I expect no more delays, so 1.5 should be released in a few days. I'm actually still finishing the implementation of the test cases that will make into 1.5. Remember: as I said in a past update, the quantity of test cases to implement is massive so only some would make into the 1.5 release. Also, defining all of them requires that I finish the software design document. When it comes to software development, even well-defined processes can end up taking more time than anticipated. These final steps have been like that, demanding extra time. Because of that, if everyone agrees, I'd like to postpone the research on NetworkX and igraph until after the 1.5 release. I'll actually do it right after the release, publishing any eventual changes that may come from it as patches. The reasoning is that all the scheduled features are already implemented and changes that may come from that research, if any at all, will change the implementation under the hood, but not its behaviour or how users interact with it. We already have a functional topological sorting algorithm implemented that, as we saw in a previous post, yields the same output as NetworkX's (which is an established library in this field). So we can say with confidence that any improvements in our implementation that may come from the research, if at all, will not change how the users interact with it. In other words, there's no reason for us to make the users wait any more. The development branch already has features ready to be used that will improve the users' workflow. We already delayed the release enough (speaking of which, I updated the title of this discussion to read "Jun 2024", since we are already in June, despite being so close to releasing our work). Another important point is that this research is not something I want to rush. As an open-source project and the community that gathers around it, we must not rush any kind of research. We are not constrained by budget or deadlines like commercial organizations often are, so we should take advantage of this and really value proper research and development. So what I propose is this:
That's all I wanted to share for now. As always, feedback, questions and constructive criticism is always welcome. Also remember you can follow/inspect my work in the development branches of the related repos: Nodezator's dev branch and the dev branch for Nodezator's system testing. Have a nice weekend! Peace |
Beta Was this translation helpful? Give feedback.
-
|
Hi @KennedyRichard, I see no need to explore NetworkX any further. As you said, you already have a correct implementation of topological sorting which is already faster than NetworkX. In theory, the same function in iGraph could be even faster because it's a C library. But I remember that you prefer not to depend on unnecessary libraries. Is there something you feel is missing from your current implementation? |
Beta Was this translation helpful? Give feedback.
-
|
Hello, Mr. Alexander! Thank you for the feedback. It is much appreciated. Even more so since you were the one that started the conversation regarding the other libraries. Considering both my points and yours, indeed, you are right in that the research is not needed. We already have a functional implementation with the same output as NetworkX's equivalent and superior speed. It is not lacking anything that I can think of. And, despite our expectation that iGraph is faster, we don't actually have speed requirements to meet, so our native solution is preferable to introducing an additional dependency. Despite being unnecessary, though, it doesn't mean the research isn't desirable, or that it may not result in relevant changes to our original solution. I guess in the end this boils down to how basic research is still important despite applied research having more appeal to most people (I assume). Taking all that into consideration, I suggest this, then: after releasing 1.5 in a few days, I'll postpone this research indefinitely (at least for now) and start my work on the next tasks/features for Nodezator, including the tasks I listed yesterday (finishing the remaining test cases and the design document). In the future, once Nodezator is in a more complete state (with all basic and more urgent features implemented), we can then reschedule this research and other important ones that may pick our interest along the way. I was actually excited about taking a deeper look into NetworkX and iGraph, but we do have a lot of higher priority work to do. |
Beta Was this translation helpful? Give feedback.
-
|
Hello, everyone! Nodezator 1.5 is finally out! Thank you all for your patience! Just execute Release info: 👉 https://github.com/IndiePython/nodezator/releases/tag/v1.5.0 👈 I'll keep this discussion open for a few extra days in case anyone wants to share any feedback. In a few days I'll also open a new discussion like this one, in order to list a few features that are good candidates for being implemented next and gathering your suggestions as well, so we can start planning the next round of development work. Have a nice weekend! Peace |
Beta Was this translation helpful? Give feedback.
-
|
Hi @KennedyRichard, congratulations on this big milestone! Recently I found another node-based Python project and I wanted to share it with you: |
Beta Was this translation helpful? Give feedback.
-
|
Thank you for your kind words and continued support, Mr. Alexander, both as a patron and an engaged member of the Indie Python community. It is not a stretch to say Nodezator wouldn't be the same without your participation. This project you shared is very interesting to say the least, specially for existing in the form of an ETL tool. Never heard of it before. That's a great find. Not only that, but one of the rare kind that generates code as well. |
Beta Was this translation helpful? Give feedback.
-
Hello, everyone,
Every time I'm about to dive into working on a changes and new features I create a discussion like this in order to...
Introduction and features to be implemented
This is an announcement regarding the planned development work for Nodezator's next version: 1.5.
Everyone is not only welcome but encouraged to take part in this discussion, including feedback, opposing opinions, etc. Nothing in the project is set in stone until properly discussed.
I'd like to keep the pattern of implementing more than one feature for each new version, but not as many as in last version (1.4). For 1.4 we actually only originally planned a few features, but ended up changing our plans halfway due to various circumstances.
However, implementing too many features at once causes new versions to take too long to be released, which is why I want to keep the original plan of implementing only 02 or 03 features each time. This way the new versions take less time to be published and it is easier to discuss things with the community.
The features for next Nodezator version (1.5):
Automated GUISystem testing (finish implementation);Automated GUISystem testingThe importance of
automated GUIsystem testing for Nodezator has been stressed several times across different conversations on Discord and GitHub so I won't go too deep here.Nodezator, being a node editor, is a software with many features, tools and a varied workflow. There are innumerable actions that users can take and underlying systems supporting it. Additionally, being an open-source software project, it is subject to external development work being merged into it. Even if there was only my own work being merged into it, the use-cases/systems are just too many to be manually tested by a single person. In the last release, despite my careful testing literally hundreds of times, I still couldn't manually test every possible action and it resulted in some nasty bugs being introduced (bugs that were already solved in the last few patches).
Also, because Nodezator offers a node-based interface to Python, its usage is virtually unlimited. To the point that I believe it can be considered a meta application rather than an application per se. With its increased adoption over time, it is crucial that we provide a stable rock solid experience for the users. Without an
automated GUIsystem testing system with a comprehensive set of tests, we simply cannot guarantee that changes implemented by me or merged from PRs will not introduce bugs.Because Nodezator has all this complexity and scope of usage but not
automated GUIsystem tests, I never removed the "Release Candidate" label from the splash screen of the app since its release last year. However, Nodezator has been stable since its release, with the occasional bug being dealt with as soon as possible. However, in order to remove such label and guarantee the complete stability of the app, theGUIsystem tests are crucial. This way we'll be able to keep developing Nodezator with confidence, knowing that no bugs (or at least no substantial/usage-deterrent bugs) will be introduced.Given the urgency and importance of this feature my conclusion on the matter is that we do need to make this system available as soon as possible.
Thankfully, most of the logic is already implemented, since we originally intended to release this feature in the last version and already done most of the work. It can even be seen in action in this video (it shows the input playing feature, which is the basis for
automated GUIsystem testing):input_play_demo_Y2023M03D15.mp4
I'd also like to remind that
automated GUIsystem testing is actually part of theplaybackGUI automation feature. TheplaybackGUI automation feature is a larger feature that consists of 04 features/functionalities/subsystems, roughly represented below:--- title: GUI automation feature --- flowchart LR A["Input recording"] --> B["input playing"] --> C["System testing"] & D["Demonstrations mode"]That is, input recording and input playing are used to support
automated GUIsystem testing and the demonstration mode.Input playing and recording already have enough functionality to support
automated GUIsystem testing. In fact, the only reason I didn't releaseautomated GUIsystem testing yet is because I'd like to complement such functionality to support extra use-cases.The demonstration mode on the other hand is meant to be a more fancy version of input playing with additional instructional elements like text and figures describing user actions. It is not a priority at all though, specially in comparison to
automated GUIsystem testing and other features not related toplaybackGUI automation. Because of this, the demonstration mode willonly be implemented far into the futuretake a bit more time to be finished and exposed to users.Topological sorting
This is a feature request made by Mr. Alexander @OlegAlexander. As the maintainer of Nodezator and after considering the merits of his request I decided to accept it.
However, nothing in the Indie Python project or Nodezator project is set in stone until properly discussed. Even established decisions can be changed if supporting evidence is presented at a later point in time. For now though, I'm convinced Mr. Alexander's request will indeed greatly benefit Nodezator. Of course, I'll be presenting his request as well as the arguments that led me to accept it in the rest of this subsection.
A while ago Mr. Alexander brought to light the need to update Nodezator's graph execution algorithm and mentioned the topological sorting technique as a proper candidate for adoption. Even before that, he had also mentioned it, although briefly, in an unrelated conversation on discord (the conversation was about a design proposal made by me that ended up being rejected).
After a quick web search I found out that the topological sorting has many applications in computer science and software engineering. In summary, it is a established key technique to solve many different kinds of problems. The most concise and straightforward explanation I found was this answer on Quora (as I said, I just did a quick research for now):
In my conversations with Mr. Alexander, he also mentioned topoligical sorting can be used for finding cycles in the graph. In case someone doesn't know, cycles are not allowed in directed acyclic graphs (the kind of graph used by Nodezator and many other node editors). In other words, the data must have a clear direction and never circle back to a node that was already visited. Among the materials I skimmed, many mentioned that feature of topological sorting as well. As I explained to Mr. Alexander in one of the conversations linked above, this specific feature, though, is not needed in Nodezator because it already has a mechanism that simply doesn't allow any cycle to be formed (this kind of mechanism is called Poka-yoke or Behaviour-shaping constraint). Even so, this fact doesn't nullify the other merits of the topological sort and is only mentioned here for completion (and because this knowledge may be useful to anyone reading, which is one of the purposes of an open source project).
Mr. Alexander also brought to my knowledge the existence of third-party libraries that provide implementations of the algorithm like NetworkX and igraph. On the occasion, I shared my stance on avoiding increasing the number of external dependencies for Nodezator. This is actually something that I avoid doing on any kind of work. In my experience and observations, unnecessary dependencies increase the cost of maintenance over time, because they simply increase the number of things with which we must keep compatibility. Dependencies, when not absolutely needed, are just more work.
Although I believe the reason I just presented is already strong enough to justify my stance on this, there are additional valid reasons to be considered. One of such reasons is that using an external library requires us to shape our code/data to be able to communicate properly with the external library. Nodezator is an app, not a framework or library, so the way we store and manage our graph data is tailored to meet its needs (instead of using a general format, like a Python collection, for instance). We do so in pursuit of both performance and easy access to the data. Using an external library would likely require additional steps to prepare the data before we could pass it to the external library to be processed. In all fairness though, although likely, at this point in time it is speculation on my part, since only a complete research on the libraries mentioned could confirm that.
Another of such additional valid reasons not to use an external dependency is the possibility of customizing our solution. The topological sorting solution requires us to visit all nodes in the graph to define the order which they can be executed. However, we can actually use the visit to do more things, and thus make our solution more efficient. I actually have a real need for this: while visiting each node to define the topological sort, I'd also like to check whether the node is missing any data.
That is, if a node has a socket without any data (no widgets or connections), then the node cannot be executed and thus the graph cannot be executed. When this happens, if we are using a custom solution we write it so that when the node is visited we check this condition. If such condition is found to be true, we can then abort the calculation of the topological sort altogether, thus saving time.
The execution of the graph that would happen after the calculation wouldn't even start (since the graph is missing data and can't be executed anyway). We'd also notify the user of the problem. Using an external dependency would likely require us to iterate over the nodes once more to check this. In summary, by using our own solution we can customize the behaviour as much as we need, as long as we calculate the topological sort properly as defined by the algorithm to be used.
There are still 02 more things that I'd like to stress regarding my stance to keep the number of external dependencies as small as possible. First, that it is actually OK to add a dependency when it is needed. If some feature proves to be too difficult to implement or we don't manage to achieve an effective solution despite our best efforts, then we do have a legitimate reason to include a new dependency.
Second, this stance doesn't mean we must shut ourselves off from external knowledge. Quite the opposite. Although we should prioritize developing and using our own solution, it would be unscientific and counter-productive not to check the existing ones. Researching existing solutions before creating our own is the scientific thing to do and how real sustainable progress is achieved. In practice, this means that I will study and inspect the source of the libraries mentioned by Mr. Alexander. Of course, as he aptly pointed out, if we ever use something taken from those libraries, we must properly credit the source.
On the approach
Regarding
automated GUIsystem testing, there's not much to discuss, since it is already mostly ready, so I'll just implement what is missing and refine it. I'll then make a list of the behaviours I want to test and create the tests.In the case of topological sorting, because it is such established solution in many different areas, there are algorithms available on the web (and they can probably be easily found in other sources as well, like books and papers). The wikipedia article on topological sorting linked at the beginning of this post, for instance, has a section presenting usual algorithms used as detailed pseudocode, ready to be translated into actual code. This will probably be my first source of info in attempt to implement the algorithm in Nodezator.
Additionally, topological sorting is actually a kind of traversal problem. Graph traversal is something that I use often in the Nodezator source to solve many problems. Things like checking whether a connection would create a cycle in the behaviour-shaping constraint mentioned earlier. I also suspect that the average developer, upon inspecting the available algorithms in the wikipedia article we just mentioned would also find them relatively easy to implement. Even so, these are just mere observations for the sake of completeness and are not valid reasons for underestimating the implementation.
In addition to implementing a custom solution based on the available algorithms, I'll also research and inspect the solutions from the libraries recommended by Mr. Alexander to see if there's something that must be considered for our custom solution. During the entire process, I'll be posting new comments in this discussion and taking into account feedback written by others.
On the timeline
Regarding the timeline I intend to follow for finishing the implementation of
automated GUIsystem testing and implementing topological sorting, I originally wanted to start right away, however, at the present moment, a series of factors prevent me from doing that.First, since I started the Indie Python project and released Nodezator on June last year (almost 16 months ago) I have been working nonstop on the project without vacation or any kind of extended rest except for the occasional holiday here and there. Thankfully, I've successfully established a healthy and productive work routine that allowed me to persist through all that without any observable issues. However, health is not something to be taken lightly and a period of extended rest is important for the mental and physical health of any human.
Even so, as the maintainer of an open-source project, it is important for me to be constantly available for people that occasionally interact in the available channels and repository. People seeking help on discord, reaching via social media networks or publishing issues, discussions and pull requests on GitHub. Because of that, instead of taking an extended vacation, I'll actually take:
The couple weeks off in this month will begin as soon as I finish reviewing/merging the pending pull request #53. During the couple of weeks off, I'll still check all the social media, channels and repositories of the project daily as I usually do. I'll answer anything that is urgent and postponing anything that isn't. I won't be doing any development or content production work for the Indie Python project in those days, though.
The second factor is that the Bionic Blue game, which is a integral part of the Indie Python project has had its development paused for far too long. Once I'm back from my vacation this month, I'd like to put at least a month of work onto it. I've been working on Nodezator since March of this year and recently released several features with the new version, so I think putting one month of work on Bionic Blue is only fair. Although I didn't have the time to discuss it properly with the community, the Bionic Blue game actually plays a strategic role on the project. It isn't part of the project just on a whim.
It serves not only as a fun way of promoting the project, but also has a lot of instructional and operational value for the Indie Python project. Instructional because its source, released to the public domain just like Nodezator, offers a lot of value for people willing to learn how to build game and simulation systems (although it is only a prototype at the moment). Operational because it provides a lot of real problems that result in new ideas, features and systems/services for Nodezator. Games, when taken seriously, serve as a powerful driver of innovation. A quick research on the web will reveal to you how much innovation game systems have directly or indirectly help produce over the years. Nodezator is one of such products. I was only able to create Nodezator due to my programming and game making hobbies. Integrating game development in open-source projects, when properly managed, promote fun, relaxation and creativity.
So, in summary, once I publish this discussion, I'll start working on reviewing PR #53 and keep working on other tasks of the project (mostly production of instructional material), then I'll start my brief 02 weeks vacation, work on Bionic Blue on November, and jump right into developing Nodezator version 1.5 on the very first day of December, which will hopefully be released by February 2024 (taking the second half of my vacations into account).
timeline title Next few months of work October : Review PR 53 and produce content : 02 weeks off November: work in Bionic Blue game December to February : Start implementing features for Nodezator 1.5 : 02 weeks off : Finish implementing features and release Nodezator 1.5As usual, my work as the maintainer of the project is very hard to predict and plan for, since it consists of many different things, including things that are outside my control, like new bugs popping up or people needing help with stuff, etc. My work outside the project also affects my schedule. So delays are always possible, despite my best efforts to provide accurate estimations and to work diligently.
Clarifications on scope of the changes for topological sorting
From a conversation with Mr. Alexander linked at the beginning of this post, one might notice my eagerness to explore not only topological sorting, but other potentially useful algorithms that might exist, as well as exploring other possibilities like executing nodes asynchronously. However, although my desire and eagerness to pursue such possibilities remain unchanged, upon reflection I concluded they are all tasks whose scope is far broader in comparison to what Mr. Alexander actually requested/proposed.
In other words, the extra time and effort required by such additional tasks would far surpass what is needed to implement topological sorting. It would be a different endeavor altogether. Moreover, although still desirable, such extra possibilities are of lower priority in comparison to other more urgent missing features like subgraphs (group nodes). Thus, for the time being, I believe it is better to focus our efforts solely in the implementation of Mr. Alexander's original request. The other possibilities can be pursued at a later date when Nodezator is in a more complete state and ready to have its many services incremented/improved.
The topological sorting solution will already bring a lot of benefits to Nodezator and only cost us a relatively small amount of effort and time to implement it, allows us to quickly move on to work in other more urgent features.
Mr. Alexander also mentioned the Dijkstra's shortest path algorithm, saying that it could be used to update objects downstream to a node when its values are changed. Again, to keep the scope of the changes simple, I believe we should postponing any research/development/discussion regarding this. This is totally something that should be listed for future consideration though, given how useful it could be.
Finally, I just wanted to add that although the current graph execution algorithm used is effective, no particular effort was made to guarantee its efficiency and it doesn't follow any specific guidelines/established solutions. It is just a temporary solution I implemented until I could revisit it in the future. Since the beginning I was actually considering keeping it as an alternative solution, but after just a bit of research on topological sorting I'm not sure anymore whether my solution has any undeniable advantage over topological sorting. In other words, topological sorting probably supersede it in every way. This is why I want to replace the current solution by topological sorting altogether.
Beta Was this translation helpful? Give feedback.
All reactions