2
$\begingroup$

There are various variants of graph coloring, such as when I want to compute the star chromatic number of a graph, Mathematica seems not to provide relevant functions.

Fortunately, the software ColPack offers this functionality. However, it supports the MTX format. So, the question is:

  • How can I write a graph in MTX format?

And

  • how can the MTX format be converted into a graph format?

Of course, I would like to perform these operations in Mathematica.

The following is an example (bcsstk01.mtx） in the directory ColPack-master/Graphs directory of the source code of ColPack.

%%MatrixMarket matrix coordinate real symmetric
48 48 224
1 1  2.8322685185200e+06
5 1  1.0000000000000e+06
6 1  2.0833333333300e+06
7 1 -3.3333333333300e+03
11 1  1.0000000000000e+06
19 1 -2.8000000000000e+06
25 1 -2.8935185185200e+04
30 1  2.0833333333300e+06
2 2  1.6354475308600e+06
4 2 -2.0000000000000e+06
6 2  5.5555555555500e+06
8 2 -6.6666666666700e+03
10 2 -2.0000000000000e+06
20 2 -3.0864197530900e+04
24 2  5.5555555555500e+06
26 2 -1.5979166666700e+06
3 3  1.7243672839500e+06
4 3 -2.0833333333300e+06
5 3 -2.7777777777800e+06
9 3 -1.6800000000000e+06
21 3 -1.5432098765400e+04
23 3 -2.7777777777800e+06
27 3 -2.8935185185200e+04
28 3 -2.0833333333300e+06
4 4  1.0033333333300e+09
8 4  2.0000000000000e+06
10 4  4.0000000000000e+08
22 4 -3.3333333333300e+06
27 4  2.0833333333300e+06
28 4  1.0000000000000e+08
5 5  1.0675000000000e+09
7 5 -1.0000000000000e+06
11 5  2.0000000000000e+08
21 5  2.7777777777800e+06
23 5  3.3333333333300e+08
29 5 -8.3333333333300e+05
6 6  1.5353333333300e+09
12 6 -2.0000000000000e+06
20 6 -5.5555555555500e+06
24 6  6.6666666666700e+08
25 6 -2.0833333333300e+06
30 6  1.0000000000000e+08
7 7  2.8322685185200e+06
11 7 -1.0000000000000e+06
12 7  2.0833333333300e+06
13 7 -2.8000000000000e+06
31 7 -2.8935185185200e+04
36 7  2.0833333333300e+06
8 8  1.6354475308600e+06
10 8  2.0000000000000e+06
12 8  5.5555555555500e+06
14 8 -3.0864197530900e+04
18 8  5.5555555555500e+06
32 8 -1.5979166666700e+06
9 9  1.7243672839500e+06
10 9 -2.0833333333300e+06
11 9 -2.7777777777800e+06
15 9 -1.5432098765400e+04
17 9 -2.7777777777800e+06
33 9 -2.8935185185200e+04
34 9 -2.0833333333300e+06
10 10  1.0033333333300e+09
16 10 -3.3333333333300e+06
33 10  2.0833333333300e+06
34 10  1.0000000000000e+08
11 11  1.0675000000000e+09
15 11  2.7777777777800e+06
17 11  3.3333333333300e+08
35 11 -8.3333333333300e+05
12 12  1.5353333333300e+09
14 12 -5.5555555555500e+06
18 12  6.6666666666700e+08
31 12 -2.0833333333300e+06
36 12  1.0000000000000e+08
13 13  2.8360994695000e+06
17 13 -2.1492852945100e+06
18 13  2.3591618040200e+06
19 13 -3.3333333333300e+03
23 13 -1.0000000000000e+06
37 13 -2.8935185185200e+04
42 13  2.0833333333300e+06
43 13 -3.8309509817100e+03
47 13 -1.1492852945100e+06
48 13  2.7582847068300e+05
14 14  1.7674107444600e+06
15 14  5.1792213181600e+05
16 14  4.2985705890200e+06
18 14 -5.5555555555500e+06
20 14 -6.6666666666700e+03
22 14  2.0000000000000e+06
38 14 -1.5979166666700e+06
44 14 -1.3196321359900e+05
45 14 -5.1792213181600e+05
46 14  2.2985705890200e+06
15 15  3.8900380684800e+06
16 15 -2.6349902747000e+06
17 15  2.7777777777800e+06
21 15 -1.6800000000000e+06
39 15 -2.8935185185200e+04
40 15 -2.0833333333300e+06
44 15 -5.1792213181600e+05
45 15 -2.1656707845300e+06
46 15 -5.5165694136700e+05
16 16  1.9757206353100e+09
20 16 -2.0000000000000e+06
22 16  4.0000000000000e+08
39 16  2.0833333333300e+06
40 16  1.0000000000000e+08
44 16 -2.2985705890200e+06
45 16  5.5165694136600e+05
46 16  4.8619365099000e+08
17 17  1.5273465154700e+09
18 17 -1.0977973133200e+08
19 17  1.0000000000000e+06
23 17  2.0000000000000e+08
41 17 -8.3333333333300e+05
43 17  1.1492852945100e+06
47 17  2.2972466123600e+08
48 17 -5.5717351077900e+07
18 18  1.5641114371100e+09
24 18 -2.0000000000000e+06
37 18 -2.0833333333300e+06
42 18  1.0000000000000e+08
43 18 -2.7582847068300e+05
47 18 -5.5717351077900e+07
48 18  1.0941196003800e+07
19 19  2.8322685185200e+06
23 19  1.0000000000000e+06
24 19  2.0833333333300e+06
43 19 -2.8935185185200e+04
48 19  2.0833333333300e+06
20 20  1.6354475308600e+06
22 20 -2.0000000000000e+06
24 20 -5.5555555555500e+06
44 20 -1.5979166666700e+06
21 21  1.7243672839500e+06
22 21 -2.0833333333300e+06
23 21  2.7777777777800e+06
45 21 -2.8935185185200e+04
46 21 -2.0833333333300e+06
22 22  1.0033333333300e+09
45 22  2.0833333333300e+06
46 22  1.0000000000000e+08
23 23  1.0675000000000e+09
47 23 -8.3333333333300e+05
24 24  1.5353333333300e+09
43 24 -2.0833333333300e+06
48 24  1.0000000000000e+08
25 25  6.0879629629600e+04
29 25  1.2500000000000e+06
30 25  4.1666666666700e+05
31 25 -4.1666666666700e+03
35 25  1.2500000000000e+06
26 26  3.3729166666700e+06
28 26 -2.5000000000000e+06
32 26 -8.3333333333300e+03
34 26 -2.5000000000000e+06
27 27  2.4117129629600e+06
28 27 -4.1666666666700e+05
33 27 -2.3550000000000e+06
28 28  1.5000000000000e+09
32 28  2.5000000000000e+06
34 28  5.0000000000000e+08
29 29  5.0183333333300e+08
31 29 -1.2500000000000e+06
35 29  2.5000000000000e+08
30 30  5.0250000000000e+08
36 30 -2.5000000000000e+06
31 31  3.9858796296300e+06
35 31 -1.2500000000000e+06
36 31  4.1666666666700e+05
37 31 -3.9250000000000e+06
32 32  3.4114969135800e+06
34 32  2.5000000000000e+06
36 32  6.9444444444400e+06
38 32 -3.8580246913600e+04
42 32  6.9444444444500e+06
33 33  2.4310030864200e+06
34 33 -4.1666666666700e+05
35 33 -3.4722222222200e+06
39 33 -1.9290123456800e+04
41 33 -3.4722222222200e+06
34 34  1.5041666666700e+09
40 34 -4.1666666666700e+06
35 35  1.3351666666700e+09
39 35  3.4722222222200e+06
41 35  4.1666666666700e+08
36 36  2.1691666666700e+09
38 36 -6.9444444444400e+06
42 36  8.3333333333300e+08
37 37  3.9858796296300e+06
41 37 -1.2500000000000e+06
42 37  4.1666666666700e+05
43 37 -4.1666666666700e+03
47 37 -1.2500000000000e+06
38 38  3.4114969135800e+06
40 38  2.5000000000000e+06
42 38 -6.9444444444500e+06
44 38 -8.3333333333300e+03
46 38  2.5000000000000e+06
39 39  2.4310030864200e+06
40 39 -4.1666666666700e+05
41 39  3.4722222222200e+06
45 39 -2.3550000000000e+06
40 40  1.5041666666700e+09
44 40 -2.5000000000000e+06
46 40  5.0000000000000e+08
41 41  1.3351666666700e+09
43 41  1.2500000000000e+06
47 41  2.5000000000000e+08
42 42  2.1691666666700e+09
48 42 -2.5000000000000e+06
43 43  6.4710580611300e+04
47 43  2.3992852945100e+06
48 43  1.4083819598400e+05
44 44  3.5048798802700e+06
45 44  5.1792213181600e+05
46 44 -4.7985705890200e+06
45 45  4.5773837474900e+06
46 45  1.3499027470000e+05
46 46  2.4723873019800e+09
47 47  9.6167984880400e+08
48 47 -1.0977973133200e+08
48 48  5.3127810377500e+08

./ColPack -f ../../Graphs/bcsstk01.mtx -m STAR
Out: 11

But I do not know what the graph in the example is. I don't understand what the very long decimal numbers (like 2.8322685185200e+06) in the third column in the MTX-file. Will it affect the imformation of the entire graph?

On the contrary, I would like to compute the star chromatic number of the graph below, and I also don't know how to convert it into the MTX format like the above.

G = GridGraph[{2, 2, 2, 3}, VertexLabels -> "Name"]
Improve this question
$\endgroup$
5
  • $\begingroup$ Look up "MTX" in the help. MMA can import and export this format. $\endgroup$
    – Daniel Huber
    Sep 2 at 6:57
  • $\begingroup$ @DanielHuber Thank you, I knew that "MTX" is supported (sorry, I forgot to mention it in the main text). However, I can only obtain some matrices or matrix plots, rather than graphs. For example, s = Import["~\\ColPack-master\\Graphs\ \\bcsstk01.mtx", "Graphics"] $\endgroup$
    – licheng
    Sep 2 at 7:05
  • $\begingroup$ I do not know MTX well, but I think it is thought for 3D graphics. And a Graph is 2D. $\endgroup$
    – Daniel Huber
    Sep 2 at 8:08
  • $\begingroup$ @DanielHuber Graphs can also be represented as matrices, primarily the adjacency matrices. However, I don't understand what the very long decimal numbers (like 2.8322685185200e+06) in the third column in the MTX-matrix. $\endgroup$
    – licheng
    Sep 2 at 8:29
  • $\begingroup$ @creidhne Thanks! I know. I am concerned these numbers in the third column will effect the information of whole graph $\endgroup$
    – licheng
    Sep 3 at 0:09

1 Answer 1

Reset to default
1
$\begingroup$

I assume we're working with adjacency matrices that you want to import or export in MTX format, and the goal is to create an adjacency matrix from a Graph.

The bcsstk01.mtx file isn't an adjacency matrix. Instead, let's look at the graph in your example. We use AdjacencyMatrix to find an adjacency matrix from the graph, and VertexChromaticNumber to find the graph's chromatic number.

g = GridGraph[{2, 2, 2, 3}, VertexLabels -> "Name"];
amat = AdjacencyMatrix[g];
VertexChromaticNumber[g]
(*2*)

Exporting the amat to MTX is simple as a file, or as a string as an example.

ExportString[amat, "MTX"]

%%MatrixMarket matrix coordinate integer symmetric
%Created with the Wolfram Language : www.wolfram.com
24 24 52
2 1 1
3 1 1
4 2 1
[snip]
24 20 1
24 22 1
24 23 1

FindVertexColoring was introduced in v13. Use it to color the graph vertices.

FindVertexColoring[g, ColorData[106,"ColorList"]];(*introduced v13*)
Annotate[g,
  {VertexStyle -> Thread[VertexList[g] -> %],
    VertexSize -> .5, GraphLayout -> "SpringEmbedding"}]

vertex colored graph

Use MatrixPlot to plot the adjacency matrix.

MatrixPlot[amat]

plot of adjacency matrix

Answer for Comment:

For graphs, these decimals seem to be considered as 1 (with the first two columns representing vertices, and their adjacency).

The data in the bcsstk01.mtx file is not an adjacency matrix. We can force the data with Unitize that replaces the decimal values with 1. AdjacencyGraph makes a graph from amat.

(*data = Import["bcsstk01.mtx"];*)(*data imported from MTX file*)
amat = Unitize[amat];
MatrixPlot[amat]
g = AdjacencyGraph[amat]

adjacency matrix for MTX file

graph from adjacency matrix

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you see math.nist.gov/MatrixMarket/formats.html? For graphs, these decimals seem to be considered as 1 (with the first two columns representing vertices, and their adjacency). Of course, this is my interpretation and may not be correct. $\endgroup$
    – licheng
    Sep 3 at 3:41
  • 1
    $\begingroup$ @licheng I think the code I've added will show how you can use the data from the MTX file as an adjacency matrix. $\endgroup$
    – creidhne
    Sep 3 at 4:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.