Graph with multiple partitions

Question

I have an edgelist

originalEdgeList = {"K.CC.2" -> "1.OA.5", "K.CC.3" -> "K.CC.7", 
   "K.CC.3" -> "1.NBT.1", "K.CC.4" -> "K.CC.5", "K.CC.4" -> "K.CC.6", 
   "K.CC.5" -> "K.CC.3", "K.CC.5" -> "K.CC.4", "K.CC.6" -> "K.CC.7", 
   "K.CC.7" -> "1.NBT.3", "K.OA.1" -> "K.OA.2", "K.OA.1" -> "K.OA.3", 
   "K.OA.1" -> "K.OA.5", "K.OA.1" -> "4.NF.3a", "K.OA.2" -> "1.OA.1", 
   "K.OA.3" -> "K.OA.4", "K.OA.3" -> "K.OA.5", "K.OA.3" -> "4.NF.3b", 
   "K.OA.4" -> "K.NBT.1", "K.OA.4" -> "1.OA.3", "K.OA.4" -> "1.OA.4", 
   "K.OA.5" -> "K.OA.3", "K.OA.5" -> "1.OA.6", "K.OA.5" -> "1.NBT.4", 
   "K.NBT.1" -> "1.NBT.2", "K.MD.1" -> "K.MD.2", "K.MD.2" -> "K.CC.6",
    "K.MD.2" -> "K.CC.7", "K.MD.2" -> "1.MD.1", "K.G.2" -> "K.G.1", 
   "K.G.2" -> "K.G.4", "K.G.2" -> "K.G.5", "K.G.2" -> "K.G.6", 
   "K.G.3" -> "K.G.1", "K.G.3" -> "K.G.4", "K.G.3" -> "K.G.5", 
   "K.G.4" -> "1.G.1", "K.G.5" -> "1.G.1", "K.G.6" -> "1.G.2", 
   "K.G.6" -> "1.G.3", "1.OA.1" -> "1.OA.2", "1.OA.1" -> "1.OA.8", 
   "1.OA.1" -> "4.NF.3d", "1.OA.3" -> "1.OA.6", "1.OA.3" -> "1.OA.7", 
   "1.OA.3" -> "4.NF.3c", "1.OA.4" -> "1.OA.6", "1.OA.4" -> "1.OA.7", 
   "1.OA.6" -> "1.NBT.4", "1.OA.6" -> "2.OA.2", "1.OA.6" -> "2.NBT.5",
    "1.OA.7" -> "1.OA.8", "1.NBT.1" -> "1.NBT.2", 
   "1.NBT.1" -> "2.NBT.2", "1.NBT.2" -> "1.NBT.1", 
   "1.NBT.2" -> "1.NBT.3", "1.NBT.2" -> "1.NBT.4", 
   "1.NBT.2" -> "1.NBT.6", "1.NBT.2" -> "2.NBT.1", 
   "1.NBT.3" -> "2.NBT.4", "1.NBT.4" -> "2.NBT.7", 
   "1.NBT.5" -> "2.NBT.8", "1.NBT.6" -> "1.NBT.5", 
   "1.NBT.6" -> "2.NBT.7", "1.MD.1" -> "1.MD.2", "1.MD.1" -> "2.MD.2",
    "1.MD.1" -> "2.MD.4", "1.MD.1" -> "2.MD.9", "1.MD.2" -> "2.MD.1", 
   "1.MD.3" -> "2.MD.7", "1.MD.4" -> "2.MD.10", "1.G.1" -> "2.G.1", 
   "1.G.3" -> "2.G.2", "1.G.3" -> "2.G.3", "2.OA.1" -> "2.NBT.5", 
   "2.OA.1" -> "2.MD.5", "2.OA.1" -> "3.OA.8", "2.OA.1" -> "4.OA.2", 
   "2.OA.2" -> "3.NBT.2", "2.OA.3" -> "3.OA.9", "2.OA.4" -> "2.NBT.2",
    "2.OA.4" -> "3.OA.1", "2.NBT.1" -> "2.NBT.2", 
   "2.NBT.1" -> "2.NBT.3", "2.NBT.1" -> "2.NBT.4", 
   "2.NBT.1" -> "2.NBT.5", "2.NBT.1" -> "2.NBT.6", 
   "2.NBT.1" -> "2.NBT.7", "2.NBT.1" -> "2.NBT.8", 
   "2.NBT.1" -> "3.NBT.1", "2.NBT.1" -> "4.NBT.1", 
   "2.NBT.2" -> "2.OA.4", "2.NBT.2" -> "2.NBT.1", 
   "2.NBT.2" -> "3.NBT.1", "2.NBT.3" -> "4.NBT.2", 
   "2.NBT.4" -> "4.NBT.2", "2.NBT.5" -> "2.OA.1", 
   "2.NBT.5" -> "2.NBT.9", "2.NBT.5" -> "3.NBT.2", 
   "2.NBT.7" -> "3.NBT.2", "2.NBT.8" -> "3.NBT.2", 
   "2.NBT.9" -> "3.NBT.2", "2.MD.1" -> "2.MD.3", "2.MD.1" -> "2.MD.4",
    "2.MD.1" -> "2.MD.6", "2.MD.1" -> "3.MD.4", "2.MD.2" -> "2.MD.3", 
   "2.MD.4" -> "2.MD.5", "2.MD.5" -> "2.OA.1", "2.MD.5" -> "2.MD.6", 
   "2.MD.5" -> "3.MD.8", "2.MD.6" -> "3.NF.2a", "2.MD.6" -> "3.MD.1", 
   "2.MD.7" -> "3.MD.1", "2.MD.8" -> "4.NF.6", "2.MD.9" -> "3.MD.4", 
   "2.MD.10" -> "3.MD.3", "2.G.1" -> "3.G.1", "2.G.2" -> "3.OA.1", 
   "2.G.2" -> "3.MD.6", "2.G.2" -> "3.MD.7c", "2.G.2" -> "4.NBT.5", 
   "2.G.3" -> "3.G.2", "3.OA.1" -> "3.OA.3", "3.OA.1" -> "3.OA.4", 
   "3.OA.1" -> "3.OA.5", "3.OA.1" -> "3.OA.7", "3.OA.1" -> "3.MD.7a", 
   "3.OA.1" -> "4.NBT.5", "3.OA.1" -> "4.NF.4a", "3.OA.2" -> "3.OA.3",
    "3.OA.2" -> "3.OA.4", "3.OA.2" -> "3.OA.5", "3.OA.2" -> "3.OA.6", 
   "3.OA.2" -> "3.OA.8", "3.OA.2" -> "4.NBT.6", "3.OA.3" -> "4.NF.4c",
    "3.OA.5" -> "6.EE.3", "3.OA.7" -> "4.OA.4", "3.OA.7" -> "4.NBT.5",
    "3.OA.8" -> "4.OA.3", "3.OA.9" -> "4.OA.5", 
   "3.NBT.1" -> "4.NBT.3", "3.NBT.2" -> "4.NBT.4", 
   "3.NBT.3" -> "4.NBT.5", "3.NBT.3" -> "4.NBT.6", 
   "3.NF.1" -> "3.NF.2a", "3.NF.1" -> "3.MD.4", "3.NF.2" -> "6.NS.6a",
    "3.NF.2a" -> "3.NF.2b", "3.NF.2b" -> "3.NF.3a", 
   "3.NF.2b" -> "3.NF.3c", "3.NF.3a" -> "3.NF.3b", 
   "3.NF.3a" -> "3.NF.3d", "3.NF.3b" -> "4.NF.1", 
   "3.NF.3b" -> "4.NF.5", "3.NF.3d" -> "4.NF.2", 
   "3.NF.3d" -> "4.NF.5", "3.NF.3d" -> "4.NF.7", "3.MD.1" -> "4.MD.1",
    "3.MD.2" -> "5.MD.3a", "3.MD.4" -> "4.MD.4", 
   "3.MD.5.a" -> "3.MD.5.b", "3.MD.5.b" -> "3.MD.6", 
   "3.MD.6" -> "3.MD.7a", "3.MD.7" -> "2.G.2", "3.MD.7" -> "5.NF.4b", 
   "3.MD.7a" -> "3.MD.7b", "3.MD.7a" -> "3.MD.7d", 
   "3.MD.7a" -> "5.NF.4b", "3.MD.7d" -> "3.MD.7c", 
   "3.MD.7d" -> "4.MD.3", "3.MD.8" -> "4.MD.3", "3.G.1" -> "5.G.3", 
   "3.G.2" -> "3.NF.1", "3.G.2" -> "3.MD.7a", "4.OA.1" -> "4.OA.2", 
   "4.OA.1" -> "5.NF.5.a", "4.OA.3" -> "6.EE.2a", 
   "4.OA.4" -> "6.NS.4", "4.OA.5" -> "5.OA.3", "4.NBT.1" -> "4.NBT.2",
    "4.NBT.1" -> "5.NBT.1", "4.NBT.2" -> "5.NBT.3", 
   "4.NBT.3" -> "5.NBT.4", "4.NBT.5" -> "5.NBT.5", 
   "4.NBT.5" -> "5.NF.4b", "4.NBT.6" -> "5.NBT.6", 
   "4.NBT.6" -> "5.NF.7a", "4.NF.1" -> "5.NF.1", 
   "4.NF.3a" -> "4.NF.3b", "4.NF.3a" -> "4.NF.3c", 
   "4.NF.3a" -> "4.NF.3d", "4.NF.3d" -> "5.NF.2", 
   "4.NF.4a" -> "4.NF.4b", "4.NF.4b" -> "4.NF.4c", 
   "4.NF.4c" -> "5.NF.6", "4.NF.5" -> "4.NF.6", "4.NF.6" -> "4.NF.7", 
   "4.NF.6" -> "7.NS.2d", "4.MD.1" -> "4.MD.2", "4.MD.2" -> "5.MD.1", 
   "4.MD.3" -> "6.G.1", "4.MD.4" -> "5.MD.2", "4.MD.4" -> "5.G.1", 
   "4.MD.5.a" -> "4.MD.5.b", "4.MD.5.b" -> "4.MD.6", 
   "4.MD.5.b" -> "4.G.1", "4.MD.6" -> "4.MD.7", "4.MD.6" -> "7.G.5", 
   "4.G.1" -> "4.G.2", "4.G.1" -> "7.G.2", "4.G.2" -> "5.G.3", 
   "5.OA.1" -> "5.OA.2", "5.OA.1" -> "6.EE.2b", "5.OA.3" -> "6.EE.9", 
   "5.NBT.1" -> "5.NBT.2", "5.NBT.2" -> "5.NBT.7", 
   "5.NBT.2" -> "6.EE.1", "5.NBT.6" -> "6.NS.2", 
   "5.NBT.7" -> "6.NS.3", "5.NF.1" -> "5.NF.2", "5.NF.3" -> "5.NF.4a",
    "5.NF.3" -> "5.NF.7a", "5.NF.3" -> "7.NS.2d", 
   "5.NF.4" -> "7.NS.2a", "5.NF.4a" -> "5.NF.4b", 
   "5.NF.5.a" -> "5.NF.5.b", "5.NF.7a" -> "5.NF.7b", 
   "5.NF.7b" -> "5.NF.7c", "5.NF.7b" -> "6.NS.1", 
   "5.MD.2" -> "6.SP.4", "5.MD.3a" -> "5.MD.3b", 
   "5.MD.3b" -> "5.MD.4", "5.MD.4" -> "5.MD.5a", 
   "5.MD.5a" -> "5.MD.5b", "5.MD.5b" -> "5.MD.5c", 
   "5.MD.5b" -> "6.G.2", "5.G.1" -> "5.G.2", "5.G.1" -> "6.NS.6b", 
   "5.G.2" -> "6.NS.8", "5.G.3" -> "5.G.4", "5.G.3" -> "7.G.3", 
   "5.G.4" -> "5.G.3", "6.RP.1" -> "6.RP.2", "6.RP.1" -> "6.RP.3c", 
   "6.RP.2" -> "6.RP.3a", "6.RP.2" -> "6.RP.3b", 
   "6.RP.2" -> "6.RP.3d", "6.RP.2" -> "7.RP.1", 
   "6.RP.3a" -> "7.RP.2a", "6.RP.3c" -> "7.RP.3", 
   "6.NS.1" -> "7.RP.1", "6.NS.1" -> "7.NS.2b", "6.NS.2" -> "6.NS.3", 
   "6.NS.3" -> "7.NS.2d", "6.NS.5" -> "6.NS.6a", 
   "6.NS.5" -> "6.NS.7b", "6.NS.5" -> "7.NS.1a", 
   "6.NS.6a" -> "6.NS.6b", "6.NS.6a" -> "6.NS.7c", 
   "6.NS.6b" -> "6.NS.6c", "6.NS.6c" -> "6.NS.7a", 
   "6.NS.6c" -> "6.NS.8", "6.NS.7b" -> "6.NS.7d", 
   "6.NS.7c" -> "6.NS.7d", "6.NS.7c" -> "6.NS.8", 
   "6.NS.7c" -> "7.NS.1b", "6.EE.1" -> "6.EE.2a", 
   "6.EE.1" -> "6.EE.2c", "6.EE.1" -> "6.EE.3", "6.EE.1" -> "6.EE.4", 
   "6.EE.1" -> "7.EE.3", "6.EE.1" -> "8.EE.1", "6.EE.2a" -> "6.EE.6", 
   "6.EE.2c" -> "6.EE.5", "6.EE.3" -> "6.EE.4", "6.EE.3" -> "7.EE.1", 
   "6.EE.3" -> "7.EE.2", "6.EE.4" -> "6.EE.3", "6.EE.5" -> "6.EE.7", 
   "6.EE.6" -> "6.EE.7", "6.EE.6" -> "6.EE.9", "6.EE.7" -> "6.EE.8", 
   "6.EE.7" -> "6.EE.9", "6.EE.7" -> "7.EE.4a", "6.EE.8" -> "6.EE.7", 
   "6.EE.8" -> "6.EE.9", "6.EE.8" -> "7.EE.4b", "6.EE.9" -> "6.EE.7", 
   "6.EE.9" -> "6.EE.8", "6.EE.9" -> "8.F.1", "6.G.1" -> "6.G.4", 
   "6.G.1" -> "7.G.1", "6.G.1" -> "7.G.4", "6.G.1" -> "8.G.6", 
   "6.G.2" -> "7.G.6", "6.G.3" -> "8.G.8", "6.G.4" -> "7.G.6", 
   "6.SP.1" -> "6.SP.2", "6.SP.1" -> "7.SP.1", "6.SP.2" -> "6.SP.3", 
   "6.SP.2" -> "6.SP.5a", "6.SP.2" -> "6.SP.5b", 
   "6.SP.3" -> "6.SP.5a", "6.SP.3" -> "6.SP.5b", 
   "6.SP.3" -> "6.SP.5c", "6.SP.3" -> "6.SP.5d", "6.SP.4" -> "6.SP.2",
    "6.SP.4" -> "6.SP.5d", "6.SP.4" -> "7.SP.3", "6.SP.4" -> "8.SP.1",
    "6.SP.5" -> "7.SP.3", "6.SP.5c" -> "7.SP.4", 
   "6.SP.5d" -> "7.SP.3", "7.RP.1" -> "7.RP.2a", 
   "7.RP.1" -> "7.RP.2b", "7.RP.1" -> "7.RP.2c", 
   "7.RP.2a" -> "7.RP.2d", "7.RP.2b" -> "7.RP.2d", 
   "7.RP.2c" -> "7.RP.3", "7.NS.1b" -> "7.NS.1c", 
   "7.NS.1c" -> "7.NS.1d", "7.NS.1d" -> "7.NS.3", 
   "7.NS.2a" -> "7.NS.2b", "7.NS.2b" -> "7.NS.2c", 
   "7.NS.2b" -> "7.NS.2d", "7.NS.2c" -> "7.NS.3", 
   "7.NS.2d" -> "8.NS.1", "7.EE.1" -> "7.EE.2", "7.EE.2" -> "7.EE.1", 
   "7.EE.4a" -> "8.EE.7a", "7.EE.4a" -> "8.EE.7b", "7.G.4" -> "8.G.9",
    "7.G.5" -> "8.G.5", "7.SP.1" -> "7.SP.2", "7.SP.2" -> "7.SP.4", 
   "7.SP.3" -> "7.SP.4", "7.SP.5" -> "7.SP.6", "7.SP.5" -> "7.SP.7a", 
   "7.SP.7a" -> "7.SP.7b", "7.SP.7b" -> "7.SP.8a", 
   "7.SP.7b" -> "7.SP.8c", "7.SP.8a" -> "7.SP.8b", 
   "8.NS.1" -> "8.NS.2", "8.EE.1" -> "8.EE.2", "8.EE.1" -> "8.EE.3", 
   "8.EE.3" -> "8.EE.4", "8.EE.5" -> "8.EE.6", "8.EE.5" -> "8.EE.8a", 
   "8.EE.5" -> "8.F.4", "8.EE.6" -> "8.EE.5", "8.EE.6" -> "8.EE.8a", 
   "8.EE.6" -> "8.F.4", "8.EE.7a" -> "8.EE.8a", 
   "8.EE.7b" -> "8.EE.8a", "8.EE.8a" -> "8.EE.8b", 
   "8.EE.8a" -> "8.EE.8c", "8.EE.8b" -> "8.EE.8a", 
   "8.EE.8b" -> "8.EE.8c", "8.EE.8c" -> "8.EE.8a", 
   "8.EE.8c" -> "8.EE.8b", "8.F.1" -> "8.F.2", "8.F.1" -> "8.F.3", 
   "8.F.1" -> "8.F.4", "8.F.1" -> "8.F.5", "8.F.4" -> "8.EE.5", 
   "8.F.4" -> "8.EE.6", "8.G.1" -> "8.G.3", "8.G.3" -> "8.G.2", 
   "8.G.3" -> "8.G.4", "8.G.6" -> "8.G.7", "8.G.6" -> "8.G.8", 
   "8.G.7" -> "8.G.6", "8.G.7" -> "8.G.8", "8.G.8" -> "8.G.6", 
   "8.G.8" -> "8.G.7", "8.SP.1" -> "8.SP.2", "8.SP.1" -> "8.SP.4", 
   "8.SP.2" -> "8.SP.3", "8.SP.2" -> "8.SP.4"};

and I would like to partition it into 9 directed columns corresponding to the ordering k,1,2,3,4,5,6,7,8. I thought I can implement it using MultipartiteEmbedding once I know the VertexPartitions.

The VertexPartitions can be extracted from the edgelist. But I realized the VertexList does not follow the ordering. So I reordered after I did sort, i.e.

reorderedVertexList = Flatten[Drop[Prepend[sortVertexList, sortVertexList[[261 ;; 280]]],-20]]

Then I just manually counted how many nodes start with k, 1, 2, 3, etc. to identify the partitions. I got "VertexPartition" -> {20, 21, 26, 35, 33, 34, 43, 37, 31}.

When I put them together though:

newGraph = 
 Graph[reorderedVertexList, originalEdgeList, 
  GraphLayout -> {"MultipartiteEmbedding", 
    "VertexPartition" -> {20, 21, 26, 35, 33, 34, 43, 37, 31}}]

the graph does not show the partitions k,1,2,3,4,5,6,7,8. I don't have 20 nodes for k, 21 nodes for "1" etc. Where did I get wrong? Appreciate the inputs.

Szabolcs · Accepted Answer · 2018-02-16 10:29:10Z

1

I believe that the reason for the failure is that Mathematica always breaks the graph into components before computing a layout. After laying out each component separately, it combines them.

In this case, the partition sizes you provided won't be valid after breaking up the graph into components, therefore this procedure fails.

Thus the only way to do it is to supply vertex coordinates manually.

vertices = VertexList[originalEdgeList];
types = {"K", "1", "2", "3", "4", "5", "6", "7", "8"};
partitions = Select[vertices, StringStartsQ[#]] & /@ types;

Graph[originalEdgeList, 
 VertexCoordinates -> Flatten@MapIndexed[#1 -> {10, 1} #2 &, partitions, {2}],
 EdgeStyle -> Arrowheads[Small],
 EdgeShapeFunction -> Arrow@*GraphElementData["CurvedArc"]]

edited Feb 16, 2018 at 10:29

answered Feb 16, 2018 at 8:04

Szabolcs

236k31 gold badges641 silver badges1.3k bronze badges

$\begingroup$ Hi Szabolcs...you nailed it. Thanks a lot for the answer! I learned a couple of things along the way! Thank you very much! $\endgroup$
– Narra Kalayaan
Commented Feb 16, 2018 at 13:22

Add a comment |

David G. Stork · Accepted Answer · 2018-02-16 05:10:55Z

0

Outline

Table[
  list[i] = 
   Select[originalEdgeList, 
    StringTake[#[[1]], 1] == ToString[i] &], {i, 9}];

This gives you eight sublists.

Get the vertexes with a "1" in the first position:

DeleteDuplicates[list[1][[All, 1]]]

(and likewise for the other 7 first digits).

Use Length to find how many in each "layer".

Then make VertexCoordinates[1] = Table[{1, Length[list[1]]}], and likewise for the other layers.

Flatten your list to get a full list,

myVertexCoordinates = Flatten[Union[VertexCoordinates[1],...,VertexCoordinates[8]]].

Use that in Graph[originalEdgeList, myVertexCoordinates]

answered Feb 16, 2018 at 5:10

David G. Stork

42.3k3 gold badges37 silver badges106 bronze badges

$\begingroup$ Hi David, Thank you very much for your inputs! You have given me ideas on how to address it. Appreciate very much the help! $\endgroup$
– Narra Kalayaan
Commented Feb 16, 2018 at 9:57

Add a comment |

Stack Exchange Network

Graph with multiple partitions

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged
graphs-and-networks
partitions
or ask your own question.

Hot Network Questions

Graph with multiple partitions

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
graphs-and-networks
partitions
or ask your own question.