Tag Info

46

1. Review There's no docstring. What does the function do? What arguments should I pass? What does it return? This is the kind of function that would make an ideal candidate for a doctest or two. The function does not actually determine if a graph contains a cycle. It determines if the graph contains a cycle starting at a given vertex. To detect a cycle, it ...

42

Data Structure Your terminology is a bit off. Trees have roots and children. Arbitrary graphs, on the other hand… I think "origin" and "neighbors" would be more appropriate. Visited flag: Storing the visited/unvisited flag in the Node hurts flexibility. Once you perform a dfs() or bfs(), that graph is "ruined". You won't be able to reset all nodes to ...

35

sets perform containing checks (w in visited) $O(1)$ rather than $O(n)$ for lists. collections.deque are better than lists for poping elements at the front (popleft). you should put your example code under an if __name__ == '__main__' clause. w as a variable name does not convey meaning, you should try to come up with something more explicit. import ...

21

This is quite good and professional-looking code. There are many small aspects which I really like: Using Collections.unmodifiableMap instead of a shallow copy is brilliant. The use of a generic nodeId is clever and makes for elegant code. There are input checks in all public methods (well, there are some exceptions: only the AStar and NodeData constructors,...

18

OK, so I'm going to start with your DFS method. You're right - you should be able to do it without those vars in the outer function. You should be able to work out why - after all, you have vals in the outer layer of your BFS method. Why? Because your BFS uses a recursive helper function, so the vals are only used once (and could be discarded). So your ...

18

1. Review Python's style guide recommends 4 spaces for each level of indentation, and keeping lines to a maximum of 79 characters. It's not compulsory to follow this style, but it makes it easier for other Python programmers to read the code. For example, if you had stuck to 79 characters per line, we wouldn't have to scroll the code horizontally to read it ...

17

is this a graph? Yes Am I missing anything? In terms of a graph: No. You have chosen to make your edges uni-directional (thus two edges are required to mark routes between cities). Not an issue in itself but you could have helper functions that create two edges automatically. In terms of good coding: Yes You have completely missed out encapsulation. I ...

17

This is beautiful, easy to read, and well-documented code. It is a joy reading this code, and there is very little to improve on the Java side. The greatest weakness that shows in this code is not your skill with Java (which surpasses mine by far), but your knowledge of the English language. In the addEdge JavaDoc you talk about arcs not edges. The ...

16

Here are two ways you could represent a graph with weighted edges in Python: Represent a graph as a mapping from a node $n$ to a mapping from neighbouring node $m$ to the weight $w$ of the edge from $n$ to $m$: graph = { 0: {2: 4, 4: 60, 3: 23}, 1: {}, 2: {3: 4}, 3: {1: 10}, 4: {2: 15}, } Represent a graph as a pair of ...

14

1. Introduction Your goal (if I understand correctly, of generating all the execution paths in a state transition graph for a Java thread and then using those execution paths to test the code) seems unrealistic to me. Even in an acyclic graph (or with the condition that you must not revisit a state) there may be exponentially many paths. In a graph with ...

14

(I'm assuming the code will be changed according to the comments. Otherwise it won't run with the given example graph) Performance issues: Comparing lists as in while X != V involves looping through the lists. Also, the condition is not very useful because the lists only become equal in the special case when the algorithm visits the vertices in numerical ...

14

It looks like you found a pretty nice approach there already. A few general things stand out: Using globals Magical constants and unsafe C-style arrays/raw pointers: static vector<uint64_t> *movie_map = new vector<uint64_t>[1200000]; static vector<uint64_t> *actor_movie_map = new vector<uint64_t>[2000000]; I'd suggest using std::...

13

DFS should keep track of all the nodes visited. Not the node. The node only properties is it self, and it's children. Check this amazing implementation: graph = {'A': set(['B', 'C']), 'B': set(['A', 'D', 'E']), 'C': set(['A', 'F']), 'D': set(['B']), 'E': set(['B', 'F']), 'F': set(['C', 'E'])} def dfs(graph, ...

13

The first thing that I see is a fundamental issue that would be a problem regardless of the programming language used - long procedures. The folks who study the human aspects of software development have strong evidence suggesting that readability is critical to making code easier to understand and therefore maintain. One of the critical factors in ...

12

Those comments are very difficult to read. j = list(set(j)) #someone warned that the problematic test case gives the same edge many times, so this is to remove duplicates Format this properly: # The problematic test case gives the same edge many times, # so this is to remove duplicates j = list(set(j)) Then remove fluff: # Remove duplicates. Helps some ...

12

The big problem The reason your program runs so slowly is that your dfs() function takes the edge list as a parameter by value instead of by reference. That means it is making a copy of the edge list on every call (and recursive call). I ran your program against a maximum sized input, but it didn't finish in several minutes (I gave up). But when I ...

11

class Graph { public int vertices; LinkedList<Node> nodes = new LinkedList<Node>(); } Graph Graph, as other data structures in general, should be declared public. Because you want them to be able to be used outside of the package they are declared in. nodes, vertices should be private so that you can know that they are not changed ...

11

There are some things that you could do to improve your code: First of all, your functions clearly lack documentation. Unless you know a little bit about graph theory, it is quite hard to guess that BFS and DFS stand for "Breadth-First Search" and "Depth-First Search". While the names may appear to be long, using the names breadth_first_search and ...

11

First of all, you have a possible bug in your code. If trains is empty you will get a problem at the printing of the results. Don't code that much inside the constructor. The constructor should be used for initializing only. Be consitent in the way you create objects ArrayList<Station> changeStation =new ArrayList<Station>(); ArrayList<...

11

I'm not convinced that what you are doing really makes sense, but I did see the recursive pattern in your code and I believe that this is how you can refactor it. First of all, we create a method that you can call recursively: void DoSomething(int index) { for (Pointers[index] = 0; Pointers[index] < 8; Pointers[index]++) { if (AdjM(Pointers[...

11

$O(n^2)$ time complexity Your current algorithm has $O(n^2)$ time complexity because for each edge, you count the number of vertices on one side of the edge, which is a linear time operation. However, the program is pretty fast. I ran it on three large test cases. The first was 10000 nodes arranged in a line, the second was 10000 nodes arranged in a ...

11

1. Bug The algorithm does not always find the minimum number of messages! Suppose that we have the following follower graph (an arrow from A to B means that A follows B). To reach everyone, only one message is needed (to C or D; either will do). But when I represent this graph as an adjacency matrix: connectMatrix = [ [1, 1, 1, 0], [1, 1, 0, 0], ...

11

That's a lot of code. Consider just using STL? ;) Seriously, though, you wrote an entire List utility class, almost 500 lines of code, and: It doesn't work anything like std::list, so any coworker of yours (e.g., me) can't use their existing knowledge base to understand it. Your own code doesn't use half of the functionality you implemented (e.g., slice ...

10

Couple of major issues. You are writing your own hash function. In addition some big problems. You are implementing your own hash based dictionary (badly). You need to use the visitor pattern (rather than have a mark in each node). The hash function: int Graph::getHashVal(std::string name) { int HashVal = 0; for (int i = 0; i < name.size(); i++...

10

Constructor You seem to have everything in your constructor. This isn't really great practice. You use your constructor to initialize all of your variables, so you'd have something like: TripAdvisor() { source = new Station(); destination = new Station(); cost = 0; } TripAdvisor(Station source, Station dest) { this.source = source; ...

10

if ancestor == None: The part == None is unnecessary and adds noise to your code. Since None is a falsey value, just checking for the opposite of it will result in True if it equal to None. Here is what I mean: if not ancestor: i2 = i2+1 Statements like this could be shortened to: i2 += 1 In findChain, when you are adding errors to errors, split the ...

10

Input Parsing. You declare a Scanner to process your input, but then you don't use it very effectively. Your code: input = new Scanner(fileObj); vertexTotal = Integer.parseInt(input.nextLine()); while (input.hasNext()) { if (lineCounter < vertexTotal) { vertexList.add(new Vertex(input.nextLine().trim())); } ...

10

NetworkX is nice, but you really aren't using a lot of its features, and the features you are using end up not being that pivotal; your implementation won't be changed (much) if you remove NetworkX and use some homegrown features. Also - your current method of interspersing drawing with doing calculations is kind of annoying, and it makes it hard to tell ...

10

Algorithm Correctness Due to a small problem in GetBranchPrecedents this algorithm does not actually work. The case that all parents might already be present in the complete order. E.g. take the graph with the edges (C,A), (D,A), (E,A), (D,B), (E,B). In this case, A has the most prerequisites and will be treated first. This puts all nodes but B into the ...

9

I couldn't test out your application since I don't have a facebook account but here are some tips: 1) Use dot notation instead of bracket notation to access known property names. Old Code: friends[sourceIndex]['value']; New Code: friends[sourceIndex].value; 2) Keep the operations peformed within a loop to the bare minimum. For performance, it's best ...

Only top voted, non community-wiki answers of a minimum length are eligible