Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
0answers
39 views

Graph Search in C++17

Overview I am constructing a Graph with randomly generated nodes called Positions. The Graph has a width and a height and is represented using an adjacency list <...
5
votes
1answer
61 views

3-function program computing connected components of a point cloud given a distance matrix

I wrote this code in Haskell (instead of Python) for the educational benefit. Can anyone suggest ways to improve this code? I'm guessing that I'm using fromIntegral...
2
votes
0answers
24 views

Modelling a program with modules, symbols, and dependencies

My scenario is the following: I'm modelling a Program which has many Modules. Each Module has Symbols, some of which pointing at dependencies, which are other Modules. So a Module can be pointed to by ...
1
vote
2answers
80 views

Dijkstra's Algorithm C++

This is a basic implementation of Dijkstra's Shortest Path Algorithm for Graphs. I am looking for any kind of improvement. ...
2
votes
2answers
40 views

Graph library - graph interface

I am trying to write simple graph lib in C++, BFS, DFS etc.. I want to create class GraphI which will represent any graph and will include necessary methods so my ...
6
votes
1answer
118 views

Longest carbon chain

My Code measures the longest path, not allowing cycles. For the example input below, the longest chain would be 4 Please can you review my code? ...
3
votes
1answer
45 views

Find number of islands Leetcode

Here is the question: Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally ...
7
votes
1answer
106 views

Hackerrank: Computer Game (max-flow problem with integer factorization)

I am working on a coding challenge from the Hackerrank site. Given two equal-length arrays of integers, with values from 2 to 109, find the maximum number of times we can remove a pair (Ai, Bj) where ...
2
votes
1answer
31 views

Strongly connected component in graph

My goal is to calculate the length of each strongly connected component (SCC) I have an input that looks like this: ...
2
votes
1answer
96 views

Graph implementation using FIFO lists

I've made a little implementation of an undirected graph, using FIFO lists, for one of my homeworks. Never really knew how to write a proper FIFO data structure, so I would be glad to see some opinion ...
5
votes
1answer
54 views

Optimizing graph partitioning by connected components of generated subgraph

I'm trying to optimize a function in a process which is going to be run millions of times. The function is supposed to partition the vertices of a graph, which will be used to make a quotient graph. ...
9
votes
5answers
253 views

Sort a list of pairs representing an acyclic, partial automorphism

I have this sample data: let trips = [ { from: "DEN", to: "JFK" }, { from: "SEA", to: "DEN" }, { from: 'JFK', to: 'SEA' }, ]; ...
4
votes
1answer
86 views

C++ graph class

What can be done better? My future plans is to implement algorithms such as: DFS, BFS, Prims, Dijkstra, Kruskal, ... Faults I know of: Not implementing rule of five Vertex.h: ...
1
vote
1answer
119 views

Leetcode online Find the judge, graph with highest degree

Here is the problem. In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: The town ...
3
votes
0answers
28 views

Two solutions to leetcode 127.wordLadder

I am working on Word Ladder - LeetCode Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such ...
2
votes
1answer
40 views

Kahn's algorithms to arrange CouseSchedule

I wrote a solution to Course Schedule II - LeetCode There are a total of n courses you have to take, labeled from 0 to n-1. ...
2
votes
1answer
46 views

Maximize Path Value

I recently had to code an algorithm that will, for an input of: matrix of up to 5x5 size and a defined path length, find a path of this given length from the first top left matrix element (0, 0) to ...
4
votes
2answers
113 views

Heights of Cats

I have an assignment to solve this problem. However, I have exceeded the time limit required, can anyone suggest where to improve my code? Cats like to sit in high places. It is not uncommon to see ...
3
votes
2answers
116 views

Graph using adjacency list in Java [closed]

This is the main code. Here I'm joining vertices by edges. ...
4
votes
1answer
61 views

Swift Prim's algorithm

Lots of Prim's algorithm implementations seem long, and rely on a priority queue implementation. If I use an adjacency matrix I can then calculate the next item to take using functional programming ...
4
votes
0answers
42 views

graphtimer v2 - Utility to plot timings

GitHub repo (MIT) Clone the repo and replace the contents of example.py with the one at the bottom and you'll have everything setup. Explanation of the code A ...
1
vote
2answers
69 views

Determine whether a node is reachable

I am working on this HackerRank problem but running into time constraint issues. Basically, given two arrays, we need to determine if the ith element of the second array is reachable by the ith ...
5
votes
1answer
224 views

Graph puzzle resolver

I've solved test task for job vacancy. Need your feedback about my solution. Task The image below shows the puzzle in the solved state. The puzzle consists of 10 cells. Among the cells one is empty, ...
2
votes
1answer
53 views

Modelling Immerman–Szelepcsényi in Haskell

I am trying to model the proof of Immerman–Szelepcsényi Theorem with Haskell since it heavily uses non-determinism. An explanation of what the point of this is can be found here. ...
15
votes
3answers
327 views

Traversing an infinite graph using Dijkstra's algorithm to maximize cookie production speed

Imagine the following situation: It is the year 20XX. You are a prodigious baker, capable of baking cookies at an astonishing rate of 1 cookie per second. Your archnemesis, an equally excellent baker,...
5
votes
1answer
189 views

Dijkstra algorithm implementation in Swift

I've implemented Dijkstra's algorithm to find the minimum path between two nodes. ...
6
votes
1answer
75 views

Yet Another Dijkstra with real data and drawing

I've been assigned to use Dijkstra's algorithm in order to find the shortest path on real data, more specifically on Luxembourg's map. The map is an .xml file with the following structure. ...
0
votes
1answer
220 views

Get all node descendants in a tree

I have a CSV holding a "flat" table of a tree's edges (NOT binary, but a node cannot have two parents), ~1M edges: ...
3
votes
1answer
85 views

Implementation of generic Graph class and Dijkstras

I participate in competitive programming contests, and I found myself implementing and re-implementing graphs constantly. So I decided to create a reusable implementation of a Graph class, and ...
2
votes
2answers
188 views

Dijkstra - shortest Path implementation - STL

I have implemented Dijkstra algorithm to perform Shortest Path problem. Input: Adjacency List(Directed Graph): Description is like that {Source Node, {edge_1, .. , edge_N}} Cost Matrix (Same ...
2
votes
1answer
281 views

Vertex Cover Problem Greedy Solution [closed]

As far as I understood this problem, it is a subset of vertices of Graph G, such that every edge has at least one endpoint in the subset. This problem is considered to be NP Complete. However I think ...
1
vote
1answer
43 views

Vertical Bar Graph Generator

I have created a python program that prints a vertical bar graph made from fields and values inputted by the user. It works by first creating a horizontal bar graph and then going through each layer ...
1
vote
0answers
51 views

Graph implementation from adjacency list

I've implemented a graph for a course and i'd like to know what i could improve. The graph is created from a adjacency list from a file with the following format per row: ...
0
votes
1answer
59 views

Graph Implementation in Java using Set and Map

There is a Graph implementation. I'm using Set to store unique Edges and Map to store Vertices and their associated edges. Assume Vertex and Edge class has been defined somewhere else implementing ...
3
votes
1answer
111 views

Map coloring with MRV and Degree heuristics in Python

I am relatively new to Python. I wrote this solution to the well known map coloring problem and also implemented the MRV and Degree heuristics. Here, I am considering the map of Australia - ...
2
votes
0answers
73 views

Project Euler #81 in Haskell: minimal path sum through a matrix

I just completed Project Euler Problem 81 in Haskell: In the 5 by 5 matrix below, ...
2
votes
2answers
450 views

Find all shortest paths between 2 nodes in a directed, unweighted, SQL graph

I want to find all shortest paths between a pair of vertices in a unweighted graph i.e all paths that have the same length as the shortest. The edges of the graph are stored in a SQL database. The ...
4
votes
1answer
129 views

Performing unit conversions using intermediate conversions

Challenge: Two input files are given The first contains |N| ratios in the form of two labels and a ratio: USD, GBP, 0.69 Meter, Yard, 1.09 YEN, EUR, 0.0077 GBP, YEN, 167.75 ...
1
vote
0answers
117 views

Bidirectional iterative deepening pathfinding algorithm in Java

Introduction I have this iterative deepening search algorithm. The main "research" attempt was to find out a bidirectional version of that search, and it turned out to be superior compared to two ...
1
vote
1answer
324 views

Graph implementation in C++ using adjacency list

there is my final code for implementing a Graph in C++ using adjacency list and Object-oriented. I got some help from StackOverflow and it was really helpful, but now I would ask about some advice for ...
1
vote
2answers
55 views

Find CISC prerequisites

Below I have some code written in prolog as a brief example. The goal of the program is to take a Computer and Information Science (CISC) course number and return any CISC prerequisites (prereqs). I ...
4
votes
2answers
1k views

Graph implementation in c++ using adjacency matrix

Here is my code for implementing Graph using adjacency matrix. The code should be Object-oriented and there is a method isPath() checking if there is a connection ...
7
votes
1answer
219 views

Generating maze for complicated Hunt the Wumpus game

In my previous post I made rather dull (and, as it turns out, bluntly wrong) attempt at solving the problem: Generate a maze with \$N\$ nodes, \$K<N\$ of which are border nodes. Each border must ...
3
votes
2answers
759 views

Word ladders program in Python

Background information: Given two different strings of equal length, the spacing between them is the number of other strings you would need to connect them on a word ladder. Alternately, this is 1 ...
0
votes
0answers
143 views

Functional, recursive algorithm for flattening a tree

My goals for the algorithm were to use recursion, to avoid mutation, and to decouple the tree walking from the action that we take on each node. My sense is that the result uses mode code is ...
4
votes
1answer
56 views

Find the longest connect cells region per color

I have been studying graphs/BFS/DFS. working on wrapping my head around the following problem Given a grid [m,n] where each cell has a value denotes a color, find the longest connected region that ...
1
vote
0answers
210 views

Correctness of iterative DFS for cycle detection

I'm attempting the Graph Algorithms section in CLRS right now. Here's an iterative DFS using a stack called nodes. ...
1
vote
2answers
173 views

Graph library including minimum spanning tree using Kruskal's Algorithm

I've only ever made small programs. So, I've tried to make something large but easily reusable/extendable. Posted below are the beginnings of a graph library I've written up. One particular point I'd ...
7
votes
2answers
281 views

Factory for constructing directed graphs in C++

I want to implement a directed graph which has 3 main kind of edges: self referencing edges non directional edges between two nodes directional edges between two nodes Also I want to be able to do ...
1
vote
0answers
54 views

Using HashMaps to track parent and rank of graph nodes

I often find myself in the following position: I have created a class in some file, and would like to add a new data member to that class without changing the original class definition. Now, you ...