6
$\begingroup$

The goal is to build a graph consit of six elements (La, Le ,Li, Ka, Ke, Ki). La, Le, Li belong to group L, while Ka, Ke, Ki belong to group K. There are two differet interactions possible between the elements: mailing and meeting (undirected). In the image below the interactions and groups are shown. enter image description here

How can make up this graph in Mathematica? How can I then get a track of a mail to be send from La to Ka? How can I find the link for mailing between the groups in Mathematica? Is it also possible to find tracks that an information, either passed by mailing or meeting, can take from one e.g La to Ki? I do not want to split it as the construction of the graph may be different with respect to the computations needed.

Update

I can built a graph,based on the interactions, like following:

Graph[{ "La" <-> "Le", "Le" <-> "Li", "Li" <-> "Ke", "Ke" <-> "Ka", "Li" <-> "Le", "Le" <-> "Ka", "Ka" <-> "Ke", "Ka" <-> "Ki"}, VertexLabels -> "Name"]

http://o8aucf9ny.bkt.clouddn.com/2016-12-23-08-27-01.png

But I cannot classify the edge to meet or mail to calculate.

Improve this question
$\endgroup$
2
  • $\begingroup$ Interesting question,I want know how to set different edge in a same graph,too. $\endgroup$ Commented Dec 22, 2016 at 23:08
  • $\begingroup$ Do you need to do this for a large network or is it just for this 6-node example? Do you have raw data that you could post? You may want to let us know what you have done so far. $\endgroup$ Commented Dec 22, 2016 at 23:31

3 Answers 3

Reset to default
2
$\begingroup$

This is really two problems, rendering and path finding. First let's fake an undirected multi-adjacency matrix graph:

spec = DeleteDuplicatesBy[ { "La" <-> "Le", "Le" <-> "Li", "Li" <-> "Ke", "Ke" <-> "Ka", "Li" <-> "Le", "Le" <-> "Ka", "Ka" <-> "Ke", "Ka" <-> "Ki" }, Sort[List @@ #] & ]; spec = Flatten[ spec /. UndirectedEdge[n_, n2_] :> {Property[DirectedEdge[n, n2], EdgeStyle -> Directive[Arrowheads[0], Red]], Property[DirectedEdge[n2, n], EdgeStyle -> Directive[Arrowheads[0], Green]]}]; g=Graph[spec, VertexLabels -> "Name"]

Looks like this:

graph

Then you can apply any path finding algorithm to the adjacency matrix underlying the graph:

In[100]:= Normal@AdjacencyMatrix@spec Out[100]= {{0, 1, 0, 0, 0, 0}, {1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 0}, {0, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1}, {0, 0, 0, 0, 1, 0}}

This is both the meet path adjacency matrix and the mail path one.

If you then want all mailing/meeting paths, that's pretty easy to do via some Floyd-Warshall like mechanism.

Improve this answer
$\endgroup$
7
  • $\begingroup$ How can I then get a track of a mail to be send from La to Ka from your graph? $\endgroup$ Commented Dec 23, 2016 at 17:17
  • $\begingroup$ Do you want it to go only via mailing routes or is it passed via mail or meet routes? Is one route prioritized? It's a simple-enough problem from a weighted adjacency matrix, but I need more info first. $\endgroup$ Commented Dec 23, 2016 at 17:20
  • $\begingroup$ And if you want to work directly from the graph you can regenerate the matrix via WeightedAdjacencyMatrix. $\endgroup$ Commented Dec 23, 2016 at 17:51
  • $\begingroup$ Yep,I mean go only via mailing routes,and from La to Ka. $\endgroup$ Commented Dec 23, 2016 at 17:59
  • $\begingroup$ I just realized I need to tweak the graph generating code (it's only generating a directed mail/meet pair for a pair of nodes, while those edges should really be undirected) but basically just use some variant of Dijkstra's algorithm. It operates on the adjacency matrix. $\endgroup$ Commented Dec 23, 2016 at 18:20
1
+50
$\begingroup$

As an input I used:

vertexData={Property["La","group"->"L"],Property["Le","group"->"L"],Property["Li","group"->"L"],Property["Ka","group"->"K"],Property["Ke","group"->"K"],Property["Ki","group"->"K"]}; linkData= {Property["La"<->"Le",{EdgeLabels->"mail",EdgeStyle->Blue,"interaction"->"mail"}], Property["Le"<->"Li",{EdgeLabels->"meet",EdgeStyle->Green,"interaction"->"meet"}], Property["Le"<->"Li",{EdgeLabels->"mail",EdgeStyle->Blue,"interaction"->"mail"}], Property["Le"<->"Ka",{EdgeLabels->"meet",EdgeStyle->Green,"interaction"->"meet"}], Property["Li"<->"Ke",{EdgeLabels->"mail",EdgeStyle->Blue,"interaction"->"mail"}], Property["Ka"<->"Ke",{EdgeLabels->"meet",EdgeStyle->Green,"interaction"->"meet"}], Property["Ka"<->"Ke",{EdgeLabels->"mail",EdgeStyle->Blue,"interaction"->"mail"}], Property["Ka"<->"Ki",{EdgeLabels->"meet",EdgeStyle->Green,"interaction"->"meet"}]};

I tried to use the custom property differently but that was what came out in best case. In Graph these setting are just ignored. So the passing of an information (able to use "mail" and "meet" edges is just:

(*Path for an information to go, as it does not care about different \ interactions as information by definition*) gFull = Graph[vertexData, linkData, VertexLabels -> "Name"]; infor = FindShortestPath[gFull, "La", "Ki"]

{"La", "Le", "Ka", "Ki"}

To visiualize it I needed to write my own function for the graph and the highlighting

(*make edges with its labels for GraphPlot*) kanten = Flatten[{#[[1, 1]] -> #[[1, 2]]} & /@ linkData]; beschriftung = linkData[[All, 2, 1, 2]]; pltDat = Transpose[{kanten, beschriftung}]; (*Get grouping function*) vertRand[vert_] := Prepend[Flatten@ Transpose[{vertexData[[All, 1]], vertexData[[All, 2, 2]]}], vert] /. List -> Switch (*give a list of verticies then those will be highlighted in Red, you \ can also give an empty list*) (*Here with Frameimg the Verticies*) ClearAll[grPltHigh]; grPltHigh[vertLst_: {}, edgLst_: {}] := Module[{highVert = vertLst, highEdge = edgLst, markEdge}, markEdge = {#[[1]], #[[2]]} & /@ EdgeList[highEdge]; GraphPlot[pltDat, MultiedgeStyle -> 0.5, EdgeRenderingFunction -> (If[#3 == "mail", {If[(*edge highlighting*) MemberQ[markEdge, #2] || MemberQ[markEdge, Reverse@#2], Red, Blue], Thickness[0.009], Line[#1], Black, Inset[#3, Mean[#1], Automatic, Automatic, Background -> Lighter@LightGray]}, {If[(*edge highlighting*) MemberQ[markEdge, #2] || MemberQ[markEdge, Reverse@#2], Red, Green], Thickness[0.009], Line[#1], Black, Inset[#3, Mean[#1], Automatic, Automatic, Background -> Lighter@LightGray]}] &), VertexRenderingFunction -> ( If[vertRand[#2] == "L", {Lighter@Orange, EdgeForm[Black], If[(*for highlighting as underlying rectangle in Red is made*) MemberQ[highVert, #2], {Red, Rectangle[#1 - {boxSize, boxSize}*1.3, #1 + {boxSize, boxSize}*1.3]}], Rectangle[#1 - {boxSize, boxSize}, #1 + {boxSize, boxSize}], Black, Text[#2, #1]}, If[vertRand[#2] == "K", {LightBlue, EdgeForm[Black], If[(*for highlighting as underlying rectangle in Red is made*) MemberQ[highVert, #2], {Red, Rectangle[#1 - {boxSize, boxSize}*1.3, #1 + {boxSize, boxSize}*1.3]}], Rectangle[#1 - {boxSize, boxSize}, #1 + {boxSize, boxSize}], Black, Text[#2, #1]}]] &)]

use grPltHigh[vertex list,edge list] or grPltHigh[] for pure graph

Usage with the result infor:

grPltHigh[{}, PathGraph[infor]]

enter image description here

I acctually hoped to use the custom property directly in calculations (e.g. setting EdgeWeight from it in FindShortestPath). Instead I have to use a filter function to derive different graphs for the according links "mail" or "meet".

(*This function filters the needed item per property*) edgeFilter[inList_,filtProp_,filtItem_]:=Module[{inLst=inList,fltPrp=filtProp,fltIt=filtItem,ergLst}, ergLst=fltPrp/.#[[2]]&/@inLst(*Uses the List of Property for each edge to retrieve its value*); Pick[inLst,ergLst,filtItem](*Gives only the edges that contain the item of property*) ];

Using it for getting a mail path between La and Ke:

gMail=Graph[edgeFilter[linkData,"interaction","mail"],VertexLabels->"Name"]; mailShort=FindShortestPath[gMail,"La","Ke"]; grPltHigh[{},PathGraph@mailShort]

Blockquote

It is done for "meet" pathes accordingly. To find the links between the groups one needs to setup a group graph. I have done it by replacing the vertex names with the group names and getting only the edges between different groups.

(*Derive a list of replacement for the vertex with its group*) replRuleGroup=Flatten[{#[[1]]->#[[2,2]]}&/@vertexData]; (*Replace the vertex name by the group name*) groupData=linkData/.replRuleGroup; (*Pick only links that go from one group to the other*) interGroup=Not[#[[ 1, 1]]==#[[1, 2]]]&/@groupData; groupLink=Pick[groupData,interGroup,True]

In this case the result is the two edges from K group to L group.

{Property[ "L" <-> "K", {EdgeLabels -> "meet", EdgeStyle -> RGBColor[0, 1, 0], "interaction" -> "meet"}], Property["L" <-> "K", {EdgeLabels -> "mail", EdgeStyle -> RGBColor[0, 0, 1], "interaction" -> "mail"}]}

In the end it was way more complicated than assumed. The "custom property" in Property would be more usefull if it could be used in graph related functions as a filter property e.g. for EgdeCost, EdgeWeight, EdgeCapacity. I did played around with it a lot but ended up with nothing better than this long solution above. Quite disappointing. I really would like to know how to make proper use of "custom property" in Property.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I note that gFull not very same to the the topic? $\endgroup$ Commented Dec 26, 2016 at 14:04
  • $\begingroup$ If you see it drawn, it is wrong I agree. Therefore I wrote an own function for drawing. For the purpose of finding a path from one to another vertex it works as MMA does not makes a difference whatever the "interaction" item is. Graph overwrites the EdgeStyle definitions of edges linking the same vertecies. $\endgroup$ Commented Dec 26, 2016 at 14:45
0
$\begingroup$

Regarding the representation of a multigraph you can have a look at this question: How can I display a multigraph with different colored edges?.

Finding out which nodes are reachable you can use FindPath and FindShortestPath.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Have you read the original question?Which don't mean that color demand maybe. $\endgroup$ Commented Dec 22, 2016 at 23:48
  • $\begingroup$ @yode If you refer to the linked article you will see that it does represent multigraphs and that different colors can be used to represent different types of edges (1=mail, 2=meet, etc.). Les us know if something is unclear. $\endgroup$ Commented Dec 23, 2016 at 0:17

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.