Differences between Additional Edges in a graph and a list of normalized paths

We have traditionally represented nodes and edges in a graph with vertices and adjacency matrix or list. We often use a graph to find shortest path between two vertices. Although we use well known graph algorithms to traverse the graph to find these paths dynamically, we could also capture and save this information with the graph itself. This is ideal when the graph does not have to be manipulated very often such as with addition or deletion of nodes and or edges. Data warehouses represented by graphs could benefit with additional representational aid because they don’t change very much

Some such aid to represent graphs in order to improve performance for traversal or to find paths between vertices include the following:

1)      Add additional edges to represent connectivity by skipping a number of nodes. There could be a set of edges colored differently for skipping say 2, 4, 8 … nodes in the graph.

2)      To have a normalized set of paths among all enumerable paths that could be iterated to construct path between two vertices.

The differences between these approaches are as follows:

The former is used this way: If we have a source and destination vertices, we change the source or destination to something closer between the two between which the destination is guaranteed to be present thus optimizing traversal between visiting each interim node one by one and skipping them. Additionally, we traverse the unknown segment from higher order edges to lower order edges where higher order are skip lists and lowest order is next vertex hop or single hop list.

The latter is used this way: If we have a source and destination vertices, we find all paths that contain source and destination and filter them progressively by replacing source and destination with interim nodes. The idea is that a set of normalized paths will be guaranteed to have interim nodes and also reduce the number of all possible paths that may be scanned otherwise.  By changing source or destination or both with as front most as possible or as end most as possible we can converge to a fully traversable path with fewer iterations. Each iteration skips a few nodes by knowing that there already exists a path to connect them.

The latter technique does not require touching the graph and the normalized list can be stored outside the graph. The former technique requires mode edges to be added to the same graph. Both techniques support algorithms to be modified to offload the shortest path discovery between two vertices with performance improvements.

#code question
Do linear deduplication between two integer arrays to merge them.

List<int> dedup( List <int> a, List <int> b)
{
a.sort ();
b.sort();
var ret = new List <int> ();
Int m = 0;
Int n = 0;
For (int I = 0; I < a.count + b.count;  I++)
{
int min = a[m];
If (a [m] == b [n])
{
M++;
n++;
}
If (a [m] < b [n])
{
M++;
}
Else
{
min = b[n];
N++;
}
if (ret.Count == 0 || ret.Last() != min)
     ret.Add(min);
}
Return ret;
}