{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T19:29:03Z","timestamp":1776108543096,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2023,12,5]],"date-time":"2023-12-05T00:00:00Z","timestamp":1701734400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2023,12,5]]},"abstract":"<jats:p>The use of version control is pervasive in collaborative software projects. Version control systems are based on two primary operations: diffing two versions to compute the change between them and merging two versions edited concurrently. Recent works provide solutions to diff and merge graphics assets such as images, meshes and scenes. In this work, we present a practical algorithm to diff and merge procedural programs written as node graphs. To obtain more precise diffs, we version the graphs directly rather than their textual representations. Diffing graphs is equivalent to computing the graph edit distance, which is known to be computationally infeasible. Following prior work, we propose an approximate algorithm tailored to our problem domain. We validate the proposed algorithm by applying it both to manual edits and to a large set of randomized modifications of procedural shapes and materials. We compared our method with existing state-of-the-art algorithms, showing that our approach is the only one that reliably detects user edits.<\/jats:p>","DOI":"10.1145\/3618343","type":"journal-article","created":{"date-parts":[[2023,12,5]],"date-time":"2023-12-05T10:20:48Z","timestamp":1701771648000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["<i>NodeGit<\/i>\n            : Diffing and Merging Node Graphs"],"prefix":"10.1145","volume":"42","author":[{"given":"Eduardo","family":"Rinaldi","sequence":"first","affiliation":[{"name":"Ubisoft, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Davide","family":"Sforza","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabio","family":"Pellacini","sequence":"additional","affiliation":[{"name":"University of Modena and Reggio Emilia, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,5]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00544-1"},{"key":"e_1_2_2_2_1","volume-title":"Proceedings. Springer, 293--303","author":"Blumenthal David B","year":"2018","unstructured":"David B Blumenthal, S\u00e9bastien Bougleux, Johann Gamper, and Luc Brun. 2018. Ring based approximation of graph edit distance. In Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, S+ SSPR 2018, Beijing, China, August 17--19, 2018, Proceedings. Springer, 293--303."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2772243"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2018.05.002"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001421510083"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2019.10.028"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(97)00060-3"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925956"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356550"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133883"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Scott Chacon. 2009. Pro Git. Apress.","DOI":"10.1007\/978-1-4302-1834-0"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556288.2557009"},{"key":"e_1_2_2_13_1","volume-title":"Nonlinear revision control for images. ACM Trans. Graph. 30","author":"Chen Hsiang-Ting","year":"2011","unstructured":"Hsiang-Ting Chen, Li-Yi Wei, and Chun-Fa Chang. 2011. Nonlinear revision control for images. ACM Trans. Graph. 30 (2011)."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2457317.2457373"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Timothee Cour Praveen Srinivasan and Jianbo Shi. 2007. Balanced Graph Matching. In Advances in Neural Information Processing Systems 19 B. Sch\u00f6lkopf J. C. Platt and T. Hoffman (Eds.).","DOI":"10.7551\/mitpress\/7503.003.0044"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964961"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461942"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766936"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3208806.3208809"},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Jozef Dobo\u0161 Kristian Sons Dmitri Rubinstein Philipp Slusallek and Anthony Steed. 2013. XML3DRepo: a REST API for version controlled 3D assets on the web. In Web3D.","DOI":"10.1145\/2466533.2466537"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Jozef Dobo\u0161 and Anthony Steed. 2012a. 3D Diff: an interactive approach to mesh differencing and conflict resolution. In SIGGRAPH Asia Technical Briefs.","DOI":"10.1145\/2407746.2407766"},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Jozef Dobo\u0161 and Anthony Steed. 2012b. 3D revision control framework. In Web3D.","DOI":"10.1145\/2338714.2338736"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2642937.2642982"},{"key":"e_1_2_2_24_1","volume-title":"A Survey of Graph Edit Distance. Pattern Analysis and Applications 13, 1","author":"Gao Xinbo","year":"2010","unstructured":"Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. 2010. A Survey of Graph Edit Distance. Pattern Analysis and Applications 13, 1 (2010)."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531372"},{"key":"e_1_2_2_26_1","volume-title":"Fitzmaurice","author":"Grossman Tovi","year":"2010","unstructured":"Tovi Grossman, Justin Matejka, and George W. Fitzmaurice. 2010. Chronicle: capture, exploration, and playback of document workflow histories. In UIST."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2207676.2208549"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"},{"key":"e_1_2_2_29_1","volume-title":"Bridging the Gap between Graph Edit Distance and Kernel Machines","author":"Neuhaus Michel","unstructured":"Michel Neuhaus and Horst Bunke. 2007. Bridging the Gap between Graph Edit Distance and Kernel Machines. World Scientific Publishing."},{"key":"e_1_2_2_30_1","unstructured":"Onshape. 2014. Full-cloud 3d cad system. https:\/\/www.onshape.com\/."},{"key":"e_1_2_2_31_1","volume-title":"Mercurial: The Definitive Guide","author":"O'Sullivan Bryan","year":"2009","unstructured":"Bryan O'Sullivan. 2009. Mercurial: The Definitive Guide. O'Reilly Media."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699485"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.imavis.2008.04.004"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-58961-9_20"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818110"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2018.04.003"},{"key":"e_1_2_2_37_1","volume-title":"LevelMerge: Collaborative Game Level Editing by Merging Labeled Graphs","author":"Santoni Christian","year":"2018","unstructured":"Christian Santoni, Gabriele Salvati, Valentina Tibaldo, and Fabio Pellacini. 2018. LevelMerge: Collaborative Game Level Editing by Merging Labeled Graphs. IEEE CG&A 38, 4 (2018)."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.01.010"},{"key":"e_1_2_2_39_1","volume-title":"Proc. ACM Program. Lang. 2, Article 165","author":"Sousa Marcelo","year":"2018","unstructured":"Marcelo Sousa, Isil Dillig, and Shuvendu K. Lahiri. 2018. Verified Three-Way Program Merge. Proc. ACM Program. Lang. 2, Article 165 (2018), 29 pages."},{"key":"e_1_2_2_40_1","unstructured":"Kaizhong Zhang. 1989. The editing distance between trees: algorithms and applications. Ph.D. thesis New York University (1989)."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218082"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90136-J"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618343","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618343","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T10:52:59Z","timestamp":1755773579000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618343"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,5]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12,5]]}},"alternative-id":["10.1145\/3618343"],"URL":"https:\/\/doi.org\/10.1145\/3618343","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,5]]},"assertion":[{"value":"2023-12-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}