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.

learn more… | top users | synonyms

7
votes
1answer
361 views
6
votes
1answer
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. ...
4
votes
1answer
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 ...
11
votes
1answer
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 (...
3
votes
1answer
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. ...
1
vote
0answers
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 ...
5
votes
1answer
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 ...
3
votes
2answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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: ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
6
votes
3answers
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 ...
0
votes
0answers
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: ...
3
votes
2answers
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 * ...
4
votes
0answers
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 ...
4
votes
1answer
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 ...
2
votes
1answer
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 ...
5
votes
1answer
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 ...
3
votes
2answers
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. ...
4
votes
1answer
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 ...
3
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
0answers
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 ...
0
votes
1answer
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 ...
3
votes
0answers
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 ...
4
votes
0answers
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 ...
7
votes
1answer
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 ...
0
votes
0answers
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 ...
5
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
67 views

Implementation of Prim's algorithm in C++

Could anyone comment on what could be done better and if I made any mistakes? ...
5
votes
0answers
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. ...
6
votes
3answers
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: ...
4
votes
0answers
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 ...
3
votes
1answer
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 ...
2
votes
0answers
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: ...
3
votes
1answer
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 ...
0
votes
1answer
82 views

Simple weighted directed graph in Python

I have this simplistic Python class for representing directed weighted graphs (digraphs for short): Digraph.py ...
0
votes
0answers
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 ...
5
votes
0answers
73 views

Graph Library in C

Could you guys please review the Graph Library I developed in C? It's also on GitHub ...
1
vote
0answers
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 ...
4
votes
1answer
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 ...
3
votes
0answers
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 ...
2
votes
1answer
29 views

Distributed (asynchronous) averaging

This code simulates a distributed averaging protocol. There is a network of nodes, and at the clicks of a Poisson process: A random node wakes up Transmits it's current average to all the nodes it ...
4
votes
1answer
134 views

Using the A* algorithm to search a graph generated from a grid

Following on from my previous question, I finally got round to actually doing the A* search for the Graph<MapTile>. The changes to the code from the previous ...