ngraph 0.5.0

A library for network modeling and capacity analysis.

NetGraph

🚧 Work in progress! 🚧

• Introduction
• Use Case Examples
  • Calculate MaxFlow in a graph
  • Place traffic demands on a graph
  • Perform basic capacity analysis

---

Introduction

This library is developed to help with network modeling and capacity analysis use-cases. The graph implementation in this library is a wrapper around MultiDiGraph of NetworkX. Our implementation makes edges explicitly addressable which is important in traffic engineering applications.

The lib provides the following main primitives:

• MultiDiGraph
• Demand
• FlowPolicy

Besides, it provides a number of path finding and capacity calculation functions that can be used independently.

---

Use Case Examples

Calculate MaxFlow in a graph

• Calculate MaxFlow across all possible paths between the source and destination nodes

  # Required imports
  from ngraph.lib.graph import MultiDiGraph
  from ngraph.lib.max_flow import calc_max_flow
  
  # Create a graph with parallel edges
  # Metric:
  #      [1,1]      [1,1]
  #   ┌────────►B─────────┐
  #   │                   │
  #   │                   ▼
  #   A                   C
  #   │                   ▲
  #   │   [2]        [2]  │
  #   └────────►D─────────┘
  #
  # Capacity:
  #      [1,2]      [1,2]
  #   ┌────────►B─────────┐
  #   │                   │
  #   │                   ▼
  #   A                   C
  #   │                   ▲
  #   │   [3]        [3]  │
  #   └────────►D─────────┘
  g = MultiDiGraph()
  g.add_edge("A", "B", metric=1, capacity=1)
  g.add_edge("B", "C", metric=1, capacity=1)
  g.add_edge("A", "B", metric=1, capacity=2)
  g.add_edge("B", "C", metric=1, capacity=2)
  g.add_edge("A", "D", metric=2, capacity=3)
  g.add_edge("D", "C", metric=2, capacity=3)
  
  # Calculate MaxFlow between the source and destination nodes
  max_flow = calc_max_flow(g, "A", "C")
  
  # We can verify that the result is as expected
  assert max_flow == 6.0
  

• Calculate MaxFlow leveraging only the shortest paths between the source and destination nodes

  # Required imports
  from ngraph.lib.graph import MultiDiGraph
  from ngraph.lib.max_flow import calc_max_flow
  
  # Create a graph with parallel edges
  # Metric:
  #      [1,1]      [1,1]
  #   ┌────────►B─────────┐
  #   │                   │
  #   │                   ▼
  #   A                   C
  #   │                   ▲
  #   │   [2]        [2]  │
  #   └────────►D─────────┘
  #
  # Capacity:
  #      [1,2]      [1,2]
  #   ┌────────►B─────────┐
  #   │                   │
  #   │                   ▼
  #   A                   C
  #   │                   ▲
  #   │   [3]        [3]  │
  #   └────────►D─────────┘
  g = MultiDiGraph()
  g.add_edge("A", "B", metric=1, capacity=1)
  g.add_edge("B", "C", metric=1, capacity=1)
  g.add_edge("A", "B", metric=1, capacity=2)
  g.add_edge("B", "C", metric=1, capacity=2)
  g.add_edge("A", "D", metric=2, capacity=3)
  g.add_edge("D", "C", metric=2, capacity=3)
  
  # Calculate MaxFlow between the source and destination nodes
  # Flows will be placed only on the shortest paths
  max_flow = calc_max_flow(g, "A", "C", shortest_path=True)
  
  # We can verify that the result is as expected
  assert max_flow == 3.0
  

• Calculate MaxFlow balancing flows equally across the shortest paths between the source and destination nodes

  # Required imports
  from ngraph.lib.graph import MultiDiGraph
  from ngraph.lib.max_flow import calc_max_flow
  from ngraph.lib.common import FlowPlacement
  
  # Create a graph with parallel edges
  # Metric:
  #      [1,1]      [1,1]
  #   ┌────────►B─────────┐
  #   │                   │
  #   │                   ▼
  #   A                   C
  #   │                   ▲
  #   │   [2]        [2]  │
  #   └────────►D─────────┘
  #
  # Capacity:
  #      [1,2]      [1,2]
  #   ┌────────►B─────────┐
  #   │                   │
  #   │                   ▼
  #   A                   C
  #   │                   ▲
  #   │   [3]        [3]  │
  #   └────────►D─────────┘
  g = MultiDiGraph()
  g.add_edge("A", "B", metric=1, capacity=1)
  g.add_edge("B", "C", metric=1, capacity=1)
  g.add_edge("A", "B", metric=1, capacity=2)
  g.add_edge("B", "C", metric=1, capacity=2)
  g.add_edge("A", "D", metric=2, capacity=3)
  g.add_edge("D", "C", metric=2, capacity=3)
  
  # Calculate MaxFlow between the source and destination nodes
  # Flows will be equally balanced across the shortest paths
  max_flow = calc_max_flow(
      g, "A", "C", shortest_path=True, flow_placement=FlowPlacement.EQUAL_BALANCED
  )
  
  # We can verify that the result is as expected
  assert max_flow == 2.0
  

Place traffic demands on a graph

• Place traffic demands leveraging all possible paths in a graph

  # Required imports
  from ngraph.lib.graph import MultiDiGraph
  from ngraph.lib.common import init_flow_graph
  from ngraph.lib.demand import FlowPolicyConfig, Demand, get_flow_policy
  from ngraph.lib.flow import FlowIndex
  
  # Create a graph
  # Metric:
  #     [1]        [1]
  #   ┌──────►B◄──────┐
  #   │               │
  #   │               │
  #   │               │
  #   ▼      [1]      ▼
  #   A◄─────────────►C
  #
  # Capacity:
  #     [15]      [15]
  #   ┌──────►B◄──────┐
  #   │               │
  #   │               │
  #   │               │
  #   ▼      [5]      ▼
  #   A◄─────────────►C
  g = MultiDiGraph()
  g.add_edge("A", "B", metric=1, capacity=15, label="1")
  g.add_edge("B", "A", metric=1, capacity=15, label="1")
  g.add_edge("B", "C", metric=1, capacity=15, label="2")
  g.add_edge("C", "B", metric=1, capacity=15, label="2")
  g.add_edge("A", "C", metric=1, capacity=5, label="3")
  g.add_edge("C", "A", metric=1, capacity=5, label="3")
  
  # Initialize a flow graph
  r = init_flow_graph(g)
  
  # Create traffic demands
  demands = [
      Demand(
          "A",
          "C",
          20,
      ),
      Demand(
          "C",
          "A",
          20,
      ),
  ]
  
  # Place traffic demands onto the flow graph
  for demand in demands:
      # Create a flow policy with required parameters or
      # use one of the predefined policies from FlowPolicyConfig
      flow_policy = get_flow_policy(FlowPolicyConfig.TE_UCMP_UNLIM)
  
      # Place demand using the flow policy
      demand.place(r, flow_policy)
  
  # We can verify that all demands were placed as expected
  for demand in demands:
      assert demand.placed_demand == 20
  
  assert r.get_edges() == {
      0: (
          "A",
          "B",
          0,
          {
              "capacity": 15,
              "flow": 15.0,
              "flows": {
                  FlowIndex(src_node="A", dst_node="C", flow_class=0, flow_id=1): 15.0
              },
              "label": "1",
              "metric": 1,
          },
      ),
      1: (
          "B",
          "A",
          1,
          {
              "capacity": 15,
              "flow": 15.0,
              "flows": {
                  FlowIndex(src_node="C", dst_node="A", flow_class=0, flow_id=1): 15.0
              },
              "label": "1",
              "metric": 1,
          },
      ),
      2: (
          "B",
          "C",
          2,
          {
              "capacity": 15,
              "flow": 15.0,
              "flows": {
                  FlowIndex(src_node="A", dst_node="C", flow_class=0, flow_id=1): 15.0
              },
              "label": "2",
              "metric": 1,
          },
      ),
      3: (
          "C",
          "B",
          3,
          {
              "capacity": 15,
              "flow": 15.0,
              "flows": {
                  FlowIndex(src_node="C", dst_node="A", flow_class=0, flow_id=1): 15.0
              },
              "label": "2",
              "metric": 1,
          },
      ),
      4: (
          "A",
          "C",
          4,
          {
              "capacity": 5,
              "flow": 5.0,
              "flows": {
                  FlowIndex(src_node="A", dst_node="C", flow_class=0, flow_id=0): 5.0
              },
              "label": "3",
              "metric": 1,
          },
      ),
      5: (
          "C",
          "A",
          5,
          {
              "capacity": 5,
              "flow": 5.0,
              "flows": {
                  FlowIndex(src_node="C", dst_node="A", flow_class=0, flow_id=0): 5.0
              },
              "label": "3",
              "metric": 1,
          },
      ),
  }