Problem generator?

[chaoxu]

Consider the shortest path problem. There are many dimension to the problem

• is the graph directed or undirected?
• is the weights integer, real, or general?
• is the weight positive, or allow negative?
• do we put restrictions on the path? (even, odd, length at most k?)

This kind of things happens a lot, for example, there is even a notation for scheduling problems.

One might say for each individual combination, we should have a different problem. This is definitely possible. The generalization and special case already paint the relation between them. In fact, this is what I will do for now. However, it looks very repetitive. As the problem statements seem to be restated multiple times. One can inherit problem statements and apply how to derive the special case.

I mean, one can always separate the concern. store the graph somewhere else, not in problems. Hmm, it makes editing a little more difficult.

[chaoxu]

Indeed, this should not be a problem. We don't need a problem generator, what we need is basically inheritance. Just like in object-oriented programming.

Say two problem exactly the same, except one having input integer weights

id: 1
input: 
  G: a graph
  w: real weights

id: 2
input: 
  G: a graph
  w: integer weights

We will do inheritance, and we create an edge, between a problem and its special case. Having parents instead.

id: 2
parents: 
  - 1 : optional notes
input:
  w: integer weight function, overwritten the parent.

Each problem might have multiple parents, and we can think about how to handle that later.

[chaoxu]

I started a new branch to get the inheritance feature right.

Here is an example of only 4 problems. The point is to make sure we output the correct thing here.

id: min-cost-flow
title: min-cost flow
problem: Given a graph with edge capacity and cost, find the min-cost flow.
parameters:
  - name: n
    description: number of vertices
  - name: m
    description: number of edges
  - name: m'
    description: number of edges with finite capacity upper bound
algorithms:
  - description: Orlin's 1991
    problem: [shortest-path]
    complexity: $O((n+m') log n S(m,n))$ time. Here $S(m,n)$ is running time for shortest path algorithm. 
---
id: min-cost-flow-integer-capacity
inherit: [min-cost-flow]
title: min-cost flow (integer capacity)
parameters:
  - name: U
    description: upper bound on the absolute value of the capacity
algorithms:
  - description: Edmonds and Karp
    problem: [shortest-path]
    complexity :  $O((n+m') \log U (m+n log n))$
---
id: min-cost-flow-integer-cost
inherit: [min-cost-flow]
title: min-cost flow (integer cost)
parameters:
  - name: C
    description: upper bound on the absolute value of the cost
algorithms:
  - description: Goldberg and Tarjan 1987
    complexity: $O(nm \log (n^2/m) \log (nC))$
---
id: min-cost-flow-all-integers
inherit: [min-cost-flow-integer-cost, min-cost-flow-integer-capacity]
title: min-cost flow (integer cost and capacity)
algorithms:
  - description: Ahuja, Goldberg, Orlin and Tarjan 1998
    complexity: $O(nm \log \log U \log (nC))$