graph-theory
Finding connected components of adjacency matrix graph
You need to allocate marks – int array of length n, where n is the number of vertex in graph and fill it with zeros. Then: 1) For BFS do the following: Components = 0; Enumerate all vertices, if for vertex number i, marks[i] == 0 then ++Components; Put this vertex into queue, and while … Read more
Define graph in Prolog: edge and path, finding if there is a path between two vertices
Cycles in the graph. You need to track what nodes you’re visiting, and check them. Try this, using a helper predicate with an accumulator to track the visited nodes: path(A,B) :- % two nodes are connected, if walk(A,B,[]) % – if we can walk from one to the other, . % first seeding the visited … Read more
Number of paths between two nodes in a DAG
Do a topological sort of the DAG, then scan the vertices from the target backwards to the source. For each vertex v, keep a count of the number of paths from v to the target. When you get to the source, the value of that count is the answer. That is O(V+E).
Algorithm to simplify a weighted directed graph of debts
Here is an academic paper which investigates this problem in great detail. There is also some sample code for the different algorithms in Section 8 towards the end. Verhoeff, T. (2004). Settling multiple debts efficiently : an invitation to computing science. Informatics in Education, 3(1), 105-126.
Find all complete sub-graphs within a graph
This is known as the clique problem; it’s hard and is in NP-complete in general, and yes there are many algorithms to do this. If the graph has additional properties (e.g. it’s bipartite), then the problem becomes considerably easier and is solvable in polynomial time, but otherwise it’s very hard, and is completely solvable only … Read more
Visualizing Undirected Graph That’s Too Large for GraphViz? [closed]
Graphviz itself provides a solution for rendering large graphs. Namely, Graphviz includes sfdp, a multiscale version of fdp (also in graphviz, similar to neato) for the layout of large undirected graphs which has been useful for drawing large graphs (70k nodes, 500k edges) in my project. You can find documentation for this software on the … Read more
Why DFS and not BFS for finding cycle in graphs
Depth first search is more memory efficient than breadth first search as you can backtrack sooner. It is also easier to implement if you use the call stack but this relies on the longest path not overflowing the stack. Also if your graph is directed then you have to not just remember if you have … Read more
How do I run graphx with Python / pyspark?
You should look at GraphFrames (https://github.com/graphframes/graphframes), which wraps GraphX algorithms under the DataFrames API and it provides Python interface. Here is a quick example from https://graphframes.github.io/graphframes/docs/_site/quick-start.html, with slight modification so that it works first start pyspark with the graphframes pkg loaded pyspark –packages graphframes:graphframes:0.1.0-spark1.6 python code: from graphframes import * # Create a Vertex DataFrame … Read more
Sample Directed Graph and Topological Sort Code [closed]
Here is a simple implementation of the first algorithm from the Wikipedia page on Topological Sort: import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.Iterator; public class Graph { static class Node{ public final String name; public final HashSet<Edge> inEdges; public final HashSet<Edge> outEdges; public Node(String name) { this.name = name; inEdges = new HashSet<Edge>(); outEdges … Read more