I have a serious issue with finding all possible paths in my csv file that looks like this : Source Target Source_repo Target_repo SOURCE1 Target2 repo-1 repo-2 SOURCE5 Target3 repo-5 repo-3 SOURCE8 Target5 repo-8 repo-5 There a large amount of lines in the datasets, more than 5000 lines. I want to generate a…
Tag: graph-theory
Path through specific vertices without an end point
I am trying to write an algorithm solving a type of maze. It could look something like this: The player character is the red circle and the goal is to collect all the blue squares. The player can move up, down, left or right but only stops when hitting a wall. I start by converting the maze into a graph(going
Is it possible to do a depth first search iteratively without copying visited nodes?
Background I am searching a 2D grid for a word. We can search left/right and up/down. For example, in this grid, searching for “abef” starting at (0,0) will return True Example (grid1): Where I’m at The recursive version gives expected results (see dfs_rec() below). The iterative version als…
Find all shortest paths between all pairs of nodes in NetworkX
I am trying to get all shortest paths between all pairs of nodes in an undirected unweighted graph. I am currently using nx.all_pairs_shortest_path(), but I don’t understand why it only returns one shortest path for every pair of nodes. There are cycles in my graph so there should exist multiple shortes…
Add additional cost to path depending on label of edge
I have a graph with some edges. Each edge has a weight/cost and also a label/type, which could be red and green. I know that if I run Dijkstra’s algorithm it will find the shortest/cheapest path from the weights of all edges. However, my issue is that depending on which type of edge it chooses, addition…
Algorithm for Connected Components of Graph
I am looking for the most efficient algorithm in order to find both the number of connected components in a network, and the number of nodes for each connected component. Example: Given the following inputs: I would receive the following output: This is what I have so far: I have found a way to iterate throug…
How to connect two nodes if they are disconnected
I use a python NetworkX graph. How to check if 2 nodes are disconnected and then get a new version of the graph where these 2 nodes are connected. The difference between 2 graphs should have min edit distance (Levenshtein distance) Before and after for nodes=[1,2]: | Answer you can also have a condition to ch…
deceptively simple implementation of topological sorting in python
Extracted from here we got a minimal iterative dfs routine, i call it minimal because you can hardly simplify the code further: Here’s my question, how could you transform this routine into a topological sort method where the routine also becomes “minimal”? I’ve watched this video and …
calculate indegree centralization of graph with python networkx
I have a graph and want to calculate its indegree and outdegree centralization. I tried to do this by using python networkx, but there I can only find a method to calculate indegree and outdegree centrality for each node. Is there a way to calculate in- and outdegree centralization of a graph in networkx? Ans…
Fetch connected nodes in a NetworkX graph
Straightforward question: I would like to retrieve all the nodes connected to a given node within a NetworkX graph in order to create a subgraph. In the example shown below, I just want to extract all the nodes inside the circle, given the name of one of any one of them. I’ve tried the following recursi…