10
$\begingroup$

A flow graph is a rooted directed graph that the root reaches all other vertices.

I need to generate a random flow graph in Mathematica. My idea is to use FindPath[D,u,v] in a random orientation $D$. If there exists a vertex $r$ such that FindPath[D,r,v] is not empty for all $v\in V(D)\backslash\{r\}$, then $D$ is a flow graph with root $r$.

A Method by @SjoerdC.deVries: Use VertexOutComponent[G, {1}] to find the set $S$ of all vertices that are reachable by vertex $v_1$ in $G$, then use Subgraph[G,S] to get the desired flow graph.

Actually a flow graph is only part of my requirement. I need to get a reducible flow graph in the end. I think I need to make some explanations before I introduce the definition of a reducible flow graph.

In a flow graph $D$ with root $r$, we say vertex $u$ dominates vertex $v$ if every $r-v$ path in $D$ passes $u$. A DAG is a directed acyclic graph. A DFS spanning tree of flow graph $D$ with root $r$ is a spanning tree with root $r$ obtained by depth first search algorithm. A DFS DAG of $D$ is subgraph of $D$ obtained from a DFS spanning tree of $D$ by adding a maximal subset of arcs without creating directed cycles.

A reducible flow graph is a flow graph such that it has a unique DAG. Moreover, $D=(V,A)$ is a reducible flow graph if and only if the arc set $A$ can be partitioned into two sets $A_1$ and $A_2$ such that $(V,A_1)$ is a DAG (acyclic subgraph of $D$) and $u$ dominates $v$ in $D$ for each arc $(v,u)$ in $A_2$.

Given a flow graph $D=(V,A)$ with root $r$, my idea is to check every two-partition $A_1$ and $A_2$ of arc set $A$. If there exists a two-partition satisfying the following requirements at the same time, then it is reducible:

  1. AcyclicGraphQ[D'] is true, where $D'=(V,A_1)$;
  2. Outer[MemberQ,FindPath[D,r,v,1000,All],{u},1] are all true, for each arc $(v,u)\in A_2$.

I think @SjoerdC.deVries has provided us with a very neat way to generate a random flow graph. The main problem with my method is that one has to check every acyclic subgraph of $D$ and all edges in the complement of the subgraph. Currently, I only know to AcyclicGraphQ every subgraph of $D$ generated by all elements in Subsets[A]. It has a lot of work to do to go through the power set of $A$. I worked on a $K_8$ and it took a while (around 70s on my computer) to get a result. So my questions here are:

  1. How to generate all acyclic subgraphs of $D$ efficiently?
  2. Or are there any other methods to generate a reducible flow graph efficiently?

I need to apologise for the complicated definitions here. Actually, they are selected from my papers. I want to write a Mathematica implementation for my algorithm, but I got stuck at generating a random reducible flow graph.

Any comments or suggestions on flow graphs and reducible flow graphs are welcome!

Remarks:

  1. The (reducible) flow graph need not to be very large. About 20 vertices will suffice.
  2. I also wonder whether I can construct the desired reducible flow graph backwards, say starting with a DSF spanning tree $T$ and try to add arcs to $T$ without creating directed cycles. But it seems to give special reducible flow graphs only (which is identical with its DFS DAG). To get nontrivial examples, we still need to put arcs to the resulting DFS DAG and make sure that the DSF DAG is unique. But currently I have no idea on how to do this.
$\endgroup$
  • 1
    $\begingroup$ Something like g=RandomGraph[10000,15000];Subgraph[g,VertexOutComponent[g, {1}]]? $\endgroup$ – Sjoerd C. de Vries Apr 27 '15 at 12:09
  • $\begingroup$ @SjoerdC.deVries: Yes. I didn't know VertexOutComponent before. I think your method perfectly solved my problem for generating a random flow graph. It is much neater and more efficient than mine. Thank you so much. $\endgroup$ – Han Xiao Apr 28 '15 at 3:59
  • $\begingroup$ @SjoerdC.deVries Care to post as an answer? $\endgroup$ – Dr. belisarius Feb 4 '16 at 23:17
  • $\begingroup$ @belisarius it doesn't seem to answer the follow-up question that was added later (and which I didn't notice until now). $\endgroup$ – Sjoerd C. de Vries Feb 5 '16 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.