Capacity of a Vertex

In graph theory, the concept of the “capacity of a vertex” is not standard, but it can come into play in specialized algorithms like network flow problems. In such cases, a vertex capacity limits the amount of flow that can pass through that vertex, much like an edge capacity limits the flow along an edge.

You can visualize the concept of vertex capacity in a flow network.

Imagine a directed graph with vertices and edges. Each vertex would be represented as a circle, and each directed edge as an arrow connecting two circles. Now, place a number inside each circle. This number represents the vertex capacity, which is the maximum amount of flow that the vertex can handle.

To make this visual concept more explicit:

1. Draw three circles (A, B, C) and connect them with arrows (directed edges).
2. Label the arrows with the edge capacities.
3. Place numbers inside circles A, B, and C to denote their capacities.

This visual representation will help you understand that not only the edges but also the vertices have a limit on the amount of flow they can handle. The vertex capacity restricts the total incoming or outgoing flow at that vertex.

Solution

To implement vertex capacity, we need to adjust our graph representation. Instead of just storing vertices and edges, we store an additional value for each vertex representing its capacity.

Java

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

import java.util.HashMap;

public class Graph {
    HashMap<Integer, Integer> vertexCapacity = new HashMap<>();

    public void addVertex(int vertex, int capacity) {
        vertexCapacity.put(vertex, capacity);
    }

    public int getCapacity(int vertex) {
        return vertexCapacity.get(vertex);
    }
}

C++

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

#include <unordered_map>
using namespace std;

class Graph {
public:
    unordered_map<int, int> vertexCapacity;

    void addVertex(int vertex, int capacity) {
        vertexCapacity[vertex] = capacity;
    }

    int getCapacity(int vertex) {
        return vertexCapacity[vertex];
    }
};

Python

1
2
3
4
5
6
7
8
9

class Graph:
    def __init__(self):
        self.vertex_capacity = {}
    
    def add_vertex(self, vertex, capacity):
        self.vertex_capacity[vertex] = capacity

    def get_capacity(self, vertex):
        return self.vertex_capacity[vertex]

In these code snippets, we use a hash map called vertexCapacity to store the capacity of each vertex. The addVertex method adds a vertex along with its capacity, and the getCapacity method returns the capacity of a given vertex.

So, when dealing with specialized algorithms that require vertex capacity, this is how you might adapt your graph representation to accommodate it.