UpwardPlanarizationLayout Linker Errors

[tewat...@gmail.com]

Hi, I have been using OGDF as a library in Visual Studio 2015, and everything worked until I started using the UpwardPlanarizationLayout class.

Using this class results in linker errors (LNK 2019), while, confusingly, similar classes (such as SugiyamaLayout) do not. Here is the modified example code I have been working with, which just attempts to draw an upward planar representation of a random graph:

#include <ogdf/basic/Graph.h>

#include <ogdf/basic/graph_generators.h>

#include <ogdf/layered/DfsAcyclicSubgraph.h>

#include <ogdf/fileformats/GraphIO.h>

#include <ogdf/upward/UpwardPlanarity.h>

#include <ogdf/basic/GraphAttributes.h>

#include <ogdf/upward/UpwardPlanarizationLayout.h>

#include <ogdf/layered/SugiyamaLayout.h>

using namespace ogdf;

int main()

{

srand((unsigned int)time(NULL));

Graph G;

randomSimpleGraph(G, 10, 20);

DfsAcyclicSubgraph DAS;

DAS.callAndReverse(G);

GraphIO::writeGML(G, "exgraph.gml");

bool upward = UpwardPlanarity::isUpwardPlanar_embedded(G);

// attempt to draw an upward planar representation

GraphAttributes GA(G, GraphAttributes::nodeGraphics | GraphAttributes::edgeGraphics);

SugiyamaLayout SL = SugiyamaLayout(); //no compilation errors

UpwardPlanarizationLayout UPL = UpwardPlanarizationLayout(); //compilation errors (LNK 2019)

UPL.call(GA);

GraphIO::drawSVG(GA, "exampleGraph.svg"); 

return 0;

}

And here is one of the three similar errors I get:

Error LNK2019 unresolved external symbol "__declspec(dllimport) public: __thiscall ogdf::UpwardPlanarizationLayout::UpwardPlanarizationLayout(void)" (__imp_??0UpwardPlanarizationLayout@ogdf@@QAE@XZ) referenced in function _main

Thank you to anyone who can help.

[Tilo]

Hi,

the implementation of UpwardPlanarizationLayout was removed a long

time ago but the header was missed. This is fixed in an upcoming

snapshot.

To draw an upward planar graph you could use the following code instead:

#include <ogdf/basic/graph_generators.h>

#include <ogdf/basic/simple_graph_alg.h>

#include <ogdf/fileformats/GraphIO.h>

#include <ogdf/upward/LayerBasedUPRLayout.h>

#include <ogdf/upward/UpwardPlanarity.h>

using namespace ogdf;

int main()

{

   Graph G;

   randomHierarchy(G, 50, 100, true, true, false);

   makeSimpleUndirected(G);

   GraphIO::writeGML(G, "exgraph.gml");

   adjEntry externalFaceAdj;

   bool isUpwardPlanar = UpwardPlanarity::embedUpwardPlanar(G, externalFaceAdj);

   OGDF_ASSERT(isUpwardPlanar);

   CombinatorialEmbedding emb(G);

   emb.setExternalFace(emb.rightFace(externalFaceAdj));

   UpwardPlanRep upr(emb);

   upr.augment();

   LayerBasedUPRLayout layout;

   GraphAttributes GA(G, GraphAttributes::nodeGraphics |

GraphAttributes::edgeGraphics | GraphAttributes::edgeArrow);

   layout.call(upr, GA);

   // show edge arrows

   for(edge e : G.edges) {

      GA.arrowType(e) = EdgeArrow::First;

   }

   GraphIO::drawSVG(GA, "exampleGraph.svg");

   return 0;

}

Note that I do not know whether randomHierarchy always returns an

upward planar graph, nor whether this code will work for arbitrary

upward planar graphs, so the program might fail with the respective

assertion.

If you're asking to draw a (non-upward planar but directed acylic)

graph as an upward planarization, I am not sure whether the OGDF

supports this.

Cheers

Tilo

[tewat...@gmail.com]

Thanks for the response! I am confused by some of the code though, a few functions and members here are not in my libraries (version 2015.05) and subsequently not documented here. The ones that are not in my version are embedUpwardPlanar, the "edges" member of the Graph class, and the "First" member of the EdgeArrows class. Do you know what's going on here?

[Tilo]

My code is using snapshot 2016-12-05 that can be found on GitHub. Just yesterday, we pushed snapshot 2017-02-16 that should also work for you. The latest snapshot documentation can always be found at https://ogdf.github.io/doc/ogdf-snapshot/.

You can also find porting guides there, if you are willing to switch from release 2015.05 ("Baobab") to the snapshot.

In your version, ArrowType::First is denoted by eaFirst, graph.edges have to be retrieved by calling Graph::allEdges. I too could not find the definition of embedUpwardPlanar in 2015.05 but there's a generator for upward planar graphs that you could use instead.

Cheers

Tilo

[tewat...@gmail.com]

That's very helpful, thank you. I wasn't aware my version of the library was so out of date.

[tewat...@gmail.com]

If you don't mind me hopping on this thread again, I have a couple questions about this code you posted, which I have modified a little for my own use:

1) I gather that non-single-source upwards planar embedding is much harder, but do you know of any implementations of upwards planar embedding on such graphs in OGDF? I see "embedUpwardPlanar" simply returns false for cases in which the graph isn't single-source.

2) Out of curiosity, why is the external face of the embedding set with the "right" face specifically? Does this have to do with orienting the graph in some direction?

Regards,

Taylor

On Thursday, February 16, 2017 at 5:05:18 AM UTC-6, Tilo wrote:

[Tilo]

Hi Taylor,

1) I am not aware of any such code.

What you could do, is create a sink & source yourself and set the costs of the newly created edges to zero (in the respective GraphAttributes).

I am not entirely sure though whether the algorithm respects these edge costs.

2) Quite generally, it's often easier to use adjacency entries to determine faces because, in the OGDF, any Graph object supports accessing adjacency entries but only CombinatorialEmbedding objects (that are limited to planar graphs) allow accessing faces.

With that explained, one has to choose either the right or left face. It's completely arbitrary.

Kind regards,

Tilo

[Maximilian Pfister]

Hi,

hoping that this thread is still watched:

 

To find a crossing minimal-drawing of an upward graph I would like to use the "SubgraphUpwardPlanarizer", however while initializing this module works fine I cannot compute a "UpwardPlanRep" of my non-planar graph without obtaining a segmentation fault (actually. both the line

emb.setExternalFace(emb.rightFace(externalFaceAdj));
and 
UpwardPlanRep upr(emb);
lead the segmentation faults). The input graph is directed, acyclic and single source single sink.

Full Code:


SubgraphUpwardPlanarizer SUP;
SUP.setInserter(new FixedEmbeddingUpwardEdgeInserter);
SUP.setSubgraph(new FUPSSimple());
SUP.runs(10);
adjEntry externalFaceAdj;
CombinatorialEmbedding emb(gc);
emb.setExternalFace(emb.rightFace(externalFaceAdj));
UpwardPlanRep upr(emb);
SUP.call(upr,0,0);

Any ideas on how to solve the issue?
Greetings
Maximilian

[Maximilian Pfister]

In the case that someone else also has problems for this particular method:

The solution ( credits to Markus Chimani) :

Graph G ... input graph
UpwardPlanRep U;
U.createEmpty(G);
SubgraphUpwardPlanarizer sup;
sup.call(U, 0, 0);