Group Abstract Group Abstract

Message Boards Message Boards

Little pieces of code for graph and networks theory

GROUPS:
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.
POSTED BY: Hector Zenil
Answer
8 months ago
Great! I used these functions to start the Graph, Undirected graph, and Planar graph packages on Wikicode. This discussion is listed as a reference to find improvements and expansions. How to incorporate open-source external libraries is still open to discussion. Other packages import data from external sources, so including initialization code to load an external package as part of a Wikicode package seems reasonable to me.
POSTED BY: Michael Hale
Answer
8 months ago
Cool!
Is there any reason not to use built-in UndirectedGraph function for converting directed graphs to undirected graph?
POSTED BY: Jaebum Jung
Answer
8 months ago
Good catch! I've removed that one.
POSTED BY: Michael Hale
Answer
8 months ago
Yes, good catch, the ToUndirectedGraph must have been something written pre Mathematica 8 when the built-in function was introduced. Nice to hear the proposal found some echo from others.
POSTED BY: Hector Zenil
Answer
8 months ago
What about some simple code to calculate graph spectra:
Spectrum[adjmatrix_, firstkeigenvalues_: 0] :=
If[firstkeigenvalues == 0, Eigenvalues[AdjacencyMatrix[adjmatrix]],
  Eigenvalues[AdjacencyMatrix[adjmatrix], firstkeigenvalues]]
Specially because it seems the Combinatorica alternative has some issues in M- 9.

And now we can do the classical example of cospectral graphs:
Spectrum /@ {g1 = VertexAdd[GraphData[{"Cycle", 4}], 5],
  g2 = GraphData[{"Star", 5}]}
And do all sort of fancy things with GraphData that has a couple of spectra related properties.
POSTED BY: Hector Zenil
Answer
7 months ago