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.
