1
$\begingroup$

Noticed some bizarre behavior when subgraphing on weighted graphs, which probably extends to graphs with arbitrary edge properties.

I construct a weighted graph with five edges, defining a specific vertex and edge order:

    EdgeWeightList[g_] := 
 Table[PropertyValue[{g, e}, EdgeWeight], {e, EdgeList[g]}]

G = Graph[{4, 2, 1, 3, 5}, {1 <-> 2, 2 <-> 3, 3 <-> 1, 3 <-> 4, 
   3 <-> 5}, EdgeWeight -> {30, 20, 10, 50, 40}, 
  VertexLabels -> "Name", EdgeLabels -> "EdgeWeight", ImageSize -> 250]
VertexList[G]
Thread[EdgeList[G] -> EdgeWeightList[G]]

enter image description here Next I delete edges that fall below a specific threshold.

F = G;
Do[If[PropertyValue[{G, e}, EdgeWeight] < 35, 
  F = EdgeDelete[F, e]], {e, EdgeList[G]}]
F
Options[F]
VertexList[F]
Thread[EdgeList[F] -> EdgeWeightList[F]]

enter image description here

Now I compute and subgraph with the largest weakly connected component of the graph in order to remove the disconnected vertices. Now, as Subgraph does not support weighted graphs (which I think it should, and so should as many other graph measures / operations as possible), I use Options to copy the all of the options defined on the original graph, including the edge weights. However, there are two problems here: one, the weakly connected component does not maintain a consistent ordering of vertices with respect to the original graph, and two, the edges also do not maintain a consistent ordering with respect to the original graph, as when the order of the vertices change, the effective ordering of the edges changes as well. Note also that this method will not actually work when there is more than one weakly connected component with edges, as Options will return more edge weights (or properties in general) than there are edges in the subgraph, and will not build the graph correctly.

W = WeaklyConnectedComponents[F][[1]]
Options[F]
S = Subgraph[F, W, Options[F]]
VertexList[S]
Thread[EdgeList[S] -> EdgeWeightList[S]]

enter image description here

Explicitly specifying the weakly connected component with the correct ordering does work (but again, with the same limitations as above).

W = {4, 3, 5}
Options[F]
S = Subgraph[F, W, Options[F]]
VertexList[S]
Thread[EdgeList[S] -> EdgeWeightList[S]]

enter image description here

While the above is more an unfortunate consequence of weakly connected component vertex ordering and the lack of Subgraph support for properties, it is fairly reasonable to expect specifying the edge list in the same order as the edge weights to match weights to the appropriate edges, but this is not that case, as the incorrect order of the vertices is still an issue:

W = WeaklyConnectedComponents[F][[1]]
Thread[EdgeList[F] -> EdgeWeightList[F]]
Options[F]
S = Subgraph[F, W, EdgeList[F], Options[F]]
VertexList[S]
Thread[EdgeList[S] -> EdgeWeightList[S]]

enter image description here

$\endgroup$
  • $\begingroup$ The same things and worst happen with mixed and multigraphs, I'll post more edge-weight bugs soon. $\endgroup$ – M.R. Jun 1 '15 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.