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.

581 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
564 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
37k views

...
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. ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 * ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 (...