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
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
Your sum v1 + (incident edges) + v2 + (incident edges) + …. + vn + (incident edges) can be rewritten as (v1 + v2 + … + vn) + [(incident_edges v1) + (incident_edges v2) + … + (incident_edges vn)] and the first group is O(N) while the other is O(E).
I like this algorithm: def connected_components(neighbors): seen = set() def component(node): nodes = set([node]) while nodes: node = nodes.pop() seen.add(node) nodes |= neighbors[node] – seen yield node for node in neighbors: if node not in seen: yield component(node) Not only is it short and elegant, but also fast. Use it like so (Python 2.7): old_graph … Read more
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
That heavily depends on the structure of the search tree and the number and location of solutions (aka searched-for items). If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search … Read more
Breadth-first search traverses a graph and in fact finds all paths from a starting node. Usually, BFS doesn’t keep all paths, however. Instead, it updates a prededecessor function π to save the shortest path. You can easily modify the algorithm so that π(n) doesn’t only store one predecessor but a list of possible predecessors. Then … Read more
You can use pos attribute (https://www.graphviz.org/doc/info/attrs.html#d:pos), e.g.: xxx [ label = xxx pos = “0,0!” ] yyy [ label = yyy pos = “10,10!” ] You will also have to specify neato or fdp layout engine, so that dot command-line would be (for fdp): dot -Kfdp -n -Tpng -o sample.png sample.dot
These are the connected components of a graph, and can be found using a graphing library such as networkx. For your second example: >>> edges = [(1, 5), (4, 2), (4, 3), (5, 4), (6, 3), (7, 6), (8, 9)] >>> graph = nx.Graph(edges) >>> [tuple(c) for c in nx.connected_components(graph)] [(1, 2, 3, 4, 5, … Read more
I think that depth first search solves it. If an unexplored edge leads to a node visited before, then the graph contains a cycle. This condition also makes it O(n), since you can explore maximum n edges without setting it to true or being left with no unexplored edges.