Difference between two systems of DAGs
From: Phil Bewig (pbewig_at_swbell.net)
Date: 02/21/04
- Next message: Robert Vienneau: "Re: Ideas for course on great ideas in (theoretical) CS?"
- Previous message: gowan: "Re: Ideas for course on great ideas in (theoretical) CS?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 21 Feb 2004 13:59:50 -0800
I am looking for a graph algorithm, but not being an expert
in graph algorithms I don't know the proper name for my
problem and thus am unable to find the needed algorithm in
the literature. I am hopeful that someone here can help.
My primary data structure is a system of zero or more
directed acyclic graphs. The vertices of the graphs carry
both a label and some additional information, the edges
carry no label or other information except direction.
I need an algorithm that, given two of these systems as
input, returns as output a list of the edit commands
needed to convert one system to the other. The possible
edit operations are to change the label of a vertex or the
information associated with a vertex, add or delete an
edge, and add or delete a vertex.
It would be good for the number of edit operations to be
provably minimal, but a fast heuristic that computes a
small (not necessarily minimal) edit sequence would be a
reasonable alternative; minimality and speed are both
important, but if I had to choose one at the expense of
the other, it would be minimality. I expect to have
problems where each of the systems may have ten thousand
or even more vertices and edges, but most problems will
probably be smaller, on the order of V + E <= 1000 and
most vertices with no more than a handful of edges; I
don't have a feel for how many different dags might be
in the system, but I expect that frequently each system
will contain exactly one dag with no unconnected vertices.
There are also important special cases where the system
consists of vertices but no edges and where one system is
an exact subgraph of the other. I do expect that most of
the time the two systems of graphs will be similar, with
large portions of the two systems identical, and the number
of edit operations required will be fairly small -- but
don't ask me to define similar, large portions, or fairly
small!
I also need a new method of storage. The current system
is an array of vertices represented as objects that have
methods to return the label, various pieces of additional
information, and a precedent list of edges; the array is
initially empty and is filled left to right, but becomes
sparse as edits are made.
I suppose one algorithm would be to search for two vertices
with common labels, then constantly search for common edges
that lead to other common vertices, either backtracking
when it is not possible to extend the match or adding or
deleting a candidate vertex or edge and then proceeding.
I know there is a lot of detail to fill in before that
algorithm is implementable, but even before I start, it
sounds expensive, possibly exponential in the number of
vertices and edges, and thus not practical. I am familiar
with dynamic programming methods to compute the edit
distance between two strings, which seems like a reduced
version of the problem I face.
I imagine the problem of comparing two systems of dags has
been studied before, but I can't find any references. I've
searched the usual sources for words like dag, graph,
directed acyclic graph, comp, compare, diff, difference,
edit, edit sequence, vertex, edge, and so on, in various
combinations, but my searches either turn up nothing useful
or, more commonly, far too much to be useful.
Can anyone suggest specific references to literature or
search terms that are likely to lead to such references?
Many thanks,
Phil
- Next message: Robert Vienneau: "Re: Ideas for course on great ideas in (theoretical) CS?"
- Previous message: gowan: "Re: Ideas for course on great ideas in (theoretical) CS?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
