Data Structures for Airline Information: Graph Implementation

This assignment solution explores the application of graph data structures for storing and managing airline flight information. The student chose to use graph data structures, specifically explaining the use of adjacency matrices and adjacency lists to represent cities and flights. The solution details how flight information, including starting city, destination, and flight ID, can be stored and retrieved using these structures. The assignment also covers operations within adjacency list matrices, such as printing all flight paths from a source to a destination using Depth First Traversal and counting the number of paths to a given destination. The solution also includes a discussion on semaphores and mutexes, explaining their functionality in the context of concurrency and system resource management, along with real-world applications of graphs. References are also provided.

Edward Aboagye
P16150395
Question 1
a) Graph Data Structure
For this question I will be using graph data structure. Data structures comprises of vertices and
edges. Edges connects vertices through lines. If two vertices are connected by an edge then it is
termed as adjacent matrix. In this case A and B are both connected to two certain edges, and
vertex D is not connected with any other vertex and F can also be connected to its own vertex.
Adjacency List: Every vertex on the diagram is recorded in an item as keys, these keys are
related to a sum of vertices, which sends information towards the connected edges that every
vertex has. This strategy is commonly known as putting away the rundown of edges. Along these
lines, extra data can be put away on the vertices and edges. A diagram may contain only one
edge between two hubs, or it may contain two: one from the first to the second, and one again
from the second to the first (with each edge related with its own worth). A coordinated diagram
is pitifully symmetric on the off chance that when there is an edge from node1 to node2, at that
point there additionally is an edge from node2 to node1; similarly, a coordinated chart is
emphatically symmetric on the off chance that when there is an edge from node1 to node2, at
that point there likewise is an edge from node2 to node1 with the related qualities for these edges
equivalent(Kabiljo, Dhulipala, Shalita, Sharma, Karrer, & Facebook Inc, 2017).

Edward Aboagye
P16150395
b) Storing of information in adjacency list matrix
Each row and column in the table below corresponds to vertex. Diagrams comprise of an
accumulation of hubs (otherwise known as vertices), each with a mark it is known by. Edges
(otherwise known as circular segments) happen between pair of hubs, and each edge can have a
related worth (used to encode an assortment of data: regularly a number, for the length of the
edge, the expense of the edge, and so forth). In a coordinated chart (otherwise known as digraph,
the thoughtful we will consider), edges have a recognizable source and goal hub; an edge is
composed as a bolt from its cause to its goal(Ainsworth, Jones, 2016, June).

Edward Aboagye
P16150395
For the table above, we have 6 different cities and 9 separate flights.
Here is another example of adjacency list matrix
The diagram above has 8 cities and 12 separate flights.

Edward Aboagye
P16150395
c) Operations in adjacency list matrix
(i) Printing all paths of the flight from source to a destination. The thought is to do Depth
First Traversal of given coordinated diagram. Begin the traversal from source. Continue putting
away the visited vertices in a cluster say 'path[]'. In the event that we arrive at the goal vertex,
print substance of path[]. The significant thing is to check current vertices in path[] as visited
likewise, with the goal that the traversal doesn't go in a cycle.
(ii) Counting of the number of paths to a given destination.
Approach
To discover every one of the ways which experience at any rate one stamped (cell containing -
1). On the off chance that we discover the ways that don't experience any of the stamped cells
and all the potential ways from (0, 0) to (n-1, m-1) at that point we can discover every one of the
ways that experience in any event one of the imprints cells.
Number of ways that go through in any event one stamped cell = (Total number of ways –
Number of ways that don't go through any checked cell)
We will utilize the methodology referenced in this article to locate the all out number of ways
that don't go through any checked cell and the absolute number of ways from source to goal will
be (m + n – 2)! /(n – 1)! * (m – 1)! where m and n are the quantity of lines and sections.
Question 2
a)
The semaphore is your guardian to anticipate the fifth individual to go into the room. How can it

Edward Aboagye
P16150395
work? you can call two capacities with a semaphore: pause() and sign()
pause() work essentially diminishes the semaphore an incentive by 1. what's more, if the new
worth is negative, it needs to hold up until the worth is sure once more(Massara, Di Matteo, &
Aste, 2016).
so you began with semaphore = 4. with each individual going into the room, it's diminished by 1.
individual 1 enters...sem = 3
individual 2 enters...sem = 2
individual 3 enters...sem = 1
individual 4 enters...sem = 0
individual 5 attempts to enter however sem = - 1 now, our guardian won't let him in. in this way,
he needs to pause. until, somebody leaves the room!
when you're finished with basic segment, you signal() to let the pariah realize that he can enter
now. so as should be obvious, this capacity builds the semaphore an incentive by 1(Kan, Chen, &
Huang, 2018, August).
mutex is semaphore = 1.

Edward Aboagye
P16150395
with this execution, while An is running, its absolutely impossible that B can arrive at the CS
where he changes some worldwide variable with a setting switch. B needs to hold up until An is
finished. what's more, the other way around(Liang, Shen, Feng, Lin, & Yan, 2016). Charts are
utilized to speak to some genuine applications: Graphs are utilized to speak to systems. The
systems may incorporate ways in a city or phone system or circuit arrange. Diagrams are
likewise utilized in interpersonal organizations like linkedIn, Facebook. For instance, in
Facebook, every individual is spoken to with a vertex(or hub). Every hub is a structure and
contains data like individual id, name, sex and district.
b)

Edward Aboagye
P16150395

Edward Aboagye
P16150395
References
Ainsworth, S. and Jones, T.M., 2016, June. Graph prefetching using data structure knowledge.
In Proceedings of the 2016 International Conference on Supercomputing (p. 39). ACM.
Kabiljo, I., Dhulipala, L., Shalita, A.M., Sharma, A.D. and Karrer, B.C., Facebook Inc,
2017. Cache efficiency by social graph data ordering. U.S. Patent Application 14/869,656.
Kan, J., Chen, S. and Huang, X., 2018, August. Improve Blockchain Performance using Graph
Data Structure and Parallel Mining. In 2018 1st IEEE International Conference on Hot
Information-Centric Networking (HotICN) (pp. 173-178). IEEE.
Liang, X., Shen, X., Feng, J., Lin, L. and Yan, S., 2016, October. Semantic object parsing with
graph lstm. In European Conference on Computer Vision (pp. 125-143). Springer, Cham.
Massara, G.P., Di Matteo, T. and Aste, T., 2016. Network filtering for big data: Triangulated
maximally filtered graph. Journal of complex Networks, 5(2), pp.161-178.