i m using this example as base Graph Distances and Paths
My question is that is there a way to find connection between nodes ignoring direction of the links?
I haven’t tried this, but you could change the code to call Node | GoJS API instead of Node.findLinksOutOf or Node.findLinksInto.
i dont think u got my question
consider the following diagram
i want to find the path between A and D ignoring the direction of links because C to D is reverse
When I get a chance later today I’ll see if I can modify that sample for you.
OK, all I did was replace calls to Node.findLinksInto and Node.findLinksOutOf with calls to Node.findLinksConnected, and calls to Node.findNodesInto and Node.findNodesOutOf with calls to Node.findNodesConnected. Also I replaced a call to Node.findLinksTo with a call to Node.findLinksBetween.
Everything just worked. But note that since it’s much easier to create cycles when considering all links as being undirected, the number of all possible paths explodes combinatorially. I hope your app does not need to list all paths between two nodes.
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>Graph Distances and Paths</title>
<meta name="description" content="Interactive diagram showing all distances from a node, and highlighting all paths between two nodes." />
<meta name="viewport" content="width=device-width, initial-scale=1">
<!-- Copyright 1998-2019 by Northwoods Software Corporation. -->
<script src="go.js"></script>
<script src="../assets/js/goSamples.js"></script> <!-- this is only for the GoJS Samples framework -->
<script id="code">
function init() {
if (window.goSamples) goSamples(); // init for these samples -- you don't need to call this
var $ = go.GraphObject.make; // for conciseness in defining templates
myDiagram =
$(go.Diagram, "myDiagramDiv", // must be the ID or reference to div
{
initialAutoScale: go.Diagram.UniformToFill,
padding: 10,
contentAlignment: go.Spot.Center,
layout: $(go.ForceDirectedLayout, { defaultSpringLength: 10 }),
maxSelectionCount: 2
});
// define the Node template
myDiagram.nodeTemplate =
$(go.Node, "Horizontal",
{
locationSpot: go.Spot.Center, // Node.location is the center of the Shape
locationObjectName: "SHAPE",
selectionAdorned: false,
selectionChanged: nodeSelectionChanged
},
$(go.Panel, "Auto",
$(go.Shape, "Ellipse",
{
name: "SHAPE",
fill: "lightgray", // default value, but also data-bound
stroke: "transparent", // modified by highlighting
strokeWidth: 2,
desiredSize: new go.Size(30, 30),
portId: ""
}, // so links will go to the shape, not the whole node
new go.Binding("fill", "isSelected", function(s, obj) { return s ? "red" : obj.part.data.color; }).ofObject()),
$(go.TextBlock,
new go.Binding("text", "distance", function(d) { if (d === Infinity) return "INF"; else return d | 0; }))),
$(go.TextBlock,
new go.Binding("text")));
// define the Link template
myDiagram.linkTemplate =
$(go.Link,
{
selectable: false, // links cannot be selected by the user
curve: go.Link.Bezier,
layerName: "Background" // don't cross in front of any nodes
},
$(go.Shape, // this shape only shows when it isHighlighted
{ isPanelMain: true, stroke: null, strokeWidth: 5 },
new go.Binding("stroke", "isHighlighted", function(h) { return h ? "red" : null; }).ofObject()),
$(go.Shape,
// mark each Shape to get the link geometry with isPanelMain: true
{ isPanelMain: true, stroke: "black", strokeWidth: 1 },
new go.Binding("stroke", "color")),
$(go.Shape, { toArrow: "Standard" })
);
// Override the clickSelectingTool's standardMouseSelect
// If less than 2 nodes are selected, always add to the selection
myDiagram.toolManager.clickSelectingTool.standardMouseSelect = function() {
var diagram = this.diagram;
if (diagram === null || !diagram.allowSelect) return;
var e = diagram.lastInput;
var count = diagram.selection.count;
var curobj = diagram.findPartAt(e.documentPoint, false);
if (curobj !== null) {
if (count < 2) { // add the part to the selection
if (!curobj.isSelected) {
var part = curobj;
if (part !== null) part.isSelected = true;
}
} else {
if (!curobj.isSelected) {
var part = curobj;
if (part !== null) diagram.select(part);
}
}
} else if (e.left && !(e.control || e.meta) && !e.shift) {
// left click on background with no modifier: clear selection
diagram.clearSelection();
}
}
generateGraph();
// select two nodes that connect from the first one to the second one
var num = myDiagram.model.nodeDataArray.length;
var node1 = null;
var node2 = null;
for (var i = 0; i < num; i++) {
node1 = myDiagram.findNodeForKey(i);
var distances = findDistances(node1);
for (var j = 0; j < num; j++) {
node2 = myDiagram.findNodeForKey(j);
var dist = distances.get(node2);
if (dist > 1 && dist < Infinity) {
node1.isSelected = true;
node2.isSelected = true;
break;
}
}
if (myDiagram.selection.count > 0) break;
}
}
function generateGraph() {
var names = [
"Joshua", "Kathryn", "Robert", "Jason", "Scott", "Betsy", "John",
"Walter", "Gabriel", "Simon", "Emily", "Tina", "Elena", "Samuel",
"Jacob", "Michael", "Juliana", "Natalie", "Grace", "Ashley", "Dylan"
];
var nodeDataArray = [];
for (var i = 0; i < names.length; i++) {
nodeDataArray.push({ key: i, text: names[i], color: go.Brush.randomColor(128, 240) });
}
var linkDataArray = [];
var num = nodeDataArray.length;
for (var i = 0; i < num * 2; i++) {
var a = Math.floor(Math.random() * num);
var b = Math.floor(Math.random() * num / 4) + 1;
linkDataArray.push({ from: a, to: (a + b) % num, color: go.Brush.randomColor(0, 127) });
}
myDiagram.model = new go.GraphLinksModel(nodeDataArray, linkDataArray);
}
// There are three bits of functionality here:
// 1: findDistances(Node) computes the distance of each Node from the given Node.
// This function is used by showDistances to update the model data.
// 2: findShortestPath(Node, Node) finds a shortest path from one Node to another.
// This uses findDistances. This is used by highlightShortestPath.
// 3: collectAllPaths(Node, Node) produces a collection of all paths from one Node to another.
// This is used by listAllPaths. The result is remembered in a global variable
// which is used by highlightSelectedPath. This does not depend on findDistances.
// Returns a Map of Nodes with distance values from the given source Node.
// Assumes all links are unidirectional.
function findDistances(source) {
var diagram = source.diagram;
// keep track of distances from the source node
var distances = new go.Map(/*go.Node, "number"*/);
// all nodes start with distance Infinity
var nit = diagram.nodes;
while (nit.next()) {
var n = nit.value;
distances.set(n, Infinity);
}
// the source node starts with distance 0
distances.set(source, 0);
// keep track of nodes for which we have set a non-Infinity distance,
// but which we have not yet finished examining
var seen = new go.Set(/*go.Node*/);
seen.add(source);
// keep track of nodes we have finished examining;
// this avoids unnecessary traversals and helps keep the SEEN collection small
var finished = new go.Set(/*go.Node*/);
while (seen.count > 0) {
// look at the unfinished node with the shortest distance so far
var least = leastNode(seen, distances);
var leastdist = distances.get(least);
// by the end of this loop we will have finished examining this LEAST node
seen.delete(least);
finished.add(least);
// look at all Links connected with this node
var it = least.findLinksConnected();
while (it.next()) {
var link = it.value;
var neighbor = link.getOtherNode(least);
// skip nodes that we have finished
if (finished.has(neighbor)) continue;
var neighbordist = distances.get(neighbor);
// assume "distance" along a link is unitary, but could be any non-negative number.
var dist = leastdist + 1; //Math.sqrt(least.location.distanceSquaredPoint(neighbor.location));
if (dist < neighbordist) {
// if haven't seen that node before, add it to the SEEN collection
if (neighbordist === Infinity) {
seen.add(neighbor);
}
// record the new best distance so far to that node
distances.set(neighbor, dist);
}
}
}
return distances;
}
// This helper function finds a Node in the given collection that has the smallest distance.
function leastNode(coll, distances) {
var bestdist = Infinity;
var bestnode = null;
var it = coll.iterator;
while (it.next()) {
var n = it.value;
var dist = distances.get(n);
if (dist < bestdist) {
bestdist = dist;
bestnode = n;
}
}
return bestnode;
}
// Find a path that is shortest from the BEGIN node to the END node.
// (There might be more than one, and there might be none.)
function findShortestPath(begin, end) {
// compute and remember the distance of each node from the BEGIN node
distances = findDistances(begin);
// now find a path from END to BEGIN, always choosing the adjacent Node with the lowest distance
var path = new go.List();
path.add(end);
while (end !== null) {
var next = leastNode(end.findNodesConnected(), distances);
if (next !== null) {
if (distances.get(next) < distances.get(end)) {
path.add(next); // making progress towards the beginning
} else {
next = null; // nothing better found -- stop looking
}
}
end = next;
}
// reverse the list to start at the node closest to BEGIN that is on the path to END
// NOTE: if there's no path from BEGIN to END, the first node won't be BEGIN!
path.reverse();
return path;
}
// Recursively walk the graph starting from the BEGIN node;
// when reaching the END node remember the list of nodes along the current path.
// Finally return the collection of paths, which may be empty.
// This assumes all links are unidirectional.
function collectAllPaths(begin, end) {
var stack = new go.List(/*go.Node*/);
var coll = new go.List(/*go.List*/);
function find(source, end) {
source.findNodesConnected().each(function(n) {
if (n === source) return; // ignore reflexive links
if (n === end) { // success
var path = stack.copy();
path.add(end); // finish the path at the end node
coll.add(path); // remember the whole path
} else if (!stack.has(n)) { // inefficient way to check having visited
stack.add(n); // remember that we've been here for this path (but not forever)
find(n, end);
stack.removeAt(stack.count - 1);
} // else might be a cycle
});
}
stack.add(begin); // start the path at the begin node
find(begin, end);
return coll;
}
// Return a string representation of a path for humans to read.
function pathToString(path) {
var s = path.length + ": ";
for (var i = 0; i < path.length; i++) {
if (i > 0) s += " -- ";
s += path.get(i).data.text;
}
return s;
}
// When a node is selected show distances from the first selected node.
// When a second node is selected, highlight the shortest path between two selected nodes.
// If a node is deselected, clear all highlights.
function nodeSelectionChanged(node) {
var diagram = node.diagram;
if (diagram === null) return;
diagram.clearHighlighteds();
if (node.isSelected) {
// when there is a selection made, always clear out the list of all paths
var sel = document.getElementById("myPaths");
sel.innerHTML = "";
// show the distance for each node from the selected node
var begin = diagram.selection.first();
showDistances(begin);
if (diagram.selection.count === 2) {
var end = node; // just became selected
// highlight the shortest path
highlightShortestPath(begin, end);
// list all paths
listAllPaths(begin, end);
}
}
}
// Have each node show how far it is from the BEGIN node.
function showDistances(begin) {
// compute and remember the distance of each node from the BEGIN node
distances = findDistances(begin);
// show the distance on each node
var it = distances.iterator;
while (it.next()) {
var n = it.key;
var dist = it.value;
myDiagram.model.setDataProperty(n.data, "distance", dist);
}
}
// Highlight links along one of the shortest paths between the BEGIN and the END nodes.
// Assume links are unidirectional.
function highlightShortestPath(begin, end) {
highlightPath(findShortestPath(begin, end));
}
// List all paths from BEGIN to END
function listAllPaths(begin, end) {
// compute and remember all paths from BEGIN to END: Lists of Nodes
paths = collectAllPaths(begin, end);
// update the Selection element with a bunch of Option elements, one per path
var sel = document.getElementById("myPaths");
sel.innerHTML = ""; // clear out any old Option elements
paths.each(function(p) {
var opt = document.createElement("option");
opt.text = pathToString(p);
sel.add(opt, null);
});
sel.onchange = highlightSelectedPath;
}
// A collection of all of the paths between a pair of nodes, a List of Lists of Nodes
var paths = null;
// This is only used for listing all paths for the selection onchange event.
// When the selected item changes in the Selection element,
// highlight the corresponding path of nodes.
function highlightSelectedPath() {
var sel = document.getElementById("myPaths");
var idx = sel.selectedIndex;
var opt = sel.options[idx];
var val = opt.value;
highlightPath(paths.get(sel.selectedIndex));
}
// Highlight a particular path, a List of Nodes.
function highlightPath(path) {
myDiagram.clearHighlighteds();
for (var i = 0; i < path.count - 1; i++) {
var f = path.get(i);
var t = path.get(i + 1);
f.findLinksBetween(t).each(function(l) { l.isHighlighted = true; });
}
}
</script>
</head>
<body onload="init()">
<div id="sample">
<div id="myDiagramDiv" style="border: solid 1px black; background: white; width: 100%; height: 700px"></div>
Click on a node to show distances between that node and each other node.
Click on a second node to show a shortest path between the first node and the second node.
(Note that there might not be any path between the nodes.)
<p>
Clicking on a third node will de-select the first two.
<p>
Here is a list of all paths between the first and second selected nodes.
Select a path to highlight it in the diagram.
</p>
<select id="myPaths" style="min-width:100px" size="10"></select>
</div>
</body>
</html>
thankyou it works for me