Data Structures and Algorithms
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSE 310 — Data Structures and Algorithms
HW 07 Graph Programming
There is no milestone for this project; the complete project is due Monday, 12/06/2021
This project involves algorithms on undirected graphs, represented using adjacency lists, to solve the in-band
network telemetry (INT) problem.
Note: This project must be completed individually, i.e., you must write all the code yourself.
Your implementation must use C/C++ and ultimately your code for solving the INT problem will be
evaluated for correctness using system which runs on a Linux system.
All dynamic memory allocation for the adjacency lists, and any other data structures used in this project,
must be done yourself, i.e., using either malloc() and free(), or new() and delete(). You may not use
any external libraries to implement any part of this project, aside from the standard libraries for I/O and
string functions (stdio.h, stdlib.h, string.h, and their equivalents in C++). If you are in doubt about
what libraries you may use, ask for permission.
By convention, your program should exit with a return value of zero to signal that all is well; various
non-zero values signal abnormal situations.
You must use a version control system as you develop your solution to this project and commit to it
frequently. Your code repository must be private to prevent anyone from plagiarizing your work. In this
project, your submission will require a snap shot of the commits you have made to demonstrate your work.
The rest of this project description is organized as follows. §1 the problem of in-band network telemetry
is described, along with an algorithm to find a single-path to solve it. The input format is described in §2,
while the output format is given in §3. In §4 you will find some requirements on the design of your solution
to this project. Finally, §5 provides submission instructions for this project.
1 The Problem of In-band Network Telemetry
In computer networks, in-band network telemetry (INT) seeks to achieve high-precision monitoring of the
network links (e.g., latency, packet drop rate, time-to-live, jitter, and bandwidth along a link) and also the
routers (e.g., queue-depth of interfaces in a router). In this project, we will model a computer network as a
connected undirected graph G = (V, E) with routers modelled as the vertices V ; there is an edge (u, v) ∈ E,
where u, v ∈ V and u 6= v, if there is a communication link between routers u and v.
In this project, we are interested solve the problem of in-band network telemetry by finding a single-
path that traverses each edge of the graph once, though it is allowed to visit each vertex more than once.
Unfortunately, a graph G has an Euler path if and only if it has at most two vertices of odd-degree. An
Euler circuit is a path that starts and ends at the same vertex. As we’ll see, in order to handle an arbitrary
connected graph we may need to traverse each edge more than once.
1.1 A Single-Path Solution to the Problem of In-band Network Telemetry
At a high level, the steps to find a single-path to solve the in-band telemetry problem are given in Algorithm
1. Let’s step through the algorithm for the graph corresponding to a campus network in Figure 1. In order
to guarantee the output is deterministic, lexicographic ordering is used in several steps. Be sure to pay
attention to the ordering requirements to ensure your output matches the sample output.
1
Algorithm 1 Single-Path-INT(G,n)
1: // Input: A connected undirected graph G with n vertices; all edge weights are equal to one.
2: // Output: A single-path for collecting in-band network telemetry.
3: Find all odd-degree vertices, O
4: Use Floyd-Warshall to find the length of the shortest-path in G between each pair of vertices in O
5: Find a perfect matching M in O using a greedy algorithm
6: for each edge (u, v) ∈M do
7: Insert a virtual edge (u, v) into G with weight equal to the shortest-path length
8: end for
9: Find an Euler circuit in G including any virtual edges inserted
1.1.1 Find Odd Degree Vertices
For the graph G in Figure 1, there are six vertices of odd degree, i.e., O = {3, 4, 5, 7, 14, 15}; these vertices
are coloured red in the figure.
Figure 1: A graph G corresponding to a cam-
pus network. It has six vertices of odd degree,
i.e., O = {3, 4, 5, 7, 14, 15} .
Table 1: Output of Floyd-Warshall All Pairs Shortest Paths on G.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 0 1 1 2 2 2 3 4 3 3 3 3 4 4 4
2 1 0 1 1 1 2 3 4 2 2 2 3 4 4 4
3 1 1 0 2 2 1 2 3 2 2 3 2 3 3 3
4 2 1 2 0 1 2 3 4 1 2 2 3 4 4 4
5 2 1 2 1 0 1 2 3 2 1 1 2 3 3 3
6 2 2 1 2 1 0 1 2 1 1 2 1 2 2 2
7 3 3 2 3 2 1 0 1 2 2 3 2 1 1 1
8 4 4 3 4 3 2 1 0 3 3 4 3 2 2 1
9 3 2 2 1 2 1 2 3 0 2 3 2 3 3 3
10 3 2 2 2 1 1 2 3 2 0 2 2 3 3 3
11 3 2 3 2 1 2 3 4 3 2 0 1 4 4 4
12 3 3 2 3 2 1 2 3 2 2 1 0 3 3 3
13 4 4 3 4 3 2 1 2 3 3 4 3 0 1 2
14 4 4 3 4 3 2 1 2 3 3 4 3 1 0 1
15 4 4 3 4 3 2 1 1 3 3 4 3 2 1 0
1.1.2 Use the Floyd-Warshall Algorithm
The Floyd-Warshall algorithm finds the length of the shortest-path between each pair of vertices in a graph;
these are tabulated for the graph G in Figure 1 in Table 1. However, we’re only interested in the subset of
odd-degree vertices of V , i.e., those in O; the shortest path between the vertices in O are indicated in boxes
in Table 1 and extracted and placed in a separate table, Table 2.
Figure 2: The fully connected graph on the
six vertices in O.
Table 2: Shortest path length in G between vertices in O.
3 4 5 7 14 15
3 0 2 2 2 3 3
4 2 0 1 3 4 4
5 2 1 0 2 1 1
7 2 3 2 0 1 1
14 3 4 3 1 0 1
15 3 4 3 1 1 0
1.1.3 Use a Greedy Algorithm to Find a Minimum Weight Perfect Matching
View the vertices in O as the vertices of a fully connected undirected weighted graph G′ as depicted in
Figure 2. The weights of the edges (u, v), where u, v ∈ O, correspond to the length of the shortest path
between u and v in G; see Table 2.
2
For an undirected graph, a matching is a set of edges such that no two edges in the set are incident on
the same vertex. A perfect matching is a matching in which every vertex is matched.
We will use a greedy approach to find a minimum weight perfect matching of the fully connected graph
on O. If p = |O|, is the number of vertices in the set O, then there are a total p×(p−1)2 edges in G′. First,
order the edges (u, v), by their weight which is equal to the length of the shortest path between them in G.
If there are ties, i.e., edges of the same weight, then sort the edges lexicographically. Given two edges (u, v)
and (w, x), if u < w then (u, v) < (w, x); if u = w then (u, v) < (w, x) if v < x.
Initialize the matching M = ∅. Now that the edges are sorted, step through the edges one-by-one in
order. If the edge e = (u, v) is not incident with any edge in M, then add e to the matching, i.e., M = M∪e.
Otherwise discard the edge e.