net_utils.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
#ifndef NET_UTILS_H
#define NET_UTILS_H
 
#include <fstream>
#include <sstream>
#include <random>
#include <chrono>
#include <iomanip>
#include <tpl_net.H>
#include <tpl_netcost.H>
#include <tpl_dynMapTree.H>
 
namespace Aleph
{
 
//==============================================================================
// NETWORK GENERATORS
//==============================================================================
 
struct NetworkGenParams
{
  size_t num_nodes = 10;           
  size_t num_arcs = 20;            
  double min_capacity = 1.0;       
  double max_capacity = 100.0;     
  double min_cost = 0.0;           
  double max_cost = 10.0;          
  bool ensure_connected = true;    
  unsigned seed = 0;               
};
 
template <class Net>
Net generate_random_network(const NetworkGenParams& params)
{
  using Node = typename Net::Node;
  using Flow_Type = typename Net::Flow_Type;
 
  Net net;
 
  // Initialize RNG
  unsigned seed = params.seed;
  if (seed == 0)
    seed = static_cast<unsigned>(
        std::chrono::system_clock::now().time_since_epoch().count());
 
  std::mt19937 gen(seed);
  std::uniform_real_distribution<double> cap_dist(params.min_capacity,
                                                   params.max_capacity);
  std::uniform_int_distribution<size_t> node_dist(0, params.num_nodes - 1);
 
  // Create nodes
  std::vector<Node*> nodes(params.num_nodes);
  for (size_t i = 0; i < params.num_nodes; ++i)
    nodes[i] = net.insert_node();
 
  // Set source and sink
  // Sources and sinks are detected automatically by Net_Graph
  // based on which nodes have no incoming/outgoing arcs
 
  // Ensure connectivity: create a path from source to sink
  if (params.ensure_connected)
    {
      for (size_t i = 0; i < params.num_nodes - 1; ++i)
        {
          Flow_Type cap = static_cast<Flow_Type>(cap_dist(gen));
          net.insert_arc(nodes[i], nodes[i + 1], cap);
        }
    }
 
  // Add random arcs
  size_t arcs_to_add = params.num_arcs;
  if (params.ensure_connected)
    arcs_to_add -= (params.num_nodes - 1);
 
  for (size_t i = 0; i < arcs_to_add; ++i)
    {
      size_t src = node_dist(gen);
      size_t tgt = node_dist(gen);
 
      // Avoid self-loops
      if (src == tgt)
        {
          tgt = (tgt + 1) % params.num_nodes;
        }
 
      Flow_Type cap = static_cast<Flow_Type>(cap_dist(gen));
      net.insert_arc(nodes[src], nodes[tgt], cap);
    }
 
  return net;
}
 
template <class Net>
Net generate_random_network(size_t num_nodes, size_t num_arcs,
                            double min_cap = 1.0, double max_cap = 100.0,
                            unsigned seed = 0)
{
  NetworkGenParams params;
  params.num_nodes = num_nodes;
  params.num_arcs = num_arcs;
  params.min_capacity = min_cap;
  params.max_capacity = max_cap;
  params.seed = seed;
  return generate_random_network<Net>(params);
}
 
template <class Net>
Net generate_grid_network(size_t rows, size_t cols,
                          typename Net::Flow_Type capacity,
                          bool bidirectional = true)
{
  using Node = typename Net::Node;
 
  Net net;
  std::vector<std::vector<Node*>> nodes(rows, std::vector<Node*>(cols));
 
  // Create nodes
  for (size_t i = 0; i < rows; ++i)
    for (size_t j = 0; j < cols; ++j)
      nodes[i][j] = net.insert_node();
 
  // Create horizontal arcs
  for (size_t i = 0; i < rows; ++i)
    for (size_t j = 0; j < cols - 1; ++j)
      {
        net.insert_arc(nodes[i][j], nodes[i][j+1], capacity);
        if (bidirectional)
          net.insert_arc(nodes[i][j+1], nodes[i][j], capacity);
      }
 
  // Create vertical arcs
  for (size_t i = 0; i < rows - 1; ++i)
    for (size_t j = 0; j < cols; ++j)
      {
        net.insert_arc(nodes[i][j], nodes[i+1][j], capacity);
        if (bidirectional)
          net.insert_arc(nodes[i+1][j], nodes[i][j], capacity);
      }
 
  // Source (top-left) and sink (bottom-right) are detected automatically
  // since nodes[0][0] has no incoming arcs and nodes[rows-1][cols-1] has no outgoing arcs
 
  return net;
}
 
template <class Net>
Net generate_bipartite_network(size_t left_size, size_t right_size,
                                double edge_prob = 0.5,
                                unsigned seed = 0)
{
  using Node = typename Net::Node;
  using Flow_Type = typename Net::Flow_Type;
 
  Net net;
 
  if (seed == 0)
    seed = static_cast<unsigned>(
        std::chrono::system_clock::now().time_since_epoch().count());
 
  std::mt19937 gen(seed);
  std::uniform_real_distribution<double> prob_dist(0.0, 1.0);
 
  // Create source and sink
  Node* source = net.insert_node();
  Node* sink = net.insert_node();
 
  // Create left nodes
  std::vector<Node*> left_nodes(left_size);
  for (size_t i = 0; i < left_size; ++i)
    {
      left_nodes[i] = net.insert_node();
      net.insert_arc(source, left_nodes[i], Flow_Type{1});
    }
 
  // Create right nodes
  std::vector<Node*> right_nodes(right_size);
  for (size_t i = 0; i < right_size; ++i)
    {
      right_nodes[i] = net.insert_node();
      net.insert_arc(right_nodes[i], sink, Flow_Type{1});
    }
 
  // Create random edges between left and right
  for (size_t i = 0; i < left_size; ++i)
    for (size_t j = 0; j < right_size; ++j)
      if (prob_dist(gen) < edge_prob)
        net.insert_arc(left_nodes[i], right_nodes[j], Flow_Type{1});
 
  // Source and sink are detected automatically
 
  return net;
}
 
template <class Net>
Net generate_layered_network(const std::vector<size_t>& layer_sizes,
                              typename Net::Flow_Type capacity,
                              double edge_prob = 0.5,
                              unsigned seed = 0)
{
  using Node = typename Net::Node;
 
  Net net;
 
  if (layer_sizes.size() < 2)
    return net;
 
  for (size_t l = 1; l + 1 < layer_sizes.size(); ++l)
    ah_invalid_argument_if(layer_sizes[l] == 0)
      << "Intermediate layers must be non-empty";
 
 
  if (seed == 0)
    seed = static_cast<unsigned>(
        std::chrono::system_clock::now().time_since_epoch().count());
 
  std::mt19937 gen(seed);
  std::uniform_real_distribution<double> prob_dist(0.0, 1.0);
 
  // Create nodes for each layer
  std::vector<std::vector<Node*>> layers(layer_sizes.size());
  for (size_t l = 0; l < layer_sizes.size(); ++l)
    {
      layers[l].resize(layer_sizes[l]);
      for (size_t i = 0; i < layer_sizes[l]; ++i)
        layers[l][i] = net.insert_node();
    }
 
  // Connect adjacent layers
  for (size_t l = 0; l < layer_sizes.size() - 1; ++l)
    {
      // Track which nodes in layer l+1 received at least one incoming arc
      // so we can guarantee no intermediate node has in-degree 0 (which
      // would make it an extra source and break is_single_source()).
      std::vector<bool> reached(layers[l+1].size(), false);
 
      for (size_t i = 0; i < layers[l].size(); ++i)
        {
          bool connected = false;
          for (size_t j = 0; j < layers[l+1].size(); ++j)
            if (prob_dist(gen) < edge_prob)
              {
                net.insert_arc(layers[l][i], layers[l+1][j], capacity);
                connected = true;
                reached[j] = true;
              }
 
          // Ensure every node in layer l has at least one outgoing arc
          if (not connected and not layers[l+1].empty())
            {
              size_t j = gen() % layers[l+1].size();
              net.insert_arc(layers[l][i], layers[l+1][j], capacity);
              reached[j] = true;
            }
        }
 
      // Ensure every node in layer l+1 has at least one incoming arc;
      // otherwise it would be an extra source and fail is_single_source().
      if (not layers[l].empty())
        for (size_t j = 0; j < layers[l+1].size(); ++j)
          if (not reached[j])
            {
              size_t i = gen() % layers[l].size();
              net.insert_arc(layers[l][i], layers[l+1][j], capacity);
            }
    }
 
  // Source and sink are detected automatically
 
  return net;
}
 
 
//==============================================================================
// DOT/GRAPHVIZ EXPORT
//==============================================================================
 
struct DotExportOptions
{
  bool show_flow = true;           
  bool show_capacity = true;       
  bool show_cost = false;          
  bool highlight_saturated = true; 
  bool highlight_empty = false;    
  bool use_colors = true;          
  std::string graph_name = "Network";
  std::string source_color = "green";
  std::string sink_color = "red";
  std::string saturated_color = "blue";
  std::string empty_color = "gray";
};
 
template <class Net>
void export_network_to_dot(const Net& net, const std::string& filename,
                           const DotExportOptions& options = DotExportOptions())
{
  using Node = typename Net::Node;
 
  std::ofstream out(filename);
  if (not out)
    return;
 
  // Build node ID map
  DynMapTree<Node*, size_t> node_ids;
  size_t id = 0;
  for (Node_Iterator<Net> it(net); it.has_curr(); it.next_ne())
    node_ids[it.get_curr()] = id++;
 
  out << "digraph " << options.graph_name << " {\n";
  out << "  rankdir=LR;\n";
  out << "  node [shape=circle];\n";
 
  // Export nodes
  for (Node_Iterator<Net> it(net); it.has_curr(); it.next_ne())
    {
      Node* p = it.get_curr();
      out << "  " << node_ids[p];
 
      std::string color;
      if (net.is_single_source() and p == net.get_source())
        color = options.source_color;
      else if (net.is_single_sink() and p == net.get_sink())
        color = options.sink_color;
 
      if (not color.empty() and options.use_colors)
        out << " [style=filled, fillcolor=" << color << "]";
 
      out << ";\n";
    }
 
  // Export arcs
  for (Arc_Iterator<Net> it(net); it.has_curr(); it.next_ne())
    {
      auto arc = it.get_curr();
      Node* src = net.get_src_node(arc);
      Node* tgt = net.get_tgt_node(arc);
 
      out << "  " << node_ids[src] << " -> " << node_ids[tgt];
 
      // Build label
      std::ostringstream label;
      if (options.show_flow or options.show_capacity)
        {
          label << "\"";
          if (options.show_flow)
            label << arc->flow;
          if (options.show_flow and options.show_capacity)
            label << "/";
          if (options.show_capacity)
            label << arc->cap;
          label << "\"";
        }
 
      // Build style
      std::string color;
      if (options.use_colors)
        {
          if (options.highlight_saturated and arc->flow == arc->cap)
            color = options.saturated_color;
          else if (options.highlight_empty and arc->flow == 0)
            color = options.empty_color;
        }
 
      out << " [";
      if (not label.str().empty())
        out << "label=" << label.str();
      if (not color.empty())
        {
          if (not label.str().empty())
            out << ", ";
          out << "color=" << color;
        }
      out << "];\n";
    }
 
  out << "}\n";
}
 
template <class Net>
std::string network_to_dot_string(const Net& net,
                                   const DotExportOptions& options = DotExportOptions())
{
  using Node = typename Net::Node;
 
  std::ostringstream out;
 
  // Build node ID map
  DynMapTree<Node*, size_t> node_ids;
  size_t id = 0;
  for (Node_Iterator<Net> it(net); it.has_curr(); it.next_ne())
    node_ids[it.get_curr()] = id++;
 
  out << "digraph " << options.graph_name << " {\n";
  out << "  rankdir=LR;\n";
  out << "  node [shape=circle];\n";
 
  // Export nodes
  for (Node_Iterator<Net> it(net); it.has_curr(); it.next_ne())
    {
      Node* p = it.get_curr();
      out << "  " << node_ids[p];
 
      std::string color;
      if (net.is_single_source() and p == net.get_source())
        color = options.source_color;
      else if (net.is_single_sink() and p == net.get_sink())
        color = options.sink_color;
 
      if (not color.empty() and options.use_colors)
        out << " [style=filled, fillcolor=" << color << "]";
 
      out << ";\n";
    }
 
  // Export arcs
  for (Arc_Iterator<Net> it(net); it.has_curr(); it.next_ne())
    {
      auto arc = it.get_curr();
      Node* src = net.get_src_node(arc);
      Node* tgt = net.get_tgt_node(arc);
 
      out << "  " << node_ids[src] << " -> " << node_ids[tgt];
 
      std::ostringstream label;
      if (options.show_flow or options.show_capacity)
        {
          label << "\"";
          if (options.show_flow)
            label << arc->flow;
          if (options.show_flow and options.show_capacity)
            label << "/";
          if (options.show_capacity)
            label << arc->cap;
          label << "\"";
        }
 
      std::string color;
      if (options.use_colors)
        {
          if (options.highlight_saturated and arc->flow == arc->cap)
            color = options.saturated_color;
          else if (options.highlight_empty and arc->flow == 0)
            color = options.empty_color;
        }
 
      out << " [";
      if (not label.str().empty())
        out << "label=" << label.str();
      if (not color.empty())
        {
          if (not label.str().empty())
            out << ", ";
          out << "color=" << color;
        }
      out << "];\n";
    }
 
  out << "}\n";
 
  return out.str();
}
 
 
//==============================================================================
// JSON SERIALIZATION
//==============================================================================
 
template <class Net>
void export_network_to_json(const Net& net, const std::string& filename)
{
  using Node = typename Net::Node;
 
  std::ofstream out(filename);
  if (not out)
    return;
 
  // Build node ID map
  DynMapTree<Node*, size_t> node_ids;
  size_t id = 0;
  for (Node_Iterator<Net> it(net); it.has_curr(); it.next_ne())
    node_ids[it.get_curr()] = id++;
 
  out << "{\n";
 
  // Nodes
  out << "  \"num_nodes\": " << net.vsize() << ",\n";
  out << "  \"num_arcs\": " << net.esize() << ",\n";
 
  // Source and sink
  if (net.is_single_source())
    out << "  \"source\": " << node_ids[net.get_source()] << ",\n";
  if (net.is_single_sink())
    out << "  \"sink\": " << node_ids[net.get_sink()] << ",\n";
 
  // Arcs
  out << "  \"arcs\": [\n";
  bool first = true;
  for (Arc_Iterator<Net> it(net); it.has_curr(); it.next_ne())
    {
      if (not first)
        out << ",\n";
      first = false;
 
      auto arc = it.get_curr();
      out << "    {"
          << "\"src\": " << node_ids[net.get_src_node(arc)] << ", "
          << "\"tgt\": " << node_ids[net.get_tgt_node(arc)] << ", "
          << "\"cap\": " << arc->cap << ", "
          << "\"flow\": " << arc->flow
          << "}";
    }
  out << "\n  ]\n";
  out << "}\n";
}
 
template <class Net>
std::string network_to_json_string(const Net& net)
{
  using Node = typename Net::Node;
 
  std::ostringstream out;
 
  // Build node ID map
  DynMapTree<Node*, size_t> node_ids;
  size_t id = 0;
  for (Node_Iterator<Net> it(net); it.has_curr(); it.next_ne())
    node_ids[it.get_curr()] = id++;
 
  out << "{\n";
  out << "  \"num_nodes\": " << net.vsize() << ",\n";
  out << "  \"num_arcs\": " << net.esize() << ",\n";
 
  if (net.is_single_source())
    out << "  \"source\": " << node_ids[net.get_source()] << ",\n";
  if (net.is_single_sink())
    out << "  \"sink\": " << node_ids[net.get_sink()] << ",\n";
 
  out << "  \"arcs\": [\n";
  bool first = true;
  for (Arc_Iterator<Net> it(net); it.has_curr(); it.next_ne())
    {
      if (not first)
        out << ",\n";
      first = false;
 
      auto arc = it.get_curr();
      out << "    {"
          << "\"src\": " << node_ids[net.get_src_node(arc)] << ", "
          << "\"tgt\": " << node_ids[net.get_tgt_node(arc)] << ", "
          << "\"cap\": " << arc->cap << ", "
          << "\"flow\": " << arc->flow
          << "}";
    }
  out << "\n  ]\n";
  out << "}\n";
 
  return out.str();
}
 
 
//==============================================================================
// DIMACS FORMAT
//==============================================================================
 
template <class Net>
void export_network_to_dimacs(const Net& net, const std::string& filename)
{
  using Node = typename Net::Node;
 
  std::ofstream out(filename);
  if (not out)
    return;
 
  // Build node ID map (1-based for DIMACS)
  DynMapTree<Node*, size_t> node_ids;
  size_t id = 1;  // DIMACS is 1-indexed
  for (Node_Iterator<Net> it(net); it.has_curr(); it.next_ne())
    node_ids[it.get_curr()] = id++;
 
  // Header
  out << "c Network exported from Aleph-w\n";
  out << "p max " << net.vsize() << " " << net.esize() << "\n";
 
  // Source and sink
  if (net.is_single_source())
    out << "n " << node_ids[net.get_source()] << " s\n";
  if (net.is_single_sink())
    out << "n " << node_ids[net.get_sink()] << " t\n";
 
  // Arcs
  for (Arc_Iterator<Net> it(net); it.has_curr(); it.next_ne())
    {
      auto arc = it.get_curr();
      out << "a " << node_ids[net.get_src_node(arc)] << " "
          << node_ids[net.get_tgt_node(arc)] << " "
          << static_cast<long long>(arc->cap) << "\n";
    }
}
 
template <class Net>
Net import_network_from_dimacs(const std::string& filename)
{
  using Node = typename Net::Node;
  using Flow_Type = typename Net::Flow_Type;
 
  Net net;
  std::ifstream in(filename);
  if (not in)
    throw std::runtime_error("Cannot open file: " + filename);
 
  std::vector<Node*> nodes;
  size_t source_id = 0, sink_id = 0;
 
  std::string line;
  while (std::getline(in, line))
    {
      if (line.empty() or line[0] == 'c')
        continue;
 
      std::istringstream iss(line);
      char type;
      iss >> type;
 
      if (type == 'p')
        {
          std::string problem;
          size_t n, m;
          iss >> problem >> n >> m;
 
          nodes.resize(n + 1);  // 1-indexed
          for (size_t i = 1; i <= n; ++i)
            nodes[i] = net.insert_node();
        }
      else if (type == 'n')
        {
          size_t id;
          char st;
          iss >> id >> st;
 
          if (st == 's')
            source_id = id;
          else if (st == 't')
            sink_id = id;
        }
      else if (type == 'a')
        {
          size_t src, tgt;
          long long cap;
          iss >> src >> tgt >> cap;
 
          net.insert_arc(nodes[src], nodes[tgt],
                         static_cast<Flow_Type>(cap));
        }
    }
 
  // Source and sink nodes are determined by topology in Net_Graph
  // The DIMACS format's source/sink designations guide network construction
  (void)source_id;  // Suppress unused variable warning
  (void)sink_id;
 
  return net;
}
 
 
//==============================================================================
// BENCHMARKING UTILITIES
//==============================================================================
 
template <typename Flow_Type>
struct MaxFlowBenchmarkResult
{
  Flow_Type flow_value{0};
  double elapsed_ms{0};
  std::string algorithm_name;
};
 
template <class Net, class Algo>
MaxFlowBenchmarkResult<typename Net::Flow_Type>
benchmark_maxflow(Net& net, Algo algo, const std::string& name)
{
  MaxFlowBenchmarkResult<typename Net::Flow_Type> result;
  result.algorithm_name = name;
 
  auto start = std::chrono::high_resolution_clock::now();
  result.flow_value = algo(net);
  auto end = std::chrono::high_resolution_clock::now();
 
  result.elapsed_ms = std::chrono::duration<double, std::milli>(
      end - start).count();
 
  return result;
}
 
template <typename Flow_Type>
void print_benchmark_results(
    const std::vector<MaxFlowBenchmarkResult<Flow_Type>>& results)
{
  std::cout << "\n=== Max-Flow Algorithm Benchmark ===\n";
  std::cout << std::left << std::setw(25) << "Algorithm"
            << std::setw(15) << "Flow"
            << std::setw(15) << "Time (ms)" << "\n";
  std::cout << std::string(55, '-') << "\n";
 
  for (const auto& r : results)
    std::cout << std::left << std::setw(25) << r.algorithm_name
              << std::setw(15) << r.flow_value
              << std::setw(15) << std::fixed << std::setprecision(3)
              << r.elapsed_ms << "\n";
}
 
} // namespace Aleph
 
#endif // NET_UTILS_H