1
$\begingroup$

A 2D graph has 500 nodes where the nodes are arranged in a rectangular grid of 12000 X 9500 m. 20 nodes on horizontal and 25 nodes on vertical axis of the grid. The inter-node (neighbor) distance is 500 meters. The edge between two nodes has a weight. The circular coverage of a node is 350 meters. That is two nodes have overlapping coverage. Then there are 10000 randomly deployed sensors over the whole coverage area. The number of sensors within the overlapping coverage area between two cells will decide the weight of the edge between the nodes. How to generate this connected graph in Mathematica?

Note: The rectangular grid does not mean that the two neighbour nodes are somehow how connected. I mentioned/brought this just to easily depict the node distribution and their coordinates.

So, we can get the coordinates using GridGraph as below

Remove["Global`*"];
SeedRandom[1];
g = GridGraph[{25, 20}];
coords = 500*(GraphEmbedding[g] - 1);

Then there can be an edge (with non-zero weight) if there are some sensors within their overlapped coverage.

Two diagonal nodes can also have an edge with some nonzero weight if there are some sensors within their overlapped coverage.

$\endgroup$
5
  • $\begingroup$ Hi dipak, could you provide us with your attempt on writing this code? $\endgroup$
    – alex
    Apr 11, 2023 at 10:03
  • $\begingroup$ "A graph has 500 nodes. The inter-node distance is 500 meters." This is vague. Do you mean every node pair must be 500m apart? or just some of them, or is this a maximum / minimum, or are you talking about the whole graph's diameter ? $\endgroup$
    – flinty
    Apr 11, 2023 at 11:01
  • $\begingroup$ "... is around 300 meters" is also too vague. How do you want us to generate the coverage - using what distribution? And in what dimension? Is this a 2D or 3D? $\endgroup$
    – flinty
    Apr 11, 2023 at 11:05
  • $\begingroup$ @flinty see my edit. $\endgroup$
    – MGK
    Apr 11, 2023 at 12:25
  • $\begingroup$ Are you sure you don't mean 9500 instead of 8500? 8500 wouldn't cover the whole grid. $\endgroup$
    – flinty
    Apr 11, 2023 at 13:53

1 Answer 1

3
$\begingroup$

Something like this maybe, using GridGraph.

Remove["Global`*"];
SeedRandom[1];
g = GridGraph[{25, 20}];
coords = 500*(GraphEmbedding[g] - 1);
g = GridGraph[{25, 20}, VertexCoordinates -> coords];
sensorPositions = 
  RandomVariate[UniformDistribution[{{0, 9500}, {0, 12000}}], 10000];
nf = Nearest[sensorPositions];
weight[edge_] := Length[Intersection[
   nf[coords[[edge[[1]]]], {Infinity, 300}],
   nf[coords[[edge[[2]]]], {Infinity, 300}]]
  ]
weights = weight /@ EdgeList[g];

maxweight = Max[weights];
shapeFunc = 
  With[{w = 
      PropertyValue[{g, #2}, EdgeWeight]}, {AbsoluteThickness[
      10*w/maxweight], GrayLevel[w/maxweight], Line@#1}] &;
g = Graph[g, VertexCoordinates -> coords, EdgeWeight -> weights, 
   EdgeShapeFunction -> shapeFunc];
Show[g, Graphics[{Blue, AbsolutePointSize[1], 
   Point[sensorPositions]}]]

enter image description here

$\endgroup$
4
  • $\begingroup$ why there is no edge between diagonal nodes? Lets say we have coverage of each node as 350, then there will be overlapped coverage between the diagonal nodes also! $\endgroup$
    – MGK
    Apr 11, 2023 at 22:31
  • $\begingroup$ see my edit. I have updated my scenario. $\endgroup$
    – MGK
    Apr 11, 2023 at 22:41
  • $\begingroup$ @MGK why did you not put this in your question originally? I cannot delete my answer. You are wasting people's time if you don't properly specify what you want in your question. $\endgroup$
    – flinty
    Apr 12, 2023 at 10:55
  • $\begingroup$ I had to update my question as it was not so clear or you got it wrong. In my question, I never mentioned that the diagonal nodes cannot have edge. I am not asking you to delete your answer. I have already accepted it! $\endgroup$
    – MGK
    Apr 12, 2023 at 15:11

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.