performance tuning - Faster way to extract partial data from AdjacencyMatrix

I am dealing with a lot of Graph objects. One task is to obtain an Id for each of them. So I first used

g = Graph[{1 -> 2, 1 -> 3, 4 -> 2, 3 -> 5, 4 -> 5, 7 -> 2, 4 -> 7, 3 -> 8}];

GraphId[g_] := Module[{}, AdjacencyMatrix@CanonicalGraph@g]

FullForm@GraphId@g

which gives

SparseArray[
  Automatic,
  List[7,7],
  0,
  List[
    1,
    List[

      List[0,2,5,5,6,8,8,8],
      List[List[5],List[7],List[4],List[6],List[7],List[7],List[3],List[6]]
    ],
    List[1,1,1,1,1,1,1,1]
  ]
]

I have to reduce this result to save space. The first approach is not to including List[1,1,1,1,1,1,1,1] in the result. So I tried

ToData[g_] := (Last@ToExpression@StringReplace[ToString@FullForm@g, "Graph" -> "List"])[[1]]
GraphIdReduced[g_] := Module[{}, ToData@CanonicalGraph@g]

FullForm@GraphIdReduced@g

which gives

SparseArray[
  Automatic,
  List[7,7],
  0,
  List[
    1,
    List[

      List[0,2,5,5,6,8,8,8],
      List[List[5],List[7],List[4],List[6],List[7],List[7],List[3],List[6]]
    ],
    Pattern
  ]
]

Of course I can use the same approach to reduce the result much further. But the problem is the above method is very slow.

gT=Table[g,{i,1,10^5}];
AbsoluteTiming[GraphId/@gT][[1]]

AbsoluteTiming[GraphIdReduced/@gT][[1]]

gives

1.185602
14.445625

, and for 10^6 times, the difference is 12.386422 vs 146.539146.

Maybe this is because the string operations are slow, but I don't know how to do without it. Graph and SparseArray are atomic object and I can't not use Apply to change their Head to List and then locate the contents I care about.

So how to extract some data from the above result more quickly?

In fact, the data I need is only

Answer

You can use the new-in-Version-10 properties "RowPointers" and "ColumnIndices" of a SparseArray object:

g = Graph[{1 -> 2, 1 -> 3, 4 -> 2, 3 -> 5, 4 -> 5, 7 -> 2, 4 -> 7, 3 -> 8}];
sa=AdjacencyMatrix@CanonicalGraph@g;

{sa["RowPointers"],Flatten[sa["ColumnIndices"]]}
(* {{0,2,5,5,6,8,8,8},{5,7,4,6,7,7,3,6}} *)

Or define a function

foo=Function[{s},{s@#,Flatten@s@#2}&@@{"RowPointers","ColumnIndices"}]
foo@sa
(* {{0,2,5,5,6,8,8,8},{5,7,4,6,7,7,3,6}} *)

Alternatively, you can use the second part of "NonzeroPositions" instead of "ColumnIndices":

{sa["RowPointers"],sa["NonzeroPositions"][[All,2]]}
(* {{0,2,5,5,6,8,8,8},{5,7,4,6,7,7,3,6}} *)

Note: There has been few additions to the still-undocumented SparseArray "Properties", including "RowPointers" and "ColumnIndices" used above.

sa["Properties"]

(* {AdjacencyLists, Background, ColumnIndices, Density, NonzeroPositions,
    NonzeroValues, PatternArray, Properties, RowPointers} *)