search

davecom / SwiftGraph

A Graph Data Structure in Pure Swift
Apache License 2.0
754 stars 79 forks source link

Graphviz encodable #63

Open ferranpujolcamins opened 5 years ago

ferranpujolcamins commented 5 years ago

It would be great to add an encoder for the dot language of https://www.graphviz.org/ This way applications can export the graphs they build with SwiftGraph for human visualization.

ferranpujolcamins commented 5 years ago

I started working on this as a separate project, independent of Swiftgraph. This way Swiftgraph ios not polluted and can be versioned separately. Also the encoder can work with other graph libraries.

davecom commented 5 years ago

Great, what license are you going to be releasing it under? I may want to pull it into the mainline since it would add a lot of value.

ferranpujolcamins commented 5 years ago

It's MIT license: https://github.com/ferranpujolcamins/DotSwift I'm working on the SwiftGraph bindings now. There will be a product with the Encoder itself and another one with the SwiftGraph bindings. You might add instructions on the readme on how to install DotSwift to use with SwiftGraph.

Of course you could also pull the whole project or part of it into SwiftGraph. But keeping them separated might be easier for versioning.

ferranpujolcamins commented 5 years ago

I don't how to handle directed / undirected graphs. Graphviz let us choose how to draw each edge (see this link. But, when I add an undirected edge between vertices A and B, Swiftgraph adds a directed edge from A to B and a directed edge from B to A.

When inspecting such a graph, shall we draw one undirected edge or two directed edges? We can't tell.

davecom commented 5 years ago

Yeah that is an issue. I guess for importing it's not an issue but for exporting it is. You could check every time if there is an edge in both directions and if there is just do an undirected edge. It could be a configurable flag?

ferranpujolcamins commented 5 years ago

I'm experimenting with an alternative representation of a Graph. See https://github.com/ferranpujolcamins/SwiftGraph/tree/new_edges, there's an explanation in the Graph protocol file.

Basically, the Edge object now has a directed property, to know if it's a directed edge or not. Each Edge object is stored only once in a new allEdges array. Then, the adjacencyLists now do not store the Edge object itself, but its index, its position in the allEdges array.

So now, when we add an undirected edge, we really add just one undirected edge, not two directed edges. So the graph does not lose information on whether edges are directed or not, as opposed to what happened before. Also, when a user adds an undirected edge, the edge count is 1, not 2, which is more intuitive.

What are your thoughts on this?

ferranpujolcamins commented 5 years ago

The approach above involved extensive changes to the codebase and resulted in a massive performance drop, so I discarded it.

I thought of a much simpler solution with no performance impact in existing performance tests: https://github.com/davecom/SwiftGraph/pull/67