Search over Algebraic Graphs

As a reminder, alga defines an algebraic graph as something similar to following data type. This time, it has labeled (weighted) edges:

data Graph w v
  = Empty
  | Vertex v
  | Overlay (Graph w v) (Graph w v)
  | Connect w (Graph w v) (Graph w v)

The challenge we have is to conduct algorithms over the description of the graph, and not the graph itself; expanding the graph prior to a search would require materializing all edges, which is \(O(n^2)\), and we’d lose out on the benefits of many algorithms that are sub quadratic in the number of vertices.

Rather than rehash the basics, let’s focus on perhaps the most important constructor, Connect. For directed graphs, this operation describes a biclique, i.e. a complete directed bipartite subgraph when the vertices are disjoint, which is set of edges stemming from every vertex in the left child graph to every vertex in the right child graph. It can accomplish this using \(O (1)\) space for itself, and \(O(n)\) space for its children, i.e. not proportional to the number of edges, which is \(O(n^2)\). In other words, alga’s representation is a form of graph compression.

The field of graph compression is active and evolving. In Faster Graph Algorithms Through DAG Compression⁴, Max Bannach, Florian Andreas Marwitz, and Till Tantau (BMT) describe a set of algorithms over a data structure they dubbed a switching graph.

Before we introduce switching graphs, let’s introduce its building blocks. BMT define a cluster DAG \(C = (V', A)\) as a DAG whose sinks are exactly the set of vertices \(V\) in the graph \(G\) it describes. A vertex \(v' \in V'\) describes a so-called cluster \(C(v')\), which represents the subset of sinks that are reachable from that vertex. A cluster \(C(v)\) where \(v\in V\) is trivially the set \(\{v\}\). \(A\) represents the set of directed edges in the cluster DAG and are called cluster edges.

Building on top of cluster DAGs, a DAG compression is a graph \(D = (V', A, E')\) where \(V'\) and \(A\) are the same vertex and edge sets as in the cluster DAG \(C\). \(E' \subseteq V' \times V'\) is an additional edge relation. If \((u', v')\) is in \(E'\), then the set of edges \(C(u') \times C(v')\) is in \(G\). This is a complete bipartite graph with directed edges from all sinks (vertices in \(G\)) reachable from \(u'\) to all reachable from \(v'\).

This may seem slightly familiar. alga’s Connect w x y adds edges \(V(x) \times V(y)\) to the parent graph \(G'\), which is the cross product of all vertices in child graph x and all vertices in child graph y, unioned with the edges in x and y. Given that all trees are DAGs, if we consider the node for child graph x to be a cluster node \(x'\), and the node for child graph y to be a cluster node \(y'\), then we can see that the set of vertices in \(G\) described by \(V(x)\) equals the set of vertices described by \(C(x')\), and likewise for \(V(y)\) and \(C(y')\). The cross product \(V(x) \times V(y)\) therefore describes the same set of edges as \(C(x') \times C(y')\). To convert an alga expression into a DAG compression, we contribute each edge from an Overlay or Connect node to its child to \(A\), and we contribute an edge \((x', y')\) for each Connect w x' y', which represents \(C(x') \times C(y')\), to \(E'\).

One missing piece in reducing an alga expression to a DAG compression is that there is no limit to the number of leaf Vertex constructors that can denote the same logical vertex \(v\). In a cluster DAG, as mentioned earlier, the set of sinks is exactly \(V\). To fully reduce a tree compression to a DAG compression, all logically equivalent Vertex v constructors must be consolidated into one node. We can discard subexpressions that contain no vertices, such as Empty or Overlay Empty Empty, and not carry them to the DAG representation. Lastly, because alga expressions can outline multiedges due to duplicate node occurrences, we can handle those by taking the minimum weighted edge. This is okay for the purposes of SSSP because we will always take the edge that costs less for any shortest path.

The switching graph is an augmentation of the DAG compression that allows a search to traverse backwards through parent-child directed edges in order to establish reachability and distances between vertices in \(G\). To accomplish this, BMT duplicate all vertices \(V'\) except for the vertices representing \(V\). The original, copied vertex \(x'\in V'\setminus V\) is an upper vertex, a non-copied vertex \(v\in V\) is a middle vertex, and a copy \(\overline{x'}\) is a lower vertex. For all middle vertices, \(\bar v=v\). Edges \((\overline{y'}, \overline{x'})\) are added to the switching graph for every parent-child edge \((x', y') \in A\). Semantically, they represent climbing back up to ancestor cluster nodes. For every compressed edge \((x', y')\) in \(E'\), the compressed edge is removed and a switching edge is added in the switching graph from node \(\overline{x'}\) to node \(y'\). The source \(\overline{x'}\) can either be a lower node or a middle node, and the destination \(y'\) can either be a middle or upper node, depending on whether or not the endpoints belong to \(V\). Traversing those switching edges incurs a switching cost \(w\).

BMT prove that there is no loss of search or distance semantics when performing those algorithms over the switching graph compared to the original graph \(G\). They prove that these algorithms run over the switching graph, which is \(O(s)\), without needing to decompress the representation and generate the same SSSP as the search would on \(G\).

Consequently, we can perform a search over the alga expression without decompressing it into an adjacency map, as the alga library does today. However, in the spirit of performing as much of the algorithm on the Graph expression as possible, we will not be constructing a separate switching graph. Instead, we will perform the search over a lazily-generated frontier of search states and visit nodes of the expression.

To support this, we’re going to traverse the expression and create an index that caches some important information about the graph. Unlike an adjacency map, this construction will not be proportional to the number of edges in \(G\):

makeBaseFunctor [''Graph]

type Weight w = (Ord w, Num w)
type Vertex v = Ord v

type NodeId = Int

data Index w v = Index
  { parentOf      :: IntMap NodeId
  , occurrencesOf :: Map v [NodeId]
  , nodeFor       :: IntMap (GraphF w v NodeId)
  }

First, the obvious; the index stores the parent of every node other than the root. Every node in the graph expression will be assigned an integer NodeId. What’s not obvious are the purposes of occurrencesOf and nodeFor; because there are no restrictions on how many times a vertex \(v\) can appear as Vertex v in the graph, there may be more than one. So, we want to track which node ids those occurrences correspond to, which are inserted into occurrencesOf. For convenience, and for Connect and Overlay constructors, we’d like a way to quickly retrieve the node ids of their children; that is the purpose of nodeFor. This way, the node ids are available to us directly as we traverse the expression.

When reading the BMT paper, I thought that the terminology was a bit confusing. I’m used to looking at DAGs from sources at the top to sinks at the bottom. Same with trees. As mentioned earlier, in the BMT switching graph, copies of the parents that we move to are considered lower nodes. This is counterintuitive to me! So in the SearchState, Down will represent visiting a node’s child, Up will represent visiting its parent, and At v will represent visiting a Vertex v.

Our search will traverse the expression and, for each node in the expression, generate SearchState neighbors that indicate the next state. Let’s start with the simplest case to understand, moving down from a node:

-- given the index and a node id, move downward from the
-- corresponding node
descend :: Index w v -> NodeId -> [SearchState v]
descend index n =
  case nodeFor index IM.! n of
    EmptyF -> []
    VertexF v -> [At v]
    _ -> [Down n]

downNeighbors
  :: Weight w
  => Index w v -> NodeId -> [(w, SearchState v)]
downNeighbors index n =
  [ (0, s) -- descending to a node costs nothing
  | child <- toList (nodeFor index IM.! n)
  , s <- descend index child
  ]

descend gives us the downward state representation of a node n. If we’re at a Vertex v, then we’re At v. If we’re at a Connect or Overlay node, the corresponding search state is Down.

Given the index and a node id, downNeighbors converts the children of a node to a list and, for each child, converts that child to its search state form. Traveling to that child costs nothing because it does not represent traversing a real, weighted edge.

Finally, we want a special function for visiting neighbors from a Vertex in the expression tree, i.e. from the search state At. You may have thought to yourself that upNeighbors should cover this case. The reason we don’t use this directly is because, given that there can be more than one Vertex v in the expression tree, we need all possible upward neighbors from that search state:

atNeighbors
  :: (Weight w, Vertex v)
  => Index w v -> v -> [(w, SearchState v)]
atNeighbors index v =
  concatMap (upNeighbors index)
    (M.findWithDefault [] v (occurrencesOf index))

We can now define dijkstra using the familiar construction; we keep a distance map that doubles as the seen set, and a priority queue of (w, SearchState v) using Haskell’s Set, which gives us a convenient minView function.

dijkstra :: (Weight w, Vertex v)
  => Index w v -> v -> Map v w
dijkstra index start =
  go (Set.singleton (0, At start)) M.empty
  where
    go queue distances =
      case Set.minView queue of
        Nothing -> vertexDistances distances
        Just ((d, next), rest)
          | M.member next distances -> go rest distances
          | otherwise ->
              let relax (cost, neighbor) =
                    Set.insert (d + cost, neighbor)
                  newQueue =
                    foldr relax rest (neighbors index next)
                  newDistances = M.insert next d distances
               in go newQueue newDistances

    -- grab only distances from vertices in G,
    -- i.e. At search states
    vertexDistances distances =
      M.fromList [ (v, d) | (At v, d) <- M.toList distances ]

To refresh your memory of Dijkstra’s algorithm, we set up a queue prioritized by minimum distance to a particular node, pop that value and, if unvisited, get its neighbors and insert them into the queue. Something different about this implementation is that we do not gate insertion of neighbors into the priority queue based on whether or not we’ve already visited the search state; the neighbors are inserted into the queue regardless. What makes this okay is the line M.member next distances -> go rest distances, which gates at the pop step rather than at the push step. As a consequence, we pay a minor penalty of having the queue ignore values already seen.