Skip to content
Advertisement

Tag: graph-theory

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 also gives expected results (see dfs_iter() below). However, in this version I am

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, additional cost should be added.

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 through the nodes assuming that

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 check for an edge of

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 recursive function, but hit Python’s

Advertisement