Categories
Idea

Bimodal mobile markdown editors

Mobile text editors (like the WordPress one I am writing this on) tend to be drastically less convenient than their desktop-based equivalents. I am wondering whether this is could be improved if they supported two modes: one input mode in which you would write text without any formatting (possibly with macros for stuff like brackets) and a vim-like visual mode.

In the visual mode one would have a toolbar on the bottom of the screen. You could either select blocks of text and then the toolbar would show formatting for them (turn into code block, make every newline a list item..) or you could select words by tapping on them. Then the toolbar would show word formatting (bold, italic, in-line code) and one could drag and drop words around.

I feel like this would be quite an improvement over what I have seen in editors so far. I should probably extend the open source WordPress app and see where it leads me, but I don’t know java apps too well, so I might be doing a prototype in Reflex.

Categories
Idea

Generate flashcards from an API

I feel like I am spending inordinate amounts of time looking up functions I should absolutely have memorized by now. To the point where it might be more efficient to just generate flashcards (or even better: something like Lingvist or Duolingo) for APIs.

Such an app would consist of two parts: First scraping through docs. And then generating interesting memory retrieval tasks from it. For Haskell that could involve guessing the order of arguments to functions, matching name to type signature, guessing type class constraints, matching one-line haddock comment to name (and reverse).

This might be monetized by offering to support company-internal APIs for faster onboarding. Not sure, how useful this would be though. Might help a bit, but probably the real cost is understanding the architecture.

I am kinda planning on implementing this sometime next year (Backend: ASP.NET core/Giraffe, Frontend: Flutter). If you would like to join in, drop me a message!

Categories
Idea

Store ideas for more interesting conversations

Many conversations follow very predictable patterns. “Hey, how are you?” “Fine, you?”, even when we have so many interesting things happening to us. But when we are stressed or spend the last few hours thinking about some homology group, we might not remember them. So, why not store them in an app?

At the moment I am storing them in Google Notes, but this is unsatisfactory for a few reasons:

  • Clutter: I have way too much in Google Notes already
  • Hard to lookup based on topics. I currently save notes with the name of the person as title, but I would like to keep a story for people interested in coding, feminism, that latest techno artist and then have it appear for every person I tagged with this previously.

Maybe this could even be a business. One could for example scrap the Instagram timelines of people for interests. Then strangers would just need to exchange their Instagram names and would get a ton of shared interests to talk about. Or one turns this into a more personal CRM for businesses.

I don’t have time to do it right now, but write me if you like this idea too (no strings attached). My email is (* github user name *)@posteo.de

Categories
General

Tracking club attendance in Flutter

My debating society always has lots of new people, but then exam time rolls around and afterwards they don’t come back. So we wanted to track who had a real interest in debating to make sure we could keep these active.

The solution: A custom app in which we can add events, add people to events and sync this with Mailchimp. The app can then sort people into categories (came a few times but not in the last month, etc.) and add these as a target audience in Mailchimp so we can send a personalized campaign to them.

I decided to write this in Flutter, a framework from Google that promises near-native iOS and Android Apps. If you have ever developed a webapp with React or Angular, Flutter will feel instantly familiar.

First, I needed a model of the Mailchimp member API. It is a REST API, but since dart:mirrors doesn’t work in Flutter we can’t just derive classes from the JSON. Instead I generated it with a custom fork of Json to dart.

Building the App itself was fairly straightforward. While some things took longer than I would have hoped, I never encountered a point where something I wanted to do was impossible or different from how I expected it to work.

Categories
Tutorial

A Spreadsheet in Reflex

I recently came across a list of challenging projects. Most seemed like something I had already done; but the spreadsheet caught my eye. Since I wanted to learn more about Reflex anyway, why not do it in Reflex?

First: the model as a DAG

If you don’t care about the model you can jump right to the next section. Here’s an overview over the API we will build in this section:

data Coord -- the coordinates of a cell
data Expr -- an expression in a cell
parseExpr :: String -> Maybe Expr
data Sheet -- a spreadsheet as a directed acyclic graph
data EvalError = CyclicDependencies [Coord]
emptySheet :: Sheet
update :: Coord -> Expr -> Sheet -> Either EvalError Sheet
lookupCoord :: Coord -> Sheet -> Maybe Int

Lets start by building a language for expressions:

data Coord = Coord String Int
  deriving (Eq, Ord)

instance Show Coord where
  show (Coord s i) = map toUpper s ++ show i

instance Read Coord where
  readPrec = parens $ prec 10 $ do
    s <- lift $ munch1 isUpper
    n <- lift $ readDecP
    pure $ Coord s n

data Expr
  = IntVal Int
  | Add Expr Expr
  | Times Expr Expr
  | Dependency Coord
  deriving (Eq, Ord)

instance Show Expr where
  show (IntVal i) = show i
  show (Add e1 e2) = show e1 ++ "+" ++ show e2
  show (Times e1 e2) = show e1 ++ "*" ++ show e2
  show (Dependency d) = show d

instance Read Expr where
  readPrec = parens $
    (prec 10 $ IntVal <$> lift readDecP)
    +++ (prec 10 $ Dependency <$> readPrec)
    +++ (prec 5 $ do
      e1 <- step readPrec
      Symbol "+" <- lexP
      e2 <- readPrec
      pure $ Add e1 e2)
    +++ (prec 6 $ do
      e1 <- step readPrec
      Symbol "*" <- lexP
      e2 <- readPrec
      pure $ Times e1 e2)

parseExpr :: String -> Maybe Expr
parseExpr = go . filter (/=' ')
  where
    go "" = Just $ IntVal 0
    go s  = readMaybe s

The Read and Show instances allow us to parse and display expressions. We also accept the empty string, since Nothing stands for a parse failure here and an empty cell should have value 0.

Lets build a model for our spreadsheet next! Since cells may depend on each other we need to build a directed acyclic graph of dependencies.

newtype Sheet = Sheet { unSheet :: Map Coord Cell }
  deriving (Eq, Ord, Show)

data Cell = Cell
  { cellDeps :: Set Coord -- ^ cells that this depends on
  , cellFounds :: Set Coord -- ^ cells that depend on this
  , cellExpr :: Expr
  , cellValue :: Int
  }  deriving (Eq, Ord, Show)

data EvalError 
  = CyclicDependencies [Coord]
  deriving (Eq, Ord, Show)

We can connect this to our expressions:

evaluate :: Expr -> Sheet -> Int
evaluate e (Sheet m) = go e
  where
    go (IntVal i) = i
    go (Dependency d) = case Map.lookup d m of
      Nothing -> 0
      Just c -> cellValue c
    go (Add e1 e2) = go e1 + go e2
    go (Times e1 e2) = go e1 * go e2

dependencies :: Expr -> Set Coord
dependencies = go mempty
  where
    go acc (IntVal _) = acc
    go acc (Add e1 e2) = go (go acc e1) e2
    go acc (Times e1 e2) = go (go acc e1) e2
    go acc (Dependency d) = Set.insert d acc

We will start with an empty map as our sheet and add new cells as they are being written or referenced. We can handle input by calling the update function:

nullCell :: Cell
nullCell = Cell mempty mempty (IntVal 0) 0

addDependency :: Coord -> Coord -> Sheet -> Sheet
addDependency parent child (Sheet m) =
  let c = Map.findWithDefault nullCell child m 
  in Sheet $ Map.insert child 
       (c { cellFounds = Set.insert parent $ cellFounds c }) m

update :: Coord -> Expr -> Sheet -> Either EvalError Sheet
update p e (Sheet m) = case Map.lookup p m of
  Just c -> recompute p $ go (cellFounds c) -- see below for recompute
  Nothing -> Right (go mempty)
  where
    value = evaluate e (Sheet m)
    newDeps = dependencies e
    newCell founds = Cell newDeps founds e value
    go founds = Sheet $ Map.insert p (newCell founds) $ unSheet $
      foldl' (\m d -> addDependency p d m) (Sheet m) newDeps

When a cell changed we need to recompute all cells that depend on this cell recursively. If we encounter our original cell in the process we have a cycle and report it. We will assume though that every cycle in our graph must involve p, e.g. that the graph was acyclic before we updated p.

data RecomputeState = RecomputeState
  { currentPath :: [Coord]
  , uptodate :: Set Coord
  , todos :: Set Coord
  , currentSheet :: Sheet
  } deriving (Eq, Ord, Show)

-- | Compute all cells that depend on p.
recompute :: Coord -> Sheet -> Either EvalError Sheet
recompute p sheet = fmap (currentSheet . snd) $ runExcept
  $ runStateT (mapM_ go (cellFounds pCell)) 
              (RecomputeState [] mempty (cellFounds pCell) sheet)
  where
    pCell = fromMaybe nullCell $ Map.lookup p $ unSheet sheet
    go q = do
      s <- get
      when (q == p) $ 
        throwError $ CyclicDependencies $ (q:) $ currentPath s
      when (q `Set.member` uptodate s) $ pure ()
      let nCell = fromMaybe nullCell $ Map.lookup q 
                $ unSheet $ currentSheet s
      mapM_ go $ Set.toList $ Set.intersection (cellDeps nCell) (todos s)
      s <- get
      let v = evaluate (cellExpr nCell) (currentSheet s)
      put $ s
        { todos = (cellFounds nCell) <> Set.delete q (todos s)
        , currentPath = q : currentPath s
        , currentSheet = Sheet $ Map.insert q (nCell {cellValue = v}) 
                       $ unSheet $ currentSheet s
        , uptodate = Set.insert q (uptodate s)
        }
      mapM_ go (cellFounds nCell)
      s <- get
      put $ s { currentPath = tail $ currentPath s }

Adding a Reflex UI

The most basic component in our spreadsheet is going to be a single cell. It shows the value of the corresponding cell in the spreadsheet when not focused and the corresponding expression when focused. Furthermore we want the cell to have an hasError attribute when an error occurred.

cell :: (DomBuilder t m, MonadFix m, MonadHold t m)
     => Coord -> Dynamic t Bool -> Dynamic t Sheet -> m (Event t Expr)
cell coord errored sheet = mdo
  expr <- holdDyn "" $ gate (current $ _inputElement_hasFocus input)
    $ _inputElement_input input
  let value = (maybe "" (T.pack . show) . lookupCoord coord) <$> sheet
  let view = _inputElement_hasFocus input >>= \b ->
        if b then expr else value
  let cur = (parseExpr . T.unpack) <$> expr
  let err = (&&) <$> (not <$> _inputElement_hasFocus input) 
                 <*> ((||) <$> errored <*> (isNothing <$> cur))
  input <- inputElement
    $ modifyAttributes .~
      ((\b -> "hasError" =: if b then Just "" else Nothing) <$> updated err)
    $ def & inputElementConfig_setValue .~ updated view
  pure $ fmapMaybe id $ updated cur

It is remarkable how readable the code is once you get used to it. value is always the value of the cell in the sheet, expr is the content of the input field when it has focus. We set the value of the input field to view. If the field doesn’t have focus and we either couldn’t parse the expression or get an error signal from outside, the field gets the attribute hasError.

A grid is just a collection of cells plus some extra state:

grid :: (DomBuilder t m, MonadFix m, MonadHold t m) 
     => m (Dynamic t Sheet)
grid = mdo
  sheet <- holdDyn emptySheet (fmapMaybe (either (const Nothing) Just) 
    $ attachWith (flip ($)) (current sheet) changes)
  cycle <- holdDyn [] -- a possible cycle in the definitions
    $ fmapMaybe (either (\(CyclicDependencies d) -> Just d) (\_ -> Just []))
    $ attachWith (flip ($)) (current sheet) changes
  el "tr" $ sequence_ $ (el "th" (text "")) :
    [ el "th" (text (T.pack (a:[]))) | a <- ['A'..'B']]
  cs <- concat <$> sequenceA
    [ el "tr" $ sequenceA $ (el "td" (text (T.pack (show n)) >> pure never))
    : [ el "td" $ fmap (c, ) <$> cell c ((c `elem`) <$> cycle) sheet
      | a <- ['A'..'B'], let c = read (a:(show n))]
    | n <- [1..4]]
  let changes = mergeWith (\f g s -> f s >>= g)
        $ map (fmap (\(p,e) -> update p e)) cs
  pure sheet

We pass an error code to the cell if it is part of a cycle. We make sure to arrange the cells in a table with headers.

Finally, we just plug the grid into our site and we are done!

frontend :: Frontend (R FrontendRoute)
frontend = Frontend
  { _frontend_head = do 
      el "title" $ text "Literally Excel!"
      el "style" $ text "input[hasError] { border: 3px solid red; } "
  , _frontend_body = do
      _ <- grid
      return ()
  }

Conclusion

I am still unsure, whether I would build a bigger project with Reflex. On the one hand, the cell widget above would have been a lot harder to build in any other language and I am impressed by the ease with which it is possible to pass state around. But there are some pain-points:

  • The documentation isn’t that good. When I first looked at InputElement I thought that _inputElement_input referred to the input as typed by the user with one event for every character. Then I thought that _inputElement_input == updated _inputElement_value. Both are wrong and I am still not sure what _inputElement_value does.
  • My current solution is unbearably slow on normal-sized spreadsheets (26*100 cells). It seems like reflex is adding all the input elements to the dom and then needs a few seconds to place them at the right location and add the event handlers.

Still, it feels like reflex is getting more usable: Thanks to Obelisk installing it is now a breeze and there are enough tutorials to get started. If you are interested in FRP you should give Reflex a try!

Categories
Code Dump

Putting operators between numbers

You might have heard of this riddle: Given the numbers 1,5,6,7 permute them and put operators between them so that the solution is 21. Let’s find a solution with Haskell:

module Main where

import Data.List

data Action = Join | Add | Sub | Times | Div
  deriving (Eq, Show)

nums = permutations [1,5,6,7]
compOps = let as = [Join, Add, Sub, Times, Div] in [[a,b,c] | a <- as, b <- as, c <- as]
permOps = nub $ concatMap permutations compOps

eval :: Action -> Double -> Double -> Double
eval Join a b = a * 10^^(floor (logBase 10 b) + 1) + b
eval Add a b = a + b
eval Sub a b = a - b
eval Times a b = a * b
eval Div a b = a / b

brackets [a,b,c,d] [p,q,r] =
  [ check [p]   $ eval p (eval q a b)  (eval r c d)
  , check [p,q] $ eval p a (eval q (eval r b c) d)
  , check [p,q] $ eval p a (eval q b (eval r c d))
  , check [p,q] $ eval p (eval q (eval r a b) c) d
  , check [p,q] $ eval p (eval q a (eval r b c)) d
  ]
  where check xs a = if all (/=Join) xs then a else 0

main = print $ filter (any (==21) . snd) $ [((n, o), brackets n o) | n <- nums, o <- permOps]

And this yields:

>> main
[(([6.0,1.0,5.0,7.0],[Div,Sub,Div]),[7.0,-0.8823529411764706,21.0,0.14285714285714285,0.8285714285714285])]
>> 6.0 / 1.0 - 5.0 / 7.0
5.285714285714286
>> (6.0 / 1.0 - 5.0) / 7.0
0.14285714285714285
>> 6.0 / (1.0 - 5.0 / 7.0)
21.0
Categories
Code Dump

Successive shortest paths in C++

This solves the assignment problem by solving the associated minimum cost flow using the successive shortest paths method.

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <limits>

using std::vector;

using node = int;
using edge = int;
using capacity = int;
using flow = int;
using cost = int;

struct Edge {
  node from;   // from < 2^31
  node to;     // to   < 2^31
  cost c;      // cost < 2^31
  capacity u;  // capacity < 2^31 
  flow f;      // flow <= capacity
};

// In an EdgeCollection we store both edges and their inverses. 
// A edge is represented by an integer [0,edges.size) and its inverse edge 
// by the negative minus one [-edges.size, 0).
class EdgeCollection {
public:
  EdgeCollection(vector<Edge>& es): edges{es} {}

  edge inverse(edge e) {
    return -e-1;
  }
  node from(edge e) {
    return e >= 0 ? edges[e].from : edges[inverse(e)].to;
  }
  node to(edge e) {
    return e >= 0 ? edges[e].to : edges[inverse(e)].from;
  }
  cost get_cost(edge e) {
    return e >= 0 ? edges[e].c : - edges[inverse(e)].c;
  }
  capacity capacity_left(edge e) {
    return e >= 0 ? edges[e].u - edges[e].f : get_flow(inverse(e));
  }
  flow get_flow(edge e) {
    return e >= 0 ? edges[e].f : capacity_left(inverse(e));
  }
  void augment(edge e, flow f) {
    if(e >= 0) {
      edges[e].f += f;
    } else {
      edges[inverse(e)].f -= f;
    }
  }
  std::size_t size() {
    return edges.size();
  }
  vector<Edge>& get_edges() {
    return edges;
  }
private:
  vector<Edge> edges;
};

class AssignmentProblem {
public:
  AssignmentProblem(int num_nodes, vector<Edge>& edges)
    : ec(edges), pi(num_nodes + 2, 0), num_nodes{num_nodes}, s{num_nodes}, t{num_nodes + 1} {
    // Since all the edges go from A to B, 
    // we can calculate the initial potential pi in linear time:
    cost max = 0;
    for(size_t i = 0; i < edges.size(); ++i) {
      pi[edges[i].from] = - std::min( - pi[edges[i].from], edges[i].c);
      max = - std::min(edges[i].c, - max);
    }
    pi[s] = max;
    for(int i = 0; i < num_nodes/2; ++i) {
      edges.push_back(Edge {s,i,0,1,0});
    }
    for(int i = num_nodes/2; i < num_nodes; ++i) {
      edges.push_back(Edge {i,t,0,1,0});
    }
    ec = EdgeCollection(edges);
  }

  vector<Edge> succ_shortest_paths() {
    for(int b_of_s = num_nodes/2; b_of_s > 0; --b_of_s) {
      vector<int>  l(num_nodes + 2, std::numeric_limits<int>::max());
      vector<bool> r(num_nodes + 2, false);
      vector<edge> p(num_nodes + 2, -1);
      l[s] = 0;
      node next = s;
      vector<vector<size_t>> incident(num_nodes + 2);
      for(size_t i = 0; i < ec.size(); ++i) {
        if(ec.capacity_left(i) > 0) {
          incident[ec.from(i)].push_back(i);
        }
        if(ec.get_flow(i) > 0) {
          incident[ec.to(i)].push_back(ec.inverse(i));
        }
      }
      while(next != -1) { // Dijkstra
        r[next] = true;

        for(size_t i = 0; i < incident[next].size(); ++i) {
          edge e = incident[next][i]; node w = ec.to(e);
          cost c = l[next] + ec.get_cost(e) + pi[next] - pi[w];
          if(!r[w] and l[w] > c) {
            l[w] = c; p[w] = incident[next][i];
          }
        }

        next = -1; cost min = std::numeric_limits<int>::max();
        for(size_t i = 0; i < r.size(); ++i) {
          if(!r[i] and l[i] < min) {
            min = l[i];
            next = i;
          }
        }
      }

      node w = t;
      while(w != s) {
        edge way = p[w];
        ec.augment(way, 1); // In every iteration gamma will be 1.
        w = ec.from(way);
      }

      for(size_t i = 0; i < pi.size(); ++i) {
        pi[i] += l[i];
      }
    }
    return ec.get_edges();
  }
private:
  EdgeCollection ec;
  vector<int> pi;
  int num_nodes;
  node s, t;
};

void solve(int n, vector<Edge>& edges) {
  AssignmentProblem ap(n, edges);
  vector<Edge> f = ap.succ_shortest_paths();
  int total_cost = 0;
  for(size_t i = 0; i + n < f.size(); ++i) if(f[i].f == 1) total_cost += f[i].c;
  std::cout << total_cost << std::endl;
  for(size_t i = 0; i + n < f.size(); ++i) {
    Edge e = f[i];
    if(e.f == 1) {
      std::cout << e.from << " " << e.to << std::endl;
    }
  }
}

int main(int argc, char *argv[]) {
  if(argc != 2) {
    // We expect exactly one argument...
    std::cout << "Aufruf: " << argv[0] << " <filename>" << std::endl;
  } else {
    // which should be a filename...
    std::ifstream file(argv[1]);
    unsigned int n = 0;
    vector<Edge> edges(0);
    if(!file.is_open()) {
      // of a non-busy file.
      std::cout << "Konnte Datei nicht öffnen." << std::endl;
    } else {
      file >> n; // First we read the number of nodes...
      node a, b; cost c;
      while(file >> a >> b >> c) {
        // and then the edges...
        edges.push_back(Edge {a,b,c,1,0});
      }
      solve(n, edges);
    } 
  }
}
Categories
Code Dump

Push-relabel in C++

In a course on discrete maths I took in my second year, we had to implement the push-relabel algorithm in C++. This is a modified solution that has a worse theoretical, but better practical running time.

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <map>

using std::vector;
using node = int;
using edge = int;
using capacity = int;
using flow = int;

struct Edge {
  node from;   // from < 2^31
  node to;     // to   < 2^31
  capacity u;  // capacity < 2^31 
  flow f;      // flow <= capacity
};

// In an EdgeCollection we store both edges and their inverses. 
// A edge is represented by an integer [0,edges.size) and its inverse edge 
// by the negative minus one [-edges.size, 0).
class EdgeCollection {
public:
  EdgeCollection(vector<Edge>& es): edges{es} {}
  edge inverse(edge e) {
    return -e-1;
  }
  node from(edge e) {
    return e >= 0 ? edges[e].from : edges[inverse(e)].to;
  }
  node to(edge e) {
    return e >= 0 ? edges[e].to : edges[inverse(e)].from;
  }
  node capacity_left(edge e) {
    return e >= 0 ? edges[e].u - edges[e].f : get_flow(inverse(e));
  }
  flow get_flow(edge e) {
    return e >= 0 ? edges[e].f : capacity_left(inverse(e));
  }
  void augment(edge e, flow f) {
    if(e >= 0)    edges[e].f += f;
    else edges[inverse(e)].f -= f;
  }
  std::size_t size() {
    return edges.size();
  }
private:
  vector<Edge> edges;
};

// GoldbergTarjan contains the main push_relabel algorithm.
// We maintain the following invariants:
//  - incident[v] contains a list of edges starting in v,
//    inverse or otherwise, without duplicates.
//  - ex[v] stores the excess at v.
//  - phi[v] stores the distance phi(v).
//  - L[i] stores the active nodes v with phi[v] == i
//    without duplicates.
//  - A[v] stores a vector of allowed edges starting in v,
//    inverse or otherwise, without duplicates.
//    We may keep edges that were allowed once but aren't anymore.
class GoldbergTarjan {
public:
    GoldbergTarjan(int num_nodes, EdgeCollection ec, node source, node t_node)
      :phi(num_nodes,0), s{source}, t{t_node}, incoming(num_nodes), 
      outgoing(num_nodes), A(num_nodes), edges{ec}, ex(num_nodes, 0) {
      for(std::size_t i = 0; i < edges.size(); ++i) {
        if(edges.from(i) == s) {
          edges.augment(i, edges.capacity_left(i));
          if(edges.to(i) != t and edges.get_flow(i) > 0) 
            L.insert({0, edges.to(i)});
          ex[edges.to(i)] += edges.get_flow(i);
          ex[s] -= edges.get_flow(i);
        }
        outgoing[edges.from(i)].push_back(i);
        incoming[edges.to(i)].push_back(edges.inverse(i));
      }
      phi[s] = num_nodes; // phi[v] == 0 else (see initialization)
    }

    EdgeCollection push_relabel() {
      node v = get_maximum_active_node();
      bool still_active = false;
      while(v != -1) {
        if(A[v].size() != 0) {
          still_active = push(A[v].back());
        } else {
          relabel(v);
          // v is active and since it was the maximum active node before
          // it will be now (phi[v] never decreases).
          still_active = true;
        }
        v = still_active ? v : get_maximum_active_node();
      }
      return edges;
    }

    flow value() {
      return -ex[s];
    }
private:
    vector<unsigned> phi;
    node s,t;
    vector<vector<edge>> incoming;
    vector<vector<edge>> outgoing;
    std::multimap<int, node> L;
    vector<vector<edge>> A;
    EdgeCollection edges;
    vector<int> ex;

    bool push(edge e) { // returns true iff ex[v] remains > 0
      node v = edges.from(e); 
      node w = edges.to(e);
      if(phi[v] != phi[w] + 1) {
        A[v].pop_back(); // We remove not-any-more-allowed edges
        return true;
      }
      bool still_active = true;
      flow gamma = std::min(ex[v], edges.capacity_left(e));
      edges.augment(e, gamma);
      ex[v] -= gamma;
      ex[w] += gamma;
      if(ex[v] == 0) {
        L.erase(--L.end());
        still_active = false;
      }
      if(edges.capacity_left(e) == 0)          A[v].pop_back();
      if(ex[w] == gamma and w != s and w != t) L.insert({phi[w], w});
      return still_active;
    }

    void relabel(node v) {
      unsigned m = 2*phi.size();
      L.erase(--L.end());
      // Splitting outgoing and incoming is better for branch-prediction.
      std::vector<vector<edge>*> incident({&(outgoing[v]), &(incoming[v])});
      for(auto* vec : incident)
        for(auto e : *vec)
          if(edges.capacity_left(e) > 0)
            m = std::min(m, phi[edges.to(e)] + 1);
      phi[v] = m;
      L.insert({phi[v],v});
      for(auto* vec : incident)
        for(auto e : *vec)
          if(phi[v] == phi[edges.to(e)] + 1 and edges.capacity_left(e) > 0)
            A[v].push_back(e);
    }
    node get_maximum_active_node() {
      if(L.size() != 0) return L.rbegin()->second;
      return -1;
    }
};

int main(int argc, char *argv[]) {
  if(argc != 2) {
    // We expect exactly one argument...
    std::cout << "Aufruf: " << argv[0] << " <filename>" << std::endl;
  } else {
    // which should be a filename...
    std::ifstream file(argv[1]);
    unsigned int n = 0;
    vector<Edge> edges(0);
    if(!file.is_open()) {
      // of a non-busy file.
      std::cout << "Konnte Datei nicht öffnen." << std::endl;
    } else {
      file >> n; // First we read the number of nodes...
      node a, b; capacity c;
      while(file >> a >> b >> c) {
        // and then the edges...
        edges.push_back(Edge {a,b,c});
      }
    } 
    GoldbergTarjan gt(n, EdgeCollection(edges), 0, 1);
    EdgeCollection result = gt.push_relabel();
    std::cout << gt.value() << std::endl;
    for(std::size_t i = 0; i < result.size(); ++i) {
      if(result.get_flow(i) > 0) {
        std::cout << i << " " << result.get_flow(i) << std::endl;
      }
    }
  }
}
Categories
Code Dump

Kruskals algorithm in C++

This is a faster version of the standard algorithm for finding a minimum spanning tree using a Union-Find datastructure.

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using std::vector;

// A Branching object is a Union-Find-Structure with elements
// of type Branching::node (unsigned int).
// Union and Find are as in the lecture, but there is no MakeSet
// method as we know in advance how many elements we will need.
class Branching {
  public:
    using node = unsigned int;
    // Create a Branching of size n.
    Branching(unsigned int n) {
      size = n;
      rank = vector<node>(n,0); // Initially ranks are 0
      parent = vector<node>(n,0);
      for(node i = 0; i < n; ++i) {
        parent[i] = i; // Initially each element is its own parent.
      }
    }

    // Find with path-compression
    node Find(node x) {
      if(x != parent[x]) {
        parent[x] = Find(parent[x]);
      }
      return parent[x];
    }

    // Union as in lecture
    void Union(node x, node y) {
      node x_bar = Find(x);
      node y_bar = Find(y);
      if(rank[x_bar] > rank[y_bar]) {
        parent[y_bar] = x_bar;
      } else {
        parent[x_bar] = y_bar;
        if(rank[x_bar] == rank[y_bar]) {
          ++rank[y_bar];
        }
      }
    }
  private:
    unsigned int size;
    vector<node> parent;
    vector<node> rank;
};

struct edge {
  Branching::node from; // from < 2^32
  Branching::node to;   // to   < 2^32
  long long cost;       // abs(cost) < 2^32
};

// Kruskals algorithm
vector<edge> kruskal(unsigned int n, vector<edge>& edges) {
  // Lambda functions were introduced in C++11,
  // enable -std=c++11 if this fails to compile.
  std::sort(edges.begin(), edges.end(), [](edge e1, edge e2) {
    return e1.cost < e2.cost;
  });
  Branching nodes(n);
  vector<edge> mst(0);
  for(auto e : edges) {
    // We identify connected components in mst with components
    // in the Branching structure.
    // If the edge connects two disjoint components...
    if(nodes.Find(e.from) != nodes.Find(e.to)) {
      // add the edge to mst and union them in nodes.
      nodes.Union(e.from, e.to);
      mst.push_back(e);
    }
  }
  return mst;
}

// Output the result of Kruskals algorithm.
void output(unsigned int n, vector<edge> mst) {
  if(mst.size() != n - 1) {
    // A minimum spanning tree has exactly n-1 edges
    // if mst has less, the graph can't be connected.
    std::cout << "Der Graph ist nicht zusammenhängend!" << std::endl;
  } else {
    long long sum = 0;
    for(auto e : mst) {
      sum += e.cost; // Sum the costs.
    }
    std::cout << "Es gibt einen MST mit Gewicht " << sum << "." << std::endl;
    for(auto e : mst) {
      // Give back each edge in the order in which they were added to mst.
      std::cout << e.from << " -> " << e.to << " : "  << e.cost << std::endl;
    }
  }
}

int main(int argc, char *argv[]) {
  if(argc != 2) {
    // We expect exactly one argument...
    std::cout << "Aufruf: " << argv[0] << " <filename>" << std::endl;
  } else {
    // which should be a filename...
    std::ifstream file(argv[1]);
    unsigned int n = 0;
    vector<edge> edges(0);
    if(!file.is_open()) {
      // of a non-busy file.
      std::cout << "Konnte Datei nicht öffnen." << std::endl;
    } else {
      file >> n; // First we read the number of nodes...
      Branching::node a, b; long long c;
      while(file >> a >> b >> c) {
        // and then the edges...
        edges.push_back(edge {a,b,c});
      }
      // and then we compute the MST.
      output(n, kruskal(n, edges));
    }
  }
}