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:
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
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.
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 [parameter.name] TO parameter.value remove querystring from route SET RemainingSegments TO array of route split by '/' CALL WalkRouteLoop WITH routedata, basenode END FUNCTION 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 EXIT FUNCTION END IF SET match TO nextmatch END WHILE 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 END FUNCTION 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 ELSE SET match to null END IF END FOR RETURN match END FUNCTION