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.
3
votes
2answers
84 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 * ...
2
votes
0answers
30 views
Finding shortest paths in a Wikipedia article graph using Java
I have this sort of a web crawler that asks for two (English) Wikipedia article titles (the source and the target), and proceeds to compute the shortest path between the two. My code is as follows:
...
-4
votes
0answers
26 views
Could anyone find a bug in my code for finding whether the graph is BIPARTITE or not ? [closed]
I am solving this problem on spoj. The problem essentially tells to find whether graph is bipartite or not. I have written the code and tried many(really many) test cases but it seems to work ...
3
votes
1answer
72 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
44 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
31 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
110 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
94 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
35 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 ...
-2
votes
0answers
52 views
Can anybody help me with this (graph theory)?
I am preparing for job interviews and learning Analysis and design of algorithms. I have solved many problems using dynamic programming and greedy methods, but I am struck with this problem and unable ...
1
vote
0answers
28 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
59 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
91 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 can ...
2
votes
1answer
53 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
40 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
39 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
13 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
61 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
53 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
31 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 ...
4
votes
0answers
79 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
101 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
65 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
72 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. ...
5
votes
3answers
101 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
46 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
74 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
52 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
101 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
61 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
70 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 ...
3
votes
0answers
67 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
30 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
44 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
63 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
129 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 ...
3
votes
1answer
72 views
DFS algorithm too slow
I am practicing my coding on leetcode, and my submission, although correct for small cases, is timing out for large ones. Could you please let me know how to improve my code?
The question is as ...
3
votes
2answers
66 views
Generating a graph from a rectangular grid for graph searching
I recently reviewed some code implementing some heuristics which has piqued my interest in the A* graph searching algorithm. I'm going to do that in a bit but first I need a way to create a graph in ...
3
votes
1answer
80 views
A graph representation of Adjacent Matrix in Python
I'm trying to create a graph representation in Adj Matrix in Python. I'm not sure if this is the best pythonic way.
...
1
vote
0answers
39 views
Depth Limited Search for Map Coloring Graph in Python [closed]
Hey I'm trying to solve the Map Coloring Problem using a Depth Limited Search. I found an example of the problem here (https://courses.cs.washington.edu/courses/cse473/10au/slides/chapter05-6pp.pdf), ...
1
vote
2answers
63 views
Check if the undirected graph is cyclic
Here is my approach. Do DFS and check in stack whether the new node is already in the Stack or not.
...
1
vote
1answer
44 views
Check directed graph is tree or not
Here is my approach.
1. Checking there is no cycle.(Using BFS)
2. All nodes are connected. (visited)
...
3
votes
0answers
106 views
CLRS(Introduction To Algorithms) implementation of BFS and DFS in Java
This is the implementation of BFS and DFS i have tried to follow from CLRS.Please suggest what can be improved in this code.
...
0
votes
2answers
60 views
Check if path exists directed graph, without using collection
I have written code to find whether the path exists between source and destination in a directed graph. I have used BFS and instead of ArrayList or queue. I have ...
5
votes
1answer
78 views
Find the largest continuous descending sum in a 2d matrix
Given a 2d array, the problem is to find the largest sum, where each subsequent is >= the previous digit but < all of the 'neighbour' digits. You can only move up, down, left and right.
My ...
2
votes
1answer
79 views
Finding smallest number of moves
We are given a map of sides of length n and m (both n and m are less than 1000), divided into n*m fields (squares of side 1). The map looks (for example) like this:
...
5
votes
3answers
392 views
“Researcher Hatim is right or wrong” challenge
I wrote a program to solve a problem, I am not so good in python so want help to find areas where this program can be improved or simplified and readable too:-
I got this problem in a code challenge
...
2
votes
1answer
80 views
Find all the countries I can visit by just crossing direct borders
I was helping on this question. There you have a table border to indicate countryA and countryB have a common border. And want ...
1
vote
1answer
84 views
Computing the distance and weight matrix of a graph
I would like to create an igraph object. First, I set up the size of igraph object — n, m, then create a random matrix. As a result matrix ...
