WO2019046872A1 - Procédé de comparaison de deux graphiques - Google Patents

Procédé de comparaison de deux graphiques Download PDF

Info

Publication number
WO2019046872A1
WO2019046872A1 PCT/AT2018/060192 AT2018060192W WO2019046872A1 WO 2019046872 A1 WO2019046872 A1 WO 2019046872A1 AT 2018060192 W AT2018060192 W AT 2018060192W WO 2019046872 A1 WO2019046872 A1 WO 2019046872A1
Authority
WO
WIPO (PCT)
Prior art keywords
node
graph
nodes
graphs
assigned
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/AT2018/060192
Other languages
German (de)
English (en)
Inventor
Roman Bretz
Wilfried NESENSOHN
Konrad WIELAND
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Lieberlieber Software GmbH
Original Assignee
Lieberlieber Software GmbH
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Lieberlieber Software GmbH filed Critical Lieberlieber Software GmbH
Publication of WO2019046872A1 publication Critical patent/WO2019046872A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/901—Indexing; Data structures therefor; Storage structures
    • G06F16/9024—Graphs; Linked lists
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/70—Software maintenance or management
    • G06F8/71—Version control; Configuration management
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/10—Office automation; Time management
    • G06Q10/101—Collaborative creation, e.g. joint development of products or services

Definitions

  • the invention relates to a method for comparing two graphene, in particular such graphene, one of which has been produced by manual processing of the other. Furthermore, the invention relates to a method for the conflict-proof updating of such graphs and to the collaborative working of a plurality of persons on a common graph.
  • the object of the invention is to provide a method for comparing graphs, with which it is possible for the individual user to detect changes in graphs or in parts of the graph.
  • each of the graphs being associated with an acyclic directed subgraph comprising all of the nodes of the respective graphs
  • each edge of the two graphs being associated with edge information relating to those edges contained in the respective graph but not in the acyclic directed subgraph associated with the graph,
  • each node of the two graphs are optionally associated with further information
  • the directed acyclic subgraphs for each node in each case a hash value based on the node associated edge information and others Information and the hash values of his, in particular immediate, child nodes are taken into account,
  • the child nodes of the respective nodes are recursively checked for diversity according to the aforementioned criteria.
  • the second graph was created by modifying, adding and / or deleting individual nodes of the first graph
  • step b in each case those child nodes to which the same key has been assigned are compared with one another.
  • a change record is created which indicates for the nodes identified as changed respectively which change, in particular also addition or deletion of edges or child nodes, in the relevant node of the second graph relative to the respective node of the first graph.
  • a simple distribution of change information which manages with existing data structures, provides that the changes affecting one node and those changes that affect an edge associated with the node are each provided node by node separately.
  • a particularly simple versioning and archiving provides that in the event that conflicting change requests are contained in the two change records, a conflict is detected, and in particular
  • Conflicting can be done by examining only change requests for inconsistencies assigned to the same node to determine conflicting change requests.
  • steps b) and d) are carried out by means of at least one client, wherein the graph or a subgraph of the graph is downloaded to the client, the downloaded subgraph is modified by the client,
  • a change record is created by the client describing the changes made by the client, and
  • step f) is performed by the server.
  • a computer network can be used to collaborate between multiple distributed users or clients by identifying a potential conflict
  • the server transmits a message containing the refusal of the change to the client, and / or
  • the server creates a conflict message indicating which nodes the conflict was detected for.
  • a graph is understood to mean any data structure having a number of nodes and edges, one edge connecting two nodes at a time. Both the edges and the nodes can each be assigned further data, in particular also data in the form of key-value pairs.
  • a directed graph refers to a graph in which the individual edges are assigned an inner direction, ie in which the two nodes are assigned a predetermined order. In the case of a directed graph, the order of the nodes can be understood in each case as an association of a direction with which it can be specified whether the relevant edge points from one node to the other or vice versa.
  • a subgraph of a graph is understood to mean a graph which contains a subset of the nodes of the graph; if necessary, the nodes of the graph can also correspond to the nodes of its subgraph.
  • the subgraph also contains a subset of the edges of the graph, where in the subgraph only edges of the graph may be contained, to which two nodes contained in the subgraph are assigned.
  • the present graph is altogether connected, ie that each node is connected to each other node via a path comprising a number of edges.
  • subgraphs are used which have all the nodes of the original graph. Since the graph generally does not necessarily need to be acyclic, that is, can also have loops, it may be necessary to create a directed acyclic subgraph to delete individual edges.
  • An acyclic directed subgraph of such a fixed contiguous graph regularly has a tree structure, ie starting from a given root node, each individual node of the subgraph can be reached by a path along the edge direction. Nodes along the given edge direction at the end of the respective directed acyclic subgraph are called leaf nodes.
  • FIG. 1 shows a graph.
  • FIG. 2 shows an acyclic subgraph associated with the graph shown in FIG.
  • FIG. 3 shows a further graph created by modifying the graph shown in FIG. 1.
  • FIG. 4 shows an acyclic subgraph associated with the graph shown in FIG.
  • FIG. 5 shows a further graph created by modifying the graph shown in FIG.
  • FIG. 6 shows an acyclic subgraph associated with the graph shown in FIG.
  • FIG. 7 shows a network comprising a server and a client with which a collaborative work of several users on different versions of the same graph is possible.
  • an acyclic directed subgraph 110 comprising all the nodes of the original graph 1 1 is shown in greater detail.
  • the node A is chosen freely as a root node.
  • another node could be assumed as a root node.
  • the choice of another node as a root node leads to another acyclic directed subgraph 10, but ultimately does not change the procedure according to the invention.
  • the creation of an acyclic subgraph 10 comprising all nodes of a graph 1 1 is usually carried out together with the creation of a graph 1 1.
  • the root node is set as the node that was first inserted in the graph 1 1.
  • 1 new nodes can be added to the graph 1 1 by adding a new edge connecting an already existing node of the graph 1 1 to the new node.
  • a new edge is also assigned to the acyclic directed subgraph 110 and oriented to the newly added node.
  • the graph 1 1 has at least two nodes, it is also possible to connect two nodes already associated with the graph 1 1 via a new edge to be inserted. In this case, a loop is generated in the graph 1 1. In order to generate an acyclic graph in parallel with the creation of a graph 1 1, it may be provided that such edges are not included in the acyclic subgraphs 10.
  • a first graph 1 1 as shown in FIG. 1, can be achieved. Initially, a root node A is inserted. Then be
  • a node B is inserted and connected via the edge a to the node A,
  • a node C is inserted and connected via the edge b to the node A,
  • a node D is inserted and connected via the edge c to the node B,
  • a node E is inserted and connected via the edge e to the node C,
  • a node F is inserted and connected via the edge f to the node D,
  • a node G is inserted and connected via the edge g to the node E,
  • an edge d is inserted connecting the two nodes B and E, and
  • This first graph 1 1 thus comprises a total of seven nodes A, B, C, D, E, F, G and eight edges a, b, c, d, e, f, g, h.
  • the graph 1 1 shown in FIG. 1 is cyclical. It has, for example, a loop comprising the edges a, b, d, e.
  • the acyclic graph (FIG. 2) associated with the first graph 1 1 1 1 1 one of these edges, in the present case the edge d, is not included.
  • the graph 1 1 has a loop comprising the edges c, d, f, g, h.
  • associated acyclic subgraphs 1 10 is one of these edges, in the present case the edge h, not included.
  • the edges of the acyclic directed subgraph 1 10 of the first graph 1 1 are represented by bold lines and by specifying a direction.
  • the directional edge a is oriented to point from the node A to the node B.
  • the acyclic directed sub-graph 1 1 0 includes all nodes A-G of the first graph 1 1 and has no cycles, i. Starting from the root node A, all the individual nodes can be reached via the subgraph 1 1 0 or its edges, however, each node can only be reached from the root node A via directed edges of the acyclic subgraph 1 1 0 in a single way.
  • the edge d is not part of the acyclic directed subgraph 110, because if it were associated with the acyclic directed subgraph 110, a cyclic subgraph comprising the edges a, b, d, e would result.
  • the edge h is not included in the acyclic directed subgraph 1 1 0.
  • each node is a child node of exactly one other node of the acyclic directed subgraph 1 10.
  • Those nodes that can be reached via one or more directed edges of the subgraph 110 along the edge direction are called child nodes.
  • Those nodes that do not have child nodes are commonly referred to as leaf nodes.
  • a second graph 12 is created (FIG. 2), which was created by revising and supplementing first graph 1 1.
  • Corresponding nodes AG, A'-G 'and a-h; a'-h' edges are represented by identical reference symbols and provided with an apostrophe (').
  • the second graph 1 2 has a number of further nodes and edges which are not contained in the first graph 1 1.
  • the respective acyclic directed subgraph 1 10 of the first graph 1 1 and the acyclic directed subgraph 120 of the second graph 12 are identical except for the inserts made with respect to the second graph 12.
  • inserts can be accomplished through the operations already described, namely, on the one hand, adding a new node and connecting the new node over a new edge of the directed graph from an existing node and, on the other, connecting two existing nodes over a new one and not the one to be inserted Subgraph 120 edge to be assigned.
  • edges k ', n', m 'do not belong to the acyclic directed graph of the second graph 12; these are in the present case
  • each individual node is assigned a hash value k A , k G characterizing it .
  • k A hash value
  • k G characterizing it .
  • the individual nodes are traversal traversal by means of post-order.
  • the information directly associated with the respective node F, G is taken into account, such as, for example, the ID of the leaf node F, G and information associated with the node, in particular value pairs.
  • information relating to edges which do not belong to the acyclic subgraph 1 10, 120 is taken into account, ie with regard to the edge h at the two leaf nodes F, G considered. This information can be made, for example, by reference to an ID or a key that uniquely identifies the edge h.
  • information directly associated with this edge, in particular key value pairs can be taken into account.
  • k E of the remaining nodes A, B, C, D, E of the graph 1 1, 12 are in addition to the information already mentioned in terms of the node itself and connected to the node and not to Also includes the hash values of the immediate child nodes, and uses information of those edges that connect the respective node to its immediate child nodes.
  • the hash value k G assigned to it first changes.
  • the hash values of the child nodes of the node E must also be taken into account. If the hash value k G of the leaf node G changes, the hash value k E of the parent node E necessarily changes as well. A change in the hash value k G of the leaf node G also affects all of its direct and indirect parent nodes E, C, A, while the hash values of the remaining nodes B, F, D are not affected by the change.
  • the hash value of a node B can be calculated in such a way that the hash values of the children D of the node in question are first recursively determined, and the hash value of the relevant node B is only determined when they are available. In the context of calculating the hash values of the children D of the relevant node B, it may be necessary to recalculate the hash values of the children F of the child node D to determine. This process can be repeated recursively until you reach the leaf nodes that have no children.
  • nodes B, B 'and the nodes C, C each have different hash values k B , k B '; k c , kc, their respective child nodes are recursively checked for diversity. It follows that the same hash value is assigned to the two nodes D, D 'assigned to one another, since neither the node D, D' nor the child node F, when creating the second graph 12 with respect to the first graph 1 1, F 'information and edge information changed. Therefore, further investigation of the equality of the hash values of the child nodes F, F can be omitted.
  • FIGS. 5 and 6 show a third graph 13, which differs from the graphs shown in FIGS. 1 and 2 merely in that a node K "has been added via an edge o 'containing the node K" with the existing one Node C " combines.
  • Corresponding nodes AG, A “-G” and ah; a “-h” edges are represented by identical reference numerals and provided with two quotation marks (").
  • the different hash values k c ; k C "of the nodes C; C" indicate differences in the topological structure or in the information of the respective nodes, so that a further recursive search for differences becomes necessary.
  • a deep recursive search establishes the insertion of the node K "over the edge o"
  • the node E and its children are unchanged from the node E, so that a further recursion for the comparison of the nodes G, G "can be omitted.
  • the said approach is also advantageous in order to save storage space and transmission capacity when multiple versions of a graph 1 1, 12, 13 are to be processed at different locations by different users.
  • the advantage can also be used, in particular, when only those information items are transmitted between the users that represent changes compared to a predefined dataset.
  • nodes with different hash values are marked as different in the recursive comparison.
  • the respective changes of the nodes are stored to each other.
  • no change information need to be stored.
  • the changes described herein may be changes to information associated with a node, addition or deletion of individual nodes or edges.
  • the graph shown in Fig. 1 and 2 is regarded as the original graph 1 1, which represents an initial state or common processing status.
  • the first user loads the graph - in its entirety or with the parts of interest - onto its client computer and, based on this origin graph 1 1, creates the graph 13 shown in FIG. 3, which is referred to below as the first processing graph 13.
  • a change data set 22, 23 is created both for the updated graph 12 and for the processing graph 13, indicating the differences between the original graph 1 1 and the respective graphs 12, 13.
  • a first change record 22 indicates the changes between the original graph 1 1 and the updated graph 12.
  • a second change record 23 indicates the changes between the original graph 1 1 and the edit graph 13.
  • a common change data record 24 is created, which summarizes for the individual nodes in each case the changes specified in the first and second change data record 22, 23.
  • This common change record 24 is kept available and can in particular be applied to the source graph 1 1 in order to be able to accept the changes of the two change records.
  • the common change record 24 acts as a new (first) change record 22 to represent the current graph 12 so that further changes can be made in the graph.
  • FIG. 8 shows a network comprising a server 30 and a client 31 with which a collaborative work of several users on different versions of the same graph is possible.
  • a current graph 12 On the server 30 is a current graph 12, as shown in the above embodiments, stored.
  • the server 30 is connected to the clients 31 via an interface that allows the client in question to retrieve the entire graph or subgraph 1 10, 120 of the graph.
  • Client 31 allows the user to modify the currently downloaded graph.
  • the client 31 may create change records 22, 23 in the manner described above indicating how the modified graphs differ from the downloaded graphs 1 1, 12, 13 or subgraphs 1 10, 120, 130.
  • the change data records 23 can be transmitted back to the relevant server by the respective client 31, whereupon the server updates the current graph 12 on the basis of the transmitted change data record.
  • the server optionally checks the change record 23 for conflicts with intermittent changes and updates and issues it to the client If necessary, return a conflict message informing the client that the desired change can not be made.
  • the server 30 may also communicate a conflict message to the relevant client 31 specifying for which nodes the conflict was detected.
  • the change records may be transmitted as separate records as shown in the above tables.
  • a node is to be deleted, it is sufficient if the information relating to this node is deleted in its assigned parent node. If a node is to be added, the new node and its modified parent node are transmitted. The addition and deletion of edges as well as the modification of edge information is informed by the change of the node storing the edge information.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Business, Economics & Management (AREA)
  • General Physics & Mathematics (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Human Resources & Organizations (AREA)
  • General Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Strategic Management (AREA)
  • Databases & Information Systems (AREA)
  • Tourism & Hospitality (AREA)
  • General Business, Economics & Management (AREA)
  • Quality & Reliability (AREA)
  • Computer Security & Cryptography (AREA)
  • Operations Research (AREA)
  • Marketing (AREA)
  • Economics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

L'invention concerne un procédé de comparaison de deux graphiques, - chacun des graphiques (11, 12) étant associé à un graphique partiel dirigé acyclique comprenant l'ensemble des nœuds (A-F ; A'-J') des graphiques respectifs (11, 12), - des informations d'arête concernant les arêtes (d, h) qui sont contenues dans le graphique respectif (11, 12), mais pas dans le graphique partiel (110, 120) dirigé acyclique associé au graphique (11, 12), étant associées respectivement à chaque nœud (A-F ; A'-J') des deux graphiques (11, 12), - d'autres informations étant éventuellement associées respectivement à chaque nœud (A-F, A'-J') des deux graphiques (11, 12), - une valeur de hachage sur la base des informations d'arête et des autres informations associées au nœud et les valeurs de hachage de ses nœuds enfants, en particulier directs, étant respectivement prises en compte en partant des nœuds d'extrémité (G, H), en particulier au moyen d'un parcours d'arbre, des graphiques partiels (110, 120) dirigés acycliques pour le nœud respectif, - les valeurs de hachage de nœuds correspondants étant comparées récursivement en partant de nœuds racines (A, A') pour la comparaison des deux graphiques (11, 12), - en cas d'identité des valeurs de hachage, l'identité de tous les nœuds enfants du nœud respectif ainsi que de toutes les informations associées au nœud respectif étant fixée et - en cas de différences des valeurs de hachage, a) les informations associées au nœud ainsi qu'éventuellement les informations qui sont attribuées aux arêtes associées au nœud étant comparées, et en cas de la présence de différences de ces informations, les deux nœuds étant marqués comme étant différents, et b) la différence des nœuds enfants des nœuds respectifs étant contrôlée récursivement selon des critères susmentionnés.
PCT/AT2018/060192 2017-09-07 2018-08-17 Procédé de comparaison de deux graphiques Ceased WO2019046872A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
ATA50750/2017A AT520349A2 (de) 2017-09-07 2017-09-07 Verfahren zum Vergleich von zwei Graphen
ATA50750/2017 2017-09-07

Publications (1)

Publication Number Publication Date
WO2019046872A1 true WO2019046872A1 (fr) 2019-03-14

Family

ID=63517624

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/AT2018/060192 Ceased WO2019046872A1 (fr) 2017-09-07 2018-08-17 Procédé de comparaison de deux graphiques

Country Status (2)

Country Link
AT (1) AT520349A2 (fr)
WO (1) WO2019046872A1 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20220342644A1 (en) * 2021-04-21 2022-10-27 Figma, Inc. Branching and merging in a design interface

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
"Generic Model Management", 14 June 2004, SPRINGER-VERLAG, Berlin/Heidelberg, ISBN: 978-3-540-21980-4, article SERGEY MELNIK: "Models", pages: 19, XP055517335, 032288 *
DANIEL ARCHAMBAULT ED - MATTAUSCH O ET AL: "Structural differences between two graphs through hierarchies", GRAPHICS INTERFACE 2005 : PROCEEDINGS ; VICTORIA, BRITISH COLUMBIA, 9 - 11 MAY 2005, CANADIAN INFORMATION PROCESSING SOCIETY, 403 KING STREET WEST, SUITE 205 TORONTO, ONT. M5U 1LS CANADA, 25 May 2009 (2009-05-25), pages 87 - 94, XP058200170, ISSN: 0713-5424, ISBN: 978-1-56881-337-0 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20220342644A1 (en) * 2021-04-21 2022-10-27 Figma, Inc. Branching and merging in a design interface

Also Published As

Publication number Publication date
AT520349A2 (de) 2019-03-15

Similar Documents

Publication Publication Date Title
DE102016216843B4 (de) Verteiltes Zusammenführen von Dateien
DE69130814T2 (de) Verfahren und Gerät zur Umwandlung von Maschinensprachprogrammstrukturen in Strukturen höherer Sprachen durch Manipulierung graphischer Programmdarstellungen
EP0791884A2 (fr) Procédé pour l'ajustement informatisé de plusieurs copies de fichiers d'un fichier stocké, stockées dans au moins un ordinateur
DE102012209711A1 (de) Systeme und Verfahren zum Verwenden grafischer Darstellungen für die Verwaltung von Abfrageergebnissen
DE112017006106T5 (de) Erzeugen von, Zugreifen auf und Anzeigen von Abstammungsmetadaten
DE10040987B4 (de) Verfahren und Vorrichtung für übereinstimmende Aktualisierungen von redundanten Daten in relationalen Datenbanken
DE19844013A1 (de) Strukturierter Arbeitsordner
DE202015009277U1 (de) Systeme zur Verwaltung von Bearbeitungsvorschlägen in einer Textbearbeitungsumgebung für kollaborative Dokumente
DE19844071A1 (de) Verfahren zum Lösen von Datenkonflikten in einem gemeinsamen Datenumfeld
DE102016204710A1 (de) Sichern und Wiederherstellen von Klondaten
DE112013000916T5 (de) System zum Anzeigen und Bearbeiten von Artefakten an einem zeitbezogenen Referenzpunkt
DE112013005993T5 (de) Verfahren, Vorrichtung und computerlesbares Medium für eine optimale Bestimmung von Daten-Teilmengen
DE102012223167A1 (de) Gemeinsame Nutzung von Artefakten zwischen kollaborativen Systemen
DE102016006202B4 (de) Numerische Steuervorrichtung zum Verwalten von Bearbeitungsdaten und Bearbeitungsergebnissen
DE202015009316U1 (de) Metadatenmanagement in einem dezentralen Verarbeitungssystem
DE202014010948U1 (de) Nicht-kollaborative Filter in einem kollaborativen Dokument
DE202014005278U1 (de) Einbetten von archivierten Daten in eine Datenquelle
WO2019046872A1 (fr) Procédé de comparaison de deux graphiques
DE69428426T2 (de) Verfahren zum automatischen beweisen
DE112021007160T5 (de) Datenvalidierungsvorrichtung, datenvalidierungsverfahren, unddatenvalidierungsprogramm
EP1647898A1 (fr) Système de replication de base de données sans serveur
DE10110039A1 (de) Ein Verfahren zur generischen Beschreibung und Manipulation beliebiger Datenstrukturen
DE19607132B4 (de) Verfahren zum rechnergestützten Abgleich mehrerer, in mindestens einem Rechner gespeicherten Dateikopien einer gespeicherten Datei
EP3796161A1 (fr) Procédé de détermination d'une configuration de conteneur d'un système, système, programme informatique et support lisible par ordinateur
DE112020006703T5 (de) Anzeigebilddaten-Editierprogramm, Anzeigebilddaten-Editiervorrichtung und Anzeigebilddaten-Editierverfahren

Legal Events

Date Code Title Description
NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 18765539

Country of ref document: EP

Kind code of ref document: A1