1
$\begingroup$

What are the relative merits of the various graph representations, such as adjacency matrix, edge list, adjacency list, directly connected network etc. Given that this graph will be frequently updated, split, joined to other graphs?

Business Context: I am writing a molecule editor in C# and have currently used a directly connected network. By this, I mean each edge maintains direct object references to each node, and each node supports a collection of edges, although this has proven to present problems when updating. I am looking for a better way of doing this.

The model should support

  • Adding and removal of nodes
  • Adding and removal of edges
  • Splitting connected graphs into two separate graphs
  • Joining graphs together

EDIT: by a 'directly connected network' I imply the following. Vertices are Atom objects. Edges are Bond objects. Each Atom has a collection of Bonds, and each Bond has a StartAtom and EndAtom. The collections hold object references, so it is possible to directly retrieve the Atoms by calling Bond.StartAtom and Bond.EndAtom. Setting the StarAtom or EndAtom requires that both Bond collections on each atom be update in synchrony.

Also, Atoms and Bonds reside within a Molecule, each being stored in one of two dedicated collections, and each Atom and Bond holds a direct reference to its parent Molecule. Also, Molecules may contain an arbitrary number of child Molecules, and each of these has a reference to its parent.

The major difficulty with this approach is book-keeping. Molecular graphs, when being edited are constantly being updated. A typical operation is to remove a linking bond between to portions of a Molecule, which would split it into two separate Molecules. Or to perform the revers operation, joining the Molecules into one combined Molecules, simply by drawing a bond between two disconnected Atoms.

The current approach is challenging to maintain easily and reliably. When you add the requirement that you must support Undo and Redo then it becomes near impossible. So I am looking for any approaches or design patterns that would simply this task though abstracting the representation. I am currently experimenting with an edge-list approach. I want to know if there are any better ways of doing it.

$\endgroup$
  • 3
    $\begingroup$ Please describe in more detail the operations that the graph should support. Also, please describe the exact meaning of "directly connected network". $\endgroup$ – Vincenzo Jan 14 at 12:27
  • 2
    $\begingroup$ It's not clear exactly how you would wish to split a connected graph, nor join two graphs. $\endgroup$ – Pål GD Jan 14 at 19:20
  • $\begingroup$ This site is not about chemistry. It is about computer science. If you cannot explain your problem in terms that computer scientists can understand, then we cannot help you. $\endgroup$ – Yuval Filmus Jan 16 at 9:28
  • 1
    $\begingroup$ I don't take the comment as questioning your motives. I don't think it's asking you why you want to do that, but what you want to do. It's not clear what exactly is meant by splitting the graph; how do you want it to be split? What should that operation do? Also I notice that you haven't answered the prior question about what you mean by a directly connected network. Do you mean a directed graph? Please remember that folks here are volunteering their time to help you. When they ask questions, it's often because there's information they need to know before they can help you. $\endgroup$ – D.W. Jan 16 at 19:53
  • 1
    $\begingroup$ "What are the relative merits?" sounds pretty broad to me. Can you narrow it down to ask about some specific aspect, or identify some specific metrics or criteria that are relevant to you? How do you plan to evaluate a representation? What criteria are relevant to you? You mention you've experienced problems with one representation; what problems did you experience? Without narrowing this down, it might be too broad to be answerable here. $\endgroup$ – D.W. Jan 16 at 19:56
0
$\begingroup$

You might be interested to know after all that I settled on an edge-list representation. This allows easy cloning and has loosely coupled nodes and edges, which makes it idea for frequent editing operations.

Thanks for all the help and constructive comments.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.