Skip to content

Graph Based Routing Find out more about the core concepts behind Superscribe

What is Graph Based Routing?

Graph based routing is a Url parsing and matching strategy most commonly used as part of a Web Applications. Instead of a routing table containing string definitions, route definitions are stored in a graph structure as complex objects. This allows for us to attach methods and functions to our definitions for use during the matching process, and to execute code when a route segment is matched succesfully. This ability to execute arbritary code is known as the Routing Pipeline

For example, consider the following routes and below, their graph representation:

  • /api/products/{id}
  • /api/products/bestsellers
  • /api/customers/{id}

The advantages of Graph based routing can be summarised as follows:

  • Efficiency - Matches for the next segment are only ever considered from the edges of the current node
  • Composibility - Nodes can be assigned to variables, passed around and reused in multiple definitions
  • Extensibility - Free to create new types of node with any desired behavior
Don't be fooled by the diagram of a Tree... a Tree is just a type of graph where not all nodes are connect by edges.

The three types of Function

Flow through the routing pipeline is controlled by three methods that can be assigned to nodes. These can contain any code at all so long as they conform to the required interface, and are known as the Graph Based Routing Functions. Between them, these Functions allow the routing pipeline to take actions, determine whether or not a node is a match for the current segment, and set values that a framework or handler can use to repsond to the http request once matching has finished.

Data can be passed between nodes using an object called the RouteData, which is passed as a parameter to each function, along with the current segment. This Data is a read-write dictionary or property bag that can store any information required. The following Functions are available:

  • Activation Function - Returns a boolean true or false indicating if this node is a match for the current segment
  • Action Function - Executes some code upon a succesful match, such as parameter capture
  • Final Function - Run when route matching finishes at a given node.

Final Functions are only executed once matching has finished succesfully. If routing finishes on a node that does not define one then no final function is executed, and a flag is set on the route data accordingly (see match result flags below).

The Matching Process

Graph Nodes, their constraints, and Functions form a simple state machine, which can then be used to perform the matching process as seen in this example from Asp.Net Web API:

  • Default Web API routing case:


In addition to the behaviors emergent from the presence of the three Functions, Final Functions can also have allowed methods. A final function with an allowed method will only be executed if this matched the incoming Http Method of the request.

Parameters and the Querystring

In Graph Based Routing, parameter capture is the responsibility of Action Functions defined against nodes that represent values. They are then added them to the Parameters Dictionary which sits on the RouteData object so they become available to subsequent nodes and Final Functions. No provision is made in the implementation itself to capture parameters at this time, with the exception of the Querystring.

Because Querystring parameters can come in any order, they cannot be treated as graph nodes for the purposes of matching. Any compatible Graph Based Routing implementation will decode and store all querystring parameters prior to matching the remainder of the URL. This means that all nodes have access to querystring values, and if matching based on these values is required this can be performed accordingly in the relevant Activation Function.

Match Result Flags

Graph Based Routing implementations must not respond to requests themselves, but can set a number of flags on the RouteData object to indicate certain scenarios. It is then up to the framework or code handling the request to deal with these flags as they see fit:

  • Extraneous Match - There are no more edges present in the current node, but we still have route segments remaining to match
  • Final Function Executed - All segments were consumed, and a final function was matched and executed
  • No Matching Final Function - Indicates that although all segments were consumed and the find node did provide one or more final functions - none of them matched the request method.

For further reading, please see the original Graph Based Routing blog post

Graph Based Routing Pseudocode

The following pseudocode represents a completely standards compliant graph based routing algortihm that can be used a base for any language specific implementations.

  queue RemainingSegments;

  FUNCTION WalkRoute (string route, string method, dictionary routedata)  
    SET routedata Url TO route parameter value
    SET routedata Method TO method parameter value

    FOR EACH querystring parameter IN route
      SET routedata.Parameters dictionary entry for [] TO parameter.value

    remove querystring from route
    SET RemainingSegments TO array of route split by '/'

    CALL WalkRouteLoop WITH routedata, basenode

  FUNCTION WalkRouteLoop (dictionary routedata, graphnode match)  
    finalfunction oncomplete;

    WHILE match IS NOT null    
      IF match has an Action Function THEN CALL Action Function WITH routedata, current segment
      IF there are remaining segments THEN DEQUEUE the current segment FROM RemainingSegments

      SET oncomplete TO null
      IF match has a final functions defined for the current method THEN
        SET oncomplete TO final function for this method

      SET nextmatch to result of CALL FindNextMatch WITH routedata, current segment, match.Edges
      IF nextmatch IS null
        AND current match has Final Functions but none match this method THEN
          SET NoMatchingFinalFunction flag to true
      END IF

      SET match TO nextmatch

    IF there are still remaining segments THEN SET ExtraneousMatch flag to true
    IF oncomplete IS set THEN
      CALL oncomplete WITH routedata
      SET FinalFunctionExecuted flag to true
    END IF

  FUNCTION FindNextMatch (routedata, string segment, list edges)    
    FOR EACH potential next match IN edges
      IF the potential match Activation Function returns true THEN
          SET match to potential match
          SET match to null
      END IF

    RETURN match