# Tagged Questions

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.

361 views

...
26 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. ...
67 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 ...
67 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 (...
74 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. ...
24 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 ...
91 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 ...
141 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 ...
99 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 ...
85 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 ...
46 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: ...
118 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 ...
42 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 ...
125 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 ...
36 views

### Finding shortest paths in a Wikipedia article graph using Java - second attempt

I have improved Finding shortest paths in a Wikipedia article graph using Java. Now I have this: AbstractWikipediaShortestPathFinder.java: ...
93 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 * ...
59 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 ...
116 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 ...
57 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 ...
43 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 ...
139 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. ...
99 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 ...
71 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 ...
34 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 ...
110 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 ...
137 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 ...
92 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 ...
47 views

### Comparing linear time strongly connected component algorithms in Java

So I have implemented three linear time ($\mathcal{O}(V + E)$) algorithms for finding strongly connected components of a (directed) graph. A strongly connected component is just a maximal subset of ...
46 views

### Optimizing and accounting for edge cases in Dijkstra's algorithm

I just recently wrote a program to simulate how multicast routing works. The program uses a weighted graph to represent the network and simply runs it through the algorithm. I would like to know if ...
15 views

### Data Explorer query that makes bar graphs

I wrote a query for SEDE that I think is pretty cool. It uses the currently available graphing capabilities (scatter plots) to create a bar graph. I have used it as the subject for a self-answer on ...
78 views

### Pseudo-parallel depth-first search

I'm writing a small program, that generates a file containing an adjancency matrix, it then reads from that file, constructs a graph and does something like a parallel dfs on it. How can I make the ...
55 views

### Social network graph of characters in a novel

I wrote a C program that builds a social network graph of characters in a novel. The program takes two text files as input: a list of the names of the characters in the novel, and the file of the ...
35 views

### Adjacency List Graph Implementation for search

I wrote this adjacency list graph implementation to learn about implement path finding and graph search. I'm looking to fix any coding style / best practice issues, and performance issues. Also, the ...
89 views

### Plotting charts for a large data set

I have created an automated macro which takes vehicle crash data from a .csv file and automatically creates a pivot table and plots and compares it to the previous year. The code is approximately 1400 ...
120 views

### Implementation of Dijkstra's algorithm in C++

This is my implementation of Dijkstra's algorithm. Could you tell me what am I doing wrong and what should be fixed? I was not sure how to keep track of the shortest outgoing edge from a node and I ...
67 views

### Implementation of Prim's algorithm in C++

Could anyone comment on what could be done better and if I made any mistakes? ...
89 views

### Topological sort using recursive DFS

I am currently learning Graph algorithms by solving questions on online judges. The below code is for implementing Topological sort, using recursive DFS. Also, it is my first time with C++ STL. ...
119 views

### Idiomatic ruby to calculate distance to points on a graph

Can this code be made more like idiomatic ruby using methods such as map or inject? @random_tour is a variable length array of points on a graph: ...
53 views

### Simple graph in Rust

I have written simple code to construct a graph, but I think there are too many different types for such a simple task. In this code I need to store Node structs ...
87 views

### Detect cycle in undirected graph

Below is my code to detect cycle in an undirected graph. Could anyone please review and let me know if I have taken care of all the cases? The basic idea is to use DFS (non-recursive using stack) and ...
76 views

### Finding all paths between nodes in a graph

I wanted to write a function paths that returns the possible routes between two nodes in a graph. For example: ...
134 views

### Dijkstra's algorithm: traditional and bidirectional in Python

I have translated Dijkstra's algorithms (uni- and bidirectional variants) from Java to Python, eventually coming up with this: Dijkstra.py ...
82 views

### Simple weighted directed graph in Python

I have this simplistic Python class for representing directed weighted graphs (digraphs for short): Digraph.py ...
73 views

### Hierarchical Data to Graph

I am using vis.js to visualize some hierarchical data. I have created a recursive routine to add nodes and edges for each group and value in the dataset. I feel like something already exists for this ...
73 views

### Graph Library in C

Could you guys please review the Graph Library I developed in C? It's also on GitHub ...
32 views

### Minimum number of moves to reach the end - follow-up

I need to calculate the minimum number of jumps to reach the end of an array with dice throws. Array values may be negative/positive: When positive - move forward When negative - go back The ...
50 views

### Minimum number of moves to reach the end

I need to calculate the minimum number of jumps to reach the end of an Array with dice throw. Array values may be negative/positive: When positive - move forward When negative - go back The ...
103 views

### Implementation of Dijkstra's Algorithm in JavaScript that returns both shortestDist/shortestPaths

I decided to try to understand the basic idea behind Dijkstra's algorithm better so I implemented it in JavaScript (the only language I am proficient in as of now) so I could really see what was ...