A graph can refer to a graphic (such as a chart or diagram) showing or displaying the relationship between two or more variables used, for instance, in visualizing scientific data.
0
votes
0answers
16 views
Clone an undirected graph
I'm looking for code-review, optimization and best practices. Also verifying complexity to be O(E) time and O(V+E) space complexity.
final class NodeClone<T> {
private final T item;
...
3
votes
0answers
38 views
Ford-Fulkerson algorithm
Solved the ford-fulkerson algorithm, which is too vast to explain it comprehensively here. Check Wikipedia for Ford-Fulkerson and Princeton lecture on Ford-Fulkerson.
Looking for code review, ...
10
votes
3answers
353 views
Find all paths from source to destination
Given a directed connected graphs, find all paths from source to destination.
Looking for code review, optimizations and best practices. Also need help figuring out complexity, which in my best ...
2
votes
0answers
13 views
Completing a Graph in Scheme
For the record, this is part of a homework assignment, but I have already implemented a solution. I am simply wondering if there is a better way to do it.
Background: I am asked to write a procedure, ...
11
votes
1answer
92 views
Topological sort in Java
I am learning algorithms in graphs. I have implemented topological sort using Java. Kindly review my code and provide me with feedback.
import java.util.LinkedList;
import java.util.Queue;
import ...
0
votes
0answers
27 views
Iterative DFS algorithm
I've written an iterative version for DFS. For a quick overview of the benchmark results for a complete graph:
So it looks like it behaves within the boundaries of the theoretical complexity.
...
5
votes
2answers
128 views
Map color problem: Optimize using a heap?
I've written some python code to solve the map coloring problem. In my code, I represent the problem using Territory and MapColor objects:
class Territory:
def __init__(self, name, neighbors, ...
6
votes
1answer
78 views
Dijkstra-like routing algorithm
I've got the following code to find the shortest path between two nodes using almost-Dijkstra's-algorithm which was written for an exercise, and I'm looking for things to improve my general Scala ...
4
votes
1answer
48 views
Maximize the number of nodes that could be reachable in a graph
Description of my code:
I am trying to maximize the number of nodes that could be reachable in a graph. Please do not consider my main algorithm, I want it to be like that. The only parts that I need ...
4
votes
1answer
81 views
Modified BFS code optimizations
I need some help reviewing this code in terms of making as fast as possible. This is a modified version of BFS that does quite a bit of processing on the side.
Use case:
I have a large graph ...
1
vote
0answers
24 views
Actionscript Graph data structure implementation
So, I am not sure if I should have Vertex extend Point, because the equals() and compareTo() functions are already parameterized with Point. I guess I don't really need compare to...
Does this ...
2
votes
1answer
155 views
Automate a dependency graph with parallel programming [closed]
I found a C/Linux exercise in a book, and I propose a code as a solution, please feel free to correct it.
Here is the exercise :
Taking into consideration the following dependency graph, which ...
3
votes
0answers
112 views
Dijkstra's and Prim's algorithms: correctness/efficiency
This is in preparation for a competition that only allows C++03.
// Neighbor index plus weight of edge connecting this vertex with neighbor
struct NeighborWeight
{
Index neighbor;
Distance ...
5
votes
1answer
136 views
Code to construct a complete graph
I have tried to design a class for a complete graph.
Needless to say, disadvantages of my current solution are very visible:
dependent inputs have led to verification headaches.
In this code we ...
5
votes
1answer
333 views
A* search algorithm
A* search algorithm. Looking for reviews on optimization, accuracy and best practices.
/**
* NodeData stores all information of the node needed by the AStar algorithm.
* This information includes ...
7
votes
2answers
368 views
Check if directed graph contains a cycle
I have solved the question, and in turn felt the need to get it reviewed. Any suggestions for clean up and optimization would help. Also please verify my complexity: Complexity: O (V + E). ...
2
votes
0answers
130 views
STL and Dijkstra's algorithm optimization
This is the problem and my solution to this is:
#include "iostream"
#include "stdio.h"
#include "algorithm"
#include "math.h"
#include "string.h"
#include "time.h"
#include "stdlib.h"
#include ...
5
votes
1answer
1k views
Prims algorithm implementation
Review this code regarding optimization, cleanup, and best practices.
final class EdgePrims<T> {
private final T source, target;
private final int distance;
public EdgePrims(T ...
5
votes
2answers
1k views
Learning to code a graph
This is my first attempt at putting the conceptual knowledge I've gained about graphs into code. When searching for examples they all seem overly complicated, and searching for a tutorial or ...
4
votes
2answers
85 views
How to improve this algorithm for building a graphs closures
We have a large directed acyclic graph and a requirement to filter it by allowing a user to select certain nodes and then we remove all nodes that are not selected nodes, ancestors of those nodes, or ...
0
votes
1answer
94 views
Applying Dijkastra's algorithm on a graph of five nodes
Last week I posted a piece of code to apply Dijkastra algorithm to calculate the shortest path between to nodes in a graph. Now, I've made some improvements, but I am still having difficulties.
I ...
0
votes
1answer
1k views
Implementation of Prim's minimum spanning tree
Feel free to tell about every possible issue (style, errors, inffective solution etc.) you found. Here is the main part of what I want to be reviewed, through there is some related code on GitHub.
...
2
votes
0answers
94 views
Evaluating code for a graph [closed]
This is relatively long code. Please take a look at this code if you are still willing to do so. I will appreciate your feedback.
I have spent two days trying to come up with code to represent a ...
1
vote
1answer
173 views
DFS algorithm with generators
Background:
I was working on a project were I needed to write some rules for text-processing. After working on this project for a couple of days and implementing some rules, I realized I needed to ...
3
votes
1answer
90 views
Review/rate my new graph class
I have written a PHP class called "graph". It is a class that performs RESTful-like commands to a MySQL database. I have posted the GitHub repo.
Here is the code as well:
config.php
<?php
...
5
votes
2answers
444 views
Implementation of Dijkstra's algorithm
Please pick my code apart and give me some feedback on how I could make it better or more simple.
final class Edge {
private final Node node1, node2;
private final int distance;
public ...
1
vote
1answer
151 views
2003 Canadian Computing Competition, Stage 1 ; Why Is My Solution Invalid?
I am doing old versions of the Canadian Computing Competition, on a website where I can run my solution against some test cases they have. I am failing one of their test cases, and cannot figure out ...
6
votes
1answer
204 views
Shortest Path in a Unit Cost DAG BFS in Hadoop
Just got done implementing a shortest path algo of a unit cost DAG BFS in Hadoop and wanting to get anyone's opinion on how I could have done it better. The main issue I see is that I lose the ...
3
votes
1answer
413 views
Do I need to delete a vector?
I want to make a graph from input from a text file in the format:
vertex1 vertex2 cost time
where vertex1 and vertex2 are strings that form an edge and cost and time are the properties of that ...
3
votes
1answer
222 views
Please review my Digraph Code in Java
can people please review my digraph code? This is used to create a directed graph of type T. The directed graph has edges and vertices with values but is directional such that nodes can loop unto ...
4
votes
1answer
358 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.
type Vertex=Int
...
1
vote
1answer
388 views
python optimization, 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 stopped running I don't know if it will ...
3
votes
2answers
605 views
Can someone help me optimize my DFS implementation in Python?
def dfs(graph, node):
"""Run DFS through the graph from the starting
node and return the nodes in order of finishing time.
"""
stack = [[node, True]]
while True in [x[1] for x in stack]:
i = 0
...
3
votes
1answer
115 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, ...
1
vote
1answer
722 views
Strongly Connected Component for a graph C++
I implemented a strongly connected graph code in C++
matrix_graph.h
#pragma once
#include "stdafx.h"
class matrix_graph
{
private:
int** v;
int vertexes;
public:
matrix_graph(int**, ...
2
votes
1answer
150 views
DFS/BFS implementation Cormen's pseudo code
I like this site and thought if putting this dfs/bfs C++ code for Cormen pseudo code.....please give your comments
#include "iostream"
#include "vector"
#include "list"
enum color{
WHITE,
...
7
votes
1answer
379 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 ...
2
votes
1answer
172 views
Is this implementation of Kruskal's algorithm maintainable and efficient?
Update
I've posted some updated code and included the definition of Vertex and Edge to try to answer as many questions as I could. To summarize what's changed:
I've followed the advice here to ...
2
votes
1answer
78 views
Is this code for getting the dependency tree of a file correct?
function dep_tree(graph,node,prev_deps){
return uniq(flatten(graph[node].map(function(child_node){
if (contains(prev_deps,child_node))
throw "Circular reference between ...
0
votes
2answers
233 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 ...
3
votes
1answer
486 views
My first python graph traversal review
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
95 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
276 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.
from Tkinter import *
'''
This program tries to compute the longest path (largest number of
...
1
vote
2answers
129 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
#include <algorithm>
#include ...
3
votes
2answers
1k 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
#include <vector>
#include <list>
using std::vector;
using ...
4
votes
1answer
838 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 ...
6
votes
3answers
967 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 ...
5
votes
4answers
414 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 ...
1
vote
0answers
413 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.
neighbours[g_Graph, v_] :=
Module[
{vl = VertexList[g],
pos},
...
