Would graph crossing utilities belong here?

[narnold0]

Hi there,

I've been working with graph crossings and their properties and such. Originally I was using Networkx but I've been using Graphs.jl and Julia now. Some of the things I've been using are mapping from the edge pairs (e,e)->crossing, if they have one that is ofc . The # crossings per edge (so can check for k-planarity of embedding, crossing count etc...), crossing per vertex (the # of crossings of edges on that vertex), sparse matrix of the crossings in the graph embedding, and also graph constructions from the crossings in a graph embedding. Also # faces, and some things. Would that be the kind of thing that would be welcome here?

[gdalle]

Hi, thanks for offering to contribute! The specific functions you describe would feel more at home in Graphs.jl, where all the algorithms will live in the future. GraphsBase.jl is only meant to host a basic interface and a few standard graph types

[gdalle]

Can you reopen your issue there, and maybe a PR if you want?

[narnold0]

Can you reopen your issue there, and maybe a PR if you want?

I'm not sure, for me it says it is in Graphs.jl here

[jpfairbanks]

Yeah this issue is on Graphs.jl I don't see any indication that it was moved from GraphsBase. Maybe he was looking at several issues in parallel and got confused.

[gdalle]

Indeed, sorry for the mistake. Then your PR is welcome here, although reviewing times may vary 😊

[etiennedeg]

Note that for the moment, this library lacks even the most basic functionalities for planarity and embeddings (which is welcome contribution, of course) although something was started here: https://github.com/JuliaGraphs/Graphs.jl/pull/208

[narnold0]

Is there a standard or consistent way of storing information related to a graph, or in relating information in Julia in general? Would this be a struct or something? methods? I only just started using Julia really and there can be a lot of ways to accomplish something sometimes so I'm not sure what I should be doing

For example, for myself, so far I've just been doing it such that when I use a function with a pair (G,layout) it first checks a nested Dict, using G as a key first (or creates), then uses the positions in a Dict below that as a key, my thinking being that you could be able to have multiple layouts associated with a single graph, and be able to differentiate in some way, but also keep them related somehow. Then it just runs the other functions which themselves could be used alone of course but just consolidating the calls into the dictionary for the pair. And that was where I was storing other dictionary mappings that were useful for functions involving the (G,layout) pair and it seemed faster always to just access it and use what I needed or to pass this dictionary and use what was needed. So I was using the dictionary accessed by the pair to store key mappings and information to be accessed for the functions involved like

crossinginfo2 = crossing_construction(H, positions2)
#accessed then with keys 
crossinginfo2[:crossings]
crossinginfo2[:graph]
crossinginfo2[:positions]
ccrossinginfo2[:edges_to_segments]

etc.. So it was easy for me to then use a function like

 crossing_edge(info::Dict, e)

to return the edges that cross with e in that particular configuration, and in general update/store information if I was creating it for the first time or such.

What its worth I did try metagraphsnext but I didn't get much use given the regular Graphs.jl functions being faster and having to create the meta graph and such. Wouldn't be surprised if it was just how I was doing it, and not writing the best code(to say the least) but I couldn't get it to run efficiently compared to using just Graphs.jl

[gdalle]

Is there a standard or consistent way of storing information related to a graph, or in relating information in Julia in general?

The answer is: "not yet, but soon". We're working on a full rewrite that will allow easy manipulation of metadata associated with vertices or edges (see GraphsBase.jl). In the meantime, shortest path algorithms for example take an edge weight matrix as additional argument. So your approach of giving layout (which I assume contains vertex coords?) seems fine to me. As for the output, I don't think I really understand what you're trying to do with the dictionary, but it would probably be more Julian to use a custom struct instead. If you need guidance about that I'll try to give some pointers when I review your PR