Comments (5)
I have another data point for this. In working on the dot package, the returned concrete edge type is not well defined in the API, so I cannot make type assertions to discover if the client want to add an edge attribute. At least not without hacky horribleness to test for WeightedEdge and then extract the Edge and then type assert on that. Given that WeightedEdge return from EdgeBetween/EdgeTo is not documented in the API AFAICS this probably should not happen.
from graph.
This interacts with the Edge methods in a difficult way when way only allow simple graphs (which is the case now). If we want a simple way to find all weights/costs from all nodes to all nodes, we expect that the cost from n to n is zero. The current API does not do this for us; retrieving the edge in this case gets us nil, which then has no valid weight to return.
I think the solution to this is change the weight handling from a method that takes an edge to a method that takes two nodes - this actually clarifies a another issue: if edges carry a weight then why do we have a weight method - because we don't get the edge first.
Another advantage we may get from this is that it makes it possible (though not required) to drop the path.HeuristicCoster interface since Weight does the same thing when an edge is not required; a weight returned in the absence of an edge is by necessity a heuristic weight.
from graph.
So to summarize this for my better understanding, what you propose is to change
type Weighter interface {
Weight(Edge) float64
}
to
type Weighter interface {
Weight(Node, Node) float64
}
That indeed sounds like a good idea, it could help to distinguish between edge-is-nil-because-there-is-no-edge (in which case heuristic cost could be returned) and edge-is-nil-because-it-is-a-loop-edge. The only downside is that if I already had the edge, to get its weight I'd have to retrieve it again (which can be more expensive than just look up a number in a matrix).
from graph.
That is correct. The issue that you raise is something I have thought about and am not sure about how to deal with - from another direction.
In full, with the changes that I would like to see here, graph.Edge gains a Weight method, so if you have the edge, you have the weight (I would expect that for existing edges, the graph would just return the held edge weight), so there is no need to call weight. If you don't have the edge, then to determine whether the weight returned by the graph's method is heuristic or concrete you would need to see if there was an edge - this is an additional cost. It could be saved by returning a boolean indicating that the weight came from an edge or self-loop or was calculated by a heuristic.
That there are two ways to find an edge weight is troubling for me, but it is the only way we can signal that a graph has edge weights that are meaningful via the type system. I think this is close to the least bad way. Designing a good API for graphs is difficult.
from graph.
from graph.
Related Issues (20)
- graph/all: consider using golang.org/x/tools/container/intsets HOT 2
- simple: DirectedDenseGraph.Edge() is incorrect HOT 1
- Remove/Add node bug in simple.DirectedGraph HOT 5
- go version: drop 1.3 support HOT 1
- internal: break package into conceptually related types and functions
- topo: panic messages in johnson cycles graph are wrong
- {path/...,topo}: lack package doc comments
- Paths from search HOT 3
- Failing search HOT 2
- community: add directed Louvain implementation HOT 4
- graph/community: add multiplex graph handling for community detection HOT 1
- simple: Self-referential nodes HOT 8
- graph/community: undirected edge API for directed graphs is incorrectly implemented HOT 1
- graph/community: error reporting is incorrect in TestReduceQConsistency* HOT 2
- topo: replace ConnectedComponents implementation with union-find HOT 2
- graphs/gen: Gnm documentation incorrect
- graphs/gen/batagelj_brandes.go should be renamed to erdos_renyi HOT 3
- graph/topo: hope to implements CyclesIn for undirect graph HOT 1
- Inline LICENSE file from github.com/gonum/license/LICENSE HOT 3
- graph/simple: directed acyclic graph HOT 2
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.