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$

2 Answers 2

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}

$\endgroup$
1
  • $\begingroup$ many thanks all ... very efficient and creative ... prg $\endgroup$
    – user42700
    Oct 31, 2019 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}

$\endgroup$
1
  • 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, 2019 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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