Questions tagged [graph]

A graph is an abstract representation of objects (vertices) connected by links (edges). For questions about plotting data graphically, use the [data-visualization] tag instead.

Filter by
Sorted by
Tagged with
3
votes
1answer
4k views

A*, Uniform cost and Greedy Best first search implementations

I am writing the code for A*, Uniform cost search and Greedy best first search algorithms in Java. I have finished the code which is working fine but I have used a bit different design strategy while ...
2
votes
1answer
124 views

Internal method to calculate the distance between all nodes in Kruskal's Importance (Driver) Algorithm

I've been trying to reduce the indentation from a method in my code. The solution will probably be unrelated to the language, in this case python, although it may rely on some python specific ...
4
votes
1answer
2k views

Graph represented by an adjacency matrix in C++

I'm working on my data structures knowledge and wanted to create a graph with a small DFS driver which simply prints the nodes as it visits them. Here's my graph class: ...
4
votes
1answer
3k views

Dijkstra's algorithm using a dictionary for the priority queue

Unrelated to code: This is my first project in Python using classes and algorithms. I have spent the last week self teaching myself about queues and stacks, so I am NOT trying to use any Python ...
5
votes
1answer
85 views

Calculating how similar two objects are according to a database

I want to calculate how similar two objects are according to a database. However the code is very slow; it takes around 2 minutes to analyze just 3 objects. How can I speed it up? I have tried to ...
3
votes
1answer
4k views

Implementing an Adjacency List in C

I haven't yet implemented any sort of graph thus far in C and decided to give it a go by trying to implement an adjacency list in C. Is there anything in my code that you see that I can improve and is ...
5
votes
1answer
564 views

Social network broadcast message algorithm

Working on below problem and post problem and my current code. My idea is to always iterate from the minimal in-degree node which has not been visited before. Then based on this node to do a BFS. I am ...
1
vote
0answers
48 views

FindUnion data structure used to find the minimum cut of a graph

I am trying to find the bottleneck in my code for computing the minimum cut of a graph. Currently the program runs in about 40 minutes on the test data set linked below (200 nodes and ~2000 edges). I ...
2
votes
1answer
4k views

Directed weighted Graph Data Structure in Java

I am beginner in Java. I coded Directed weighted Graph data structure by myself without anyone's help i want to have some constructive feedback regarding my program design, weather my code is perfect ...
4
votes
1answer
3k views

Node Graph-based User Interface with python

I'd like to create a pyqt widget similar to the one Blender uses for representing its nodes After wasting some bounties without getting any answers on Stack Overflow, I thought maybe posting a little ...
3
votes
1answer
90 views

Shortest code to generate a full mesh of elements

I am trying to find the shortest code that generates a full mesh of the elements fed into it in graphviz format e.g. the full mesh of [0, 1, 2] is: 2 -> 0 2 -> 1 1 -> 0 I have the code below and I ...
4
votes
2answers
2k views

My attempt at Dijkstra's Algorithm in Python 3

I am practicing my coding at HackerRank. The exact problem statement can be found here, but to summarize, it is finding the distances of the shortest path from a starting node to every other node in a ...
2
votes
0answers
2k views

Prim's MST Java implementation

Can someone review this code, just have look if it's logically correct or If you may point me to a more simple and minimalist program ...
1
vote
0answers
71 views

Storing large maps in memory

Context of the problem: I have a very large graph that cost about 4GB to store. About 3M nodes and 34M edges. My program takes this large graph and recursively builds smaller graphs from it. At each ...
2
votes
0answers
1k views

Dijkstra's single source shortest path algorithm (with Fibonacci heap)

I implemented a generic Dijkstra algorithm. It's lazy since the vertices with their final distances are request on demand. I used the Fibonacci Heap from this question with a few changes (added a copy ...
3
votes
1answer
3k views

Weighted graph and pathfinding implementation in C#

I am implementing fundamental data structures in C#. I have written a weighted graph in Java so my main motivation here is to sharpen my skills in C#. I have tested with various cases and there seems ...
1
vote
0answers
24 views

Wikipath stack in Java - Part II/IV - The implicit Wikipedia article graph

This question is the continuation of the Wikipath stack series: the two classes that - given a Wikipedia article \$A\$ - return the lists of neighbour articles. The forward node expander return the ...
5
votes
2answers
5k views

Prim's algorithm for finding the minimum spanning tree

So I was coding Prim's algorithm for practice and this is what I wrote. It works for finding the weight of the minimum spanning tree (MST) but I'm wondering if the loop I am doing to add the the edges ...
11
votes
3answers
532 views

Dijkstra's algorithm in C99

I just implement Dijkstra's algorithm in C99. Can you review my code please? I'm looking for any mistake, performance improvement or coding style errors. main.c ...
20
votes
1answer
261 views

Rainfall - August 2016 Community Challenge (Hooray for graphs!)

A solution for the August 2016 Community Challenge (Rainfall). I've intentionally left out error checking on the file formatting. This seems like a very obvious graph problem to me - we want to ...
3
votes
0answers
1k views

Strongly connected components in a graph: Kosaraju's algorithm

I implemented Kosaraju's algorithm on a graph with 800k vertices and 5100k edges. The time taken by various operations are: building graph took 11.84 seconds ordering took 2.54 seconds ...
5
votes
4answers
7k views

Sum of all paths between all pairs of nodes in a tree

I'm trying to solve a competitive programming problem. It basically gives a undirected graph (tree-like: no multiple paths between two nodes...) and asks for the sum of all possible paths between any ...
2
votes
2answers
790 views

Converting XML to DOT

I would like to show an XML tree as a tree using GraphViz Dot tool. Then I must convert it to a DOT file. It is what I have tried ...
17
votes
2answers
37k views

BFS Implementation in Python 3

...
6
votes
1answer
80 views

Counting single degree vertex removal rounds (from a graph)

Problem: In this problem I had to remove all vertices with degree one from a given graph in rounds and count how many rounds are required to remove all possible vertices with degree 1. e.g. ...
5
votes
1answer
8k views

Undirected graph implementation in java

Here is my code which implements a undirected graph in java. I'm fairly new to java(I come from C) and I am not sure if this is a good implementation. Here are a few things i worry about - Did I use ...
12
votes
1answer
106 views

Create edges from cells

I have a (large) number of nodes and (triangular) cells, e.g., cells_nodes = [ [0, 3, 1], [0, 2, 3] ] This example represents the small mesh (Please ...
7
votes
2answers
2k views

Karger's min-cut algorithm implemented in python

I implemented Karger's algorithm with the function find_min_cut and it works, but I don't feel satisfied with the code I wrote. ...
2
votes
0answers
50 views

Parametric HOAS and graph reification

Is it possible to reify the graph of lambda terms expressed as parametric HOAS. Not quite sure if it is ...
5
votes
2answers
1k views

Clustering nodes with Hamming distance < 3

I want to speed up the following code, which is from an algorithm class. I get a list of 200000 nodes where every node is a tuple of the length of 24 where every item is either a 1 or 0. These ...
3
votes
2answers
835 views

Connected components in an undirected graph in C#

My knowledge in graph theory is very limited. I have to look for elements in an (undirected) graph who are in the same connected component. The idea is simple. First, build the graph. Then, allocate ...
2
votes
1answer
291 views

Find the number of possible infinite cycles that Bessie the Cow can get stuck in

Bessie the cow is in Farmer John's field. The field is of size 0..1,000,000,000 for x and y. Farmer John knows that there are N/2 wormholes at certain coordinates, but he does not know which wormholes ...
2
votes
1answer
145 views

Pointer lists for a C++ garbage collector

The problem My intention is to have a class A and class B. class B has a ...
1
vote
0answers
672 views

Graph (adjacency list) and DFS (topological sort)

The vertices on the graph are numbers from 0 to |V| - 1 for convenience. I was thinking later to use a template wrapper for the graph. Graph.h: ...
0
votes
1answer
502 views

Shortest path via two intermediate points

My code takes a long time for big graphs. How can I make it faster? I'm trying to calculate the shortest path for 3 path's using queue but for big input my program crashes. I'm stuck here. Can ...
5
votes
1answer
127 views

Reliability polynomial calculation

The reliability polynomial (specifically, the all-terminal reliability polynomial) is, given a value \$0 \le p \le 1\$, outputs the probability that a given graph \$G\$ is connected. Note: at the ...
8
votes
3answers
15k views

Generic graph implementation in C#

I am implementing fundamental data structures in C# while trying to learn techniques in the language to make my code cleaner, more concise, and reusable. I have implemented a generic graph with a few ...
3
votes
2answers
107 views

Assembling edges of a graph

I'm making a neural network that comprises five populations of feature-selective neurons and one population of non-selective neurons. Each neuron in this network receives connections from c * f * ...
5
votes
1answer
242 views

Finding shortest paths in a Wikipedia article graph using Java

(See also Finding shortest paths in a Wikipedia article graph using Java - second attempt.) I have this sort of a web crawler that asks for two (English) Wikipedia article titles (the source and the ...
4
votes
1answer
557 views

Dijkstra's algorithm

Assuming everything else works as expected, is the following a correct - but not the most efficient way - of implementing Dijkstra algorithm? Because I have tested it on several examples and it gives ...
3
votes
1answer
2k views

Maximum clique problem: fast heuristic

I have implemented an algorithm which computes a maximum clique via a heuristic. The pseudo-code can be found in this Paper (see Algorithm 2). Maximum Clique Problem Given an undirected, simple ...
7
votes
1answer
3k views

Cyclic “dependency detection” in JavaScript

I have written some simple code to detect cyclic dependencies for a module loading system and I'd like some feedback on how I can go about improving it. The code itself finds the first cycle in the ...
6
votes
2answers
5k views

C++ Graph Class Implementation (adjacency list)

I've got a barebones C++ graph class implemented as an adjacency list. The graph consists of a vector of vertices. Each vertex has a vector of outgoing edges that store the destination vertex id. ...
4
votes
1answer
158 views

Algorithms to find various kinds of paths in graphs

I think many here are familiar with the graph data structure. Not very long ago, I implemented as an exercise a supposedly simple Graph application that does some traversals. To note, the most complex ...
3
votes
1answer
2k views

Finding the maximum distance from the starting node

I've tried everything to make my program faster but with 250 nodes my code takes around 9 seconds to print the result, and with 5000 nodes it took around 260 seconds. Is there a way to make my ...
4
votes
0answers
208 views

Time Limit Exceeded with shortest path algorithm

The problem: SHPATH You are given a list of cities. Each direct connection between two cities has its transportation cost (an integer bigger than 0). The goal is to find the paths of ...
1
vote
0answers
73 views

Checking whether a directed graph contains a cycle

I create a myGraph class as shown below. Then I created an instance of the graph by giving the adjacency list as a NSDictionary and then call the isGraphCycleFree method. Will this answer look good ...
3
votes
2answers
7k views

Graph and minimum spanning tree in Python

Here is my Graph class that implements a graph and has nice a method to generate its spanning tree using Kruskal's algorithm. I want to: Make it pythonic Improve readability Improve the abstraction (...
2
votes
1answer
6k views

Find shortest paths in a matrix using Dijkstra's algorithm

The problem is as follows: I have a matrix with impassable fields those are marked by the input. There is also a castle which reaches up the right side of the matrix. I have to find how many paths ...
3
votes
1answer
806 views

Maxflow for baseball elimination game

I have a problem similar to the baseball elimination. Given some teams, the number of wins they have and the number of games they have left between each other I have to find for which team it is still ...