Menu

Graphs in Python and Prolog for Shortest Paths

Category Data Engineering

Graphs are omnipresent in today’s computing world. From implementing compilers to computer games to maps, you will need to use graphs everywhere. In case you are a programmer and not sure what is a graph or any of the major graph algorithms, please take a look at these books on graph algorithms. In this blog, we will be talking about graphs in python and prolog

Graphs

 

Let’s build a graph and see what the solution using standard techniques look like. First, let’s define a graph. We will define the graph in Python and try to visualize it as well.

graph = {'a': {'w': 14, 'x': 7, 'y': 9},
'b': {'w': 9, 'z': 6},
'w': {'a': 14, 'b': 9, 'y': 2},
'x': {'a': 7, 'y': 10, 'z': 15},
'y': {'a': 9, 'w': 2, 'x': 10, 'z': 11},
'z': {'b': 6, 'x': 15, 'y': 11}}

This can be visualized in Python using the libraries networkx and matplotlib.

%matplotlib inline

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import pylab

# initialise a directed graph
G = nx.DiGraph()

# add the edges and the weights.
G.add_edges_from([('A', 'W')], weight=14)
G.add_edges_from([('A', 'X')], weight=7)
G.add_edges_from([('A', 'Y')], weight=9)

G.add_edges_from([('B', 'W')], weight=9)
G.add_edges_from([('B', 'Z')], weight=6)

G.add_edges_from([('W', 'A')], weight=14)
G.add_edges_from([('W', 'B')], weight=9)
G.add_edges_from([('W', 'Y')], weight=2)

G.add_edges_from([('X', 'A')], weight=7)
G.add_edges_from([('X', 'Y')], weight=10)
G.add_edges_from([('X', 'Z')], weight=15)

G.add_edges_from([('Y', 'A')], weight=9)
G.add_edges_from([('Y', 'W')], weight=2)
G.add_edges_from([('Y', 'X')], weight=10)
G.add_edges_from([('Y', 'Z')], weight=11)

G.add_edges_from([('Z', 'B')], weight=6)
G.add_edges_from([('Z', 'X')], weight=15)
G.add_edges_from([('Z', 'Y')], weight=11)

# value map so that we have different colors for different nodes
val_map = {
'A': 1.0,
'B': 0.9,
'W': 0.8,
'X': 0.7,
'Y': 0.6,
'Z': 0.5
}

values = [val_map.get(node, 0.45) for node in G.nodes()]
edge_labels=dict([((u,v,),d['weight'])
for u,v,d in G.edges(data=True)])
red_edges = [('A','Y'),('Y','W'), ('W', 'B')]
edge_colors = ['black' if not edge in red_edges else 'red' for edge in G.edges()]
node_labels = {node:node for node in G.nodes()}

plt.axis('off')
fig = plt.figure(1)
fig = plt.figure(num=1, figsize=(10, 10), dpi=100)
fig.set_size_inches(10.5, 10.5)

# draw it out.
pos=nx.spring_layout(G)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
nx.draw_networkx_labels(G, pos, labels=node_labels)
nx.draw(G,pos, node_color = values, node_size=1500,edge_color=edge_colors,edge_cmap=plt.cm.Reds)

xmax = 1.2
ymax = 1.1
plt.xlim(-0.1, xmax)
plt.ylim(-0.1, ymax)

pylab.show()
pylab.close()
del fig

To find the shortest path using python you probably will need to implement a known algorithm such as Dijkstra. You can try to look at the code linked here which I would argue is huge. The implementation will be the same in almost all object oriented and procedural code. But in Prolog, due to many things being handled by the compiler, the code gets reduced a lot.

No need to write node classes or priority queues

Just write the relationships between the nodes and edges in a simple, clean manner.

edge(a,w,14).
edge(a,x,7).
edge(a,y,9).

edge(b,w,9).
edge(b,z,6).

edge(w,a,14).
edge(w,b,9).
edge(w,y,2).

edge(x,a,7).
edge(x,y,10).
edge(x,z,15).

edge(y,a,9).
edge(y,w,2).
edge(y,x,10).
edge(y,z,11).

edge(z,b,6).
edge(z,x,15).
edge(z,y,11).

Now, looking at the code that crunches the numbers.

findapath(X, Y, W, [X,Y], _) :- edge(X, Y, W). % findapath between X and Y has weight W  if there is an edge between X and Y of weight W
findapath(X, Y, W, [X|P], V) :-                % else findapath between X and Y
        \+ member(X, V),                       % is true
edge(X, Z, W1),                        % if we can findapath between X and Z with weight W1
findapath(Z, Y, W2, P, [X|V]),         % and there is findapat between Z and Y of weight W2
W is W1 + W2.                          % where W is W1 + W2


:-dynamic(solution/2).
findminpath(X, Y, W, P) :-
\+ solution(_, _),
findapath(X, Y, W1, P1, []),
assertz(solution(W1, P1)),
!, findminpath(X,Y,W,P).


findminpath(X, Y, _, _) :-
findapath(X, Y, W1, P1, []),
solution(W2, P2),
W1 < W2,
retract(solution(W2, P2)),
asserta(solution(W1, P1)), fail.


findminpath(_, _, W, P) :- solution(W,P), retract(solution(W,P)).


main :-
    findminpath(a,b,W,P),
    write('the minimum cost that we must pay.'),
    write(W),
    nl,
    write('path that has the minimum cost.'),
    write(P),
    nl, halt.

A huge shout-out to Rodney who has made a brilliant description of the above code.

Last Thoughts

In many cases involving graphs, Prolog helps us in writing clear and concise code. It is easier to express some data structures using Prolog that needs more careful code writing with intricate testing to come to the same solution.

In case you found this interesting and would like to talk more on this, just drop me a message @alt227Joydeep. I would be glad to discuss this further. You can also hit the like button and follow me here, on Medium.

References:

Recommended Reading

Explore our insightful articles, whitepapers, and case studies that delve deeper into the latest industry trends, best practices, and success stories. Gain valuable knowledge and stay informed about the ever-evolving landscape of digital transformation.

Navigating The Two Major Data Trends in 2024

As the data landscape continues to evolve rapidly, businesses are compelled to stay abreast of emerging trends to maintain competitiveness. In the year 2024, two prominent trends are poised to redefine data analytics: the proliferation of Generative AI and the adoption of modern data contracts. These trends not only reshape how organizations utilize data but also underscore the importance of ethical considerations and robust governance in data management. This article explores these trends in-depth, providing insights into effective strategies for implementation and the implications for businesses navigating the data landscape.Trend #1: The Ascendancy of Generative AIGenerative AI, characterized by its ability to create new content autonomously, has gained significant traction across industries. The advent of large language models (LLMs) has propelled Generative AI into the mainstream, with tech giants like Microsoft, Google, and Meta integrating Generative AI capabilities into their products. As businesses increasingly rely on AI-driven insights, Generative AI is poised to become an indispensable tool for enhancing productivity and driving innovation.Strategy for Effective Implementation:To leverage Generative AI effectively, businesses must develop a comprehensive strategy tailored to their specific needs and objectives. This strategy should encompass several key components:Identifying suitable use cases:Organizations should identify areas where Generative AI can augment existing processes and generate tangible value. Whether it’s automating content creation, personalizing customer experiences, employee training, or optimizing business operations, identifying the right use cases is essential for maximizing ROI.Comprehensive employee training:Implementing Generative AI requires upskilling employees to ensure they can effectively utilize AI tools while adhering to ethical guidelines and best practices. Training programs should cover topics such as data privacy, bias mitigation, and ethical AI usage to foster a culture of responsible AI adoption.Strong data governance:Robust data governance is critical for ensuring the accuracy, security, and ethical usage of AI-generated insights. Organizations must establish clear guidelines and protocols for data collection, storage, and usage to mitigate risks associated with data misuse or bias.Managing costs and licensing:While Generative AI offers immense potential, it also comes with significant costs, both in terms of technology investments and licensing fees. Organizations must develop a cost-effective strategy for scaling AI initiatives while ensuring compliance with budgetary constraints.Balancing automation and human judgment:While AI-driven insights can enhance decision-making processes, it’s essential to strike a balance between automation and human judgment. Human oversight is crucial for interpreting AI-generated insights, identifying biases, and ensuring ethical decision-making.Ethical considerations:As AI becomes increasingly integrated into business operations, organizations must prioritize ethical considerations and accountability. This includes addressing issues related to data privacy, algorithmic bias, and the potential societal impact of AI-driven decisions.Trend #2: Adoption of Modern Data ContractsModern data contracts have emerged as a solution to streamline data usage and sharing, effectively addressing the challenges associated with broken data integrations and communication gaps between application and analytics teams.Structured Data Interactions:Modern data contracts represent a paradigm shift in how organizations manage data interactions. Unlike traditional contracts, which are static and cumbersome to maintain, modern data contracts are dynamic agreements that evolve with changing data requirements and business needs.Integration into workflows:By integrating data contracts into existing workflows and development processes, organizations can ensure seamless data interactions across disparate systems and applications. This integration enables teams to collaborate more effectively, reducing friction and improving data quality and consistency.Implementation Strategies:Implementing modern data contracts requires a strategic approach focused on collaboration, standardization, and automation. Key strategies include:Developing clear standards:Organizations should establish clear standards and guidelines for data contracts, outlining key parameters such as data formats, schemas, and validation rules. These standards help ensure consistency and interoperability across data systems and applications.Instituting change controls:Change management processes are essential for managing versioning and ensuring smooth transitions between data contract iterations. By implementing robust change controls, organizations can minimize disruptions and maintain data integrity throughout the contract lifecycle.Training and tools:Equipping teams with the necessary training and tools is crucial for successful data contract implementation. Training programs should cover topics such as contract management, data governance, and compliance, while tools such as data modeling platforms and contract management software can streamline the contract development and deployment process.As businesses navigate the complexities of the data landscape in 2024, adapting to the rise of Generative AI and modern data contracts is essential for driving innovation and maintaining competitiveness. By developing comprehensive strategies for AI adoption and data governance, organizations can harness the transformative power of Generative AI while ensuring ethical and responsible data usage. Likewise, embracing modern data contracts enables organizations to streamline data interactions, improve collaboration, and enhance data quality and consistency. By embracing these trends and implementing best practices, businesses can unlock new opportunities for growth and success in the digital age.

Learn More >

The Journey from System Admin to DevOps Superstar

According to a report by the Economic Times, when organizations cultivate a better work environment, the overall experience improves exponentially. They find true meaning in their jobs by prioritizing employees’ mettle, exceeding expectations, and work allocation.Employees seek exposure and opportunities in their jobs. By building productivity and customer satisfaction they enhance their portfolio.Radhakrishnan one of our DevOps superstars, has contributed with his service and time for over 8 years. To commemorate this everlasting relationship we got into a candid conversation with him. Here’s what he had to say about his journey before and with Nineleaps.Radhakrishnan is originally from a small town near Bengaluru, Hosur. After completing his MBA, his interest developed in computers and networking. He successfully gained appropriate knowledge by undertaking network courses and embarked on a journey to becoming a system admin. He enjoyed working for various companies as a system admin.Then came Nineleaps which gave new horizons of opportunities to his mettle. When we asked him about his transition from a system admin to a DevOps engineer, he fondly remembered a quote given to him by our CEO on the day of his selection.“You are on the flight now, just fly,” — Divy Shrivastava.And, so he did.Divy’s words of confidence boosted his resolve. The walk towards DevOps became a sprint, as multiple iterations of knowledge and experience suffused him. The arena of his work leaped and much to his admiration, he realized DevOps to be his passion and soul.Right from the get-go, an intensive training regimen, honing his skills, immersing himself in countless hours of study, and shadowing esteemed senior members of our organization he grasped the crucial importance of comprehending tasks and prioritizing them effectively. Driven by an unwavering desire to learn and prove his mettle, his transition from a system admin to a DevOps maestro was seamless. Multiple training sessions helped him get a deeper understanding of internal and external projects as well as the product, giving him never-to-dull confidence.Learning and development, knowledge transfers, and peer learning are certainly at the core of Nineleaps which helped him become the super engineer he is today. These trainings were both from the client’s side as well as in-house learning at Nineleaps.“In my opinion what sets Nineleaps apart is our dynamic and flexible approach to projects, with extensive focus on Agile methodology we are trained and nourished to build quality solutions for our clients, and also are facilitated with high-tech exposure by working with industry giants and rewarded with the utmost respect and growth opportunities.”To understand more closely we asked him about the challenges he faced at times, and according to him, documentation was a challenge. He feels all the work that the employee is doing must be documented and organized in a proper way as it will help them in the future. He also informed about instances where a person working on a specific problem might face similar challenges later in the same week and not be able to recall what the solution was properly, in such cases documenting everything became important. The organization’s culture was very open and asking questions or requesting help was never an issue which facilitated collaboration in resolving such challenges.Nineleaps became the crucible to test his mettle and with each strike of the hammer, a superstar was born.

Learn More >

Performance Testing Trends: Future of Software Optimization

Performance testing is an integral part of the software development lifecycle as it helps determine the scalability, stability, speed, and responsiveness of an application as compared to the workload given. It is not a standalone process and should be run throughout the software development process.It serves the purpose of assessing various aspects of an application’s performance, such as application output, processing speed, data transfer velocity, network bandwidth usage, maximum concurrent users, memory utilization, workload efficiency, and command response times. By evaluating these metrics, performance testers can gain valuable insights into the application’s capabilities and identify any areas that require improvementUsing AI to automate testing:Performance testing encompasses various stages, each posing unique challenges throughout the testing lifecycle. These challenges include test preparation, execution, identifying performance bottlenecks, pinpointing root causes, and implementing effective solutions. AI can help reduce or even eliminate these differences. AI-powered systems can handle the mountains of data collected during performance testing and be able to produce efficient and accurate analyses. AI can also identify the sources of performance slowdowns in complex systems, which can otherwise be tedious to pinpoint. With AI-driven automation, performance testers can streamline the testing process, ultimately saving time and resources while ensuring reliable results.Open Architecture:Performance testing, which evaluates how well a system performs, is undergoing a significant shift away from relying solely on browser-based evaluations. Instead, internet protocols like TCP/IP are being adopted for comprehensive performance monitoring. This approach emphasizes the need for system components to work together harmoniously while assessing their performance individually. The integration of cloud-based environments has become crucial, as cloud computing is an integral part of modern technology infrastructure. Cloud-based environments provide a flexible and reliable platform that enables seamless integration and coordination of various components, ultimately leading to enhanced system performance. It is crucial to prioritize comprehensive performance testing, which involves evaluating individual component performance, managing loads, monitoring in real-time, and debugging, to ensure optimal system performance.Self Service:When adopting the aforementioned trends, it’s essential to consider practical implementation tips for successful outcomes. For instance, performance engineers can use AI-powered tools to analyze performance data more effectively, leading to more accurate and actionable insights. Integrating cloud-based solutions can provide the flexibility and scalability required for modern performance testing demands. As stakeholders implement these trends, the collaboration between development, testing, and IT operations teams becomes crucial for successful integration and improved application performance.SaaS-based Tools:Testers can now easily set up and execute tests at cloud scale within minutes, thanks to the convergence of self-service, cloud-based testing, SaaS, and open architecture. Unlike older desktop-based tools that demand extensive setup, the emerging tools simplify the process with just a few clicks. Furthermore, these modern technologies offer seamless interoperability, significantly enhancing performance capabilities.Changing Requirements:In classic app testing, testers had to make educated guesses about the software’s use and create requirements and service-level agreements accordingly. However, in DevOps-oriented environments, performance requirements are seen as dynamic and evolving. Traditional requirements are now driven by complex use cases, accommodating different user experiences across various devices and locations. Performance engineering plays a critical role in continuously monitoring systems and proactively identifying and resolving issues before they can negatively impact customer retention or sales.Sentiment analysis:Monitoring production provides insight into server response times but does not capture the true customer experience. Synthetic transactions, on the other hand, simulate real user actions in production continuously. They can range from basic interactions like logging into an e-commerce site and adding products to a cart, to more complex transactions that track performance end to end without actually completing real orders or charging credit cards. Tracking the actual user experience is crucial for identifying bottlenecks, delays, and errors in real-time, as some issues may go unreported by users. Sentiment analysis is a powerful technology that evaluates customer responses based on emotions, providing valuable insights from customers’ reactions expressed in plain text and assigning numerical sentiment scores.Chaos Testing:Chaos testing is a disciplined methodology that proactively simulates and identifies failures in a system to prevent unplanned downtime and ensure a positive user experience. By understanding how the application responds to failures in various parts of the architecture, chaos testing helps uncover uncertainties in the production environment. The main objective is to assess the system’s behavior in the event of failures and identify potential issues. For instance, if one web service experiences downtime, chaos testing ensures that the entire infrastructure does not collapse. This approach helps identify system weaknesses and addresses them before reaching the production stage.Conclusion:As software development continues to evolve, performance testing must keep pace with emerging trends and technologies. By leveraging AI-driven automation, open architecture with cloud integration, and practical implementation tips, stakeholders can optimize their performance testing processes to deliver high-performing and responsive software applications. Real-world examples and a focus on key performance metrics ensure that these trends are not only understood but effectively implemented to achieve the desired outcomes. Embracing these trends empowers software development teams to elevate the user experience, enhance customer satisfaction, and drive business success.

Learn More >

Ready to embark on a transformative journey? Connect with our experts and fuel your growth today!

Explore Now