title: Using R / igraph, is there a way to find a shortest path between nodes taking the count of unique node attributes into account?
body: <p>I'm trying to figure out how to find the shortest path between two nodes on a graph, using both the weights of the edges and an arbitrary penalty based on the count of the unique attributes of the nodes used.</p>
  
  <p>I'm trying to keep the problem as general as possible.</p>
  
  <p>For example, consider the following graph (simplified to demonstrate):</p>
  
  <p><a href="https://i.stack.imgur.com/zXIGb.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/zXIGb.png" alt="enter image description here"></a></p>
  
  <p>In R, I might construct my igraph object like:</p>
  
  <p>EDIT - fixed typo in the edge weights!</p>
  
  <pre><code>library(igraph)
  
  nodes = data.frame(id=c("A","B","C","D","E","F","G","H","I"),
                     colour = c("blue","blue","blue","blue","blue",
                                "red","green","yellow", "red"))
  
  edges = data.frame(from = c("A","B","C","D","E","F","G","H","I","I","I"),
                     to = c("B","C","D","E","F","G","H","A","A","E","F"),
                     #weight = c(5,6,7,5,1,5,3,2,8,8,4)) &lt;&lt;- TYPO - SORRY
                     weight = c(5,6,9,5,1,5,3,2,8,8,4))
  
  g = graph_from_data_frame(edges, directed = F, vertices = nodes)
  </code></pre>
  
  <p>To get from A to E, I can use igraph functions to calculate the shortest path.</p>
  
  <p><code>shortest_paths(g, from="A",to="E", output="vpath")[[1]]</code> returns the path A-H-G-F-E with <code>distances(g, "A","E")</code> total of 11.</p>
  
  <p>However - what if I wanted to add a penalty based on the count of unique colours of the nodes? i.e for every new coloured node it passes through, the weight is +10.</p>
  
  <p>A-H-G-F-E = edge weight of 11 and uses 4 colours, so total weight is 11+(4*10)=51</p>
  
  <p>A-B-C-D-E = edge weight of 25 uses 1 colour, total weight is 25+(1*10)=35</p>
  
  <p>A-I-E = edge weight of 16, uses 2 colours, total weight is 16+(2*10)=36</p>
  
  <p>A-I-F-E = edge weight of 13, uses 2 colours, total weight is 13+(2*10)=33</p>
  
  <p>A-I-F-E is now the "shortest route".</p>
  
  <p>I think (naively) that the weight needs to be a function of the previously visited node history.</p>
  
  <p>I'm currently playing with igraph <code>bfs</code> and <code>dfs</code> without much success to try and understand how it's working but I think I'm barking up the wrong tree.</p>
  
  <p>Before I try and reinvent the wheel, is there an existing igraph 'out of the box` function I'm missing to solve this?</p>
  
  <p>I'm using R 3.6.0 and igraph 1.2.4.1 but can understand Python also.</p>
  
  <p>TIA</p>