Object Oriented Implementation of Graph Data Structures

Question

I have read quite a bit of graph data structure lately, as I have intentions to write my own UML tool. As far as I can tell, what I want can be modeled as a simple graph consisting of vertices and edges. Vertices will have several values ​​and will be best represented as objects. The edges, apparently, should be neither directed nor weighted, but I do not want to choose an implementation that makes it impossible to include such properties later.

Being educated in purely object-oriented programming, the first things that seem to me are vertices and edges by classes, for example, for example:

Class: Vertice - Array arrayOfEdges; - String name; Class: Edge - Vertice from; - Vertice to; 

This allows me to enter weights, direction, etc. later. Now, when I read about the introduction of schedules, it seems that this is a very unusual solution. Earlier questions here about stack overflows offer adjacency lists and adjacency matrices, but being completely new to the graphs, I hardly understand why this is better than my approach.

The most important aspects of my application are the ability to easily calculate which vertex is pressed and moved, as well as the ability to add and remove vertices and edges between vertices. Would it be easier to do in one implementation over another?

My language of choice is Objective-C, but I do not think this should have any meaning.

Answer 1

Here are two basic types of diagrams along with their typical implementations:

Tight graphics :

• Adjacency matrix
• Incident Matrix

Sparse graphs :

• Address list
• Incidence list

In the framework (unfortunately, the source is closed), which I wrote (> 12k loc graph uses +> 5k loc unit tests and still counts) I was in the state (Directed / Undirected / Mixed) Hypergraphs (Directed / Undirected / Mixed) Multigraphs , (Directed / Undirected / Mixed) Ordered Charts, (Directed / Undirected / Mixed) KPartite Graphs , as well as all kinds of Trees, such as Generic Trees, (A, B) -Trees, KAry-Trees, Full-KAry-Trees , (Trees in front: VP-trees, KD-trees, BKTrees, B-trees, R-trees, octers , ...).
And all without a single vertex or edge class. Pure generics. And without any redundant implementations **
Oh, and as if that wasn't enough, they all exist as mutable, immutable, observable ( NSNotification ), thread-safe, and thread-safe versions.
How? Thanks to the excessive use of Decorators .
In principle, all graphs are mutable, unsafe, and not observable. Therefore, I use Decorators to add all kinds of tastes to them (the result is no more than 35 classes, and no more than 500+ if they are implemented without decorators).

While I can’t give any real code, my graphs are mainly implemented through Lists using mostly NSMutableDictionaries and NSMutableSets (and NSMutableArrays for my ordered trees).

My indirect sparse graph has nothing but these ivars, for example:

 NSMutableDictionary *vertices; NSMutableDictionary *edges; 

Ivar vertices maps vertices onto vertex adjacency maps on falling edges ( {"vertex": {"vertex": "edge"}} )
Ivar edges maps edges to falling pairs of vertices ( {"edge": {"vertex", "vertex"}} ), and Pair is a paired data object that has a vertex of an edge vertex and a tail vertex.

Mixed sparse plots would have a slightly different display of adjacency / incident lists as well as Directional sparse plots , but you should get this idea.

The limitation of this implementation is that each and every vertex and each edge must have an object associated with it. And to make things more interesting (sic!), Each vertex object must be unique, and each edge object. This means that dictionaries do not allow duplicate keys. In addition, objects must implement NSCopying . NSValueTransformers or encapsulation of values ​​is a way around these restrictions (the same goes for memory overhead from copying dictionary keys).

While the implementation has its drawbacks, there is a big benefit: universal versatility! There is hardly any type graph that I could think of that it is impossible to archive what I already have. Instead of building each type of graph with custom parts, you basically go to your box of lego blocks and assemble the graphs as you need.

Additional Information:

Each large graph type has its own protocol, here are a few:

 HypergraphProtocol MultigraphProtocol [tagging protocol] (allows parallel edges) GraphProtocol (allows directed & undirected edges) UndirectedGraphProtocol [tagging protocol] (allows only undirected edges) DirectedGraphProtocol [tagging protocol] (allows only directed edges) ForestProtocol (allows sets of disjunct trees) TreeProtocol (allows trees) ABTreeProtocol (allows trees of ab children per vertex) FullKAryTreeProtocol [tagging protocol] (allows trees of either 0 or k children per vertex) 

Attachment to a protocol implies innate nature (of both protocols and implementations).

If there is anything else that you would like to get some understanding, feel free to leave a comment.

Ps . To give credit where credit should be: The architecture is heavily dependent on the JUNG Java Graphics Framework (55k + loc).

Pps Before choosing this type of implementation, I wrote a little brother using only undirected graphs, which I wanted to expand to also support oriented graphs. My implementation was very similar to the one you provide in your question. This is what gave my first (rather naive) project a sharp end, then: Subclassing a set of interdependent classes in Objective-C and ensuring type safety. Adding a simple focus to my graph makes my whole code split. (I didn’t even use the solution I posted then, as that would just put off the pain). Now with the general implementation, I have implemented more than 20 graph options without any hacks. It's worth it.

If all you need is to draw a graph and move its nodes on the screen, it will be good if you just implement a general class of the graph, which can then be expanded to a certain direction, if necessary.

Answer 2

Check out this PowerPoint presentation, especially the last slide: http://digital.cs.usu.edu/~cyan/CS5050/Graph.ppt

Answer 3

The adjacency matrix will be a bit more complicated than your object model when adding and removing vertices (but not edges), as this includes adding and removing rows and columns from the matrix. There are tricks you could use to do this, such as saving empty rows and columns, but it will still be a bit more complicated.

When you move the vertices around the screen, the edges will also be moved. This also gives your object model a slight advantage, since it will have a list of connected edges and will not have to search through the matrix.

Both models have an inherent focus on the edges, so if you want to have non-oriented edges, then you will have to do extra work anyway.

I would say that overall there is not much difference. If I implemented this, I would probably do something similar to what you are doing.

Answer 4

If you use Objective-C, I assume that you have access to Core Data strong>, which is likely to be a great place to start - I understand that you are creating your own schedule, Basic data is what he can do a great test, which you talk about for free if you set up the circuit correctly.