Maybe the naming would be a little weird for that use case, but they didn't specify what the output of `Neighbors(v)` is; I don't see any reason why it couldn't return a multiset or a relation (w, c) where `c` is the number of connections between `v` and `w`
Returning the same neighbor multiple times kind of misses the point. The point was that you need to return edges (not neighbors) because the edges connecting the same neighbors can be different.
Like, imagine two train lines between the same pair of stations. Or two roads between the same intersections. They might have different travel times, costs, etc.
I still don't see how this couldn't work with a `Neighbors(v)` function with an unspecified return type. The outputs I gave were examples of how it could be adapted for various use cases, not an exhaustive list of all possibilities; in the example with multiple edges with multiple weights, the output could instead be a relation of (v2, w, c) that indicates that v connects to v2 with weight w with c as the number different edges between the two with that weight.
In all of your earlier examples (and actually, including the current one too), you're treating vertices as first-class objects, but edges as second-class. There's no way to even identify an edge in your formulation -- only vertices.
This is a common oversight in graph structures that ends up being very annoying in many applications. You keep trying to work around it by associating the edge's properties with those of the vertex pairs and hoping that's sufficient for the application, but I'm trying to point out that the abstraction you're implicitly dancing around -- and the one that many practical uses need -- is actually one that treats edges as first-class. In fact, I would go further and say that if anything should be second-class, it ought to be the vertices, since they're already implied by the edges. (That is to say, for many practical applications of graphs, an edge determines its endpoints, but the endpoints don't determine the edge.)
I'm not clear what an abstraction that makes edges first class but vertices second class looks like. An edge connects two vertices, so if two edges connect to the same vertex, what does this look like?
The most minimal example of it I can think of would be a little ridiculous, but it could look like this:
interface Edge { }
interface Graph {
List<Edge> getRoots(); // Returns some ~minimal set of edges with connectivity to all the others
List<Edge> getAdjacentEdges(Edge e, boolean tail);
}
There's no way to directly refer to a vertex here at all (unlike with edges), and yet (since edges have identity) there's enough information to determine the graph structure!
Well to be fair, that constraint is also part of the mathematical definition of a graph, where the set of edges E is a binary relation over vertices V (i.e., a subset of V x V). You'd need either a multiset or a labelled relation (i.e., a subset of V x L x V for some set of labels L) to overcome that.
"Definitions in graph theory vary. [...] A multigraph is a generalization that allows multiple edges to have the same pair of endpoints. In some texts, multigraphs are simply called graphs."
It's a bit disingenuous to skip over the Graph subsection of that article, right after the "definitions vary" line:
> A graph (sometimes called an undirected graph to distinguish it from a directed graph, or a simple graph to distinguish it from a multigraph) is a pair G = (V, E), where V is a set whose elements are called vertices (singular: vertex), and E is a set of unordered pairs of vertices, whose elements are called edges (sometimes links or lines).
An unqualified "graph" is almost always this one—a simple, undirected graph. If you mean something different you almost always need to use one of the more specific names to be clear.
Sorry, I didn't intend to make it personal, I was just pointing out that the very next paragraph after the chunk you quoted included the definition of "graph" that lou1306 was referring to, almost verbatim.
Definitions sometimes vary, but lou1306 is correct on the merits that the most widely accepted definition of an unqualified "graph" states that "the set of edges E is a binary relation over vertices V (i.e., a subset of V x V)".