Project description

NetGraph

🚧 Work in progress! 🚧

Python-test

Introduction
Use Case Examples

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:

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,
        },
    ),
}

Project details

These details have not been verified by PyPI

Project links

Homepage

Release history Release notifications | RSS feed

This version

0.5.0

Jan 15, 2024

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

ngraph-0.5.0.tar.gz (47.9 kB view hashes)

Uploaded Jan 15, 2024 Source

Built Distribution

ngraph-0.5.0-py3-none-any.whl (36.6 kB view hashes)

Uploaded Jan 15, 2024 Python 3

Hashes for ngraph-0.5.0.tar.gz

Hashes for ngraph-0.5.0.tar.gz
Algorithm	Hash digest
SHA256	`54b74327580c65bd19fe37378c1b3951efe99927bb442fec4b4359dc19278749`
MD5	`5fa42a001db033357648e08cbdfa6524`
BLAKE2b-256	`6e189727d315f6005e4bcc6f26dfdc5bb5d0ba87f6acf2c0fce8b5e7dc6583c8`

Hashes for ngraph-0.5.0-py3-none-any.whl

Hashes for ngraph-0.5.0-py3-none-any.whl
Algorithm	Hash digest
SHA256	`bd444a5f183b1eb36b623e80a1bc1cc9d98acb1eb78c3bb0ddda27496b939ec2`
MD5	`2ab424735a43e07983f03c3cb76adade`
BLAKE2b-256	`61f0a4357001835d2931f5ebbdb0d46afb0937795ca35614873d1ea0176bd211`