5
$\begingroup$

Suppose I have the edges set below. From this, can a list of all nodes that in-link to all other nodes be generated? For example, 17 nodes link into node 5 (i.e., 17 nodes point to node 5 as a directed link) and these are the set {27,23,22,21,4,25,7,24,30,15,18,19,29,3,8,9,10}. How can I generate a set like this (a set of inlinks) for all nodes in the graph?

edges = {5 -> 27, 27 -> 5, 5 -> 23, 23 -> 5, 27 -> 23, 23 -> 27,     5
-> 22, 22 -> 5, 27 -> 22, 22 -> 27, 5 -> 21, 21 -> 5, 27 -> 21,     21 -> 27, 5 -> 4, 4 -> 5, 27 -> 4, 4 -> 27, 5 -> 25, 25 -> 5,     27 -> 25, 25 -> 27, 5 -> 7, 7 -> 5, 5 -> 24, 24 -> 5, 27 -> 26,     26 ->
 27, 27 -> 24, 24 -> 27, 24 -> 20, 5 -> 30, 30 -> 5, 15 -> 5,     5 ->
 18, 18 -> 5, 5 -> 19, 19 -> 5, 15 -> 18, 18 -> 15, 18 -> 19,     19 ->
 18, 29 -> 5, 5 -> 29, 29 -> 27, 27 -> 29, 29 -> 1, 1 -> 29,     29 ->
 18, 18 -> 29, 29 -> 15, 15 -> 29, 28 -> 29, 29 -> 30,     30 -> 29, 5
 -> 11, 18 -> 16, 16 -> 18, 18 -> 17, 56 -> 18,     15 -> 12, 12 -> 15, 15 -> 13, 13 -> 15, 15 -> 14, 14 -> 15, 5 -> 3,
     3 -> 5, 5 -> 8, 8 -> 5, 5 -> 9, 9 -> 5, 5 -> 10, 10 -> 5, 5 -> 31,
     27 -> 31, 5 -> 32, 27 -> 32, 5 -> 33, 27 -> 33, 5 -> 34, 27 -> 34,
     5 -> 35, 27 -> 35, 5 -> 36, 27 -> 36, 5 -> 37, 27 -> 37, 5 -> 38,     27 -> 38, 5 -> 39, 27 -> 39, 5 -> 40, 27 -> 40, 21 -> 41, 42 -> 9,    
 1 -> 6, 6 -> 1};
$\endgroup$
4
$\begingroup$

Simple pattern matching:

Cases[edges, edge : (v_ -> 5) :> v]

{27, 23, 22, 21, 4, 25, 7, 24, 30, 15, 18, 19, 29, 3, 8, 9, 10}

If you had specified the graph using DirectedEdge instead, then the pattern would have looked like this:

Cases[DirectedEdge @@@ edges, edge : DirectedEdge[v_, 5] :> v]

{27, 23, 22, 21, 4, 25, 7, 24, 30, 15, 18, 19, 29, 3, 8, 9, 10}

If you have a big graph, IncidenceList can be used to efficiently narrow it down to all edges that are incident to a given node:

Cases[
 IncidenceList[Graph[edges], 5],
 DirectedEdge[v_, 5] :> v
 ]

{27, 23, 22, 21, 4, 25, 7, 24, 30, 15, 18, 19, 29, 3, 8, 9, 10}

This leverages the graph functions even more:

g = Graph[edges];
m = IncidenceMatrix[g];
First /@ Extract[
  EdgeList[g],
  Position[m[[VertexIndex[g, 5], ;;]] // Normal, 1]
  ]

{27, 23, 22, 21, 4, 25, 7, 24, 30, 15, 18, 19, 29, 3, 8, 9, 10}

| improve this answer | |
$\endgroup$
  • $\begingroup$ many thanks all ... very efficient and creative ... prg $\endgroup$ – PRG Oct 31 '19 at 21:07
4
$\begingroup$

A few additional alternatives:

VertexInComponent

Rest @ VertexInComponent[edges, 5,1]

{27, 23, 22, 21, 4, 25, 7, 24, 30, 15, 18, 19, 29, 3, 8, 9, 10}

GroupBy

GroupBy[edges, Last -> First] @ 5

{27, 23, 22, 21, 4, 25, 7, 24, 30, 15, 18, 19, 29, 3, 8, 9, 10}

ReplaceAll

Rest @ DeleteDuplicates[5 /. List /@ Reverse /@ edges]

{27, 23, 22, 21, 4, 25, 7, 24, 30, 15, 18, 19, 29, 3, 8, 9, 10}

SparseArray + "AdjacencyLists"

SparseArray[Reverse /@ List @@@ edges -> 1]["AdjacencyLists"][[5]]

{27, 23, 22, 21, 4, 25, 7, 24, 30, 15, 18, 19, 29, 3, 8, 9, 10}

Transpose[SparseArray[List @@@ edges -> 1]]["AdjacencyLists"][[5]]

{3, 4, 7, 8, 9, 10, 15, 18, 19, 21, 22, 23, 24, 25, 27, 29, 30}

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Ah, there it is! I was almost sure there should be a function like that (VertexInComponent), I just couldn't find it. It's not linked from related functions like VertexInDegree. +1 $\endgroup$ – C. E. Nov 1 '19 at 5:19

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.