I thought it would be nice to have a discussion of little pieces of Mathematica code that can help when working with graphs and networks. Here for example, one to undirect graphs when needed:
ToUndirectedGraph[dirGraph_] :=
Graph[VertexList@dirGraph, #[[1]] \[UndirectedEdge] #[[2]] & /@
Union[Sort[{#[[1]], #[[2]]}] & /@ EdgeList@dirGraph]]
or what about a graph planarity check function (i.e. adding any edge would destroy its planarity):
MaxPlanarQ[graph_] :=
PlanarGraphQ[graph] &&
With[{pos =
Select[Position[Normal@AdjacencyMatrix@graph,
0], #[[1]] < #[[2]] &],
vertex = VertexList[graph],
edges = EdgeList[graph]
},
val = True;
Do[If[PlanarGraphQ[
Graph[Append[edges,
vertex[[i[[1]]]] \[UndirectedEdge] vertex[[i[[2]]]]]]],
val = False; Break[]], {i, pos}]; Return[val]]
And one to produce random permutations for a given graph with the indicated number n of nodes:
PermuteGraph[g_, n_] :=
Table[AdjacencyMatrix@
Graph[RandomSample[VertexList@g], EdgeList@g], {n}]
What about code for counting sizes of graph automorphism groups? I have some, but it uses Saucy, an open-source software that has been tested to be (surprisingly) in practice very fast, despite the NP question underlying this task (unknown whether it has a polynomial time algorithm or it is NP-complete). There is a function in Combnatorica but you can read about its drawbacks in the
graph automorphism page in MathWorld.
