7
$\begingroup$

I am writing a software and I need to represent an graph in a orthogonal manner from topological data (vector of edges,vertices and their connectivity data)

Graphs consist of a set of vertices and a set of edges, each connecting two vertices.A vertex may have any number of connected edges so it makes the problem a lot more complicated.

I have read some articles and its looks like that the Kandinsky model is the post popular one. However I just don't know the algorithm, any other solution (algorithm) that solve the problem is also very welcome.


Added after edit

The following picture shows a real world example for an electricity network which should be considered as raw data, in order to create a graph from this network, some preliminary tasks must be done.

Input Data:

Input Data

The result I am looking for is something like below, there are some characteristics if you take a look much closer :

The Red Polygon in the middle of the above picture(input data) represents an electricity substation which is a node itself and can be connected to more than 4 edges. There are more red polygons but only one can be fit into the above picture however as you may see, the following picture could cover much more than a red polygon that means it can map a bigger area, so the following picture is much more denser.

In Schematics diagrams, red polygons (Substations) usually maintain their position against each other relatively so if we manage to see beyond the extents of the above map by zooming out for example, we should almost see a triangle that is obviously can be seen at the below while having the left one at the left, the down one at the down ..... (this is not a rule, but I thought it could be a head start for desired algorithm)

Orthogonal Diagram:

Orthogonal Schematic

$\endgroup$
  • $\begingroup$ Does orthogonal in this context mean using only vertical and horizontal edges? Are you looking for a way to represent more than 4 edges meeting at a single vertex? $\endgroup$ – trichoplax May 28 '16 at 14:49
  • $\begingroup$ @trichoplax Exactly, and I do appreciate any help. $\endgroup$ – Zich May 31 '16 at 12:52
  • 2
    $\begingroup$ Is the graph guaranteed to be planar so that, forgetting the orthogonal edges for a moment, the graph can be drawn without edges overlapping? $\endgroup$ – Daniel M Gessel Jun 1 '16 at 18:36
  • 1
    $\begingroup$ General graph layout algorithms are anoying to program and implement. Even just finding proper ones from literature is pain. You should describe a bit more what you expect, draw a picture. $\endgroup$ – joojaa Jun 2 '16 at 7:57
  • 1
    $\begingroup$ The vertexes already have a given position in 2D (or on a sphere), so it's more of an edge routing problem? The trivial solution is to route each edge first along the x, then along the y axis (or the other way 'round). If this is right, explaining the problems with this trivial solution might be helpful. I imagine a minimization problem by assigning penalties for the problems... $\endgroup$ – Daniel M Gessel Jun 3 '16 at 16:54
-1
$\begingroup$

libCola

cola.js (a.k.a. WebCola) is a JavaScript based rewrite of libcola which works well with D3.js

http://marvl.infotech.monash.edu/webcola/

Gridified Layout example:

http://marvl.infotech.monash.edu/webcola/examples/dotpowergraph.html

OGDF

Open Graph Drawing Framework

Have an orthogonal layout

Orthogonal: Ortholayout with modules for the steps of shape and compaction, ClusterOrthoLayout

http://www.ogdf.net/doku.php/ogdf:features

Check projects that uses OGDF

http://www.ogdf.net/doku.php/project:external

HOLA

Human-like Orthogonal Layout Algorithm

https://vimeo.com/150509722

Kieffer, Steve, Tim Dwyer, Kim Marriott, and Michael Wybrow. "Hola: Human-like orthogonal network layout." Visualization and Computer Graphics, IEEE Transactions on 22, no. 1 (2016): 349-358.

$\endgroup$
  • $\begingroup$ This sounds promising. Could you edit to add some detail of what this provides? $\endgroup$ – trichoplax Jul 4 '16 at 12:24
  • 1
    $\begingroup$ It would also be useful to have an overview of how each algorithm works, so that they can be compared without needing to leave the answer. $\endgroup$ – trichoplax Jul 5 '16 at 1:21

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.