Stack Exchange Network

Stack Exchange network consists of 174 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
1answer
75 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, ...
1
vote
1answer
43 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. ...
12
votes
2answers
216 views
+100

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,...
4
votes
1answer
145 views

Dijkstra algorithm implementation in Swift

I've implemented Dijkstra's algorithm to find the minimum path between two nodes. ...
6
votes
1answer
67 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
50 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
50 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
75 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
66 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
38 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
29 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
44 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
61 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
60 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
211 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
102 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
69 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
145 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 ...
0
votes
1answer
31 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
184 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
191 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
332 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
52 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
50 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
84 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
125 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
251 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
50 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 ...
4
votes
1answer
84 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 ...
4
votes
0answers
34 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 ...
3
votes
1answer
843 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 ...
1
vote
1answer
95 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 ...
10
votes
1answer
192 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 ...
5
votes
1answer
88 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)? ...
4
votes
1answer
155 views

Dijkstra's algorithm in Rust

I'd love to get feedback on my first go at Dijkstra's algorithm in Rust: ...
1
vote
1answer
186 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 ...
4
votes
1answer
62 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,...
3
votes
2answers
157 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 ...
1
vote
1answer
38 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 ...
1
vote
0answers
83 views

Finding center of graph/tree

Given graph/network of nodes without any loops/circuits. I'm trying to find the center: the node from which I can reach all other nodes the fastest. Imagine if I want to spread the word about ...
6
votes
1answer
114 views

Finding intersting path in a graph

There is a question in a contest but it doesn't have any answer. I solve it but I get time limit for most of test case. Is it possible to improve my code or give a better approach? Question There is ...
3
votes
1answer
85 views

Efficient Road Network

Intro I've decided to learn haskell, because I've always enjoyed the functional aspect of Python and want to explore other languages that use this concept. I'm still stumbling in the dark most of the ...
8
votes
2answers
108 views

Maximize a traveling employee's vacation over k weeks

I have following problem statement A lazy employee works at a multi-national corporation with N offices spread across the globe. They want to work as few days over k weeks as possible. ...
4
votes
1answer
146 views

Python: Dijkstra's Algorithm

In this code, I focused more on code readability rather than algorithmic complexity. I didn't really care about the code in the main function because it was just ...
3
votes
1answer
47 views

A-Star Search with 3D Universe

I am attempting to write up a program in Python that will find the shortest path between two nodes in 3D space. The actual domain is the EVE-Online Universe, which is composed of systems connected by ...
2
votes
0answers
62 views

DFS logic to traverse a graph

I tried to literally convert recursive algorithm taught here to iterative, by simulating the recursive stack exactly as much as possible. I have tested my code and it passed all test cases. Please ...
4
votes
1answer
2k views

Searching a maze using DFS and BFS in Python 3

I solved the problem posted from Make School Trees and Maze article, which asks me to searching a maze using DFS and BFS in Python. Here's the final output from PyGame: I would like to ask for code ...
0
votes
1answer
160 views

Cracking the Coding Interview - 4.1 Graph Traversal

I'm working through the classic Cracking the Coding Interview book. I'm trying to solve the following graph problem: 4.1) Route Between Nodes: Given a directed graph, design an algorithm to find ...
0
votes
2answers
95 views

Building a graph using dictionary

I have an input text file which contains distance between 2 cities shown below ...