Weight Function for a Graph

A weight function for a graph assigns a weight or cost value to each edge. It represents numeric properties of the connections between vertices.

Some examples of graph weight functions:

• Shortest path weights - Travel time or distance
• Betweenness centrality - Number of shortest paths through edge
• Probabilistic weights - Likelihood of traversing edge

Java example - Random weight assignment:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Graph {

  class Edge {
    double weight;
  }

  public void assignWeights() {
    Random rand = new Random();
    for (Edge e : edges) {
      e.weight = rand.nextDouble();
    }
  }

}

C++ example - Distance weights:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

struct Graph {

  struct Edge {
    double weight;
  };

  void assignWeights(const vector<Point>& points) {
    for (Edge e : edges) {
      e.weight = dist(points[e.a], points[e.b]); 
    }
  }

};

Python example - Betweenness centrality:

1
2
3
4
5

class Graph:

  def assign_betweenness_weights(self):
    for edge in self.edges:
      edge.weight = self.num_shortest_paths_through(edge)

Weight functions allow modeling edge costs and numeric properties in graphs. Useful for optimization problems.

In graph theory, a weight function assigns a value, often referred to as “weight,” to each edge in the graph. This weight can represent distances, costs, or any other measure that one might want to optimize. For example, in a road network, the weight could represent the distance or time required to traverse from one city to another. Weighted graphs are often used in algorithms like Dijkstra’s shortest path, Kruskal’s algorithm, etc.

Let’s visualize a weighted graph to clarify the concept of a weight function for a graph. In a weighted graph, each edge has an assigned weight, often representing distances, costs, or other metrics.

Consider a simple graph with 4 vertices: A, B, C, and D. These vertices are connected by the following edges:

1. Edge AB with weight 5
2. Edge AC with weight 3
3. Edge BC with weight 2
4. Edge BD with weight 6
5. Edge CD with weight 4

Here’s a textual representation of this weighted graph:

     A --5-- B --6-- D
     |      /         |
     |     /          |
     3    2           4
     |  /             |
     C ---------------

The weight function ( w: E \rightarrow \mathbb{R} ) maps each edge to a real number, representing its weight:

• ( w(AB) = 5 )
• ( w(AC) = 3 )
• ( w(BC) = 2 )
• ( w(BD) = 6 )
• ( w(CD) = 4 )

This weight function is often a key part of algorithms that solve problems like finding the shortest path or minimum spanning tree.

The concept of a weight function in a graph assigns a numerical value to each edge in the graph. These values are often called “weights.”

Visual Representation:

Let’s consider a simple weighted graph with vertices A, B, C, and D and weights on the edges as follows:

 A---(2)---B
 |         |
(1)       (3)
 |         |
 D---(4)---C

In this graph:

• The edge between A and B has a weight of 2.
• The edge between B and C has a weight of 3.
• The edge between C and D has a weight of 4.
• The edge between D and A has a weight of 1.

The weight function w can be represented as a set of tuples:

• w(A, B) = 2
• w(B, C) = 3
• w(C, D) = 4
• w(D, A) = 1

Key Takeaway:

A weight function assigns numerical values to the edges of a graph. It’s commonly used in problems involving shortest paths, network flow, and many other optimization problems in graph theory.

Solution

Below are code examples that demonstrate how to implement a weight function for a graph in Java, C++, and Python.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import java.util.*;

public class WeightedGraph {
    private Map<Integer, Map<Integer, Integer>> graph;

    public WeightedGraph() {
        graph = new HashMap<>();
    }

    public void addEdge(int u, int v, int weight) {
        graph.putIfAbsent(u, new HashMap<>());
        graph.get(u).put(v, weight);
    }

    public int getWeight(int u, int v) {
        return graph.get(u).getOrDefault(v, Integer.MAX_VALUE);
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <iostream>
#include <map>
#include <limits>

class WeightedGraph {
private:
    std::map<int, std::map<int, int>> graph;
public:
    void addEdge(int u, int v, int weight) {
        graph[u][v] = weight;
    }

    int getWeight(int u, int v) {
        return graph[u].count(v) ? graph[u][v] : std::numeric_limits<int>::max();
    }
};

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class WeightedGraph:
    def __init__(self):
        self.graph = {}
        
    def add_edge(self, u, v, weight):
        if u not in self.graph:
            self.graph[u] = {}
        self.graph[u][v] = weight
        
    def get_weight(self, u, v):
        return self.graph.get(u, {}).get(v, float('inf'))

Key Takeaways

• A weight function assigns a value to each edge in the graph.
• Weighted graphs are foundational in several important graph algorithms.
• The code examples use a nested map (Java, C++) or dictionary (Python) to hold the weight values for each edge.