8
$\begingroup$

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously.

Yet, when I recently read here a question on real life example of graphs with negative weight edges I was amazed I never asked this one before:

Does anyone know a meaninfgul example of weighted graph where edges with zero weight make sense (other than non-existing edges)?

Negative weights may be allowed, but I would prefer cases where only positive weights are allowed, including zero weights.

Improve this question
$\endgroup$
6
  • 14
    $\begingroup$ Unless I am misunderstanding you, it seems like answers to the negative weights question you linked give answers to this question for free. Just consider what the edges represent (a force, a statistical correlation, a measure of profit, etc.) and ask yourself what it means when this value approaches or equals zero. All the examples I can think of where weights can be positive or negative have a reasonable interpretation at zero as well. $\endgroup$
    – stam_a
    Commented Dec 6, 2021 at 0:38
  • 1
    $\begingroup$ @stam_a You are right, the relevance of zero weights may be seen as a consequence of the relevance of negative weights. I did not want to exclude negative weights from my question, but I would really prefer an example with positive and possibly zero weights only. $\endgroup$
    – Matthieu Latapy
    Commented Dec 6, 2021 at 7:27
  • 1
    $\begingroup$ The answer I gave in the question you linked (cs.stackexchange.com/questions/146311/…) arguably also applies to this one. $\endgroup$
    – Austin Hemmelgarn
    Commented Dec 6, 2021 at 12:43
  • $\begingroup$ @MatthieuLatapy I kind of see what you are saying. Where the interpretation at zero is not merely a consequence of the negative interpretation. The arbitrage example I gave does seem to have a distinct interpretation at zero–when the transaction is perfectly efficient. Where the meaning at zero seems to come first and any deviations from zero are interpreted with respect to zero as opposed to the other way around. $\endgroup$
    – stam_a
    Commented Dec 6, 2021 at 17:32
  • $\begingroup$ Umm, graphs are abstract entities that don't exist in real life. $\endgroup$
    – einpoklum
    Commented Dec 6, 2021 at 20:59

11 Answers 11

Reset to default
25
$\begingroup$

Of course. The weight can mean things that are irrelevant to the existence of an edge.

Since you don't ask for a "list of say 6 or 7 real-life examples", I will just add one.

Consider a road network. If you want to find a path from A to B in a road network, you need to keep all the road segments that exist. There are two important measures:

  • Current amount of traffic
  • Additional costs for that specific path

That is, how quickly can we go from A to B, and how much does it cost.

  • Many roads have zero traffic at a given time, and you shouldn't delete the road segment.
  • Many roads have zero incurred cost, you should not delete these either.

Of course, you can change $t$ to be for example (as in the linked question) steepness, or other things like congestion, expected delays, or whatever else, e.g. "toll road cost" or expected number of trolls. The point is that the edge in itself is important. And many road segments have properties that can be explained with a zero.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you for this answer! It seems however that these examples would be modeled in ways that make zero weight edges equivalend to removed edges. For instance, if you want to avoid traffic, than you would compute some kind of (dynamic) edge capacity, and if an edge has too much traffic then its capacity drops to 0, meaning that you cannot use it, aka it is not there, right? $\endgroup$
    – Matthieu Latapy
    Commented Dec 6, 2021 at 7:33
  • 9
    $\begingroup$ No, on the contrary, the 0 means that there is 0 congestion and you prefer lower weight edges. Take also the example of "additional cost" e.g. toll boots. What is the extra cost of a road segment? Take also the expected energy used (for EVs) on a road segment. In all of those examples, you prefer a zero-weight edge over positively weighted edges. $\endgroup$
    – John Kemeny
    Commented Dec 6, 2021 at 8:08
  • 2
    $\begingroup$ And to add, in the congestion case, a non-existent road would be modeled by an edge with weight of infinity, not zero. $\endgroup$
    – justhalf
    Commented Dec 6, 2021 at 13:26
  • $\begingroup$ Sure, this was my point: instead of modeling congestion, I would model capacity, and then an infinite weight edge, equivalent to a non-existent edge, becomes a zero weight edge, if I am correct. $\endgroup$
    – Matthieu Latapy
    Commented Dec 6, 2021 at 15:50
  • 2
    $\begingroup$ @MatthieuLatapy That may be a different sort of question. 0 congestion may be a very natural notation (especially in the current era of big data observing the roads). You could choose to take the inverse, and make that "infinite capacity." However, you don't have to. If you're looking for real life applications of graphs that must have zero weight edges, that is a bit trickier. $\endgroup$
    – Cort Ammon
    Commented Dec 7, 2021 at 5:42
12
$\begingroup$

The classic strategy game Civilization by MicroProse represents the world map as a square grid where each node of the grid is a tile of the world map, representing some type of terrain. Players control civilian and military units over this map. Each unit has a specific allocation of movement points, and each terrain type costs a specific amount of movement points to traverse, sometimes depending on the unit type. For example, an armor unit may be able to move three tiles on a plain, but only one tile on a mountain. Due to the variable terrain cost for movement, pathfinding in this model can be conceived as a shortest path search in a weighted graph.

The game allows the construction of roads and railroads to facilitate the deployment of units. A railroad segment is constructed within a single tile at a time and renders movement completely free between two adjacent tiles containing a railroad segment each. For the purposes of pathfinding, tiles with this kind of railroad connection can therefore be treated as setting the edge weight between them to zero.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is by far the easiest to understand example here :) $\endgroup$
    – Kevin Sijbers
    Commented Dec 7, 2021 at 14:40
  • $\begingroup$ This might be correct in theory. But without looking at the sourcecode I am pretty certain that internally the weight of railroad edges used by the route finding algorithm is not zero but only very close to zero. Otherwise the algorithm might occasionally prefer a long railroad line over a short railroad line leading to the same tile. This might not make a difference mechanically, but it would look weird when visualizing unit movement. $\endgroup$
    – Philipp
    Commented Dec 8, 2021 at 17:33
9
$\begingroup$

In circuity, we often construct a graph of a circuit. Wires are typically modeled as 0 resistance because, frankly, measuring the resistance of wires is really tricky and rarely profitable. So if we have multiple devices connected to a single wire, we can treat that as separate vertices with 0 weight nodes between them.

We can transform them into one "supernode." Indeed, in many analyses we do so. However, the first step is almost always to get a graph with 0 weight edges, and then transform it.

This also has the advantage that, when we short a circuit and suddenly have to care about that minuscule resistance of each wire, the circuit we analyze is trivially comparable to the one we started with.

Improve this answer
$\endgroup$
4
$\begingroup$

Such a graph does not need to represent an actual road network. It can be anything representable by a network. For example, conversion options between various online banking and cryptocurrency services. Most of them have a little or more fee, but sometimes you can do it for free (most likely, internal conversions by the same service, like sending cash from your bank account to your credit card account).

If you want to buy bitcoin from the money on your bank account, the cheapest way is often not some direct service. This is yet more complex if you are also trying to speculate with bitcoin, and not only store cash in it. Finding the optimal way is a graph walking process where some edges have zero price.

Improve this answer
$\endgroup$
3
$\begingroup$

Distances and times (and other units of measurement)

Consider a graph where the edges are the driving distances between warehouses across the country. If two warehouses are on the same premises, they could potentially be given a distance of 0. Strictly speaking there might be some distance between them, but this may be considered negligible if the distance is small enough or if you can transport the goods without actually having to drive from one to the other.

Why not just merge those into one vertex? Wouldn't all the outgoing and incoming edges be duplicated? Not necessarily. If different warehouses serve different purposes, it could be reasonable for those 2 warehouses to be connected to different sets of other warehouses.

Or consider some arbitrary process flow graph (e.g. the general flow of processes and equipment inside a factory) with various tasks which each generally take a few days to complete, where the edges represent time.

Now consider a task that can be run in a few milliseconds on a computer. Under the right circumstances, one could reasonably just assign this an edge weight of 0.

As above, you may want to keep the vertices which have a 0-weight edge separate, because this can provide some visibility about the additional process and better reflect the real world, and the vertices can again be connected to different subsets of other vertices.

Improve this answer
$\endgroup$
2
$\begingroup$

Neural networks

A neural network assigns weights to each connection between the simulated neurons. As you say, when calculating the output of the network, any edges with zero weight are equivalent to missing connections.

However, the training step considers both the weight of the edge and the partial derivative of the output value with regards to the weight. In other words: to adjust the weight of each edge, the training algorithm calculates how much the change affects the output. If the edge was truly missing, it could never get a weight other than 0.

Improve this answer
$\endgroup$
2
$\begingroup$

Not sure if this is a stretch for this question, but an NFA for the regex (xx)? is

          ϵ
[Start] ─────→ [Accept]
   │              ↑
   └───── xx ─────┘

It's not technically a number, but semantically the ϵ edge is a "null"-weighted edge: you can take it without incurring any "cost" (which in this case might be consumption of characters).

So if you wanted to make an NFA for a regex (which you might, if e.g. the DFA is too large), you might end up with a transition like this.

Improve this answer
$\endgroup$
0
1
$\begingroup$

Airport terminals

(That's an interesting question and kind of a nice brain-teaser. I haven't seen the answers given in the other question, so I might be duplicating something)

Imagine a graph of world's international airport routes with:

  • each terminal being a vertex
  • each edge being a flight connection with scheduled flight time as its weight

Then quite naturally you would like to model two terminals of the same airport to be two distinct vertices, but the edge between being of 0 weight (as there's no flight time involved to move between them).

Improve this answer
$\endgroup$
1
$\begingroup$

Consider a road network that consists of segments of toll roads, with a fixed toll for each type of vehicle on each segment.

So we represent the road network as a graph and to work out the cost of a path add up the cost of the links in the path. However some links don't have tolls for bike, hence will have a zero cost.

If we removed these zero cost links from the graph for bikes, then we would need a seperate copy of graph for each vehicle type. This would then need many graphs to be edited whenever a road was changed.

Also if you ever work with real life map data you will find roads of zero length that can't be removed from the published data for practical reasons.

Improve this answer
$\endgroup$
1
$\begingroup$

Three computers (nodes a, b, and c) networked together (edges) with the amount of traffic between the each node the weight, in MB.

(a) <-- 50MB --> (b) <--+
 ^                      |
 |                     10MB
 |                      |
  \-- 0MB --> (c) <-----+

Here the edges are a<->b, b<->c, and a<->c with weights 50, 10, and 0. Negative weights are meaningless in this example -- a directed graph measuring traffic in each direction might be appropriate.

A previous comment mentioned roads. Maybe the weight is the number of cars per hour and maybe between 2:00AM and 3:00AM there were zero cars. The road didn't disappear, it just wasn't used.

Improve this answer
$\endgroup$
0
$\begingroup$

An video game example.

Take a game where raw resources are processed into more complex items. For example, Wire can be made from copper, but it can also be made from Iron.
The game does not differ between Regular Wire and Iron Wire (they are the same thing), hence edge weight of 0.
However, it is organizationally advantageous for player to consider them separate nodes, because of iron and copper availability in the area.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm not sure I follow the example. I would model this with three vertices (Copper, Iron, Wire) and two edges with positive weight (Copper->Wire, Iron->Wire). How are you imagining the graph and what's the zero-weight edge? $\endgroup$
    – John Kugelman
    Commented Dec 6, 2021 at 19:56
  • $\begingroup$ There are four ~lights~ vertices. Iron, Copper, Wire and IronWire. The last two have zero weight edge between them. They are the same from perspective of supplying Wire, but from point of resource availability and reasoning with other players, Wire(copper) and wire(iron) are different things, manufactured in different places. This comes in handy when planning bases - should I sit near iron and build all from iron, or move toward copper? Makes for nice optimization challenge when trying to find best location between N mines of different weights to minimize transport lanes. $\endgroup$
    – Thomas
    Commented Dec 7, 2021 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.