Comments (17)
Hey @warpfork :)
Yeah, this is something I need as well but unfortunatelly it's not just one map that's causing the issue. - Ignoring the underlying structure the edges/vertices are stored, the AdjacencyMap()
and PredecessorMap()
methods that are used by the various graph methods both return map[K]map[K]Edge[K]
.
Maybe something like the following could work?
I think it should be enough to satisfy the needs of the various callers.
Only reason this is an interface is to allow transparently refactoring the implementation in the future.
// placeholder names for struct/methods, suggestions welcome
type Edges interface {
Range(func(K, []K) bool)
GetPredecessors(K) []K
}
@dominikbraun I wonder if this could be tackled at the same time as #62?
from graph.
Ah, or are you thinking, if we want to be able to sort according to multiple algorithms, and so we should pass the
less
function, rather than make it a property of the vertex?
Exactly. The less
function doesn't need to be a vertex property because it's going to be the same for all vertices, and it could be different for functions other than TopologicalSort
, so accepting it as an argument would make sense.
from graph.
I wish I could tell you I would get to it this weekend, but I likely won't have time for another week. But post here as you go through it, and I will jump in as I can. I probably can be more helpful with test cases anyways, as that does not require knowing the internal guts of the graph implementation.
from graph.
@warpfork @tonglil @vito @deitch @williamfzc
This change has been released in graph v0.22.0.
from graph.
And a beautiful thing it is. Enjoying it right now.
from graph.
@dominikbraun I am seeing major performance degradation with the new sort, even if I do not use the stable function. A program that used to take 42s, with the sort func not even showing up in the flame graph, is now taking ~222s, with the sort the single largest factor. I will open a new issue and try to replicate it in a sample.
from graph.
@dominikbraun I wonder if this could be tackled at the same time as #62?
@geoah Sure, there's no need to refactor the edge storage twice.
from graph.
I was taking a quick look at this and since comparable
only allows for equality and not ordering, we can only go as far as making the sorting stable given the order the edges were added is the same.
Contraints like like constraints.Ordered would significantly limit what we could use for hashes, same with specifying an interface for hashes that could enable ordering.
Is there an obvious way of sorting comparables or something similar that I might be missing?
from graph.
Ah, I just came across this. I too am using TopologicalSort()
, and couldn't figure out why I was getting slightly different ordering each time, until I dug into it.
In my case, I would perfectly happy to do something like, "nodes at the same level, sort lexicographically by key", anything as long as it is consistent.
Has anyone figured a workaround to it?
from graph.
@deitch I'm not sure if there is a workaround with the existing functions other than implementing it yourself, but this issue is gaining more and more significance and hence will be tackled in one of the very next releases.
from graph.
other than implementing it yourself
That seems like a bit of a waste.
I have been thinking a bit about the UI. Are we thinking that we would have some additional property to each vertex, e.g. SortWeight
, such that it would be considered between various vertices, all else being equal? Or maybe SortFunc
, the same way as sortSlice()
takes a less
func?
Actually, I rather like that last option. It keeps you from having to predetermine what algorithms work for whom, and just let people set their own sort priority. If you want consistently stable, you always could have a default func that can get overridden.
How can I help?
from graph.
@deitch I'd also prefer a less
function for direct comparisons. That would be one way. The other way would be to keep track of the order in which the edges have been added to the graph as proposed by @warpfork. Would this approach work for you, too?
from graph.
keep track of the order in which the edges have been added to the graph
I am concerned that it can be arbitrary. For example, let's say I have a graph with 5 nodes with no dependencies, and 5 direct dependencies, one of each. Something like:
A -> 1
B -> 2
C -> 3
D -> 4
E -> 5
I would think a normal expectation would be that it wouldn't matter what order I added them, the graph is the same, and so the sort order should not depend if I added A->1 and later B->2 or the reverse.
However, if time does matter for some people, we could track when the nodes where added, and then they can use the less
style function to track it to meet their needs.
from graph.
Yes, I think you're right. A less
-function-style or lexicographical-style ordering of vertices is a saner default than a time-based ordering, at least when it comes to reproducibility.
When you are given a mere adjacency map or a representation like in your example, you can't make any assumptions about the order in which the edges have been added but only about the ordering of vertices that makes sense for your case.
We could provide a new function like StableTopologicalSort
(or something similar, to maintain backwards compatibility) which takes a less
function. If the user needs a time-based ordering, they could do this themselves within the less
function.
from graph.
Yup, answers all use cases.
I don't know that you need a new function. I would just use the existing one. Is there any case where someone might want to have non-stable sort intentionally?
Ah, or are you thinking, if we want to be able to sort according to multiple algorithms, and so we should pass the less
function, rather than make it a property of the vertex? I can see that. One time I might call sort with one function, another time with another, so it is important to have an argument, and hence we need an argument and therefore changing the func or adding a new one? Got it.
from graph.
If I can help, let me know.
from graph.
If you want, you can either help by implementing the new function, writing tests for the new function, or verify/test the new function once it is implemented. In any case, feedback is appreciated :-) I'm going to start with the implementation this weekend if nobody else wants to do it.
from graph.
Related Issues (20)
- Return a slice of all vertices in the graph. HOT 1
- RemoveVertex from graph HOT 2
- go1.20.5 type problem HOT 4
- GitHub Actions CI could be optimized HOT 1
- Shortest Path Doesn't Support Negative Edge Weights Properly HOT 6
- Query edges from/to given vertex HOT 4
- Vertex Attributes And Edge Attributes auto add double quote
- BFSWithDepth not calculating depth correctly HOT 3
- DAG Graph Pagination
- No way to list vertices? HOT 1
- How to split graph into disconnected subgraphs HOT 4
- Expose MemoryStore HOT 1
- can i find the leader/source vertex of a directed acyclic graph ? HOT 5
- multigraph support HOT 4
- Topological sort has a significant performance penalty HOT 1
- Feature Request: Add method for updating Vertex property HOT 1
- Feature: Add method for querying toVertex/fromVertex and steps HOT 1
- can value of vertexAttribute be of type 'any' ?
- guidance on marshaling/unmarshaling
- VertexAttributes func caching last values
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from graph.