All Questions
64 questions
2
votes
1
answer
73
views
Clique Connect: minimum spanning tree
Problem Statement
You are given a weighted undirected graph G with N vertices, numbered 1 to N. Initially, G has no edges.
You will perform M operations to add edges to G. The i-th operation (1≤i≤M) ...
- 244
0
votes
1
answer
60
views
Performance optimization of traveling salesman like issue
I need help optimizing the performance of this, which is essentially similar to the traveling salesman problem, with the addition that I want to make the graph complete first, with the weight of the ...
- 109
2
votes
0
answers
194
views
Backtracking graph algorithms for a word puzzle in Python
Motivation
Recently, Buzzfeed released a browser-based puzzle game called "Pyramid Scheme." It is available at the following link. The puzzle in an initial state looks like this:
To solve ...
- 163
6
votes
1
answer
238
views
Python code to contract (shrink) a graph
To better understand a paragraph, I implemented the intent behind the paragraph. In this case, it was a formal definition of a graph contraction:
Suppose we have an undirected graph G and X ⊆ V(G). ...
- 1,008
4
votes
2
answers
2k
views
Floyd-Warshall Path Reconstruction
Below is the implementation for the Floyd-Warshall algorithm, which finds all-pairs shortest paths for a given weighted graph.
The function floyd_warshall takes a ...
- 435
8
votes
1
answer
2k
views
Recursive and iterative implementation on Kosaraju algorithm
Kosaraju algorithm is mainly phrased as two recursive subroutines running postorder DFS twice to mark SCCs with linear time complexity O(V+E) below,
For each vertex \$u\$ of the graph, mark \$u\$ as ...
- 181
3
votes
2
answers
165
views
Finding Number of Objects in Image
I wrote a program that, given a 2D array representing pixels in a birds eye view image, it returns the number of Objects in the image.
Pixels that are connected in the up, down, left, and right ...
- 51
5
votes
1
answer
1k
views
Tarjan's Algorithm Python Implementation
I'm planning to use Tarjan's algorithm for a program in which I would be processing a file, converting the processed data to a dictionary, doing a topological sort on that dictionary (using this ...
- 435
4
votes
1
answer
805
views
Python implementation of Kahn's Algorithm
Please provide any suggestions on the below code for Kahn's algorithm. Can it be implemented in a better manner, or be improved:
...
- 435
5
votes
1
answer
10k
views
Greedy Graph Coloring in Python
Graph Coloring Algorithm (Greedy/ Welsh Powell)
I am trying to learn graphs, and I couldn't find a Python implementation of the Welsh Powell algorithm online, so I tried to write my own. Here are the ...
- 53
3
votes
1
answer
450
views
friendship program using graph type python/algorithm
I have created a program but I feel the def common(friendships, person1, person2) function can be more efficient, if anyone has any good idea how I can improve it I ...
- 31
4
votes
1
answer
2k
views
CodeChef's Tree MEX (Minimum Excludant) challenge
This code is a solution for CodeChef's Tree MEX problem:
Minimum excludant (or MEX for short) of a collection of integers is
the smallest non-negative integer not present in the set.
You ...
- 233
5
votes
2
answers
13k
views
Constraint Programming: Map color problem
I've written some python code to solve the map coloring problem. In my code, I represent the problem using Territory and MapColor...
- 1,233
3
votes
2
answers
3k
views
Word ladders program in Python
Background information: Given two different strings of equal length, the spacing between them is the number of other strings you would need to connect them on a word ladder. Alternately, this is 1 ...
- 391
1
vote
0
answers
378
views
Directed graph and Dijkstra algorithm using heap
I have implemented directed graph and Dijkstra algorithm using heap in Python.
I first implemented an abstract base class WeightedGraph, of which ...
- 256