# 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.

604 questions
Filter by
Sorted by
Tagged with
227 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 ...
44 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 ...
44 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. ...
62 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 ...
143 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 ...
525 views

### Graph using adjacency list in Java [closed]

This is the main code. Here I'm joining vertices by edges. ...
74 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 ...
70 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 ...
114 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 ...
254 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, ...
61 views

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. ...
372 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,...
286 views

### Dijkstra algorithm implementation in Swift

I've implemented Dijkstra's algorithm to find the minimum path between two nodes. ...
89 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. ...
861 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: ...
207 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 ...
260 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 ...
509 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 ...
50 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 ...
65 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: ...
186 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 ...
185 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 - ...
83 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, ...
628 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 ...
154 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 ...
153 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 ...
511 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 ...
71 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 ...
2k 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 ...
256 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 ...
2k 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 ...
334 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 ...
59 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 ...
412 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. ...
240 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 ...
303 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 ...
55 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 ...
114 views

### Generate multi dimensional maze with borders and fixed degree on each node type

IMPORTANT: giving too big combination of node count and edge/neighbor count can overflow your RAM and swap file very quickly, thus I recommend staying below 500 on node count and below 50 on neighbor ...
38 views

### Modular graph searcher

some words in forehand: Unfortunately this post is very long, thus I decided to put the whole and compilable code into an online compiler. The link is at the end of this post. In the last few days I ...
4k views

### Greedy Graph Coloring in Python

Graph Coloring Algorithm (Greedy/ Welsh Powell) I am trying to learn graphs, and I couldn't find a Python implementation of the Welsh Powell algorithm online, so I tried to write my own. Here are the ...
286 views

### Implementing a faster inbound neighbour similarity in Networkx

Given a directed graph G of 20+ million edges and approximately 2 million unique nodes, can this function/process be made faster on a dataset of 40k edges? The current speed is at ~1.8 seconds per ...
254 views

### Displaying programming languages on a timeline

I did the following two exercises in Programming: Principles and Practice Using C++ (2nd Edition), by Stroustrup, which build upon each other: From Chapter 22 (Ideals and History), Write a ...
149 views

### Latitude/Longitude graph optimised A* Algorithm

Can anyone point me in the direction of a C# or pseudocode implementation of A* optimised for relatively sparsely connected graphs (average < 3 edges per node)? ...
652 views

### Dijkstra's algorithm in Rust

I'd love to get feedback on my first go at Dijkstra's algorithm in Rust: ...
388 views

### Adjacency list graph in Java

I am reading a text, that from a higher level explained adjacency list implementation of a graph. I have now tried to implement this as simply as I could. I did not see any reason to have an actual ...
106 views

### Making a graph of the import structure of a program

When I read other people's code, it's sometimes difficult to understand the import structure. I thought making a graph of the import structure of a given python program would be a fun programming task,...
320 views

### DFS for Graph search with generic data types

This question is a follow up to this. I am learning Graph data structure and have implemented DFS and BFS in a way that it can handle data types other than int. These function try to search an end or ...
58 views

### C++ - Graph implementation for data types other than int

I am learning graphs and most of the implementations that I see are meant for int. So, I decided to code an example that can take other data types such as ...