Iteratively strip off simply connected edges in graph?

up vote
2
down vote

favorite

Consider a set of edges composing a directed graph. For example:

edges = DirectedEdge[1, 2], DirectedEdge[2, 3], DirectedEdge[4, 3], DirectedEdge[3, 5], DirectedEdge[5, 6], DirectedEdge[6, 7];
Graph[edges]

I would like to have a function stripOff that iteratively strips off the outer edges that are simply connected to the rest, and returns them together with the remaining graph:

incoming1, outgoing1, remains1= stripOff[edges]
Graph[remains1]

DirectedEdge[1, 2],DirectedEdge[4, 3] ,

DirectedEdge[6, 7] ,

DirectedEdge[2, 3], DirectedEdge[3, 5], DirectedEdge[5, 6]

In the next iteration step it should give

incoming2, outgoing2, remains2= stripOff[remains1]
Graph[remains2]

DirectedEdge[2, 3] ,

DirectedEdge[5, 6] ,

DirectedEdge[3, 5]

And finally in the last iteration step

incoming3, outgoing3, remains3= stripOff[remains2]

DirectedEdge[3, 5] ,

,

Is there a quick way to construct such a stripOff function in mathematica? Thanks for any suggestion!

asked 2 hours ago

Kagaratsch

4,50931246

shouldn't the last step give DirectedEdge[3, 5] ,DirectedEdge[3, 5] , ?
â€“Â kglr
1 hour ago

@kglr I'd like all edges to be unique, without double counting. If an edge triggers for incoming classification, it is spent and is not available to be classified as outgoing any more.
â€“Â Kagaratsch
34 mins ago

add a commentÂ |Â

up vote
2
down vote

favorite

Consider a set of edges composing a directed graph. For example:

edges = DirectedEdge[1, 2], DirectedEdge[2, 3], DirectedEdge[4, 3], DirectedEdge[3, 5], DirectedEdge[5, 6], DirectedEdge[6, 7];
Graph[edges]

I would like to have a function stripOff that iteratively strips off the outer edges that are simply connected to the rest, and returns them together with the remaining graph:

incoming1, outgoing1, remains1= stripOff[edges]
Graph[remains1]

DirectedEdge[1, 2],DirectedEdge[4, 3] ,

DirectedEdge[6, 7] ,

DirectedEdge[2, 3], DirectedEdge[3, 5], DirectedEdge[5, 6]

In the next iteration step it should give

incoming2, outgoing2, remains2= stripOff[remains1]
Graph[remains2]

DirectedEdge[2, 3] ,

DirectedEdge[5, 6] ,

DirectedEdge[3, 5]

And finally in the last iteration step

incoming3, outgoing3, remains3= stripOff[remains2]

DirectedEdge[3, 5] ,

,

Is there a quick way to construct such a stripOff function in mathematica? Thanks for any suggestion!

asked 2 hours ago

Kagaratsch

4,50931246

shouldn't the last step give DirectedEdge[3, 5] ,DirectedEdge[3, 5] , ?
â€“Â kglr
1 hour ago

@kglr I'd like all edges to be unique, without double counting. If an edge triggers for incoming classification, it is spent and is not available to be classified as outgoing any more.
â€“Â Kagaratsch
34 mins ago

add a commentÂ |Â

up vote
2
down vote

favorite

Consider a set of edges composing a directed graph. For example:

edges = DirectedEdge[1, 2], DirectedEdge[2, 3], DirectedEdge[4, 3], DirectedEdge[3, 5], DirectedEdge[5, 6], DirectedEdge[6, 7];
Graph[edges]

I would like to have a function stripOff that iteratively strips off the outer edges that are simply connected to the rest, and returns them together with the remaining graph:

incoming1, outgoing1, remains1= stripOff[edges]
Graph[remains1]

DirectedEdge[1, 2],DirectedEdge[4, 3] ,

DirectedEdge[6, 7] ,

DirectedEdge[2, 3], DirectedEdge[3, 5], DirectedEdge[5, 6]

In the next iteration step it should give

incoming2, outgoing2, remains2= stripOff[remains1]
Graph[remains2]

DirectedEdge[2, 3] ,

DirectedEdge[5, 6] ,

DirectedEdge[3, 5]

And finally in the last iteration step

incoming3, outgoing3, remains3= stripOff[remains2]

DirectedEdge[3, 5] ,

,

Is there a quick way to construct such a stripOff function in mathematica? Thanks for any suggestion!

asked 2 hours ago

Kagaratsch

4,50931246

Consider a set of edges composing a directed graph. For example:

edges = DirectedEdge[1, 2], DirectedEdge[2, 3], DirectedEdge[4, 3], DirectedEdge[3, 5], DirectedEdge[5, 6], DirectedEdge[6, 7];
Graph[edges]

I would like to have a function stripOff that iteratively strips off the outer edges that are simply connected to the rest, and returns them together with the remaining graph:

incoming1, outgoing1, remains1= stripOff[edges]
Graph[remains1]

DirectedEdge[1, 2],DirectedEdge[4, 3] ,

DirectedEdge[6, 7] ,

DirectedEdge[2, 3], DirectedEdge[3, 5], DirectedEdge[5, 6]

In the next iteration step it should give

incoming2, outgoing2, remains2= stripOff[remains1]
Graph[remains2]

DirectedEdge[2, 3] ,

DirectedEdge[5, 6] ,

DirectedEdge[3, 5]

And finally in the last iteration step

incoming3, outgoing3, remains3= stripOff[remains2]

DirectedEdge[3, 5] ,

,

Is there a quick way to construct such a stripOff function in mathematica? Thanks for any suggestion!

list-manipulation function-construction graphs-and-networks

asked 2 hours ago

Kagaratsch

4,50931246

asked 2 hours ago

Kagaratsch

4,50931246

asked 2 hours ago

Kagaratsch

4,50931246

asked 2 hours ago

Kagaratsch

4,50931246

asked 2 hours ago

Kagaratsch

4,50931246

shouldn't the last step give DirectedEdge[3, 5] ,DirectedEdge[3, 5] , ?
â€“Â kglr
1 hour ago

@kglr I'd like all edges to be unique, without double counting. If an edge triggers for incoming classification, it is spent and is not available to be classified as outgoing any more.
â€“Â Kagaratsch
34 mins ago

add a commentÂ |Â

shouldn't the last step give DirectedEdge[3, 5] ,DirectedEdge[3, 5] , ?
â€“Â kglr
1 hour ago

@kglr I'd like all edges to be unique, without double counting. If an edge triggers for incoming classification, it is spent and is not available to be classified as outgoing any more.
â€“Â Kagaratsch
34 mins ago

shouldn't the last step give DirectedEdge[3, 5] ,DirectedEdge[3, 5] , ?
â€“Â kglr
1 hour ago

@kglr I'd like all edges to be unique, without double counting. If an edge triggers for incoming classification, it is spent and is not available to be classified as outgoing any more.
â€“Â Kagaratsch
34 mins ago

add a commentÂ |Â

2 Answers
2

active

oldest

votes

up vote
2
down vote

g = Graph[edges, VertexLabels -> Automatic]

enter image description here

source[g_?GraphQ] := Pick[VertexList[g], VertexInDegree[g], 0]
sink[g_?GraphQ] := Pick[VertexList[g], VertexOutDegree[g], 0]

strip[g_] :=
 With[so = source[g], si = sink[g],
 Flatten[IncidenceList[g, #] & /@ so], 
 Flatten[IncidenceList[g, #] & /@ si], 
 VertexDelete[g, Join[so, si]]
 ]

enter image description here

There are minor issues, such as returning an edge twice at the last step, but that should be easy (if tedious) to fix.

answered 1 hour ago

Szabolcs

156k13423912

add a commentÂ |Â

up vote
2
down vote

sourceEdges = IncidenceList[#, GeneralUtilities`GraphSources @ # ]&;
sinkEdges = Complement[IncidenceList[#, GeneralUtilities`GraphSinks @ #], 
 sourceEdges @ #]&; 
rest = Complement[#, sourceEdges@#, sinkEdges@#] &;
f = Rest @ NestWhileList[sourceEdges @ #[[3]], sinkEdges @ #[[3]], rest @ #[[3]]&,
 , , #, #[[3]] =!= &]&;

f @ edges

1 -> 2, 4 -> 3, 6 -> 7, 2 -> 3, 3 -> 5, 5 -> 6,

2 -> 3, 5 -> 6, 3 -> 5,

3 -> 5, ,

You can also use GraphComputation`SourceVertexList and GraphComputation`SinkVertexList for GeneralUtilities`GraphSources and GeneralUtilities`GraphSinks, respectively.

edited 24 mins ago

answered 57 mins ago

kglr

170k8193396

I wonder if GeneralUtilities'GraphSinks would trigger on 2->3 and 4->3 in a situation like 1->2 , 2->3 , 4->3 , 5->4 , where 2->3 and 4->3 do point to a sink but are not simply connected to the rest of the graph? Asking, since I'd actually like to avoid this in my case.
â€“Â Kagaratsch
42 mins ago

@Kagaratsch, not sure I understand el = 1->2 , 2->3 , 4->3 , 5->4 , but GeneralUtilities`GraphSinks @Flatten[el] gives 3.
â€“Â kglr
33 mins ago

I see, that is what I was afraid of. In my application case I am only looking for sources and sinks which are simply connected to the rest of the graph.
â€“Â Kagaratsch
31 mins ago

@Kagaratsch, sounds like the example in your question does not reflect your requirements accurately. Adding the example in your comment to your post with some explanation would be useful.
â€“Â kglr
18 mins ago

add a commentÂ |Â

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\$","\$"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "387"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f185556%2fiteratively-strip-off-simply-connected-edges-in-graph%23new-answer', 'question_page');

);

Post as a guest

Name

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

up vote
2
down vote

g = Graph[edges, VertexLabels -> Automatic]

enter image description here

source[g_?GraphQ] := Pick[VertexList[g], VertexInDegree[g], 0]
sink[g_?GraphQ] := Pick[VertexList[g], VertexOutDegree[g], 0]

strip[g_] :=
 With[so = source[g], si = sink[g],
 Flatten[IncidenceList[g, #] & /@ so], 
 Flatten[IncidenceList[g, #] & /@ si], 
 VertexDelete[g, Join[so, si]]
 ]

enter image description here

There are minor issues, such as returning an edge twice at the last step, but that should be easy (if tedious) to fix.

answered 1 hour ago

Szabolcs

156k13423912

add a commentÂ |Â

up vote
2
down vote

g = Graph[edges, VertexLabels -> Automatic]

enter image description here

source[g_?GraphQ] := Pick[VertexList[g], VertexInDegree[g], 0]
sink[g_?GraphQ] := Pick[VertexList[g], VertexOutDegree[g], 0]

strip[g_] :=
 With[so = source[g], si = sink[g],
 Flatten[IncidenceList[g, #] & /@ so], 
 Flatten[IncidenceList[g, #] & /@ si], 
 VertexDelete[g, Join[so, si]]
 ]

enter image description here

There are minor issues, such as returning an edge twice at the last step, but that should be easy (if tedious) to fix.

answered 1 hour ago

Szabolcs

156k13423912

add a commentÂ |Â

up vote
2
down vote

g = Graph[edges, VertexLabels -> Automatic]

enter image description here

source[g_?GraphQ] := Pick[VertexList[g], VertexInDegree[g], 0]
sink[g_?GraphQ] := Pick[VertexList[g], VertexOutDegree[g], 0]

strip[g_] :=
 With[so = source[g], si = sink[g],
 Flatten[IncidenceList[g, #] & /@ so], 
 Flatten[IncidenceList[g, #] & /@ si], 
 VertexDelete[g, Join[so, si]]
 ]

enter image description here

There are minor issues, such as returning an edge twice at the last step, but that should be easy (if tedious) to fix.

answered 1 hour ago

Szabolcs

156k13423912

g = Graph[edges, VertexLabels -> Automatic]

enter image description here

source[g_?GraphQ] := Pick[VertexList[g], VertexInDegree[g], 0]
sink[g_?GraphQ] := Pick[VertexList[g], VertexOutDegree[g], 0]

strip[g_] :=
 With[so = source[g], si = sink[g],
 Flatten[IncidenceList[g, #] & /@ so], 
 Flatten[IncidenceList[g, #] & /@ si], 
 VertexDelete[g, Join[so, si]]
 ]

enter image description here

There are minor issues, such as returning an edge twice at the last step, but that should be easy (if tedious) to fix.

answered 1 hour ago

Szabolcs

156k13423912

answered 1 hour ago

Szabolcs

156k13423912

answered 1 hour ago

Szabolcs

156k13423912

answered 1 hour ago

Szabolcs

156k13423912

add a commentÂ |Â

up vote
2
down vote

sourceEdges = IncidenceList[#, GeneralUtilities`GraphSources @ # ]&;
sinkEdges = Complement[IncidenceList[#, GeneralUtilities`GraphSinks @ #], 
 sourceEdges @ #]&; 
rest = Complement[#, sourceEdges@#, sinkEdges@#] &;
f = Rest @ NestWhileList[sourceEdges @ #[[3]], sinkEdges @ #[[3]], rest @ #[[3]]&,
 , , #, #[[3]] =!= &]&;

f @ edges

1 -> 2, 4 -> 3, 6 -> 7, 2 -> 3, 3 -> 5, 5 -> 6,

2 -> 3, 5 -> 6, 3 -> 5,

3 -> 5, ,

You can also use GraphComputation`SourceVertexList and GraphComputation`SinkVertexList for GeneralUtilities`GraphSources and GeneralUtilities`GraphSinks, respectively.

edited 24 mins ago

answered 57 mins ago

kglr

170k8193396

I wonder if GeneralUtilities'GraphSinks would trigger on 2->3 and 4->3 in a situation like 1->2 , 2->3 , 4->3 , 5->4 , where 2->3 and 4->3 do point to a sink but are not simply connected to the rest of the graph? Asking, since I'd actually like to avoid this in my case.
â€“Â Kagaratsch
42 mins ago

@Kagaratsch, not sure I understand el = 1->2 , 2->3 , 4->3 , 5->4 , but GeneralUtilities`GraphSinks @Flatten[el] gives 3.
â€“Â kglr
33 mins ago

I see, that is what I was afraid of. In my application case I am only looking for sources and sinks which are simply connected to the rest of the graph.
â€“Â Kagaratsch
31 mins ago

@Kagaratsch, sounds like the example in your question does not reflect your requirements accurately. Adding the example in your comment to your post with some explanation would be useful.
â€“Â kglr
18 mins ago

add a commentÂ |Â

up vote
2
down vote

sourceEdges = IncidenceList[#, GeneralUtilities`GraphSources @ # ]&;
sinkEdges = Complement[IncidenceList[#, GeneralUtilities`GraphSinks @ #], 
 sourceEdges @ #]&; 
rest = Complement[#, sourceEdges@#, sinkEdges@#] &;
f = Rest @ NestWhileList[sourceEdges @ #[[3]], sinkEdges @ #[[3]], rest @ #[[3]]&,
 , , #, #[[3]] =!= &]&;

f @ edges

1 -> 2, 4 -> 3, 6 -> 7, 2 -> 3, 3 -> 5, 5 -> 6,

2 -> 3, 5 -> 6, 3 -> 5,

3 -> 5, ,

You can also use GraphComputation`SourceVertexList and GraphComputation`SinkVertexList for GeneralUtilities`GraphSources and GeneralUtilities`GraphSinks, respectively.

edited 24 mins ago

answered 57 mins ago

kglr

170k8193396

I wonder if GeneralUtilities'GraphSinks would trigger on 2->3 and 4->3 in a situation like 1->2 , 2->3 , 4->3 , 5->4 , where 2->3 and 4->3 do point to a sink but are not simply connected to the rest of the graph? Asking, since I'd actually like to avoid this in my case.
â€“Â Kagaratsch
42 mins ago

@Kagaratsch, not sure I understand el = 1->2 , 2->3 , 4->3 , 5->4 , but GeneralUtilities`GraphSinks @Flatten[el] gives 3.
â€“Â kglr
33 mins ago

I see, that is what I was afraid of. In my application case I am only looking for sources and sinks which are simply connected to the rest of the graph.
â€“Â Kagaratsch
31 mins ago

@Kagaratsch, sounds like the example in your question does not reflect your requirements accurately. Adding the example in your comment to your post with some explanation would be useful.
â€“Â kglr
18 mins ago

add a commentÂ |Â

up vote
2
down vote

sourceEdges = IncidenceList[#, GeneralUtilities`GraphSources @ # ]&;
sinkEdges = Complement[IncidenceList[#, GeneralUtilities`GraphSinks @ #], 
 sourceEdges @ #]&; 
rest = Complement[#, sourceEdges@#, sinkEdges@#] &;
f = Rest @ NestWhileList[sourceEdges @ #[[3]], sinkEdges @ #[[3]], rest @ #[[3]]&,
 , , #, #[[3]] =!= &]&;

f @ edges

1 -> 2, 4 -> 3, 6 -> 7, 2 -> 3, 3 -> 5, 5 -> 6,

2 -> 3, 5 -> 6, 3 -> 5,

3 -> 5, ,

You can also use GraphComputation`SourceVertexList and GraphComputation`SinkVertexList for GeneralUtilities`GraphSources and GeneralUtilities`GraphSinks, respectively.

edited 24 mins ago

answered 57 mins ago

kglr

170k8193396

sourceEdges = IncidenceList[#, GeneralUtilities`GraphSources @ # ]&;
sinkEdges = Complement[IncidenceList[#, GeneralUtilities`GraphSinks @ #], 
 sourceEdges @ #]&; 
rest = Complement[#, sourceEdges@#, sinkEdges@#] &;
f = Rest @ NestWhileList[sourceEdges @ #[[3]], sinkEdges @ #[[3]], rest @ #[[3]]&,
 , , #, #[[3]] =!= &]&;

f @ edges

1 -> 2, 4 -> 3, 6 -> 7, 2 -> 3, 3 -> 5, 5 -> 6,

2 -> 3, 5 -> 6, 3 -> 5,

3 -> 5, ,

You can also use GraphComputation`SourceVertexList and GraphComputation`SinkVertexList for GeneralUtilities`GraphSources and GeneralUtilities`GraphSinks, respectively.

edited 24 mins ago

answered 57 mins ago

kglr

170k8193396

edited 24 mins ago

answered 57 mins ago

kglr

170k8193396

answered 57 mins ago

kglr

170k8193396

answered 57 mins ago

kglr

170k8193396

I wonder if GeneralUtilities'GraphSinks would trigger on 2->3 and 4->3 in a situation like 1->2 , 2->3 , 4->3 , 5->4 , where 2->3 and 4->3 do point to a sink but are not simply connected to the rest of the graph? Asking, since I'd actually like to avoid this in my case.
â€“Â Kagaratsch
42 mins ago

@Kagaratsch, not sure I understand el = 1->2 , 2->3 , 4->3 , 5->4 , but GeneralUtilities`GraphSinks @Flatten[el] gives 3.
â€“Â kglr
33 mins ago

I see, that is what I was afraid of. In my application case I am only looking for sources and sinks which are simply connected to the rest of the graph.
â€“Â Kagaratsch
31 mins ago

@Kagaratsch, sounds like the example in your question does not reflect your requirements accurately. Adding the example in your comment to your post with some explanation would be useful.
â€“Â kglr
18 mins ago

add a commentÂ |Â

I wonder if GeneralUtilities'GraphSinks would trigger on 2->3 and 4->3 in a situation like 1->2 , 2->3 , 4->3 , 5->4 , where 2->3 and 4->3 do point to a sink but are not simply connected to the rest of the graph? Asking, since I'd actually like to avoid this in my case.
â€“Â Kagaratsch
42 mins ago

@Kagaratsch, not sure I understand el = 1->2 , 2->3 , 4->3 , 5->4 , but GeneralUtilities`GraphSinks @Flatten[el] gives 3.
â€“Â kglr
33 mins ago

I see, that is what I was afraid of. In my application case I am only looking for sources and sinks which are simply connected to the rest of the graph.
â€“Â Kagaratsch
31 mins ago

@Kagaratsch, sounds like the example in your question does not reflect your requirements accurately. Adding the example in your comment to your post with some explanation would be useful.
â€“Â kglr
18 mins ago

I wonder if GeneralUtilities'GraphSinks would trigger on 2->3 and 4->3 in a situation like 1->2 , 2->3 , 4->3 , 5->4 , where 2->3 and 4->3 do point to a sink but are not simply connected to the rest of the graph? Asking, since I'd actually like to avoid this in my case.
â€“Â Kagaratsch
42 mins ago

@Kagaratsch, not sure I understand el = 1->2 , 2->3 , 4->3 , 5->4 , but GeneralUtilities`GraphSinks @Flatten[el] gives 3.
â€“Â kglr
33 mins ago

I see, that is what I was afraid of. In my application case I am only looking for sources and sinks which are simply connected to the rest of the graph.
â€“Â Kagaratsch
31 mins ago

@Kagaratsch, sounds like the example in your question does not reflect your requirements accurately. Adding the example in your comment to your post with some explanation would be useful.
â€“Â kglr
18 mins ago

add a commentÂ |Â

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Search This Blog

Iyfjky