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.

Filter by
Sorted by
Tagged with
9
votes
1answer
11k views

BFS and DFS in Scala

I would love it if someone could give me some suggestions for these 2 graph search functions. I am new to scala and would love to get some insight into making these more idiomatic. ...
1
vote
1answer
2k views

Finding strongly connected components of directed graph, kosaraju

Given a graph in [[sourcevertex,targetvertex],...] format with all the directed edges of the graph I am trying to optimize the code here because it still hasn't ...
4
votes
2answers
5k views
5
votes
1answer
1k views

Complete graph traversal algorithm in Prolog

Given a table, I want to explore all possible transition between the elements in the table. ex: for a table with size 3 [0,1,2], the output of the algorithm should be 0->1, 1->0, 0->2, 2->1, 1->2, 2->...
2
votes
1answer
3k views

Strongly-connected component for a graph

I implemented a strongly connected graph code in C++. matrix_graph.h ...
5
votes
1answer
12k views

DFS/BFS implementation of Cormen's pseudo code

This is DFS/BFS C++ code for Cormen pseudo code. Please comment on this. ...
4
votes
1answer
18k views

Creating an adjacency list

I've created this adjacency list, but I don't like the design of the graph. The issue is that there is one pointer in the node to its adjacency list and there is a pointer in an ...
7
votes
1answer
1k views

Find almost-shortest path more efficiently

I'm trying to solve a SPOJ problem, which is code SAMER08A at this link. The problem is that when I ran my code in my IDE with all the examples given in the problem, the code works perfectly. But ...
1
vote
1answer
124 views

Small graph API to track vertices and edges added to graph

I'm working on my Scala chops and implemented a small graph API to track vertices and edges added to graph. I have basic GraphLike Trait, and have an Undirected Graph class ( ...
7
votes
2answers
783 views

Simplifying finding neighbors in graph

...
2
votes
1answer
512 views

Is this implementation of Kruskal's algorithm maintainable and efficient?

I'm implementing Kruskal's algorithm in C++11 and would like feedback on style and performance on my graph data structure and algorithm for educational purposes (for production code, I'd use a pre-...
3
votes
3answers
3k views

Finding the closest node

I have a function that I need to optimize: ...
2
votes
1answer
310 views

Is this code for getting the dependency tree of a file correct?

...
1
vote
2answers
467 views

Improving readability of non-recursive depth first search function in Lisp

As a free-time activity in order to learn some Lisp I had to implement depth first directed graph search. Due to large graph size (800K nodes, 5M arcs) recursion-based approach I could devise didn't ...
6
votes
1answer
1k views

My first graph traversal code

I'm trying to solve a graph traversal problem I found, and was wondering how I could improve my implementation. Currently it seems a little convoluted and long. The problem is as follows: I have a ...
2
votes
1answer
764 views

BFS implementation to find connected components taking too long

This is in continuation to a question I asked here. Given the total number of nodes (employees) and the adjacency list (friendship amongst employees), I need to find all the connected components. <...
3
votes
1answer
2k views

Evaluating longest path

Here is a program which keeps track of the longest path in a graph. I think it can be written much better. ...
1
vote
1answer
3k views

Generating adjacency matrix on random cout of graphs with output the matrix

I've developed program, which may work with graphs and its edges (connections between vertices): http://ideone.com/FDCtT0 ...
2
votes
2answers
10k views

Undirected, connected and weighted graph implementation

I was thinking in a way of implementing a graph in such that would let find a minimum spanning tree. Graph.h ...
4
votes
1answer
351 views

Finding and returning a loopy path in a directed graph

I wrote a function in Scala to find out and return a loopy path in a directed graph. One of the arguments is a graph presented in an adjacent list, and the other is a start node. It returns a pair ...
1
vote
2answers
271 views

unw_graph class (unweighted graph)

Here is my new STL-like implementation of an unweighted graph. Could you please tell me what member functions I should include in my library? unweighted_graph.hpp ...
8
votes
2answers
6k views

D3 visualization of a Facebook friend graph

I've been learning Python for about a year and now I'm trying to improve my JavaScript. I wrote this simple d3 visualization that shows your Facebook friends as a force-directed graph. Here's a live ...
5
votes
2answers
4k views

STL-like graph implementation

I have implemented an STL-like graph class. Could someone review it and tell me things that I could add to it? File graph.hpp ...
8
votes
2answers
11k views

Implementation of Kosaraju's algorithm for strongly connected components

To learn and practice coding in C++, I wrote an implementation of Kosaraju's two-pass algorithm for computing the strongly connected components in a directed graph, using depth-first search. This was ...
8
votes
3answers
1k views

Reorder a list of courses, given their prerequisites

I recently graduated from college and applied for a position with a company. I was sent a coding exercise as part of the process. After completing the exercise and submitting it I was told that the ...
4
votes
2answers
22k views

STL graph implementation

I'm looking for a code review on the following C++/STL graph implementation: ...
1
vote
1answer
125 views

“Causes” Puzzle solution (network of words with Levenshtein distance 1)

The "Causes" puzzle is to recursively find, starting with the word "causes", the number of words that can be formed by substituting one letter. ...
12
votes
1answer
3k views

Variadic function with restricted types

I am designing a class which (among other things) acts as a vertex in an undirected graph. ...
7
votes
2answers
334 views

“Ringing in the New Year (2011→ 2012)” puzzle

I am trying to solve the puzzle RINGING IN THE NEW YEAR. Start at 2011. By moving through the maze and doing any arithmetic operations you encounter, exit the maze with a result of 2012. You may ...
10
votes
1answer
463 views

Graph generator for undirected graphs

I am still pretty new to Haskell and am working on a graph generator for undirected unlabeled graphs containing loops and I have a bottleneck in the following functions. So far, I have not given any ...
4
votes
1answer
1k views

Javascript graph skeleton implementation

I started implementing a graph drawing application in javascript and < canvas > element, and i just wanted to hear your thought on the progress so far. I'm very open to suggestions and i'm very ...
2
votes
1answer
1k views

BFT/DFT/Topological graph implementation

I am trying to learn graphs and implement in code. Can you please review my code and give me feedback? Source code ...
6
votes
3answers
1k views

Print pair representing objects from sequence of nonnegative integer pairs

There are some things I am not sure of from a professional standpoint about the "correct" way to write C++ code. I have been looking through source code produced by various opensource projects, as ...
6
votes
4answers
590 views

Compute random triplets of float pairs and average area of generated triangles

I am trying to get in a lot of practice for interviews so I am trying to write as much code as possible, and getting feed back from excellent programmers like "you". Can I get some general feed back ...
5
votes
2answers
282 views

Social network evolution

I am writing a piece of code which models the evolution of a social network. The idea is that each person is assigned to a node and relationships between people (edges on the network) are given a ...
3
votes
1answer
1k views

Fastest way to find all neighbours of a vertex in a graph

I'm looking for the fastest way to find all neighbours of a vertex in an undirected Graph. Please improve on the code if possible. ...
5
votes
1answer
2k views

Coding adjacency list representing graph

I want to write some basic code on graph like DFS, BFS but before that I am coding graph representation in adjacency list, and some basic functions like ...
9
votes
3answers
415 views

Function, taking up to 27 parameters, that checks for the existence of a path in a graph

There's got to be a better way than this that preserves the logic while sparing me the multitude of lines: ...