8000 Deterministic graph layout? · Issue #84 · ogdf/ogdf · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Deterministic graph layout? #84

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
TheComet opened this issue Apr 3, 2023 · 7 comments
Open

Deterministic graph layout? #84

TheComet opened this issue Apr 3, 2023 · 7 comments

Comments

@TheComet
Copy link
TheComet commented Apr 3, 2023 •
edited
Loading

I have noticed that the positions of nodes change randomly between runs on the same graph, even if I use ogdf::setSeed(42);.

This looks like a data race problem. Even if you set the seed on the global PRNG, the layout algorithms have worker threads, so the points at which random numbers are obtained is... well, random.
@milsen
Copy link
Member
milsen commented Apr 5, 2023

Thank you for the report. With which layout algorithm(s) does this occur for you?

It seems to be a layout-specific problem. For example, multiple runs of the SugiyamaLayout or PlanarizationLayout with the same seed resulted in the same exact layout. However, the DavidsonHarelLayout produced different layouts (even though it does not seem to use multiple threads).
I assume that the problem of non-deterministic layouts happens for multiple layout algorithms, some of which may have data race issues, while others may have other issues (e.g. they use non-ogdf rng functions and are thus unaffected by ogdf::setSeed).

@TheComet
Copy link
Author
TheComet commented Apr 5, 2023

Here's my code:

    ogdf::Graph G;
    ogdf::GraphAttributes GA(G,
        ogdf::GraphAttributes::nodeGraphics
      | ogdf::GraphAttributes::edgeGraphics
      | ogdf::GraphAttributes::nodeLabel
      | ogdf::GraphAttributes::edgeStyle
      | ogdf::GraphAttributes::nodeStyle
      | ogdf::GraphAttributes::nodeTemplate);

    // Add node and edges here

    ogdf::SugiyamaLayout layout;
    layout.setRanking(new ogdf::OptimalRanking);
    layout.setCrossMin(new ogdf::MedianHeuristic);

    ogdf::OptimalHierarchyLayout* ohl = new ogdf::OptimalHierarchyLayout;
    ohl->layerDistance(30.0);
    ohl->nodeDistance(25.0);
    ohl->weightBalancing(0.8);
    layout.setLayout(ohl);
    layout.call(GA);

I can't debug right now but I remember placing a breakpoint on randomNumber() and seeing the stacktrace go through OptimalRanking. Are you saying the layout is deterministic without layout.setRanking(new ogdf::OptimalRanking);?

@milsen
Copy link
Member
milsen commented Apr 6, 2023

Hmmm, I've been using the same code as you (including OptimalRanking) for multiple runs with the same seed and got exact the exact same layout. So there's definitely a problem with some other layouts but SugiyamaLayout works as intended for me, even with OptimalRanking.

Here's the exact code I used: 
#include <ogdf/basic/graph_generators.h>
#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/layered/MedianHeuristic.h>
#include <ogdf/layered/OptimalHierarchyLayout.h>
#include <ogdf/layered/OptimalRanking.h>
#include <ogdf/layered/SugiyamaLayout.h>

using namespace ogdf;

int main(int argc, char *argv[])
{
	Graph G;
	GraphAttributes GA(G, GraphAttributes::all);
	randomGraph(G, 50, 100);

	for (int i {0}; i < 15; ++i) {
		ogdf::setSeed(42);
		std::cout << "Round " << i << std::endl;
		SugiyamaLayout SL;
		SL.setRanking(new OptimalRanking);
		SL.setCrossMin(new MedianHeuristic);

		OptimalHierarchyLayout *ohl = new OptimalHierarchyLayout;
		ohl->layerDistance(30.0);
		ohl->nodeDistance(25.0);
		ohl->weightBalancing(0.8);
		SL.setLayout(ohl);

		SL.call(GA);
		GraphIO::write(GA, "issue-84-" + std::to_string(i) + ".svg", GraphIO::drawSVG);
	}
	return 0;
}

@TheComet
Copy link
Author
TheComet commented Apr 7, 2023

Thanks for taking the time to look into this, appreciate it.

I added back my call to ogdf::setSeed(42) to my code and suddenly it just works as intended. I really have no idea what changed (even tried checking out earlier versions where I know it was broken).

I think I might be going insane

@milsen
Copy link
Member
milsen commented Apr 7, 2023

No problem, I know that feeling all too well.

I'll keep this issue open for now as a reminder that there are other non-deterministic layouts that probably should be deterministic (with a set seed).

@N-Coder
Copy link
Member
N-Coder commented Nov 1, 2023

Note that the Sugiyam 9B6F a Docs mention that you need to set runs=1 if you want to get deterministic behaviour. I vaguely recall that I had a similar issue when writing tests for ogdf-python and this might have fixed it.

@zyrkiel zyrkiel mentioned this issue Feb 13, 2025
Open
@zhangyixing3
Copy link

Dear Sir,

I am trying to use the FMMMLayout to generate the positions of nodes. However, I noticed that even after setting the random seed with ogdf::setSeed(1), I am unable to obtain the same results consistently.

I would like to use OGDF (Open Graph Drawing Framework) in the Rust language, but I am not very familiar with OGDF and C++ . Could you please provide me with some advice?

Thank you for your time and assistance.

Best regards,
Yixing Zhang

extern "C" {
    // Result structure
    struct Result {
        double* x;
        double* y;
        size_t n; // Using size_t to match vector.size()
    };

    // Create a graph
    GraphHandle create_graph() {
        return new GraphWrapper();
    }

    // Add a node and return its index (0-based)
    size_t add_node(GraphHandle handle) {
        GraphWrapper* wrapper = static_cast<GraphWrapper*>(handle);
        node n = wrapper->graph.newNode();
        wrapper->nodes.push_back(n);
        return wrapper->nodes.size() - 1;
    }

    // Add an edge
    void add_edge(GraphHandle handle, size_t source, size_t target) {
        GraphWrapper* wrapper = static_cast<GraphWrapper*>(handle);
        if (source >= wrapper->nodes.size() || target >= wrapper->nodes.size()) return;
        wrapper->graph.newEdge(wrapper->nodes[source], wrapper->nodes[target]);
    }

    // Free graph memory
    void free_graph(GraphHandle handle) {
        delete static_cast<GraphWrapper*>(handle);
    }

    // Run layout algorithm with a fixed random seed of 1
    LayoutResult run_layout(GraphHandle handle) {
        GraphWrapper* wrapper = static_cast<GraphWrapper*>(handle);
        Graph& g = wrapper->graph;

        // Set fixed random seed to 1
        ogdf::setSeed(1);

        // Initialize graph attributes
        GraphAttributes ga(g, GraphAttributes::nodeGraphics);

        // Configure layout parameters
        FMMMLayout layout;
        layout.useHighLevelOptions(true);
        layout.unitEdgeLength(50.0);
        layout.newInitialPlacement(true);
        layout.call(ga);

        // Extract coordinates
        Result* res = new Result;
        res->n = g.numberOfNodes();
        res->x = new double[res->n];
        res->y = new double[res->n];

        size_t i = 0;
        for (node v : g.nodes) {
            res->x[i] = ga.x(v);
            res->y[i] = ga.y(v);
            i++;
        }

        return res;
    }

    // Free layout result memory
    void free_layout_result(LayoutResult res) {
        Result* r = static_cast<Result*>(res);
        delete[] r->x;
        delete[] r->y;
        delete r;
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@N-Coder @TheComet @milsen @zhangyixing3
0