4
$\begingroup$

A complete k-Partite graph can be divided into "k" distinct sets of nodes, each of which is connected to all nodes not in its own set. This can be generated with code CompleteGraph[{an, bn, cn}] where "an", "bn", and "cn" are the number of nodes in k = 3 distinct set. I would like to generate a graph that is similar, but the subset "A" connects only to "B", and "B" connects only to "C" as seen below:

enter image description here

This occurs in artificial neural networks.

This can be done using:

LayeredGraph[{nnA_, nnB_, nnC_}] :=
 Module[{graph1, graph2},
  graph1 = CompleteGraph[{nnA, nnB}, DirectedEdges -> True];
  graph2 = IndexGraph[#, nnA + 1] &@ CompleteGraph[{nnB, nnC}, DirectedEdges -> True];
  GraphUnion[graph1, graph2]
 ]

or

LayeredGraph2[{nnA_, nnB_, nnC_}] :=
 Module[{graph1, deletableEdges},
  graph1 = CompleteGraph[{nnA, nnB, nnC}, DirectedEdges -> True]; 
  Print["graph built"];
  deletableEdges = 
  Apply[DirectedEdge[#1, #2] &, #, {1}] &@ Tuples[{Range[1, nnA], Range[nnA + nnB + 1, nnA + nnB + nnC]}]; 
  Print["edges calculated"];
  EdgeDelete[graph1, deletableEdges]
 ]

but both become very slow at the GraphUnion[] and the EdgeDelete[] functions for {nnA, nnB, nnC} = {400, 100, 400} and I would like to create even larger graphs. In contrast, CompleteGraph[{400, 100, 400}] with even more edges completes in a moment.

$\endgroup$
5
$\begingroup$

I trust you'll find this much faster (not sure how much, still waiting for yours to finish on the {400,100,400} case - I'll update when it does):

lg[vcList_] := 
  Graph[Flatten@Map[Outer[DirectedEdge, #[[1]], #[[2]]] &, 
                    Partition[Range@vcList + Prepend[Accumulate@Most@vcList, 0], 2, 1]],
         GraphLayout -> None];

N.b.: I do no layout - I'm assuming at these sizes it's the graph you're after, not visualizing the whole thing at once. If not, just add appropriate GraphLayout info.

Edit: Some timings. I gave up on the {400,100,400} case - just taking too long. Here's up to 300 on the loungebook, so 5-10X faster expected on real HW. I did not use your LayeredGraph - I'm sure you know it's much slower than your LayeredGraph2. N here is {N,N/2,N} cases. Scaling seems much better also - by the time LayeredGraph2 does the {200,100,200} case, lg can do a {1700, 850, 1700} case...

enter image description here

$\endgroup$
  • 2
    $\begingroup$ Or you can use GraphLayout -> None for safe. (+1) $\endgroup$ – Silvia Sep 21 '15 at 4:03
  • $\begingroup$ @Silvia: Good idea... $\endgroup$ – ciao Sep 21 '15 at 4:24
  • $\begingroup$ Yep... that did it. I like how you made it work for an arbitrary number of layers. Thanks! $\endgroup$ – Brian Sep 23 '15 at 18:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.