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

3
votes
1answer
71 views

Solving Project Euler problem #60 in C++

I have implemented a solution to Project Euler problem #60. In summary, the problem asks to find the smallest sum of a set of five prime numbers such that the decimal strings of any two numbers in the ...
11
votes
2answers
137 views
+100

Kosaraju in Scala

I started coding in Scala some time ago, and also learning some fundamental algorithms in CS. Here's a terribly slow implementation of Kosaraju algorithm to find strongly connected components in a ...
3
votes
1answer
30 views

Directed graph path enumerator in Java - follow-up

I have refactored the graph path enumerator. DirectedGraphNode was not changed, so refer to the link above in case you want to have a look at it. The node type is ...
4
votes
2answers
69 views

Directed graph path enumerator in Java

I have this iterator class that expects in its constructor two directed graph nodes, source and target, and upon each ...
-1
votes
1answer
41 views

Shortest path in dag saga: Dijkstra's algorithm [closed]

I have this Dijkstra's shortest path algorithm: net.coderodde.graph.pathfinding.AbstractWeightedPathFinder: ...
2
votes
1answer
56 views

Maximum matching in graph

I'm currently working on this problem for my own practice. It's a paintball problem where I should determine if everyone can get a unique target. The problem is as follows I get a number of pair like: ...
1
vote
0answers
44 views

Generalized Missionaries and Cannibals in Java - follow-up

See the previous and initial iteration. Now I have incorporated all the points suggested by mdfst13, and have the following: StateNode.java: ...
7
votes
1answer
50 views

Animating a 2D particle “web”

I have written a small class to generate and animate one of those trendy particle webs. I plan to use this as the main background of my personal website, so naturally I'm concerned about the ...
1
vote
1answer
59 views

2D Histogram class

I scraped some data looking at trajectories of popular posts on Reddit, and now I want to group and histogram them by type. I put this class together in C++ to do so. Characteristics of the data are ...
5
votes
1answer
88 views

Generalized Missionaries and Cannibals in Java

See the next iteration. I was in the mood for some basic AI, and decided to code up an algorithm for solving "\$M\$ missionaries, \$C\$ cannibals in the boat with \$B\$ places" -algorithm: ...
2
votes
2answers
55 views

Java DFS Implementation that tracks time and parent node

I have a project where I'm to implement a DFS using a direct graph. The implementation should print the currently visited vertex, the parent (the node from which the current node was reached), and the ...
1
vote
2answers
61 views

Graph implementation to be used for finding Cycles, Paths, closest path between two nodes, etc

I am restudying graph theories and I want to write a Graph class that would allow me to implement those methods. Is there a better way of implementing a general ...
0
votes
1answer
47 views

Find unconnected nodes of a graph

It is a set of edges of a graph given. An edge is given as an array of its endpoints, e.g. [:a, :b]. The array can contain an arbitrary amount of endpoints. ...
3
votes
1answer
106 views

Breadth-first tree cutting

I have a working solution for 'Cut the tree' problem but it is not fast enough. Problem Statement: Atul is into graph theory, and he is learning about trees nowadays. He observed that the ...
3
votes
1answer
45 views

Prim's minimal spanning algorithm

Is there a way to speed up this code so it is \$O(n^2)\$ instead of \$O(n^3)\$? I'd appreciate if someone showed me how to do so. ...
2
votes
1answer
46 views

First Graph Adjacency List

First time implementing a adjacency list. Is the use of exceptions correct? If anyone could test/read the code and give some advice on improvments I would appreciate it. ...
1
vote
4answers
56 views

Checking whether a graph is bipartite using BFS

I am solving a simple problem that checks whether a graph is two-colourable (bipartite graph). I am using BFS for this approach using C++ STL. I've replaced cin and ...
6
votes
2answers
79 views

Bitonic Tour algorithm

This is my implementation of Bitonic Tour (simplification of the Traveling Salesman Problem). Tests are not done very well, but it is not the point. I would be particularly interested in the comments ...
3
votes
0answers
36 views

Frequent subgraph mining program

I'm trying to make a programme that reads graphs from a .txt file, puts them in a vector, and finally puts the frequent closed graphs in another resulting file. ...
4
votes
3answers
214 views

Algorithm to group connected graphs

I am working on an algorithm, which should group connected Arcs. The situation is described via code examples below. I have Arcs: ...
5
votes
2answers
423 views

Dijkstra Algorithm

I have implemented Dijkstra's Algorithm in C, using arrays instead of any structs. Here is my implementation: ...
5
votes
1answer
66 views

Shortest paths from a single source (Dijkstra and Bellman-Ford)

I did not implement a priority queue in Dijkstra. I'm not sure if a trivial priority queue is the best choice, since, after each iteration, several elements change their value. Maybe it is better to ...
3
votes
2answers
68 views

Basic graph traversals

Below is an implementation of two graph traversals. Graph constructor creates a random graph with a fixed number of edges (fixed as a proportion of the maximum number of vertices, ...
8
votes
3answers
147 views

Dijkstra's algorithm without relaxation

I'm trying to implement Dijkstra's algorithm in Python, but the issue is that Python doesn't have support for key-based heaps out of the box, so applying relaxation step of the classical algorithm ...
2
votes
1answer
53 views

Graph, and a search that visits each edge exactly once in each direction

My assignment was to write a method that is capable of visiting each edge in a graph in each direction exactly once. With it, I included a basic Graph class to test it with. What I'd like a review ...
11
votes
2answers
383 views

Word Morph (changing one letter at a time)

Below is my implementation of Word Morph solver in Python. The challenge consists of transforming one word into another word by changing one letter at a time. Each word in the chain should be an ...
2
votes
1answer
80 views

Interview adjacency list graph problems in C++: proper graph implementation

I know this type of question has been asked before. However, my reason for asking it is gaining insight into what is expected in a 45 min interview when asked to implement graph algorithms. I have ...
2
votes
2answers
70 views

Parsing a text file of node data into Nodes and Edges

I'm a fairly new developer (well, engineer really, but currently working on a software project). In the Android project I'm working on, I read a node representation of a map into my app and interpret ...
5
votes
5answers
167 views

Enumeration of random trees

I'm interested in recursive generation of trees in Python. For my eventual application, it's important that the trees be represented as a list of nodes (rather than say a dictionary, or an edge list, ...
3
votes
1answer
101 views

Converting a CSV file to a social network graph for Pajek

The code will ask for a directory and will then read the CSV file and then generate a file in that directory describing a social network for Pajek. Does anyone know a way to load this CSV file to a ...
6
votes
1answer
72 views

Topological sort

The algorithm works in steps: Produce the graph in the form of an adjacency list e.g. this graph 0 - - 2 \ 1 -- 3 produces this adjacency list ...
3
votes
0answers
45 views

Golang A* Pathfinder

This is a generalized A* pathfinder in Go. I am new to the language and am eager for advice about best practices. In particular, I am not sure if the type assertion I make in ...
2
votes
1answer
45 views

Populate a networkx graph with tuples of varying lengths

I've got a list with tuples of variable length containing nodes, out of which I want to build a network: ...
10
votes
1answer
119 views

Detecting cycles in a directed graph without using mutable sets of nodes

I recently came across the classic algorithm for detecting cycles in a directed graph using recursive DFS. This implementation makes use of a stack to track nodes currently being visited and an extra ...
5
votes
1answer
77 views

Sort a scrambled itinerary (Google apac test problem)

This is my first time writing ruby - and I was mainly hoping to get some feedback and stylistic pointers. The algorithm is pretty straight-forward, since Google guarantees airports aren't repeated I ...
1
vote
2answers
60 views

Shortest path algorithm in 0-1-unoriented graph

I have an unoriented graph with n vertices and m edges, 1 <= n, m <= 100000. All edges ...
3
votes
1answer
100 views

Graph data structure implementation

I just started using C++, and I was wondering if my code fits the standards so far. Specifically, I was wondering if I did the addEdge, ...
8
votes
1answer
204 views

A rapidly-growing script that visualizes WiFi sniffing

Below is one of the versions of my wifimap script: ...
1
vote
1answer
78 views

Graphs processing in Scala

I've just started to learn Scala and decided to implement small graph library to train. Here is the basic version, that describes graph and nodes structure and also provides implementation of ...
1
vote
2answers
64 views

Data loading Hash Map

I'm trying to improve my code's performance, and I've found an area where the execution time is being significantly increased. I've had a look through the code but I can't see how I can improve it. ...
0
votes
1answer
55 views

Plotting a trigonometric function appears to be too slow

This calculates the mobility and it's derivative of one element. If I calculate with 1 value of w, it's very fast. ...
2
votes
1answer
312 views

Graph representation using adjacency list for BFS, DFS, and Karger's algorithm

I want to implement some graph algorithms for learning purposes (e.g BFS, DFS, Karger's min-cut algo) and before diving into them I want to make sure I have got the graph representation right (using ...
2
votes
2answers
158 views

Implementing Directed and Undirected Graph in C++

I am learning C++ and I decided to implement a Directed and UnDirected graph. (I haven't learned how to do inheritance yet, so they are distinct classes.) I have not handled any error cases (i.e. ...
3
votes
2answers
69 views

A* versus Bidirectional Dijkstra's algorithm

I have added bidirectional Dijkstra's algorithm into my pathfinding "framework", and I would like to make good use of C++ programming idioms, eliminate all possible memory leaks, otherwise improve ...
2
votes
1answer
66 views

Generic pathfinding framework in C++

I have this generic framework for finding (weighted) shortest paths. Also, the program demonstrates the performance of A* and Dijkstra's algorithms on a directed weighted graph. Both run in ...
3
votes
1answer
69 views

Yet another graph search

I noticed there were already countless implementations of graphsearch procedures on here, but there were a couple of features of my approach that I haven't seen in the others, plus I would greatly ...
1
vote
3answers
267 views

Adjacency matrix on undirected graph

Please review my Adjacency Matrix class based on this code. Since I use std::vector to create the matrix, I would like to store as many nodes as possible. Is it ...
1
vote
1answer
101 views

Creating an adjacency list in C++

I want to create an adjacency list based on data I get from a text file. Could I make this simpler? ...
3
votes
1answer
143 views

PHP implementation of “depth-first search” on the graph data structure

As I am a totally self-taught 'person writing code', I decided to learn algorithms with one online course that taught them using Java for demonstrative purposes. The first topic I covered is the graph ...
5
votes
1answer
122 views

Strongly connected components, component graph, semiconnected graph and new graph from SCCs

I have written a program in C to do the following: Read a matrix (in file format, first line you have the size, then next are the entries). This is done by the "input" function. Find the strongly ...