I am interested in computing total number of simple paths(no node repeated) between two nodes in a graph(sparse, directed and contains cycles). The graph is a strongly connected component.

I initially tried using matrix multiplication, where I raised the adjacency matrix to all powers from 2 through n-1, n being the number of nodes. However this fails because of cycles in graph. For a DAG just computing all these powers and summing them up will do the job.

Unfortunately this question is highly non-trivial on arbitrary graphs. There is an analytical method but it requires explicit calculations and thus cannot provide generic answers. It consists in weighting each edge leaving a node by a variable x_node. Then consider these variables to be commute with one another and square to zero. Powers of the so-weighted adjacency matrix generate the simple paths. This adjacency matrix is known as the nilpotent adjacency matrix of the graph and the variables live in a Clifford algebra (see the litterature by R. Schott). As I mentioned earlier this method is unfortunately largely useless on sizeable graphs since it requires actual matrix powers to be analytically calculated. I hope to be proven wrong on this point though.

There is no efficient algorithm for this problem.

The problem of counting the number of simple paths from vertex *s* to *t* is #P-complete. Therefore, you cannot expect a polynomial-time algorithm that will work in general. See, e.g., http://cstheory.stackexchange.com/q/20246/5038, http://stackoverflow.com/a/5570751/781723, http://cs.stackexchange.com/q/423/755.

Time to try to find some way to avoid solving this problem, or making do with an approximation algorithm, or something.

Similar Questions

So I came to this beautiful problem that asks you to write a program that finds whether a negative infinity shortest path exists in a directed graph. (Also can be thought of as finding whether a nega

For undirected graphs , if we need to find a cycle , we use depth-first search as described in this older question,which is a well known method and also optimal . But for directed graph, this other qu

I have the basic linear shortest path algorithm implemented in Python. According to various sites I've come across, this only works for directed acyclic graphs, including this, this, and this. However

There's no restrictions that you have to cross each edge only once, or each vertex. Is there some property of the graph that is necessary and sufficient for the existence of such a path (like the deg

I work a lot with directed graphs resulting from heap dumps of Java programs. One thing that characterizes them is that they contain lots of repeating patterns. I would like to find a way of compressi

I have been writing code to get all the possible cycles in a directed graph. Here is an implementation that keeps track of back edges and whenever one back edge is found, it return true that one cycle

What algorithm can I use to find a minimum spanning tree on a directed graph? I tried using a modification of Prim's algorithm, but wasn't able to make it work.

I am working on finding cycles in directed graph using recursive backtracking. There is a suggested pseudocode for this here, which is here: dfs(adj,node,visited): if (visited[node]): if (node == star

I have created a graph similar to this force directed graph: http://bl.ocks.org/d3noob/5141278 : Using the link as an example: Sarah is linked to James and James is linked to Sarah. Instead of clutte

I am reading Numerical Recipes in C The Art of Scientific Computing, and in chapter one there is a section which discusses how floating point numbers are represented from a somewhat architecture agn

I'm facing an issue right now where I'm trying to make a force-directed graph that's smart about how it clusters. Currently I'm getting the following, which as you can see, has a very broken layout in

My following code is working perfectly fine for directed graphs and when given an undirected graph, it will not return the shortest path. public void Djikstra(int s){ boolean[] marked = new boolean[V]

for an assignment I am asked by to find find an algorithm that calculates the transitive closure of a directed graph using O(n 4 ) time. We already learned about the floyd warshall algorithm, which is

I have a directed cyclic graph with more than one cycle in it and I need a way to detect (and list) each cycle present in the digraph. The graph can be seen here: http://img412.imageshack.us/img412/33

I'm looking for a Scala (or Java) graph library implementing min-cut for directed graphs. Is there any library you would recommend me to use?

I am working on a force directed graph using d3.js. I need to handle tap and double tap event on nodes for mobile devices. Mouseover and click functions need to replicated as tap and double tap in d3.

What is the difference between a Directed Graph and a Finite State Machine, in Computer Science/Software Engineering ?

I'd like to draw a rectangular grid with arrows pointing from each cell to its 4 neighbors. It can also be a directed graph with nodes and labelled edges. Any suggestions to do this in a less tedious

I have a graph with huge number of nodes with one start node ( all edges are outward ) and one end node ( all edges towards it ). It is an unidirectional and unweighted graph.How to optimize the searc

I am using Boost Graphs. The edges of my graph have a directed meaning. Thats why I chose a directed graph. However when I traverse the graph, I usually want to do this ignoring the direction. However

I want to create a directed graph with weights in netlogo. I searched documentions but I couldn't find a way to put weights on my links. Here is my code: to setup clear-all ;; clear everything on canv

I have an input text file containing a line for each edge of a simple undirected graph. The file contains reciprocal edges, i.e. if there's a line u,v, then there's also the line v,u. I need an algori

I use d3.js exactly as shown here but with different data value. When the graph is first shown all elements are scattered and for around a second rapidly move towards their position. This looks nice

As a warning, I'm still a bit inexperienced in python I'm trying to perform the transitive reduction of directed graph using the networkx library. I've figured out an algorithm but I'm having trouble

Given an undirected graph and a node, how would you modify the graph into a directed graph such that, any path leads to one particular node.The question is coming up as a popular algorithmic question

I have a Dataset which looks like this: PostID UserID ReplyTo 1 11 NA 2 12 1 3 11 2 4 13 NA 5 12 4 I want to have a directed Graph with the Edges: 12->11, 11->12, 12->13 The Idea is that ad

Given a directed graph, the goal is to combine the node with the nodes it is pointing to and come up with minimum number of these [lets give the name] super nodes. The catch is once you combine the n

I have computed the indegree and outdegree of each node in the directed graph in two separate queries: SELECT ?s (COUNT(*) AS ?outdegree) { ?s ?p ?o } GROUP BY ?s ORDER BY DESC(?outdegree) SELECT ?o (

Given an undirected graph G=(V,E) with n vertices ( |V| = n ), how do you find if it contains a cycle in O(n) ?

I am trying to add text label to nodes in d3 Force Directed Graph, there seems to be an issue. This is my Fiddle: When I add the node name like this: node.append(text) .attr(class, word) .attr(

I need to construct directed graph (at runtime) with cycles in Prolog and don't know how to represent it, so i can get from one vertex to his neigbour in a constant time. Is it possible to do it someh

I'm working on a research problem which involves storing all non-cyclic paths from a source vertex to a destination vertex in a general directed graph (may or may not be cyclic). The input consists of

I have graphs with thousands of nodes to millions of nodes. I want to detect all possible cycles in such graphs. I use hash table to store the edges. ( (source node,edge weight) -> (target node) )

I require a tree / directed acyclic graph implementation something like this: public class TreeNode<K, V> { private K key; // 'key' for this node, always present private V value; // 'value' for

I need to find the complexity of finding all the cycles in a undirected graph consisting of 50 nodes. Moreover, if the graph grows large, will the complexity be changed and what will be it if the netw

I have a directed graph, and a set U of nodes of that graph. I want to find out if there is a path(not necessarily a simple path) that includes all nodes in the set U. What is the most efficient way o

Consider this graph: The second image (with weights in parenthesis) is balanced, i.e. each node sends the right amount of weight to the other nodes, and the end node has the same weight as the star

I'm loading horse genealogical data recursively. For some wrong sets of data my recursion never stops... and that is because in the data there are cycles. How can I detect those cycles to stop recursi

I've managed to get highlight working on my force directed graph, with help of this tutorial from Mike Bostock. Now for further procedure in my idea and needs of my graph, I'm little bit stuck, firstl

Using the dot directed graph language, is it possible to create subgraphs with a different rankdir? I tried the following, which didn't work. Both graphs were left to right, despite the presence of ra

We are given a graph with the following facts: edge(a,b) edge(a,c) edge(b,a) edge(c,d) edge(d,d) edge(d,e) edge(e,f) edge(f,g) edge(g,e) And we are asked to define a rule, cycle(X), that determines i

how to Find the center of graph (vertex, that is connected with every other vertex, but edges are directed to the center of graph) with java. its very useful application for facebook like site.

I have code written for calculating the no of cycles in a directed graph using DFS. The method to check if a cycle exists or not works fine. I now iterate through all the vertices (which I have in a H

There is a directed graph having a single designated node called root from which all other nodes are reachable. Each terminal node (no outgoing edges) takes an string value. Intermediate nodes have on

I'm going to be designing a simple data analysis tool which processes different kinds of data through a directed graph. The directed graph is somewhat customizable by the user. Each node will consist

I am trying to implement a search function on a d3 force directed graph example. When I type in the search query in the text field, relevant items will be shown and the irrelevant ones will fade out.

I have a directed graph with millions of vertices and edges. A set of vertices are given, let's assume that they are called START_POINTS. Another set of vertices, called END_POINTS are also given.

Let's say I have an acyclic directed graph such as a family tree (not really a tree since a child has 2 parents). I want to place a representation of this graph in a relational database so that it's

I'm looking for a tool to create directed graphs where I can move the nodes around and expand / shrink the graph when I, for example, click on a node. I want to use the graph in a QT interface. I thou

Say we have a strongly connected directed graph G (V,E) with positive edge weights and V0 belongs to V. Write an algorithm to find the shortest paths between all pairs of nodes through V0 An interview