65.9K
CodeProject 正在变化。 阅读更多。
Home

EpForceDirectedGraph.cs - C# 中的 2D/3D 力导向图算法

Chris La
starIconstarIconstarIconstarIconstarIcon

5.00/5 (9投票s)

2014年10月26日

MIT

5分钟阅读

viewsIcon

40321

downloadIcon

1696

C# 中的 2D/3D 力导向图算法

目录

  1. 引言 
  2. 基本用法
  3. 高级用法
  4. 结论
  5. 参考

简介 

我在用 C# 开发游戏 UI 时，想要一个创新的算法。在寻找好的算法的过程中（因为我对常规的基于按钮的 UI 不满意），我发现了一个很棒的 JavaScript 实现，它是一个由 Denniss Hotson 实现的力导向图。然后我想到，“为什么不为 C# 也做一个呢？”于是，它就诞生了！EpForceDirectedGraph.cs！

EpForceDirectedGraph.cs 的工作方式与 Springy 非常相似。

(如果您对力导向图算法的更多细节以及原始的 JavaScript 实现感兴趣，请参阅维基百科的 力导向图绘制 和 Dennis Hotson 的 实现。)

基本用法  

图

为了方便使用，其用法和演示都已做得与 Springy 在线演示 非常相似。

您首先需要一个 Graph 实例。

Graph m_fdgGraph = new Graph();

这个 Graph 实例将用于操作您的力导向图结构，例如添加/删除新节点，添加/删除边等。

节点操作

如何添加节点/节点？

只需在图中添加一个带有名称的新节点

Node newNode = m_fdgGraph.CreateNode("some node label");

您还可以通过修改节点的标签和/或质量来添加带有 NodeData 的新节点

NodeData data = new NodeData();
data.label = "some node label";
data.mass = 3.0f; // Optional
Node newNode = m_fdgGraph.CreateNode(data);

通过手动创建节点和节点数据来将节点添加到图中

NodeData data=new NodeData();
data.mass = 3.0f;
data.label = "some node label" 
Node newNode = new Node("Unique ID", data);
Node createdNode = m_fdgGraph.AddNode(newNode);

您也可以批量添加新节点，使用 string 或 NodeData 的列表

List<string> nodeNames= new List<string>();
...
m_fdgGraph.CreateNodes(nodeNames);
 
// OR

List<NodeData> nodeDatas =new List<NodeData>();
...
m_fdgGraph.CreateNodes(nodeDatas); 

添加节点到图后，您可以通过其 label 轻松获取您添加的节点实例

Node node = m_fdgGraph.GetNode("some node label");
如何删除/分离节点？

从图中删除节点

Node node = m_fdgGraph.GetNode("some node label");
if(node != null)
   m_fdgGraph.RemoveNode(node);

分离节点上的所有边（注意：节点仍然存在于图中）

Node node = m_fdgGraph.GetNode("some node label");
if(node != null)
   m_fdgGraph.DetachNode(node);

边操作

如何添加边/边？

在添加节点后，您可以通过创建边来连接两个节点

Node node1 = m_fdgGraph.GetNode("node1");
Node node2 = m_fdgGraph.GetNode("node2");

EdgeData data= new EdgeData();
data.label = "node1"+"-"+"node2";
data.length = 60.0f;
Edge newEdge = m_fdgGraph.CreateEdge(node1, node2, data);

您还可以直接通过节点的 ID（节点创建时给定的唯一 ID）而不是节点实例来创建新的 Edge

Node node1 = m_fdgGraph.GetNode("node1");
Node node2 = m_fdgGraph.GetNode("node2");

EdgeData data= new EdgeData();
data.label = "node1"+"-"+"node2";
data.length = 60.0f;

Edge newEdge = m_fdgGraph.CreateEdge(node1.ID, node2.ID, data);

通过手动创建边和边数据来将边添加到图中

Node node1 = m_fdgGraph.GetNode("node1");
Node node2 = m_fdgGraph.GetNode("node2");

EdgeData data=new EdgeData();
data.label = "node1"+"-"+"node2";
data.length = 60.0f; 
Edge newEdge = new Edge("Unique ID", node1, node2, data);
Edge createdEdge = m_fdgGraph.AddEdge(newEdge);

您还可以批量添加新边，使用由第一个节点的唯一 ID 字符串、第二个节点的唯一 ID 字符串组成的对的列表，或者由第一个节点的唯一 ID 字符串、第二个节点的唯一 ID 字符串以及边的 EdgeData 组成的列表。

// First string is first node's Unique ID and second string is second node's Unique ID
List<Pair<string,string>> edges= new List<Pair<string,string>>();
...
m_fdgGraph.CreateEdges(edges);
 
// OR

List<Triple<string,string,EdgeData>> edges =new List<Triple<string,string,EdgeData>>();
...
m_fdgGraph.CreateEdges(edges); 

添加边到图后，您可以通过其 label 轻松获取您添加的边实例

Edge edge = m_fdgGraph.GetEdge("node1-node2");

您还可以按如下方式获取连接到节点的边的列表

Node node1 = m_fdgGraph.GetNode("node1");
List<Edge> edgesConnected = m_fdgGraph.GetEdges(node1);

最后，您可以通过以下方式获取连接两个节点之间的边的列表

Node node1 = m_fdgGraph.GetNode("node1");
Node node2 = m_fdgGraph.GetNode("node2");
List<Edge> edgesConnected = m_fdgGraph.GetEdges(node1, node2);
如何删除边？

从图中删除边

Edge edge = m_fdgGraph.GetEdge("node1-node2");
if(edge != null)
   m_fdgGraph.RemoveEdge(edge);

ForceDirected2D/ForceDirected3D

ForceDirected2D 或 ForceDirected3D 是力导向图的物理计算类。ForceDirected2D/3D 的实例将接受 Graph（力导向图的逻辑结构），并被插入到 Renderer 的实例中。

创建 ForceDirected2D/3D 以计算您的力导向图的物理特性

float stiffness = 81.76f;
float repulsion = 40000.0f;
float damping   = 0.5f;

// 2D Force Directed
ForceDirected2D m_fdgPhysics = new ForceDirected2D(m_fdgGraph // instance of Graph
                                                   stiffness, // stiffness of the spring
                                                   repulsion, // node repulsion rate 
                                                   damping    // damping rate  
                                                   );
// OR

// 3D Force Directed
ForceDirected3D m_fdgPhysics = new ForceDirected3D(m_fdgGraph // instance of Graph
                                                   stiffness, // stiffness of the spring
                                                   repulsion, // node repulsion rate
                                                   damping    // damping rate 
                                                   );
如何更改力导向图的物理计算变量？

更改弹簧（边）的刚度

m_fdgPhysics.Stiffness = 90.55f;

更改节点的排斥率

m_fdgPhysics.Repulsion = 50000.0f;

更改阻尼

m_fdgPhysics.Damping = 0.7f;

最后，您还可以设置 Threadshold 以在特定点停止物理迭代（取决于您如何设置阈值，它将影响图计算的性能）

m_fdgPhysics.Threadshold = 0.1f;

这个 ForceDirected2D/3D 在后台完成了大部分工作，例如计算节点和边位置，并将它们插入到 Renderer 以渲染图。

渲染器 (Renderer)

首先，您需要定义自己的 Renderer，它继承自 AbstractRenderer

class Renderer: AbstractRenderer
{
   ...
};

您需要实现三个方法才能使您的力导向图正确渲染。

  • 构造函数 [ base(IForceDirected) ]
    • 在创建您的 Renderer 时，必须将上面创建的 IForceDirected 实例传递给 AbstractRenderer 构造函数。
  • 清除 [ void Clear() ]
    • 清除任何先前的绘制以绘制新场景
    • 这将在 AbstractRenderer::Draw 方法中调用。
  • 绘制边 [ void drawEdge(Edge iEdge, AbstractVector iPosition1, AbstractVector iPosition2) ]
    • 根据给定的位置绘制给定的边
    • 如果使用 ForceDirected2D，AbstractVector 将是 FDGVector2；如果使用 ForceDirected3D，则为 FDGVector3。
  • 绘制节点 [ void drawNode(Node iNode, AbstractVector iPosition) ]
    • 根据给定的位置绘制给定的节点
    • 如果使用 ForceDirected2D，AbstractVector 将是 FDGVector2；如果使用 ForceDirected3D，则为 FDGVector3。
class Renderer: AbstractRenderer
{
   public Renderer(IForceDirected iForceDirected): base(iForceDirected)
   {
      // Your initialization to draw
   }

   public override void Clear()
   {
      // Clear previous drawing if needed
      // will be called when AbstractRenderer:Draw is called
   }
   
   protected override void drawEdge(Edge iEdge, AbstractVector iPosition1, AbstractVector iPosition2)
   {
      // Draw the given edge according to given positions
   }

   protected override void drawNode(Node iNode, AbstractVector iPosition)
   {
      // Draw the given node according to given position
   }
};

然后，以 ForceDirected2D/3D 实例作为参数创建您的 Renderer 实例

Renderer m_fdgRenderer = new Renderer(m_fdgPhysics);

最后，要用您上面创建的渲染器绘制您的 Graph，只需调用 Draw 即可。

float timeStep = 0.05f; // The time passed from previous Draw call in second
m_fdgRenderer.Draw(timeStep);

高级用法  

可扩展性

扩展 NodeData

您可以创建自己的类，继承自 NodeData，并扩展它以存储更多变量，以便以后使用，例如在 Draw 方法中，并使用您版本的 NodeData 来创建节点。

public class MyNodeData: NodeData
{
   public string subType{
      get;set; 
   }
   public MyNodeData(string iSubType):base()
   {
      subType= iSubType;
   }
}

...
MyNodeData data= new MyNodeData("Button");
data.label = "Play";
Node newNode = m_fdgGraph.CreateNode(data);

扩展 EdgeData

与 NodeData 类似，您还可以通过创建自己的类并继承自 EdgeData 来扩展 EdgeData。

public class MyEdgeData: EdgeData
{
   public string subType{
      get;set; 
   }
   public MyEdgeData(string iSubType):base()
   {
      subType= iSubType;
   }
}

...
MyEdgeData data= new MyEdgeData("Button");
data.label= "Play";
Edge newEdge = m_fdgGraph.CreateEdge(data);

图结构变更通知

您可以注册一个监听器类，以便在图结构发生变化时收到通知。监听器类必须实现 IGraphEventListener 接口的 GraphChanged 方法。您可以按如下方式添加监听器：

IGraphEventListener listener = new MyGraphEventListner();
m_fdgGraph.AddGraphListener(listner); // After this point when graph structure changed, 
                                      //   listener.GraphChanged() method will be called

结论  

EpForceDirectedGraph.cs 项目的大部分功能和工作最初都来自于 Dennis Hotson 的 Springy，所以所有的辛勤工作和贡献都应该归功于 Dennis Hotson。我在此展示它的原因，是希望对可能需要在 C# 中使用此算法的任何人有所帮助。

参考文献  

历史

  • 2014.10.27：- 修复了拼写错误
  • 2014.10.26：- 提交了文章 
© . All rights reserved.