Workshop:
Introductory Graph Computation

Jaebum Jung, Charles Pooh, Yan Zhuang

Mathematica Algorithms R&D, Wolfram Research

What is a Graph?

In its simplest form, a graph is a collection of points joined together in pairs by lines.

The points are referred to as vertices and the lines are referred to as edges.

A graph with 10 vertices and 15 edges:

PetersenGraph[5,2,VertexSize-> 0.18,EdgeStyle-> Thick]

Graph Representation [link]

Graphs are first class citizens in Mathematica, and can be used as input, outputs, in programs and in documents.

Graph[{(Subscript[e, 1]),(Subscript[e, 2]),…}] yields a graph with edges (Subscript[e, j]).
Graph[{(Subscript[v, 1]),(Subscript[v, 2]),…}, {(Subscript[e, 1]),(Subscript[e, 2]),…}] yields the graph with vertices (Subscript[v, i]) and edges (Subscript[e, j]).
Graph[{…,(Subscript[w, i])[(Subscript[v, i]),…],…},{…,(Subscript[w, j])[(Subscript[e, j]),…],…}] yields a graph with vertex and edge properties defined by symbolic wrappers (Subscript[w, i]).

Undirected graphs & UndirectedEdge (<->)

Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]1}]

Directed graphs & DirectedEdge (->)

Graph[{1\[DirectedEdge]2,2\[DirectedEdge]3,3\[DirectedEdge]1}]

Graphs & Wrappers (Button, EventHandler, PopupWindow, Style, Tooltip, …)

Graph[{1,2,Style[3,Red]},{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]1,Blue}]

Graph Options (VertexShape, VertexStyle, VertexSize, EdgeStyle, …)

Options[Graph]

Graph[{1\[DirectedEdge]2,2\[DirectedEdge]3,3\[DirectedEdge]1},VertexShapeFunction->"Diamond"]

Graph Representation

•  Graph[…] displays in a notebook as a plot of a graph

•  Graph[…] is converted to an optimized standard form

•  Graph[…] is treated as a raw object by functions like AtomQ, and for purposes of pattern matching

•  Any expression can be used as vertices

web={"Aphid"\[DirectedEdge]"Ladybug","Beetle"\[DirectedEdge]"Mouse","Caterpillar"\[DirectedEdge]"Beetle","Caterpillar"\[DirectedEdge]"Mouse","Caterpillar"\[DirectedEdge]"Towhee","Grasshopper"\[DirectedEdge]"Mouse","Grasshopper"\[DirectedEdge]"Towhee","Ladybug"\[DirectedEdge]"Towhee","Louse"\[DirectedEdge]"Mouse","Mosquito"\[DirectedEdge]"Dragonfly","Mosquito"\[DirectedEdge]"Towhee","Mouse"\[DirectedEdge]"Owl","Sunflower"\[DirectedEdge]"Aphid","Sunflower"\[DirectedEdge]"Caterpillar","Sunflower"\[DirectedEdge]"Grasshopper","Sunflower"\[DirectedEdge]"Louse","Towhee"\[DirectedEdge]"Owl"};

shapes={"Sunflower"->,"Aphid"->,"Ladybug"->,"Towhee"->,"Owl"->,"Grasshopper"->,"Louse"->,"Caterpillar"->,"Beetle"->,"Mosquito"->,"Dragonfly"->,"Mouse"->};

Graph[web,VertexShape-> shapes,VertexSize-> 0.9]

Construction of Graphs

Graphs can be constructed in variety of ways:

Graph, UndirectedEdge (<->) and DirectedEdge (->)

Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]1}]

Curated Graphs

GraphData — collection of theoretical graphs

GraphData["PappusGraph"]

ExampleData — collection of empirical graphs

ExampleData[{"Graphs","ZakaryKarateClub"}]

SocialMediaData . PolyhedronData . ChemicalData . WordData . CountryData . IsotopeData

Graph[Flatten[Thread[#->CountryData[#,"BorderingCountries"]]&/@CountryData["SouthAmerica"]],VertexShapeFunction-> "Name"]

Parametric Graphs

CompleteGraph — generate a complete graph or a complete k-partite graph

ButterflyGraph . CirculantGraph . CompleteKaryTree . CycleGraph . DeBruijnGraph . GridGraph . HararyGraph . HypercubeGraph . KaryTree . KnightTourGraph . PathGraph . PetersenGraph . StarGraph . TreeGraph . TuranGraph . WheelGraph

Grid[{{CompleteGraph[5,PlotLabel-> "CompleteGraph"],ButterflyGraph[2,PlotLabel-> "ButterflyGraph"],CirculantGraph[10,{2,4},PlotLabel-> "CirculantGraph"],CycleGraph[5,PlotLabel-> "CycleGraph"],GridGraph[{2,2,2,2},PlotLabel-> "GridGraph"],HararyGraph[4,8,PlotLabel-> "HararyGraph"]},{HypercubeGraph[4,PlotLabel-> "HypercubeGraph"],KnightTourGraph[4,4,PlotLabel-> "KnightTourGraph"],PathGraph[Range[25],PlotLabel-> "PathGraph"],PetersenGraph[5,2,PlotLabel-> "PetersenGraph"],StarGraph[6,PlotLabel-> "StarGraph"],TuranGraph[5,2,PlotLabel-> "TuranGraph"]}},Spacings-> {2,2}]

VertexCount[ButterflyGraph[n,k]]

EdgeCount[ButterflyGraph[n,k]]

Random Graphs

RandomGraph — generate random graphs following a graph distribution

UniformGraphDistribution . BernoulliGraphDistribution . BarabasiAlbertGraphDistribution . PriceGraphDistribution . WattsStrogratzGraphDistribution . DegreeGraphDistribution

RandomGraph[{6,7},5]

RandomGraph[UniformGraphDistribution[6,7],5]

RandomGraph[BernoulliGraphDistribution[6,0.7],5]

RandomGraph[BarabasiAlbertGraphDistribution[6,2],5]

Matrix Graphs

AdjacencyGraph — construct a graph from an adjacency matrix

IncidenceGraph . KirchhoffGraph . WeightedAdjacencyGraph .

AdjacencyGraph[{{0,0,1,1,0,1,0,0,0,0},{0,0,0,1,1,0,1,0,0,0},{1,0,0,0,1,0,0,1,0,0},{1,1,0,0,0,0,0,0,1,0},{0,1,1,0,0,0,0,0,0,1},{1,0,0,0,0,0,1,0,0,1},{0,1,0,0,0,1,0,1,0,0},{0,0,1,0,0,0,1,0,1,0},{0,0,0,1,0,0,0,1,0,1},{0,0,0,0,1,1,0,0,1,0}}]

Importing Graphs

Import — import graphs from different graph file formats

“GraphML” . “GXL” . “Graphlet” . “Pajek” . “TGF” . “DOT” . “DIMACS” . “Graph6” . “Sparse6” . “LEDA”

Operations and Modification of Graphs

Subgraph — extract subgraphs
NeighborhoodGraph . UndirectedGraph . DirectedGraph . GraphComplement . GraphUnion . GraphDifference . GraphIntersection . GraphDisjointUnion . BooleanGraph . EdgeAdd . EdgeDelete . VertexAdd . VertexDelete

Use of Context menu for graphs

RandomGraph[{10,20}]

Migrating Combinatorica and GraphUtilities to Graph

GraphUtilities

Needs["GraphUtilities`"]

g={1->3,1->2,1->4,2->3,2->4};
GraphPlot[g,VertexLabeling->True]

FindHamiltonianCycle[g]

g=UndirectedGraph[Graph[{1->3,1->2,1->4,2->3,2->4}]]

FindHamiltonianCycle[g][[1,All,1]]

Combinatorica

Needs["Combinatorica`"]

g=GraphUnion[CompleteGraph[3],CompleteGraph[4]];
ShowGraph[g]

ConnectedComponents[g]

g=GraphDisjointUnion[CompleteGraph[3],CompleteGraph[4]]

ConnectedComponents[g]

Build graph from image

NPR Power hungry: reinventing the us electric power grid

geo=GeoGraphics[{EdgeForm[Directive[Thick,]],FaceForm[None],Polygon[(Entity["United States", Entity["Country","UnitedStates"], "Entity[\"Country\", \"UnitedStates\"]", "country"])]},GeoRangePadding->{Scaled[0.7],0},ImageSize->500];

pic=;

r=ImageAdjust[ColorConvert[ColorQuantize[ColorNegate[pic],3],"GrayLevel"]];

grid=MorphologicalGraph[r,ImagePadding->{{25,14},{32,20}},ImageSize->{390,390}, VertexShapeFunction->None,EdgeShapeFunction->({CapForm["Butt"],Line[#1]}&),Prolog-> Inset[geo,Offset[{-18,-10},{435,269}]]]

Analysis

Major high-capacity electric transmission lines of the US electric grid form a disconnected network with two major sectors — eastern sector and western sector.

Robust subgrids that can sustain failures of two transmission lines.

{eastern,western}=Subgraph[grid,#]& /@ Take[ConnectedComponents[grid],2];

HighlightGraph[grid, {Style[Subgraph[grid,First[KEdgeConnectedComponents[eastern,2]]],,Thick],Style[Subgraph[grid,First[KEdgeConnectedComponents[western,2]]],,Thick]}]

Using GraphData to find computed property

g=Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,1\[UndirectedEdge]4,1\[UndirectedEdge]5,2\[UndirectedEdge]6,2\[UndirectedEdge]7,2\[UndirectedEdge]8,3\[UndirectedEdge]6,3\[UndirectedEdge]9,3\[UndirectedEdge]10,4\[UndirectedEdge]7,4\[UndirectedEdge]11,4\[UndirectedEdge]12,5\[UndirectedEdge]8,5\[UndirectedEdge]13,5\[UndirectedEdge]14,6\[UndirectedEdge]15,6\[UndirectedEdge]16,7\[UndirectedEdge]19,7\[UndirectedEdge]20,8\[UndirectedEdge]17,8\[UndirectedEdge]18,9\[UndirectedEdge]15,9\[UndirectedEdge]17,9\[UndirectedEdge]19,10\[UndirectedEdge]16,10\[UndirectedEdge]18,10\[UndirectedEdge]20,11\[UndirectedEdge]16,11\[UndirectedEdge]17,11\[UndirectedEdge]20,12\[UndirectedEdge]15,12\[UndirectedEdge]18,12\[UndirectedEdge]19,13\[UndirectedEdge]16,13\[UndirectedEdge]18,13\[UndirectedEdge]19,14\[UndirectedEdge]15,14\[UndirectedEdge]17,14\[UndirectedEdge]20}]

cg=CanonicalGraph[g]

candidate=Select[GraphData[20],(GraphData[#,"EdgeCount"]==40)&]

it=Select[candidate,(AdjacencyMatrix[GraphData[#,"CanonicalGraph"]]==AdjacencyMatrix[cg])&]

GraphData[it[[1]], "Properties"]

TSP art: How to make a continuous-line drawing from your images

Mona lisa:

monafile="http://www.math.uwaterloo.ca/tsp/data/ml/mona-lisa100K.tsp";

monalisa=Cases[Import[monafile,"Table"],{_Integer,x_?NumericQ,y_?NumericQ}:>{x,y}];

AbsoluteTiming[res=FindShortestTour[monalisa];]

Graphics[Line[monalisa[[res[[2]]]]]]

Producing a stippled image of 3d image:

img=ExampleData[{"TestImage3D","MRbrain"}]

i=RidgeFilter[img];
b=ImageAdjust@ColorQuantize[ColorConvert[i,"Grayscale"],2.5];
pos=PixelValuePositions[b,1,.5];

tour=FindShortestTour[pos];

Graphics3D[Line[pos[[tour[[2]]]]]]

Producing a stippled image with Gimp [url]

wolfram=;

wpts=ImageValuePositions[wolfram,Black];

res=FindShortestTour[wpts];

Graphics[Line[wpts[[res[[2]]]]]]

Graphics[{White,Polygon[wpts[[res[[2]]]]]}, Background->Black]