Message Boards Message Boards

0
|
6711 Views
|
5 Replies
|
8 Total Likes
View groups...
Share
Share this post:

Lists of vertices by level from "LayeredEmbedding"?

Posted 4 years ago

When a Graph is generated with layout "LayeredEmbedding", is there a built-in means of obtaining lists of vertices per layer, in horizontal order (e.g. left to right)? enter image description here

POSTED BY: Richard Frost
5 Replies
Posted 4 years ago

You can just do some sorting and grouping with vertex coordinates.

g = TreeGraph[
  RandomInteger[#] \[UndirectedEdge] # + 1 & /@ Range[0, 30], 
  VertexLabels -> Automatic]

coord = Thread[VertexList[g] -> GraphEmbedding[g]];

layers = (SortBy[#, #[[2, 1]] &] & /@ 
     GatherBy[Reverse[SortBy[coord, #[[2, 2]] &]], #[[2, 2]] &])[[All,
     All, 1]];

Column[layers]
POSTED BY: Jaebum Jung

Thank you Jaebum Jung. I have used your technique to extract vertices by layer, then alternated the label positions Above and Below left to right in each layer. This, along with reducing the precision in the edgeweights has greatly improved the legibility of the graph. I'm very happy to achieve this in an automated way!

POSTED BY: Richard Frost

You can also use VertexComponent and crawl through your graph.

Flatten[
 Block[
  {
   cnt = 0,
   lastvertex = VertexComponent[LEgPP, "Pied De Boeuf"][[-1]]
   },
  Reap[
    While[
     MemberQ[Sow@VertexComponent[LEgPP, "Pied De Boeuf", {cnt++}], 
       lastvertex] == False]][[2]]
  ]
 , 1]

You pick your starting point and from there you call for the exact depth. {{"Pied De Boeuf"}, {"Yede Vern", "Kukurchinskii", "Milco", "UCR-291"}, {"Shevlan 1", "Kadota", "Bourjassotte Blanche", "Maslin 150"}, {"Centroid [CapitalGamma]", "Fico Nero", "Ischia Black", "Conadria", "Shih Berdy 3", "Long Yellow", "Encanto"}, {"Calabacita", "Long Fellow", "Adriatic", "Flanders", "Moscatel", "Vernino", "Zidi", "T 30E", "Verte"}, {"Ficus palmata", "Gulbun Selection", "Enderud", "Calimyrna", "Watts Algerian", "Italian 281", "Bournabat", "Italian 258", "Zheltoplodnyi Okruglyi", "King", "Encanto Brown Turkey", "Moissoniere", "Saleeb", "San Joao Branco", "UCR-291-4"}, {"Aked", "Archipel", "Roeding 4", "Santa Cruz Light", "Golden Celeste", "LSU Gold", "Early Violet", "Alma", "Chater Green", "Kop Fiomi", "San Antonio", "Santa Cruz Dark", "M.C. Smyrnay", "Latarulla", "Italian 372", "Brown Turkey", "Italian 320", "Becane", "Hacin", "Capri Q", "Green Panachee", "LSU Hollier"}, {"Barbillone", "Santa Cruz White", "Celeste", "Hurricane", "Honigal", "Dawalki", "Italian 215", "Kalamata", "Genoa", "Karayaprak", "Bosnat", "Mission", "Panachee"}, {"Caucasus #1", "Cuello Dama Negro", "Oregon Little Red", "Nero Cesar", "Col De Dame", "Violette De Bordeaux", "DiRedo", "Asisi", "Hative D[CloseCurlyQuote]Argenteuil", "Igo", "Capri W", "White Russian"}, {"Tiberio", "Stanford", "Bianco", "Green Germany 1920", "Verdal Longue", "Shevlan 2", "San Pietro", "Italian 358", "Tena", "Abruzzi", "Barada", "Italian 395", "Italian 253", "Ischia White", "Capri X", "Double Header"}, {"Bourjassote Grise", "Pastiliere", "Armenian", "Zheltyi from Seidov", "Hearty Chicago", "Brunswick", "Italian 88", "St. Jean"}, {"Caucasus #6", "Black Fig I", "Yellow Neches", "A. Koinekashirskii", "Sierra", "Chikishlyarskii"}, {"Skardu Black", "Kury Gol", "Ischia Green", "Afghan A"}, {"Sucrette", "A. Kuruzhdeiskii"}, {"Nuhurskii", "Blanquette", "Excel"}}

POSTED BY: l van Veen

Thank you Ivan, this could be useful. I would need a method to extract which vertex the LayeredEmbedding has placed at the "top". Is there a direct means other than GraphEmbedding[] ?

POSTED BY: Richard Frost

Hi Richard, I don't know (I'm not an expert alas). There should be :)

Anyway I always thought that for the LayeredEmbedding the RootVertex chosen was one of the Vertexes with the lowest VertexEccentricity.

Playing with the random graph written by @Jaebum Jung this might be right.

{VertexEccentricity[LEgPP, #], #} & /@ VertexList[LEgPP] //Sort // First // Last

seems to do the trick for your graph and a couple of the randomgraphs I tried. Using on Graphs with some disconnected Vertex will not work (unless you cast out the ones with 0 Eccentricity first). I think that Jaebum's way will be the fastest way of sorting it out anyway. But if you Use the option GraphLayout -> {"LayeredEmbedding", "Orientation" -> Left} it will fail and mine will still work. Obviously Jaebum's way will work with changing the sorting order.

POSTED BY: l van Veen
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract