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.

4
votes
0answers
31 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
54 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 ...
0
votes
0answers
13 views

Time limit exceeded for a Prims implementation

Here is a question from HackerEarth, that has the basic aim of: In a connected component, find the Maximal spanning tree. Delete the remaining edges. All the components can be connected to ...
1
vote
1answer
56 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
169 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
69 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
67 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
36 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
57 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
60 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
32 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
70 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
102 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
76 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
101 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
80 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
33 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
55 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
242 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
100 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
90 views

Building a graph using dictionary

I have an input text file which contains distance between 2 cities shown below ...
1
vote
2answers
111 views

Cycle in Directed graph to vector

I created a class of a directed graph and a method for finding if graph has an Euler cycle and updating a vector accordingly.Is there any optimization or a nicer way to do this. ...
4
votes
0answers
58 views

Add an edge to a graph to minimize the average shortest path length

This program is used to find the nodes in a grid network, between which, if an edge is added, the average shortest path length of the entire grid reduces by the most. "Average shortest path length" ...
3
votes
2answers
129 views

Greedy preference-matching algorithm

The problem that this is based on is something like the following: A matchmaker is working with six clients: John, Joe, Charlie, Jill, Leslie, and Katie. John is compatible with Jill and Leslie, ...
7
votes
2answers
257 views

Trace route based on Cisco routing table text output

I created a script for path search across network topology based on uploaded routing tables in text format. The final purpose is to be able to get all available paths to given subnet/host from each ...
11
votes
2answers
753 views

Milking order compatible with maximum number of observations

I'm using some old USA Computing Olympiad (USACO) problems to help teach me. This is the "Milking order" problem: Farmer John has \$N\$ cows (\$1≤N≤10^5\$), numbered \$1…N\$. He has made \$M\$ ...
0
votes
1answer
67 views

Balanced tree in C#

Given the adjacency list to represent a tree from the root (node 0) to the leaves, I want to write a function that takes this adjacency list as a parameter and return whether the tree is balanced. ...
3
votes
1answer
63 views

Draw common tangents to two circles interactively in MATLAB

Requirement After a user draws two circles with their mouse successively, the program should draw all common tangents, if any, to them. Here is my implementation ...
1
vote
2answers
89 views

Finding the size of the largest connected component in a graph

Given this question, which simply can be explained as follows: Given the number of nodes and the number of edges in a graph, find the size of the largest connected component of the graph. If this ...
2
votes
1answer
276 views

Graph Implementation in Java using adjacency list - v2

Updated version from Graph Implementation in Java using adjacency list ...
1
vote
1answer
280 views

Graph Implementation in Java using adjacency list

I am building a Graph class to learn and eventually plan to add Dijkstra's algorithm to this implementation. What do you think of the overall approach? Any feedback on how to improve this? Vertex....
2
votes
0answers
83 views

Max flow Ford-Fulkerson using DFS augmented path retrieval

I have written a naive max flow with DFS, could anyone review my below code. What can be done to improve the code and what are the worst cases where this won’t work acceptably? ...
0
votes
1answer
255 views

Depth First Search of graph in Python

Task: Do DFS traversal from a given given graph and print output. Is this code the correct implementation of DFS traversal in Graph? ...
2
votes
1answer
55 views

Djikstra implementation for large graphs

I am implementing the Djikstra algorithm for a large graph (40k nodes, 100k arcs). For shorter paths the searchtime is under a second for larger ones (from one end to the other) it take quite some ...
2
votes
1answer
106 views

Implement a graph in Python

Question : Build a graph in python, given its edge representation. ...
3
votes
0answers
62 views

Number of subGraphs with given vertice and degree

Demo: There are three questions: How many subgraphs whose Num(vertices) <= 5 and all vertices have two degrees? How many subgraphs whose Num(vertices) == 4 and all vertices have 3 degrees? If ...
2
votes
1answer
155 views

Player Marking , Optimal Marking Using Graph

I was asked this problem for a challenge, and I decided to share my solution here to review the code: Here is the problem statement: For this challenge, we are going to cover some graph problems. We ...
3
votes
1answer
650 views

Generic Graph using Adjacency matrix - Java

The main purpose of representing Graph using adjacency matrix method is, to check the vertex and its neighbor's existence in constant time proportional to \$\mathcal{O}(n)\$. In the various ...
0
votes
1answer
163 views

Java agent-based model

I've been working on an agent-based model as part of my PhD and I've hit a roadblock. I started learning Java by doing this project and I definitely started to run before I could walk. The problem is ...
1
vote
1answer
229 views

Graph Representation using smart pointers. Kosaraju's algorithm implementation

Coming from a Java background, and being fairly new to C++ as well as code review, I am trying to get accustomed to C++11/14 concepts. I have been reading Modern Effective C++ by Scott Meyers to ...
4
votes
1answer
88 views

Levenshtein Distance of transitively similar words

The code's purpose is this: Two words are friends if they have a Levenshtein distance of 1. That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social ...
7
votes
1answer
217 views

Cheapest flights with at most k stops

This is the Cheapest Flights Within K Stops problem from leetcode.com: There are \$n\$ cities connected by \$m\$ flights. Each fight starts from city \$u\$ and arrives at \$v\$ with a price \$w\$. ...
2
votes
1answer
178 views

Calculating Euclidean distance

Code: I have a list of ~15,000 Euclidean points which represent a connected graph. I'm trying to solve/approximate the traveling salesman problem with this graph. Problem: Finding neighbors, i.e. ...
4
votes
1answer
45 views

Generate another random path through a complete graph

What this does is generate a random path of cities to later calculate the length of the newly generated tour of cities, the TSP. I am trying to figure out if there is a more efficient way to write ...
1
vote
0answers
61 views

Adjacency List C++14

I would like to create a graph library for fun and run various searching algorithms on it. For now, all I have is an adjacency list that I threw together. The adjacency list currently only supports ...
0
votes
0answers
107 views

Kruskal Algorithm in C++

After studying from CLSR, I have implemented this algorithm. It prints the minimum cost. Help me to improve it. ...
2
votes
0answers
75 views

Computing most-cost effective loans in financial graphs using Java

Problem statement We are given a directed graph \$G = (V, A)\$, where \$V\$ is the set of actors and \$A \subseteq V^2\$ is the set of directed arcs. Existence of an arc \$(u, v) \in A\$ is ...
0
votes
1answer
279 views

Dijkstra's Algorithm implementation in C++

After applying suggestions from here about Bellman Ford Algorithm. Help me to improve this program. ...
4
votes
2answers
2k views

Bellman Ford algorithm implementation

Please review my code and help me to improve it. ...