-
Notifications
You must be signed in to change notification settings - Fork 184
Edges are not necessarily Arcs #401
Comments
Inconsistency example : The following code
returns true but this one
prints nothing |
for undirected graps edges are always returned such that x=>y has always x<y. This could be of some help I'm in favor of having a type type Edge
first::Int
second::Int
end also because I don't like for example having Base.show(p::Pair) overwritten and displaying "Edge 1 2" for hany pair. I fail to see though how can this solve the problem of Arc/Edge comparison |
Well i don't mind having two types that are exactly the same from a structural point of view.
As far as they are different types we can have different function specialization for both. For example
|
we should check what impact this would have thoughout the library, in particular regarding code duplication and type instability |
Sure and it would be better to keep all methods that do not make a difference between directed and undirected edges unique :
|
It was an explicit design decision to keep the structure of the graph independent of the structure of the edges. That is, edges do not contain information relative to their graph. There are a few reasons for this, but the main one is that it really doesn't matter. We have an accepted interface for checking edge membership, and Sometimes the lack of directedness on edges makes things more complex, but in general, it simplifies things a great deal. That is: I'm not in favor of creating two different edge types based on directedness. We have a history with this issue where basic operations required two separate functions depending on directedness of edges, and it was unnecessarily complex. Also: Edges used to just be a type with two Ints, as you're suggesting. It made sense to move to a primitive structure just for convenience, but if there's a compelling reason to move back, we can do it. |
but for me it really does matter. I wanted to write a mip that finds the shortest cycle in a graph using JuMP.jl
In JuMP when you declare your variable, you also declare the set of its indexes then you can do mathematic expressions over subsets in this set. Since out_edges(v,g) is not a subset of edges(g) there are a lot of mathematical programs that can not be written in a simple way anymore. |
the easiest ways to do this for undirected graphs are 1) to just ignore edges that are not in vertex order (use the unexported |
Yes I saw noticed these solutions. but they have three drawbacks.
After thinking half an hour one way I found to fix my model is to rewrite this
into that
I think this illustrate the 3 points I mentioned. Another way would be to transform pairs into sets that contain two elements and let the keys be Sets of vertices instead of Edges. but this would be even uglier in my opinion I am pretty sure you have reasons behind your decision of making Edges always Pairs, and I would be grateful if you could share some of them. |
Collecting / set-testing edges like that is expensive, though it may be unavoidable given what you need to pass in to JuMP. If that's the case, then just union the edgeset and its reverse:
~~(there's an equivalent for As far as the reasons for making Bottom line: yes, you've run into a case where you have to make something more complex due to the "light" nature of LightGraphs, and ultimately, this package may not be well-suited for your application. The alternative, to reengineer LG so that your case is simple, will have the effect of making other stuff more complex. It's not (even) a net-zero tradeoff. The fact that you've got a few reasonable workarounds and we don't have to upend / reengineer all the native data structures to accommodate this request means that, absent any demonstration that this proposed change improves LG with respect to 1) correctness, 2) memory utilization, 3) code simplicity, and/or 4) performance, it's probably not going to happen. If you want to submit a PR with appropriate benchmarks showing (at a minimum) no regressions in terms of those four goals, then you would then be presenting a more compelling reason to switch. I hope that helps. |
Another option is to use
|
Thank you for providing such a long explanation for something that was already discussed in the past (I m sorry i didn't know about that ). I actually did check all the issues posted even the closed ones before submitting this issue but i didn't check the commit history. I will go over it before eventually trying to submit a PR. |
To be fair, you wouldn't have known where to search in the commit history, nor what to look for, so no worries. I look forward to your PR. When you get closer to finalizing it, reach out to us to make sure you've got the proper benchmarking information included - this will represent a MAJOR change to the codebase and will require a ton of scrutiny. |
I changed the return type of in_edges in #403 , let me know what you think about it. Another option is to define and export an @constraint(m , adjacency[v in vertices(g)], sum{c[order(e)] , e in out_edges(g,v)} == 2b[v]) would work correctly |
@CarloLucibello I thought also about the same modification as what you suggested in #403 , but I didn't want to request it because, although it solves my issues, it could break some algorithms if they were relying on the fact that when looping thought However I really like your idea of adding the function
|
What do you think about leaving |
wait. What does If you need this, then use |
I don't see any problem with |
You have asked about order() because the name was not appropriate. By the way is_ordered() is another exemple, it should be named is_sorted() in my opinion. All pairs are ordered (they have a "first" and "second" element) Additionally I don't understand why you want to prevent users from sorting Edges when they are coming from directed graphs since you don t make a difference between edges of directed and undirected graphs. These are just "Pairs" so what you are saying is that you want to prevent a user from sorting a Pair. I am just trying to help improve the library in which you guys have done really a great job. You probably know better about it than me and I will find it normal if my suggestions get refused. |
For the extremely simple reason that
NOTHING is preventing you from doing this yourself. I have a stated objection to including this functionality in the public LG API because IT WILL CONFUSE PEOPLE. Bottom line: you can continue to debate the merits (or demerits) of having arcs, edges, other functionality - but in the absence of a PR of the type I described above, I will not take further part. |
In simple graphs :
An arc (directed edge) is an ordered pair of vertices
u-->v
A line (undirected edge) is a set of two vertices
u---v
Directed graphs have arcs, while undirected graphs have lines(often called edges).
https://en.wikipedia.org/wiki/Glossary_of_graph_theory#edge
These two objects are not equal
u-->v , v-->u
But these two are equal
u---v , v---u
In both Graphs.jl and LightGraphs.jl there is only the notion of Arcs that are called Edges and are used for both directed and undirected graphs with a confusing equality test of edges in undirected graphs.
At least in Graphs.jl it is possible to do a work around by redefining the operator
==
of Edges in parts of the code where only undirected edges are used. But it becomes more problematic in LightGraphs since the edges are just pairs and thus the operator to redefine is this one==(p::Pair, q::Pair) = (p.first==q.first) & (p.second==q.second)
The text was updated successfully, but these errors were encountered: