Shortest Path in Text Data, AI-Exercise from Research Perspective

Here is next article, which is written from research perspective. The aim of article is to form a base to cover shortest path problems in Textual Data. Graph based algorithms have a huge potential to be used in Natural Language Processing and in many Graph based problems. In this article I introduce you how, how to initialize Graph based analysis in Text file. Note, that Graph based algorithms are still in the arena of being used in research works for NLP and Text Mining.

Lets start with initializing of graphs from a Text Data. So let us make a Graph from Textual input which is a file as of now, means in this article.

Graph is a collection of vertices and edges connecting them along with the weights of these connection. This is a highly used data structure in computer science, and its use if often made in research in AI.

Step 1. We use networkx and initiliaze the graph G with it, sentences is the list of text fragments in the input.

import networkx as nx
G = nx.MultiDiGraph()
sentences = []
inputMediumfile = open("/content/File1.txt")
num_sent = 1
for sentence in inputMediumfile:
num_sent = num_sent+1

Step 2. Now adding edges to the Graph, if the similarity between the two vertices in the Graph just created is greater that a given threshold

import matplotlib.pyplot as plt

print('Making of non complete graph from these nodes, avoiding self loops')

def edge_Weight(i,j):
########################similarity code as per requirement ###########
return distance_t

for i in range(1, num_sent-1):
for j in range(1, num_sent-1):
weight = edge_Weight(i,j)
if weight >= threshold:
G.add_edge(i,j, weight+1)
print("Vertex set: ",G.nodes())
print("Edge set: ",G.edges())
nx.draw(G, with_labels=True)

Step 3. Find the shortest path from node 2,

nx.shortest_path(G, 2)

Sample Output

Published by Nidhika

Hi, I have an excellent problems solving skills in the domain of Engineering, and Modelling Solutions for tasks. Apart from profession, I have inherent interest in writing especially about Global Issues of Concern, poems, stories, doing painting, cooking, photography, music to mention a few! And most important on my website you can find my suggestions to latest problems, views and ideas, my poems, stories, novels, my comments, my proposals for people with funding's to implement, my blogs, my interests, my personal experiences and glimpses of my research work as well.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: