Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
net_utils_example.cc File Reference

Network Utilities: Generation, Visualization, Serialization. More...

#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <chrono>
#include <limits>
#include <tpl_net.H>
#include <tpl_maxflow.H>
#include <net_utils.H>
Include dependency graph for net_utils_example.cc:

Go to the source code of this file.

Typedefs

using FlowType = double
 
using Net = Net_Graph< Net_Node< string >, Net_Arc< Empty_Class, FlowType > >
 
using Node = Net::Node
 

Functions

static size_t density_to_num_arcs (size_t n, double density)
 
static void add_super_source_and_sink (Net &net)
 
void print_network_stats (Net &net, const string &title)
 Print network statistics.
 
void demo_random_networks ()
 Demo 1: Random Network Generation.
 
void demo_grid_networks ()
 Demo 2: Grid Network Generation.
 
void demo_layered_networks ()
 Demo 3: Layered Network Generation.
 
void demo_dot_export ()
 Demo 4: DOT Export for Visualization.
 
void demo_json_export ()
 Demo 5: JSON Serialization.
 
void demo_benchmarking ()
 Demo 6: Benchmarking.
 
int main ()
 

Detailed Description

Network Utilities: Generation, Visualization, Serialization.

This example demonstrates utility functions for working with flow networks in Aleph-w. These utilities help with network generation, visualization, serialization, and benchmarking, making it easier to work with flow networks in practice.

Why Network Utilities?

Working with flow networks often requires:

  • Generating test networks: For algorithm development and testing
  • Visualizing networks: To understand structure and debug
  • Saving/loading networks: For persistence and sharing
  • Benchmarking: To compare algorithm performance

Features

1. Network Generation

Random Networks

  • Approximate density: Choose an edge count from a target density
  • Random capacities: Assign random capacities to edges
  • Configurable size: Control number of vertices and edges

Grid Networks

  • Regular structure: Grid-based networks for benchmarking
  • Predictable: Known properties for testing
  • Scalable: Easy to generate large grids

Layered Networks

  • DAG structure: Directed acyclic graphs
  • Layered layout: Vertices organized in layers
  • Applications: Perfect for DAG-based flow problems

Bipartite Networks

  • Two sets: Vertices divided into two sets
  • Matching problems: Ideal for bipartite matching
  • Applications: Job assignment, resource allocation

2. Visualization

DOT Format Export

  • GraphViz compatibility: Export to DOT format
  • Visualization tools: Use GraphViz, dot, neato, etc.
  • Customizable: Show capacities, flows, labels

3. Serialization

JSON Export

  • Human-readable: Easy to inspect and edit
  • Structured data: Preserve network structure
  • Interoperability: Work with other tools

DIMACS Format

  • Standard format: DIMACS challenge format
  • Compatibility: Work with other max-flow solvers
  • Benchmarking: Use standard test cases

4. Benchmarking

  • Compare algorithm performance
  • Generate test cases
See also
net_utils.H
Author
Leandro Rabindranath León

Definition in file net_utils_example.cc.

Typedef Documentation

◆ FlowType

using FlowType = double

Definition at line 118 of file net_utils_example.cc.

◆ Net

Definition at line 119 of file net_utils_example.cc.

◆ Node

using Node = Net::Node

Definition at line 120 of file net_utils_example.cc.

Function Documentation

◆ add_super_source_and_sink()

◆ demo_benchmarking()

◆ demo_dot_export()

void demo_dot_export ( )

◆ demo_grid_networks()

void demo_grid_networks ( )

Demo 2: Grid Network Generation.

Definition at line 227 of file net_utils_example.cc.

References Aleph::dinic_maximum_flow(), Aleph::maps(), print_network_stats(), and Aleph::size().

Referenced by main().

◆ demo_json_export()

void demo_json_export ( )

Demo 5: JSON Serialization.

Definition at line 343 of file net_utils_example.cc.

References add_super_source_and_sink(), density_to_num_arcs(), Aleph::dinic_maximum_flow(), Aleph::maps(), and Aleph::network_to_json_string().

Referenced by main().

◆ demo_layered_networks()

void demo_layered_networks ( )

Demo 3: Layered Network Generation.

Definition at line 258 of file net_utils_example.cc.

References Aleph::dinic_maximum_flow(), l, Aleph::maps(), and print_network_stats().

Referenced by main().

◆ demo_random_networks()

void demo_random_networks ( )

Demo 1: Random Network Generation.

Definition at line 185 of file net_utils_example.cc.

References add_super_source_and_sink(), density_to_num_arcs(), Aleph::dinic_maximum_flow(), Aleph::maps(), and print_network_stats().

Referenced by main().

◆ density_to_num_arcs()

static size_t density_to_num_arcs ( size_t  n,
double  density 
)
static

Definition at line 122 of file net_utils_example.cc.

References Aleph::maps().

Referenced by demo_benchmarking(), demo_json_export(), and demo_random_networks().

◆ main()

◆ print_network_stats()

void print_network_stats ( Net net,
const string &  title 
)